k means algorithm

algoritma k-means

Ini adalah implementasi Python dari algoritma k-means termasuk metode siku dan metode siluet untuk memilih K optimal

K-means adalah algoritma pengelompokan populer yang digunakan untuk mempartisi data menjadi K cluster. Ia bekerja dengan menugaskan setiap titik data secara berulang ke pusat massa cluster terdekat dan kemudian menghitung ulang pusat massa setiap cluster berdasarkan titik data yang ditugaskan padanya. Proses ini diulang sampai konvergensi.

Algoritma

• Pilih secara acak K pusat klaster awal dari titik data.
• Tetapkan setiap titik data ke pusat cluster terdekat.
• Hitung ulang pusat massa setiap cluster berdasarkan titik data yang ditetapkan padanya.
• Ulangi langkah 2-3 hingga konvergensi (yaitu ketika penetapan cluster tidak lagi berubah).

Fungsi Tujuan

Tujuan dari k-means adalah untuk meminimalkan jumlah jarak kuadrat antara setiap titik data dan pusat cluster yang ditugaskan. Fungsi tujuan dapat ditulis sebagai: $$J = jumlah_{j=1}^K jumlah_{i=1}^N||x_i^j - mu_j||^2$$ Di mana $x_i^j$ adalah titik data i-th dalam cluster j , μj adalah pusat massa cluster j , dan N adalah jumlah total titik data.

Metode Siku

Metode Elbow merupakan heuristik yang digunakan untuk menentukan jumlah cluster optimal pada clustering K-Means. Metode ini memplot jumlah jarak kuadrat antara setiap observasi dan pusat massa yang ditetapkan sebagai fungsi dari jumlah cluster. Titik "siku" pada plot menunjukkan jumlah cluster dimana penambahan cluster tambahan tidak menghasilkan pengurangan jumlah kuadrat jarak yang signifikan.

Metode Elbow dapat diringkas dengan langkah-langkah berikut:

• Jalankan pengelompokan K-Means untuk rentang nilai k
• Hitung jumlah jarak kuadrat untuk setiap nilai k
• Plot jumlah jarak kuadrat sebagai fungsi dari k
• Identifikasi titik "siku" pada plot

Metode Siluet

Metode Silhouette adalah heuristik lain yang digunakan untuk menentukan jumlah cluster optimal dalam clustering K-Means. Metode ini mengukur kualitas penugasan cluster setiap observasi dengan menghitung koefisien siluetnya. Koefisien siluet berkisar antara -1 hingga 1, dimana nilai 1 menunjukkan bahwa observasi tersebut berkerumun dengan baik dan nilai -1 menunjukkan bahwa observasi tersebut salah klasifikasi. Rumus untuk menghitung koefisien siluet suatu titik data i adalah: $$s(i) = frac{(b(i) - a(i))}{maks(a(i), b(i))}$$ dimana a(i) adalah jarak rata-rata antara i dan semua titik data lain dalam clusternya, dan b(i) adalah jarak rata-rata minimum antara i dan semua cluster lainnya (yaitu cluster dengan pusat massa terdekat berikutnya). Koefisien siluet untuk keseluruhan pengelompokan adalah rata-rata koefisien siluet untuk semua titik data.

Metode Silhouette dapat diringkas dengan langkah-langkah berikut:

• Jalankan pengelompokan K-Means untuk rentang nilai k
• Untuk setiap pengamatan, hitung koefisien siluetnya
• Hitung koefisien siluet rata-rata untuk setiap nilai k
• Plot koefisien siluet rata-rata sebagai fungsi dari k
• Identifikasi nilai k dengan koefisien siluet rata-rata tertinggi