Was ist ein guter Algorithmus zum Schätzen des Medians eines riesigen Datensatzes mit einmaligem Lesen?

48

Ich suche einen guten Algorithmus (dh minimale Berechnung, minimale Speicheranforderungen), um den Median eines Datensatzes zu schätzen, der zu groß zum Speichern ist, sodass jeder Wert nur einmal gelesen werden kann (es sei denn, Sie speichern diesen Wert explizit). Es gibt keine Grenzen für die Daten, die angenommen werden können.

Annäherungen sind in Ordnung, solange die Genauigkeit bekannt ist.

Irgendwelche Hinweise?

PeterR
quelle
4
Wenn Sie nach Stackoverflow fragen, erhalten Sie möglicherweise bessere Antworten.
2
@Srikant:> Es ist ein ziemlich aktives Forschungsgebiet in der Statistik :) Die Lösung, die den unteren theoretischen Grenzen in Bezug auf die Speicherung am nächsten kommt, beinhaltet auch einige ziemlich clevere Wahrscheinlichkeitskonstrukte. Alles in allem war ich überrascht, als ich es mir vor ein paar Monaten zum ersten Mal ansah; Hier gibt es mehr Statistiken als man denkt.
User603

Antworten:

6

Könnten Sie den Datensatz in viel kleinere Datensätze gruppieren (z. B. 100 oder 1000 oder 10.000 Datenpunkte)? Berechnen Sie dann den Median jeder der Gruppen. Wenn Sie dies mit genügend Datenmengen tun, können Sie so etwas wie den Durchschnitt der Ergebnisse jeder der kleineren Mengen darstellen, indem Sie genügend kleinere Datenmengen ausführen, die zu einer "durchschnittlichen" Lösung konvergieren.

Ian Turner
quelle
Das ist interessant, und wo könnte man statistische Ratschläge einholen! Angenommen, ich habe insgesamt 500.000 iid-Punkte und ich betrachte Gruppen von 1000 davon und berechne den Median jeder Gruppe. Jetzt habe ich 500 Mediane. Gibt es eine Theorie, die es mir ermöglichen könnte, ein Konfidenzintervall für den Gesamtmedian basierend auf diesen 500 Medianen zu berechnen?
PeterR
4
Nach Ansicht eines längst verlorenen Kollegen scheinen Chiranjeeb Buragohain und Subhash Suri der beste Weg zu sein. Quantile in Strömen. cs.ucsb.edu/~suri/psdir/ency.pdf Ich mag auch Ians Ansatz, da diese Mediane kleinerer Datensätze zu einer Normalverteilung konvergieren und ich so Conf-Intervalle für die Mediane bilden kann.
PeterR
10

Wie wäre es mit so etwas wie einem Binning-Verfahren? Nehmen Sie an (zur Veranschaulichung), dass Sie wissen, dass die Werte zwischen 1 und 1 Million liegen. Richten Sie N Fächer der Größe S ein. Wenn also S = 10000 ist, stehen 100 Fächer zur Verfügung, die den Werten [1: 10000, 10001: 20000, ..., 990001: 1000000] entsprechen.

Gehen Sie dann die Werte durch. Anstatt jeden Wert zu speichern, erhöhen Sie einfach den Zähler im entsprechenden Fach. Unter Verwendung des Mittelpunkts jedes Fachs als Schätzung können Sie eine vernünftige Annäherung an den Median vornehmen. Sie können diese Einstellung beliebig fein oder grob skalieren, indem Sie die Größe der Fächer ändern. Sie sind nur durch Ihren Speicherplatz begrenzt.

Da Sie nicht wissen, wie groß Ihre Werte werden können, wählen Sie einfach eine Behältergröße aus, die groß genug ist, damit Ihnen wahrscheinlich nicht der Arbeitsspeicher ausgeht. Sie können die Lagerplätze auch sparsam lagern, sodass Sie einen Lagerplatz nur dann hinzufügen, wenn er einen Wert enthält.

Bearbeiten:

Der von ryfm bereitgestellte Link gibt ein Beispiel dafür, wobei zusätzlich die kumulativen Prozentsätze verwendet werden, um den Punkt innerhalb des Median-Bin genauer zu schätzen, anstatt nur die Mittelpunkte zu verwenden. Das ist eine schöne Verbesserung.

Chrisamiller
quelle
Das Problem beim Binning-Ansatz ist, dass wir keine gute Obergrenze für die Daten haben und der Mittelpunkt für den größten Bin daher riesig sein müsste. Wir würden also eine große Anzahl von Fächern benötigen (nicht genug Speicher) oder ziemlich breite Fächer haben (was dann zu einer ziemlich ungenauen Antwort führen würde.) Und die Daten sind nicht sehr spärlich.
PeterR
Da Sie sich nur für den Median interessieren, warum konnten Sie die Klassen bei höheren Werten Ihrer Variablen nicht breiter machen?
Russellpierce
drknexus - weil wir nicht wissen, was der größte Behälter sein soll.
PeterR
Haben Sie eine Ahnung, wie hoch die Reichweite sein wird? Wenn Sie ziemlich sicher sind, dass mehr als die Hälfte der Antworten unter der Zahl N liegt, können Sie Ihren letzten Behälter so groß machen, wie Sie möchten. Vielleicht sind alle Zahlen in Ihrem letzten Behälter größer als 1 Billion - wäre das hoch genug? Mit der Speicherkapazität moderner Systeme können Sie eine Menge Fächer speichern und eine ziemlich hohe Auflösung erzielen. In Bezug auf Datenstrukturen sprechen wir hier nicht über etwas Phantasievolles und Speicherintensives.
Chrisamiller
Irgendeine Intuition? Ja. Und Ihr Ansatz könnte allgemein funktionieren. In diesem Fall können wir jedoch nicht viel Speicher / Berechnung haben. Es befindet sich in einer Netzwerkanwendung, in der das Gerät Zehntausende von Elementen pro Sekunde sehen kann und für diesen Zweck SEHR wenig Verarbeitung übrig bleibt. Ich weiß, nicht das ideale / typische Szenario, aber das macht es interessant!
PeterR
9

