Empat langkah yang diulang
K-Means bekerja dengan gagasan yang sangat sederhana: sebuah kelompok diwakili oleh titik tengahnya. Bila titik tengah sudah benar, setiap data seharusnya masuk ke titik tengah terdekat. Dan bila keanggotaan sudah benar, titik tengah seharusnya sama dengan rata-rata anggotanya. Dua syarat itu saling bergantung, jadi algoritmanya bergantian memenuhi keduanya sampai tidak ada yang berubah lagi.
- 01Pilih k titik sebagai pusat awal (centroid).
- 02Tetapkan tiap data ke centroid terdekat menurut jarak Euclidean.
- 03Hitung ulang tiap centroid sebagai rata-rata anggota barunya.
- 04Ulangi langkah 2–3 sampai keanggotaan tidak berubah lagi.
Prosedur ini dikenal sebagai algoritma Lloyd. Ia dijamin berhenti: setiap iterasi menurunkan total jarak kuadrat ke centroid, dan karena jumlah cara membagi 45 emiten ke 3 kelompok itu terbatas, penurunan tidak bisa berlangsung selamanya.