Từ điển học thuật Khoa học tự nhiên

K-means là gì? Ý nghĩa và ứng dụng chuyên sâu

Tiếng Anhk-means clustering

Tên gọi khácthuật toán k-meansk-means clusteringphân cụm k-meansthuật toán Lloyd

K-means là thuật toán học máy không giám sát kinh điển dùng để phân cụm dữ liệu, phân chia tập hợp n quan sát đa chiều thành k cụm phân biệt sao cho mỗi quan sát thuộc về cụm có tâm cụm gần nhất theo thước đo khoảng cách xác định.

316 lượt xem Cập nhật 3/9/2026

K-means (k-means clustering) là thuật toán học máy không giám sát kinh điển dùng để phân cụm dữ liệu, phân chia tập hợp n quan sát đa chiều thành k cụm phân biệt sao cho mỗi quan sát thuộc về cụm có tâm cụm gần nhất theo thước đo khoảng cách xác định.

Nguyên lý toán học và hàm mục tiêu của thuật toán

Mục tiêu toán học của phân cụm K-means là cực tiểu hóa tổng bình phương khoảng cách giữa các điểm dữ liệu và tâm cụm tương ứng trong nội bộ cụm (Within-Cluster Sum of Squares - WCSS), hay còn gọi là quán tính (inertia). Giả sử tập dữ liệu gồm $n$ điểm quan sát X={x1,x2,…,xn}⊂RdX = \{x_1, x_2, \dots, x_n\} \subset \mathbb{R}^d cần được phân chia thành $k$ tập hợp con rời nhau S={S1,S2,…,Sk}S = \{S_1, S_2, \dots, S_k\}:

Hàm mục tiêu được định nghĩa chính thức bởi công thức tối ưu hóa:

J=∑i=1k∑x∈Si∥x−μi∥2J = \sum_{i=1}^{k} \sum_{x \in S_i} \|x - \mu_i\|^2

Trong đó μi\mu_i là vector trọng tâm hình học của cụm SiS_i, được tính bằng trung bình cộng tọa độ của mọi phần tử trong cụm:

\mu_i = rac{1}{|S_i|} \sum_{x \in S_i} x

Bài toán tìm kiếm sự phân vùng tối ưu toàn cục để hàm $J$ đạt cực tiểu tuyệt đối là một bài toán NP-khó (NP-hard). Do đó, thuật toán K-means sử dụng phương pháp heuristic lặp cục bộ (thuật toán Lloyd) nhằm hội tụ về một nghiệm cực tiểu địa phương.

Quy trình vận hành từng bước theo thuật toán Lloyd

Thuật toán Lloyd chuẩn hóa tiến trình tối ưu hóa luân phiên qua bốn giai đoạn thực thi lặp:

  1. Khởi tạo tâm cụm: Chọn ngẫu nhiên $k$ điểm trong không gian đặc trưng làm vị trí ban đầu cho các tâm cụm μ1(0),μ2(0),…,μk(0)\mu_1^{(0)}, \mu_2^{(0)}, \dots, \mu_k^{(0)}.
  2. Bước gán nhãn (Assignment step): Gán mỗi điểm dữ liệu $x_j$ vào cụm $S_i$ có khoảng cách bình phương Euclid đến tâm cụm là nhỏ nhất: S_i^{(t)} = \left\{ x_j : \|x_j - \mu_i^{(t)}\|^2 \le \|x_j - \mu_l^{(t)}\|^2 \quad orall l, 1 \le l \le k ight\}
  3. Bước cập nhật tâm cụm (Update step): Tính toán lại vị trí mới của các tâm cụm μi(t+1)\mu_i^{(t+1)} dựa trên giá trị trung bình cộng tọa độ các điểm vừa được gán vào cụm đó ở bước 2.
  4. Kiểm tra điều kiện dừng (Convergence check): Lặp lại bước 2 và bước 3 cho đến khi vị trí các tâm cụm không còn dịch chuyển đáng kể (độ thay đổi nhỏ hơn ngưỡng sai số ϵ\epsilon), hoặc không còn điểm dữ liệu nào bị đổi nhãn cụm, hoặc số lượt lặp đạt giới hạn cực đại quy định.

Phương pháp xác định số cụm tối ưu và khởi tạo K-means++

