Odległość między dwiema mieszankami gaussowskimi do oceny rozwiązań klastrowych

11

Korzystam z szybkiej symulacji, aby porównać różne metody klastrowania, i obecnie mam problem z oceną rozwiązań klastrowych.

Znam różne miary sprawdzania poprawności (wiele z nich znajduje się w klaster.stats () w R), ale zakładam, że najlepiej je wykorzystać, jeśli szacunkowa liczba klastrów faktycznie równa się prawdziwej liczbie klastrów. Chcę zachować możliwość pomiaru, jak dobrze działa rozwiązanie klastrowania, gdy nie określa ono prawidłowej liczby klastrów w oryginalnej symulacji (tj. Jak dobrze dane modelu rozwiązania z trzema klastrami, które zostały zasymulowane, mają 4-klaster rozwiązanie). Tylko dla twojej informacji, klastry są symulowane, aby posiadać identyczne macierze kowariancji.

Myślałem, że rozbieżność KL między dwiema mieszaninami Gaussów byłaby użyteczna do wdrożenia, ale nie istnieje żadne rozwiązanie w formie zamkniętej ( Hershey i Olson (2007) ), a wdrożenie symulacji Monte Carlo zaczyna być kosztownie obliczeniowe.

Czy są jakieś inne rozwiązania, które mogą być łatwe do wdrożenia (nawet jeśli są tylko przybliżeniem)?

dmartin
źródło
Odległość L2 między dwiema mieszankami gaussowskimi jest dostępna w formie zamkniętej. Użyj tego i powinieneś być gotowy.
Nie wiem, jak byś to zrobił, ale nie wydaje mi się to dobrym pomysłem. Weź mieszaninę, permutuj składniki (bez zmiany na p (x)), a odległość L2 może być dowolna. Ponadto odległość L2 nie jest dobrym pomysłem na macierzach kowariancji.
bayerj
Prawdopodobieństwo predykcyjne późniejsze zbioru danych testowych. Podejrzewam jednak, że będziesz potrzebować priors na k.
przypuszcza
Pierwszy link jest zepsuty
ttnphns

Odpowiedzi:

6

Załóżmy, że mamy dwa Gaussa mieszaniny w Rd :

P=i=1nαiPi=i=1nαiN(μi,Σi)Q=j=1mβjQj=j=1mN(mj,Sj).
Nazwij ich gęstości odpowiedniop() iq() , i oznacz gęstość ich składnikówPi ,Qj przezpi(x)=N(x;μi,Σi) ,qj(x)=N(x;mj,Sj) .

Następujące odległości są dostępne w formie zamkniętej:

  • L2Odległość L 2 , zgodnie z sugestią użytkownika39665. To jest:

    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.
    Należy zauważyć, że jak widać na przykład w sekcji 8.1.8matrycowej książki kucharskiej:
    N(x;μ,Σ)N(x;μ,Σ)dx=N(μ;μ,Σ+Σ)
    więc można to łatwo ocenić w czasieO(mn).

  • Maksymalna średnia rozbieżność (MMD) z jądrem Gaussa RBF. To fajny dystans, który nie jest jeszcze zbyt dobrze znany społeczności statystyk, którego zdefiniowanie zajmuje trochę matematyki.

    Pozwalając

    k(x,y):=exp(12σ2xy2),
    określenie HilbertaHco jądro odtwarzające Hilberta przestrzeni odpowiadającejk:k(x,y)=φ(x),φ(y)H.

    Określić średnią jądra mapę jako

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

    MMD to wtedy

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

    PQ

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

    L2K(N(μ,Σ),N(μ,Σ))

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

    σ0L.2)dystans. Zwykle chcesz użyć innegoσjednak jeden w skali zmienności danych.

    Formularze zamknięte są również dostępne dla jąder wielomianowych kw MMD; widzieć

    Muandet, Fukumizu, Dinuzzo i Schölkopf (2012). Uczenie się z dystrybucji za pośrednictwem maszyn do pomiaru wsparcia. W Advances in Neural Information Processing Systems ( oficjalna wersja ). arXiv: 1202,6504 .

    Aby zobaczyć wiele fajnych właściwości tej odległości, zobacz

    Sriperumbudur, Gretton, Fukumizu, Schölkopf i Lanckriet (2010). Osadzanie przestrzeni kosmicznej Hilberta i miary dotyczące miar prawdopodobieństwa. Journal of Machine Learning Research, 11, 1517–1561 . arXiv: 0907.5309 .

  • Kwadratowa dywergencja Jensen-Rényi. The Rényi-α entropia jest zdefiniowana jako

    Hα(p)=11αlog(p(x)αdx).
    Its limit as α1 is the Shannon entropy. The Jensen-Rényi divergence is
    JRα(p,q)=Hα(p+q2)Hα(p)+Hα(q)2
    where p+q2 denotes an equal mixture between p and q. It turns out that, when α=2 and when P and Q are Gaussian mixtures (as here), you can compute a closed form for JR2. This was done by

    Wang, Syeda-Mahmood, Vemuri, Beymer, and Rangarajan (2009). Closed-Form Jensen-Renyi Divergence for Mixture of Gaussians and Applications to Group-Wise Shape Registration. Med Image Comput Comput Assist Interv., 12(1), 648–655. (free pubmed version)

Dougal
źródło
0

If your clusters are actually not Gaussian mixtures but arbitrarily shaped, your results may actually be much better when you produce much more clusters, then merge some again afterwards.

In many cases, one just chooses k to be arbitrarily high, e.g. 1000 for a large data set; in particular when you aren't really interested in the models, but just want to reduce the complexity of the data set via vector quantization.

Has QUIT--Anony-Mousse
źródło
I simulated the clusters to be drawn from a Gaussian mixture, so I think my assumption is valid. The goal here is not to reduce complexity or come up with a decision criterion for choosing k, but to compare how well k clusters models the data when k is actually incorrect. Some incorrect choices might model the data better than others, and I'm trying to quantify this degree of misfit with some calculation (like KL divergence, but easier to implement for Gaussian mixtures).
dmartin