Algorithmen zur Berechnung der multivariaten empirischen Verteilungsfunktion (ECDF)?

Eindimensionales ECDF ist ziemlich einfach zu berechnen. Wenn es um zwei Dimensionen und mehr geht, werden Online-Ressourcen jedoch spärlich und schwer zu erreichen. Kann jemand effiziente Algorithmen (nicht vorgefertigte Implementierung) für die Berechnung multivariater ECDF vorschlagen, definieren und / oder präsentieren?

ecdf multivariate-distribution Alexander F.
quelle

Dies mag eine Informatikfrage sein, aber ich denke, dies ist der beste Ort, um eine Antwort zu finden. Lassen Sie mich wissen, ob ich woanders suchen sollte. Vielen Dank.

Alexander F.

Gibt es wirklich einen grundlegenden Unterschied? Die Berechnung eines univariaten ECDF entspricht dem Sortieren der Daten. Die Berechnung eines multivariaten ECDF entspricht der lexikografischen Sortierung der Daten.

whuber

@whuber, nicht genau, soweit ich weiß. Für jeden Datenpunkt X(i)müssen wir die Anzahl der Punkte zählen, die in dem von ihm definierten Hypercube enthalten sind (von -infbis einschließlich X(i)in allen Dimensionen). Die lexikografische Sortierung (Wörterbuch?) Funktioniert hier nicht unbedingt, da die Datenpunkte in jeder Dimension separat verglichen werden müssen. ZB: (2,3,4)wird im Vergleich zu lexikographisch größer sein (1,2,15), aber der durch definierte Hypercube (2,3,4)wird (1,2,15)seitdem nicht mehr enthalten 15>4.

Alexander F.

Die Korrespondenz ist zwar nicht so direkt. Aber man würde diese Sortierung oder ähnliches ausnutzen, um mit Aufwand einen Punktquadtree (oder Octree usw. ) zu erstellen . Möglicherweise möchten Sie die Literatur zu Computergeometrie und räumlicher Indizierung auf Details untersuchen.

O (n \log (n))

$O(n\log(n))$

whuber

Antworten:

Bei weiteren Untersuchungen gibt das folgende Papier effiziente Algorithmen für das kD-ECDF-Problem an:

Bentley, JL (1980). Mehrdimensionales Teilen und Erobern. Mitteilungen der ACM, 23 (4), 214-229.

Die eingeführte Hauptdatenstruktur ist als Bereichsbaum bekannt und ähnelt einem kd-Baum , verwendet jedoch einen Kompromiss zwischen Raum und Zeit, um schnellere Bereichsabfragen zu erzielen. Der Autor des obigen Papiers, Jon Bentley (bekannt als Programming Pearls), ist der Erfinder beider Datenstrukturen.

Beide sind Binärbäume, die eine Menge von dimensionalen Punkten rekursiv aufteilen, indem sie entlang einer Koordinatenachse am Median teilen. In einem kd-Baum werden die Unterbäume eines Knotens entlang der ten Dimension aufgeteilt, wobei durch läuft, die sich den Baum hinunter bewegen. In einem Bereichsbaum werden die Unterbäume immer entlang der ersten Dimension aufgeteilt, aber jeder Knoten wird durch einen dimensionalen Bereichsbaum erweitert, der über die verbleibenden Dimensionen definiert ist. $k$ $d$ $d$ $1\ldots k$ $k-1$

Zum Zeitpunkt dieses Schreibens verweist die oben verlinkte Wikipedia-Seite für "Range Tree" auf eine CS-Vorlesung (Utrecht U.), in der diese beiden Baumtypen aus dem Jahr 2012 verglichen werden. Dies legt nahe, dass diese Datenstrukturen immer noch im Wesentlichen "Stand der Technik" sind ". Es wird eine verbesserte "fraktionierte Kaskadierungs" -Variante für Bereichsbäume erwähnt, aber für das Allpunkt-ECDF-Problem ermöglicht dies nur, dass die Leistung des Bentley-Algorithmus durch wiederholte Abfragen des Bereichsbaums erreicht wird.

GeoMatt22
quelle

Danke für das interessante Papier! Ich denke, das ist es, was ich für Bäume brauche. Wäre toll, alternative Methoden zu sehen. Es sei denn, dies ist der Stand der Technik.

Alexander F.

@ AlexanderF. Ich habe meine Antwort aktualisiert, um den Algorithmus besser zu beschreiben (einschließlich einer "offiziellen" Referenz). Es scheint, dass der Ansatz immer noch dem Stand der Technik entspricht. Für die jüngsten Entwicklungen scheint der Schlüsselbegriff "orthogonale Bereichsabfragen" zu sein, wenn Sie weitere Untersuchungen durchführen möchten.

