Distancia entre dos mezclas gaussianas para evaluar soluciones de clúster

11

Estoy ejecutando una simulación rápida para comparar diferentes métodos de agrupación, y actualmente me encuentro con un problema tratando de evaluar las soluciones de agrupación.

Conozco varias métricas de validación (muchas de ellas se encuentran en cluster.stats () en R), pero supongo que es mejor usarlas si el número estimado de clústeres en realidad es igual al número real de clústeres. Quiero mantener la capacidad de medir qué tan bien funciona una solución de agrupación cuando no especifica el número correcto de agrupaciones en la simulación original (es decir, qué tan bien simulan los datos de un modelo de solución de tres agrupaciones que tienen 4 agrupaciones solución). Solo para su información, los clústeres se simulan para poseer matrices de covarianza idénticas.

Pensé que la divergencia KL entre dos mezclas de gaussianos sería útil para implementar, pero no existe una solución de forma cerrada ( Hershey y Olson (2007) ) y la implementación de una simulación de Monte Carlo está comenzando a ser computacionalmente costosa.

¿Hay alguna otra solución que pueda ser fácil de implementar (aunque solo sea una aproximación)?

clustering kullback-leibler gaussian-mixture dmartin
fuente

La distancia L2 entre dos mezclas gaussianas está disponible en forma cerrada. Usa esto y deberías estar listo.

No sé cómo lo harías, pero no me parece una buena idea. Tome una mezcla, permute los componentes (sin cambios en p (x)) y la distancia L2 puede ser cualquier cosa. Además, la distancia L2 no es una buena idea en las matrices de covarianza.

bayerj

Probabilidad predictiva posterior de un conjunto de datos de prueba extendido. Sin embargo, sospecho que necesitarías antecedentes en k.

conjeturas

El primer enlace está roto

ttnphns

6

Supongamos que tenemos dos mezclas gaussianas en : Llame a sus densidades y , respectivamente, y denote las densidades de sus componentes , por , . $\mathbb R^d$ $\DeclareMathOperator{\N}{\mathcal N} \newcommand{\ud}{\mathrm{d}} \DeclareMathOperator{\E}{\mathbb E} \DeclareMathOperator{\MMD}{\mathrm{MMD}}$

P = \sum_{i = 1}^{n} α_{i} P_{i} = \sum_{i = 1}^{n} α_{i} N (μ_{i}, Σ_{i}) Q = \sum_{j = 1}^{m} β_{j} Q_{j} = \sum_{j = 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)$

Las siguientes distancias están disponibles en forma cerrada:

$L_2$ Distancia , como se sugiere en un comentario del usuario39665. Esto es: Tenga en cuenta que, como se ve por ejemplo en la sección 8.1.8 del libro de recetas de matriz : para que esto pueda evaluarse fácilmente en tiempo .
$\begin{aligned} L_{2} (P, Q)^{2} & = \int (p (x) - q (x))^{2} d x \\ = \int {(\sum_{i} α_{i} p_{i} (x) - \sum_{j} β_{j} q_{j} (x))}^{2} d x \\ = \sum_{i, i^{'}} α_{i} α_{i^{'}} \int p_{i} (x) p_{i^{'}} (x) d x + \sum_{j, j^{'}} β_{j} β_{j^{'}} \int q_{j} (x) q_{j^{'}} (x) d x \\ - 2 \sum_{i, j} α_{i} β_{j} \int p_{i} (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)$
La máxima discrepancia media (MMD) con un núcleo gaussiano RBF. Esta es una distancia genial, aún no muy conocida entre la comunidad estadística, que requiere un poco de matemática para definirla.

