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

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

Jawaban:

6

Misalkan kita memiliki dua campuran Gaussian di : Panggil kepadatan mereka dan , masing-masing, dan menunjukkan kepadatan komponen mereka , oleh , .Rd

P=i=1nαiPi=i=1nαiN(μi,Σi)Q=j=1mβjQj=j=1mN(mj,Sj).
p()q()PiQjpi(x)=N(x;μi,Σi)qj(x)=N(x;mj,Sj)

Jarak-jarak berikut tersedia dalam bentuk tertutup:

  • L2 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 .

    L2(P,Q)2=(p(x)q(x))2dx=(iαipi(x)jβjqj(x))2dx=i,iαiαipi(x)pi(x)dx+j,jβjβjqj(x)qj(x)dx2i,jαiβjpi(x)qj(x)dx.
    N(x;μ,Σ)N(x;μ,Σ)dx=N(μ;μ,Σ+Σ)
    O(mn)

  • 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(12σ2xy2),
    Hkk(x,y)=φ(x),φ(y)H

    Tentukan kernel peta rata - rata sebagai

    K(P,Q)=EXP,YQk(X,Y)=EXPφ(X),EYQφ(Y).

    MMD kemudian

    MMD(P,Q)=EXP[φ(X)]EYQ[φ(Y)]=K(P,P)+K(Q,Q)2K(P,Q)=supf:fH1EXPf(X)EYQf(Y).

    Untuk campuran dan , perhatikan bahwa dan demikian pula untuk dan .PQ

    K(P,Q)=i,jαiβjK(Pi,Qj)
    K(P,P)K(Q,Q)

    Ternyata, menggunakan trik serupa seperti untuk , bahwa adalah L2K(N(μ,Σ),N(μ,Σ))

    (2πσ2)d/2N(μ;μ,Σ+Σ+σ2I).

    Sebagai , jelas ini menyatu dengan kelipatan dari jarak . Anda biasanya ingin menggunakan berbeda , meskipun, satu pada skala variasi data.σ0L2σ

    Formulir tertutup juga tersedia untuk kernel polinomial dalam MMD; Lihatk

    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α

    Hα(p)=11αlog(p(x)αdx).
    α1
    JRα(p,q)=Hα(p+q2)Hα(p)+Hα(q)2
    p+q2pqα=2PQJR2

    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