Kmeans Clustering dan Implementasinya
Kmeans adalah salah satu metode clustering yang bertujuan untuk mengelompokan suatu kumpulan data menjadi beberapa kelompok. Idenya adalah dengan mengelompokkan data yang memiliki kemiripan berada dalam 1 kelompok dan memisahkan data yang berbeda kedalam kelompok yang berbeda.
Cara kerja Kmeans
Misalnya kita memiliki kumpulan data yang divisualisasikan secara linear sebagai berikut.
Langkah 1 : Tentukan jumlah cluster yang akan dibuat. Jumlah cluster adalah nilai “K” pada “K-means clustering”. Pada kasus ini mari kita tentukan jumlah K=3.
Langkah 2 : Pilih 3 titik data secara random sebagai inisial centroid cluster
Langkah 3 : Hitung jarak tiap data ke semua centroid cluster
Langkah 4 : Tetapkan data X menjadi anggota cluster yang terdekat yaitu cluster Biru
Lakukan langkah 3 dan 4 pada point lainnya
Langkah 5 : Hitung centroid (mean) dari setiap anggota cluster
Lakukan langkah 3 dan 4 hingga titik centroid cluster tidak berubah.
Apabila data yang digunakan memiliki dimensi fitur lebih dari satu, maka untuk menghitung jaraknya dapat menggunakan euclidean distance.
Bagaimana Cara Menentukan Jumlah K ?
Pada kasus tertentu, kita bingung menentukan berapa jumlah cluster yang dibutuhkan pada suatu data. Salah satu caranya adalah dengan menggunakan elbow method berdasarkan jumlah perhitungan Variation dari beberapa nilai K.
Misalnya, lakukan percobaan pada K=1 sampai K= 4.
Semakin tinggi nilai K, semakin berkurang juga Variation pada cluster tersebut.
Buat plot grafik antara Variation dengan K.
Dari grafik diatas, dapat disimpulkan bahwa nilai K = 3 dikarenakan adanya lengkungan yang cukup tajam pada titik tersebut.
Implementasi pada Python
Saya akan menggunakan dataset dari kaggle tentang Mall Customer Segmentation Data. Data tersebut memiliki attribute Pendapatan pembeli per tahun dan Spending Score. Saya akan melakukan visualisasi terhadap kedua atribut tersebut menggunakan script berikut :
Define Function
import numpy as np
from numpy.linalg import normclass Kmeans:
'''Implementing Kmeans algorithm.'''def __init__(self, n_clusters, max_iter=100, random_state=123):
self.n_clusters = n_clusters
self.max_iter = max_iter
self.random_state = random_statedef initializ_centroids(self, X):
np.random.RandomState(self.random_state)
random_idx = np.random.permutation(X.shape[0])
centroids = X[random_idx[:self.n_clusters]]
return centroidsdef compute_centroids(self, X, labels):
centroids = np.zeros((self.n_clusters, X.shape[1]))
for k in range(self.n_clusters):
centroids[k, :] = np.mean(X[labels == k, :], axis=0)
return centroidsdef compute_distance(self, X, centroids):
distance = np.zeros((X.shape[0], self.n_clusters))
for k in range(self.n_clusters):
row_norm = norm(X - centroids[k, :], axis=1)
distance[:, k] = np.square(row_norm)
return distancedef find_closest_cluster(self, distance):
return np.argmin(distance, axis=1)def compute_sse(self, X, labels, centroids):
distance = np.zeros(X.shape[0])
for k in range(self.n_clusters):
distance[labels == k] = norm(X[labels == k] - centroids[k], axis=1)
return np.sum(np.square(distance))
def fit(self, X):
self.centroids = self.initializ_centroids(X)
for i in range(self.max_iter):
old_centroids = self.centroids
distance = self.compute_distance(X, old_centroids)
self.labels = self.find_closest_cluster(distance)
self.centroids = self.compute_centroids(X, self.labels)
if np.all(old_centroids == self.centroids):
break
self.error = self.compute_sse(X, self.labels, self.centroids)
def predict(self, X):
distance = self.compute_distance(X, old_centroids)
return self.find_closest_cluster(distance)
Data Visualization
# Modules
import matplotlib.pyplot as plt
from matplotlib.image import imread
import pandas as pd
import seaborn as sns
from sklearn.datasets.samples_generator import (make_blobs,
make_circles,
make_moons)
from sklearn.cluster import KMeans, SpectralClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_samples, silhouette_score%matplotlib inline
sns.set_context('notebook')
plt.style.use('fivethirtyeight')
from warnings import filterwarnings
filterwarnings('ignore')# Import the data
df = pd.read_csv('Mall_Customers.csv')
df = df[['Annual Income (k$)','Spending Score (1-100)']]# Plot the data
plt.figure(figsize=(6, 6))
plt.scatter(df.iloc[:, 0], df.iloc[:, 1])
plt.xlabel('Annual Income')
plt.ylabel('Spending Score')
plt.title('Visualization of raw data');
Dari hasil visualisasi diatas, kemungkinan kita akan bingung untuk menentukan berapa jumlah K yang cocok untuk data tersebut. Maka dari itu, saya akan melakukan elbow analysis untuk menentukan jumlah K yang sesuai menggunakan script berkut :
Elbow Analysis
# Run the Kmeans algorithm and get the index of data points clusters
sse = []
list_k = list(range(1, 10))# Turn dataframe into list
list_data = np.array(df.values.tolist())for k in list_k:
km = KMeans(n_clusters=k,max_iter=100)
km.fit(list_data)
sse.append(km.inertia_)# Plot sse against k
plt.figure(figsize=(6, 6))
plt.plot(list_k, sse, '-o')
plt.xlabel(r'Number of clusters (K)')
plt.ylabel('Sum of squared distance');
Berdasarkan grafik diatas, dapat dilihat pada titik 5 terjadi lengkungan yang cukup tajam. Sehingga dapat di ambil kesimpulan bahwa K=5 merupakan nilai yang optimal.
Clustering dengan K=5 menggunakan script berikut :
Kmeans Clustering
# Run local implementation of kmeans
km = Kmeans(n_clusters=5, max_iter=200)
km.fit(list_data)
centroids = km.centroids# Plot the clustered data
fig, ax = plt.subplots(figsize=(6, 6))
plt.scatter(list_data[km.labels == 0, 0], list_data[km.labels == 0, 1],
c='green', label='cluster 1')
plt.scatter(list_data[km.labels == 1, 0], list_data[km.labels == 1, 1],
c='blue', label='cluster 2')
plt.scatter(list_data[km.labels == 2, 0], list_data[km.labels == 2, 1],
c='red', label='cluster 3')
plt.scatter(list_data[km.labels == 3, 0], list_data[km.labels == 3, 1],
c='yellow', label='cluster 4')
plt.scatter(list_data[km.labels == 4, 0], list_data[km.labels == 4, 1],
c='magenta', label='cluster 5')
plt.scatter(centroids[:, 0], centroids[:, 1], marker='*', s=300,
c='r', label='centroid')
plt.legend()
# plt.xlim([-2, 2])
# plt.ylim([-2, 2])
plt.xlabel('Annual Income')
plt.ylabel('Spending Score')
plt.title('Visualization of clustered data', fontweight='bold')
ax.set_aspect('equal');
Dari plot di atas terlihat 5 buah cluster data yang dapat di interpretasikan sebagai berikut :
- Cluster Ungu : Pendapatan rendah tapi banyak belanja.
- Cluster Hijau : Pendapatan rendah dan sedikit belanja.
- Cluster Kuning : Pendapatan sedang dan belanja sedang.
- Cluster Merah : Pendapatan tinggi dan banyak belanja.
- Cluster Biru : Pendapatan tinggi tapi sedikit belanja.
Kesimpulan
Kmeans merupakan algoritma yang cukup populer. Algoritma ini sangat bagus dalam melakukan clustering pada data yang memiliki bentuk spherical. Tetapi, kita harus melakukan inisialisasi pada jumlah cluster. Hal tersebut dapat diatasi dengan menggunakan metode elbow analysis untuk menentukan jumlah K yang paling optimal.
