Skip to content
Kembali ke hasil pencarian

Clustering K-means

Diperkenalkan oleh
MacQueen, J. B.; Lloyd, S. P.
Tahun
1967 (formalized 1982)
Jenis
Partitional clustering
Keluarga
Machine learning

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

K-means adalah algoritma pengelompokan partisional tanpa pengawasan klasik yang membagi kumpulan data menjadi K kelompok yang tidak tumpang tindih dengan secara iteratif menetapkan setiap observasi ke sentroid terdekatnya dan memperbarui sentroid sebagai rata-rata dari titik-titik yang ditugaskan.

Ini adalah salah satu alat eksplorasi yang paling banyak digunakan dalam pembelajaran mesin dan analisis data.

Intuisi di balik metode

Bayangkan menjatuhkan K magnet pada peta titik data. Setiap titik ditarik ke magnet terdekatnya, dan kemudian setiap magnet bergerak ke pusat gravitasi dari titik-titik yang ditariknya. Ulangi siklus tarik-dan-gerak ini sampai tidak ada yang bergerak: magnet telah menemukan K pengelompokan alami. K-means memformalkan ide ini, meminimalkan jarak kuadrat total dari setiap titik ke pusat clusternya, yang disebut jumlah kuadrat dalam klaster (WCSS atau inersia).

Sejarah

Ide k-means diperkenalkan secara independen oleh MacQueen pada tahun 1967, yang menciptakan istilah tersebut, dan diformalkan sebagai algoritma iteratif yang efisien oleh Stuart Lloyd di Bell Labs pada tahun 1950-an (diterbitkan 1982). Peningkatan inisialisasi k-means++ oleh Arthur dan Vassilvitskii pada tahun 2007 mengatasi masalah sensitivitas minimum lokal. Saat ini k-means tetap menjadi metode pembelajaran tanpa pengawasan yang menjadi landasan yang diajarkan di hampir setiap kurikulum ilmu data.

Kapan digunakan

K-means cocok untuk pengelompokan eksploratif kumpulan data numerik murni yang besar ketika Anda memerlukan partisi yang cepat dan terukur dan nyaman menentukan K sebelumnya atau mencarinya dengan metode siku atau siluet. Ini bekerja dengan baik untuk segmentasi pelanggan, kompresi gambar, pengelompokan topik dokumen, dan pra-pemrosesan sebelum pembelajaran terawasi. Hindari jika klaster tidak berbentuk bola, memiliki ukuran atau kepadatan yang bervariasi, ketika fitur bersifat kategorikal atau ordinal (gunakan k-modes atau k-prototypes sebagai gantinya), ketika jumlah klaster sama sekali tidak diketahui dan eksperimen K yang bervariasi tidak layak, atau ketika data mengandung banyak pencilan (gunakan DBSCAN atau varian yang kuat sebagai gantinya).

Batasan dan pertimbangan

  • Memerlukan K untuk ditentukan sebelumnya; memilih K yang buruk menghasilkan klaster yang tidak berarti.
  • Mengasumsikan klaster berbentuk bola, berukuran serupa; klaster yang memanjang, tidak beraturan, atau berskala berbeda akan salah dibagi atau digabungkan.
  • Sensitif terhadap pencilan: satu titik ekstrem dapat menarik sentroid jauh dari sebagian besar klaster.
  • Hanya bekerja dengan fitur kontinu numerik; data kategorikal memerlukan algoritma yang berbeda (k-modes).
  • Konvergen ke minimum lokal; hasil dapat bervariasi antar eksekusi dengan benih acak yang berbeda kecuali jika k-means++ atau beberapa pengulangan digunakan.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Cepat dan terukur: O(nKdi) per iterasi, praktis pada jutaan observasi dengan K dan dimensi sedang.
  • Sederhana untuk diimplementasikan, tersedia secara luas di setiap kerangka kerja ML utama, dan mudah dijelaskan kepada audiens non-teknis.
  • Bekerja dengan baik pada klaster besar, terpisah dengan baik, kira-kira berbentuk bola dengan ukuran serupa.
  • Inisialisasi k-means++ secara substansial mengurangi sensitivitas terhadap kondisi awal dibandingkan dengan inisialisasi acak.
  • Deterministik dalam batas benih acak yang tetap, membuat hasil dapat direproduksi.

Penerapan

  • Segmentasi pelanggan untuk pemasaran dan personalisasi berdasarkan fitur perilaku atau demografis.
  • Kompresi gambar dengan mengkuantisasi warna piksel ke K nilai representatif (kuantisasi warna).
  • Pengelompokan dokumen dan teks sebagai langkah dalam alur pemodelan topik setelah vektorisasi.
  • Pra-pemrosesan deteksi anomali: titik-titik yang jauh dari sentroid mana pun adalah kandidat pencilan.
  • Langkah inisialisasi untuk algoritma yang lebih kompleks seperti model campuran Gaussian atau pengelompokan hierarkis.
  • Analisis ekspresi gen untuk mengelompokkan gen atau sampel dengan profil ekspresi yang serupa.

