Incremental Median

[Gast]

Hi,

kennt irgendjemand eine vernünftige Methode un einen online Median zu berechnen? Also ohne sich Messwerte zu merken?

alpha = 0.002;
m += alpha*sign(current_value);

hab ich schon probiert. Diverse sequential quantile estimation methoden
http://www.waset.org/journals/waset/v8/v8-13.pdf
hab ich mir kurz angesehen, aber wie ich das verstanden habe funktionieren die am besten wenn man einen Buffer der letzten paar Messwerte hat (je größer der Buffer umso besser). Ich bin aber wirklich auf Buffergröße 1 beschränkt.

Die Methode mit alpha funktioniert gar nicht so schlecht, das Problem ist halt wie man den Parameter, d.h. den Tradeoff zwischen Stabilität und Reaktionsgeschwindigkeit vernünftig wählt.

Kennt da jemand noch was anderes?

[Gast]

Sollte natürlich heißen

m += alpha*sign(current_value-m);

[Trap]

Ich kann die Problembeschreibung von dir nicht nachvollziehen. Das was du Median nennst ist keiner, der Code berechnet keinen Median, die von dir genannte Einschränkung garantiert sogar, dass man keinen Median berechnen kann.

Was willst du denn wirklich haben? Und woher kommt die merkwürdige Einschränkung nichts speichern zu können? Normalerweise ist genau das eine der Stärken von allen Computern...

[pest]