GeoMatt22

Ich bin nicht sicher, ob es eine effizientere Methode zur Berechnung des ECDF an den Datenpunkten gibt , aber der folgende Brute-Force-Ansatz sollte für die Berechnung des ECDF über das Daten- "Raster" effizient sein . Es ist eine einfache Verallgemeinerung der 1D-Version.

Angenommen, Sie haben einen Datensatz, der aus Punkten in Dimensionen besteht und in der Matrix . Der Einfachheit halber gehe ich davon aus, dass vollständig aus eindeutigen Zahlen besteht (dh allgemeine Position *). Ich werde die Matlab- Notation im folgenden Pseudocode verwenden, wie ich es mir für den Algorithmus vorgestellt habe, aber ich kann dies bei Interesse erweitern. $N$ $d$ $N\times d$ $X$ $X$

Zuerst berechnen

$[x_{:,k},I_{:,k}]=\text{sort}[X_{:,k}]$ für , $k=1:d$

Dabei ist die koordinatenweise Rangmatrix und die Koordinatengitterachsenmatrix (beide mit der Größe ). $I$ $x$ $N\times d$

Dann rastern die Datenpunkte in den implizierten Datenraster, Berechnen eines (normalisiert) Histogramm als . $P=\text{accumarray}[I,\frac{1}{N},N\times\text{ones[1,d]}]$

Integrieren Sie dann dieses "EPDF" in jede Dimension, um das ECDF zu erhalten: für . $P=\text{cumsum}[P,k]$ $k=1:d$

Jetzt ist die ECDF, die bei . $P_{i_1,\ldots,i_d}$ $x_{i_1,1},\ldots x_{i_d,d}$

Dieser Algorithmus benötigt Zeit für jede Sortierung und für jede Summe, sodass die Gesamtkosten . Da das gerasterte ECDF selbst -Elemente enthält, sollte dies im Wesentlichen optimal sein. $\text{O}[N\log N]$ $\text{O}[N^d]$ $\text{O}[d(N^d+N\log N)]$ $\text{O}[N^d]$

(* Die Annahme bestimmter Punkte kann gelockert werden, indem anstelle von zusammen mit ein wenig Buchhaltung verwendet wird.) $\text{unique}[]$ $\text{sort}[]$

GeoMatt22
quelle

Vielleicht möchten Sie mehr über Quadtrees und ihre höherdimensionalen Verallgemeinerungen erfahren, die effiziente Möglichkeiten bieten, euklidische Räume nach Punkten zu durchsuchen. Sie verwenden asymptotisch Ressourcen, was für weitaus besser ist als .

O (N \log (N))

$O(N\log(N))$

O (N^{d})

$O(N^d)$

d > 1

$d\gt 1$

whuber

@whuber Ich habe eine Vorstellung davon (zB kd Bäume ). Ich bin mir nicht sicher, ob es hier eine einzige "beste Antwort" gibt? In der Regel geben Sie bei einem solchen Problem auch an, welche Operationen Ihre abstrakte ECDF-Datenstruktur unterstützen soll (z. B. Punktabfragen, Subraumintegrale, Aktualisierung mit neuen Punkten usw.). Auf diese Weise können Sie ermitteln, welche Implementierung am besten geeignet ist.

GeoMatt22

Ich glaube, es sollte klar sein, welche Operationen für ein ECDF unterstützt werden müssen. Das Minimum ist, es an jedem Punkt im Raum auszuwerten. Es ist richtig, dass alternative Ansätze überlegen sein könnten, wenn ein ECDF dynamisch aufgebaut werden soll, aber diese Probleme scheinen den Rahmen dieser Frage zu sprengen.

whuber

@ GeoMatt22, dies sieht in der Tat wie eine Methode zur Berechnung des Histogramms aus und kann in Fällen in Ordnung sein, in denen die Approximation "gut genug" ist. Warum verwendet jedoch ein Verfahren, das ist , O(N^d)wenn der Brute - Force - Ansatz O(d*N^2). Zum Beispiel habe ich momentan keinen zu großen Datensatz, daher verwende ich den folgenden Matlab-Einzeiler, um d-dimensionales ECDF mit O(d*N)Speicherkomplexität zu berechnen ( C(i)ist die Häufigkeit des Datenpunkts Y(i,:)): arrayfun(@(i) sum(C(all(bsxfun(@le,Y, Y(i,:)), 2))), (1:size(Y,1)).');

Alexander F.

(+1) Nicht um einen effizienten Algorithmus anzugeben, sondern um einen ineffizienten Algorithmus klar zu erklären, der mir geholfen hat, das Problem zu verstehen.

Scortchi - Monica wieder einsetzen