Jarak antara dua campuran Gaussian untuk mengevaluasi solusi cluster

11

Saya sedang menjalankan simulasi cepat untuk membandingkan metode pengelompokan yang berbeda, dan saat ini mengalami kesulitan mencoba untuk mengevaluasi solusi cluster.

Saya tahu berbagai metrik validasi (banyak ditemukan di cluster.stats () di R), tetapi saya menganggap itu paling baik digunakan jika perkiraan jumlah cluster sebenarnya sama dengan jumlah sebenarnya dari cluster. Saya ingin mempertahankan kemampuan untuk mengukur seberapa baik kinerja suatu solusi clustering ketika itu tidak menentukan jumlah cluster yang benar dalam simulasi asli (yaitu, seberapa baik data model solusi tiga cluster yang disimulasikan untuk memiliki 4-cluster larutan). Sekadar informasi Anda, cluster disimulasikan untuk memiliki matriks kovarian yang identik.

Saya pikir perbedaan KL antara dua campuran Gaussians akan berguna untuk diterapkan, tetapi tidak ada solusi bentuk tertutup ( Hershey dan Olson (2007) ) dan menerapkan simulasi Monte Carlo mulai mahal secara komputasi.

Apakah ada solusi lain yang mungkin mudah diimplementasikan (bahkan jika hanya perkiraan)?

clustering kullback-leibler gaussian-mixture dmartin
sumber

Jarak L2 antara dua campuran Gaussian tersedia dalam bentuk tertutup. Gunakan ini dan Anda harus siap.

Saya tidak tahu bagaimana Anda akan melakukannya, tetapi itu kedengarannya bukan ide yang baik bagi saya. Ambil campuran, permutasi komponen (tidak ada perubahan ke p (x)) dan jarak L2 bisa apa saja. Juga, jarak L2 bukan ide yang baik pada matriks kovarian.

bayerj

Probabilitas prediktif posterior dari dataset uji yang diulurkan. Saya menduga Anda akan membutuhkan prior pada k.

Dugaan

Tautan pertama terputus

ttnphns

6

Misalkan kita memiliki dua campuran Gaussian di : Panggil kepadatan mereka dan , masing-masing, dan menunjukkan kepadatan komponen mereka , oleh , . $\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)$

Jarak-jarak berikut tersedia dalam bentuk tertutup:

$L_2$ jarak, seperti yang disarankan dalam komentar oleh user39665. Ini adalah: Perhatikan bahwa, seperti yang terlihat misalnya dalam bagian 8.1.8 dari buku masak matriks : sehingga ini dapat dievaluasi dengan mudah dalam waktu .
$\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)$
Perbedaan rata-rata maksimum (MMD) dengan kernel Gaussian RBF. Ini adalah jarak yang keren, belum terkenal di antara komunitas statistik, yang membutuhkan sedikit matematika untuk didefinisikan.

Membiarkan tentukan ruang Hilbert sebagai kernel Hilbert mereproduksi sesuai dengan : .
$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$

Tentukan kernel peta rata - rata sebagai
$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 kemudian
$\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}$

Untuk campuran dan , perhatikan bahwa dan demikian pula untuk dan . $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)$

Ternyata, menggunakan trik serupa seperti untuk , bahwa adalah $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) .$

Sebagai , jelas ini menyatu dengan kelipatan dari jarak . Anda biasanya ingin menggunakan berbeda , meskipun, satu pada skala variasi data. $\sigma \to 0$ $L_2$ $\sigma$

Formulir tertutup juga tersedia untuk kernel polinomial dalam MMD; Lihat $k$

Muandet, Fukumizu, Dinuzzo, dan Schölkopf (2012). Belajar dari Distribusi melalui Mesin Pengukur Dukungan. Dalam Kemajuan dalam Sistem Pemrosesan Informasi Saraf Tiruan ( versi resmi ). arXiv: 1202.6504 .

Untuk banyak properti bagus dari jarak ini, lihat

Sriperumbudur, Gretton, Fukumizu, Schölkopf, dan Lanckriet (2010). Embeddings dan metrik ruang Hilbert pada ukuran probabilitas. Jurnal Penelitian Pembelajaran Mesin, 11, 1517-1561 . arXiv: 0907.5309 .
Divergensi Jensen-Rényi kuadratik. Entropi Rényi- didefinisikan sebagai Batasnya sebagai adalah entropi Shannon. Divergensi Jensen-Rényi adalah mana menunjukkan campuran yang sama antara dan . Ternyata, ketika dan ketika dan adalah campuran Gaussian (seperti di sini), Anda dapat menghitung formulir tertutup untuk . Ini dilakukan oleh $\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, dan Rangarajan (2009). Divergensi Jensen-Renyi Bentuk Tertutup untuk Campuran Gaussians dan Aplikasi pada Registrasi Bentuk Bijaksana Kelompok. Med Image Comput Comput Assist Interv., 12 (1), 648-655. ( versi dipublikasikan gratis )

Dougal
sumber

0

Jika cluster Anda sebenarnya bukan campuran Gaussian tetapi dibentuk secara sewenang-wenang, hasil Anda mungkin sebenarnya jauh lebih baik ketika Anda menghasilkan lebih banyak cluster, kemudian menggabungkannya lagi setelahnya.

Dalam banyak kasus, seseorang hanya memilih k menjadi tinggi sewenang-wenang, misalnya 1000 untuk kumpulan data besar; khususnya ketika Anda tidak benar-benar tertarik pada model, tetapi hanya ingin mengurangi kerumitan set data melalui kuantisasi vektor.

Memiliki QUIT - Anony-Mousse
sumber

Saya mensimulasikan cluster yang akan diambil dari campuran Gaussian, jadi saya pikir asumsi saya valid. Tujuannya di sini bukan untuk mengurangi kerumitan atau menghasilkan kriteria keputusan untuk memilih k, tetapi untuk membandingkan seberapa baik k cluster memodelkan data ketika k sebenarnya tidak benar. Beberapa pilihan yang salah mungkin memodelkan data lebih baik daripada yang lain, dan saya mencoba untuk mengukur tingkat ketidakcocokan ini dengan beberapa perhitungan (seperti divergensi KL, tetapi lebih mudah diterapkan untuk campuran Gaussian).

dmartin

0

Berikut ini adalah generalisasi dari Mahalanobis D ke GMM menggunakan metode Fisher Kernel dan teknik lainnya:

Tipping, Michael E. "Mendapatkan fungsi jarak analitik kluster dari model campuran Gaussian." (1999): 815-820. https://pdfs.semanticscholar.org/08d2/0f55442aeb79edfaaaafa7ad54c513ee1dcb.pdf

Lihat juga: Apakah ada versi multi-Gaussian untuk jarak Mahalanobis?

Lenar Hoyt
sumber

Jarak antara dua campuran Gaussian untuk mengevaluasi solusi cluster

Jawaban: