Thuật toán K-Means (K-Means clustering) và ví dụ

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.

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,…

Thuật toán k-means là gì?

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 (2, 2), (9, 2) và (4,9).

Ứ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à X0, X1, X2.

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à n_cluster = 3 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ị n_cluster 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()

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 (2, 2), (9, 2) và (4,9). 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 n_cluster 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 n_cluster tâm cụm bằng cách lấy ngẫu nhiên n_cluster đ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ố n_cluster 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 kmeans_visualize 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 kmeans 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

[[ 4.63795825  8.18623907]
 [-0.30216026  3.63816318]
 [ 4.53141139  1.41293449]]

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:

print(centers)
>>
[[4.03457895 8.99262915]
 [1.96728805 1.9546642 ]
 [8.81688307 1.9386987 ]]

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à (2, 2), (9, 2) và (4,9). Đ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é!

[sc_box]

Bạn có thể xem code & thực hành trực tiếp tại đây

[/sc_box]

Hãy để lại thắc mắc của bạn xuống mục bình luận. Tôi sẽ trả lời các bạn sớm nhất có thể!