Algorithmen zur Berechnung des laufenden Medians?

Bei kleineren Fenstergrößen n log nfunktioniert die Sortierung möglicherweise. Gibt es dafür bessere Algorithmen?

Es ist eine schlechte Form, ein Array zu sortieren, um einen Median zu berechnen. Mediane (und andere Quantile) werden normalerweise mithilfe des Schnellauswahlalgorithmus mit -Komplexität berechnet .$O(n)$

Vielleicht möchten Sie hier auch meine Antwort auf eine kürzlich gestellte verwandte Frage lesen .

Hier ist ein Artikel, der einen möglichen Algorithmus beschreibt. Der Quellcode ist enthalten und eine ziemlich ernsthafte Anwendung (Gravitationswellendetektion basierend auf Laserinterferometrie), so dass Sie erwarten können, dass es gut getestet wird.

Wenn Sie bereit sind, eine Annäherung zu tolerieren, gibt es andere Methoden. Eine Näherung ist beispielsweise ein Wert, dessen Rang innerhalb eines (benutzerdefinierten) Abstands vom wahren Median liegt. Der Medianwert hat beispielsweise den Rang 0,5 (normalisiert). Wenn Sie einen Fehlerterm von 10% angeben, möchten Sie eine Antwort mit einem Rang zwischen 0,45 und 0,55.

Wenn eine solche Antwort angemessen ist, gibt es viele Lösungen, mit denen Datenfenster verschoben werden können. Die Grundidee besteht darin, eine Stichprobe der Daten einer bestimmten Größe (ungefähr 1 / Fehlerbegriff) zu führen und den Median dieser Stichprobe zu berechnen. Es kann gezeigt werden, dass der resultierende Median mit hoher Wahrscheinlichkeit unabhängig von der Art der Eingabe die oben genannten Eigenschaften erfüllt.

Die Hauptfrage ist daher, wie eine laufende Stichprobe der Daten einer bestimmten Größe verwaltet werden kann, und dafür gibt es viele Ansätze, einschließlich der als Reservoir-Stichprobe bekannten Technik. Beispiel: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Wenn Sie ein Datenfenster der Länge k als sortierte doppelt verknüpfte Liste verwalten, verwenden Sie eine binäre Suche (um jedes neue Element einzufügen, wenn es in das Fenster verschoben wird) und ein kreisförmiges Array von Zeigern (um die Elemente sofort zu lokalisieren) müssen gelöscht werden), jede Verschiebung des Fensters erfordert O (log (k)) Aufwand zum Einfügen eines Elements, nur O (1) Aufwand zum Löschen des aus dem Fenster verschobenen Elements und nur O (1) Aufwand zum Suchen der Median (da jedes Mal, wenn ein Element in die Liste eingefügt oder daraus gelöscht wird, ein Zeiger auf den Median in O (1) aktualisiert werden kann). Der Gesamtaufwand für die Verarbeitung eines Arrays der Länge N beträgt daher O ((nk) log (k)) <= O (n log (k)). Dies ist besser als alle anderen bisher vorgeschlagenen Methoden, und es ist keine Annäherung, es ist genau.

Wie Sie erwähnt haben, wäre das Sortieren O(n·log n)für ein Fenster von Länge n. Durch diesen Umzug werden l=vectorlengthdie Gesamtkosten um einen weiteren erhöht O(l·n·log n).

Der einfachste Weg, dies zu tun, besteht darin, eine geordnete Liste der letzten n Elemente im Speicher zu behalten, wenn Sie von einem Fenster zum nächsten wechseln. Da das Entfernen / Einfügen eines Elements aus / in eine geordnete Liste beides ist O(n), entstehen Kosten in Höhe von 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)

Hier ist eine Lösung O (1) zum Ermitteln des aktuellen Medians und O (log n) zum Hinzufügen einer neuen Zahl http://www.dsalgo.com/RunningMedian.php

Wenn Sie mit einer Schätzung anstelle des wahren Medians leben können, ist der Remedian-Algorithmus (PDF) ein Durchgang mit geringem Speicherbedarf und genau definierter Genauigkeit.

Der Remedian mit der Basis b berechnet die Mediane der b-Beobachtungsgruppen und dann die Mediane dieser Mediane, bis nur noch eine einzige Schätzung übrig bleibt. Diese Methode benötigt lediglich k Arrays der Größe b (wobei n = b ^ k) ...

Ich habe diese RunningStats C ++ - Bibliothek in einer eingebetteten Anwendung verwendet. Es ist die einfachste Statistikbibliothek, die ich bisher gefunden habe.

Über den Link:

Der Code ist eine Erweiterung der Methode von Knuth und Welford zur Berechnung der Standardabweichung in einem Durchgang durch die Daten. Es berechnet auch die Schiefe und die Kurtosis mit einer ähnlichen Schnittstelle. Der Algorithmus benötigt nicht nur einen Durchgang durch die Daten, sondern ist auch numerisch stabil und genau.