Dejando defina el espacio de Hilbert como el espacio de Hilbert del núcleo de reproducción correspondiente a : .
$k (x, y) := \exp (- \frac{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 el núcleo del mapa medio 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 .$

El MMD es entonces
$\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 nuestras mezclas y , tenga en cuenta que y de manera similar para y . $P$ $Q$
$K (P, Q) = \sum_{i, j} α_{i} β_{j} K (P_{i}, Q_{j})$ $K(P, Q) = \sum_{i, j} \alpha_i \beta_j K(P_i, Q_j)$ $K(P, P)$

Resulta, usando trucos similares a los de , que es $L_2$ $K(\N(\mu, \Sigma), \N(\mu', \Sigma'))$
$(2 π σ^{2})^{d / 2} N (μ; μ^{'}, Σ + Σ^{'} + σ^{2} I) .$ $(2 \pi \sigma^2)^{d/2} \N(\mu; \mu', \Sigma + \Sigma' + \sigma^2 I) .$

Como , claramente esto converge a un múltiplo de la distancia . Sin embargo, normalmente querrá usar un diferente , uno en la escala de la variación de datos. $\sigma \to 0$ $L_2$ $\sigma$

Los formularios cerrados también están disponibles para los núcleos polinomiales en el MMD; ver $k$

Muandet, Fukumizu, Dinuzzo y Schölkopf (2012). Aprendizaje de distribuciones a través de máquinas de medición de soporte. En Avances en sistemas de procesamiento de información neuronal ( versión oficial ). arXiv: 1202.6504 .

Para ver muchas propiedades agradables de esta distancia, vea

Sriperumbudur, Gretton, Fukumizu, Schölkopf y Lanckriet (2010). Integraciones espaciales de Hilbert y métricas sobre medidas de probabilidad. Journal of Machine Learning Research, 11, 1517-1561 . arXiv: 0907.5309 .
Divergencia cuadrática Jensen-Rényi. La entropía Rényi- se define como Su límite como es la entropía de Shannon. La divergencia Jensen-Rényi es donde denota una mezcla a partes iguales entre y . Resulta que, cuando y cuando y son mezclas gaussianas (como aquí), puede calcular una forma cerrada para . Esto fue hecho por $\alpha$
$H_{α} (p) = \frac{1}{1 - α} \log (\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 y Rangarajan (2009). Divergencia Jensen-Renyi de forma cerrada para la mezcla de gaussianos y aplicaciones para el registro de formas grupales. Med Image Comput Comput Assist Interv., 12 (1), 648–655. ( versión gratuita de pubmed )

Dougal
fuente

0

Si los grupos son en realidad no mezclas de gaussianas, pero de forma arbitraria, sus resultados pueden ser en realidad mucho mejor cuando se producen mucho más racimos, y luego fusionar algunos de nuevo después.

En muchos casos, uno elige que k sea arbitrariamente alto, por ejemplo, 1000 para un conjunto de datos grande; en particular cuando no estás realmente interesado en los modelos, pero solo quieres reducir la complejidad del conjunto de datos a través de la cuantificación vectorial.

HA SALIDO - Anony-Mousse
fuente

Simulé que los grupos se extrajeron de una mezcla gaussiana, por lo que creo que mi suposición es válida. El objetivo aquí no es reducir la complejidad o idear un criterio de decisión para elegir k, sino comparar qué tan bien los clústeres de k modelan los datos cuando k es realmente incorrecto. Algunas opciones incorrectas podrían modelar los datos mejor que otras, y estoy tratando de cuantificar este grado de desajuste con algún cálculo (como la divergencia KL, pero más fácil de implementar para mezclas gaussianas).

dmartin

0

Aquí hay una generalización de Mahalanobis D a GMMs usando el método Fisher Kernel y otras técnicas:

Propinas, Michael E. "Derivando funciones de distancia analítica de clúster a partir de modelos de mezcla gaussianos". (1999): 815-820. https://pdfs.semanticscholar.org/08d2/0f55442aeb79edfaaaafa7ad54c513ee1dcb.pdf

Ver también: ¿Existe una versión multi-gaussiana de la distancia de Mahalanobis?

Lenar Hoyt
fuente

Distancia entre dos mezclas gaussianas para evaluar soluciones de clúster

Respuestas: