Bagaimana cara memutuskan jumlah cluster yang benar?

54

Kami menemukan pusat-pusat klaster dan menetapkan poin ke k tempat-tempat klaster yang berbeda dalam klaster k-means yang merupakan algoritma yang sangat terkenal dan ditemukan hampir di setiap paket pembelajaran mesin di internet. Tetapi bagian yang hilang dan paling penting menurut saya adalah pilihan k yang benar. Apa nilai terbaik untuk itu? Dan, apa yang dimaksud dengan yang terbaik ?

Saya menggunakan MATLAB untuk komputasi ilmiah di mana melihat plot siluet diberikan sebagai cara untuk memutuskan k dibahas di sini . Namun, saya akan lebih tertarik pada pendekatan Bayesian. Ada saran yang dihargai.

petrichor
sumber
2
Pertanyaan yang bagus ...
Di bawah visualisasi-untuk-pengelompokan ada (ahem) cara untuk menggambarkan k-cluster dan melihat efek berbagai k dalam satu tembakan, menggunakan MST.
denis
Saya sudah menjawab pertanyaan ini dengan setengah lusin metode dalam Rlebih di sini
Ben
1
Menentukan jumlah k "terbaik" dari kluster menyiratkan membandingkan solusi klaster dengan k - solusi yang berbeda "." Sehubungan dengan hal itu, tugas tersebut tampak serupa dengan bagaimana membandingkan metode pengelompokan - yang "lebih baik" untuk data Anda. Pedoman umum ada di sini .
ttnphns

Jawaban:

28

Ini telah diminta beberapa kali di stackoverflow: di sini , di sini dan di sini . Anda dapat melihat apa pendapat orang-orang di sana tentang pertanyaan ini (atau varian kecilnya).

Izinkan saya juga menyalin jawaban saya sendiri untuk pertanyaan ini, di stackoverflow.com:

Sayangnya tidak ada cara untuk secara otomatis mengatur "benar" K juga tidak ada definisi apa yang "benar". Tidak ada metode statistik berprinsip, sederhana atau kompleks yang dapat mengatur "K kanan". Ada heuristik, aturan praktis yang kadang-kadang berfungsi, kadang tidak.

Situasinya lebih umum karena banyak metode pengelompokan memiliki jenis parameter ini, dan saya pikir ini adalah masalah besar yang terbuka di komunitas penelitian pembelajaran pengelompokan / tanpa pengawasan.

carlosdc
sumber
+1 Setelah membaca ini - menurut saya sangat intuitif .... tetapi saya harus mengatakan bahwa saya tidak pernah memikirkan hal ini sebelumnya. bahwa sebenarnya masalah memilih jumlah PC di PCA sama dengan masalah memilih jumlah cluster dalam K-mean ...
Dov
2
@Dov kedua hal ini tidak cukup setara. Ada langkah-langkah spesifik yang dapat digunakan untuk memeriksa kualitas solusi PCA (terutama kesalahan rekonstruksi, tetapi juga% dari varians yang ditangkap dll), dan ini cenderung (kebanyakan) konsisten. Namun dalam pengelompokan sering kali tidak ada satu "jawaban yang benar" - satu pengelompokan mungkin lebih baik daripada yang lain dengan satu metrik, dan sebaliknya mungkin benar menggunakan metrik lain. Dan dalam beberapa situasi dua pengelompokan yang berbeda bisa sama-sama dimungkinkan di bawah metrik yang sama.
tdc
@tdc tetapi jangan en.wikipedia.org/wiki/… ini lebih atau kurang seperti ini dengan peningkatan hasil.com/docs/WebSiteDocs/PCA/… ?
Dov
2
@Dov Ya, mereka "kurang lebih" seperti satu sama lain, tapi saya hanya mengatakan bahwa masalah memilih jumlah cluster jauh lebih penuh daripada memilih jumlah PC - yaitu mereka tidak "setara".
tdc
1
+1 Anda benar. Kami agak memperkenalkan beberapa model atau asumsi lain untuk memutuskan k yang terbaik, tetapi kemudian pertanyaannya adalah mengapa model atau asumsi itu yang terbaik ...
petrichor
19

Pertama, peringatan. Dalam pengelompokan seringkali tidak ada satu "jawaban yang benar" - satu pengelompokan mungkin lebih baik daripada yang lain dengan satu metrik, dan sebaliknya mungkin benar menggunakan metrik lain. Dan dalam beberapa situasi dua pengelompokan yang berbeda bisa sama-sama dimungkinkan di bawah metrik yang sama.

Karena itu, Anda mungkin ingin melihat Dirichlet Processes . Lihat juga tutorial ini .

Jika Anda mulai dengan model Gaussian Mixture, Anda memiliki masalah yang sama dengan k-means - bahwa Anda harus memilih jumlah cluster. Anda dapat menggunakan bukti model, tetapi tidak akan kuat dalam hal ini. Jadi triknya adalah dengan menggunakan Proses Dirichlet sebelum melewati komponen campuran, yang kemudian memungkinkan Anda untuk memiliki jumlah komponen campuran yang berpotensi tak terbatas, tetapi model akan (biasanya) secara otomatis menemukan jumlah komponen yang "benar" (berdasarkan asumsi dari model).

Perhatikan bahwa Anda masih harus menentukan parameter konsentrasi dari Proses Dirichlet sebelumnya. Untuk nilai kecil , sampel dari DP cenderung terdiri dari sejumlah kecil ukuran atom dengan bobot besar. Untuk nilai besar, sebagian besar sampel cenderung berbeda (terkonsentrasi). Anda dapat menggunakan hiper-sebelum pada parameter konsentrasi dan kemudian menyimpulkan nilainya dari data, dan hiper-sebelum ini dapat samar-samar sesuai untuk memungkinkan berbagai nilai yang mungkin. Namun, dengan data yang cukup, parameter konsentrasi akan berhenti menjadi sangat penting, dan hiper-prior ini dapat dibatalkan.ααα

tdc
sumber
1
Proses Dirichlet di bawah parameter konsentrasi apa? Ini sama dengan pertanyaan asli yang sama, k-berarti di bawah apa k? Meskipun saya setuju bahwa kita lebih memahami distribusi Direchlet bahwa perilaku beberapa algoritma yang kompleks pada beberapa data dunia nyata.
carlosdc
@carlosdc poin bagus, saya telah memperbarui jawaban untuk menyertakan sedikit diskusi tentang parameter konsentrasi
tdc
1
Dalam pengalaman saya, jauh lebih mudah untuk mempelajari parameter konsentrasi bernilai terus menerus seperti alfa daripada menentukan jumlah cluster dalam model campuran hingga. Jika Anda ingin tetap menggunakan model campuran yang terbatas, dan mengambil taktik Bayesian, ada lompatan MCMC ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
1
Jawaban yang bagus Saya akan menambahkan kertas Revisiting K-Means: Algoritma Baru melalui Bayesian Nonparametrics . Yang memberikan pendekatan "Berkelanjutan" sederhana untuk K-Means. Maka mudah, menggunakan optimasi, untuk menemukan nilai optimal.
Royi
9

Saya menggunakan metode Siku :

  • Mulailah dengan K = 2, dan terus tingkatkan di setiap langkah dengan 1, menghitung kelompok Anda dan biaya yang datang dengan pelatihan. Pada beberapa nilai untuk K biaya turun secara dramatis, dan setelah itu mencapai dataran tinggi ketika Anda meningkatkannya lebih lanjut. Ini adalah nilai K yang Anda inginkan.

Alasannya adalah bahwa setelah ini, Anda menambah jumlah cluster tetapi cluster baru sangat dekat dengan beberapa yang sudah ada.

vonPetrushev
sumber
Ini kedengarannya seperti prinsip yang dievaluasi Metode L (lihat jawaban saya).
Menang
6

Ukuran cluster sangat bergantung pada data Anda dan untuk apa Anda akan menggunakan hasilnya. Jika Anda menggunakan data Anda untuk memisahkan berbagai hal ke dalam kategori, coba bayangkan berapa banyak kategori yang Anda inginkan terlebih dahulu. Jika itu untuk visualisasi data, buatlah ini dapat dikonfigurasi, sehingga orang dapat melihat cluster besar dan kecil.

Jika Anda perlu mengotomatiskannya, Anda mungkin ingin menambahkan penalti ke peningkatan k, dan menghitung cluster optimal dengan cara itu. Dan kemudian Anda hanya berat k tergantung pada apakah Anda ingin satu ton cluster atau Anda ingin sangat sedikit.

neuron
sumber
5

Saya telah berhasil menggunakan "Metode L" untuk menentukan jumlah cluster dalam aplikasi geografis (mis. Pada dasarnya masalah 2d meskipun secara teknis non-Euclidean).

Metode L dijelaskan di sini: Menentukan Jumlah Cluster / Segmen dalam Hierarchical Clustering / Algoritma Segmentasi Stan Salvador dan Philip Chan

Pada dasarnya ini mengevaluasi kecocokan untuk berbagai nilai k. Grafik berbentuk "L" terlihat dengan nilai k optimal yang ditunjukkan oleh lutut pada grafik. Perhitungan fitting dual-line kuadrat sederhana digunakan untuk menemukan titik lutut.

Saya menemukan metode ini sangat lambat karena k-means iteratif harus dihitung untuk setiap nilai k. Saya juga menemukan k-means bekerja paling baik dengan banyak putaran dan memilih yang terbaik di akhir. Meskipun setiap titik data hanya memiliki dua dimensi, jarak Pythagoras yang sederhana tidak dapat digunakan. Jadi itu banyak perhitungan.

Satu pemikiran adalah melompati setiap nilai k (katakanlah) untuk setengah perhitungan dan / atau untuk mengurangi jumlah iterasi k-means, dan kemudian untuk sedikit memuluskan kurva yang dihasilkan untuk menghasilkan kecocokan yang lebih akurat. Saya bertanya tentang ini di StackOverflow - IMHO, pertanyaan smoothing tetap menjadi pertanyaan penelitian terbuka.

menang
sumber
4

Anda perlu mempertimbangkan kembali apa arti k-means. Ia mencoba untuk menemukan partisi Voronoi optimal dari kumpulan data ke dalam sel . Sel Voronoi adalah sel berbentuk aneh, struktur ortogonal dari triangulasi Delaunay.k

Tetapi bagaimana jika set data Anda tidak benar-benar cocok dengan skema Voronoi?

Kemungkinan besar, cluster yang sebenarnya tidak akan sangat berarti. Namun, mereka mungkin masih bekerja untuk apa pun yang Anda lakukan. Bahkan memecah cluster "true" menjadi dua bagian karena Anda terlalu tinggi, hasilnya dapat bekerja dengan sangat baik misalnya untuk klasifikasi. Jadi saya akan mengatakan: yang terbaik adalah , yang bekerja paling baik untuk tugas khusus Anda.kkk

Bahkan, ketika Anda memiliki cluster yang tidak berukuran sama dan berjarak (dan dengan demikian tidak cocok dengan skema partisi Voronoi), Anda mungkin perlu meningkatkan k untuk k-means untuk mendapatkan hasil yang lebih baik.k

Anony-Mousse
sumber
3
Meskipun deskripsi K-means pada paragraf pertama tidak salah, itu mungkin menyesatkan beberapa orang untuk menyamakan metode ini dengan partisi Voronoi berdasarkan data asli. Ini tidak demikian: partisi tersebut didasarkan pada lokasi-lokasi cluster yang berarti, yang mungkin tidak (dan biasanya tidak) bertepatan dengan data asli mana pun.
whuber
3

Secara keseluruhan, Anda dapat memilih jumlah cluster dalam dua jalur berbeda.

  1. didorong oleh pengetahuan: Anda harus memiliki beberapa ide berapa banyak kluster yang Anda butuhkan dari sudut pandang bisnis. Misalnya, Anda mengelompokkan pelanggan, Anda harus bertanya pada diri sendiri, setelah mendapatkan pelanggan ini, apa yang harus saya lakukan selanjutnya? Mungkin Anda akan memiliki perlakuan berbeda untuk berbagai kluster? (mis. beriklan melalui email atau telepon). Lalu berapa banyak kemungkinan perawatan yang Anda rencanakan? Dalam contoh ini, Anda memilih mengatakan 100 cluster tidak akan terlalu masuk akal.

  2. Didorong oleh data: lebih banyak jumlah kluster yang terlalu pas dan lebih sedikit jumlah kluster yang kurang pas. Anda selalu dapat membagi data menjadi dua dan menjalankan validasi silang untuk melihat berapa banyak jumlah cluster yang baik. Catatan, dalam pengelompokan Anda masih memiliki fungsi kerugian, mirip dengan pengaturan yang diawasi.

Akhirnya, Anda harus selalu menggabungkan pengetahuan yang didorong dan data yang didorong bersama di dunia nyata.

Haitao Du
sumber
2

Karena belum ada yang menunjuk, saya pikir saya akan membagikan ini. Ada metode yang disebut X-means, ( lihat tautan ini ) yang memperkirakan jumlah cluster yang tepat menggunakan kriteria informasi Bayesian (BIC). Pada dasarnya, ini akan seperti mencoba K berarti dengan Ks yang berbeda, menghitung BIC untuk setiap K dan memilih K. terbaik. Algoritma ini melakukan itu secara efisien.

Ada juga implementasi weka , yang detailnya dapat ditemukan di sini .

rivu
sumber
0

Pendekatan lain adalah dengan menggunakan algoritma evolusi yang individu-individu memiliki kromosom dengan panjang yang berbeda. Setiap individu adalah solusi kandidat: masing-masing membawa koordinat centroid. Jumlah centroid dan koordinatnya dikembangkan untuk mencapai solusi yang menghasilkan skor evaluasi pengelompokan terbaik.

Makalah ini menjelaskan algoritma.

felipeduque
sumber