Расстояние между двумя гауссовыми смесями для оценки кластерных решений

11

Я провожу быстрое моделирование для сравнения различных методов кластеризации, и в настоящее время попадаю в ловушку, пытаясь оценить кластерные решения.

Мне известны различные метрики проверки (многие из них содержатся в cluster.stats () в R), но я предполагаю, что они лучше всего используются, если предполагаемое количество кластеров фактически равно истинному количеству кластеров. Я хочу сохранить возможность измерять, насколько хорошо работает решение для кластеризации, когда оно не указывает правильное количество кластеров в исходной имитации (т. Е. Насколько хорошо данные модели для трех кластеров, которые были смоделированы, имели 4-кластерный кластер). решение). Просто для вашей информации, кластеры моделируются, чтобы иметь идентичные ковариационные матрицы.

Я думал, что дивергенцию KL между двумя смесями Гауссиана было бы полезно реализовать, но решения в замкнутой форме не существует ( Hershey and Olson (2007) ), и реализация моделирования Монте-Карло начинает становиться вычислительно дорогой.

Существуют ли другие решения, которые могут быть легко реализованы (даже если это только приблизительное значение)?

clustering kullback-leibler gaussian-mixture dmartin
источник

Расстояние L2 между двумя гауссовыми смесями доступно в закрытом виде. Используйте это, и у вас должно быть все готово.

Я не знаю, как вы это сделаете, но для меня это не очень хорошая идея. Возьмите смесь, переставьте компоненты (без изменений в p (x)) и расстояние L2 может быть любым. Кроме того, расстояние L2 не очень хорошая идея для ковариационных матриц.

Bayerj

Предиктивная прогнозирующая вероятность сохраненного тестового набора данных. Я подозреваю, что вам нужны приоры на к хотя.

предположения

Первая ссылка не работает

ttnphns

6

Предположим, у нас есть две гауссовские смеси в : Назовите их плотности и соответственно и обозначим плотности их компонентов , через , . $\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)$

Следующие расстояния доступны в закрытом виде:

$L_2$ Расстояние , как указано в комментарии пользователя 39665. Это: Обратите внимание, что, как видно, например, в разделе 8.1.8 поваренной книги матрицы : так что это можно легко оценить за времени.
$\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)$
Максимальное среднее расхождение (MMD) с ядром гауссова RBF. Это крутая дистанция, еще не очень известная среди статистического сообщества, для определения которой требуется немного математики.

Пусть определим гильбертово пространство как воспроизводящее гильбертово пространство ядра, соответствующее : .
$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$

Определите ядро средней карты как
$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 будет
$\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$ $\sigma$

Замкнутые формы также доступны для полиномиальных ядер в MMD; видеть $k$

Muandet, Fukumizu, Dinuzzo и Schölkopf (2012). Изучение из распределений через машины поддержки мер. Достижения в области нейронных систем обработки информации ( официальная версия ). arXiv: 1202.6504 .

Для много хороших свойств этого расстояния, см.

Sriperumbudur, Gretton, Fukumizu, Schölkopf и Lanckriet (2010). Вложения гильбертова пространства и метрики на вероятностных мерах. Журнал исследований машинного обучения, 11, 1517–1561 . arXiv: 0907.5309 .
Квадратичное расхождение Дженсена-Реньи. Энтропия Рени- определяется как Его предел как является энтропией Шеннона. Расхождение Дженсена-Реньи равно где обозначает равную смесь между и . Оказывается, что когда и когда и являются гауссовыми смесями (как здесь), вы можете вычислить замкнутую форму для . Это было сделано $\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 и Rangarajan (2009). Расхождение Дженсена-Реньи в замкнутой форме для смеси гауссианов и приложения к групповой регистрации форм. Med Image Comput Comput Assist Interv., 12 (1), 648–655. ( бесплатная опубликованная версия )

Дугал
источник

0

Если ваши кластеры на самом деле не являются гауссовыми смесями, а имеют произвольную форму, ваши результаты могут быть намного лучше, когда вы создаете гораздо больше кластеров, а затем объединяете некоторые из них снова.

Во многих случаях просто выбирают k как произвольно высокий, например, 1000 для большого набора данных; в частности, когда вы на самом деле не интересуетесь моделями, а просто хотите уменьшить сложность набора данных с помощью векторного квантования.

ВЫЙТИ - Anony-Mousse
источник

Я смоделировал кластеры, которые будут взяты из гауссовой смеси, поэтому я думаю, что мое предположение верно. Цель здесь не состоит в том, чтобы уменьшить сложность или придумать критерий принятия решения для выбора k, но сравнить, насколько хорошо k кластеров моделирует данные, когда k фактически неверно. Некоторые неправильные варианты могут моделировать данные лучше, чем другие, и я пытаюсь количественно оценить эту степень несоответствия с помощью некоторых вычислений (например, дивергенция KL, но ее легче реализовать для гауссовых смесей).

dmartin

0

Вот обобщение Mahalanobis D для GMM с использованием метода ядра Фишера и других методов:

Типпинг, Майкл Э. «Получение кластерных аналитических дистанционных функций из моделей гауссовой смеси». (1999): 815-820. https://pdfs.semanticscholar.org/08d2/0f55442aeb79edfaaaafa7ad54c513ee1dcb.pdf

Ленар Хойт
источник

Расстояние между двумя гауссовыми смесями для оценки кластерных решений

Ответы: