Chào tất cả các bạn, hôm nay Nguyễn Văn Hiếu Blog sẽ trình bày về một thuật toán phân cụm dữ liệu có tên là k-means. Phần mở đầu mình sẽ giới thiệu về thuật toán phân cụm k-means. Tiếp đến mình sẽ trình bày tới ý tưởng giải quyết bài toán phân cụm với k-means. Và sau cùng sẽ là mình và các bạn sẽ cùng thực hiện code minh họa bài toán phân cụm trên không gian 2 chiều.

NỘI DUNG BÀI VIẾT

Giới thiệu về K-Means

K-means là một thuật toán phân cụm đơn giản thuộc loại học không giám sát(tức là dữ liệu không có nhãn) và được sử dụng để giải quyết bài toán phân cụm. Ý tưởng của thuật toán phân cụm k-means là phân chia 1 bộ dữ liệu thành các cụm khác nhau. Trong đó số lượng cụm được cho trước là k. Công việc phân cụm được xác lập dựa trên nguyên lý: Các điểm dữ liệu trong cùng 1 cụm thì phải có cùng 1 số tính chất nhất định. Tức là giữa các điểm trong cùng 1 cụm phải có sự liên quan lẫn nhau. Đối với máy tính thì các điểm trong 1 cụm đó sẽ là các điểm dữ liệu gần nhau.

Thuật toán phân cụm k-means thường được sử dụng trong các ứng dụng cỗ máy tìm kiếm, phân đoạn khách hàng, thống kê dữ liệu,…

Kết quả phân cụm của thuật toán kmeans

Thuật toán phân cụm k-means là một phương pháp được sử dụng trong phân tích tính chất cụm của dữ liệu. Nó đặc biệt được sử dụng nhiều trong khai phá dữ liệu và thống kê. Nó phân vùng dữ liệu thành k cụm khác nhau. Giải thuật này giúp chúng ta xác định được dữ liệu của chúng ta nó thực sử thuộc về nhóm nào.

Để các bạn dễ hình dung ứng dụng của thuật toán. Chúng ta hãy quan sát một ví dụ thực tế như sau:

Trong các mô hình kinh doanh, doanh nghiệp sẽ chia nhỏ tệp khách hàng ra thành những nhóm đối tượng khác nhau để có thể áp dụng những chiến lược kinh doanh cụ thể cho từng nhóm đối tượng. Điều này giúp cho khách hàng được tiếp cận với các sản phẩm thật sự phù hợp với bản thân họ. Sự phù hợp đó sẽ kéo doanh số của chúng ta tăng lên. Vấn đề đặt ra là làm sao có thể chia nhỏ tệp khách hàng đó ra khi mà số lượng hóa đơn là rất lớn và chúng ta không thể ngồi để phân tích từng vị khách.

Và mục tiêu của các thuật toán phân cụm là từ tập dữ liệu khổng lồ đó. Làm sao chúng ta biết có những nhóm dữ liệu đặc trưng nào trong đó? Từng dữ liệu trong đó thuộc vào nhóm nào? Đó là cái mà thuật toán phân cụm của chúng ta cần đi tìm câu trả lời.

Có thể bạn quan tâm: Tensorflow tutorial

Thực hành với K-Means

Đây là một ví dụ đơn giản về thuật toán phân cụm k-means trên không gian 2 chiều. Code ví dụ được viết bằng ngôn ngữ python. Sẽ có nhiều hình ảnh để các bạn hiểu được từng bước của thuật toán này.

Bài toán: Có 1 tập hợp các điểm trên không gian tọa độ Oxy. Mỗi điểm sẽ có tọa độ (x, y) xác định. Bài toán cần giải quyết là chia các điểm này thành K cụm khác nhau phân biệt.

Triển khai code

Đầu tiên, hãy import các thư viện cần thiết

import numpy as np # thư viện tính toán toán học import matplotlib.pyplot as plt # visualize data sử dụng đồ thị from scipy.spatial.distance import cdist # Hỗ trợ tính khoảng cách

Tôi sẽ khởi tạo ngẫu nhiên các điểm dữ liệu. Tuy nhiên, để thể hiện tính chất cụm của dữ liệu, ta sẽ khởi tạo các mẫu dữ liệu này xung quanh 3 tâm cụm

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

2.

Ứng với mỗi tâm cụm, ta sẽ khởi tạo 500 điểm dữ liệu xung quanh nó. Ở đây lần lượt là

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

3.

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

Để đơn giản, tôi sẽ chỉ định số tâm cụm cho bài toán này là

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

4 luôn – chính là K đó ạ. Đúng với số cụm chúng ta vừa khởi tạo. Bạn có thể thử và xem với các giá trị

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

5 khác nhau để xem sự thay đổi.

Bạn có thể xem phân bố của dữ liệu mà chúng ta vừa tạo ra như sau:

plt.xlabel('x') plt.ylabel('y') plt.plot(X[:, 0], X[:, 1], 'bo', markersize=5) plt.plot() plt.show()

Phân bố của dữ liệu chúng ta vừa tạo

Như vậy, nếu thuật toán phân cụm k-means hoạt động tốt, nó sẽ phải học ra 3 tâm cụm có tọa độ sát với 3 tâm cụm

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

2. Và ban đầu tọa độ của các tâm này sẽ được lấy ngẫu nhiên.

Bây giờ, chúng ta hãy viết hàm khởi tạo

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

5 tâm cụm

def kmeans_init_centers(X, n_cluster):

random k index beetween 0 and shape(X) without duplicate index.

Then return X[index] as cluster

return X[np.random.choice(X.shape[0], n_cluster, replace=False)]

Ở đây, tôi khởi tạo

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

5 tâm cụm bằng cách lấy ngẫu nhiên

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

5 điểm dữ liệu của tập dữ liệu. Bạn có thể lấy tọa độ nào đó không thuộc vào tệp dữ liệu. Nhưng hãy lưu ý đến: “Việc khởi tạo vị trí của k tâm cụm cũng rất quan trọng” tôi đã nói ở trên.

Xác định các tâm cụm

def kmeans_predict_labels(X, centers): D = cdist(X, centers)

return index of the closest center

return np.argmin(D, axis = 1)

Với mỗi điểm dữ liệu trong tập dữ liệu, tâm cụm của nó sẽ là 1 trong số

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

5 tâm cụm gần với nó nhất. Việc tính toán khoảng cách giữa 2 điểm trong bài này sử dụng Euclidean distance. Công thức này bạn vẫn thường sử dụng để tính khoảng cách giữa hai điểm khi biết tọa độ hồi cấp 3. Ngoài ra còn có rất nhiều công thức tính khoảng cách khác nữa.

Cập nhật lại vị trí của các tâm cụm

def kmeans_update_centers(X, labels, n_cluster): centers = np.zeros((n_cluster, X.shape[1])) for k in range(n_cluster):

# collect all points assigned to the k-th cluster   
Xk = X[labels == k, :]  
# take average  
centers[k,:] = np.mean(Xk, axis = 0)  

return centers

Việc tính toán lại tọa độ của mỗi tâm cụm được thực hiện đơn giản bằng cách lấy trung bình cộng tọa độ của tất cả các điểm dữ liệu của cụm. Sau khi tính toán xong, vị trí mới của tâm cụm sẽ nằm chính giữa cụm của nó.

Kiểm tra tính hội tụ

def kmeans_has_converged(centers, new_centers):

return True if two sets of centers are the same

return (set([tuple(a) for a in centers]) ==

  set([tuple(a) for a in new_centers]))

Nếu việc cập nhật lại vị trí của các tâm cụm không có thay đổi gì thì có nghĩa là chúng ta đã có thể dừng và đưa ra kết quả. Nghĩa là tọa độ cũ và tọa độ sau khi cập nhật của các tâm cụm là như nhau. Trong trường hợp này, nếu bạn có tiếp tục chạy nữa thì cũng sẽ không thay đổi gì.

Để các bạn có thể thấy rõ cách hoạt động của thuật toán, hãy bổ sung thêm hàm visualize này

Hàm này dùng để vẽ dữ liệu lên đồ thị

Random color chỉ làm việc với k <= 4

Nếu bạn thay đổi k > 4, hãy sửa lại phần random color nhé

Chỉ sử dụng trong bài toán này thôi nhé.

def kmeans_visualize(X, centers, labels, n_cluster, title): plt.xlabel('x') # label trục x plt.ylabel('y') # label trục y plt.title(title) # title của đồ thị plt_colors = ['b', 'g', 'r', 'c', 'm', 'y', 'k', 'w'] # danh sách các màu hỗ trợ for i in range(n_cluster):