O(n)

user603
quelle
8

Mit dem Rivest-Tarjan-Selection-Algorithmus (manchmal auch als Median-of-Medians-Algorithmus bezeichnet) können Sie das Median-Element in linearer Zeit ohne Sortieren berechnen. Bei großen Datenmengen kann dies erheblich schneller sein als die log-lineare Sortierung. Ihr Speicherproblem wird dadurch jedoch nicht gelöst.

Robby McKilliam
quelle
2

Ich musste das noch nie machen, das ist also nur ein Vorschlag.

Ich sehe zwei (andere) Möglichkeiten.

Halbe Daten

  1. Laden Sie die Hälfte der Daten und sortieren Sie
  2. Lesen Sie als nächstes die restlichen Werte ein und vergleichen Sie sie mit Ihrer sortierten Liste.
    1. Wenn der neue Wert größer ist, verwerfen Sie ihn.
    2. Andernfalls wird der Wert in die sortierte Liste eingefügt und der größte Wert aus dieser Liste entfernt.

Stichprobenverteilung

Die andere Möglichkeit besteht darin, eine Annäherung zu verwenden, die die Stichprobenverteilung einbezieht. Wenn Ihre Daten Normal sind, dann ist der Standardfehler moderat n :

1,253 * sd / sqrt (n)

Um die Größe von n zu bestimmen, mit der Sie zufrieden sind, habe ich eine schnelle Monte-Carlo-Simulation in R durchgeführt

n = 10000
outside.ci.uni = 0
outside.ci.nor = 0
N=1000
for(i in 1:N){
  #Theoretical median is 0
  uni = runif(n, -10, 10)
  nor  = rnorm(n, 0, 10)

  if(abs(median(uni)) > 1.96*1.253*sd(uni)/sqrt(n))
    outside.ci.uni = outside.ci.uni + 1

  if(abs(median(nor)) > 1.96*1.253*sd(nor)/sqrt(n))
    outside.ci.nor = outside.ci.nor + 1
}

outside.ci.uni/N
outside.ci.nor/N

Für n = 10000 lagen 15% der Schätzungen für den einheitlichen Median außerhalb des CI.

csgillespie
quelle
3
Der Datensatz ist möglicherweise zu groß, um die Hälfte davon zu lesen. In einem Netzwerkkontext kann das Gerät, das die Verarbeitung durchführt, Zehntausende von Elementen pro Sekunde sehen und verfügt wahrscheinlich über genügend Speicher, um nur einige Hundert zu speichern. Auch die Daten sind definitiv nicht Gaußsch. Tatsächlich passt es nicht gut zu einer der gängigen Distributionen.
PeterR
1

Sie können versuchen, einen Median basierend auf der gruppierten Häufigkeitsverteilung zu finden. Hier einige Details

Ryfm
quelle
1

Hier ist eine Antwort auf die beim Stackoverflow gestellte Frage: https://stackoverflow.com/questions/1058813/on-line-iterator-algorithms-for-estimating-statistical-median-mode-skewness/2144754#2144754

Das iterative Update Median + = eta * sgn (sample - median) scheint ein langer Weg zu sein.

Gemeinschaft
quelle
1
aber wie wählt man dann eta aus und was bedeutet das dann statistisch? dh wie man aus diesem Ergebnis Konfidenzintervalle für den Median bildet?
PeterR
@ PeterR, hey, was ist die endgültige Lösung, die Sie verwendet haben?
Aakash Goel
1

Der Remedian-Algorithmus (PDF) liefert eine Medianschätzung in einem 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) ...

Schuhmacher
quelle
1

Wenn die von Ihnen verwendeten Werte innerhalb eines bestimmten Bereichs liegen, z. B. 1 bis 100000, können Sie den Median einer extrem großen Anzahl von Werten (z. B. Billionen von Einträgen) mit einem Ganzzahl-Bucket (dieser Code stammt aus BSD-lizenziertem ea) effizient berechnen -utils / sam-stats.cpp)

class ibucket {
public:
    int tot;
    vector<int> dat;
    ibucket(int max) {dat.resize(max+1);tot=0;}
    int size() const {return tot;};

    int operator[] (int n) const {
        assert(n < size());
        int i;
        for (i=0;i<dat.size();++i) {
            if (n < dat[i]) {
                return i;
            }
            n-=dat[i];
        }
    }

    void push(int v) {
        assert(v<dat.size());
        ++dat[v];
        ++tot;
    }
};


template <class vtype>
double quantile(const vtype &vec, double p) {
        int l = vec.size();
        if (!l) return 0;
        double t = ((double)l-1)*p;
        int it = (int) t;
        int v=vec[it];
        if (t > (double)it) {
                return (v + (t-it) * (vec[it+1] - v));
        } else {
                return v;
        }
}
Erik Aronesty
quelle
Dies kann auch auf die Verwendung einer begrenzten Anzahl von Behältern für Echtzeitmediane usw.
ausgedehnt werden