k-Means Clustering
Latar Belakang
Clustering, atau pengelompokkan, adalah suatu permasalahan dalam menentukan kelompok yang sesuai dari data yang ada sehingga setiap data yang berada di dalam satu kelompok memiliki suatu kedekatan. Kedekatan ini dapat didefinisikan secara berbeda-beda, tergantung kepada permasalahan yang dihadapi. Berikut adalah beberapa contoh permasalahan clustering:
- Terdapat banyak pembeli di sebuah minimarket. Berdasarkan barang yang dibelinya, ingin dicari mengenai kelompok-kelompok pelanggan yang ada. Sebagai contoh, bisa saja terdapat kelompok Ibu Rumah Tangga, Mahasiswa Kostan, dan Orang yang akan Bepergian. Nantinya, minimarket tersebut dapat menarik kesimpulan mengenai karakteristik tiap kelompok pelanggan ini.
- Terdapat banyak lagu yang ada di Spotify. Berdasarkan lirik, judul, penyanyi, dan mungkin melodi lagu, lagu-lagu ini dapat dikelompokkan menjadi beberapa tipe lagu. Hal ini akan sangat berguna dalam sistem perekomendasian lagu.
Permasalahan clustering merupakan sebuah metode penyelesaian unsupervised learning. Artinya, wawasan dan karakteristik data dapat disimpulkan tanpa adanya pelabelan mengenai keluaran data.
Clustering secara matematis
Permasalahan clustering dapat dianggap sebagai sebuah permasalahan optimasi. Secara formal, permasalahan ini dapat dianggap sebagai peminimalan nilai dari
dimana,
- N adalah banyak data yang ada
- k adalah banyak kelompok yang diharapkan
- d_i adalah data yang ada untuk 1 ≤ i≤N
- G adalah fungsi yang mengirim indeks sebuah data ke nama kelompok data tersebut
- rep adalah fungsi yang mengirim kelompok data ke data yang merupakan representasi kelompok tersebut
- dist adalah fungsi yang menghitung jarak antara dua buah data
Representasi dari sebuah kelompok dapat dianggap sebagai data yang dianggap paling mewakili kelompok tersebut. Representasi dari sebuah kelompok bisa saja berupa median, modus, ataupun rata-rata aritmetika dari data-data di kelompok tersebut. Pada algoritma k-Means, representasi kelompok adalah rata-rata aritmetika dari data-data kelompok tersebut.
Jarak antara dua buah data disesuaikan dengan tipe dari data tersebut. Salah satu fungsi jarak yang paling sering digunakan adalah jarak Euclidean antara dua vektor. Ada juga fungsi jarak lainnya. Sebagai contoh, fungsi Cosine Similarity untuk data yang bertipe artikel dan fungsi jarak Haversine untuk data berupa koordinat pada bola.
Nilai k perlu dibandingkan terlebih dahulu agar kelompok data yang terbentuk dapat diamati polanya. Saat k = N, setiap kelompok hanya memuat satu data saja meskipun nilai J di kasus ini adalah 0, nilai paling minimal yang dapat dicapai. Pengelompokan ini jelas tidak berguna. Sebaliknya, pada kasus k = 1, semua data dikelompokkan di kelompok yang sama. Pengelompokkan ini juga jelas tidak berguna. Penentuan nilai k ini akan dibahas pada bagian berikutnya.
Permasalahan utama adalah bagaimana mengatur fungsi G untuk menyortir setiap data menjadi salah satu dari kelompok yang ada. Untuk suatu nilai k tertentu, yang diharapkan adalah adanya algoritma yang dapat menentukan nilai J yang minimal. Sayangnya, algoritma ini sangat tidak efisien untuk digunakan. Oleh karena itu, algoritma yang digunakan hanya mengembalikan solusi minimal lokal, termasuk di antaranya algoritma k-Means. Meskipun begitu, dalam kasus umum, algoritma k-Means ini sudah memadai.
Algoritma k-Means
Algoritma k-Means adalah algoritma yang dapat digunakan untuk mengelompokkan data-data yang ada. Algoritma ini didasarkan kepada heuristik bahwa setiap kelompok memiliki sebuah pusat dan setiap data akan dikelompokkan ke kelompok dengan pusat terdekat. Lebih lengkapnya, pseudocode dari algoritma ini ditunjukkan di bawah.
Algoritma k-Means
Diberikan sebuah kumpulan data N dan data-data tersebut ingin dikelompokkan menjadi k buah kelompok.Cluster(N, k):
1. Pilih secara acak k buah data untuk dijadikan pusat dari kelompok.
2. Untuk setiap data, carilah data pusat terdekat C dan masukkan data tersebut ke kelompok C
3. Untuk setiap kelompok yang ada, tentukan pusat yang baru dengan mengambil rata-rata dari semua data di kelompok tersebut
4. Kembali ke langkah 2 hingga konvergen. Salah satunya adalah ketika data-data pusat sudah tidak berubah lagi
Mari kita lihat implementasi algoritma k-Means dengan mengikuti pseudocode di atas. Implementasi algoritma ini dalam bahasa python sedikit dimodifikasi dari algoritma yang ada di https://jakevdp.github.io/PythonDataScienceHandbook/05.11-k-means.html.
Pertama, akan dibuat data secara acak dengan library sklearn.datasets.
import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np
from sklearn.datasets import make_blobs
X, y_true = make_blobs(n_samples=200, centers=5,
cluster_std=0.70, random_state = 2)
plt.scatter(X[:, 0], X[:, 1])
plt.show()
Perhatikanlah bahwa terdapat 3–5 cluster di data tersebut, tergantung dari bagaimana cara memandangnya. Sekarang, algoritma yang digunakan diimplementasikan pada kode di bawah ini. Banyak kelompok yang dibuat adalah n_clusters dan menggunakan fungsi jarak pairwise_distances_argmin.
from sklearn.metrics import pairwise_distances_argmindef find_clusters(X, n_clusters):
# 1. Randomly choose clusters
i = np.random.RandomState(1).permutation(X.shape[0])[:n_clusters]
centers = X[i]
while True:
# 2a. Assign labels based on closest center
labels = pairwise_distances_argmin(X, centers)
# 2b. Find new centers from means of points
new_centers = np.array([X[labels == i].mean(0)
for i in range(n_clusters)])
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='magma')
plt.scatter(centers[:,0], centers[:,1], marker='*', c='g', s=200)
plt.show()
# 2c. Check for convergence
if np.all(centers == new_centers):
break
centers = new_centers
Untuk kelompok sebanyak 5, setiap iterasi pengelompokan data ditunjukkan pada gambar-gambar di bawah ini. Bintang hijau melambangkan posisi pusat dari kelompok.
Untuk kelompok sebanyak 4, berikut adalah iterasinya.
Untuk kelompok sebanyak 3, berikut adalah iterasinya.
Library scikit.cluster sudah menyediakan fungsi k-Means ini yang sudah siap digunakan. Berikut adalah perbandingan hasil fungsi k-Means yang awal dan yang berasal dari library scikit.cluster ini.
Dapat terlihat bahwa pola pengelompokan data menjadi tiga dan empat kelompok sudah sama dan juga sesuai dengan intuisi kebanyakan orang. Hal ini berbeda dengan kasus saat ada lima kelompok karena terdapat lebih dari satu cara untuk membagi data menjadi lima kelompok, setidaknya berdasarkan intuisi.
Hal yang mendasari terjadinya perbedaan pengelompokan data dalam kasus k = 5 adalah pemilihan acak pusat kelompok di awal iterasi. Perhatikan tiga hasil berikut yang didapat dengan mengubah random state untuk nilai i di fungsi find_clusters.
Pemilihan nilai k
Banyak kelompok dapat ditentukan dengan bantuan diagram Elbow. Diagram Elbow menunjukkan total kuadrat selisih setiap data dengan pusat kelompoknya untuk setiap nilai k berbeda. Nilai ini disebut juga sebagai SSE (Sum of Squared Errors). Nilai k yang baik bisa dilihat dari titik saat nilai SSE mulai melandai.
Diagram Elbow sudah disediakan dalam library Yellowbrick. Berikut adalah algoritma untuk memvisualisasikan diagram Elbow dari data yang dibahas sebelumnya.
from yellowbrick.cluster import KElbowVisualizer
model = KMeans()
visualizer = KElbowVisualizer(model)
visualizer.fit(X)
visualizer.show()
Terlihat bahwa saat k = 4, nilai SSE sudah mulai melandai setelah sebelumnya turun dengan curam. Oleh karena itu, pengelompokan data menjadi 4 kelompok merupakan pilihan yang sangat baik.
Referensi
- https://jakevdp.github.io/PythonDataScienceHandbook/05.11-k-means.html
- Boyd, Stephen; Vandenberghe, Lieven. Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares.
- https://www.scikit-yb.org/en/latest/api/cluster/elbow.html
