K-means Clustering with Excel, Python, R, and Math
K-Means clustering adalah salah satu metode clustering yang paling populer dalam analisis data. Tujuannya adalah untuk mengelompokkan data menjadi beberapa kelompok berdasarkan kemiripan karakteristiknya. Algoritma ini bekerja dengan cara menginisialisasi titik-titik pusat klaster secara acak, kemudian mengiterasi antara menetapkan setiap titik data ke klaster terdekat dan menghitung ulang pusat klaster berdasarkan rata-rata dari anggota klaster tersebut. Proses ini berlanjut hingga pusat klaster tidak berubah secara signifikan atau iterasi telah mencapai batas yang ditentukan sebelumnya.
Artikel ini akan membahas bagaimana pengaplikasian algoritma pengaplikasian k-means clustering pada excel, python, dan matematika
K-means Clustering
Langkah-langkah Algoritma:
Langkah 1: Menghitung Jumlah Cluster (K)
Langkah 2: Memilih Centroid Awal Secara Acak
Langkah 3: Menghitung Jarak Antara Titik Data dan Centroid
Formula Euclidean distance biasanya digunakan untuk mengukur jarak antara setiap titik data dan setiap centroid.
Rumus Eucledian distance untuk jarak a dan b dengan k dimension:
Rumus Manhattan distance untuk jarak a dan b dengan k dimension:
Rumus Cosine distance jika diberikan matriks data X berukuran m-by-n, yang dianggap sebagai m (1-by-n) vektor baris x1, x2, …, xm, jarak kosinus antara vektor xs dan xt didefinisikan sebagai berikut:
Rumus Correlation distance jika diberikan matriks data X berukuran m-by-n, yang dianggap sebagai m (1-by-n) vektor baris x1, x2, …, xm, jarak kosinus antara vektor xs dan xt didefinisikan sebagai berikut:
Berikut perbandingan penggunaan tiap distance calculation method
Langkah 4: Mengalokasikan Titik Data ke Centroid Terdekat
Berdasarkan jarak yang dihitung, setiap titik data dialokasikan ke cluster dengan centroid terdekat.
Langkah 5: Memperbarui Centroid
Centroid dari cluster yang baru terbentuk diperbarui dengan menghitung rata-rata dari semua titik data dalam setiap cluster.
Langkah 6: Ulangi Langkah 3–5
Proses ini diulangi sampai salah satu kriteria berhenti terpenuhi, yang meliputi konvergensi (tidak ada perubahan dalam penugasan cluster), mencapai jumlah iterasi maksimum, atau perubahan minimal dalam posisi centroid.
K-means Clustering On Math
Misal kita memiliki titik-titik klaster P1(1,3), P2(2,2), P3(5,8), P4(8,5), P5(3,9), P6(10,7), P7(3,3), P8(9,4), P9(3,7).
Pertama, kita mengambil nilai K kita sebagai 3 dan kita mengasumsikan bahwa pusat klaster awal kita adalah P7(3,3), P9(3,7), P8(9,4) sebagai C1, C2, C3. Kita akan mencari pusat-pusat baru setelah 2 iterasi untuk data-data di atas.
Langkah 1 Temukan jarak antara titik data dan Pusat Klaster. titik mana yang memiliki jarak minimum yang pindah ke pusat klaster terdekat.
Iterasi 1 Hitung jarak antara titik data dan K (C1, C2, C3)
C1P1 => (3,3)(1,3) => sqrt[(1–3)²+(3–3)²] => sqrt[4] =>2
C2P1 => (3,7)(1,3) => sqrt[(1–3)²+(3–7)²] => sqrt[20] =>4.5
C3P1 => (9,4)(1,3) => sqrt[(1–9)²+(3–4)²]=> sqrt[65] =>8.1
Untuk P2,
C1P2 => (3,3)(2,2) => sqrt[(2–3)²+(2–3)²] => sqrt[2] =>1.4
C2P2 => (3,7)(2,2) => sqrt[(2–3)²+(2–7)²] => sqrt[26] =>5.1
C3P2 => (9,4)(2,2) => sqrt[(2–9)²+(2–4)²]=> sqrt[53] =>7.3
Untuk P3,
C1P2 => (3,3)(5,8) => sqrt[(5–3)²+(8–3)²] => sqrt[29] =>5.3
C2P2 => (3,7)(5,8) => sqrt[(5–3)²+(8–7)²] => sqrt[5] =>2.2
C3P2 => (9,4)(5,8) => sqrt[(5–9)²+(8–4)²]=> sqrt[32] =>5.7
Demikian pula untuk jarak-jarak lainnya…
Cluster 1 => P1(1,3) , P2(2,2) , P7(3,3)
Cluster 2 => P3(5,8) , P5(3,9) , P9(3,7)
Cluster 3 => P4(8,5) , P6(10,7) , P8(9,4)
Sekarang, saya menghitung kembali klaster baru dan pusat klaster baru dihitung dengan mengambil rata-rata dari semua titik yang terdapat dalam klaster tersebut.
Pusat baru dari Klaster 1 => (1+2+3)/3 , (3+2+3)/3 => 2,2.7
Pusat baru dari Klaster 2 => (5+3+3)/3 , (8+9+7)/3 => 3.7,8
Pusat baru dari Klaster 3 => (8+10+9)/3 , (5+7+4)/3 => 9,5.3
Iterasi 1 telah selesai. Sekarang, mari kita ambil titik-titik pusat baru saya dan ulangi langkah-langkah yang sama, yaitu menghitung jarak antara titik data dan titik pusat baru dengan rumus Euclidean dan menemukan kelompok klaster.
Iterasi 2 Hitung jarak antara titik data dan K (C1,C2,C3)
C1(2,2.7) , C2(3.7,8) , C3(9,5.3)
C1P1 =>(2,2.7)(1,3) => sqrt[(1–2)²+(3–2.7)²] => sqrt[1.1] =>1.0
C2P1 =>(3.7,8)(1,3)=> sqrt[(1–3.7)²+(3–8)²] => sqrt[32.29] =>4.5
C3P1 =>(9,5.3)(1,3) => sqrt[(1–9)²+(3–5.3)²]=> sqrt[69.29] =>8.3
Demikian juga untuk jarak-jarak lainnya..
Klaster 1 => P1(1,3) , P2(2,2) , P7(3,3)
Klaster 2 => P3(5,8) , P5(3,9) , P9(3,7)
Klaster 3 => P4(8,5) , P6(10,7) , P8(9,4)
Pusat dari Klaster 1 => (1+2+3)/3 , (3+2+3)/3 => 2,2.7
Pusat dari Klaster 2 => (5+3+3)/3 , (8+9+7)/3 => 3.7,8
Pusat dari Klaster 3 => (8+10+9)/3 , (5+7+4)/3 => 9,5.3
Saya mendapatkan pusat yang sama dan kelompok klaster yang menunjukkan bahwa dataset ini hanya memiliki 2 kelompok. K-Means clustering menghentikan iterasi karena klaster yang sama berulang sehingga tidak perlu melanjutkan iterasi dan menampilkan iterasi terakhir sebagai kelompok klaster terbaik untuk dataset ini.
K-means Clustering On Excel
Pada contoh berikut saya menggunakan manhattan distance karena lebih mudah diinterpretasikan
K-means Clustering On Python
Implementasi pada python akan terdiri dari beberapa tahap yakni:
- Penentuan nilai K optimum
- Pemodelan dengan K means
saya akan memberikan contoh from scratch dan menggunakan library untuk pemodelan K means
Penentuan nilai K optimum
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
x = [4, 5, 10, 4, 3, 11, 14 , 6, 10, 12]
y = [21, 19, 24, 17, 16, 25, 24, 22, 21, 21]
data = list(zip(x, y))
inertias = []
for i in range(1,11):
kmeans = KMeans(n_clusters=i)
kmeans.fit(data)
inertias.append(kmeans.inertia_)
plt.plot(range(1,11), inertias, marker='o')
plt.title('Elbow method')
plt.xlabel('Number of clusters')
plt.ylabel('Inertia')
plt.show()Hasil:
dapat dilihat bahwa nilai K paling optimal adalah 2 dikarenakan menghasilkan inertia yang signifikan menurun.
Pemodelan dengan library scikit-learn
kmeans = KMeans(n_clusters=2)
kmeans.fit(data)
plt.scatter(x, y, c=kmeans.labels_)
plt.show()Hasil:
Pemodelan from scratch
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from numpy.random import uniform
from sklearn.datasets import make_blobs
import seaborn as sns
import random
def euclidean(point, data):
"""
Jarak euclidean antara titik & data.
Titik memiliki dimensi (m,), data memiliki dimensi (n,m), dan output akan memiliki ukuran (n,).
"""
return np.sqrt(np.sum((point - data)**2, axis=1))
class KMeans:
def __init__(self, n_clusters=8, max_iter=300):
self.n_clusters = n_clusters
self.max_iter = max_iter
def fit(self, X_train):
# Inisialisasi centroid, menggunakan metode "k-means++", di mana datapoint acak dipilih sebagai yang pertama,
# kemudian sisanya diinisialisasi dengan probabilitas yang sebanding dengan jarak mereka ke yang pertama
# Pilih titik acak dari data latih untuk centroid pertama
self.centroids = [random.choice(X_train)]
for _ in range(self.n_clusters-1):
# Hitung jarak dari titik ke centroid
dists = np.sum([euclidean(centroid, X_train) for centroid in self.centroids], axis=0)
# Normalisasi jarak
dists /= np.sum(dists)
# Pilih titik-titik yang tersisa berdasarkan jarak mereka
new_centroid_idx, = np.random.choice(range(len(X_train)), size=1, p=dists)
self.centroids += [X_train[new_centroid_idx]]
# Metode awal ini untuk memilih centroid secara acak kurang efektif
# min_, max_ = np.min(X_train, axis=0), np.max(X_train, axis=0)
# self.centroids = [uniform(min_, max_) for _ in range(self.n_clusters)]
# Iterasi, menyesuaikan centroid sampai konvergen atau melewati max_iter
iteration = 0
prev_centroids = None
while np.not_equal(self.centroids, prev_centroids).any() and iteration < self.max_iter:
# Urutkan setiap datapoint, mengassign ke centroid terdekat
sorted_points = [[] for _ in range(self.n_clusters)]
for x in X_train:
dists = euclidean(x, self.centroids)
centroid_idx = np.argmin(dists)
sorted_points[centroid_idx].append(x)
# Pindahkan centroid saat ini ke sebelumnya, menetapkan centroid sebagai rata-rata dari titik-titik yang termasuk ke dalamnya
prev_centroids = self.centroids
self.centroids = [np.mean(cluster, axis=0) for cluster in sorted_points]
for i, centroid in enumerate(self.centroids):
if np.isnan(centroid).any(): # Tangkap np.nan apa pun, yang dihasilkan dari sebuah centroid tidak memiliki titik
self.centroids[i] = prev_centroids[i]
iteration += 1
def evaluate(self, X):
centroids = []
centroid_idxs = []
for x in X:
dists = euclidean(x, self.centroids)
centroid_idx = np.argmin(dists)
centroids.append(self.centroids[centroid_idx])
centroid_idxs.append(centroid_idx)
return centroids, centroid_idxsContoh Pemakaian:
# Buat dataset distribusi 2D
centers = 5
X_train, true_labels = make_blobs(n_samples=100, centers=centers, random_state=42)
X_train = StandardScaler().fit_transform(X_train)
# Fit centroid ke dataset
kmeans = KMeans(n_clusters=centers)
kmeans.fit(X_train)
# Lihat hasil
class_centers, classification = kmeans.evaluate(X_train)
sns.scatterplot(x=[X[0] for X in X_train],
y=[X[1] for X in X_train],
hue=true_labels,
style=classification,
palette="deep",
legend=None
)
plt.plot([x for x, _ in kmeans.centroids],
[y for _, y in kmeans.centroids],
'k+',
markersize=10,
)
plt.show()Hasil:
K-means Clustering On R From Scratch
# Data contoh
set.seed(100)
xval <- rnorm(12, mean = rep(1:3, each = 4), sd = 0.2)
yval <- rnorm(12, mean = rep(c(1,2,1), each = 4), sd = 0.2)
# Fungsi Kmeans dengan random.seed untuk inisialisasi
kclus <- function(x, y, nclus, random.seed=123) {
set.seed(random.seed)
# mulai dengan pusat cluster acak
xcen <- runif(n = nclus, min = min(x), max = max(x))
ycen <- runif(n = nclus, min = min(y), max = max(y))
# titik data dan penugasan cluster di "data"
# koordinat cluster di "clus"
data <- data.frame(xval = x, yval = y, clus = NA)
clus <- data.frame(name = 1:nclus, xcen = xcen, ycen = ycen)
finish <- FALSE
while(finish == FALSE) {
# menetapkan cluster dengan jarak minimum ke setiap titik data
for(i in 1:length(x)) {
dist <- sqrt((x[i]-clus$xcen)^2 + (y[i]-clus$ycen)^2)
data$clus[i] <- which.min(dist)
}
xcen_old <- clus$xcen
ycen_old <- clus$ycen
# menghitung pusat cluster baru
for(i in 1:nclus) {
clus[i,2] <- mean(subset(data$xval, data$clus == i))
clus[i,3] <- mean(subset(data$yval, data$clus == i))
}
# menghentikan loop jika tidak ada perubahan dalam koordinat cluster
if(identical(xcen_old, clus$xcen) & identical(ycen_old, clus$ycen)) finish <- TRUE
}
data
}
# dengan random seed default 123, Anda seharusnya bisa mereproduksi hasilnya
# seperti yang dapat Anda lihat, dalam kasus ini, tidak ada titik data yang ditugaskan ke cluster ke-4
cluster <- kclus(xval, yval, 4)
cluster.centers <- aggregate(.~clus, cluster, mean)
ggplot(cluster, aes(xval, yval, color = as.factor(clus))) +
geom_point(size=5) +
geom_point(data=cluster.centers, aes(xval, yval, col=as.factor(clus)), pch=8, size=5)Hasil:
Kesimpulan
K-Means Clustering merupakan salah satu metode yang paling umum digunakan dalam analisis data untuk mengelompokkan data ke dalam kelompok-kelompok yang memiliki karakteristik serupa. Metode ini memulai dengan inisialisasi titik-titik pusat klaster secara acak dan terus mengiterasi untuk menetapkan setiap titik data ke klaster terdekat serta menghitung ulang pusat klaster berdasarkan rata-rata dari anggota klaster tersebut. Artikel ini membahas langkah-langkah algoritma K-Means Clustering dan memberikan contoh implementasi menggunakan Excel, Python, R, serta analisis matematis. Dalam artikel ini, kita mendapatkan pemahaman yang mendalam tentang penggunaan dan implementasi K-Means Clustering dalam berbagai platform dan bahasa pemrograman.
Lampiran
File Excel: https://drive.google.com/drive/folders/12UFVjya0JE6luQ2qVzycXZHZfHUiXkoi?usp=sharing