Một trong những thách thức cốt lõi của K-means là đòi hỏi người dùng phải xác định trước số lượng cụm $k$. Hai kỹ thuật phổ biến nhất để lựa chọn $k$ hợp lý là:

  • Phương pháp điểm khuỷu tay (Elbow method): Vẽ đồ thị giá trị hàm mất mát WCSS theo các giá trị $k$ tăng dần từ 1 đến $M$. Khi $k$ tăng, WCSS luôn giảm; điểm "khuỷu tay" xuất hiện tại vị trí mà tốc độ giảm WCSS đột ngột chậm lại, đại diện cho giá trị $k$ cân bằng giữa độ chính xác và độ phức tạp mô hình.
  • Hệ số Silhouette (Silhouette coefficient): Đo lường mức độ tương đồng của một điểm với cụm của chính nó (tính gắn kết nội cụm $a$) so với các cụm lân cận (tính phân tách ngoại cụm $b$): s(i) = rac{b(i) - a(i)}{\max(a(i), b(i))} Giá trị s(i)∈[−1,1]s(i) \in [-1, 1]. Điểm trung bình Silhouette của toàn bộ tập dữ liệu càng tiến gần 1 chứng tỏ cấu trúc phân cụm càng rõ nét và tách biệt.

Bên cạnh đó, giải thuật K-means++ (Arthur & Vassilvitskii, 2007) giải quyết triệt để vấn đề nhạy cảm với vị trí khởi tạo ban đầu. K-means++ chọn tâm đầu tiên ngẫu nhiên, sau đó chọn các tâm tiếp theo với xác suất tỷ lệ thuận với bình phương khoảng cách đến tâm gần nhất đã chọn D(x)2D(x)^2, giúp các tâm ban đầu trải rộng đều và tăng tốc độ hội tụ gấp nhiều lần.

Bảng so sánh K-means với các thuật toán phân cụm khác

Tiêu chí so sánh K-means Hierarchical Clustering DBSCAN
Độ phức tạp thời gian O(n⋅k⋅d⋅I)O(n \cdot k \cdot d \cdot I) (Rất nhanh) O(n2log⁡n)O(n^2 \log n) hoặc O(n3)O(n^3) (Chậm) O(nlog⁡n)O(n \log n) với cây chỉ mục không gian
Hình dạng cụm nhận diện Hình cầu lồi, kích thước tương đương Cụm phân cấp cây đa dạng Hình dạng bất kỳ, phi cầu, uốn lượn
Yêu cầu tham số Cần biết trước số cụm $k$ Số cụm hoặc khoảng cách cắt dendrogram Bán kính ϵ\epsilon và số điểm lân cận cực tiểu MinPts
Khả năng kháng nhiễu Nhạy cảm với giá trị ngoại lai (outliers) Phụ thuộc vào liên kết (linkage) Tự động phân loại điểm nhiễu ngoại lai

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

Thuật toán K-means tối ưu hóa hàm mục tiêu nào?

K-means cực tiểu hóa tổng bình phương khoảng cách giữa các điểm dữ liệu và tâm cụm tương ứng trong nội bộ cụm (Within-Cluster Sum of Squares - WCSS).

Phương pháp nào thường được dùng để chọn số cụm k tối ưu?

Phương pháp điểm khuỷu tay (Elbow method) và phân tích hệ số Silhouette (Silhouette analysis).

K-means++ mang lại cải tiến gì so với K-means truyền thống?

K-means++ khởi tạo các tâm cụm ban đầu cách xa nhau với xác suất tỷ lệ thuận với bình phương khoảng cách, giúp tránh rơi vào cực tiểu địa phương kém và tăng tốc độ hội tụ.

Tài liệu tham khảo

  1. Zhao (2024). Review of: "Application of Data Mining Combined with K-means Clustering Algorithm in Enterprises' Risk Audit". Qeios Ltd. DOI: 10.32388/h2cxy9
  2. Patel (2024). Review of: "Application of Data Mining Combined with K-means Clustering Algorithm in Enterprises' Risk Audit". Qeios Ltd. DOI: 10.32388/rrh4e3
  3. Gad (2024). Review of: "Application of Data Mining Combined with K-means Clustering Algorithm in Enterprises' Risk Audit". Qeios Ltd. DOI: 10.32388/x8sd8g