Cara kerjanya

Cara kerjanya

1

K sentroid klaster ditempatkan dalam ruang fitur, baik dengan memilih secara acak K titik data (Forgy) atau dengan strategi k-means++ yang lebih cerdas yang menyebarkan sentroid awal untuk mengurangi kemungkinan minimum lokal yang buruk. Pilihan inisialisasi penting: k-means++ biasanya menghasilkan konvergensi yang lebih cepat dan solusi akhir yang lebih baik.

2

Setiap observasi ditugaskan ke klaster yang sentroidnya terdekat menurut jarak Euclidean. Penugasan keras ini menciptakan K partisi data yang tidak tumpang tindih. Secara formal, setiap titik x_i ditugaskan ke klaster c_i = argmin_k ||x_i - mu_k||^2.

Rumus
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

Setiap sentroid dihitung ulang sebagai rata-rata aritmatika dari semua titik yang saat ini ditugaskan ke klaster tersebut: mu_k = (1/|C_k|) dikalikan jumlah semua x_i di C_k. Langkah ini menjamin bahwa sentroid baru meminimalkan WCSS dalam setiap klaster mengingat penugasan saat ini.

Rumus
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

Langkah penugasan dan pembaruan bergantian sampai posisi sentroid berhenti berubah (atau berubah kurang dari ambang batas toleransi) atau jumlah iterasi maksimum tercapai. Algoritma dijamin konvergen ke minimum lokal WCSS, meskipun tidak selalu minimum global.

5

Kualitas solusi dinilai dengan WCSS total (inersia) J = jumlah di atas klaster dari jumlah di atas titik yang ditugaskan dari ||x_i - mu_k||^2. Memilih K adalah masalah terpisah yang ditangani oleh metode siku, skor siluet, atau statistik celah, karena algoritma itu sendiri memerlukan K untuk ditentukan sebelumnya.

Rumus
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

Kesalahan umum

  • Melupakan standarisasi fitur sebelum pengelompokan — variabel pada skala besar akan mendominasi perhitungan jarak.
  • Memilih K dengan hanya memeriksa WCSS dalam sampel tanpa plot siku atau validasi siluet, yang mengarah ke K yang terlalu kecil atau terlalu besar.
  • Menjalankan hanya satu inisialisasi dan menerima hasil pertama tanpa beberapa pengulangan untuk melindungi dari minimum lokal yang buruk.
  • Memasukkan variabel kategorikal atau ordinal dalam matriks fitur tanpa pengkodean yang sesuai atau beralih ke k-modes.
  • Memperlakukan label klaster sebagai identitas kelompok yang bermakna tanpa validasi eksternal, terutama ketika klaster tidak terpisah dengan baik.

Pertanyaan yang sering diajukan

Bagaimana cara memilih jumlah klaster K yang tepat?

Jalankan k-means untuk berbagai nilai K, plot jumlah kuadrat dalam klaster terhadap K, dan cari 'siku' di mana tingkat penurunan melambat tajam. Lengkapi ini dengan skor siluet, yang mengukur seberapa mirip setiap titik dengan klaster sendiri dibandingkan dengan klaster tetangga; siluet rata-rata yang lebih tinggi menunjukkan klaster yang terdefinisi lebih baik.

Mengapa saya mendapatkan hasil yang berbeda setiap kali dijalankan?

K-means sensitif terhadap inisialisasi dan konvergen ke minimum lokal daripada global dari WCSS. Gunakan inisialisasi k-means++ dan atur benih acak yang tetap untuk reproduktifitas. Menjalankan algoritma beberapa kali dengan benih yang berbeda dan menyimpan solusi dengan inersia terendah adalah praktik yang baik.

Apakah k-means bekerja dengan data kategorikal?

Tidak. K-means bergantung pada jarak Euclidean dan rata-rata sentroid, yang tidak terdefinisi untuk variabel kategorikal. Untuk data kategorikal murni gunakan k-modes; untuk data campuran numerik dan kategorikal gunakan k-prototypes.

Kapan saya harus memilih DBSCAN atau GMM daripada k-means?

Gunakan DBSCAN ketika klaster memiliki bentuk tidak beraturan atau Anda memerlukan deteksi pencilan otomatis tanpa menentukan K. Gunakan Model Campuran Gaussian (GMM) ketika Anda menginginkan penugasan klaster yang lunak (probabilistik) atau klaster dengan ukuran dan orientasi yang berbeda, dengan biaya kompleksitas komputasi yang lebih tinggi.

Apakah saya perlu menskalakan fitur saya?

Ya, hampir selalu. K-means menggunakan jarak Euclidean, jadi fitur dengan rentang numerik besar akan mendominasi pengelompokan. Terapkan standarisasi z-score atau penskalaan min-max sebelum menyesuaikan k-means, kecuali semua fitur sudah dalam skala yang sama.

Metode terkait

Sumber

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    Buka referensi DOI
    Disalin.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    Buka referensi publikasi
    Disalin.