Saya membaca Bishop pada algoritma EM untuk GMM dan hubungan antara GMM dan k-means.
Dalam buku ini dikatakan bahwa k-means adalah versi GMM yang sulit. Saya bertanya-tanya apakah itu menyiratkan bahwa jika data yang saya coba kluster bukan Gaussian, saya tidak dapat menggunakan k-means (atau setidaknya itu tidak cocok untuk digunakan)? Sebagai contoh, bagaimana jika data adalah gambar dari angka tulisan tangan, masing-masing terdiri dari 8 * 8 piksel dengan nilai 0 atau 1 (dan anggap mereka independen maka harus campuran Bernoulli)?
Saya sedikit bingung tentang ini dan akan menghargai setiap pemikiran.
clustering
data-mining
k-means
gaussian-mixture
eddie.xie
sumber
sumber
Jawaban:
Dalam situasi GMM EM umum, seseorang memang memperhitungkan varians dan kovarian. Ini tidak dilakukan dalam k-means.
Tapi memang, salah satu heuristik populer untuk k-means (catatan: k-means adalah masalah, bukan algoritma) - algoritma Lloyd - pada dasarnya adalah algoritma EM, menggunakan model centroid (tanpa varian) dan tugas yang sulit.
Saat melakukan k-means style clustering (mis. Minimisasi varians), Anda
Secara umum dikatakan bahwa k-means mengasumsikan cluster bola. Secara umum juga diakui bahwa k-means cluster adalah sel Voronoi, yaitu tidak berbentuk bola. Keduanya benar, dan keduanya salah. Pertama-tama, kluster bukanlah sel Voronoi yang lengkap, tetapi hanya objek yang diketahui di dalamnya. Tidak perlu mempertimbangkan ruang mati di antara cluster untuk menjadi bagian dari salah satu cluster, karena memiliki objek di sana akan mempengaruhi hasil algoritma. Tetapi tidak jauh lebih baik untuk menyebutnya "bulat", hanya karena jarak euclidean bulat. K-means tidak peduli dengan jarak Euclidean. Semua itu, adalah heuristik untuk meminimalkan varians . Dan itu sebenarnya, apa yang harus Anda pertimbangkan k-artinya: minimalisasi varians.
sumber
minimize squared euclidean distance
atauminimize the variances
? Pasti ada kata "jumlah" atau "dikumpulkan" atau semacamnya, karena kita memiliki 2+ cluster, bukan?coincidentally minimize Euclidean distance, because the sqrt function is monotone
adalah, tepatnya, tidak benar.minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance
berarti ? Apakah Anda mengatakan "kuadrat d antara objek-objek dalam cluster diminimalkan karena WCSS penyimpangan diminimalkan", atau hanya "WCSS penyimpangan diminimalkan, yang - penyimpangan - adalah jarak euclidean secara alami"? Atau apa lagi?GMM menggunakan tumpang tindih bukit yang membentang hingga tak terbatas (tetapi praktis hanya dihitung untuk 3 sigma). Setiap titik mendapatkan semua nilai probabilitas bukit. Juga, bukit-bukit itu "berbentuk telur" [oke, mereka elips simetris ] dan, dengan menggunakan matriks kovarian penuh, dapat dimiringkan .
K-berarti hard-assign sebuah titik ke satu cluster, sehingga skor dari pusat-pusat cluster lainnya diabaikan (secara implisit diatur ulang ke nol / tidak peduli). Bukit-bukit itu adalah gelembung-gelembung sabun berbentuk bola. Ketika dua gelembung sabun bersentuhan, batas di antara keduanya menjadi bidang datar (hyper-). Seperti halnya ketika Anda mengeluarkan busa dari banyak gelembung sabun, gelembung di bagian dalam tidak datar tetapi berbentuk kotak, sehingga batas antara banyak bola (hyper-) sebenarnya membentuk partisi ruang Voronoi dari ruang tersebut. Dalam 2D, ini cenderung terlihat samar-samar seperti pengepakan heksagonal, pikirkan sarang lebah (walaupun tentu saja sel Voronoi tidak dijamin menjadi heksagon). Bukit K-means bundar dan tidak miring, sehingga memiliki kekuatan representasi yang lebih kecil; tetapi lebih cepat untuk menghitung, terutama di dimensi yang lebih tinggi.
Karena K-means menggunakan metrik jarak Euclidean, maka diasumsikan bahwa dimensi dapat dibandingkan dan memiliki bobot yang sama. Jadi jika dimensi X memiliki satuan mil per jam, bervariasi dari 0 hingga 80, dan dimensi Y memiliki satuan pound, bervariasi dari 0 hingga 400, dan Anda memasang lingkaran di ruang XY ini, maka satu dimensi (dan penyebarannya) akan menjadi lebih kuat daripada dimensi lain dan akan menaungi hasilnya. Inilah sebabnya mengapa biasa untuk menormalkan data saat mengambil K-means.
Baik GMM dan K-means memodelkan data dengan menyesuaikan perkiraan terbaik dengan apa yang diberikan. GMM cocok untuk telur yang dimiringkan, dan K-means cocok untuk bola yang didahului. Tetapi data yang mendasarinya bisa berbentuk seperti apa pun, bisa berupa spiral atau lukisan Picasso, dan masing-masing algoritma masih berjalan, dan mengambil bidikan terbaiknya. Apakah model yang dihasilkan terlihat seperti data aktual tergantung pada proses fisik yang mendasari menghasilkan data. (Misalnya, pengukuran waktu tunda satu sisi; apakah Gaussian cocok? Mungkin.)
Dengan demikian gambar biner 8x8 Anda akan ditafsirkan sebagai hypercube 64 dimensi di hyperquadrant pertama. Algoritma kemudian menggunakan analogi geometris untuk menemukan kelompok. Jarak, dengan K-means, muncul sebagai jarak Euclidean dalam ruang 64-dimensi. Itu salah satu cara untuk melakukannya.
sumber