ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← ML cơ bản

AI Foundation

Phân cụm k-means

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

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.

lesson46 minML cơ bảnAI Foundation

Thử đoán

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?

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.

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.

Ba bước lặp

1 / 3
  1. 1. Bước 1: Đoán

    Đặt 3 kho ở 3 vị trí bất kỳ — thậm chí là ngẫu nhiên.

Khám phá

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ổ xẻ một vòng lặp

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.

Bước 1: Đo khoảng cách từ điểm đến mỗ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ụmTính trung bìnhTâ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ụ.

Khoảnh khắc hiểu

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.

Thử thách

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

J=∑k=1K∑x∈Ck∥x−μk∥2J = \sum_{k=1}^{K} \sum_{x \in C_k} \|x - \mu_k\|^2

μk\mu_k là tâm cụm k, CkC_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)

μk=1∣Ck∣∑x∈Ckx\mu_k = \frac{1}{|C_k|} \sum_{x \in C_k} x

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.

Tại sao k-means luôn hội tụ?

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).

Ứng dụng thực tế của k-means

  • Phân khúc khách hàng: gom khách thành 4–8 cụm hành vi để gửi email/ưu đãi khác nhau.
  • Nén ảnh (color quantization): gom các màu tương tự thành một bảng 256 màu, giảm 80% dung lượng.
  • Phát hiện bất thường: điểm xa mọi tâm là outlier — dùng cho phát hiện gian lận thẻ tín dụng.
  • Phân cụm tài liệu: gom tin tức thành chủ đề bằng k-means trên vector embedding.
  • Gợi ý nhạc: Spotify dùng k-means trên vector nghe của người dùng để tìm “đồng minh thẩm mỹ” — xem bài ứng dụng.

Tóm tắt

5 điều cần nhớ về k-means

  • Ý 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.

Continue the path

Lesson 50 of 106