data = X[labels == i] # lấy dữ liệu của cụm i  
plt.plot(data[:, 0], data[:, 1], plt_colors[i] + '^', markersize = 4, label = 'cluster_' + str(i)) # Vẽ cụm i lên đồ thị  
plt.plot(centers[i][0], centers[i][1],  plt_colors[i+4] + 'o', markersize = 10, label = 'center_' + str(i)) # Vẽ tâm cụm i lên đồ thị  

plt.legend() # Hiện bảng chú thích plt.show()

Sau mỗi lần cập nhật tâm cho từng điểm dữ liệu, hoặc cập nhật lại tọa độ của các tâm. Hãy gọi hàm này để xem sự thay đổi của vị trí tâm và tâm của các điểm dữ liệu. Kết quả sẽ được vẽ lên đồ thị để bạn dễ quan sát.

Toàn bộ thuật toán k-means

def kmeans(init_centes, init_labels, X, n_cluster): centers = init_centes labels = init_labels times = 0 while True:

labels = kmeans_predict_labels(X, centers)  
kmeans_visualize(X, centers, labels, n_cluster, 'Assigned label for data at time = ' + str(times + 1))  
new_centers = kmeans_update_centers(X, labels, n_cluster)  
if kmeans_has_converged(centers, new_centers):  
  break  
centers = new_centers  
kmeans_visualize(X, centers, labels, n_cluster, 'Update center possition at time = ' + str(times + 1))  
times += 1  

return (centers, labels, times)

Bạn đầu, chúng ta sẽ khởi tọa độ cho các tâm cụm. Khởi tạo tất cả các điểm dữ liệu thuộc cụm 0(tùy chọn).

Lặp lại việc tìm tâm cụm cho các điểm dữ liệu, cập nhật tọa độ tâm cụm cho tới khi tọa độ của các tâm cụm không còn thay đổi nữa.

Do bài toán này khá đơn giản, nên việc giải chỉ mất vài lần lặp.

Chúng ta sẽ gọi hàm

plt.xlabel('x') plt.ylabel('y') plt.plot(X[:, 0], X[:, 1], 'bo', markersize=5) plt.plot() plt.show()

1 sau mỗi lần gán lại tâm cụm cho từng điểm dữ liệu hoặc tính toán lại tọa độ các tâm cụm.

Bây giờ, việc ta cần làm là khởi tạo tọa độ tâm các cụm. Và sau đó gọi hàm

plt.xlabel('x') plt.ylabel('y') plt.plot(X[:, 0], X[:, 1], 'bo', markersize=5) plt.plot() plt.show()

2 phía trên để thực thi.

init_centers = kmeans_init_centers(X, n_cluster) print(init_centers) # In ra tọa độ khởi tạo ban đầu của các tâm cụm init_labels = np.zeros(X.shape[0]) kmeans_visualize(X, init_centers, init_labels, n_cluster, 'Init centers in the first run. Assigned all data as cluster 0') centers, labels, times = kmeans(init_centers, init_labels, X, n_cluster) print('Done! Kmeans has converged after', times, 'times')

Bạn có thể xem sự thay đổi ở các lần chạy như sau:

Đây là tọa độ tâm các cụm khởi tạo ngẫu nhiên

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

0

Quá trình chạy được thể hiện lần lượt theo đồ thị dưới đây:

Sau khi chạy xong thuật toán k-means. Chúng ta hãy thử in gia tọa độ của các tâm cụm:

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

1

Kết quả cho ra tọa độ của 3 tâm cụm khá sát vớt các tâm mà chúng ta khởi tạo là

means = [[2, 2], [9, 2], [4, 9]] cov = [[2, 0], [0, 2]] n_samples = 500 n_cluster = 3 X0 = np.random.multivariate_normal(means[0], cov, n_samples) X1 = np.random.multivariate_normal(means[1], cov, n_samples) X2 = np.random.multivariate_normal(means[2], cov, n_samples) X = np.concatenate((X0, X1, X2), axis = 0)

2. Điều đó cho thấy k-means đã làm rất tốt trong bài toán này.

Các bạn có thể thử thay đổi các giá trị k khác nhau để xem sự thay đổi. Bạn cũng có thể sử đổi theo ý mình để hiểu cả ý tưởng của thuật toán lẫn triển khai code.

Bạn đọc thực nghiệm

Source code thuật toán K-Measn trình bày trong bài viết này được lưu tại Github, bạn đọc có thể nhấp vào link dưới đây để thực hành trực tiếp nhé!