Comment calculer ou approchée de la médiane d'une liste sans stocker la liste

j'essaie de calculer la médiane d'un ensemble de valeurs, mais je ne veux pas stocker toutes les valeurs car cela pourrait nuire aux exigences de mémoire. Existe-t-il un moyen de calculer ou d'approximer la médiane sans stocker et trier toutes les valeurs individuelles?

idéalement, je voudrais écrire mon code un peu comme le suivant 

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

Tout ce dont j'ai besoin c'est le vrai code du calculateur!

mise à Jour: certaines personnes ont demandé si les valeurs que j'essaie de calculer la médiane pour avoir des propriétés connues. La réponse est oui. Une valeur de 0.5 incréments d'environ -25 à -0.5. L'autre est également en 0.5 incréments de -120 à -60. Je suppose que cela signifie que je peux utiliser une certaine forme d'histogramme pour chaque valeur.

Merci

Nick

38
demandé sur Noha Kareem 2009-03-12 13:28:59

9 réponses

si les valeurs sont discrètes et que le nombre de valeurs distinctes n'est pas trop élevé, vous pouvez simplement accumuler le nombre de fois que chaque valeur se produit dans un histogramme, puis trouver la médiane à partir des comptes de l'histogramme (additionnez juste les comptes du haut et du bas de l'histogramme jusqu'à ce que vous atteigniez le milieu). Ou s'il s'agit de valeurs continues, vous pouvez les distribuer dans des bacs - cela ne vous indiquerait pas la médiane exacte, mais cela vous donnerait une plage, et si vous avez besoin d'en savoir plus précisément, vous pourriez itérer sur la liste de nouveau, en examinant uniquement les éléments dans le centre de la corbeille.

40
répondu David Z 2014-02-13 00:43:29

il y a la statistique "remedian". Il fonctionne en mettant d'abord en place K tableaux, chacun de longueur B. Les valeurs de données sont introduites dans le premier tableau et, lorsque celui-ci est plein, la médiane est calculée et stockée dans le premier pos du tableau suivant, après quoi le premier tableau est réutilisé. Lorsque le second tableau est plein, la médiane de ses valeurs est stockée dans la première position du Troisième tableau, etc. etc. Vous avez l'idée :)

c'est simple et assez robuste. La référence est ici...

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf

Espérons que cette aide

Michael

35
répondu michael 2015-09-02 22:18:30

j'utilise ces estimateurs de moyenne et de médiane incrémentielles/récursives, qui utilisent tous deux le 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 un de {-1, 0, 1}.

ce type d'estimateur de moyenne incrémentale semble être utilisé partout, par exemple dans les règles d'apprentissage non supervisées des réseaux neuronaux, mais la version médiane semble beaucoup moins courante, malgré son avantages (robustesse aux valeurs aberrantes). Il semble que la version médiane pourrait être utilisée pour remplacer l'estimateur moyen dans de nombreuses applications.

j'aimerais voir un mode incrémental estimateur de forme similaire...

