Algorithmes "en ligne" (itérateurs) pour l'estimation de la médiane, du mode, de l'asymétrie et de l'aplatissement statistiques ?

Question

Existe-t-il un algorithme permettant d'estimer la médiane, le mode, l'asymétrie et/ou l'aplatissement d'un ensemble de valeurs, mais qui ne nécessite PAS de stocker toutes les valeurs en mémoire en même temps ?

J'aimerais calculer les statistiques de base :

• moyenne : moyenne arithmétique
• variance : moyenne des écarts au carré par rapport à la moyenne.
• écart-type : racine carrée de la variance
• médiane : valeur qui sépare la moitié la plus grande des nombres de la moitié la plus petite.
• mode : valeur la plus fréquente trouvée dans l'ensemble
• asymétrie : tl ; dr
• aplatissement : tl ; dr

Les formules de base pour calculer n'importe lequel de ces éléments relèvent de l'arithmétique de l'école primaire, et je les connais. Il existe de nombreuses bibliothèques de statistiques qui les mettent en œuvre, également.

Mon problème est le grand nombre (des milliards) de valeurs dans les ensembles que je manipule : En travaillant en Python, je ne peux pas simplement créer une liste ou un hachage avec des milliards d'éléments. Même si je l'avais écrit en C, les tableaux de milliards d'éléments ne sont pas très pratiques.

Les données ne sont pas triées. Elles sont produites aléatoirement, à la volée, par d'autres processus. La taille de chaque ensemble est très variable, et les tailles ne sont pas connues à l'avance.

J'ai déjà trouvé comment gérer la moyenne et la variance assez bien, en itérant à travers chaque valeur de l'ensemble dans n'importe quel ordre. (En fait, dans mon cas, je les prends dans l'ordre dans lequel elles sont générées.) Voici l'algorithme que j'utilise, avec courtoisie http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm :

• Initialiser trois variables : le nombre, la somme et la somme des carrés.
• Pour chaque valeur :
  • Comptage des incréments.
  • Ajoutez la valeur à la somme.
  • Ajoutez le carré de la valeur à sum_of_squares.
• Diviser la somme par le nombre, en stockant comme variable la moyenne.
• Diviser la somme des carrés par le nombre, en stockant comme variable la moyenne des carrés.
• Moyenne carrée, stockée comme square_of_mean.
• Soustraire la moyenne_carrée de la moyenne_des_carrés, en la stockant comme variance.
• Moyenne et variance de la sortie.

Cet algorithme "en ligne" présente des faiblesses (par exemple, des problèmes de précision lorsque la somme des carrés dépasse rapidement la plage des entiers ou la précision des flottants), mais il me donne essentiellement ce dont j'ai besoin, sans avoir à stocker chaque valeur de chaque ensemble.

Mais je ne sais pas si des techniques similaires existent pour estimer les statistiques supplémentaires (médiane, mode, asymétrie, aplatissement). Je pourrais m'accommoder d'un estimateur biaisé, ou même d'une méthode qui compromet la précision dans une certaine mesure, tant que la mémoire requise pour traiter N valeurs est sensiblement inférieure à O(N).

Il serait également utile de m'indiquer une bibliothèque de statistiques existante, si celle-ci dispose de fonctions permettant de calculer une ou plusieurs de ces opérations "en ligne".

Answer 1

J'utilise ces estimateurs incrémentiels/récurrents de la moyenne et de la médiane, qui utilisent tous deux un stockage constant :

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

où eta est un petit paramètre de taux d'apprentissage (par exemple, 0,001), et sgn () est la fonction signum qui renvoie l'un de {-1, 0, 1}. (Utilisez une constante eta si les données sont non stationnaires et que vous voulez suivre les changements dans le temps ; sinon, pour les sources stationnaires, vous pouvez utiliser quelque chose comme eta \=1/n pour l'estimateur moyen, où n est le nombre d'échantillons vus jusqu'à présent... malheureusement, cela ne semble pas fonctionner pour l'estimateur médian).

Ce type d'estimateur incrémental de la moyenne semble être utilisé partout, par exemple dans les règles d'apprentissage des réseaux neuronaux non supervisés, mais la version médiane semble beaucoup moins courante, malgré ses avantages (robustesse aux valeurs aberrantes). Il semble que la version médiane pourrait être utilisée en remplacement de l'estimateur de la moyenne dans de nombreuses applications.

J'aimerais bien voir un estimateur de mode incrémental d'une forme similaire...

UPDATE

Je viens de modifier l'estimateur incrémental de la médiane pour estimer des quantiles arbitraires. En général, une fonction quantile ( http://en.wikipedia.org/wiki/Quantile_function ) vous indique la valeur qui divise les données en deux fractions : p et 1-p. Ce qui suit estime cette valeur de manière incrémentielle :

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

La valeur p doit être comprise entre [0,1]. Ceci déplace essentiellement le sgn () pour pencher d'un côté, en partitionnant les échantillons de données en deux bacs de taille inégale (les fractions p et 1-p des données sont respectivement inférieures/grandes à l'estimation du quantile). Notez que pour p=0,5, cela se réduit à l'estimateur médian.

Answer 2

Skewness et Kurtosis

