4 Algoritma K-Means
“It’s not the data that’s important, it’s the story the data tells”
– Moneyball
Algoritma K-Means merupakan salah satu algoritma cluster berbasis partisi yang paling populer dalam analisis cluster, yang digunakan untuk mengelompokkan data ke dalam beberapa kelompok berdasarkan kesamaan fitur atau atribut (Jain 2010) . Algoritma ini bekerja dengan cara membagi data ke dalam \(k\) cluster, di mana \(k\) adalah jumlah cluster yang ditentukan sebelumnya oleh pengguna. Proses pengelompokan algoritma K-Means dilakukan dengan meminimalkan jarak antara data dalam satu cluster dan pusat cluster (centroid) yang dihasilkan. Langkah pertama dalam algoritma K-Means adalah inisialisasi centroid untuk setiap cluster, yang dapat dilakukan secara acak atau menggunakan metode tertentu seperti K-Means++ (Arthur and Vassilvitskii 2007). Setelah centroid diinisialisasi, algoritma K-Means kemudian mengelompokkan setiap data ke dalam cluster terdekat berdasarkan jarak Euclidean (Hastie, Tibshirani, and Friedman 2009). Proses ini diulang hingga tidak ada perubahan signifikan dalam posisi centroid atau tidak ada perubahan dalam pengelompokan data.
Sejarah algoritma k-means dapat ditelusuri kembali ke tahun 1950-an, meskipun konsep dasar pengelompokan data telah ada jauh sebelumnya. Algoritma ini pertama kali diperkenalkan oleh Stuart Lloyd pada tahun 1957 dalam konteks pengkodean vektor, namun baru mendapatkan perhatian luas setelah dipopulerkan oleh MacQueen pada tahun 1967 (MacQueen 1967). Sejak saat itu, k-means telah menjadi salah satu algoritma yang paling banyak digunakan dalam analisis data dan machine learning, dengan banyak variasi dan pengembangan yang muncul seiring dengan kemajuan teknologi dan kebutuhan analisis data yang semakin kompleks.
Algoritma k-means berfokus pada pengukuran jarak antara data dan centroid. Umumnya, jarak Euclidean digunakan sebagai metrik untuk menentukan kedekatan antara titik data dan centroid. Proses ini dimulai dengan pemilihan \(k\) centroid awal secara acak dari dataset. Selanjutnya, setiap titik data akan dialokasikan ke cluster berdasarkan jarak terdekat ke centroid. Setelah semua data dialokasikan, centroid diperbarui dengan menghitung rata-rata posisi dari semua titik data yang termasuk dalam cluster tersebut. Proses ini diulang hingga tidak ada perubahan dalam alokasi cluster atau hingga jumlah iterasi maksimum tercapai.
\[ d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2} \]
di mana:
\(d(x, y)\): Jarak Euclidean antara dua titik \(x\) dan \(y\).
\(x_i\): Koordinat titik \(x\) pada dimensi ke-\(i\).
\(y_i\): Koordinat titik \(y\) pada dimensi ke-\(i\).
\(n\): Jumlah dimensi dalam ruang data.
\((x_i - y_i)^2\): Kuadrat dari selisih nilai koordinat pada dimensi ke-\(i\).
Algoritma k-means melibatkan minimisasi fungsi objektif, yang merupakan jumlah kuadrat jarak antara setiap titik data dan centroid cluster yang sesuai. Fungsi objektif ini dinyatakan sebagai berikut:
\[ J = \sum_{i=1}^{k} \sum_{x \in C_i} | x - \mu_i |^2 \]
di mana:
\(J\) adalah fungsi objektif
\(k\) adalah jumlah cluster
\(C_i\) adalah cluster ke-i,
\(x\) adalah titik data, dan
\(\mu_i\) adalah centroid dari cluster ke-i.
Kelebihan utama dari algoritma k-means adalah kesederhanaan dan kecepatan eksekusinya, terutama pada dataset besar. Algoritma ini dapat dengan cepat memberikan hasil yang memadai dan mudah diinterpretasikan (Han, Kamber, and Pei 2011). Selain itu, k-means juga dapat diimplementasikan dengan mudah dalam berbagai bahasa pemrograman dan platform analisis data, menjadikannya pilihan yang menarik bagi para peneliti dan praktisi di berbagai bidang. Namun, algoritma k-means juga memiliki beberapa kelemahan yang perlu diperhatikan. Salah satu kelemahan utama adalah ketergantungannya pada pemilihan jumlah cluster \((k)\) yang tepat, yang sering kali sulit ditentukan tanpa pengetahuan sebelumnya tentang data. Selain itu, k-means sensitif terhadap outlier dan noise, yang dapat mempengaruhi posisi centroid dan hasil akhir pengelompokan (Elbow 1975). Algoritma ini juga mengasumsikan bahwa cluster berbentuk bulat dan memiliki ukuran yang seragam, yang tidak selalu mencerminkan struktur data yang sebenarnya
Dalam praktiknya, algorima K-Means banyak digunakan dalam berbagai bidang, termasuk pemasaran, pengenalan pola, dan analisis citra (Xu and Wunsch 2005). Misalnya, dalam pemasaran, K-Means dapat digunakan untuk segmentasi pelanggan berdasarkan perilaku pembelian mereka, sehingga perusahaan dapat menargetkan strategi pemasaran yang lebih efektif (Kumar and Reinartz 2016). Dengan demikian, pemahaman yang baik tentang algoritma K-Means sangat penting bagi para peneliti dan praktisi yang ingin menerapkan analisis cluster dalam pekerjaan mereka. Secara keseluruhan, algoritma K-Means adalah alat yang kuat dan fleksibel untuk analisis cluster, meskipun penggunaannya memerlukan pemahaman yang mendalam tentang data dan konteks analisis (Bishop 2006). Dalam buku ini, akan dibahas secara rinci tentang cara menerapkan algoritma K-Means menggunakan R, serta memberikan panduan langkah demi langkah untuk membantu pemula memahami dan menguasai teknik ini.