(Note: j'ai également posté sur un sujet similaire ici: "on-line" (itérateur) algorithmes pour l'estimation statistique de la médiane, le mode, l'asymétrie, aplatissement? )

16
répondu Tyler Streeter 2017-05-23 12:18:27

Voici une approche folle que vous pourriez essayer. C'est un problème classique en streaming algorithmes. Les règles sont

  1. Vous avez peu de mémoire, dire O(log n) où n est le nombre d'éléments que vous voulez
  2. vous pouvez regarder chaque article une fois et prendre une décision puis et là ce qu'il faut en faire, si vous le stocker, il coûte la mémoire, si vous le jeter il est parti pour toujours.

l'idée pour le résultat une médiane est simple. Exemple O(1 / a^2 * log(1 / p)) * log(n) éléments de la liste au hasard, vous pouvez le faire par échantillonnage de réservoir (voir question précédente ). Maintenant, il suffit de retourner la médiane de vos éléments échantillonnés, en utilisant une méthode classique.

La garantie est que l'index de l'article retourné sera (1 +/- a) / 2 avec une probabilité d'au moins 1-p . Donc il y a une probabilité p d'échouer, vous pouvez le choisir en échantillonnant plus d'éléments. Et il ne retournera pas la médiane ou la garantie que la valeur de l'article retourné est n'importe où proche de la médiane, juste que lorsque vous triez la liste l'article retourné sera proche de la moitié de la liste.

cet algorithme utilise O(log n) espace supplémentaire et s'exécute en temps linéaire.

13
répondu Pall Melsted 2018-06-20 19:48:23

c'est difficile d'obtenir la bonne réponse en général, surtout pour gérer les séries dégénérées qui sont déjà triées, ou qui ont un tas de valeurs au" début " de la liste, mais la fin de la liste a des valeurs dans une gamme différente.

l'idée de base de faire un histogramme est très prometteuse. Cela vous permet d'accumuler des informations de distribution et d'y répondre à des questions (comme la médiane). La médiane sera approximative puisque vous ne stockez évidemment pas toutes les valeurs. L'espace de stockage est corrigé pour qu'il fonctionne avec n'importe quelle séquence de longueur que vous avez.

mais vous ne pouvez pas simplement construire un histogramme à partir des 100 premières valeurs et utiliser cet histogramme en permanence.. la modification des données peut invalider cet histogramme. Donc vous avez besoin d'un histogramme dynamique qui peut changer sa portée et les bacs à la volée.

faire une structure qui a N bacs. Vous stockerez la valeur X de chaque transition de fente (n+1 Valeurs total) ainsi que la population de la corbeille.

Flux dans vos données. Enregistrer les premières valeurs N+1. Si le flux se termine avant cela, SUPER, vous avez toutes les valeurs chargées et vous pouvez trouver la médiane exacte et la retourner. Sinon, utilisez les valeurs pour définir votre premier histogramme. Il suffit de trier les valeurs et utiliser ceux-ci comme définitions bin, chaque bin ayant une population de 1. C'est normal d'avoir des dupes (bacs de 0 Largeur).

affiche maintenant de nouvelles valeurs. Pour chacun d'eux, recherche binaire pour trouver la corbeille à laquelle il appartient. Dans le cas courant, on augmente la population de cette cellule et on continue. Si votre échantillon est au-delà des bords de l'histogramme (le plus haut ou le plus bas), il suffit d'étendre la portée du bac d'extrémité pour l'inclure. Lorsque votre flux est terminé, vous trouvez la valeur médiane de l'échantillon en trouvant la cellule qui a la population égale sur les deux côtés de celui-ci, et en interpolant linéairement la largeur restante de la cellule.

mais ce n'est pas assez.. vous devez encore adapter l'histogramme aux données au fur et à mesure qu'il est diffusé. Lorsque une corbeille est pleine à craquer, vous perdez des informations sur la sous-distribution de la corbeille. Vous pouvez corriger cela en vous adaptant sur la base d'une certaine heuristique... La plus facile et la plus robuste est que si un bac atteint une certaine population de seuil (quelque chose comme 10*v/N où v=# de valeurs vues jusqu'ici dans le flux, et N est le nombre de bacs), vous divisez ce bac overfull. Ajouter une nouvelle valeur au milieu de la corbeille, donner de chaque côté la moitié de la population de la corbeille originale. Mais maintenant vous avez trop de bacs, donc vous avez besoin pour supprimer une corbeille. Un bon heuristique pour cela est de trouver la bin avec le plus petit produit de la population et la largeur. Supprimez - le et fusionnez-le avec son voisin de gauche ou de droite (celui des voisins lui-même a le plus petit produit de la largeur et de la population.). Fait! Notez que la fusion ou le fractionnement des bacs perd de l'information, mais c'est inévitable.. vous n'avez de stockage fixe.

cet algorithme est agréable en ce qu'il traitera avec tous types d'entrée les ruisseaux et donnent de bons résultats. Si vous avez le luxe de choisir la commande d'échantillon, un échantillon aléatoire est préférable, car cela minimise les divisions et les fusions.

L'algorithme permet également d'interroger n'importe quel percentile, et pas seulement médiane, puisque vous avez une distribution complète estimation.

j'utilise cette méthode dans mon propre code à de nombreux endroits, principalement pour déboguer les journaux.. où certaines statistiques que vous enregistrez ont une distribution inconnue. Avec cet algorithme, vous n'avez pas besoin de deviner à l'avance.

l'inconvénient est que les largeurs inégales de bin signifie que vous devez faire une recherche binaire pour chaque échantillon, de sorte que votre algorithme net est O(NlogN).

7
répondu SPWorley 2009-03-12 14:52:37

la suggestion de David semble être l'approche la plus sensée pour se rapprocher de la médiane.

"151910920 Un" running signifie pour le même problème est beaucoup plus facile à calculer:

M n = m n-1 + ((V n - M n-1 ) / n)

où M n est la moyenne des valeurs de n, M n-1 est la moyenne précédente, et V n est la nouvelle valeur.

en d'autres termes, la nouvelle moyenne est la moyenne existante plus la différence entre la nouvelle valeur et la moyenne, divisée par le nombre de valeurs.

en code cela ressemblerait à quelque chose comme: 

new_mean = prev_mean + ((value - prev_mean) / count)

bien qu'évidemment vous pourriez vouloir considérer des choses spécifiques à la langue comme les erreurs d'arrondi à virgule flottante etc.

3
répondu GrahamS 2009-04-08 12:12:11

Je ne pense pas qu'il soit possible de faire sans avoir la liste en mémoire. Vous pouvez évidemment approximer avec

  • moyenne si vous savez que les données sont distribuées symétriquement
  • ou calculer une médiane appropriée d'un petit sous - ensemble de données (qui correspond à la mémoire) - si vous savez que vos données ont la même distribution dans l'échantillon (par exemple que le premier élément a la même distribution que le dernier)
2
répondu Grzenio 2009-03-12 10:40:46

trouver Min et Max de la liste contenant N éléments par recherche linéaire et les nommer comme de haute et de Basse valeur MedianIndex = (N+1)/2

recherche binaire de premier ordre:

répétez les 4 étapes suivantes jusqu'à ce que la valeur soit inférieure à la valeur supérieure.

  1. Obtenir MedianValue environ = ( Valeur + LowValue ) / 2

  2. Get NumberOfItemsWhichAreLessThanorEqualtomedianvalue = K

  3. est K = MedianIndex, puis retour MedianValue

  4. est K > MedianIndex ? puis haute valeur = moyenne Valeur sinon basse valeur = moyenne Valeur

Il sera plus rapide, sans consommer de la mémoire

2nd Order binaire Search:

LowIndex=1 HighIndex=N

répéter les 5 étapes suivantes jusqu'à (LowIndex < HighIndex)

  1. Get Approximate DistrbutionPerUnit=(HighValue-LowValue)/(HighIndex-LowIndex)

  2. Get Approximate MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

  3. "Get Number Of Items Which Arelessthanorequaltomedianvalue = K

  4. est (K=Médianindex)? retour Médianvalue

  5. est (K > MedianIndex) ? puis HighIndex=K et HighValue = MedianValue Else LowIndex = K et LowValue=MedianValue

Il sera plus rapide que le 1er ordre, sans consommer de la mémoire

nous pouvons également penser à ajuster HighValue, LowValue et MedianValue avec HighIndex, LowIndex et MedianIndex à une parabole, et peut obtenir Thirdorder binaire Recherche qui sera plus rapide que le 2ème ordre sans consommer de mémoire et ainsi de suite...

2
répondu lakshmanaraj 2009-03-13 04:25:16

généralement si l'entrée se situe dans une certaine fourchette, disons 1 à 1 million, il est facile de créer un tableau de nombres: lisez le code pour "quantile" et "ibucket" ici: http://code.google.com/p/ea-utils/source/browse/trunk/clipper/sam-stats.cpp

cette solution peut être généralisée comme une approximation en exerçant une pression sur l'entrée dans un entier à l'intérieur d'une certaine plage en utilisant une fonction que vous inversez ensuite sur la sortie: IE: foo.push (((int) input/1000000) et quantile(foo) * 1000000.

si votre entrée est un nombre de double précision arbitraire, alors vous devez autoscalifier votre histogramme car les valeurs sont hors de portée (voir ci-dessus).

ou vous pouvez utiliser la méthode des triplets médians décrite dans cet article: http://web.cs.wpi.edu hofri medsel.pdf

0
répondu Erik Aronesty 2013-01-04 12:36:47