Calculer des quantiles approximatifs pour un flux d'entiers en utilisant des moments?

migré depuis math.stackexchange .

Je traite un long flux d'entiers et j'envisage de suivre quelques instants afin de pouvoir calculer approximativement divers centiles pour le flux sans stocker beaucoup de données. Quelle est la façon la plus simple de calculer des centiles à partir de quelques instants. Existe-t-il une meilleure approche qui implique de ne stocker qu'une petite quantité de données?

Vous ne le dites pas explicitement, mais d'après votre description du problème, il semble probable que vous recherchiez un ensemble de quantiles fortement biaisé (par exemple, 50e, 90e, 95e et 99e centiles).

Si tel est le cas, j'ai eu beaucoup de succès avec la méthode décrite dans «Calcul efficace des quantiles biaisés sur les flux de données» par Cormode et al. C'est un algorithme rapide qui nécessite peu de mémoire et qui est facile à mettre en œuvre.

La méthode est basée sur un algorithme antérieur de Greenwald et Khanna qui maintient un petit échantillon du flux d'entrée ainsi que des limites supérieure et inférieure sur le rang des valeurs dans l'échantillon. Elle nécessite plus d'espace qu'une collection de quelques instants, mais sera bien meilleure pour décrire avec précision la région de queue intéressante de la distribution.

Il existe un algorithme plus récent et beaucoup plus simple pour cela qui fournit de très bonnes estimations des quantiles extrêmes.

$q$

Voir https://github.com/tdunning/t-digest