Clustering (k-means, atau sebaliknya) dengan batasan ukuran cluster minimum

14

Saya perlu mengelompokkan unit ke dalam cluster untuk meminimalkan sum-kuadrat dalam-grup (WSS), tetapi saya perlu memastikan bahwa masing-masing cluster mengandung setidaknya unit. Adakah yang tahu jika ada salah satu fungsi pengelompokan R yang memungkinkan pengelompokan ke dalam cluster tunduk pada batasan ukuran cluster minimum? kmeans () tampaknya tidak menawarkan opsi batasan ukuran.m kkmk

r clustering Cyrus S
sumber

Jawaban:

5

Gunakan EM Clustering

Dalam pengelompokan EM, algoritma iteratif memperbaiki model klaster awal agar sesuai dengan data dan menentukan probabilitas bahwa suatu titik data ada dalam sebuah klaster. Algoritme mengakhiri proses ketika model probabilistik cocok dengan data. Fungsi yang digunakan untuk menentukan kecocokan adalah log-kemungkinan data yang diberikan model.

Jika cluster kosong dihasilkan selama proses, atau jika keanggotaan satu atau lebih cluster jatuh di bawah ambang batas yang diberikan, cluster dengan populasi rendah diunggah kembali pada titik-titik baru dan algoritma EM dijalankan kembali.

mariana lebih lembut
sumber
Terima kasih, Marianna. Saya lebih suka solusi yang tidak terlalu bergantung pada model parametrik (biasanya, tidak dapat dibenarkan), tetapi pasti akan memeriksanya.
Cyrus S
4

Masalah ini dibahas dalam makalah ini:

Bradley, PS, KP Bennett, dan Ayhan Demiriz. "K-means terkelompok." Microsoft Research, Redmond (2000) : 1-8.

Saya memiliki implementasi algoritma dalam python.

Behrouz Babaki
sumber
Ini sempurna, terima kasih! Saya menggunakan rPythonpaket dalam R untuk membuat antarmuka untuk implementasi ini yang saya akses dari script R.
Michael Ohlrogge
@MichaelOhlrogge apakah Anda memiliki contoh di suatu tempat (github?) Pada antarmuka yang Anda tulis untuk memanggil paket python itu berupa R? Terima kasih!
Matifou
Maaf, saya melihat-lihat kode lama saya tetapi tidak dapat menemukannya lagi.
Michael Ohlrogge
3

Saya pikir itu hanya akan menjadi masalah menjalankan k berarti sebagai bagian dari jika loop dengan tes untuk ukuran cluster, Ie Hitung n di cluster k - juga ingat bahwa k berarti akan memberikan hasil yang berbeda untuk masing-masing berjalan pada data yang sama sehingga Anda mungkin harus menjalankannya sebagai bagian dari loop untuk mengekstrak hasil "terbaik"


sumber
1
Terima kasih, Alex. Saya melihat masalah dengan ini: bagaimana jika di atas loop solusi yang dihasilkan tidak pernah memenuhi kendala? Itu bisa terjadi jika k means ditetapkan untuk berjalan tanpa batasan ukuran cluster. Saya suka solusi yang menghindari ini. (Sifat aplikasi adalah sedemikian rupa sehingga saya benar-benar perlu memastikan bahwa cluster berukuran minimum.)
Cyrus S
1

Seberapa besar kumpulan data Anda? Mungkin Anda bisa mencoba menjalankan pengelompokan hierarkis dan kemudian memutuskan kelompok mana yang dipertahankan berdasarkan dendrogram Anda.

Jika kumpulan data Anda sangat besar, Anda juga bisa menggabungkan kedua metode pengelompokan: pengelompokan non-hierarkis awal dan kemudian pengelompokan hierarkis menggunakan grup dari analisis non-hierarkis. Anda dapat menemukan contoh dari pendekatan ini dalam Martínez-Pastor et al (2005)

Manuel Ramón
sumber
Terima kasih, Manuel. Ini sebenarnya terdengar seperti kemungkinan yang sangat menarik. Saya perlu berpikir tentang apakah partisi hierarkis akan memaksakan batasan tertentu yang akan mencegah algoritma mencapai partisi cluster optimal langsung di bawah batasan ukuran. Tetapi secara intuitif, saya dapat melihat bahwa ini mungkin berhasil.
Cyrus S
0

Ini dapat dicapai dengan memodifikasi langkah penugasan gugus (E dalam EM) dengan merumuskannya sebagai masalah optimisasi jaringan linear Aliran Biaya Minimum (MCF).

Saya telah menulis paket python yang menggunakan SimpleMinCostFlow dari Google Research Operations Research tools yang merupakan implementasi C ++ yang cepat. Ini memiliki standar API scikit-lean.

Astaga
sumber