Pour les algorithmes en ligne pour Skewness et Kurtosis (sur le modèle de la variance), voir dans la même page wiki ici les algorithmes parallèles pour les statistiques à moment élevé.

Médiane

La médiane est difficile sans données triées. Si vous connaissez le nombre de points de données dont vous disposez, il vous suffit en théorie de trier partiellement les données, par exemple en utilisant un fichier de type algorithme de sélection . Cependant, cela n'est pas très utile avec des milliards de valeurs. Je vous suggère d'utiliser les comptes de fréquence, voir la section suivante.

Médiane et mode avec les compteurs de fréquence

S'il s'agit d'entiers, je compterais fréquences Il est probable que les valeurs les plus élevées et les plus basses soient coupées au-delà d'une certaine valeur où je suis sûr qu'elles ne sont plus pertinentes. Pour les flottants (ou trop d'entiers), je créerais probablement des buckets / intervalles, puis j'utiliserais la même approche que pour les entiers. Le calcul (approximatif) du mode et de la médiane devient alors facile, sur la base du tableau des fréquences.

Variables aléatoires normalement distribuées

S'il est normalement distribué, j'utiliserais l'échantillon de population. moyenne , variance , asymétrie et aplatissement comme estimateurs du maximum de vraisemblance pour un petit sous-ensemble. Les algorithmes (en ligne) pour les calculer, vous les connaissez déjà. Par exemple, lisez quelques centaines de milliers ou millions de points de données, jusqu'à ce que votre erreur d'estimation devienne suffisamment faible. Assurez-vous simplement que vous choisissez au hasard dans votre ensemble (par exemple, que vous n'introduisez pas de biais en choisissant les 100 000 premières valeurs). La même approche peut également être utilisée pour estimer le mode et la médiane dans le cas normal (pour les deux, la moyenne de l'échantillon est un estimateur).

Autres commentaires

Tous les algorithmes ci-dessus peuvent être exécutés en parallèle (y compris de nombreux algorithmes de tri et de sélection, par exemple QuickSort et QuickSelect), si cela peut vous aider.

J'ai toujours supposé (à l'exception de la section sur la distribution normale) que nous parlions des moments de l'échantillon, de la médiane et du mode, et non des estimateurs des moments théoriques étant donné une distribution connue.

En général, l'échantillonnage des données (c'est-à-dire l'examen d'un sous-ensemble seulement) devrait donner de bons résultats compte tenu de la quantité de données, tant que toutes les observations sont des réalisations de la même variable aléatoire (ont les mêmes distributions) et que les moments, le mode et la médiane existent réellement pour cette distribution. La dernière mise en garde n'est pas anodine. Par exemple, la moyenne (et tous les moments supérieurs) pour la variable aléatoire Distribution de Cauchy n'existent pas. Dans ce cas, la moyenne de l'échantillon d'un "petit" sous-ensemble peut être très éloignée de la moyenne de l'ensemble de l'échantillon.

Answer 3

J'ai mis en œuvre le Algorithme P-carré pour le calcul dynamique des quantiles et des histogrammes sans stockage des observations dans un module Python que j'ai écrit et qui s'appelle LiveStats . Elle devrait résoudre votre problème de manière assez efficace. La bibliothèque prend en charge toutes les statistiques que vous mentionnez, sauf le mode. Je n'ai pas encore trouvé de solution satisfaisante pour l'estimation du mode.

Answer 4

Ryan, j'ai peur que tu ne fasses pas la moyenne et la variance correctement... C'est arrivé il y a quelques semaines ici . Et l'un des points forts de la version en ligne (qui porte en fait le nom de méthode de Welford) est le fait qu'elle est particulièrement précise et stable, cf. la discussion ici . L'un des points forts est le fait que vous n'avez pas besoin de stocker la somme totale ou la somme totale des carrés...

Je ne vois pas d'approche en ligne pour le mode et la médiane, qui semblent nécessiter de considérer toute la liste en même temps. Mais il se peut très bien qu'une approche similaire à celle utilisée pour la variance et la moyenne fonctionne également pour l'asymétrie et l'aplatissement...

Answer 5

L'article de Wikipedia cité dans la question contient les formules pour calculer l'asymétrie et l'aplatissement en ligne.

Pour le mode - je crois - il n'y a pas moyen de faire cela en ligne. Pourquoi ? Supposons que toutes les valeurs de votre entrée soient différentes à l'exception de la dernière qui duplique une valeur précédente. Dans ce cas, vous devez vous souvenir de toutes les valeurs déjà vues dans l'entrée pour détecter que la dernière valeur duplique une valeur vue précédemment et en fait la plus fréquente.

Pour la médiane, c'est presque la même chose - jusqu'à la dernière entrée, vous ne savez pas quelle valeur deviendra la médiane si toutes les valeurs d'entrée sont différentes, car elle pourrait être avant ou après la médiane actuelle. Si vous connaissez la longueur de l'entrée, vous pouvez trouver la médiane sans stocker toutes les valeurs en mémoire, mais vous devrez quand même en stocker un grand nombre (je suppose autour de la moitié) parce qu'une mauvaise séquence d'entrée pourrait décaler fortement la médiane dans la seconde moitié, faisant éventuellement de n'importe quelle valeur de la première moitié la médiane.

(Notez que je me réfère uniquement à un calcul exact).