ENID
Lensa ML

K-Means Clustering

Langkah 1 dari 6: Apa Itu Clustering?

Mengelompokkan tanpa label

data tanpa label
Titik
60
Cluster
3
Separasi
4.9

Clustering mencari kelompok alami dalam data tanpa label. Geser k untuk mengubah jumlah cluster yang sebenarnya, lalu tampilkan.

Geser slider jumlah cluster (k) dari 2 ke 5, lalu klik Tampilkan Cluster untuk mewarnai setiap titik menurut kelompok asalnya. Kartu separasi membagi rata-rata jarak antarpusat cluster dengan rata-rata sebaran di dalam cluster, jadi nilai yang lebih tinggi berarti kelompok lebih mudah dibedakan. Dalam masalah nyata, kelompok yang sebenarnya tidak diketahui, sehingga hasil clustering sulit dinilai. Skor internal seperti silhouette coefficient membandingkan jarak setiap titik ke cluster-nya sendiri dengan jaraknya ke cluster terdekat berikutnya.

Langkah 2 dari 6: Cara Kerja K-Means

Algoritmanya, langkah demi langkah

k = 3 cluster yang dicari
Fase
1/6
k
3
Berpindah
—
Inertia
—

Data ini tanpa label, dan tujuannya menemukan k=3 cluster di dalamnya.

Klik keenam tombol fase secara berurutan, atau geser slider fase. Prosedur ini adalah algoritma Lloyd, yang dijelaskan Stuart Lloyd di Bell Labs pada 1957 dan diterbitkan pada 1982. Biaya setiap iterasi adalah O(n · k · d) untuk n titik, k centroid, dan d dimensi, karena setiap titik dibandingkan dengan setiap centroid. Pada data ini, prosesnya sudah stabil setelah dua kali pembaruan. Centroid awal yang acak bisa jatuh di posisi buruk, jadi metode k-means++ memilih setiap centroid awal baru dengan probabilitas yang sebanding dengan jarak kuadratnya dari centroid yang sudah terpilih.

Langkah 3 dari 6: Langkah Penetapan

Warnai menurut centroid terdekat

Iterasi: 0
Iterasi
0
Berpindah
60
Inertia
929.0
Terbesar
35

Setiap titik bergabung dengan centroid terdekat, sehingga bidang terbagi menjadi wilayah Voronoi. Tekan Putar atau geser slider.

Tekan Putar atau geser slider iterasi, lalu lihat titik berganti warna. Selama centroid tidak bergerak, menetapkan setiap titik ke centroid terdekat menghasilkan inertia serendah mungkin, jadi langkah ini menyelesaikan separuh masalahnya secara tepat. Batas antara dua cluster adalah garis bagi tegak lurus dari ruas yang menghubungkan kedua centroid, sehingga setiap wilayah berbentuk poligon konveks. Cluster yang memanjang atau melengkung terpotong oleh batas lurus ini. Karena aturannya memakai jarak Euclidean, feature berskala besar lebih dominan, dan data biasanya distandardisasi dulu.

Langkah 4 dari 6: Langkah Pembaruan

Pindahkan centroid ke rata-ratanya

Iterasi: 1
Iterasi
1
Geser maks.
3.11
Inertia
287.7
% perubahan
-69.0%

Centroid bergeser sampai 3,11 satuan, masing-masing menuju rata-rata cluster-nya.

Tekan Putar atau geser slider iterasi, lalu ikuti panah putus-putus. Untuk sekumpulan titik yang tetap, rata-rata adalah lokasi yang meminimalkan jumlah jarak kuadrat, jadi langkah ini juga menyelesaikan separuh masalahnya secara tepat. Itulah sebabnya k-means memasangkan rata-rata dengan jarak Euclidean kuadrat. Memakai median dengan jarak Manhattan menghasilkan k-medians, sedangkan mewajibkan setiap pusat berupa titik data asli menghasilkan k-medoids, yang bekerja dengan jarak apa pun. Mini-batch k-means memperbarui centroid dari sampel acak kecil sehingga sanggup menangani jutaan titik.

Langkah 5 dari 6: Konvergensi

Saat penetapan berhenti berubah

Iterasi: 0
IterasiInertia05101576526975
Iterasi
0
Inertia
929.0
Δ inertia
—
Konvergen?
Belum

K-means berhenti ketika tidak ada titik yang berganti cluster. Tekan Putar dan lihat inertia turun.

Tekan Putar atau geser slider iterasi melewati 15 iterasi, lalu perhatikan kurva inertia. Inertia tidak pernah naik, karena setiap langkah optimal untuk separuh masalahnya. Cara menetapkan titik ke cluster juga jumlahnya terbatas, jadi algoritma pasti berhenti. Di sini inertia turun dari 734 ke 85 dalam dua kali pembaruan. Titik berhentinya bisa berupa optimum lokal, dan secara umum mencari optimum global tergolong NP-hard. Karena itu, library mengulang dari beberapa titik awal acak dan menyimpan hasil dengan inertia terendah. Parameter n_init di scikit-learn menentukan berapa kali pengulangannya.

