Abstand zwischen zwei Gaußschen Gemischen zur Bewertung von Clusterlösungen

11

Ich führe eine schnelle Simulation durch, um verschiedene Clustering-Methoden zu vergleichen, und stoße derzeit auf einen Haken beim Versuch, die Cluster-Lösungen zu bewerten.

Ich kenne verschiedene Validierungsmetriken (viele finden sich in cluster.stats () in R), aber ich gehe davon aus, dass diese am besten verwendet werden, wenn die geschätzte Anzahl von Clustern tatsächlich der tatsächlichen Anzahl von Clustern entspricht. Ich möchte die Fähigkeit beibehalten, zu messen, wie gut eine Clustering-Lösung funktioniert, wenn sie nicht die richtige Anzahl von Clustern in der ursprünglichen Simulation angibt (dh wie gut Daten eines Drei-Cluster-Lösungsmodells simuliert wurden, um einen 4-Cluster zu haben Lösung). Nur zu Ihrer Information werden Cluster so simuliert, dass sie identische Kovarianzmatrizen besitzen.

Ich dachte, die KL-Divergenz zwischen zwei Gemischen von Gaußschen wäre nützlich zu implementieren, aber es gibt keine geschlossene Lösung ( Hershey und Olson (2007) ), und die Implementierung einer Monte-Carlo-Simulation beginnt rechenintensiv zu werden.

Gibt es andere Lösungen, die möglicherweise einfach zu implementieren sind (auch wenn es sich nur um eine Annäherung handelt)?

Dmartin
quelle
Der L2-Abstand zwischen zwei Gaußschen Gemischen ist in geschlossener Form verfügbar. Verwenden Sie dies und Sie sollten fertig sein.
Ich weiß nicht, wie Sie es machen würden, aber es klingt für mich nicht nach einer guten Idee. Nehmen Sie eine Mischung, permutieren Sie die Komponenten (keine Änderung von p (x)) und der L2-Abstand kann alles sein. Außerdem ist der L2-Abstand bei Kovarianzmatrizen keine gute Idee.
Bayerj
Posteriore prädiktive Wahrscheinlichkeit eines durchgehaltenen Testdatensatzes. Ich vermute, du brauchst Priors auf k.
Vermutungen
Erster Link ist unterbrochen
ttnphns

Antworten:

6

Angenommen, wir haben zwei Gaußsche Mischungen in : Nennen Sie ihre Dichten bzw. und bezeichnen Sie die Dichten ihrer Komponenten , mit , .Rd

P=i=1nαiPi=i=1nαiN(μi,Σi)Q=j=1mβjQj=j=1mN(mj,Sj).
p()q()PiQjpi(x)=N(x;μi,Σi)qj(x)=N(x;mj,Sj)

