Des algorithmes pour calculer la médiane en cours d'exécution?

18

Sur des fenêtres plus petites, le n log ntri peut fonctionner. Existe-t-il de meilleurs algorithmes pour y parvenir?

miku
la source
1
Je pense que c'est le premier candidat à être déplacé vers Stack Overflow.
Peut-être, mais il faudrait beaucoup plus d'explications sur SO.
walkytalky
2
La plupart des programmeurs connaissent la «médiane». (sort (array)) [length / 2] est un indice assez grand pour ceux qui ont oublié. Aussi à son plus basique pour chaque nouveau point, il vous suffit de faire une bissection / insertion sur une moitié du tableau ...
Paul
1
Réouverture après discussion sur meta.stats.stackexchange.com/questions/276/…
Rob Hyndman
2
Trop trivial pour être plus qu'un commentaire, mais le code pour la médiane de 3s est juste a + b + c - max (a, b, c) - min (a, b. C). Cela fonctionne bien même si des liens sont présents. Cela n'était évident pour moi qu'une fois que j'y avais pensé à partir du code de quelqu'un d'autre (pourquoi est-il (dans ce cas) en ajoutant et en soustrayant pour obtenir une médiane ???) et quelques autres pourraient avoir la même réaction. max () et min () sont souvent implémentées en tant que fonctions ultra-rapides. Malheureusement, il n'y a pas une telle astuce en général.
Nick Cox

Réponses:

11

C'est une mauvaise forme de trier un tableau pour calculer une médiane. (Médianes et autres quantiles) sont généralement calculées en utilisant le QuickSelect algorithme, avec complexes.O(n)

Vous pouvez également consulter ma réponse à une récente question connexe ici .

user603
la source
7

Voici un article décrivant un algorithme possible. Code source inclus et application assez sérieuse (détection des ondes gravitationnelles basée sur l'interférométrie laser), vous pouvez donc vous attendre à ce qu'il soit bien testé.

Łukasz Lew
la source
1
Le lien est rompu et sans informations sur le titre ou l'auteur, il est difficile de trouver ce à quoi il fait référence.
Kristopher Johnson
6

Si vous êtes prêt à tolérer une approximation, il existe d'autres méthodes. Par exemple, une approximation est une valeur dont le rang est à une certaine distance (spécifiée par l'utilisateur) de la vraie médiane. Par exemple, la médiane a un rang (normalisé) 0,5, et si vous spécifiez un terme d'erreur de 10%, vous voudriez une réponse dont le rang se situe entre 0,45 et 0,55.

Si une telle réponse est appropriée, il existe de nombreuses solutions qui peuvent fonctionner sur des fenêtres coulissantes de données. L'idée de base est de conserver un échantillon des données d'une certaine taille (environ 1 / terme d'erreur) et de calculer la médiane de cet échantillon. On peut montrer qu'avec une probabilité élevée, quelle que soit la nature de l'entrée, la médiane résultante satisfait les propriétés que j'ai mentionnées ci-dessus.

Ainsi, la principale question est de savoir comment maintenir un échantillon courant des données d'une certaine taille, et il existe de nombreuses approches pour cela, y compris la technique connue sous le nom d'échantillonnage de réservoir. Par exemple, cet article: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Suresh Venkatasubramanian
la source
4

Si vous conservez une fenêtre de données de longueur k en tant que liste triée à double lien, alors, au moyen d'une recherche binaire (pour insérer chaque nouvel élément au fur et à mesure qu'il est déplacé dans la fenêtre) et d'un tableau circulaire de pointeurs (pour localiser immédiatement les éléments qui doivent être supprimés), chaque décalage de la fenêtre nécessite O (log (k)) effort pour insérer un élément, seulement O (1) effort pour supprimer l'élément déplacé hors de la fenêtre, et seulement O (1) effort pour trouver la médiane (car chaque fois qu'un élément est inséré ou supprimé dans la liste, vous pouvez mettre à jour un pointeur sur la médiane en O (1)). L'effort total pour traiter un tableau de longueur N est donc O ((nk) log (k)) <= O (n log (k)). C'est mieux que n'importe quelle autre méthode proposée jusqu'à présent et ce n'est pas une approximation, c'est exact.

whuber
la source
1
Pourriez-vous nous expliquer comment vous proposez d'effectuer une recherche binaire dans une liste triée à double lien?
NPE
un «lien» vous permet de parcourir la liste dans l'ordre trié; l'autre vous permet de parcourir dans l'ordre d'apparition des éléments. Cependant, la façon dont vous le feriez avec les pointeurs n'est pas claire, en tant que questions @aix.
shabbychef
2
@aix Je pense que votre intimation est correcte; J'aurais besoin d'une liste de sauts indexable, pas seulement d'une liste triée à double lien. L'idée est d'avoir une structure de données qui permet l'insertion d'un élément, la suppression d'un élément et la recherche de la médiane dans le temps O (log (n)) attendu (ou mieux).
whuber
3

Comme vous l'avez mentionné, le tri serait O(n·log n)pour une fenêtre de longueur n. Faire ce déplacement en ajoute un autre l=vectorlengthfaisant le coût total O(l·n·log n).

Le moyen le plus simple de le faire est de garder une liste ordonnée des n derniers éléments en mémoire lors du passage d'une fenêtre à la suivante. Étant donné que la suppression / l'insertion d'un élément de / dans une liste ordonnée sont les deux, O(n)cela entraînerait des coûts O(l·n).

Pseudocode:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)
ymihere
la source
2

Si vous pouvez vivre avec une estimation au lieu de la vraie médiane, l' algorithme Remedian (PDF) est un passage avec de faibles exigences de stockage et une précision bien définie.

Le remède de base b procède au calcul des médianes de groupes d'observations b, puis des médianes de ces médianes, jusqu'à ce qu'il ne reste qu'une seule estimation. Cette méthode a simplement besoin de k tableaux de taille b (où n = b ^ k) ...

lacet
la source
0

J'ai utilisé cette bibliothèque C ++ RunningStats dans une application intégrée. C'est la bibliothèque de statistiques en cours d'exécution la plus simple que j'ai trouvée à ce jour.

Depuis le lien:

Le code est une extension de la méthode de Knuth et Welford pour calculer l'écart type en un seul passage à travers les données. Il calcule également l'asymétrie et le kurtosis avec une interface similaire. En plus de ne nécessiter qu'un seul passage à travers les données, l'algorithme est numériquement stable et précis.

Chris K
la source
Cette page dit-elle quelque chose sur la médiane?
musiphil