Langkah 6 dari 6: Metode Elbow

Memilih k yang tepat

k (cluster)Inertia12345678910elbow
k
3
Inertia
84.8
Δ inertia
306.3
k yang disarankan
3

Inilah elbow: setelah k=3, setiap cluster tambahan hanya menurunkan sedikit inertia. Ini pilihan yang umum.

Geser k dari 1 ke 10 dan bandingkan angka inertia. Inertia selalu turun saat k bertambah dan mencapai nol ketika setiap titik menjadi cluster-nya sendiri, jadi nilai terendah bukan tujuannya. Di sini penurunan dari k = 2 ke k = 3 sekitar 306, sedangkan dari k = 3 ke k = 4 hanya sekitar 13. Tekukan itu menandai elbow di 3, sesuai dengan 3 kelompok asal data. Kurva pada data nyata sering menekuk kurang jelas, dan silhouette score atau gap statistic bisa membantu memilih k.

Apa itu k-means clustering?

K-means adalah algoritma unsupervised clustering yang membagi data menjadi k kelompok. Setiap titik masuk ke cluster dengan pusat terdekat, yang disebut centroid. Algoritma ini bergantian menjalankan dua langkah, yaitu menetapkan titik ke centroid terdekat dan memindahkan setiap centroid ke rata-rata titiknya, sampai penetapan berhenti berubah. Hasilnya meminimalkan, setidaknya secara lokal, total jarak kuadrat dari titik ke centroid-nya.

K-means dipakai untuk segmentasi pelanggan, color quantization gambar, pengelompokan dokumen, dan kompresi embedding vector, seperti vector quantization di dalam indeks approximate nearest-neighbor. Metode ini cepat dan sederhana, tetapi mengasumsikan cluster yang kurang lebih bulat dan berukuran mirip, dan nilai k harus dipilih di awal.

Ide utama

  • K-means membagi data menjadi k cluster, dan setiap cluster diwakili rata-rata titiknya.
  • Algoritma ini bergantian menjalankan langkah penetapan dan langkah pembaruan sampai penetapan berhenti berubah.
  • Kedua langkah menurunkan inertia, yaitu total jarak kuadrat dari titik ke centroid-nya.
  • Algoritma ini selalu konvergen, tetapi sering ke optimum lokal yang bergantung pada centroid awal.
  • Inisialisasi k-means++ dan beberapa kali pengulangan acak membuat hasil yang baik jauh lebih mungkin.
  • Elbow pada kurva inertia adalah heuristic yang umum untuk memilih k.

Ulasan singkat tentang topik ini

Pertanyaan umum

Apa bedanya k-means dan k-NN?

K-means adalah unsupervised clustering, dan k-nya adalah jumlah cluster yang dicari. K-nearest neighbors adalah klasifikasi atau regresi supervised, dan k-nya adalah jumlah tetangga berlabel yang memberi suara. Keduanya bergantung pada jarak, dan dari situlah kebingungannya sering muncul.

Kapan k-means gagal?

K-means kesulitan ketika cluster memanjang, melengkung, bersarang, atau sangat berbeda ukuran atau kepadatannya, karena batas yang digambarnya lurus di tengah antar-centroid. Outlier juga menarik centroid menjauh dari bagian utama cluster. DBSCAN menangani bentuk sembarang dan noise, sedangkan Gaussian mixture model menangani cluster elips dengan ukuran berbeda.

Apa hubungan k-means dengan Gaussian mixture model?

Gaussian mixture yang di-fit dengan expectation-maximization memberi setiap titik probabilitas soft untuk masuk ke setiap cluster. Kalau setiap komponen punya variance sferis yang sama dan kecil, penetapan soft itu berubah menjadi penetapan hard ke centroid terdekat, dan algoritmanya menjadi k-means.

Apakah k-means perlu feature scaling?

Biasanya perlu. Jarak Euclidean kuadrat menjumlahkan selisih di semua feature, jadi feature dengan satuan besar mendominasi clustering. Menstandardisasi setiap feature lebih dulu membuat pengaruhnya sebanding, kecuali satuan aslinya memang bermakna dan bisa dibandingkan.

Penjelasan terkait

Referensi

  1. Lloyd (1982), "Least Squares Quantization in PCM", IEEE Transactions on Information Theory
  2. James, Witten, Hastie & Tibshirani, "An Introduction to Statistical Learning", chapter 12: Unsupervised Learning

Terakhir diperbarui