Membagi dua k-means adalah pendekatan gabungan antara Pengelompokan Hierarki Divisif (pengelompokan top-down) dan Pengelompokan K-means. Alih-alih mempartisi kumpulan data menjadi K cluster di setiap iterasi, algoritma membagi dua k-means membagi satu cluster menjadi dua sub cluster pada setiap langkah membagi dua (dengan menggunakan k-means) hingga diperoleh k cluster.
Pengelompokan Hirarki yang Memecah belah
Clustering Divisive dimulai dari tingkat atas dengan satu cluster dan membaginya ke tingkat bawah. Untuk memutuskan kelompok mana yang harus dipecah, diperlukan ukuran ketidaksamaan antar kumpulan observasi. Hal ini dicapai dengan menggunakan ukuran jarak antar pasangan observasi.
Cara Kerja Membagi Dua K-means
- Atur K untuk menentukan jumlah cluster
- Tetapkan semua data sebagai satu cluster
3. Gunakan K-means dengan K=2 untuk membagi cluster
4. Ukur jarak tiap intra cluster.
- Jumlah Jarak kuadrat
5. Pilih cluster yang memiliki jarak terbesar dan bagi menjadi 2 cluster menggunakan K-means.
6. Ulangi langkah 3–5 hingga jumlah tandan daun = K.
Cluster terakhir adalah cluster [C,D,E,F]
Penerapan
Tentukan Fungsi
"""Implementation of k-means clustering algorithm.
These functions are designed to work with cartesian data points
"""
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
def convert_to_2d_array(points):
"""
Converts `points` to a 2-D numpy array.
"""
points = np.array(points)
if len(points.shape) == 1:
points = np.expand_dims(points, -1)
return points
def visualize_clusters(clusters):
"""
Visualizes the first 2 dimensions of the data as a 2-D scatter plot.
"""
plt.figure()
for cluster in clusters:
points = convert_to_2d_array(cluster)
if points.shape[1] < 2:
points = np.hstack([points, np.zeros_like(points)])
plt.plot(points[:,0], points[:,1], 'o')
plt.show()
def SSE(points):
"""
Calculates the sum of squared errors for the given list of data points.
"""
points = convert_to_2d_array(points)
centroid = np.mean(points, 0)
errors = np.linalg.norm(points-centroid, ord=2, axis=1)
return np.sum(errors)
def kmeans(points, k=2, epochs=10, max_iter=100, verbose=False):
"""
Clusters the list of points into `k` clusters using k-means clustering
algorithm.
"""
points = convert_to_2d_array(points)
assert len(points) >= k, "Number of data points can't be less than k"
best_sse = np.inf
for ep in range(epochs):
# Randomly initialize k centroids
np.random.shuffle(points)
centroids = points[0:k, :]
last_sse = np.inf
for it in range(max_iter):
# Cluster assignment
clusters = [None] * k
for p in points:
index = np.argmin(np.linalg.norm(centroids-p, 2, 1))
if clusters[index] is None:
clusters[index] = np.expand_dims(p, 0)
else:
clusters[index] = np.vstack((clusters[index], p))
# Centroid update
centroids = [np.mean(c, 0) for c in clusters]
# SSE calculation
sse = np.sum([SSE(c) for c in clusters])
gain = last_sse - sse
if verbose:
print((f'Epoch: {ep:3d}, Iter: {it:4d}, '
f'SSE: {sse:12.4f}, Gain: {gain:12.4f}'))
# Check for improvement
if sse < best_sse:
best_clusters, best_sse = clusters, sse
# Epoch termination condition
if np.isclose(gain, 0, atol=0.00001):
break
last_sse = sse
return best_clusters
def bisecting_kmeans(points, k=2, epochs=10, max_iter=100, verbose=False):
"""
Clusters the list of points into `k` clusters using bisecting k-means
clustering algorithm. Internally, it uses the standard k-means with k=2 in
each iteration.
"""
points = convert_to_2d_array(points)
clusters = [points]
while len(clusters) < k:
max_sse_i = np.argmax([SSE(c) for c in clusters])
cluster = clusters.pop(max_sse_i)
two_clusters = kmeans(
cluster, k=2, epochs=epochs, max_iter=max_iter, verbose=verbose)
clusters.extend(two_clusters)
return clusters
Kode Utama
# Import the data
df = pd.read_csv('Mall_Customers.csv')
df = df[['Annual Income (k$)','Spending Score (1-100)']]
points = np.array(df.values.tolist())
# algorithm = kmeans
algorithm = bisecting_kmeans
k = 5
verbose = False
max_iter = 1000
epochs = 10
clusters = algorithm(
points=points, k=k, verbose=verbose, max_iter=max_iter, epochs=epochs)
visualize_clusters(clusters)
Keuntungan Menggunakan B-Kmeans dibandingkan Kmeans
- Membagi dua k-means akan lebih efisien jika K besar.
Untuk algoritma kmeans, komputasi melibatkan setiap titik data dari kumpulan data dan k centroid. Di sisi lain, dalam setiap langkah Bisecting k-means, hanya titik data dari satu cluster dan dua centroid yang terlibat dalam komputasi. Dengan demikian, waktu komputasi berkurang. - Membagi dua k-means menghasilkan cluster dengan ukuran yang sama, sedangkan k-means diketahui menghasilkan cluster dengan ukuran yang sangat berbeda.
