Phân cụm K-Means

Phân cụm K-Means là gì?

K-Means là thuật toán phân chia lặp lại, chia n điểm dữ liệu thành K cụm bằng cách tối thiểu hóa WCSS. Mỗi cụm được đại diện bởi tâm cụm.

Thuật toán bắt đầu với K tâm ban đầu, sau đó luân phiên: (1) gán mỗi điểm vào tâm gần nhất, (2) tính lại tâm. Thường hội tụ trong 10-50 lần lặp.

Chọn K là thách thức chính. Phương pháp khuỷu tay vẽ WCSS theo K và tìm điểm 'gập'. Điểm Silhouette gần +1 cho thấy phân cụm tốt.

Formula: WCSS = Σₖ Σ(xᵢ ∈ Cₖ) ‖xᵢ − μₖ‖² trong đó μₖ = tâm của cụm Cₖ ‖·‖ = khoảng cách Euclid Thuật toán hội tụ khi việc gán không còn thay đổi

Ví dụ tính toán

Điểm: (1,1), (1.5,2), (3,4), (5,7), (3.5,5), (4.5,5), (3.5,4.5). K=2, tâm μ₁≈(1.25, 1.5), μ₂≈(3.9, 5.1). WCSS = 8,525.

Khi nào sử dụng công cụ này

• Chuyên viên phân tích marketing phân khúc khách hàng thành các nhóm dựa trên hành vi mua sắm, nhân khẩu học hoặc chỉ số tương tác
• Kỹ sư chất lượng nhóm dữ liệu đo lường để xác định các quần thể riêng biệt hoặc các dạng hư hỏng trong dữ liệu sản xuất
• Nhà nghiên cứu thực hiện phân loại không giám sát để khám phá các nhóm tự nhiên trong tập dữ liệu đa chiều
• Nhà khoa học dữ liệu thực hiện phân tích khám phá để xác định liệu dữ liệu có chứa các cụm có ý nghĩa trước khi áp dụng học có giám sát

Những sai lầm thường gặp

• Không chuẩn hóa đặc trưng trước khi phân cụm — nếu một biến nằm trong khoảng 0-1000 và biến khác 0-1, K-Means sẽ bị biến có thang lớn hơn chi phối; luôn chuẩn hóa về trung bình 0 và phương sai đơn vị
• Chọn K theo trực giác mà không dùng Phương pháp khuỷu tay (Elbow) hoặc Điểm Silhouette — K tùy tiện tạo ra các cụm vô nghĩa; hãy dùng tiêu chí định lượng để biện minh cho lựa chọn
• Chỉ chạy K-Means một lần — khởi tạo ngẫu nhiên có thể cho kết quả khác nhau mỗi lần chạy; hãy chạy nhiều lần (10-20) với các seed khác nhau và chọn WCSS tốt nhất
• Áp dụng K-Means cho dữ liệu có cụm không hình cầu hoặc chồng lấn — K-Means giả định các cụm lồi, kích thước bằng nhau; dùng DBSCAN hoặc Mô hình hỗn hợp Gauss cho các hình dạng cụm bất thường

Cách diễn giải kết quả

• WCSS thấp hơn cho thấy các cụm chặt hơn, nhưng WCSS luôn giảm khi K tăng — hãy dùng Phương pháp khuỷu tay để tìm K mà tại đó việc thêm cụm không còn cải thiện đáng kể
• Kích thước cụm phải có ý nghĩa với ứng dụng của bạn — cụm chỉ có 1-2 điểm có thể là nhóm ngoại lai chứ không phải cụm thực sự
• Xem xét tọa độ tâm cụm để hiểu mỗi cụm đại diện cho điều gì — tâm cụm là thành viên trung bình và xác định đặc trưng của cụm

Tiêu chuẩn và tài liệu tham khảo

• MacQueen, J. (1967), 'Some Methods for Classification and Analysis of Multivariate Observations', Proc. 5th Berkeley Symposium — nguồn gốc của thuật ngữ 'k-means'
• Lloyd, S. (1957, công bố 1982), 'Least Squares Quantization in PCM', IEEE Transactions on Information Theory — vòng lặp gán-cập nhật tiêu chuẩn
• Jain, A. K. (2010), 'Data Clustering: 50 Years Beyond K-Means', Pattern Recognition Letters — khảo sát thực hành k-means, cách khởi tạo và cách chọn K

Câu hỏi thường gặp

Làm sao chọn đúng số cụm (K)?

Phương pháp khuỷu tay: vẽ WCSS cho K = 1~10, chọn K tại điểm gập. Hoặc chọn K có điểm Silhouette cao nhất.

Hạn chế của K-Means?

Giả định cụm hình cầu, nhạy cảm với ngoại lai. Không phát hiện cụm không lồi. Xét DBSCAN hoặc GMM cho những trường hợp này.