Distance entre deux mélanges gaussiens pour évaluer les solutions de cluster

11

J'exécute une simulation rapide pour comparer différentes méthodes de clustering et je suis actuellement confronté à un problème en essayant d'évaluer les solutions de cluster.

Je connais différentes métriques de validation (beaucoup se trouvent dans cluster.stats () dans R), mais je suppose que celles-ci sont mieux utilisées si le nombre estimé de clusters est réellement égal au nombre réel de clusters. Je souhaite conserver la capacité de mesurer la performance d'une solution de clustering lorsqu'elle ne spécifie pas le nombre correct de clusters dans la simulation d'origine (c.-à-d. La qualité des données d'un modèle de solution à trois clusters simulés pour avoir un cluster à 4 clusters) Solution). Juste pour votre information, les clusters sont simulés pour posséder des matrices de covariance identiques.

Je pensais que la divergence KL entre deux mélanges de gaussiens serait utile à mettre en œuvre, mais aucune solution de forme fermée n'existe ( Hershey et Olson (2007) ) et la mise en œuvre d'une simulation de Monte Carlo commence à être coûteuse en termes de calcul.

Existe-t-il d'autres solutions qui pourraient être faciles à mettre en œuvre (même si ce n'est qu'une approximation)?

dmartin
la source
La distance L2 entre deux mélanges gaussiens est disponible sous forme fermée. Utilisez-le et vous devriez être prêt.
Je ne sais pas comment tu le ferais, mais cela ne me semble pas une bonne idée. Prenez un mélange, permutez les composants (pas de changement à p (x)) et la distance L2 peut être n'importe quoi. De plus, la distance L2 n'est pas une bonne idée sur les matrices de covariance.
bayerj
Probabilité prédictive postérieure d'un ensemble de données de test retenu. Je suppose que vous auriez besoin de priors sur k cependant.
conjectures
Le premier lien est rompu
ttnphns

Réponses:

6

Supposons que nous ayons deux mélanges gaussiens dans : Appelons leurs densités et , respectivement, et dénotons les densités de leurs composantes , par , .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)

Les distances suivantes sont disponibles sous forme fermée:

  • L2Distance , comme suggéré dans un commentaire de user39665. C'est: Notez que, comme le montre par exemple la section 8.1.8 du livre de recettes matriciel : donc cela peut être évalué facilement en temps .

    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)

  • L'écart moyen maximum (MMD) avec un noyau RBF gaussien. Il s'agit d'une distance intéressante, pas encore très bien connue de la communauté des statistiques, qui nécessite un peu de mathématiques pour être définie.

    Soit définissez l'espace Hilbert comme l'espace Hilbert du noyau reproducteur correspondant à : .

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

    Définissez le noyau de carte moyen comme

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

    Le MMD est alors

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

    Pour nos mélanges et , notons que et de même pour et .PQ

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

    Il s'avère, en utilisant des astuces similaires à celles de , que est L2K(N(μ,Σ),N(μ,Σ))

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

    Comme , cela converge clairement vers un multiple de la distance . Vous voudriez normalement utiliser un différent , cependant, un à l'échelle de la variation des données.σ0L2σ

    Des formes fermées sont également disponibles pour les noyaux polynomiaux dans le MMD; voirk

    Muandet, Fukumizu, Dinuzzo et Schölkopf (2012). Apprendre des distributions via des machines de mesure de support. In Advances in Neural Information Processing Systems ( version officielle ). arXiv: 1202.6504 .

    Pour beaucoup de belles propriétés de cette distance, voir

    Sriperumbudur, Gretton, Fukumizu, Schölkopf et Lanckriet (2010). Plongements dans l'espace de Hilbert et métriques sur les mesures de probabilité. Journal of Machine Learning Research, 11, 1517–1561 . arXiv: 0907.5309 .

  • Divergence quadratique Jensen-Rényi. L' entropie Rényi- est définie comme Sa limite comme est l'entropie de Shannon. La divergence Jensen-Rényi est où désigne un mélange égal entre et . Il s'avère que, lorsque et lorsque et sont des mélanges gaussiens (comme ici), vous pouvez calculer une forme fermée pour . Cela a été fait parα

    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 et Rangarajan (2009). Divergence de Jensen-Renyi sous forme fermée pour le mélange de gaussiens et applications à l'enregistrement de forme en groupe. Med Image Comput Comput Assist Interv., 12 (1), 648–655. ( version gratuite publiée )

Dougal
la source
0

Si vos clusters ne sont en fait pas des mélanges gaussiens mais qu'ils ont une forme arbitraire, vos résultats peuvent en fait être bien meilleurs lorsque vous produisez beaucoup plus de clusters, puis en fusionnez à nouveau par la suite.

Dans de nombreux cas, on choisit simplement k comme étant arbitrairement élevé, par exemple 1000 pour un grand ensemble de données; en particulier lorsque vous n'êtes pas vraiment intéressé par les modèles, mais que vous souhaitez simplement réduire la complexité de l'ensemble de données via la quantification vectorielle.

A QUIT - Anony-Mousse
la source
J'ai simulé les grappes à tirer d'un mélange gaussien, donc je pense que mon hypothèse est valide. Le but ici n'est pas de réduire la complexité ou de proposer un critère de décision pour choisir k, mais de comparer la façon dont k clusters modélise les données lorsque k est réellement incorrect. Certains choix incorrects pourraient mieux modéliser les données que d'autres, et j'essaie de quantifier ce degré de décalage avec certains calculs (comme la divergence KL, mais plus facile à implémenter pour les mélanges gaussiens).
dmartin