การแบ่งครึ่งเคมีนเป็นวิธีการแบบผสมระหว่างการแบ่งกลุ่มแบบลำดับชั้นแบบแยก (การจัดกลุ่มจากบนลงล่าง) และการจัดกลุ่มแบบเคมีนแบบแยกส่วน แทนที่จะแบ่งพาร์ติชันชุดข้อมูลออกเป็น K คลัสเตอร์ในการวนซ้ำแต่ละครั้ง การแบ่งอัลกอริทึม k-mean จะแบ่งคลัสเตอร์หนึ่งคลัสเตอร์ออกเป็นสองคลัสเตอร์ย่อยในแต่ละขั้นตอนการแบ่งครึ่ง (โดยใช้ k-mean) จนกระทั่งได้ k คลัสเตอร์
การจัดกลุ่มแบบลำดับชั้นแบบแบ่งแยก
Divisive Clustering เริ่มต้นที่ระดับบนสุดด้วยคลัสเตอร์เดียวและแบ่งไปยังระดับล่างสุด ในการตัดสินใจว่าควรแยกกลุ่มใด จำเป็นต้องมีการวัดความแตกต่างระหว่างชุดการสังเกต ซึ่งทำได้โดยใช้การวัดระยะห่างระหว่างคู่การสังเกต
การแบ่งแยก K-mean ทำงานอย่างไร
- ตั้งค่า K เพื่อกำหนดจำนวนคลัสเตอร์
- ตั้งค่าข้อมูลทั้งหมดเป็นคลัสเตอร์เดียว
3. ใช้ K-means กับ K=2 เพื่อแยกคลัสเตอร์
4. วัดระยะทางของแต่ละคลัสเตอร์ภายใน
- ผลรวมของระยะทางกำลังสอง
5. เลือกคลัสเตอร์ที่มีระยะทางมากที่สุดและแบ่งออกเป็น 2 คลัสเตอร์โดยใช้ K-means
6. ทำซ้ำขั้นตอนที่ 3–5 จนกระทั่งจำนวนคลัสเตอร์ใบไม้ = K
คลัสเตอร์สุดท้ายคือคลัสเตอร์ [C,D,E,F]
การนำไปปฏิบัติ
กำหนดฟังก์ชัน
"""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
รหัสหลัก
# 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)
ข้อดีของการใช้ B-Kmeans มากกว่า Kmeans
- การแบ่งครึ่งเคมีนจะมีประสิทธิภาพมากกว่าเมื่อ Kมีขนาดใหญ่
สำหรับอัลกอริทึม kmeans การคำนวณจะเกี่ยวข้องกับทุกจุดข้อมูลของชุดข้อมูลและ k centroid ในทางกลับกัน ในแต่ละขั้นตอนการแบ่งครึ่งของการแบ่งครึ่ง k-means มีเพียงจุดข้อมูลของคลัสเตอร์หนึ่งคลัสเตอร์และเซนทรอยด์สองจุดเท่านั้นที่เกี่ยวข้องในการคำนวณ ดังนั้นเวลาในการคำนวณจึงลดลง - การแยกเคมีนออกเป็นสองส่วนทำให้เกิดกลุ่มที่มีขนาดใกล้เคียงกัน ในขณะที่เคมีนเป็นที่รู้จักกันว่าสร้างกลุ่มที่มีขนาดแตกต่างกันอย่างมาก