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)?

clustering kullback-leibler gaussian-mixture 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

6

Suponha que tenhamos duas misturas gaussianas em : Chame suas densidades e , respectivamente, e denote as densidades de seus componentes , por , . $\mathbb R^d$ $\DeclareMathOperator{\N}{\mathcal N} \newcommand{\ud}{\mathrm{d}} \DeclareMathOperator{\E}{\mathbb E} \DeclareMathOperator{\MMD}{\mathrm{MMD}}$

P = \sum_{Eu = 1 1}^{n} α_{Eu} P_{Eu} = \sum_{Eu = 1 1}^{n} α_{Eu} N (μ_{Eu}, Σ_{Eu}) Q = \sum_{j = 1 1}^{m} β_{j} Q_{j} = \sum_{j = 1 1}^{m} N (m_{j}, S_{j}) .

$P = \sum_{i=1}^{n} \alpha_i P_i = \sum_{i=1}^n \alpha_i \N(\mu_i, \Sigma_i) \qquad Q = \sum_{j=1}^m \beta_j Q_j = \sum_{j=1}^m \N(m_j, S_j) .$

p (\cdot)

$p(\cdot)$

q (\cdot)

$q(\cdot)$

P_{i}

$P_i$

Q_{j}

$Q_j$

p_{i} (x) = N (x; μ_{i}, Σ_{i})

$p_i(x) = \N(x; \mu_i, \Sigma_i)$

q_{j} (x) = N (x; m_{j}, S_{j})

$q_j(x) = \N(x; m_j, S_j)$

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

$L_2$ 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 .
$\begin{aligned} L_{2} (P, Q)^{2} & = \int (p (x) - q (x))^{2} d x \\ = \int {(\sum_{Eu} α_{Eu} p_{Eu} (x) - \sum_{j} β_{j} q_{j} (x))}^{2} d x \\ = \sum_{Eu, {Eu}^{'}} α_{Eu} α_{{Eu}^{'}} \int p_{Eu} (x) p_{{Eu}^{'}} (x) d x + \sum_{j, j^{'}} β_{j} β_{j^{'}} \int q_{j} (x) q_{j^{'}} (x) d x \\ - 2 \sum_{Eu, j} α_{Eu} β_{j} \int p_{Eu} (x) q_{j} (x) d x . \end{aligned}$ $\begin{align} L_2(P, Q)^2 &= \int (p(x) - q(x))^2 \,\ud x \\&= \int \left( \sum_{i} \alpha_i p_i(x) - \sum_j \beta_j q_j(x) \right)^2 \ud x \\&= \sum_{i,i'} \alpha_i \alpha_{i'} \int p_i(x) p_{i'}(x) \ud x + \sum_{j,j'} \beta_j \beta_{j'} \int q_j(x) q_{j'}(x) \ud x \\&\qquad - 2 \sum_{i,j} \alpha_i \beta_j \int p_i(x) q_j(x) \ud x .\end{align}$ $\begin{aligned} \int N (x; μ, Σ) N (x; μ^{'}, Σ^{'}) d x & = N (μ; μ^{'}, Σ + Σ^{'}) \end{aligned}$ $\begin{align} \int \N(x; \mu, \Sigma) \N(x; \mu', \Sigma') \,\ud x &= \N(\mu; \mu', \Sigma + \Sigma') \end{align}$ $O(m n)$
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 (- \frac{1 1}{2 σ^{2}}__x - y {__}^{2}),$ $k(x, y) := \exp\left( - \frac{1}{2 \sigma^2} \lVert x - y \rVert^2 \right),$ $\mathcal{H}$ $k$

Defina o kernel médio do mapa como
$K (P, Q) = E_{X \sim P, Y \sim Q} k (X, Y) = ⟨ E_{X \sim P} φ (X), E_{Y \sim Q} φ (Y) ⟩ .$ $K(P, Q) = \E_{X \sim P, Y \sim Q} k(X, Y) = \langle \E_{X \sim P} \varphi(X), \E_{Y \sim Q} \varphi(Y) \rangle .$

O MMD é então
$\begin{aligned} M M D (P, Q) & = ‖ E_{X \sim P} [φ (X)] - E_{Y \sim Q} [φ (Y)] ‖ \\ = \sqrt{K (P, P) + K (Q, Q) - 2 K (P, Q)} \\ = sup_{f : ‖ f ‖_{H} \leq 1} E_{X \sim P} f (X) - E_{Y \sim Q} f (Y) . \end{aligned}$ $\begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[\varphi(X)] - \E_{Y \sim Q}[\varphi(Y)] \rVert \\&= \sqrt{K(P, P) + K(Q, Q) - 2 K(P, Q)} \\&= \sup_{f : \lVert f \rVert_{\mathcal H} \le 1} \E_{X \sim P} f(X) - \E_{Y \sim Q} f(Y) .\end{align}$

Para nossas misturas e , observe que e da mesma forma para e . $P$ $Q$
$K (P, Q) = \sum_{Eu, j} α_{Eu} β_{j} K (P_{Eu}, Q_{j})$ $K(P, Q) = \sum_{i, j} \alpha_i \beta_j K(P_i, Q_j)$ $K(P, P)$

Acontece que, usando truques semelhantes aos de , é $L_2$ $K(\N(\mu, \Sigma), \N(\mu', \Sigma'))$
$(2 π σ^{2})^{d / 2} N (μ; μ^{'}, Σ + Σ^{'} + σ^{2} Eu) .$ $(2 \pi \sigma^2)^{d/2} \N(\mu; \mu', \Sigma + \Sigma' + \sigma^2 I) .$

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. $\sigma \to 0$ $L_2$ $\sigma$

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

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 $\alpha$
$H_{α} (p) = \frac{1 1}{1 1 - α} registro (\int p (x)^{α} d x) .$ $H_\alpha(p) = \frac{1}{1-\alpha} \log\left( \int p(x)^\alpha \,\ud x \right) .$ $\alpha \to 1$ ${J R}_{α} (p, q) = H_{α} (\frac{p + q}{2}) - \frac{H_{α} (p) + H_{α} (q)}{2}$ $\mathrm{JR}_\alpha(p, q) = H_\alpha\left( \frac{p + q}{2} \right) - \frac{H_\alpha(p) + H_\alpha(q)}{2}$ $\frac{p + q}{2}$ $p$ $q$ $\alpha = 2$ $P$ $Q$ $\mathrm{JR}_2$

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

0

Aqui está uma generalização do Mahalanobis D para GMMs usando o método Fisher Kernel e outras técnicas:

Gorjeta, Michael E. "Derivando funções de distância analítica de cluster de modelos de mistura gaussianos". (1999): 815-820. https://pdfs.semanticscholar.org/08d2/0f55442aeb79edfaaaafa7ad54c513ee1dcb.pdf

Veja também: Existe uma versão multi-Gaussiana da distância Mahalanobis?

Lenar Hoyt
fonte

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

Respostas: