Saya telah mempelajari tentang k-means clustering , dan satu hal yang tidak jelas adalah bagaimana Anda memilih nilai k. Apakah ini hanya masalah coba-coba, atau ada yang lebih dari itu?
cluster-analysis
k-means
Jason Baker
sumber
sumber
R
) di sini: stackoverflow.com/a/15376462/1036500Jawaban:
Anda dapat memaksimalkan Kriteria Informasi Bayesian (BIC):
di mana
L(X | C)
kemungkinan log dari datasetX
menurut modelC
,p
adalah jumlah parameter dalam modelC
, dann
jumlah titik dalam dataset. Lihat "X-means: memperluas K- berarti dengan estimasi efisien jumlah cluster" oleh Dan Pelleg dan Andrew Moore dalam ICML 2000.Pendekatan lain adalah mulai dengan nilai besar untuk
k
dan terus menghapus centroid (mengurangi k) sampai tidak lagi mengurangi panjang deskripsi. Lihat "Prinsip MDL untuk quantisation vektor yang kuat" oleh Horst Bischof, Ales Leonardis, dan Alexander Selb dalam Analisis Pola dan Aplikasi vol. 2, hal. 59-72, 1999.Akhirnya, Anda bisa mulai dengan satu kluster, lalu terus membelah kluster hingga titik yang ditetapkan untuk masing-masing klaster memiliki distribusi Gaussian. Dalam "Learning the k in k -means" (NIPS 2003), Greg Hamerly dan Charles Elkan menunjukkan beberapa bukti bahwa ini bekerja lebih baik daripada BIC, dan bahwa BIC tidak cukup menghukum kompleksitas model yang cukup kuat.
sumber
Pada dasarnya, Anda ingin menemukan keseimbangan antara dua variabel: jumlah cluster ( k ) dan varians rata-rata dari cluster. Anda ingin meminimalkan yang pertama sementara juga meminimalkan yang kedua. Tentu saja, ketika jumlah cluster meningkat, varians rata-rata menurun (hingga kasus sepele k = n dan varians = 0).
Seperti biasa dalam analisis data, tidak ada satu pendekatan sejati yang berfungsi lebih baik daripada semua yang lain dalam semua kasus. Pada akhirnya, Anda harus menggunakan penilaian terbaik Anda sendiri. Untuk itu, ada baiknya untuk merencanakan jumlah cluster terhadap varian rata-rata (yang mengasumsikan bahwa Anda telah menjalankan algoritma untuk beberapa nilai k ). Kemudian Anda bisa menggunakan jumlah cluster di bagian bawah kurva.
sumber
Ya, Anda dapat menemukan jumlah cluster terbaik menggunakan metode Elbow, tetapi saya merasa kesulitan untuk menemukan nilai cluster dari grafik siku menggunakan skrip. Anda dapat mengamati grafik siku dan menemukan titik siku sendiri, tetapi banyak pekerjaan yang menemukannya dari skrip.
Jadi pilihan lain adalah menggunakan Metode Silhouette untuk menemukannya. Hasil dari Silhouette sepenuhnya mematuhi hasil dari metode Elbow di R.
Inilah yang saya lakukan.
Semoga ini bisa membantu !!
sumber
Mungkin seseorang pemula seperti saya mencari contoh kode. informasi untuk silhouette_score tersedia di sini.
sumber
Lihatlah makalah ini , "Belajar k dalam k-means" oleh Greg Hamerly, Charles Elkan. Ini menggunakan tes Gaussian untuk menentukan jumlah cluster yang tepat. Juga, penulis mengklaim bahwa metode ini lebih baik daripada BIC yang disebutkan dalam jawaban yang diterima.
sumber
Ada sesuatu yang disebut Aturan Jempol. Dikatakan bahwa jumlah cluster dapat dihitung oleh
k = (n/2)^0.5
di mana n adalah jumlah total elemen dari sampel Anda. Anda dapat memeriksa kebenaran informasi ini di kertas berikut:
http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf
Ada juga metode lain yang disebut G-means, di mana distribusi Anda mengikuti Distribusi Gaussian atau Distribusi Normal. Ini terdiri dari peningkatan k sampai semua grup k Anda mengikuti Distribusi Gaussian. Itu membutuhkan banyak statistik tetapi bisa dilakukan. Inilah sumbernya:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Saya harap ini membantu!
sumber
Pertama-tama buat pohon rentang minimum data Anda. Menghapus tepi K-1 yang paling mahal akan membagi pohon menjadi cluster K,
sehingga Anda dapat membangun MST satu kali, melihat pengelompokan / metrik klaster untuk berbagai K, dan ambil lutut kurva.
Ini hanya berfungsi untuk Single-linkage_clustering , tetapi untuk itu cepat dan mudah. Plus, MST membuat visual yang bagus.
Lihat misalnya plot MST di bawah software visualisasi stats.stackexchange untuk pengelompokan .
sumber
Saya terkejut tidak ada yang menyebutkan artikel yang luar biasa ini: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
Setelah mengikuti beberapa saran lain, saya akhirnya menemukan artikel ini ketika membaca blog ini: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
Setelah itu saya mengimplementasikannya di Scala, implementasi yang untuk kasus penggunaan saya memberikan hasil yang sangat baik. Ini kode:
sumber
Jika Anda menggunakan MATLAB, versi apa pun sejak 2013b, Anda dapat menggunakan fungsi ini
evalclusters
untuk mencari tahu apa yang seharusnya optimalk
untuk dataset yang diberikan.Fungsi ini memungkinkan Anda memilih di antara 3 algoritma pengelompokan -
kmeans
,linkage
dangmdistribution
.Hal ini juga memungkinkan Anda memilih dari antara kriteria evaluasi 4 pengelompokan -
CalinskiHarabasz
,DaviesBouldin
,gap
dansilhouette
.sumber
Jika Anda tidak tahu jumlah klaster k yang harus disediakan sebagai parameter untuk k-means, maka ada empat cara untuk menemukannya secara otomatis:
Algortitme G-means: ia menemukan jumlah cluster secara otomatis menggunakan uji statistik untuk memutuskan apakah akan membagi pusat k-means menjadi dua. Algoritme ini mengambil pendekatan hierarkis untuk mendeteksi jumlah cluster, berdasarkan pada uji statistik untuk hipotesis bahwa subset data mengikuti distribusi Gaussian (fungsi kontinu yang mendekati distribusi peristiwa binomial yang tepat), dan jika tidak memecah cluster . Ini dimulai dengan sejumlah kecil pusat, katakan satu klaster saja (k = 1), kemudian algoritma membaginya menjadi dua pusat (k = 2) dan membelah masing-masing dua pusat ini lagi (k = 4), memiliki empat pusat di total. Jika G-means tidak menerima empat pusat ini maka jawabannya adalah langkah sebelumnya: dua pusat dalam kasus ini (k = 2). Ini adalah jumlah cluster yang akan dibagi oleh dataset Anda. G-means sangat berguna ketika Anda tidak memiliki estimasi jumlah cluster yang akan Anda dapatkan setelah mengelompokkan instance Anda. Perhatikan bahwa pilihan yang tidak nyaman untuk parameter "k" mungkin memberi Anda hasil yang salah. Versi paralel dari g-means disebutp-means . Sumber G-means: sumber 1 sumber 2 sumber 3
x-means : algoritma baru yang efisien, mencari ruang lokasi cluster dan jumlah cluster untuk mengoptimalkan Bayesian Information Criterion (BIC) atau ukuran Akaike Information Criterion (AIC). Versi k-means ini menemukan angka k dan juga mempercepat k-means.
Online k-means atau Streaming k-means: memungkinkan untuk mengeksekusi k-means dengan memindai seluruh data satu kali dan menemukan secara otomatis jumlah k yang optimal. Spark mengimplementasikannya.
Algoritma MeanShift : ini adalah teknik cluster nonparametric yang tidak memerlukan pengetahuan sebelumnya tentang jumlah cluster, dan tidak membatasi bentuk cluster. Mean shift clustering bertujuan untuk menemukan "gumpalan" dalam kepadatan sampel yang halus. Ini adalah algoritma berbasis centroid, yang bekerja dengan memperbarui kandidat untuk centroid menjadi rata-rata poin dalam wilayah tertentu. Kandidat ini kemudian disaring dalam tahap pasca-pemrosesan untuk menghilangkan duplikat-hampir untuk membentuk set terakhir centroid. Sumber: source1 , source2 , source3
sumber
Saya menggunakan solusi yang saya temukan di sini: http://efavdb.com/mean-shift/ dan itu bekerja sangat baik untuk saya:
sumber
Ide saya adalah menggunakan Koefisien Siluet untuk menemukan nomor cluster optimal (K). Penjelasan detail ada di sini .
sumber
Dengan asumsi Anda memiliki matriks data yang disebut
DATA
, Anda dapat melakukan partisi di sekitar medoid dengan estimasi jumlah cluster (dengan analisis siluet) seperti ini:sumber
Salah satu jawaban yang mungkin adalah menggunakan Meta Heuristic Algorithm seperti Genetic Algorithm untuk menemukan k. Sederhana saja. Anda dapat menggunakan K acak (dalam beberapa rentang) dan mengevaluasi fungsi kecocokan Algoritma Genetika dengan beberapa pengukuran seperti Silhouette Dan Temukan basis K terbaik pada fungsi fit.
https://en.wikipedia.org/wiki/Silhouette_(clustering)
sumber
sumber
Pendekatan lain adalah menggunakan Self Organizing Maps (SOP) untuk menemukan jumlah cluster yang optimal. SOM (Self-Organizing Map) adalah metodologi jaringan saraf yang tidak diawasi, yang hanya membutuhkan input yang digunakan untuk pengelompokan untuk pemecahan masalah. Pendekatan ini digunakan dalam makalah tentang segmentasi pelanggan.
Referensi dari makalah ini adalah
Abdellah Amine et al., Model Segmentasi Pelanggan dalam E-commerce Menggunakan Teknik Clustering dan Model LRFM: Kasus Toko Online di Maroko, World Academy of Science, Engineering and Technology Jurnal Internasional Teknik Komputer dan Informasi Vol: 9, No: 8 , 2015, 1999 - 2010
sumber
Hai Saya akan membuatnya sederhana dan langsung untuk menjelaskan, saya ingin menentukan cluster menggunakan perpustakaan 'NbClust'.
Sekarang, bagaimana menggunakan fungsi 'NbClust' untuk menentukan jumlah cluster yang tepat: Anda dapat memeriksa proyek aktual di Github dengan data dan cluster aktual - Perluasan algoritma 'kmeans' ini juga dilakukan dengan menggunakan jumlah 'pusat' yang tepat.
Tautan Proyek Github: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook
sumber
Anda dapat memilih jumlah cluster dengan secara visual memeriksa poin data Anda, tetapi Anda akan segera menyadari bahwa ada banyak ambiguitas dalam proses ini untuk semua kecuali kumpulan data yang paling sederhana. Ini tidak selalu buruk, karena Anda melakukan pembelajaran tanpa pengawasan dan ada beberapa subjektivitas yang melekat dalam proses pelabelan. Di sini, memiliki pengalaman sebelumnya dengan masalah khusus itu atau yang serupa akan membantu Anda memilih nilai yang tepat.
Jika Anda ingin beberapa petunjuk tentang jumlah cluster yang harus Anda gunakan, Anda dapat menerapkan metode Siku:
Pertama-tama, hitung jumlah kesalahan kuadrat (SSE) untuk beberapa nilai k (misalnya 2, 4, 6, 8, dll.). SSE didefinisikan sebagai jumlah dari jarak kuadrat antara setiap anggota cluster dan centroid-nya. Secara matematis:
SSE = ∑Ki = 1∑x∈cidist (x, ci) 2
Jika Anda memplot k terhadap SSE, Anda akan melihat bahwa errornya menurun ketika k bertambah besar; ini karena ketika jumlah cluster meningkat, mereka harus lebih kecil, sehingga distorsi juga lebih kecil. Gagasan metode siku adalah untuk memilih k di mana SSE menurun secara tiba-tiba. Ini menghasilkan "efek siku" pada grafik, seperti yang Anda lihat pada gambar berikut:
Dalam hal ini, k = 6 adalah nilai yang telah dipilih metode Elbow. Mempertimbangkan bahwa metode Siku adalah heuristik dan, dengan demikian, mungkin atau mungkin tidak berfungsi dengan baik dalam kasus khusus Anda. Terkadang, ada lebih dari satu siku, atau tidak ada siku sama sekali. Dalam situasi tersebut, Anda biasanya menghitung k terbaik dengan mengevaluasi seberapa baik kinerja k-means dalam konteks masalah pengelompokan tertentu yang Anda coba selesaikan.
sumber
Saya bekerja pada rajutan paket Python (algoritma Kneedle). Ia menemukan nomor cluster secara dinamis sebagai titik di mana kurva mulai merata .. Diberikan satu set nilai x dan y, rajutan akan mengembalikan titik lutut fungsi. Titik lutut adalah titik kelengkungan maksimum. Berikut adalah contoh kode.
y = [7342,1301373073857, 6881,7109460930769, 6531,1657905495022,
6356,2255554679778, 6209,8382535595829, 6094,9052166741121, 5980,0191582610196, 5880,1869867848218, 5779,8957906367368, 5691,1879324562778, 5617,5153566271356, 5532,2613232619951, 5467,352265375117, 5395,4493783888756, 5345,3459908298091, 5290,6769823693812, 5243,5271656371888, 5207,2501206569532, 5164,9617535255456]
x = rentang (1, len (y) +1)
dari impor kneed KneeLocator kn = KneeLocator (x, y, kurva = 'cembung', arah = 'menurun')
print (kn.knee)
sumber