Comment calculer ou approximer la médiane d'une liste sans stocker la liste

Question

Je suis en train de calculer la médiane d'un ensemble de valeurs, mais je ne veux pas stocker toutes les valeurs que pourrait faire sauter à la mémoire. Est-il un moyen de calcul ou de rapprochement de la médiane sans le stockage et le tri de toutes les valeurs individuelles?

Idéalement, je voudrais écrire mon code un peu comme les suivantes

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

Tout ce que je besoin est le MedianCalculator code!

Mise à jour: Certaines personnes ont demandé si les valeurs que je suis en train 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

Answer 1

Si les valeurs sont discrètes et 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 de trouver la médiane à partir de l'histogramme compte (juste additionner les chiffres de la haut et en bas de l'histogramme jusqu'à ce que vous atteignez le milieu). Ou, si ce sont des valeurs continues, vous pouvez les distribuer dans des bacs - ce ne serait pas vous dire exactement médiane, mais il vous donnera une gamme, et si vous avez besoin de savoir plus précisément, vous avez peut itérer sur la liste de nouveau, en examinant uniquement les éléments dans le centre de la corbeille.

Answer 2

Il y a le "remedian' statistique. Il fonctionne par la configuration initiale de k tableaux, chacun de longueur b. Les valeurs de données sont nourris dans le premier tableau, et, quand c'est plein, la médiane est calculée et stockée dans le premier pos de la matrice suivante, après quoi, le premier tableau est ré-utilisé. Lorsque le deuxième tableau est plein de la médiane de ses valeurs est stocké dans le premier pos de la 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/statistics_refs/Remedian.pdf

Espérons que cette aide

Michael

Answer 3

J'utilise ces différentiels/récursif de la moyenne et de la médiane des estimateurs, qui à la fois l'utilisation constante de stockage:

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

où l'eta est un petit apprentissage taux de paramètre (par exemple 0,001) et sgn() est le signum fonction qui renvoie un des {-1, 0, 1}.

Ce type de l'accroissement de la moyenne de l'estimateur semble être utilisé partout, par exemple dans sans surveillance de réseau de neurones l'apprentissage des règles, mais la médiane version semble beaucoup moins commun, en dépit de ses avantages (robustesse aux valeurs aberrantes). Il semble que la médiane de la version pourrait être utilisé comme un remplacement pour la moyenne de l'estimateur 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: http://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness)

Answer 4

Ici, c'est un fou approche que vous pourriez essayer. C'est un problème classique en streaming algorithmes. Les règles sont

1. Vous avez peu de mémoire, par exemple O(log n) où n est le nombre d'éléments que vous voulez
2. Vous pouvez regarder à chaque fois et de prendre une décision alors et là de quoi faire avec elle, si vous les conservez, il en coûte de mémoire, si vous le jeter, il est parti pour toujours.

L'idée de la recherche d'une médiane est simple. Exemple de O(1/a^2 log(1/p))log(n) éléments de la liste au hasard, vous pouvez le faire via le réservoir d'échantillonnage (voir question précédente). Maintenant, il suffit de retourner la médiane à partir de votre échantillonnés éléments, à l'aide d'une méthode classique.

La garantie est que l'index de l'article retourné sera (1 +/- a)/2 avec probabilité au moins 1-p. Donc, il y a une probabilité p de défaut, vous pouvez le choisir par échantillonnage plus d'éléments. Et il l'habitude de retourner à la médiane ou de la garantie que la valeur de l'article retourné est n'importe où près de la médiane, c'est juste que lorsque vous triez la liste de l'article retourné sera près de la moitié de la liste.

Cet algorithme utilise O(log n) de l'espace supplémentaire et s'exécute en temps Linéaire.

Answer 5

C'est délicat à obtenir le droit en général, en particulier pour gérer les dégénérés de la série qui sont déjà triées, ou avoir un tas de valeurs au "début" de la liste, mais la fin de la liste a des valeurs dans une plage différente.

L'idée de base de faire un histogramme qui est le plus prometteur. Cela vous permet d'accumuler de l'information sur la distribution et de répondre à des requêtes (comme la médiane) de celui-ci. La médiane sera approximatifs, car manifestement, vous n'avez pas de stocker toutes les valeurs. L'espace de stockage est fixé afin qu'il fonctionne avec n'importe quelle longueur de la séquence que vous avez.

Mais vous ne pouvez pas construire un histogramme de dire que les 100 premières valeurs et de l'utilisation de l'histogramme en permanence.. la modification des données peut faire l'histogramme invalide. Si vous avez besoin d'une dynamique de l'histogramme de changer de gamme et les poubelles à la volée.

Faire une structure qui a la N des bacs. Vous allez stocker la valeur X de chaque logement de transition (N+1 valeurs total) ainsi que de la population de la corbeille.

Flux de données. Le premier N+1 valeurs. Si le flux se termine avant cette, grande, vous avez toutes les valeurs chargé et vous pouvez trouver exactement la même médiane et le retourner. Bien utiliser les valeurs à définir votre première histogramme. Juste trier les valeurs et les utiliser comme corbeille de définitions, chaque cellule ayant une population de 1. C'est OK d'avoir des dupes (0 largeur des bacs).

Maintenant, flux de nouvelles valeurs. Pour chacun, binaire de recherche pour trouver le bin il appartient. Dans la plupart des cas, vous avez juste incrémenter la population de ce bac et continuer. Si votre échantillon est au-delà de l'histogramme bords (plus haut ou plus bas), il suffit de prolonger la fin de la corbeille de la gamme de l'inclure. Lorsque votre flux est fait, vous pouvez trouver la médiane de l'échantillon valeur par trouver le bin qui a l'égal de la population sur les deux côtés, et l'interpolation linéaire le reste bin-largeur.

Mais cela ne suffit pas.. vous avez encore le besoin d'ADAPTER l'histogramme à des données d'être transmises. Lorsqu'une cellule devient de plus plein, vous êtes la perte d'information à ce sujet bin sous la distribution. Vous pouvez résoudre ce problème en adaptant basée sur certaines heuristiques... Le plus simple et le plus fiable est de savoir si un bac atteint un certain seuil de population (quelque chose comme 10*v/N v= nombre de valeurs vu jusqu'à présent dans le flux, et N est le nombre de poubelles), vous divisez le trop plein de la corbeille. Ajouter une nouvelle valeur à mi-chemin de la poubelle, donnez à chaque côté de la moitié de l'original de la corbeille de la population. Mais maintenant, vous avez trop de poubelles, de sorte que vous besoin de SUPPRIMER une poubelle. Une bonne heuristique pour ce qui est de trouver la poubelle avec le plus petit produit de la population et de la largeur. De le supprimer et de le fusionner avec de sa la gauche ou la droite voisin (celui des voisins lui-même a le plus petit produit de la largeur et de la population.). Fait! Notez que la fusion ou de la séparation des bacs de perdre de l'information, mais qui est inévitable.. vous n'avez de stockage fixe.

Cet algorithme est agréable en ce qu'elle permettra de traiter tous les types de flux d'entrée et de donner de bons résultats. Si vous avez le luxe de choisir l'ordre d'échantillon, un échantillon aléatoire est le meilleur, car qui minimise les scissions et 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 dans de nombreux endroits, surtout pour les journaux de débogage.. où certaines stats que vous enregistrez sont inconnus de la distribution. Avec cet algorithme, vous n'avez pas besoin de deviner à l'avance.

L'inconvénient, c'est l'inégalité de bin largeurs signifie que vous avez à faire une recherche binaire pour chaque échantillon, de sorte que votre net de l'algorithme est O(NlogN).