Median mit streaming daten

Shade Of Mine

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...

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

__Stefan__

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

Christoph

mwm schrieb:

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

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.

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

nman

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__

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

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/accumulators/reference.html#header.boost.accumulators.statistics.median_hpp

Shade Of Mine

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 :p)

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...

rapso

Shade Of Mine schrieb:

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.

bei sowas macht man wohl oefter ein histogram, du teilst also den wertebereich in buckets auf und approximierst darin dann den median.

__Stefan__

Ich hoffe, das verdeutlicht das Prinzip:

#include <iostream>
#include <queue>
#include <vector>

class Average
{
    public:

        Average(std::size_t median_size): m_median_size(median_size), m_deque(median_size, 0), m_count(0), m_sum(0)
        {
        }

        void Insert(double x)
        {
			// Laenge der deque bleibt konstant!
            m_deque.pop_front();
            m_deque.push_back(x);

			// Inhalt der deque sortieren
            std::vector<double> tmp(m_deque.begin(), m_deque.end());
            std::sort(tmp.begin(), tmp.end());

            // Median dazu addieren
            m_sum += tmp[m_median_size / 2];
			++m_count;
        }

        double GetAverage() const
        {
            return m_sum / m_count;
        }

    private:

        std::size_t m_median_size;
        std::deque<double> m_deque;
        std::size_t m_count;
        double m_sum;
};

int main()
{
    Average a(15);

    for(int i = 0; i < 1000; ++i)
    {
        a.Insert(std::rand());
    }

    std::cout << a.GetAverage();

    return 0;
}

Shade Of Mine

Stefan schrieb:

Ich hoffe, das verdeutlicht das Prinzip:

Genial. Auf die Idee den Durchschnitt aller Median Werte zu nehmen bin ich nicht gekommen. Aber macht vollkommen Sinn. Danke.