Thuật toán K-Means (Lloyd, 1957; MacQueen, 1967) là một trong những thuật toán học máy không giám sát kinh điển để giải quyết bài toán phân cụm. Thuật toán này được giới thiệu vào những năm 50 của thế kỷ 20 và là một trong 10 thuật toán được sử dụng nhiều nhất trong lĩnh vực khai phá dữ liệu và phát hiện tri thức. Ý tưởng của thuật toán K-Means là dựa trên k trọng tâm tại bước đầu tiên, thuật toán tiến hành gán các điểm vào các trọng tâm gần nhất và lặp lại quá trình trên cho đến khi các trọng tâm không thay đổi được nữa.

Hình 1. Phân cụm với thuật toán K-Means (Nguồn: towardsdatascience.com)

Các bước thực hiện của thuật toán K-Means được tóm tắt trong Algorithm 1 dưới đây.

Ví dụ 1. Mã chương trình dưới đây sẽ minh họa cách K-Means hoạt động trên một tập dữ liệu 2D đơn giản. Trong thực tế, K-Means có thể được áp dụng cho dữ liệu nhiều chiều hơn và thường được sử dụng trong nhiều ứng dụng như phân đoạn khách hàng, nén ảnh, hoặc giảm kích thước dữ liệu.

• Tạo dữ liệu mẫu sử dụng make_blobs từ sklearn.
• Định nghĩa hàm euclidean_distance để tính khoảng cách Euclidean giữa hai điểm.
• Áp dụng thuật toán K-Means với K=4 cụm.
• Hàm kmeans thực hiện thuật toán K-Means

Xác định số cụm cho thuận toán K-Means

Việc xác định số cụm K tối ưu cho thuật toán K-Means là một vấn đề quan trọng. Có nhiều phương pháp để xác định số cụm phù hợp. Tôi sẽ giải thích một số phương pháp phổ biến sau.

1. Phương pháp Elbow (Khuỷu tay):
   • Chạy K-Means với nhiều giá trị K khác nhau.
   • Tính tổng bình phương khoảng cách trong cụm (WCSS – Within-Cluster Sum of Squares) cho mỗi K.
   • Vẽ đồ thị WCSS theo K và tìm “khuỷu tay” – điểm mà việc tăng K không làm giảm WCSS đáng kể.
2. Phương pháp Silhouette:
   • Tính hệ số Silhouette cho mỗi điểm dữ liệu với nhiều giá trị K khác nhau.
   • Chọn K có hệ số Silhouette trung bình cao nhất.
3. Gap Statistic:
   • So sánh tổng phương sai trong cụm của dữ liệu thực với dữ liệu ngẫu nhiên.
   • Chọn K làm cực đại hóa khoảng cách (gap) giữa log(WCSS) của dữ liệu thực và dữ liệu ngẫu nhiên.
4. Phương pháp Information Criterion:
   • Sử dụng các tiêu chí như AIC (Akaike Information Criterion) hoặc BIC (Bayesian Information Criterion).
   • Cân bằng giữa độ phức tạp của mô hình (số cụm) và chất lượng phân cụm.
5. Phương pháp Cross-validation:
   • Chia dữ liệu thành tập huấn luyện và tập kiểm tra.
   • Chạy K-Means trên tập huấn luyện và đánh giá trên tập kiểm tra.
   • Chọn K cho kết quả tốt nhất trên tập kiểm tra.

Ví dụ 2. Chúng ta vẫn giữ nguyên phần dữ liệu mẫu đã tạo trong ví dụ 1 và tính WCSS trong phương pháp Elbow. “Khuỷu tay” trên đồ thị Elbow là một điểm quan trọng và nói lên việc chọn số cụm tối ưu trong thuật toán K-Means. Đây là điểm trên đồ thị Elbow nơi độ dốc của đường cong thay đổi đáng kể, tạo ra hình dạng giống như một khuỷu tay.

WCSS (Within-Cluster Sum of Squares) là tổng bình phương khoảng cách giữa mỗi điểm dữ liệu và tâm (centroid) của cụm mà nó thuộc về. Đây là một chỉ số quan trọng để đánh giá chất lượng của việc phân cụm trong K-Means.

Ý nghĩa của “khuỷu tay”:

