C/C++ Forum :: Median mit streaming daten

Shade Of Mine Moderator 10:43:57 09.02.2010 Titel:

Hallo Leute.

Ich will den Median einer quasi endlosen Zahlenreihe berechnen. Quasi endlos, da sie schon irgendwann aufhört, ich sie aber nicht speichern kann.

Mir fehlt irgendwie der Ansatz den Median zu berechnen ohne alle Elemente zu kennen.

Ich hab, muss ich zugeben, auch sehr wenig Erfahrung mit Streaming Algos...

Unregistrierter

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

__Stefan__ Mitglied 11:27:43 09.02.2010 Titel:

Soll das Resultat eine Kurve (moving median)sein oder ein einzelner Wert, den du haben willst wenn die Zahlenfolge aufgehört hat?

Christoph Moderator 11:31:24 09.02.2010 Titel:

mwm schrieb:

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

C/C++ Code:
unsigned streaming_avg (unsigned x) { static unsigned ret = 0; static unsigned count = 1; ret = (count * ret + x - ret)/count; count++; return ret; }

Das ist der Mittelwert und nicht der Median.

Ich denke, den Median kann man nicht berechnen, ohne sich alle Elemente (evtl. abzüglich Duplikate) zu merken. Meine Überlegung ist folgende: Angenommen, 1000 Elemente sind schon angekommen. Wenn du mir ein beliebiges dieser 1000 Elemente nennst, dann kann ich dir 1001 neue Elemente nennen, sodass der Median der 2001 Elemente gerade das eine Element ist, das du ausgesucht hast. Weil du das mit jedem Element machen kannst, kommt der Algorithmus nicht drumherum, alle der ersten 1000 Elemente zu speichern.
Weil du nicht weißt, dass es insgesamt 2001 Elemente werden, kann man diese Argumentation für jedes Anfangssegment führen und bekommt raus, dass der Algorithmus alle ankommenden Zahlen speichern muss.

Shade Of Mine Moderator 12:46:12 09.02.2010 Titel:

__Stefan__ schrieb:

Soll das Resultat eine Kurve (moving median)sein oder ein einzelner Wert, den du haben willst wenn die Zahlenfolge aufgehört hat?

Ein einzelner Wert am Ende.

bzw. einzelne Moment Aufnahme zu bestimmten Zeitpunkten, zB alle 10 Minuten den aktuellen Median speichern (das ist uU geplant). Aktuell interessiert mich aber nur am Ende der Median über alle Daten.

@Christoph:
das habe ich fast befürchtet dass es nicht. Gibt es eine andere Möglichkeit einen Durchschnittswert zu bekommen der gegen Ausreisser Resitent ist? Aktuell verwende ich den reinen Durchschnitt aber da gibt es dann einzelne Peaks die den ziemlich durcheinander bringen.

Unregistrierter

Median gegen Ausreisser resistent?
1,2,3,4,100,4,3,2,1
Hier IST der Medaian der Ausreisser

nman Moderator 13:11:37 09.02.2010 Titel:

mediatorXXL schrieb:

Median gegen Ausreisser resistent?
1,2,3,4,100,4,3,2,1
Hier IST der Medaian der Ausreisser

1,1,2,2,3,3,4,4,100

Kann ich nicht nachvollziehen.

__Stefan__ Mitglied 13:25:33 09.02.2010 Titel:

Shade Of Mine schrieb:

__Stefan__ schrieb:

Soll das Resultat eine Kurve (moving median)sein oder ein einzelner Wert, den du haben willst wenn die Zahlenfolge aufgehört hat?

Ein einzelner Wert am Ende.

bzw. einzelne Moment Aufnahme zu bestimmten Zeitpunkten, zB alle 10 Minuten den aktuellen Median speichern (das ist uU geplant). Aktuell interessiert mich aber nur am Ende der Median über alle Daten.

@Christoph:
das habe ich fast befürchtet dass es nicht. Gibt es eine andere Möglichkeit einen Durchschnittswert zu bekommen der gegen Ausreisser Resitent ist? Aktuell verwende ich den reinen Durchschnitt aber da gibt es dann einzelne Peaks die den ziemlich durcheinander bringen.

Da wäre doch ein moving median der richtige Weg. Du musst das Fenster halt so gross wählen dass die Ausreisser-Resistenz gegeben ist. Eine bestimmte Anzahl von Werten musst du dafür natürlich zwischenspeichern. Am Schluss mittelst dann einfach die einzelnen Medianwerte. Hast du schonmal boost accumulators angeschaut?

rüdiger Moderator 15:27:40 09.02.2010 Titel:

Ich hab das nur noch so dumpf im Hinterkopf. Aber die Wirtschaftler nutzen irgend welche Verfahren, um von einem kleinen Satz an Daten auf den Median zu schließen. Vielleicht kannst du so etwas nutzen.

Ansonsten schau mal in boost.Accumulators. Die haben was für den Median: http://www.boost.org/doc/libs/1_42_0/doc/html/accu ....... ml#header.boost.accumulators.statistics.median_hpp

Shade Of Mine Moderator 15:28:10 09.02.2010 Titel:

__Stefan__ schrieb:

Da wäre doch ein moving median der richtige Weg. Du musst das Fenster halt so gross wählen dass die Ausreisser-Resistenz gegeben ist. Eine bestimmte Anzahl von Werten musst du dafür natürlich zwischenspeichern. Am Schluss mittelst dann einfach die einzelnen Medianwerte. Hast du schonmal boost accumulators angeschaut?

Mhm, ja. Könnte funktionieren.

Sagen wir ich nehme eine sample size von 1000. dh ich ermittle alle 1000 werte den median und speichere den. nur wohin? die gespeicherte Menge wird natürlich um faktor 1000 langsamer wachsen als die Menge aller Zahlen, aber was tun wenn die immer noch zu groß wird?

Es geht um Messungen während der Laufzeit eines Programmes: das kann nun 2h oder 100 Tage sein... Ich konnte leider nichts finden was ich in so einem Fall mache. Nach welchem Algo reduziere ich dann mein gespeichertes median set?

Aber das hilft auf jedenfall schonmal ordentlich weiter, da zumindest mal bei allen tests der median funktionieren wird (ich lass ja keine 100tag lang tests laufen

)

PS:
@ruediger und __Stefan__
habt ihr dazu mal ein stichwort? denn es sieht so aus als ob die accumulators von boost wirklich genau das machen was ich suche - nur leider kann ich kein c++ verwenden...