Est-il possible d'accumuler un ensemble de statistiques décrivant un grand nombre d'échantillons afin que je puisse ensuite produire un boxplot?

22

Je dois clarifier immédiatement que je suis un développeur de logiciels pratiquant, pas un statisticien, et que mon cours de statistiques au collège était il y a très longtemps…

Cela dit, j'aimerais savoir s'il existe une méthode pour accumuler un ensemble de statistiques descriptives qui pourraient ensuite être utilisées pour produire un boxplot, qui n'implique pas le stockage d'un tas d'échantillons individuels?

Ce que j'essaie de faire est de produire un résumé graphique des temps de service de file d'attente dans un processus complexe à plusieurs files d'attente. Dans le passé, j'ai utilisé un package appelé tnftools qui permettait d'accumuler de gros échantillons et de les post-traiter dans un joli graphique des temps de réponse et des valeurs aberrantes… Mais les tnftools ne sont pas disponibles pour ma plate-forme actuelle.

Idéalement, j'aimerais pouvoir accumuler un ensemble de statistiques descriptives "à la volée" au cours du processus, puis extraire les données pour analyse à la demande. Mais je ne peux pas simplement faire accumuler des échantillons par le processus car la mémoire / E / S impliquée dans cette opération aurait un impact inacceptable sur les performances du système.

Colclasure de Kaelin
la source
Kaelin:> voulez-vous dire s'il existe une méthode «à la volée» pour calculer les statistiques récapitulatives telles que la médiane et les quartiles? Si c'est ce que vous voulez, je pourrais vous donner des liens vers des articles les détaillant. Vous pouvez également donner plus de détails sur les plates-formes sur lesquelles vous travaillez, car une implémentation GNU efficace de ces méthodes existe probablement dans R.
user603
@kwak: Oui, cela ressemble à ce que je recherche. J'apprécierais grandement ces liens. :-) Je travaille sur Mac OS X… Je peux utiliser R pour les données de post-traitement, mais je ne peux pas lier le code GPL au produit de mon entreprise pour les raisons habituelles.
Kaelin Colclasure

Réponses:

27

Pour le boxplot «à la volée», vous aurez besoin des quartiles «à la volée» min / max (triviaux) et «à la volée» (0,25,0,5 = médiane et 0,75).

Beaucoup de travaux ont été effectués récemment sur le problème de l'algorithme en ligne (ou «à la volée») pour le calcul médian.

Un développement récent est binmedian . En tant que side-kick, il bénéficie également d'une meilleure complexité dans le pire des cas que quickselect (qui n'est ni en ligne ni en un seul passage).

Vous pouvez trouver le papier associé ainsi que le code C et FORTRAN en ligne ici . Vous devrez peut-être vérifier les détails de la licence auprès des auteurs.

Vous aurez également besoin d'un algorithme à passage unique pour les quartiles, pour lequel vous pouvez utiliser l'approche ci-dessus et la caractérisation récursive suivante des quartiles en termes de médianes:

Q0,75(X)Q0,5(Xje:Xje>Q0,5(X))

et

Q0,25(X)Q0,5(Xje:Xje<Q0,5(X))

c'est-à-dire que le quartile de 25 (75) pour cent est très proche de la médiane des observations qui sont plus petites (plus grandes) que la médiane.

Addenda:

Il existe une multitude d'anciennes méthodes multi-passes pour le calcul des quantiles. Une approche populaire consiste à maintenir / mettre à jour un réservoir d'observations de taille déterministe sélectionné au hasard dans le cours d'eau et à calculer récursivement des quantiles (voir cette revue) sur ce réservoir. Cette approche (et connexe) est remplacée par celle proposée ci-dessus.

user603
la source
1
+1 à droite; J'étais encore dans un âge sombre pour faire une approximation à partir de l'histogramme.
Dois-je bien comprendre qu'une telle définition récursive des quartiles à partir des médianes nécessite deux passes si elle est implémentée naïvement? Connaissez-vous les algorithmes à passage unique?
Quartz
@Quartz: non, une seule passe suffira: vous avez deux, une seule passe, exécutant des calculs médians.
user603
2

Au lieu de simplement trouver la médiane, il existe un algorithme qui maintient directement un histogramme estimé: " l'algorithme du carré P pour le calcul dynamique des quantiles et des histogrammes sans stocker les observations". Ce sera probablement beaucoup plus efficace que le binning répété pour chaque quantile souhaité.

Neil G
la source