a) Cân bằng giữa số cụm và tổng bình phương khoảng cách trong cụm (WCSS):

• Trước “khuỷu tay”: Tăng số cụm làm giảm WCSS đáng kể.
• Sau “khuỷu tay”: Tăng số cụm chỉ làm giảm WCSS một chút.

b) Điểm tối ưu:

• “Khuỷu tay” thường được coi là số cụm tối ưu, nơi có sự cân bằng tốt nhất giữa số lượng cụm và chất lượng phân cụm.

Kết quả hiển thị đồ thị Elbow và bốn đồ thị phân cụm, tương ứng với K = 2, 3, 4, và 5 như sau (Hình 2):

Hình 2. Kết quả thực nghiệm được minh họa bằng Đồ thị Elbow (2a-hình bên trên) và bốn đồ thị phân cụm (2b-hình bên dưới).

Trong đồ thị Elbow (Hình 2a), điểm K = 4 có thể xem như là điểm “khuỷu tay” trên đồ thị, nơi có sự thay đổi đáng kể về tốc độ giảm của WCSS. Việc tăng số cụm từ 3 lên 4 mang lại cải thiện đáng kể, trong khi tăng từ 4 lên 5 (hoặc cao hơn) chỉ mang lại cải thiện nhỏ.

Bên cạnh đó, trong biểu đồ phân cụm (Hình 2b), với K=4 cũng cho thấy sự phân chia rõ ràng và có ý nghĩa nhất giữa các cụm.

Hạn chế của thuật toán phân cụm K-Means

Thuật toán phân cụm K-Means, mặc dù phổ biến và hiệu quả trong nhiều trường hợp, vẫn có một số hạn chế đáng kể. Dưới đây là những hạn chế chính của K-Means:

1. Nhạy cảm với việc khởi tạo trọng tâm ban đầu:
   • Kết quả phân cụm có thể thay đổi đáng kể tùy thuộc vào vị trí ban đầu của các trọng tâm.
   • Có thể dẫn đến kết quả không ổn định hoặc tối ưu cục bộ.
2. Cần xác định trước số cụm K:
   • Yêu cầu người dùng chỉ định số cụm trước khi chạy thuật toán.
   • Việc chọn K không phù hợp có thể dẫn đến kết quả phân cụm kém chất lượng.
3. Giả định về hình dạng cụm:
   • K-Means giả định rằng các cụm có hình dạng hình cầu và kích thước tương đương.
   • Không hiệu quả với các cụm có hình dạng phức tạp hoặc kích thước khác biệt lớn.
4. Nhạy cảm với outliers:
   • Outliers có thể ảnh hưởng đáng kể đến vị trí của các trọng tâm.
   • Có thể dẫn đến phân cụm không chính xác hoặc không mong muốn.
5. Khó xử lý dữ liệu có mật độ khác nhau (Hình 3):
   • K-Means không hiệu quả khi các cụm có mật độ điểm dữ liệu khác nhau đáng kể.
6. Không phù hợp cho dữ liệu không tuyến tính (Hình 4):
   • K-Means giả định rằng ranh giới giữa các cụm là tuyến tính
   • Không hiệu quả khi ranh giới giữa các cụm là phi tuyến tính

Hình 3. K-Means khó xử lý dữ liệu có mật độ khác nhau.

Hình 4. K-Means không hiệu quả khi ranh giới giữa các cụm là phi tuyến

Một số ứng dụng

1/ Phân cụm khách hàng (Customer Segmentation)

Chúng ta sẽ sử dụng bộ dữ liệu về khách hàng của một cửa hàng bán lẻ với các đặc trưng sau: ‘Recency’ (Thời gian từ lần mua hàng gần nhất), ‘Frequency’ (Tần suất mua hàng), và ‘Monetary’ (Giá trị tiền tệ). Đây là một ví dụ phân tích RFM (Recency, Frequency, Monetary) phổ biến trong marketing.

Bộ dữ liệu này cho phép chúng ta phân tích khách hàng dựa trên hành vi mua hàng của họ. Các biểu đồ và thống kê cung cấp cái nhìn toàn diện về các phân khúc khách hàng khác nhau, giúp doanh nghiệp có thể:

