Seperti yang disebutkan sebelumnya, banyak algoritma pengelompokan tidak diskalakan ke set data yang digunakan dalam machine learning, yang sering kali memiliki jutaan contoh. Misalnya, algoritme pengelompokan hierarkis aglomeratif atau pemisah melihat semua pasangan titik dan memiliki kompleksitas masing-masing \(O(n^2 log(n))\) dan \(O(n^2)\).
Kursus ini berfokus pada k-means karena diskalakan sebagai \(O(nk)\), dengan \(k\) adalah jumlah cluster yang dipilih oleh pengguna. Algoritma ini mengelompokkan titik ke dalam \(k\) cluster dengan meminimalkan jarak antara setiap titik dan centroid cluster-nya (lihat Gambar 1).
Akibatnya, k-means secara efektif memperlakukan data sebagai terdiri dari sejumlah distribusi yang berbentuk melingkar, dan mencoba menemukan cluster yang sesuai dengan distribusi ini. Namun, data dunia nyata berisi pencilan dan cluster berbasis kepadatan dan mungkin tidak cocok dengan asumsi yang mendasari k-means.
Algoritme pengelompokan k-means
Algoritma ini mengikuti langkah-langkah berikut:
Berikan tebakan awal untuk \(k\), yang dapat direvisi nanti. Untuk contoh ini, kita memilih \(k = 3\).
Memilih centroid \(k\) secara acak.
Gambar 1: k-means saat inisialisasi. Tetapkan setiap titik ke centroid terdekat untuk mendapatkan \(k\) cluster awal.
Gambar 2: Cluster awal. Untuk setiap cluster, hitung centroid baru dengan mengambil posisi rata-rata semua titik dalam cluster. Panah pada Gambar 4 menunjukkan perubahan posisi centroid.
Gambar 3: Centroid yang dihitung ulang. Tetapkan ulang setiap titik ke centroid baru terdekat.
Gambar 4: Cluster setelah penetapan ulang. Ulangi langkah 4 dan 5, hitung ulang centroid dan keanggotaan cluster, hingga titik tidak lagi mengubah cluster. Untuk set data yang besar, Anda dapat menghentikan algoritma sebelum konvergensi berdasarkan kriteria lain.
Karena posisi centroid awalnya dipilih secara acak, k-means dapat menampilkan hasil yang sangat berbeda pada pengoperasian berturut-turut. Untuk mengatasi masalah ini, jalankan k-means beberapa kali dan pilih hasilnya dengan metrik kualitas terbaik. (Kita akan menjelaskan metrik kualitas nanti dalam kursus ini.) Anda memerlukan k-means versi lanjutan untuk memilih posisi centroid awal yang lebih baik.
Meskipun pemahaman mendalam tentang matematika tidak diperlukan, bagi yang ingin tahu, k-means adalah kasus khusus dari algoritma ekspektasi-maksimum. Lihat catatan kuliah tentang topik ini dari UPenn.