K-Means Clustering
Phân cụm k-means
Bạn là chủ thương hiệu cà phê, có 30 cửa hàng rải rác khắp Hà Nội. Đội vận hành muốn đặt 3 kho nguyên liệu sao cho mọi cửa hàng đến kho gần nhất là ngắn nhất. Bạn đặt kho ở đâu?
Gà có trước hay trứng có trước?
Bạn không biết cửa hàng nào thuộc cụm nào — để biết điều đó cần có vị trí kho. Nhưng vị trí kho lại phụ thuộc vào danh sách cửa hàng trong cụm. Vòng tròn!
Mẹo của k-means: bắt đầu bằng một phỏng đoán thô, rồi sửa liên tục.
Đặt 3 kho ở 3 vị trí bất kỳ — thậm chí là ngẫu nhiên.
Mỗi cửa hàng → chọn kho gần nhất. Cụm được “khai sinh”.
Dời mỗi kho về trung bình cụm. Quay lại bước 2. Lặp đến khi không ai dời nữa.
Hình minh họa
Canvas bên dưới là bản đồ giả định. 30 chấm xám là cửa hàng đã có sẵn — bạn có thể nhấp vào ô trống để thêm cửa hàng mới. Kéo thanh số kho (k) rồi bấm Play để xem thuật toán chạy.
Bấm “Tiếp tục” để đi qua từng bước trong một vòng lặp: tính khoảng cách → gán cụm → dời tâm. Mỗi bước có hình ảnh riêng.
Với mỗi điểm dữ liệu, đo khoảng cách đến mỗi tâm. Dùng công thức Pythagoras: d = √((Δx)² + (Δy)²).
Số bên cạnh mỗi đường là khoảng cách. Đường đậm (xanh lá, d = 82) là tâm gần nhất — điểm sẽ được gán về cụm đó.
Đây là một ví dụ của một họ thuật toán lớn hơn gọi là Expectation-Maximization. Bạn sẽ gặp lại ý tưởng này ở nhiều nơi — Gaussian Mixture Model, thuật toán EM cho hidden Markov, thậm chí cả cách bạn tự điều chỉnh kỳ vọng khi gặp người mới.
Bạn có n điểm. Chạy k-means với k = 1 và k = n (số cụm bằng số điểm). Chuyện gì xảy ra?
Giải thích
k-means là thuật toán học không giám sát phổ biến nhất. Nó chia dữ liệu thành k nhóm sao cho tổng bình phương khoảng cách từ mỗi điểm đến tâm cụm của nó là nhỏ nhất. Đại lượng này gọi là inertia hoặc within-cluster sum of squares.
Hàm mục tiêu
là tâm cụm k, là tập điểm thuộc cụm k. Mục tiêu: tìm bộ tâm và phân cụm sao cho J nhỏ nhất. Vì inertia giảm đơn điệu qua mỗi vòng lặp, thuật toán luôn hội tụ — nhưng chỉ đảm bảo về cực tiểu địa phương.
Cập nhật tâm (M-step)
Tâm mới là trung bình toạ độ của các điểm trong cụm. Không phải trung vị, không phải một điểm bất kỳ — trung bình. Lý do: trung bình chính là điểm tối thiểu hoá tổng bình phương khoảng cách (đạo hàm J theo bằng 0 cho ra đúng công thức này).
Chọn k bằng phương pháp Elbow
Inertia luôn giảm khi k tăng (k càng lớn → cụm càng nhỏ → điểm càng gần tâm). Nhưng ở một điểm nào đó, tăng k không còn giảm inertia đáng kể nữa — đó là “khuỷu tay”.
Quan sát: từ k = 1 đến k = 3, inertia giảm mạnh. Từ k = 3 trở đi, giảm rất chậm — đó là “khuỷu tay”, gợi ý k = 3 là số cụm tự nhiên của dữ liệu này.
- Không chuẩn hoá dữ liệu: nếu một chiều có đơn vị lớn (thu nhập triệu đồng) và chiều khác nhỏ (tuổi), khoảng cách Euclidean bị chi phối bởi chiều lớn. Luôn chuẩn hoá trước khi chạy.
- Khởi tạo tồi: k-means rất nhạy với vị trí tâm ban đầu. Dùng k-means++ (chọn tâm xa nhau) thay vì ngẫu nhiên — scikit-learn mặc định đã bật.
- Cụm hình không phải cầu: k-means giả định cụm có dạng tròn (isotropic). Cụm cong hoặc mật độ khác nhau → dùng DBSCAN hoặc Spectral Clustering.
- Outlier: k-means dùng trung bình nên rất nhạy outlier. Xử lý bằng k-medoids (dùng điểm thật làm tâm) hoặc lọc outlier trước.
- Ý tưởng gốc: lặp giữa gán điểm đến tâm gần nhất (E-step) và dời tâm về trung bình cụm (M-step) đến khi không ai dời nữa.
- Hàm mục tiêu là inertia — tổng bình phương khoảng cách; luôn giảm đơn điệu và hội tụ đến cực tiểu địa phương.
- Phải chọn k trước khi chạy. Dùng Elbow hoặc Silhouette để tìm k phù hợp với dữ liệu.
- Nhạy với khởi tạo — luôn dùng k-means++ và chạy nhiều lần (n_init ≥ 10) để tránh nghiệm xấu.
- Chỉ phù hợp cụm hình cầu. Dữ liệu cong hoặc mật độ khác nhau → dùng DBSCAN, Spectral, hoặc GMM.
Kiểm tra hiểu biết
K-means thuộc loại học máy nào?