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.
Toàn bộ source code của bài học này bạn có thể xem và tải về tại đây.
Nội dung bài viết
- Giới thiệu về thuật toán phân cụm k-means
- Thuật toán phân cụm k-means
- Ý tưởng của thuật toán k-means
- Lựa chọn số cụm k là bao nhiêu thì hợp lý?
- Việc khởi tạo vị trí ban đầu của k tâm cụm cũng rất quan trọng
- Trong nhiều trường hợp, bạn sẽ không thể hoặc phải chờ rất lâu để có được lời giải
- Ý tưởng của thuật toán k-means
- Ví dụ bài toán phân cụm sử dụng k-means
Giới thiệu về thuật toán phân cụm 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 phân cụm k-means
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.
Ý tưởng của thuật toán k-means
- Khởi tạo K điểm dữ liệu trong bộ dữ liệu và tạm thời coi nó là tâm của các cụm dữ liệu của chúng ta.
- Với mỗi điểm dữ liệu trong bộ dữ liệu, tâm cụm của nó sẽ được xác định là 1 trong K tâm cụm gần nó nhất.
- Sau khi tất cả các điểm dữ liệu đã có tâm, tính toán lại vị trí của tâm cụm để đảm bảo tâm của cụm nằm ở chính giữa cụm.
- Bước 2 và bước 3 sẽ được lặp đi lặp lại cho tới khi vị trí của tâm cụm không thay đổi hoặc tâm của tất cả các điểm dữ liệu không thay đổi.
Trên thực tế, sẽ có 1 vài lưu ý cần phải giải quyết khi áp dụng thuật toán k-means
Lựa chọn số cụm k là bao nhiêu thì hợp lý?
Chỉ việc lựa chọn số cụm k đã có thể tách thành 1 bài toán riêng. Không có 1 con số k nào là hợp lý cho tất cả các bài toán. Bạn có thể đọc hiểu tập dữ liệu của mình để xác định xem trong đó có thể có bao nhiêu cụm? Nhưng không phải lúc nào bạn cũng có thể làm thế. Cách làm duy nhất là bạn hãy thử với từng giá trị k=1,2,3,4,5,… để xem kết quả phân cụm thay đổi như thế nào. Một số nghiên cứu cho thấy việc thay đổi k sẽ có hiệu quả nhưng sẽ dừng lại ở 1 con số nào đó. Như vậy bạn hoàn toàn có thể thử xem dữ liệu của mình tốt với giá trị k nào đó.
Việc khởi tạo vị trí ban đầu của k tâm cụm cũng rất quan trọng
Bằng cách nào đó, hãy có gắng khởi tạo k tâm cụm này phân bố đồng đều trên không gian của bộ dữ liệu. Điều đó có thể làm khi bạn có thể xác định được không gian và tính chất của dữ liệu. Nhưng ít nhất, các tâm cụm mà bạn khởi tạo cũng đừng quá gần nhau, cũng đừng trùng nhau.
Còn 1 cách cuối cùng là bạn sẽ chạy thuật toán nhiều lần để lấy kết quả tốt nhất trong các lần chạy đó. Với điều kiện là bạn khởi tạo tâm của k cụm ngẫu nhiên.
Trong nhiều trường hợp, bạn sẽ không thể hoặc phải chờ rất lâu để có được lời giải
Đối với những trường hợp dữ liệu phức tạp, thuật toán k-means sẽ rất lâu hoặc không bao giờ hội tụ. Tức là sẽ không bao giờ xác định được tâm cụm cố định để kết thúc bài toán. Hoặc là phải chạy qua rất nhiều bước lặp. Trong những trường hợp như vậy, thay vì phải tìm được k tâm cụm cố định thì ta sẽ dừng bài toán khi sự thay đổi ở một con số chấp nhận được. Tức là giữa hai lần cập nhật tâm cụm thì chênh lệch vị trí giữa tâm cũ và mới nhỏ hơn một số delta cho phép nào đó.
Ví dụ bài toán phân cụm sử dụng 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
0
1
2
3
4
|
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.
0
1
2
3
4
5
6
7
8
9
|
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:
0
1
2
3
4
5
6
|
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
0
1
2
3
4
5
|
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.Hàm xác định tâm cụm của từng điểm dữ liệu trong tập dữ liệu
0
1
2
3
4
5
|
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.Hàm cập nhật lại vị trí của các tâm cụm
0
1
2
3
4
5
6
7
8
9
|
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 xem đã tìm được lời giải chưa
0
1
2
3
4
5
|
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
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# 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.
Hàm chính thực hiện thuật toán k-means
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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.
0
1
2
3
4
5
6
7
8
|
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
0
1
2
3
4
|
[[ 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:
0
1
2
3
4
5
6
|
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.
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ể!
