Hướng dẫn k-means clustering python - k-nghĩa là phân cụm trăn
|
Bài viết này trình bày một minh họa về phân cụm K-mean trên một dữ liệu ngẫu nhiên mẫu sử dụng thư viện cv mở. Show Điều kiện tiên quyết: Numpy, OpenCV, matplot-lib Đầu tiên chúng ta hãy trực quan hóa dữ liệu thử nghiệm với Nhiều tính năng bằng công cụ matplot-lib. Ở đây ‘Z’ là một mảng có kích thước 100 và các giá trị nằm trong khoảng từ 0 đến 255. Bây giờ, hãy định hình lại ‘z’ thành một vectơ cột. Nó sẽ hữu ích hơn khi có nhiều hơn một tính năng. Sau đó thay đổi dữ liệu thành kiểu np.float32. Đầu ra:  Bây giờ, hãy áp dụng thuật toán phân cụm k-Means vào ví dụ tương tự như trong dữ liệu thử nghiệm ở trên và xem hành vi của nó. 1. Các bước liên quan:1) Đầu tiên chúng ta cần thiết lập một dữ liệu thử nghiệm. 2) Xác định tiêu chí và áp dụng kmeans (). 3) Bây giờ tách dữ liệu. 4) Cuối cùng Vẽ sơ đồ dữ liệu. Output Ví dụ này nhằm minh họa nơi k-mean sẽ tạo ra các cụm có thể có trực quan. Các ứng dụng: 1) Xác định Dữ liệu Ung thư. 2) Dự đoán Kết quả Học tập của Học sinh. 3) Dự đoán Hoạt động Ma túy. Cài ứng dụng cafedev để dễ dàng cập nhật tin và học lập trình mọi lúc mọi nơi tại đây.mọi lúc mọi nơi tại đây. Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng! Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!Trong thuật toán k-Means mỗi cụm dữ liệu được đặc trưng bởi một tâm (centroid). tâm là điểm đại diện nhất cho một cụm và có giá trị bằng trung bình của toàn bộ các quan sát nằm trong cụm. Chúng ta sẽ dựa vào khoảng cách từ mỗi quan sát tới các tâm để xác định nhãn cho chúng trùng thuộc về tâm gần nhất. Ban đầu thuật toán sẽ khởi tạo ngẫu nhiên một số lượng xác định trước tâm cụm. Sau đó tiến hành xác định nhãn cho từng điểm dữ liệu và tiếp tục cập nhật lại tâm cụm. Thuật toán sẽ dừng cho tới khi toàn bộ các điểm dữ liệu được phân về đúng cụm hoặc số lượt cập nhật tâm chạm ngưỡng. Cụ thể các bước của thuật toán k-Means được tóm tắt như sau: 1.- Khởi tạo ngẫu nhiên \(k\) tâm cụm \(\mu_1, \mu_2, \dots, \mu_k\).\(k\) tâm cụm \(\mu_1, \mu_2, \dots, \mu_k\). 2.- Lặp lại quá trình cập nhật tâm cụm cho tới khi dừng: a. Xác định nhãn cho từng điểm dữ liệu \(c_i\) dựa vào khoảng cách tới từng tâm cụm:\(c_i\) dựa vào khoảng cách tới từng tâm cụm: \[c_i = \arg \min_{j} \|\mathbf{x}_i - \mu_j \|_2^2\] b. Tính toán lại tâm cho từng cụm theo trung bình của toàn bộ các điểm dữ liệu trong một cụm: \[\mu_j := \frac{\sum_{i=1}^{n} \mathbf{1}(c_i = j) \mathbf{x}_i}{\sum_{i=1}^{n} \mathbf{1}(c_i = j)}\] Trong công thức 2.a thì \(\|\mathbf{x}\|_2^2\) là bình phương của norm chuẩn bậc 2, kí hiệu là \(L_2\), norm chuẩn bậc 2 là một độ đo khoảng cách thường được sử dụng trong machine learning.\(\|\mathbf{x}\|_2^2\) là bình phương của norm chuẩn bậc 2, kí hiệu là \(L_2\), norm chuẩn bậc 2 là một độ đo khoảng cách thường được sử dụng trong machine learning. Trong công thức 2.b chúng ta sử dụng hàm \(\mathbf{1}(.)\), hàm này có giá trị trả về là 1 nếu nhãn của điểm dữ liệu \(c_i\) được dự báo thuộc về cụm \(j\), trái lại thì trả về giá trị 0. Như vậy tử số của vế phải trong công thức 2.b chính là tổng khoảng cách của toàn bộ các điểm dữ liệu nằm trong cụm \(j\) trong khi mẫu số chính là số lượng các điểm dữ liệu thuộc cụm \(j\). \(\mu_j\) chính là vị trí của tâm cụm \(j\) mà ta dự báo tại thời điểm hiện tại. Trong thuật toán trên thì tham số mà chúng ta cần lựa chọn chính là số lượng cụm \(k\). Thời điểm ban đầu ta sẽ khởi tạo \(k\) điểm dữ liệu một cách ngẫu nhiên và sau đó gán các tâm bằng giá trị của \(k\) điểm dữ liệu này. Các bước trong vòng lặp ở bước 2 thực chất là:\(\mathbf{1}(.)\), hàm này có giá trị trả về là 1 nếu nhãn của điểm dữ liệu \(c_i\) được dự báo thuộc về cụm \(j\), trái lại thì trả về giá trị 0. Như vậy tử số của vế phải trong công thức 2.b chính là tổng khoảng cách của toàn bộ các điểm dữ liệu nằm trong cụm \(j\) trong khi mẫu số chính là số lượng các điểm dữ liệu thuộc cụm \(j\). \(\mu_j\) chính là vị trí của tâm cụm \(j\) mà ta dự báo tại thời điểm hiện tại. Trong thuật toán trên thì tham số mà chúng ta cần lựa chọn chính là số lượng cụm \(k\). Thời điểm ban đầu ta sẽ khởi tạo \(k\) điểm dữ liệu một cách ngẫu nhiên và sau đó gán các tâm bằng giá trị của \(k\) điểm dữ liệu này. Các bước trong vòng lặp ở bước 2 thực chất là: a. Gán nhãn cho mỗi điểm dữ liệu bằng với nhãn của tâm cụm gần nhất. b. Dịch chuyển dần dần tâm cụm \(\mu_j\) tới trung bình của những điểm dữ liệu mà được phân về \(j\).\(\mu_j\) tới trung bình của những điểm dữ liệu mà được phân về \(j\). Bên dưới ta sẽ xây dựng một class import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)0 có tác dụng kiểm tra điều kiện dừng của vòng lặp. Ở đây chúng ta sẽ dừng khi số lượng vòng lặp vượt quá import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)1 hoặc các centroids ngừng thay đổi. import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids) dataset, _ = make_blobs(n_samples=250, cluster_std=3.0, random_state=123) kmean = KMeans(k=2, max_iteration=8) centroids = kmean.fit(dataset) import matplotlib.pyplot as plt from matplotlib.gridspec import GridSpec gs = GridSpec(nrows=3, ncols=3) plt.figure(figsize = (20, 20)) plt.subplots_adjust(wspace=0.2,hspace=0.4) colors = ['green', 'blue'] labels = ['cluster 1', 'cluster 2'] for i in np.arange(len(kmean.all_centroids)): ax = plt.subplot(gs[i]) if i == 0: centroids_i = kmean.all_centroids[i] plt.scatter(dataset[:, 0], dataset[:, 1], s=50, alpha=0.5, color='red') for j in np.arange(kmean.k): plt.scatter(centroids_i[j, 0], centroids_i[j, 1], marker='x', s=100, color='red') plt.title('All points in original dataset') else: # Lấy centroids và labels tại bước thứ i centroids_i = kmean.all_centroids[i] labels_i = kmean.all_labels[i] # Visualize các điểm cho từng cụm for j in np.arange(kmean.k): idx_j = np.where(np.array(labels_i) == j)[0] plt.scatter(dataset[idx_j, 0], dataset[idx_j, 1], color=colors[j], label=labels[j], s=50, alpha=0.3, lw = 0) plt.scatter(centroids_i[j, 0], centroids_i[j, 1], marker='x', color=colors[j], s=100, label=labels[j]) plt.title(r'iteration {}'.format(i)) Hình 1: Sự dịch chuyển tâm của cụm sau mỗi vòng lặp. Thời điểm ban đầu hai tâm cụm được khởi tạo một cách ngẫu nhiên. Sau đó sau mỗi vòng lặp thì các nhãn được cập nhật lại tuỳ theo vị trí của chúng đối với tâm cụm. Tiếp tục cập nhật lại tâm cụm theo các nhãn dữ liệu mới. Cuối cùng thì thuật toán sẽ hội tụ khi tâm cụm ngừng thay đổi vị trí. Sự dịch chuyển tâm của cụm sau mỗi vòng lặp. Thời điểm ban đầu hai tâm cụm được khởi tạo một cách ngẫu nhiên. Sau đó sau mỗi vòng lặp thì các nhãn được cập nhật lại tuỳ theo vị trí của chúng đối với tâm cụm. Tiếp tục cập nhật lại tâm cụm theo các nhãn dữ liệu mới. Cuối cùng thì thuật toán sẽ hội tụ khi tâm cụm ngừng thay đổi vị trí. Trên sklearn chúng ta có thể dễ dàng huấn luyện thuật toán k-Means thông qua class import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)2 của import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)3 from sklearn.cluster import KMeans kmeans = KMeans(n_clusters=2, random_state=0) kmeans.fit(dataset) print('kmeans labels of 5 observation: ', kmeans.labels_[:5]) print('kmeans centroids: \n', kmeans.cluster_centers_) kmeans labels of 5 observation: [0 0 0 1 0] kmeans centroids: [[ 4.58876493 -3.13006162] [-4.99023469 0.44409831]] Dự báo cụm cho một quan sát mới: x = np.array([[5, 1]]) kmeans.predict(x) 13.2. Sự hội tụ của thuật toán k-Means clustering¶Liệu rằng thuật toán k-Means luôn hội tụ? Điều này là hợp lý, chúng ta sẽ chứng minh thông qua xét một hàm biến dạng (distortion function) dạng MSE: \[\mathcal{L}(\mathbf{c}, \mu) = \sum_{i=1}^{n} \sum_{j=1}^{k} \|\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_{j} \|_2^2\] Trong đó \(\mathbf{c}=(c_1, c_2, \dots, c_n)\) là véc tơ nhãn của toàn bộ các quan sát được dữ báo từ thuật toán phân cụm. \(\mathbf{1}(c_i=j)\mu_j\) chính là tâm cụm mà quan sát \(\mathbf{x}_i\) được phân bổ về. Như vậy hàm biến dạng thực tế là đo lường khoảng cách từ toàn bộ các điểm dữ liệu đến các tâm cụm. Theo như bước 2 trong qui trình của thuật toán k-Means thì đầu tiên tại bước 2.a chúng ta sẽ tính khoảng cách từ một điểm dữ liệu đến toàn bộ các tâm cụm nhằm cập nhật lại nhãn. Như vậy giá trị \(\|\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_{j} \|_2^2\) luôn giảm sau bước này. Tiếp theo sang bước thứ 2.b chúng ta cập nhật lại tâm cụm sao cho khoảng cách của chúng tới các điểm trong dữ liệu là nhỏ nhất. Vị trí này là nghiệm của phương trình đạo hàm bậc nhất:\(\mathbf{c}=(c_1, c_2, \dots, c_n)\) là véc tơ nhãn của toàn bộ các quan sát được dữ báo từ thuật toán phân cụm. \(\mathbf{1}(c_i=j)\mu_j\) chính là tâm cụm mà quan sát \(\mathbf{x}_i\) được phân bổ về. Như vậy hàm biến dạng thực tế là đo lường khoảng cách từ toàn bộ các điểm dữ liệu đến các tâm cụm. Theo như bước 2 trong qui trình của thuật toán k-Means thì đầu tiên tại bước 2.a chúng ta sẽ tính khoảng cách từ một điểm dữ liệu đến toàn bộ các tâm cụm nhằm cập nhật lại nhãn. Như vậy giá trị \(\|\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_{j} \|_2^2\) luôn giảm sau bước này. Tiếp theo sang bước thứ 2.b chúng ta cập nhật lại tâm cụm sao cho khoảng cách của chúng tới các điểm trong dữ liệu là nhỏ nhất. Vị trí này là nghiệm của phương trình đạo hàm bậc nhất: \[\begin{split}\begin{eqnarray}\frac{\delta \mathcal{L}(\mathbf{c}, \mu)}{\delta \mu_j} & = & \sum_{i=1}^{n} \sum_{j=1}^{k} \frac{\delta ~ \|\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_j \|_2^2}{\delta \mu_j} \\ & = & \sum_{i=1}^{n} \sum_{j=1}^{k} \frac{\delta ~ [\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_j]^{\intercal} [\mathbf{x}_i-\mathbf{1}(c_i=j)\mu_j]}{\delta \mu_j} \\ & = & \sum_{i=1}^{n} \sum_{j=1}^{k}-\mathbf{1}(c_i = j) [\mathbf{x}_i - \underbrace{\mathbf{1}(c_i=j)}_{1} \mu_j] \\ & = & \sum_{i=1}^{n} \sum_{j=1}^{k}-\mathbf{1}(c_i = j) [\mathbf{x}_i - \mu_j] \end{eqnarray}\end{split}\] Dòng thứ 2 suy ra dòng thứ 3 là theo công thức đạo hàm của \(\| \mathbf{x} - \mathbf{w}\|_2^2\).\(\| \mathbf{x} - \mathbf{w}\|_2^2\). Dòng thứ 3 suy ra dòng thứ 4 là vì khi nhãn \(c_i = j\) thì \(\mathbf{1}(c_i=j) = 1\). Trường hợp nhãn \(c_i \neq j\) thì là khoảng cách được gán về 0 và không ảnh hưởng tới tới hàm biến dạng.\(c_i = j\) thì \(\mathbf{1}(c_i=j) = 1\). Trường hợp nhãn \(c_i \neq j\) thì là khoảng cách được gán về 0 và không ảnh hưởng tới tới hàm biến dạng. Như vậy đạo hàm bậc nhất bằng 0 khi: \[\begin{split}\begin{eqnarray}\sum_{i=1}^{n} \sum_{j=1}^{k}-\mathbf{1}(c_i = j) [\mathbf{x}_i - \mu_j^*] & = & 0 \\ \leftrightarrow \mu_j^* & = & \frac{\sum_{i=1}^{n} \mathbf{1}(c_i = j) \mathbf{x}_i}{\sum_{i=1}^{n} \mathbf{1}(c_i = j)} \end{eqnarray}\end{split}\] Như vậy khi tâm cụm là trung bình của toàn bộ các quan sát được phân về cụm thì tổng khoảng cách giữa các quan sát tới thâm cụm mà nó thuộc về là nhỏ nhất. Điều đó có nghĩa là hàm biến dạng luôn giảm sau mỗi vòng lặp. Mặt khác hàm biến dạng bị chặn dưới bởi 0 nên là một chuỗi hội tụ. Tức là sau một hữu hạn bước thì thuật toán k-Means sẽ dừng. 13.3. Phương pháp Elbow trong lựa chọn số cụm¶Trong thuật toán k-Means thì chúng ta cần phải xác định trước số cụm. Câu hỏi đặt ra là đâu là số lượng cụm cần phân chia tốt nhất đối với một bộ dữ liệu cụ thể? Phương pháp Elbow là một cách giúp ta lựa chọn được số lượng các cụm phù hợp dựa vào đồ thị trực quan hoá bằng cách nhìn vào sự suy giảm của hàm biến dạng và lựa chọn ra điểm khuỷ tay (elbow point). Để tìm hiểu phương pháp Elbow, bên dưới chúng ta cùng thử nghiệm vẽ biểu đồ hàm biến dạng bằng cách điều chỉnh số lượng cụm của thuật toán k-Means. from scipy.spatial.distance import cdist losses = [] K = 10 for i in range(1, K): # 1. Huấn luyện với số cụm = i kmeans_i = KMeans(n_clusters=i, random_state=0) kmeans_i.fit(dataset) # 2. Tính _hàm biến dạng_ # 2.1. Khoảng cách tới toàn bộ centroids d2centroids = cdist(dataset, kmeans_i.cluster_centers_, 'euclidean') # shape (n, k) # 2.2. Khoảng cách tới centroid gần nhất min_distance = np.min(d2centroids, axis=1) # shape (n) loss = np.sum(min_distance) losses.append(loss) Vẽ biểu đồ hàm biến dạng plt.figure(figsize=(12, 8)) plt.plot(np.arange(1, K), losses, 'bx-') plt.xlabel('Values of K') plt.ylabel('Distortion') plt.title('The Elbow Method using Distortion') plt.show() Hình 2: Đồ thị hàm biến dạng của thuật toán k-Means. Trục tung là giá trị của hàm biến dạng và trục hoành là giá trị của số lượng cụm cần phân chia trong thuật toán k-Means. Đồ thị hàm biến dạng của thuật toán k-Means. Trục tung là giá trị của hàm biến dạng và trục hoành là giá trị của số lượng cụm cần phân chia trong thuật toán k-Means. Điểm khuỷ tay là điểm mà ở đó tốc độ suy giảm của hàm biến dạng sẽ thay đổi nhiều nhất. Tức là kể từ sau vị trí này thì gia tăng thêm số lượng cụm cũng không giúp hàm biến dạng giảm đáng kể. Nếu thuật toán phân chia theo số lượng cụm tại vị trí này sẽ đạt được tính chất phân cụm một cách tổng quát nhất mà không gặp các hiện tượng vị khớp (overfitting). Trong hình trên thì ta thấy vị trí của điểm khuỷ tay chính là \(k=2\) vì khi số lượng cụm lớn hơn \(2\) thì tốc độ suy giảm của hàm biến dạng dường như không đáng kể so với trước đó.\(k=2\) vì khi số lượng cụm lớn hơn \(2\) thì tốc độ suy giảm của hàm biến dạng dường như không đáng kể so với trước đó. Phương pháp Elbow là một phương pháp thường được sử dụng để lựa chọn số lượng cụm phân chia hợp lý dựa trên biểu đồ, tuy nhiên có một số trường hợp chúng ta sẽ không dễ dàng phát hiện vị trí của Elbow, đặc biệt là đối với những bộ dữ liệu mà qui luật phân cụm không thực sự dễ dàng được phát hiện. Nhưng nhìn chung thì phương pháp Elbow vẫn là một phương pháp tốt nhất được ứng dụng trong việc tìm kiếm số lượng cụm cần phân chia. 13.4. Biểu diễn dữ liệu đa chiều trên đồ thị¶Sau khi huấn luyện thuật toán k-Means chúng ta sẽ cần kiểm tra qui luật phân cụm xem chúng đã thực sự hợp lý? Điều này sẽ được thực hiện thông qua biểu đồ phân cụm. Đối với các bộ dữ liệu hai chiều và ba chiều chúng ta có thể dễ dàng biểu diễn chúng trên mặt phẳng hoặc siêu phẳng. Nhưng đối với các bộ dữ liệu nhiều hơn ba chiều thì chúng ta cần áp dụng các phương pháp giảm chiều dữ liệu trước khi đồ thị hoá. Giảm chiều dữ liệu là phương pháp giúp biến đổi các bộ dữ liệu cao chiều (high dimensional) về các bộ dữ liệu thấp chiều (low dimensional) mà vẫn giữ được nhiều nhất thông tin từ bộ dữ liệu gốc. Về các phương pháp giảm chiều dữ liệu sẽ được giới thiệu ở một bài khác. Trong chương này chúng ta sẽ học cách ứng dụng thuật toán t-SNE để giảm chiều dữ liệu về hai chiều và biểu diễn qui luật các cụm trong không gian hai chiều. Đầu tiên chúng ta sẽ huấn luyện một mô hình k-Means với 2 cụm trên bộ dữ liệu 3 chiều. Để huấn luyện mô hình import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)4 trên sklearn chúng ta sử dụng class TSNE. Chúng ta cần khai báo số lượng chiều dữ liệu sau khi giảm thông qua đối số import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)5 như sau: Hàm import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)6 có tác dụng vừa huấn luyện vừa biến đổi dữ liệu, kết quả trả ra là bộ dữ liệu được giảm chiều import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)7. Thông thường đối với các bộ dữ liệu kích thước lớn thì thuật toán t-SNE tốn khá nhiều thời gian để huấn luyện, chúng ta có thể in ra tổng thời gian huấn luyện để ước tính chi phí thời gian. Tiếp theo ta biều đồ hoá các cụm bằng biểu đồ scatter. Hình 3: Biểu diễn của các cụm trên không gian 2D bằng phương pháp giảm chiều dữ liệu t-SNE. Biểu diễn của các cụm trên không gian 2D bằng phương pháp giảm chiều dữ liệu t-SNE. Như vậy chúng ta nhận thấy rằng phép chiếu trên không gian hai chiều cho thấy thông tin cụm được bảo toàn và giữa các cụm có ranh giới rõ ràng. Bạn có đọc có thể áp dụng hàm import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)8 ở trên để visualize cho những bộ dữ liệu khác trên không gian hai chiều. Các thông tin cần truyền vào hàm là dữ liệu sau giảm chiều import numpy as np from sklearn.datasets import make_blobs class KMeans(): def __init__(self, k, max_iteration=10): self.k = k self.max_iteration = max_iteration self.all_centroids = [] self.all_labels = [] # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm def fit(self, dataSet): # Khởi tạo ngẫu nhiên k centroids numFeatures = dataSet.shape[1] centroids = self.get_random_centroids(numFeatures, self.k) self.all_centroids.append(centroids) self.all_labels.append(None) # Khởi tạo các biến iterations, oldCentroids iterations = 0 oldCentroids = None # Vòng lặp cập nhật centroids trong thuật toán k-Means while not self.should_stop(oldCentroids, centroids, iterations): # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ oldCentroids = centroids iterations += 1 # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids labels = self.get_labels(dataSet, centroids) self.all_labels.append(labels) # Cập nhật centroids dựa vào nhãn dữ liệu # print('0ld centroids: ', centroids) centroids = self.get_centroids(dataSet, labels, self.k) # print('new centroids: ', centroids) self.all_centroids.append(centroids) return centroids # Hàm khởi tạo centroids ngẫu nhiên def get_random_centroids(self, numFeatures, k): return np.random.rand(k, numFeatures) # return np.array([[-5., -5.], # [4., 6.]]) # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets def get_labels(self, dataSet, centroids): # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu. labels = [] for x in dataSet: # Tính khoảng cách tới các centroids và cập nhận nhãn distances = np.sum((x-centroids)**2, axis=1) label = np.argmin(distances) labels.append(label) return labels # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi def should_stop(self, oldCentroids, centroids, iterations): if iterations > self.max_iteration: return True return np.all(oldCentroids == centroids) # Trả về toan độ mới cho k centroids của mỗi chiều. def get_centroids(self, dataSet, labels, k): centroids = [] for j in np.arange(k): # Lấy index cho mỗi centroids idx_j = np.where(np.array(labels) == j)[0] centroid_j = dataSet[idx_j, :].mean(axis=0) centroids.append(centroid_j) return np.array(centroids)7 và nhãn dự báo dataset, _ = make_blobs(n_samples=250, cluster_std=3.0, random_state=123) kmean = KMeans(k=2, max_iteration=8) centroids = kmean.fit(dataset)0. 13.5. Hạn chế của k-Means¶Thuật toán k-Means có một số hạn chế đó là:
13.6. Online k-Means Clustering¶Dữ liệu của các công ty công nghệ chẳng hạn như Facebook, Google, Amazon,… thường có đặc điểm là những bộ dữ liệu rất lớn và đòi hỏi phải cập nhật online. Chính vì thế chúng ta không thể huấn luyện một lần trên toàn bộ dữ liệu vì làm như vậy sẽ gây lãng phí về chi phí lưu trữ, chi phí tính toán và không đảm bảo được tính realtime. Khi đó phương pháp online learning là giải pháp tối ưu thường được sử dụng để huấn luyện mô hình. Theo phương pháp này, chúng ta lựa chọn ra ngẫu nhiên một điểm dữ liệu và thực hiện cập nhật lại tâm cụm theo Gradient Descent. Cách huấn luyện mô hình trên một điểm dữ liệu như vậy còn được gọi là Stochastic Gradient Descent. Trường hợp khác khi chúng ta cũng cập nhật nghiệm theo Gradient Descent, nhưng đối với đầu vào là một batch gồm nhiều điểm dữ liệu thì được gọi là Mini-Batch Gradient Descent. Phương pháp online learning vừa đảm bảo được tính realtime và tiết kiệm chi phí tính toán nên thường được áp dụng trong thực tiễn cho nhiều thuật toán khác nhau trong machine learning, không chỉ riêng k-Means. Đối với thuật toán k-Means thì chúng ta sẽ tìm cách tối thiểu hoá hàm biến dạng theo gradient descent. Tức là khi hệ thống xuất hiện một điểm dữ liệu mới \(\mathbf{x}_i\) chúng ta sẽ xác định cụm mà điểm dữ liệu này sẽ thuộc về, chẳng hạn là \(\mu_j\), sau đó cập nhật lại tâm của cụm theo công thức gradient:\(\mathbf{x}_i\) chúng ta sẽ xác định cụm mà điểm dữ liệu này sẽ thuộc về, chẳng hạn là \(\mu_j\), sau đó cập nhật lại tâm của cụm theo công thức gradient: \[\begin{split}\begin{eqnarray}\mu_{j} & := & \mu_{j}-\alpha \nabla_{\mu_j} \mathcal{L}(\mathbf{x}_i, \mu) \\ & = & \mu_j + \alpha(\mathbf{x}_i - \mu_j) \end{eqnarray}\end{split}\] Trong đó \(\alpha\) là hệ số học tập (learning rate), thường được xác định là một giá trị rất nhỏ chẳng hạn từ 0.001 đến 0.03.\(\alpha\) là hệ số học tập (learning rate), thường được xác định là một giá trị rất nhỏ chẳng hạn từ 0.001 đến 0.03. 13.7. Tổng kết¶Thuật toán k-Means là phương pháp đơn giản và thường được áp dụng trong các bài toán phân cụm. Thuật toán này dựa trên khoảng cách để cập nhật lại nhãn cho các quan sát về tâm gần nhất và tâm cụm sau đó được tính theo trung bình của toàn bộ các quan sát bên trong cụm. Chúng ta cũng chứng minh được rằng thuật toán sẽ hội tụ sau hữu hạn bước. Tuy nhiên thuật k-Means vẫn là thuật toán tồn tại những hạn chế đó là cần phải xác định trước tâm cụm, vị trí tâm của cụm chịu sự phụ thuộc vào vị trí khởi tạo ban đầu của chúng, thuật toán cũng bị ảnh hưởng bởi outliers và sự khác biệt về đơn vị của biến đầu vào. Trong trường hợp các bộ dữ liệu có phân phối phức tạp và mất cân bằng thì thuật toán sẽ không phân cụm chính xác. 13.8. Bài tập¶
|
