K-Means Clustering

Phân cụm K-means là thuật toán học không giám sát, chia dữ liệu thành k nhóm, mỗi nhóm được đại diện bằng centroid — giá trị trung bình của các điểm được gán vào nhóm đó. Thuật toán tìm cách phân chia có tổng bình phương khoảng cách trong cụm nhỏ nhất, đại lượng gọi là inertia, nhờ đó các điểm trong một cụm nằm gần centroid. Quy trình tiêu chuẩn là thuật toán Lloyd, do Stuart Lloyd phát triển tại Bell Labs năm 1957 để lượng tử hóa tín hiệu; tên gọi "k-means" xuất phát từ bài báo năm 1967 của James MacQueen. Nhờ đơn giản, nhanh và mở rộng được đến hàng triệu điểm, k-means là công cụ mặc định cho khai phá dữ liệu, nén và khám phá cấu trúc của dữ liệu chưa gán nhãn.

Cách thuật toán hoạt động#

Sau khi chọn các centroid khởi tạo, thuật toán Lloyd luân phiên giữa bước gán và bước cập nhật cho đến khi các cụm không còn thay đổi:

1. Khởi tạo: Chọn k centroid ban đầu. Mặc định của Scikit-learn, k-means++, chọn centroid đầu tiên ngẫu nhiên; mỗi centroid tiếp theo được chọn với xác suất tỷ lệ thuận với bình phương khoảng cách đến centroid gần nhất đã chọn, giúp các seed phân tán rộng.
2. Gán: Gán từng điểm cho centroid gần nhất, thường dựa trên khoảng cách Euclid.
3. Cập nhật: Di chuyển từng centroid đến giá trị trung bình của các điểm hiện được gán cho centroid đó.
4. Lặp lại: Quay lại bước gán cho đến khi không còn điểm nào đổi cụm hoặc các centroid dịch chuyển ít hơn ngưỡng dung sai.

Cả hai bước đều không thể làm tăng inertia, vì vậy vòng lặp luôn hội tụ, nhưng chỉ đến cực tiểu cục bộ phụ thuộc vào các centroid ban đầu. Tìm cực tiểu toàn cục là bài toán NP-hard, nên các triển khai chạy nhiều lần khởi tạo và giữ lại lần có inertia thấp nhất. Trong KMeans của scikit-learn, n_init="auto" mặc định chạy một lần khi khởi tạo bằng k-means++ và 10 lần khi khởi tạo ngẫu nhiên.

Chọn số lượng cụm#

K-means cần biết trước k. Inertia luôn giảm khi k tăng vì nhiều centroid hơn sẽ nằm gần các điểm hơn; do đó, phương pháp elbow vẽ inertia theo k và tìm điểm mà mức giảm bắt đầu chững lại. Silhouette score so sánh, với từng điểm, khoảng cách trung bình đến cụm của chính nó với khoảng cách trung bình đến cụm khác gần nhất; điểm số nằm trong khoảng -1 đến 1, và giá trị cao hơn biểu thị cụm gọn, tách biệt tốt. Ví dụ này tính điểm cho k từ 2 đến 6 trên dữ liệu được tạo quanh bốn tâm:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

Inertia giảm từ 18.363 khi k=2 xuống 5.241 khi k=3 và 1.127 khi k=4, rồi chỉ giảm xuống 1.039 khi k=5 và 922 khi k=6; do đó, điểm elbow nằm ở k=4. Silhouette score cũng cho kết quả tương tự: đạt đỉnh 0,811 ở k=4 rồi giảm xuống 0,687 ở k=5, xác định lại bốn tâm dùng để tạo dữ liệu.

Giả định và biến thể#

K-means hoạt động tốt nhất khi các cụm gần hình cầu, có kích thước tương tự và tách biệt trong không gian Euclid. Các đặc trưng có thang đo lớn hơn chi phối khoảng cách, vì vậy dữ liệu thường được chuẩn hóa trước. Mọi điểm đều được gán vào một cụm; một vài giá trị ngoại lệ cực đoan có thể kéo centroid ra xa nhóm của nó. Một số biến thể nới lỏng các giới hạn này:

• K-means theo mini-batch: Cập nhật centroid từ các batch ngẫu nhiên nhỏ, chấp nhận giảm nhẹ độ chính xác để huấn luyện nhanh hơn nhiều trên tập dữ liệu lớn.
• K-medoids: Dùng các điểm dữ liệu thực làm tâm cụm, nhờ đó bền vững hơn trước giá trị ngoại lệ và hoạt động với mọi thước đo khoảng cách.
• Fuzzy c-means: Gán cho mỗi điểm mức độ thuộc về từng cụm theo tinh thần logic mờ, thay vì chỉ gán cứng vào một cụm duy nhất.
• Mô hình hỗn hợp Gaussian: Khớp một phân phối xác suất cho mỗi cụm, cho phép các cụm hình elip có kích thước khác nhau và trả về các phép gán mềm theo xác suất.

Ứng dụng trong AI và thị giác máy tính#

• Lượng tử hóa màu: Phân cụm màu pixel của ảnh rồi thay từng pixel bằng tâm cụm giúp giảm ảnh có hàng nghìn màu xuống bảng màu gồm k màu, qua đó nén ảnh và đồng thời cung cấp một dạng phân đoạn ảnh nhanh nhưng sơ bộ.
• Codebook và lượng tử hóa vector: Các tâm cụm tạo thành một codebook, còn mỗi vector được lưu dưới dạng chỉ mục của tâm cụm gần nhất. Phương pháp truy xuất ảnh túi từ thị giác cổ điển đã xây dựng từ vựng theo cách này từ các descriptor ảnh cục bộ.
• Thiết kế anchor box: YOLOv2 chạy k-means trên chiều rộng và chiều cao của các bounding box trong tập huấn luyện, dùng 1 trừ IoU làm khoảng cách để chọn anchor box.
• Lượng tử hóa bảng màu trọng số: Xuất YOLO26 sang Core ML bằng quantize=8 sẽ phân cụm các giá trị của từng tensor trọng số lớn thành 256 tâm cụm bằng k-means, nhờ đó model đã xuất lưu một chỉ mục 8 bit cho mỗi trọng số cùng một bảng tra cứu nhỏ.
• Phân khúc khách hàng: Nhà bán lẻ nhóm khách hàng theo tần suất mua hàng, quy mô giỏ hàng và thời gian từ lần mua gần nhất để điều chỉnh ưu đãi cho từng phân khúc.

K-Means và các thuật toán liên quan#

• K láng giềng gần nhất (KNN): Chữ "k" dùng chung dễ gây nhầm lẫn. KNN là thuật toán có giám sát, gán nhãn cho điểm mới dựa trên k mẫu đã gán nhãn gần nhất, còn k-means là thuật toán không giám sát và k là số cụm mà thuật toán tạo ra.
• DBSCAN: Nhóm các điểm theo mật độ, tự tìm số cụm, xử lý được các cụm có hình dạng bất kỳ và gán nhãn các điểm thưa là nhiễu thay vì buộc chúng vào một cụm.
• Phân cụm phân cấp: Xây dựng cây gồm các cụm lồng nhau bằng cách liên tục gộp các nhóm gần nhau nhất, nhờ đó có thể chọn k sau bằng cách cắt cây ở bất kỳ cấp nào, với chi phí tăng ít nhất theo bậc hai theo số điểm.