Thử đoán
Chưa có ai dán nhãn “cụm bắc” hay “cụm nam” cho 30 cửa hàng. Nhưng dữ liệu thường tự gom nhóm — cửa hàng gần nhau thì về địa lý đã “đồng nhóm” rồi. k-means là cách để máy tính tìm ra những tụ điểm tự nhiên đó mà không cần ai nói trước.
Evaluating routing across providers.
AI Foundation
Chưa ai dán nhãn, nhưng dữ liệu thường tự gom nhóm. k-means tìm các tụ điểm tự nhiên — từ đặt kho hàng Grab đến phân khúc khách hàng.
Chưa có ai dán nhãn “cụm bắc” hay “cụm nam” cho 30 cửa hàng. Nhưng dữ liệu thường tự gom nhóm — cửa hàng gần nhau thì về địa lý đã “đồng nhóm” rồi. k-means là cách để máy tính tìm ra những tụ điểm tự nhiên đó mà không cần ai nói 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.
Ba bước lặp
Đặt 3 kho ở 3 vị trí bất kỳ — thậm chí là ngẫu nhiên.
Canvas là bản đồ giả định: 30 chấm xám là cửa hàng đã có sẵn. Chọn số kho k để xem thuật toán chạy qua các vòng gán – dời.
Inertia luôn giảm hoặc giữ nguyên — nếu bạn thấy nó tăng, có lỗi trong cài đặt!
Một vòng lặp gồm ba bước: tính khoảng cách → gán cụm → dời tâm.
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)²). Tâm gần nhất là tâm được chọn — điểm sẽ được gán về cụm đó.
Lặp lại phép đo cho tất cả điểm dữ liệu. Mỗi điểm chọn tâm gần nhất — và lấy luôn màu của tâm đó. Đây là bước E-step (expectation).
Mỗi điểm đã “khoác áo” theo tâm gần nhất. Cụm hình thành từ đây.
Với mỗi cụm, tính trung bình toạ độ của các điểm trong cụm — đó là tâm mới. Đây là bước M-step (maximization — nhưng cho k-means tương đương minimization của inertia).
| Cụm | Tính trung bình | Tâm mới |
|---|---|---|
| Cụm đỏ (5 điểm) | x = (50+60+65+52+58) / 5 = 57; y = (40+48+42+50+46) / 5 = 45.2 | (57, 45.2) |
| Cụm xanh (3 điểm) | x = (200+210+220) / 3 = 210; y = (150+155+160) / 3 = 155 | (210, 155) |
Tâm mới luôn nằm ở “trung tâm khối lượng” của cụm. Sau khi dời, lặp lại bước 1 — đôi khi một số điểm gần biên sẽ đổi cụm. Quay lại bước 2. Khi không điểm nào đổi cụm nữa → hội tụ.
k-means giải bài toán “gà và trứng” bằng cách luân phiên — giả vờ biết một phần, giải phần còn lại, rồi đảo ngược.
Đâ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.
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.
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.
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).
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.
Hàm mục tiêu J giảm đơn điệu qua mỗi vòng lặp (bước E không tăng J, bước M không tăng J), và J bị chặn dưới bởi 0. Thêm vào đó, số cách phân hoạch n điểm thành k cụm là hữu hạn, nên J không thể giảm mãi — thuật toán hội tụ trong hữu hạn vòng. Lưu ý quan trọng: chỉ hội tụ đến cực tiểu địa phương, không đảm bảo toàn cục. Đó là lý do scikit-learn chạy 10 lần với seed khác nhau và chọn nghiệm tốt nhất (tham số n_init=10).