Distância entre duas misturas gaussianas para avaliar soluções de cluster

11

Estou executando uma simulação rápida para comparar diferentes métodos de cluster e atualmente enfrenta um problema ao tentar avaliar as soluções de cluster.

Conheço várias métricas de validação (muitas encontradas em cluster.stats () em R), mas presumo que sejam melhor utilizadas se o número estimado de clusters for igual ao número real de clusters. Desejo manter a capacidade de medir o desempenho de uma solução de cluster quando não especificar o número correto de clusters na simulação original (ou seja, quão bem uma solução de três clusters modela dados que foram simulados para ter um cluster de quatro clusters solução). Apenas para sua informação, os clusters são simulados para possuir matrizes de covariância idênticas.

Eu pensei que a divergência de KL entre duas misturas de Gaussians seria útil para implementar, mas não existe uma solução de forma fechada ( Hershey e Olson (2007) ) e a implementação de uma simulação de Monte Carlo está começando a ser computacionalmente cara.

Existem outras soluções que podem ser fáceis de implementar (mesmo que apenas uma aproximação)?

dmartin
fonte
A distância L2 entre duas misturas gaussianas está disponível em forma fechada. Use isso e você deve estar pronto.
Não sei como você faria isso, mas não me parece uma boa ideia. Pegue uma mistura, permita os componentes (nenhuma alteração para p (x)) e a distância L2 pode ser qualquer coisa. Além disso, a distância L2 não é uma boa ideia em matrizes de covariância.
bayerj
Probabilidade preditiva posterior de um conjunto de dados de teste estendido. Eu suspeito que você precisaria de anteriores em k embora.
conjecturas
O primeiro link está quebrado
ttnphns

Respostas:

6

Suponha que tenhamos duas misturas gaussianas em : Chame suas densidades e , respectivamente, e denote as densidades de seus componentes , por , .Rd

P=Eu=1 1nαEuPEu=Eu=1 1nαEuN(μEu,ΣEu)Q=j=1 1mβjQj=j=1 1mN(mj,Sj).
p()q()PEuQjpEu(x)=N(x;μEu,ΣEu)qj(x)=N(x;mj,Sj)

As seguintes distâncias estão disponíveis em formato fechado:

  • eu2 distância, conforme sugerido em um comentário do usuário39665. Isto é: Observe que, como visto, por exemplo, na seção 8.1.8 do livro de receitas da matriz : para que isso possa ser avaliado facilmente em .

    L2(P,Q)2=(p(x)q(x))2dx=(EuαEupEu(x)-jβjqj(x))2dx=Eu,EuαEuαEupEu(x)pEu(x)dx+j,jβjβjqj(x)qj(x)dx-2Eu,jαEuβjpEu(x)qj(x)dx.
    N ( x ; μ , Σ ) N ( x ; μ , Σ )
    N(x;μ,Σ)N(x;μ,Σ)dx=N(μ;μ,Σ+Σ)
    O(mn)

  • A discrepância média máxima (MMD) com um kernel Gaussian RBF. Essa é uma distância interessante, ainda não muito conhecida entre a comunidade de estatísticas, que requer um pouco de matemática para definir.

    Deixando defina o espaço de Hilbert como o espaço Hilbert do núcleo em reprodução correspondente a : .

    k(x,y): =exp(-1 12σ2__x-y__2),
    Hkk(x,y)=φ(x),φ(y)H

    Defina o kernel médio do mapa como

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

    O MMD é então

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

    Para nossas misturas e , observe que e da mesma forma para e .PQ

    K(P,Q)=Eu,jαEuβjK(PEu,Qj)
    K(P,P)K(Q,Q)

    Acontece que, usando truques semelhantes aos de , é eu2K(N(μ,Σ),N(μ,Σ))

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

    Como , isso claramente converge para um múltiplo da distância . Normalmente, você deseja usar um diferente , um na escala da variação de dados.σ0 0eu2σ

    Os formulários fechados também estão disponíveis para os núcleos polinomiais no MMD; Vejok

    Muandet, Fukumizu, Dinuzzo e Schölkopf (2012). Aprendendo com distribuições por meio de máquinas de medida de suporte. In Advances in Neural Information Processing Systems ( versão oficial ). arXiv: 1202.6504 .

    Para muitas propriedades agradáveis ​​dessa distância, consulte

    Sriperumbudur, Gretton, Fukumizu, Schölkopf e Lanckriet (2010). Incorporações e métricas espaciais de Hilbert sobre medidas de probabilidade. Journal of Machine Learning Research, 11, 1517–1561 . arXiv: 0907.5309 .

  • Divergência quadrática de Jensen-Rényi. A entropia Rényi- é definida como Seu limite como é a entropia de Shannon. A divergência Jensen-Rényi é onde denota uma mistura igual entre e . Acontece que, quando e quando e são misturas gaussianas (como aqui), você pode calcular um formulário fechado para . Isso foi feito porα

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

    Wang, Syeda-Mahmood, Vemuri, Beymer e Rangarajan (2009). Divergência Jensen-Renyi de formato fechado para mistura de gaussianos e aplicações para registro de formas de grupo sábio. Med Image Comput Comput Assist Interv., 12 (1), 648–655. ( versão pubmed gratuita )

Dougal
fonte
0

Se seus clusters não são na verdade misturas gaussianas, mas modelados arbitrariamente, seus resultados podem ser muito melhores quando você produz muito mais clusters, depois mescla alguns novamente.

Em muitos casos, apenas se escolhe k como arbitrariamente alto, por exemplo, 1000 para um grande conjunto de dados; especialmente quando você não está realmente interessado nos modelos, mas apenas deseja reduzir a complexidade do conjunto de dados via quantização vetorial.

Possui QUIT - Anony-Mousse
fonte
Simulei os clusters a serem extraídos de uma mistura gaussiana, então acho que minha suposição é válida. O objetivo aqui não é reduzir a complexidade ou criar um critério de decisão para a escolha de k, mas comparar o quão bem os clusters k modelam os dados quando k está realmente incorreto. Algumas escolhas incorretas podem modelar os dados melhor que outras, e estou tentando quantificar esse grau de desajuste com algum cálculo (como divergência de KL, mas mais fácil de implementar para misturas gaussianas).
dmartin