das was du machst nennt man Exponentielle Glättung (http://de.wikipedia.org/wiki/Exponentielle_Gl%C3%A4ttung)

[Gast]

Ich kann die Problembeschreibung von dir nicht nachvollziehen. Das was du Median nennst ist keiner, der Code berechnet keinen Median, die von dir genannte Einschränkung garantiert sogar, dass man keinen Median berechnen kann.

Gut dann eben eine Approximation für den Median. Ich weiß dass man den Median nicht berechnen kann ohne alle Daten zu kennen.

Was willst du denn wirklich haben?

Den Median bzw. eine (möglichst gute) Approximation.
Und woher kommt die merkwürdige Einschränkung nichts speichern zu können? Normalerweise ist genau das eine der Stärken von allen Computern...
Die Einschränkung hab ich eben. Wenn dus genau wissen willst, die Datenmengen sind zu groß um alle Messwerte zu speichern. Z.b. Quantile von Paketeigenschaften in einem 10Gbps Netzwerke -> viel Spaß beim speichern der Daten...
das was du machst nennt man Exponentielle Glättung (http://de.wikipedia.org/wiki/Exponentielle_Gl%C3%A4ttung)
Ich glaube nicht. Exponentielle Glättung ist eine Form des Mittelwerts, was ich oben mache ist schon eine Approximation für den Median. Der Unterschied ist dass bei der Glättung die Größe der Änderung vom letzten Messwert abhängt, bei der oben beschriebenen Methode nicht. Damit hat den Vorteil der Robustheit gegen Outlier -> Median.

[Tiamat]

Ich würde mir erst mal ein paar Gedanken vor dem Rechnen machen. Und zwar welche Verteilung liegt vor bzw. könnte vorliegen ?
Sind die Daten ordinal, nominal oder kategoriell?

Je nach dem was für Bedingungen zutreffen, stehen einen T-Test, ein Z-Test, ein Vorzeichentest oder ein Wilcoxon Vorzeichen-Rangtest zur Verfügung.

[pest]

Ich glaube nicht. Exponentielle Glättung ist eine Form des Mittelwerts, was ich oben mache ist schon eine Approximation für den Median. Der Unterschied ist dass bei der Glättung die Größe der Änderung vom letzten Messwert abhängt, bei der oben beschriebenen Methode nicht. Damit hat den Vorteil der Robustheit gegen Outlier -> Median.

Tja liegt wohl daran das ich nicht weiß was "sign" sein soll? Die Signumsfunktion?

m+=alpha * (cur-m)
m:=m+alpha*(cur-m)
m:=m+alpha*cur-alpha*m
m:=m*(1-alpha)+alpha*cur

das ist exponentielles glätten

[Gast]

Ich würde mir erst mal ein paar Gedanken vor dem Rechnen machen. Und zwar welche Verteilung liegt vor bzw. könnte vorliegen ?

Darüber kann ich leider keine Annahmen treffen.

Sind die Daten ordinal, nominal oder kategoriell?

Je nach dem was für Bedingungen zutreffen, stehen einen T-Test, ein Z-Test, ein Vorzeichentest oder ein Wilcoxon Vorzeichen-Rangtest zur Verfügung.
Soweit ich verstanden habe sind das Methoden um aufgrund von Stichproben einer (unbekannten) Verteilung eine Entscheidung zu treffen. Ich möchte aber den Wert des Median berechnen, nicht nur eine Entscheidung ja/nein einer Hypothese. Kann aber sein dass ich diese statistischen Tests nicht richtig verstanden habe.

Meine Daten enthalten Ausreißer, ich weiß weder wie häufig diese sind, noch wie groß.
Tja liegt wohl daran das ich nicht weiß was "sign" sein soll? Die Signumsfunktion?

Ja genau.

m+=alpha * (cur-m)
m:=m+alpha*(cur-m)
m:=m+alpha*cur-alpha*m
m:=m*(1-alpha)+alpha*cur
das ist exponentielles glätten
S. oben - mit sign=signumfunktion siehts anders aus.

[Trap]

Jeweils pro Paket einen Wert in einen Ringpuffer speichern scheint mir nicht unmöglich mehr Ressourcenbedarf als die von dir genannte Berechnung pro Paket auszuführen. Oder mit etwas mehr Laufzeitaufwand einen pseudozufälligen Eintrag in einem festen Puffer zu überschreiben (damit hat man auch eine exponentiell abfallenden Beitrag der älteren Daten und kein Abschneiden nach x Samples).

Die tatsächliche Berechnung des Median kann man ja viel seltener machen (zum Beispiel einmal pro Paketzahl=Puffergröße) und mit Quickselect geht das in Erwartungswert O(Puffergröße). Die amortisierten erwarteten Kosten bei einer Neuberechnung pro Paketzahl=Puffergröße sind für das vollständige Verfahren auch O(1) wie bei deiner Methode.

Deshalb kann man dann in beiden Fällen die Puffergröße völlig frei wählen ohne die Performance zu beeinflussen (wenn man von den Auswirkungen vom Prozessorcache absieht). Es braucht natürlich schon etwas mehr Leistung als die einfache Berechnung von dir, kann aber dafür auch mehr.

[HajottV]

alpha = 0.002;
m += alpha*sign(current_value);


Hallo Gast,

multiplikative Anpassungen konvergieren besser als additive (die Begründung spare ich mir jetzt mal).

Ich bin jetzt einfach mal davon ausgegangen, dass Du nur positive Werte hast und hab mal eine schiefe Verteilung gewählt.


import random
import math

v = [math.pow(random.random(), 1.5) for i in range(10000)]

def signum(x):
if x == 0: return 0
if x < 0: return -1
return 1

m = 0.5
for x in v: m += 0.001 * signum(x - m)
print "additiv.........", m

m = 0.5
for x in v:
if x - m > 0: m *= 1.001
else: m /= 1.001
print "multiplikativ...", m

v.sort()
print "korrekt.........", v[len(v) / 2]

[Tiamat]

Darüber kann ich leider keine Annahmen treffen.

Soweit ich verstanden habe sind das Methoden um aufgrund von Stichproben einer (unbekannten) Verteilung eine Entscheidung zu treffen. Ich möchte aber den Wert des Median berechnen, nicht nur eine Entscheidung ja/nein einer Hypothese. Kann aber sein dass ich diese statistischen Tests nicht richtig verstanden habe.

Meine Daten enthalten Ausreißer, ich weiß weder wie häufig diese sind, noch wie groß.

Ja genau.

S. oben - mit sign=signumfunktion siehts anders aus.

Ja durchaus, die können aber dazu verwendet werden. Ich hab mal nach nem Link dazu geschaut, ich denke das ist müsste dir weiterhelfen können:
Weiterführende Statistik (http://books.google.de/books?id=rEicaROV5hcC&pg=PT465&dq=vorzeichentest+median&hl=de&sa=X&ei=d8RpT7WHFs7DtAaw3JXjBw&ved=0CDAQ6AEwAA#v=onepage&q=vorzeichentest%20median&f=false)

[Gast]

Danke HajottV, sieht sehr vielversprechend aus. Erklärung würde mich direkt interessieren :)

Danke Tiamat, werds mir ansehen.

[Gast]

alpha = 0.002;
m += alpha*sign(current_value);


Hallo Gast,

multiplikative Anpassungen konvergieren besser als additive (die Begründung spare ich mir jetzt mal).

Ich bin jetzt einfach mal davon ausgegangen, dass Du nur positive Werte hast und hab mal eine schiefe Verteilung gewählt.


import random
import math

v = [math.pow(random.random(), 1.5) for i in range(10000)]

def signum(x):
if x == 0: return 0
if x < 0: return -1
return 1

m = 0.5
for x in v: m += 0.001 * signum(x - m)
print "additiv.........", m

m = 0.5
for x in v:
if x - m > 0: m *= 1.001
else: m /= 1.001
print "multiplikativ...", m

v.sort()
print "korrekt.........", v[len(v) / 2]

Hm, damit hängt die Konvergenz aber vom Wert des Median ab. Will heißen wenn der Median 1000 ist sieht die Sache anders aus als wenn der Median 1 ist. Mit additiver Korrektur ist man da unabhängig.

Gute Ergebnisse erhalte ich mit Histogrammen, also die Verteilung für jeden Samplepunkt annähern indem man den entpsrechenden bin hochzählt und der Median ist dann der Wer desjenigen bins mit den meisten Einträgen. Man hat halt Diskretisierungsartefakte je nachdem wie viele Histogramm Bins man wählt - und mann muss sich wieder zusätzliche Daten merken...