4.1 Tahapan Algoritma K-Means
1. Inisialisasi Centroid
Pilih jumlah cluster \(k\) yang diinginkan. Inisialisasi \(k\) centroid secara acak dari dataset. Centroid adalah titik yang mewakili pusat dari setiap cluster.
\[ C_k = (x_{k1}, x_{k2}, \ldots, x_{kn}) \quad \text{untuk } k = 1, 2, \ldots, K \] di mana \(C_k\) adalah centroid untuk cluster ke-\(k\) dan \(x_{ki}\) adalah nilai fitur ke-\(i\) dari centroid ke-\(k\).
2. Penugasan Cluster
Untuk setiap titik data \(x_i\), hitung jarak ke setiap centroid \(C_k\) dan tetapkan titik data tersebut ke cluster dengan centroid terdekat. Jarak yang umum digunakan adalah jarak Euclidean.
\[ d(x_i, C_k) = \sqrt{\sum_{j=1}^{m} (x_{ij} - C_{kj})^2} \] di mana \(d(x_i, C_k)\) adalah jarak antara titik data \(x_i\) dan centroid \(C_k\), \(m\) adalah jumlah fitur, dan \(x_{ij}\) adalah nilai fitur ke-\(j\) dari titik data ke-\(i\).
Penugasan cluster dapat dinyatakan sebagai:
\[ \text{Cluster}(x_i) = \arg\min_{k} d(x_i, C_k) \]
3. Perbaharui Centroid
Setelah semua titik data ditugaskan ke cluster, hitung ulang posisi centroid untuk setiap cluster dengan mengambil rata-rata dari semua titik data yang ditugaskan ke cluster tersebut.
\[ C_k = \frac{1}{N_k} \sum_{x_i \in \text{Cluster}_k} x_i \] di mana \(N_k\) adalah jumlah titik data dalam cluster ke-\(k\) dan \(\text{Cluster}_k\) adalah himpunan titik data yang ditugaskan ke cluster ke-\(k\).
4. Ulangi Langkah 2 dan 3
Ulangi langkah penugasan cluster dan pembaruan centroid hingga tidak ada perubahan signifikan dalam posisi centroid atau tidak ada perubahan dalam pengelompokan data. Kriteria konvergensi dapat berupa:
\[ \text{Jika } \| C_k^{(t)} - C_k^{(t-1)} \| < \epsilon \quad \text{atau tidak ada perubahan cluster} \]
di mana \(\epsilon\) adalah ambang batas kecil yang ditentukan sebelumnya.