Seperti yang telah disebutkan, banyak algoritma pengklasteran yang tidak diskalakan ke {i>dataset<i} digunakan dalam {i>machine learning<i}, yang sering kali memiliki jutaan contoh. Misalnya, algoritma pengklasteran hierarkis aglomeratif atau divisif melihat semua pasangan poin dan memiliki kompleksitas \(O(n^2 log(n))\) dan \(O(n^2)\), masing-masing.
Kursus ini berfokus pada k-means karena diskalakan sebagai \(O(nk)\), dengan \(k\) adalah jumlah klaster yang dipilih oleh pengguna. Algoritma ini mengelompokkan titik ke dalam \(k\) cluster dengan meminimalkan jarak antara setiap titik dan clusternya centroid cluster (lihat Gambar 1).
Akibatnya, k-means secara efektif memperlakukan data sebagai terdiri dari distribusi sirkular, dan mencoba menemukan klaster yang sesuai dengan distribusi. Tetapi data di dunia nyata berisi pencilan dan klaster berbasis kepadatan dan mungkin tidak cocok dengan asumsi yang mendasari k-means.
Algoritma pengelompokan k-means
Algoritma mengikuti langkah-langkah berikut:
Berikan tebakan awal untuk \(k\), yang dapat direvisi nanti. Untuk ini misalnya, kita pilih \(k = 3\).
Pilih sentroid \(k\) secara acak.
Gambar 1: k-means saat inisialisasi. Tetapkan setiap titik ke sentroid terdekat untuk mendapatkan \(k\) klaster awal.
Gambar 2: Cluster awal. Untuk setiap klaster, hitung sebuah sentroid baru dengan mengambil posisi rata-rata dari semua titik dalam cluster. Tanda panah pada Gambar 4 menunjukkan perubahan posisi sentroid.
Gambar 3: Sentroid yang dikomputasi ulang. Tetapkan kembali setiap titik ke sentroid baru terdekat.
Gambar 4: Cluster setelah penetapan ulang. Ulangi langkah 4 dan 5, hitung ulang sentroid dan keanggotaan klaster, sampai poin tidak lagi mengubah klaster. Dalam kasus {i>dataset <i}besar, Anda bisa menghentikan algoritma sebelum konvergensi berdasarkan kriteria lain.
Karena posisi sentroid awalnya dipilih secara acak, k-means dapat memberikan hasil yang berbeda secara signifikan pada pengujian yang berurutan. Untuk mengatasi hal ini, masalah, jalankan k-means beberapa kali dan pilih hasil dengan kualitas terbaik metrik. (Kami akan menjelaskan metrik kualitas nanti dalam kursus ini.) Anda akan memerlukan versi lanjutan k-means untuk memilih posisi sentroid awal yang lebih baik.
Meskipun pemahaman mendalam tentang matematika tidak diperlukan, bagi mereka yang penasaran, k-means adalah kasus khusus dari algoritma pemaksimalan ekspektasi. Lihat catatan kuliah tentang topik dari UPenn.