Folgende Entfernungen stehen in geschlossener Form zur Verfügung:

  • L2 Abstand, wie in einem Kommentar von user39665 vorgeschlagen. Dies ist: Beachten Sie, dass, wie in Abschnitt 8.1.8 von beispielsweise gesehen die Matrix - Kochbuch : damit dies leicht in Zeit ausgewertet werden kann .

    L2(P,Q)2=(p(x)q(x))2dx=(iαipi(x)jβjqj(x))2dx=i,iαiαipi(x)pi(x)dx+j,jβjβjqj(x)qj(x)dx2i,jαiβjpi(x)qj(x)dx.
    N(x;μ,Σ)N(x;μ,Σ)dx=N(μ;μ,Σ+Σ)
    O(mn)

  • Die maximale mittlere Diskrepanz (MMD) mit einem Gaußschen RBF-Kernel. Dies ist eine coole Distanz, die in der Statistik-Community noch nicht sehr bekannt ist und deren Definition ein wenig Mathematik erfordert.

    Lassen Sie definieren Sie den Hilbert-Raum als der reproduzierende Kernel-Hilbert-Raum, der : .

    k(x,y):=exp(12σ2xy2),
    Hkk(x,y)=φ(x),φ(y)H

    Definieren Sie den mittleren Kartenkern als

    K(P,Q)=EXP,YQk(X,Y)=EXPφ(X),EYQφ(Y).

    Die MMD ist dann

    MMD(P,Q)=EXP[φ(X)]EYQ[φ(Y)]=K(P,P)+K(Q,Q)2K(P,Q)=supf:fH1EXPf(X)EYQf(Y).

    Beachten Sie für unsere Gemische und , dass und ähnlich für und .PQ

    K(P,Q)=i,jαiβjK(Pi,Qj)
    K(P,P)K(Q,Q)

    Es stellt sich heraus, unter Verwendung von ähnlichen Tricks wie für , dass ist L2K(N(μ,Σ),N(μ,Σ))

    (2πσ2)d/2N(μ;μ,Σ+Σ+σ2I).

    Als konvergiert dies eindeutig gegen ein Vielfaches der Distanz. Normalerweise möchten Sie jedoch ein anderes , eines auf der Skala der Datenvariation.σ0L2σ

    Geschlossene Formen sind auch für Polynomkerne in der MMD verfügbar ; sehenk

    Muandet, Fukumizu, Dinuzzo und Schölkopf (2012). Lernen aus Verteilungen über Support Measure Machines. Fortschritte in neuronalen Informationsverarbeitungssystemen ( offizielle Version ). arXiv: 1202,6504 .

    Für viele schöne Eigenschaften dieser Entfernung siehe

    Sriperumbudur, Gretton, Fukumizu, Schölkopf und Lanckriet (2010). Hilbert-Raumeinbettungen und Metriken für Wahrscheinlichkeitsmaße. Journal of Machine Learning Research, 11, 1517–1561 . arXiv: 0907.5309 .

  • Quadratische Jensen-Rényi-Divergenz. Die Rényi- Entropie ist definiert als Seine Grenze als ist die Shannon-Entropie. Die Jensen-Rényi-Divergenz ist wobei eine gleiche Mischung zwischen und . Es stellt sich heraus, dass Sie, wenn und und Gaußsche Gemische sind (wie hier), eine geschlossene Form für berechnen können . Dies wurde von gemachtα

    Hα(p)=11αlog(p(x)αdx).
    α1
    JRα(p,q)=Hα(p+q2)Hα(p)+Hα(q)2
    p+q2pqα=2PQJR2

    Wang, Syeda-Mahmood, Vemuri, Beymer und Rangarajan (2009). Geschlossene Jensen-Renyi-Divergenz für die Mischung von Gaußschen und Anwendungen zur gruppenweisen Formregistrierung. Med Image Comput Comput Assist Interv., 12 (1), 648–655. ( kostenlose Pubmed-Version )

Dougal
quelle
0

Wenn Ihre Cluster eigentlich keine Gaußschen Mischungen sind, sondern willkürlich geformt, können Ihre Ergebnisse tatsächlich viel besser sein, wenn Sie viel mehr Cluster erzeugen, und anschließend einige erneut zusammenführen.

In vielen Fällen wählt man einfach k als willkürlich hoch, z. B. 1000 für einen großen Datensatz; insbesondere, wenn Sie nicht wirklich an den Modellen interessiert sind, sondern nur die Komplexität des Datensatzes durch Vektorquantisierung reduzieren möchten.

Hat aufgehört - Anony-Mousse
quelle
Ich habe die Cluster simuliert, die aus einer Gaußschen Mischung gezogen werden sollen, daher denke ich, dass meine Annahme gültig ist. Das Ziel hierbei ist nicht, die Komplexität zu reduzieren oder ein Entscheidungskriterium für die Auswahl von k zu finden, sondern zu vergleichen, wie gut k Cluster die Daten modellieren, wenn k tatsächlich falsch ist. Einige falsche Entscheidungen modellieren die Daten möglicherweise besser als andere, und ich versuche, diesen Grad der Fehlanpassung mit einigen Berechnungen zu quantifizieren (wie KL-Divergenz, aber für Gaußsche Gemische einfacher zu implementieren).
Dmartin