Kelebihan dan kekurangan k-means

K-means berguna dan efisien dalam banyak konteks machine learning, tetapi memiliki beberapa kelemahan yang berbeda.

Keunggulan k-means

Relatief mudah diterapkan.

Menskalakan ke set data besar.

Selalu berkonvergensi.

Memungkinkan warm-start posisi centroid.

Beradaptasi dengan lancar ke contoh baru.

Dapat digeneralisasi ke cluster dengan berbagai bentuk dan ukuran, seperti cluster elips.

Mengeneralisasi k-means

Penerapan k-means yang sederhana dapat mengalami kesulitan dengan cluster dengan kepadatan dan ukuran yang berbeda. Sisi kiri Gambar 1 menunjukkan cluster yang diharapkan akan kita lihat, sedangkan sisi kanan menunjukkan cluster yang diusulkan oleh k-means.

Gambar 1: Contoh k-means yang tidak digeneralisasi.

Untuk performa yang lebih baik pada cluster yang tidak seimbang seperti yang ditunjukkan pada Gambar 1, Anda dapat melakukan generalisasi, yaitu menyesuaikan, k-means. Gambar 2 menunjukkan tiga set data yang berbeda yang dikelompokkan dengan dua generalisasi yang berbeda. Set data pertama menunjukkan k-means tanpa generalisasi, sedangkan set data kedua dan ketiga memungkinkan cluster bervariasi lebarnya.

Gambar 2: pengelompokan k-means dengan dan tanpa generalisasi.

Kursus ini tidak membahas cara mengeneralisasi k-means, tetapi bagi yang tertarik, harus melihat Clustering – k-means Gaussian mixture models oleh Carlos Guestrin dari Carnegie Mellon University.

Kekurangan k-means

$k$ harus dipilih secara manual.

Hasil bergantung pada nilai awal.

Untuk $k$rendah, Anda dapat mengurangi dependensi ini dengan menjalankan k-means beberapa kali dengan nilai awal yang berbeda dan memilih hasil terbaik. Seiring meningkatnya $k$, Anda memerlukan seeding k-means untuk memilih sentroid awal yang lebih baik. Untuk diskusi lengkap tentang seeding k-means, lihat "A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm", oleh M. Emre Celebi, Hassan A. Kingravi, dan Patricio A. Vela.

Kesulitan mengelompokkan data dengan berbagai ukuran dan kepadatan tanpa generalisasi.

Sulit mengelompokkan pencilan.

Centroid dapat ditarik oleh pencilan, atau pencilan mungkin mendapatkan clusternya sendiri, bukan diabaikan. Pertimbangkan untuk menghapus atau memangkas pencilan sebelum melakukan pengelompokan.

Sulit diskalakan dengan jumlah dimensi.

Seiring bertambahnya jumlah dimensi dalam data, pengukuran kesamaan berbasis jarak akan berkonvergensi ke nilai konstan antara contoh tertentu. Kurangi dimensi dengan menggunakan PCA pada data fitur atau dengan menggunakan pengelompokan spektral untuk mengubah algoritma pengelompokan.

Kutukan dimensi dan pengelompokan spektral

Dalam tiga plot ini, perhatikan bagaimana, seiring bertambahnya dimensi, deviasi standar jarak antara contoh menyusut relatif terhadap jarak rata-rata antara contoh. Konvergensi ini berarti bahwa k-means menjadi kurang efektif dalam membedakan contoh seiring meningkatnya dimensi data. Hal ini disebut sebagai kutukan dimensi.

Gambar 3: Demonstrasi kutukan dimensi. Setiap plot menunjukkan jarak berpasangan antara 200 titik acak.

Anda dapat menghindari penurunan performa ini dengan pengelompokan spektral, yang menambahkan langkah pra-pengelompokan ke algoritma. Untuk melakukan pengelompokan spektral:

1. Kurangi dimensi data fitur menggunakan PCA.
2. Proyeksikan semua titik data ke dalam subruang berdimensi lebih rendah.
3. Mengelompokkan data dalam subruang ini menggunakan algoritma yang Anda pilih.

Lihat Tutorial tentang Pengelompokan Spektral oleh Ulrike von Luxburg untuk mengetahui informasi selengkapnya tentang pengelompokan spektral.

Istilah utama:

• pengelompokan spektral