K-Means Clustering

K-Means chia dữ liệu thành K cụm bằng cách giảm khoảng cách bình phương trong cụm (inertia).

$$ J = \sum_{i=1}^{N} \min_{1 \leq j \leq K} \left\lVert x_i - \mu_j \right\rVert^2 $$

Mỗi mẫu được gán vào tâm gần nhất, sau đó các tâm được tính lại bằng trung bình các mẫu được gán.

Thuật toán luân phiên giữa hai bước xác định:

$$ c_i \leftarrow \arg\min_j \lVert x_i - \mu_j \rVert^2 $$

$$ \mu_j \leftarrow \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i $$

Inertia giảm đơn điệu cho đến khi hội tụ về cực trị cục bộ.

Khởi tạo ngẫu nhiên đơn giản nhưng có thể bắt đầu từ seed kém.

k-means++ phân tán các tâm ban đầu, thường hội tụ nhanh hơn và có inertia cuối thấp hơn.

Trong thực tế, chạy nhiều lần với seed khác nhau để giảm nhạy cảm cực trị cục bộ.