• Tìm hiểu về các nhóm khách hàng có hành vi mua hàng khác nhau
• Phát triển chiến lược tiếp thị và chăm sóc khách hàng phù hợp cho từng phân khúc

Biểu đồ 3D (Hình 5) cung cấp cái nhìn tổng quan về cách khách hàng được phân khúc dựa trên hành vi mua hàng của họ.

• Trục X: Recency – Thời gian từ lần mua hàng gần nhất, đơn vị là ngày. Recency thấp (gần gốc tọa độ) có nghĩa là khách hàng mới mua hàng gần đây.
• Trục Y: Frequency – Tần suất mua hàng. Frequency cao có nghĩa là khách hàng mua hàng thường xuyên.
• Trục Z: Monetary – Giá trị tiền tệ, đơn vị là USD. Monetary cao có nghĩa là khách hàng chi tiêu nhiều.

Tôi đã áp dụng K-Means với 4 cụm cho tập dữ liệu minh họa. Kết quả cho thấy các cụm phân tách khá rõ ràng, đặc biệt là trên trục Monetary.

• Cụm màu tím: Đây là nhóm khách hàng ít giá trị nhất, mua hàng không thường xuyên, chi tiêu ít và đã lâu không mua hàng. Có thể gọi là “Infrequent Low Value Customers”.
• Cụm màu xanh lam: Là nhóm khách hàng mua hàng gần đây, tương đối thường xuyên, chi tiêu ở mức trung bình. Có thể gọi là “Recent Active Customers”
• Cụm màu xanh lá: Đây là nhóm khách hàng có giá trị cao, mua hàng thường xuyên và chi tiêu nhiều. Có thể gọi là “High Value Frequent Customers”
• Cụm màu vàng: Khách hàng có giá trị cao nhưng đã lâu không mua hàng. Họ từng mua thường xuyên và chi tiêu nhiều. Có thể gọi là “Dormant High Value Customers”

Hình 5. Phân khúc khách hàng dựa trên hành vi mua hàng của họ với số cụm là K=4.

2/ Ứng dụng K-Means trong bài toán Recommdation System

Tham khảo: H. -Q. Do, T. H. . -. An Nguyen, Q. -A. Nguyen, T. -H. Nguyen, V. -V. Vu and C. Le, “A Fast Clustering-based Recommender System for Big Data,” 2022 24th International Conference on Advanced Communication Technology (ICACT), PyeongChang Kwangwoon_Do, Korea, Republic of, 2022, pp. 353-359, doi: 10.23919/ICACT53585.2022.9728770. Available: https://ieeexplore.ieee.org/document/9728770

Một số thuật toán phân cụm khác được đề xuất gần đây bởi tác giả và cộng sự

• V. Vu, T. Bui, T. Nguyen, D. Tran, H. Do, V. Vu et al., “Constrained density peak clustering”, International Journal of Data Warehousing and Mining, vol. 19, no. 1, pp. 1–19, 2023. DOI: 10.4018/ijdwm.328776.
• V.-T. Dang, V.-V. Vu, H.-Q. Do, and T. K. Oanh Le, “GRAPH BASED CLUSTERING WITH CONSTRAINTS AND ACTIVE LEARNING”. Journal of Computer Science and Cybernetics, 37 (1), pp. 71–89, Mar. 2021.
• Vu, Viet-Vu; Do, Hong-Quan; Dang, Vu-Tuan; Do, Nang-Toan. “An Efficient Density-based Clustering with Side Information and Active Learning: A Case Study for Facial Expression Recognition Task”. Intelligent Data Analysis, pp. 227–240, Jan. 2019.

@Hong-Quan Do

Các bài trong cùng chủ đề:

Bài 1: Học AI bắt đầu từ đâu?

Bài 2: Giới thiệu về Học máy

Bài 3: Mô hình hồi quy tuyến tính

Bài 4.1: Phân loại với hồi quy Logistic

Bài 4.2: Hồi quy Logistic cho phân loại đa lớp và Ứng dụng phân loại cảm xúc văn bản

Bài 5.1. Một ứng dụng của học không giám sát

Bài 5.2. Thuật toán K-Means và Ứng dụng phân cụm khách hàng

Bài 6. Bình minh của mạng nơ-ron nhân tạo – Cấu Trúc Perceptron