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

clustering kullback-leibler gaussian-mixture

— 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

6

Załóżmy, że mamy dwa Gaussa mieszaniny w $\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) .$ Nazwij ich gęstości odpowiednio

p (\cdot)

$p(\cdot)$ i

q (\cdot)

$q(\cdot)$ , i oznacz gęstość ich składników

P_{i}

$P_i$ ,

Q_{j}

$Q_j$ przez

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)$ .

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

$L_2$ Odległość , zgodnie z sugestią użytkownika39665. To jest:
$\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}$ Należy zauważyć, że jak widać na przykład w sekcji 8.1.8matrycowej książki kucharskiej: $\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}$ więc można to łatwo ocenić w czasie $O(m n)$ .
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 (- \frac{1}{2 σ^{2}} ‖ x - y ‖^{2}),$ $k(x, y) := \exp\left( - \frac{1}{2 \sigma^2} \lVert x - y \rVert^2 \right),$ określenie Hilberta $\mathcal{H}$ co jądro odtwarzające Hilberta przestrzeni odpowiadającej $k$ :.

Określić średnią jądra mapę jako
$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 .$

MMD to wtedy
$\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}$

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

$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) .$

$\sigma \to 0$ $L_2$ dystans. Zwykle chcesz użyć innego $\sigma$ jednak jeden w skali zmienności danych.

Formularze zamknięte są również dostępne dla jąder wielomianowych $k$ w 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- $\alpha$ entropia jest zdefiniowana jako
$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) .$ Its limit as $\alpha \to 1$ is the Shannon entropy. The Jensen-Rényi divergence is ${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}$ where $\frac{p + q}{2}$ denotes an equal mixture between $p$ and $q$ . It turns out that, when $\alpha = 2$ and when $P$ and $Q$ are Gaussian mixtures (as here), you can compute a closed form for $\mathrm{JR}_2$ . 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

0

Here is a generalization of the Mahalanobis D to GMMs using the Fisher Kernel method and other techniques:

Tipping, Michael E. "Deriving cluster analytic distance functions from Gaussian mixture models." (1999): 815-820. https://pdfs.semanticscholar.org/08d2/0f55442aeb79edfaaaafa7ad54c513ee1dcb.pdf

— Lenar Hoyt
źródło