Rechnerisch effiziente Schätzung des multivariaten Modus

14

Kurzversion: Was ist die rechnerisch effizienteste Methode zur Schätzung des Modus eines mehrdimensionalen Datensatzes, der aus einer kontinuierlichen Verteilung entnommen wurde?

Lange Version: Ich habe einen Datensatz, dessen Modus ich abschätzen muss. Der Modus stimmt nicht mit dem Mittelwert oder Median überein. Ein Beispiel ist unten gezeigt, dies ist ein 2D-Beispiel, aber eine ND-Lösung wäre besser: Geben Sie hier die Bildbeschreibung ein

Derzeit ist meine Methode

  1. Berechnen Sie die Schätzung der Kerneldichte in einem Raster, das der gewünschten Auflösung des Modus entspricht
  2. Suchen Sie nach dem größten berechneten Punkt

Offensichtlich berechnet dies die KDE an vielen nicht plausiblen Punkten, was besonders schlecht ist, wenn es viele Datenpunkte mit hohen Dimensionen gibt oder ich eine gute Auflösung für den Modus erwarte.

Eine Alternative wäre die Verwendung eines simulierten Annealing, eines genetischen Algorithmus usw., um den globalen Peak in der KDE zu finden.

Die Frage ist, ob es eine intelligentere Methode gibt, um diese Berechnung durchzuführen.

tkw954
quelle
Ich weiß die Antwort nicht, aber ich denke, das ist eine großartige Frage. Es fällt mir schwer, mir bessere Ansätze als die von Ihnen erwähnten vorzustellen. Ich denke, es gibt Unterschiede zwischen dem Ansatz der univariaten Kernelschätzung und dem multivariaten. Dieses Buch von David Scott könnte in Bezug auf den multivariaten Kernel-Ansatz hilfreich sein, obwohl ich nicht sicher bin, ob er über die Spitzenjagd spricht. amazon.com/…
Michael R. Chernick

Antworten:

7

Die Methode, die zur Rechnung für das passt, was Sie tun möchten, ist der Mean-Shift- Algorithmus. Im Wesentlichen beruht die mittlere Verschiebung auf der Bewegung entlang der Richtung des Gradienten, die nicht parametrisch mit dem "Schatten" eines gegebenen Kerns K geschätzt wird . Wenn also die Dichte f ( x ) durch K geschätzt wird , dann wird f ( x ) durch K ' geschätzt . Details von der Gradienten einer Kerndichteschätz werden dieses beschrieben Papier , das auch den Mean-Shift - Algorithmus zufällig einzuführen.K.'K.f(x)K.f(x)K.'

Eine sehr detaillierte Darstellung des Algorithmus finden Sie auch in diesem Blogeintrag .

Sameer
quelle
3
Larry Wasserman hatte kürzlich einen kürzeren Beitrag, in dem die Technik weniger detailliert beschrieben wurde: The Amazing Mean Shift Algorithm .
Andy W
1
@AndyW Guter Anruf! Larry Wassermans Beitrag (und sein Blog im Allgemeinen) ist großartig. Beim Durchgehen der Kommentare fand ich diese veranschaulichende Referenz zu Mean-Shift, Mediod-Shift und einer Variante, QuickShift.
Sameer
2
Vielen Dank. Ich kann nicht sagen, ob dieser der schnellste ist, aber er findet mit Sicherheit das lokale Maximum. Hier sind einige Diagramme der Flugbahn und Lernrate einiger synthetischer Daten .
tkw954
9

Wenn Ihr Hauptinteresse zweidimensionale Probleme sind, würde ich sagen, dass die Kernel-Dichteschätzung eine gute Wahl ist, da sie schöne asymptotische Eigenschaften hat (beachten Sie, dass ich nicht sage, dass es die beste ist). Siehe zum Beispiel

Parzen, E. (1962). Bei Schätzung einer Wahrscheinlichkeitsdichtefunktion und -mode . Annals of Mathematical Statistics 33: 1065–1076.

de Valpine, P. (2004). Monte-Carlo-Zustandsraumwahrscheinlichkeiten durch gewichtete Schätzung der posterioren Kerndichte . Journal of the American Statistical Association 99: 523 & ndash; 536.

Für höhere Dimensionen (4+) ist diese Methode aufgrund der bekannten Schwierigkeit bei der Schätzung der optimalen Bandbreitenmatrix sehr langsam, siehe .

Das Problem mit dem Befehl ksim Paket KDEbesteht nun, wie Sie bereits erwähnt haben, darin, dass die Dichte in einem bestimmten Raster ausgewertet wird, was sehr einschränkend sein kann. Dieses Problem kann behoben werden, wenn Sie das Paket KDEzum Schätzen der Bandbreitenmatrix verwenden, indem Sie beispielsweise Hscvden Kernel-Dichteschätzer implementieren und diese Funktion dann mit dem Befehl optimieren optim. Dies wird unten anhand simulierter Daten und eines Gaußschen Kernels in gezeigt R.

rm(list=ls())

# Required packages
library(mvtnorm)
library(ks)

# simulated data
set.seed(1)
dat = rmvnorm(1000,c(0,0),diag(2))

# Bandwidth matrix
H.scv=Hlscv(dat)

# [Implementation of the KDE](http://en.wikipedia.org/wiki/Kernel_density_estimation)
H.eig = eigen(H.scv)
H.sqrt = H.eig$vectors %*% diag(sqrt(H.eig$values)) %*% solve(H.eig$vectors)
H = solve(H.sqrt)
dH = det(H.scv)

Gkde = function(par){
return( -log(mean(dmvnorm(t(H%*%t(par-dat)),rep(0,2),diag(2),log=FALSE)/sqrt(dH))))
}

# Optimisation
Max = optim(c(0,0),Gkde)$par
Max

Formbeschränkte Schätzer sind beispielsweise tendenziell schneller

Cule, ML, Samworth, RJ und Stewart, MI (2010). Maximum-Likelihood-Schätzung einer mehrdimensionalen log-konkaven Dichte . Journal Royal Statistical Society B 72: 545–600.

Aber sie sind zu hoch für diesen Zweck.

4

Andere Methoden, die Sie in Betracht ziehen könnten, sind: Anpassen einer multivariaten endlichen Mischung von Normalen (oder anderen flexiblen Verteilungen) oder

Abraham, C., Biau, G. und Cadre, B. (2003). Einfache Schätzung des Modus einer multivariaten Dichte . The Canadian Journal of Statistics 31: 23–34.

Ich hoffe das hilft.

Gemeinschaft
quelle
0

Kürzlich haben wir einen Artikel veröffentlicht, der einen schnellen konsistenten Modusschätzer vorschlägt.

PS Ruzankin und AV Logachov (2019). Ein schneller Modusschätzer im mehrdimensionalen Raum. Statistik & Wahrscheinlichkeitsschreiben

Ö(dn)dn

Ich würde auch die neuen Schätzer für den Minimalvarianzmodus aus meiner jüngsten Arbeit vorschlagen

PS Ruzankin (2020). Eine Klasse nichtparametrischer Modusschätzer. Kommunikation in der Statistik - Simulation und Berechnung

Ö(dn2)nR.d

Pavel Ruzankin
quelle