Bài 32: K-Means Clustering — gom nhóm tự động

Bốn module đầu của series tập trung vào supervised learning — mỗi sample có label \( y \) và model học hàm \( f(\mathbf{x}) \approx y \). Module 5 chuyển sang nhóm bài toán khác: chỉ có \( X \), không có \( y \). Mục tiêu không còn là dự đoán, mà là tìm cấu trúc ẩn trong data.

Module 5 gồm năm bài:

• Bài 32 (bài này) — K-Means clustering.
• Bài 33 — đánh giá clustering bằng Elbow và Silhouette.
• Bài 34 — Hierarchical clustering.
• Bài 35 — DBSCAN, clustering dựa trên mật độ.
• Bài 36 — PCA, giảm chiều dữ liệu.

K-Means là điểm khởi đầu vì đơn giản, nhanh, và là baseline mà mọi thuật toán clustering khác đem ra so sánh.

Recap Bài 2 — ba loại ML:

• Supervised: input \( X \) đi kèm label \( y \). Model học mapping \( f: X \to y \). Đo lường rõ ràng bằng accuracy, RMSE, AUC, v.v.
• Unsupervised: chỉ có \( X \), không có \( y \). Mục tiêu: phát hiện cấu trúc — nhóm tương tự, chiều giảm, phân phối bất thường.
• Reinforcement: agent học qua tương tác và reward, ngoài phạm vi series này.

Ba nhóm bài toán unsupervised chính:

• Clustering — gom sample thành nhóm tương tự (K-Means, DBSCAN, Hierarchical).
• Dimensionality reduction — giảm số chiều để visualize hoặc tăng tốc (PCA, t-SNE, UMAP).
• Anomaly detection — phát hiện sample bất thường (Isolation Forest, One-Class SVM, hoặc dùng clustering với điểm ở xa centroid).

Không có "ground truth" khi đánh giá unsupervised — đây là khác biệt cốt lõi. Bài 33 sẽ đào sâu cách đo lường gián tiếp.

Cho tập \( \{ \mathbf{x}_1, \ldots, \mathbf{x}_n \} \), clustering chia thành các nhóm sao cho:

• Các điểm trong cùng nhóm gần nhau (similarity cao, distance thấp).
• Các điểm khác nhóm xa nhau.

"Gần" và "xa" được định nghĩa bằng một distance metric — phổ biến nhất là Euclidean \( \|\mathbf{x}_i - \mathbf{x}_j\|_2 \). Cũng có cosine, Manhattan, Mahalanobis cho từng ngữ cảnh.

Khác với classification:

• Classification: biết trước class, học mapping từ feature sang class.
• Clustering: không biết trước class. Nhóm tự xuất hiện từ structure của data. Sau khi clustering xong, người làm phải giải thích nhóm đó có ý nghĩa gì (segment khách hàng VIP, segment churn, …).

K-Means là thuật toán clustering đơn giản nhất và được dùng nhiều nhất. Hai giả định cốt lõi:

• Số cluster \( K \) cho trước — người dùng phải chọn.
• Mỗi cluster đại diện bởi một centroid \( \boldsymbol{\mu}_k \in \mathbb{R}^d \) — vector "tâm" của cluster.

Quy tắc gán: mỗi điểm \( \mathbf{x}_i \) thuộc cluster có centroid gần nhất theo Euclidean distance:

\[ c_i = \arg\min_{k \in \{1, \ldots, K\}} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|_2 \]

Vấn đề: muốn tính \( c_i \) thì cần biết \( \boldsymbol{\mu}_k \), nhưng muốn tính \( \boldsymbol{\mu}_k \) thì lại cần biết các điểm thuộc cluster \( k \) — tức cần \( c_i \). Bài toán "con gà — quả trứng". Lloyd's algorithm giải bằng cách lặp.

Thuật toán chuẩn của K-Means (Lloyd, 1957; xuất bản 1982):

• Bước 1 — Init: khởi tạo \( K \) centroid \( \boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_K \) (random hoặc K-Means++, mục 7).
• Bước 2 — Assign: với mỗi điểm \( \mathbf{x}_i \), gán vào cluster có centroid gần nhất:

  \[ c_i = \arg\min_k \|\mathbf{x}_i - \boldsymbol{\mu}_k\|_2^2 \]

• Bước 3 — Update: tính lại mỗi centroid là trung bình của các điểm thuộc cluster đó:

  \[ \boldsymbol{\mu}_k = \frac{1}{|C_k|} \sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i \]

  trong đó \( C_k = \{ i : c_i = k \} \).
• Bước 4 — Lặp: quay lại Bước 2 cho tới khi convergence — không có điểm nào đổi cluster nữa, hoặc centroid đổi không đáng kể.

Một vài tính chất quan trọng:

• Mỗi vòng lặp không bao giờ làm tăng objective WCSS (mục 6) — Lloyd's algorithm là dạng coordinate descent.
• Convergence sau hữu hạn bước vì số cách gán là hữu hạn (\( K^n \)) và objective giảm đơn điệu.
• Hội tụ tới local minimum, không phải global. Init khác → kết quả khác.

K-Means là một bài toán tối ưu rõ ràng. Hàm mục tiêu cần minimize:

\[ J = \sum_{k=1}^K \sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|_2^2 \]

Tên gọi: Within-Cluster Sum of Squares (WCSS), còn gọi là inertia trong sklearn. Diễn giải: tổng bình phương khoảng cách từ mỗi điểm tới centroid của cluster nó thuộc về.

Tại sao mean lại là update tối ưu? Cố định gán \( c_i \), tìm \( \boldsymbol{\mu}_k \) để minimize \( \sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|_2^2 \). Đạo hàm theo \( \boldsymbol{\mu}_k \), set = 0:

\[ \boldsymbol{\mu}_k = \frac{1}{|C_k|} \sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i \]

Đúng là trung bình — đây là lý do thuật toán có tên "K-Means".

Cố định centroid, tìm gán tối ưu thì hiển nhiên: gán mỗi điểm vào centroid gần nhất. Hai bước này (assign / update) đều giảm \( J \), nên tổng thể \( J \) giảm đơn điệu. Tìm global minimum của \( J \) là NP-hard ngay cả với \( d = 2 \) (Mahajan et al., 2009) — Lloyd's chỉ cho local minimum.

Init random uniform các centroid có rủi ro: hai centroid rơi gần nhau → một cluster bị "chia đôi", cluster khác bị bỏ rơi (empty hoặc bị nuốt) → kết quả là local minimum xấu.

K-Means++ (Arthur & Vassilvitskii, 2007) — chiến lược init thông minh:

• Chọn centroid 1 random uniform từ data.
• Với centroid \( k = 2, \ldots, K \): chọn điểm \( \mathbf{x}_i \) làm centroid với xác suất tỉ lệ với \( D(\mathbf{x}_i)^2 \), trong đó \( D(\mathbf{x}_i) \) là khoảng cách từ \( \mathbf{x}_i \) tới centroid gần nhất đã chọn.

Ý nghĩa: điểm càng xa các centroid hiện tại thì càng có xác suất cao được chọn → centroid mới có xu hướng trải đều. Tránh được phần lớn case khởi tạo xấu.

K-Means++ có lý thuyết kèm theo: giá trị WCSS kỳ vọng sau init đã \( \leq 8(\ln K + 2) \) lần WCSS optimal. Sau khi Lloyd's chạy thêm vài vòng, kết quả thường tốt hơn nhiều so với init random.

K-Means++ là mặc định trong sklearn (init="k-means++").

API tối thiểu:

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=3, n_init=10, random_state=42)
kmeans.fit(X)

labels = kmeans.labels_              # cluster cua moi diem train, shape (n,)
centers = kmeans.cluster_centers_    # toa do K centroid, shape (K, d)
inertia = kmeans.inertia_            # WCSS sau training
n_iter = kmeans.n_iter_              # so vong lap toi convergence

Khác biệt so với supervised estimator:

• fit(X) không nhận \( y \) — K-Means là unsupervised.
• labels_ là output sau fit, KHÔNG phải input. Đây là cluster ID (số nguyên 0 tới \( K-1 \)) gán cho mỗi sample train.
• Cluster ID không có ý nghĩa thứ tự — cluster 0 và cluster 1 chỉ là tên. Hai lần fit với seed khác nhau có thể đổi chỗ ID dù partition giống hệt.

Predict cho sample mới:

new_labels = kmeans.predict(X_new)   # gan moi sample moi vao centroid gan nhat

Hoặc tính khoảng cách tới mọi centroid:

distances = kmeans.transform(X_new)  # shape (n_new, K)

• n_clusters (\( K \)) — số cluster mong muốn. Bắt buộc đoán hoặc dùng heuristic (Bài 33).
• init — chiến lược init: "k-means++" (mặc định) hoặc "random". Có thể truyền mảng tự chọn nếu có domain knowledge.
• n_init — số lần chạy K-Means với init khác nhau, sklearn giữ lại lần có inertia thấp nhất. Mặc định 10 ở sklearn cũ; từ 1.4 mặc định là "auto" (10 nếu init="random", 1 nếu "k-means++"). Khuyến nghị set thủ công n_init=10 hoặc cao hơn để chắc.
• max_iter (mặc định 300) — giới hạn số vòng Lloyd's. Thường convergence sớm hơn nhiều, không cần đụng.
• tol (mặc định 1e-4) — ngưỡng dừng theo Frobenius norm của thay đổi centroid giữa hai vòng.
• random_state — seed cho init. Bắt buộc set nếu cần reproducible — kết quả K-Means phụ thuộc seed.
• algorithm — "lloyd" (mặc định) hoặc "elkan" (tăng tốc bằng bất đẳng thức tam giác, chỉ nhanh hơn khi dữ liệu well-clustered và \( K \) lớn).

K-Means dùng Euclidean distance — mọi feature đóng góp vào khoảng cách theo đơn vị gốc. Feature có range lớn sẽ dominate.

Ví dụ: dataset có hai feature, tuổi (20–60) và thu nhập (10 triệu – 1 tỉ). Khoảng cách hai sample chênh 5 triệu thu nhập = \( 5{,}000{,}000 \) đơn vị; chênh 30 tuổi chỉ = 30. Hệ quả: K-Means chỉ thấy thu nhập, hoàn toàn bỏ qua tuổi.

Giải pháp chuẩn: StandardScaler (Bài 8) trước khi K-Means. Mọi feature về cùng scale (\( \mu = 0, \sigma = 1 \)) → khoảng cách cân đối.

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(n_clusters=3, n_init=10, random_state=42)),
])
pipe.fit(X)
labels = pipe.named_steps["kmeans"].labels_

Khi nào KHÔNG standardize: khi mọi feature đã cùng đơn vị có ý nghĩa (vd pixel intensity 0–255, embedding vector từ cùng một encoder). Khi đó scale chênh lệch là tín hiệu thật.

MinMaxScaler cũng dùng được, nhưng nhạy outlier hơn StandardScaler. Với data có outlier nặng, dùng RobustScaler hoặc loại outlier trước (Bài 12).

Câu hỏi đầu tiên khi dùng K-Means: chọn \( K \) bằng cách nào? Không có câu trả lời tuyệt đối. Bài 33 đào sâu; tóm tắt nhanh các hướng:

• Elbow method — chạy K-Means với \( K = 1, 2, \ldots \), plot inertia theo \( K \). Inertia luôn giảm khi tăng \( K \) (\( K = n \) → inertia = 0). Tìm "elbow" — điểm mà thêm cluster không giảm inertia đáng kể nữa.
• Silhouette score — đo độ "chặt" của cluster và độ "tách" giữa các cluster bằng một số trong \( [-1, 1] \). Chọn \( K \) cho silhouette cao nhất.
• Gap statistic — so sánh inertia với inertia của data ngẫu nhiên cùng range.
• Domain knowledge — quan trọng nhất. Marketing muốn 4 phân khúc khách hàng → \( K = 4 \), bất kể elbow nói gì.

Không có "đúng K". Khác lựa chọn \( K \) khác nhau cho insight khác nhau — đôi khi chạy nhiều \( K \) và đọc kết quả để chọn.

K-Means đơn giản và nhanh, nhưng có ràng buộc rõ ràng. Phải biết để chọn thuật toán phù hợp.

• Phải biết \( K \) trước — không tự tìm. Sai \( K \) → kết quả vô nghĩa.
• Giả định cluster hình cầu (spherical) — vì dùng Euclidean và mean, K-Means ngầm giả định mỗi cluster có hình dạng tròn (hoặc cầu trong nhiều chiều), kích thước tương đương, mật độ tương đương. Với cluster phi tuyến (vòng cung, hai vành trăng — make_moons), K-Means thất bại. DBSCAN (Bài 35) hợp hơn cho trường hợp này.
• Nhạy với outlier — centroid là mean, nên một outlier xa có thể kéo centroid lệch. Hệ quả: outlier có thể chiếm một cluster riêng (lãng phí), hoặc làm cluster lân cận biến dạng. Loại outlier trước hoặc dùng K-Medoids (centroid là một điểm thực) khi cần robust.
• Local minima — Lloyd's chỉ cho local optimum. Init khác → kết quả khác. Giảm rủi ro bằng n_init lớn (10–20) và K-Means++.
• Phụ thuộc scale — như mục 10.
• Cluster size không cân đối — K-Means có xu hướng chia thành các cluster kích thước tương đương. Nếu data có một cluster lớn 90% và một cluster nhỏ 10%, K-Means thường cắt cluster lớn để cân đối — kết quả sai.
• High-dimensional data — Euclidean distance mất ý nghĩa khi \( d \) rất lớn (curse of dimensionality). Cân nhắc PCA (Bài 36) hoặc đổi metric.
• Chỉ cho hard assignment — mỗi điểm thuộc đúng một cluster. Không có khái niệm "xác suất thuộc cluster nào". Gaussian Mixture Model (GMM) cho soft assignment.

K-Means chuẩn mỗi vòng Lloyd's phải quét toàn bộ \( n \) sample để update centroid → tốn khi \( n \) lên hàng triệu.

MiniBatchKMeans (Sculley, 2010) — variant scale tốt hơn:

• Mỗi vòng lấy mini-batch ngẫu nhiên (mặc định 1024 sample) thay vì toàn bộ.
• Update centroid theo running average với learning rate giảm dần.
• Nhanh hơn nhiều lần với \( n \) lớn, dùng ít RAM hơn (không cần load hết dataset).
• Đổi lại: inertia thường hơi cao hơn K-Means chuẩn (khoảng 1–5%). Trong hầu hết ứng dụng, sai số này chấp nhận được.

from sklearn.cluster import MiniBatchKMeans

mbk = MiniBatchKMeans(
    n_clusters=10,
    batch_size=1024,
    n_init=3,
    max_iter=100,
    random_state=42,
)
mbk.fit(X_large)

Quy tắc: \( n \lesssim 10^4 \) — dùng KMeans. \( n \gtrsim 10^5 \) — cân nhắc MiniBatchKMeans.

Các thuộc tính hữu ích sau khi fit:

• kmeans.labels_ — cluster ID cho mỗi sample train, shape (n,).
• kmeans.cluster_centers_ — toạ độ \( K \) centroid, shape (K, d). Đọc được để hiểu "tâm" mỗi nhóm thế nào.
• kmeans.inertia_ — WCSS sau training. Dùng cho Elbow (Bài 33).
• kmeans.n_iter_ — số vòng Lloyd's tới convergence. Nếu chạm max_iter → có thể chưa converge, tăng max_iter.

Predict cho data mới:

kmeans.predict(X_new)        # cluster ID cho moi sample moi
kmeans.transform(X_new)      # khoang cach toi K centroid, shape (n_new, K)
kmeans.fit_predict(X)        # fit + predict trong 1 step

Một ứng dụng phái sinh: anomaly detection bằng K-Means — fit trên data "bình thường", sample mới có \( \min_k \|\mathbf{x}_{new} - \boldsymbol{\mu}_k\| \) lớn bất thường → coi là anomaly. Đơn giản hơn Isolation Forest, đủ dùng cho nhiều case.

• Customer segmentation — phân khúc khách hàng dựa trên hành vi mua, RFM (Recency, Frequency, Monetary), demographics. Sau đó marketing thiết kế chiến dịch cho từng segment.
• Image color quantization — giảm số màu của ảnh xuống \( K \) màu đại diện. Mỗi pixel (R, G, B) là một sample 3 chiều, K-Means tìm \( K \) màu trung tâm, thay mỗi pixel bằng centroid gần nhất. Dùng cho compression, dithering, stylization.
• Document clustering — gom văn bản theo topic. Mỗi văn bản biểu diễn bằng TF-IDF vector hoặc embedding, K-Means cho topic clusters. Baseline trước khi dùng LDA hoặc embedding-based topic modeling.
• Anomaly detection — như mục 14.
• Vector quantization / compression — codebook learning trong audio coding, image compression cổ điển (vd VQ-VAE base idea).
• Tiền xử lý cho supervised — cluster ID làm feature mới (one-hot hoặc target encoding) để supervised model học. Đôi khi tăng accuracy đáng kể.
• Bin centroid trong vector search — IVF index trong FAISS dùng K-Means để chia không gian thành \( K \) cell, truy vấn chỉ scan các cell gần nhất.

Demo 1 — K-Means trên blob data sinh sẵn:

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

# 300 sample, 3 cluster that
X, y_true = make_blobs(
    n_samples=300, centers=3, cluster_std=0.8, random_state=42
)

kmeans = KMeans(n_clusters=3, n_init=10, random_state=42)
labels = kmeans.fit_predict(X)
centers = kmeans.cluster_centers_

print(f"Inertia (WCSS): {kmeans.inertia_:.2f}")
print(f"So vong lap: {kmeans.n_iter_}")
print(f"Toa do centroid:\n{centers}")

# Plot — moi cluster mot mau, centroid danh dau X den
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="viridis", s=30, alpha=0.7)
plt.scatter(centers[:, 0], centers[:, 1], c="black", marker="X", s=200, label="centroid")
plt.title("K-Means clustering (K=3)")
plt.legend()
plt.show()

Kết quả điển hình: 3 cluster gần khớp với 3 blob gốc; chỉ vài sample biên có thể bị gán nhầm. Inertia thấp (vài trăm), convergence trong <10 vòng.

Demo 2 — Pipeline StandardScaler + KMeans trên iris, treat như unsupervised (drop label):

from sklearn.datasets import load_iris
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

iris = load_iris()
X = iris.data            # 150 sample, 4 feature
y_true = iris.target     # KHONG dung cho fit, chi de so sanh sau

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(n_clusters=3, n_init=10, random_state=42)),
])
pipe.fit(X)
labels = pipe.named_steps["kmeans"].labels_

# Cluster ID khong nhat thiet trung label goc (cluster 0 cua KMeans co the la setosa hoac versicolor)
# Tinh confusion matrix de doi chieu
from collections import Counter
for cluster_id in range(3):
    members = y_true[labels == cluster_id]
    print(f"Cluster {cluster_id}: {Counter(members)}")

Trên iris, K-Means thường phân biệt rất rõ setosa (cluster sạch) còn versicolor và virginica bị chồng lấn — đúng với thực tế hai loài này gần nhau về morphology.

Bài 1 — K-Means trên iris. Load iris, drop label. Pipeline StandardScaler + KMeans(n_clusters=3, n_init=10, random_state=42). Tính confusion matrix giữa labels_ và y_true (cần map cluster ID sang label tốt nhất — dùng scipy.optimize.linear_sum_assignment hoặc thử cả 6 hoán vị). Tỉ lệ accuracy là bao nhiêu? Cluster nào "sạch" nhất?

Bài 2 — Vary K, lưu inertia (preview Bài 33). Trên iris đã scale, chạy KMeans với \( K = 1, 2, \ldots, 10 \), n_init=10, random_state=42. Lưu inertia_ theo \( K \), plot biểu đồ. Có thấy "elbow" rõ ở \( K = 3 \) không? Inertia tại \( K = 1 \) bằng bao nhiêu so với X.var() * n?

Bài 3 — MiniBatchKMeans cho 10.000 sample. Sinh dữ liệu bằng make_blobs(n_samples=10000, centers=10, n_features=20, random_state=42). So sánh:

• KMeans(n_clusters=10, n_init=10) — đo thời gian fit bằng time.perf_counter() và inertia cuối.
• MiniBatchKMeans(n_clusters=10, batch_size=512, n_init=10) — đo tương tự.

Tỉ lệ tốc độ khoảng bao nhiêu? Chênh lệch inertia khoảng %?

Bài 4 — Sensitivity với init. Trên blob 4 cluster đè lên nhau (make_blobs(n_samples=500, centers=4, cluster_std=2.0, random_state=42)), chạy KMeans(n_clusters=4) với:

• init="random", n_init=1, random_state=k cho \( k = 0, 1, \ldots, 19 \).
• init="k-means++", n_init=1, random_state=k cho \( k = 0, 1, \ldots, 19 \).

So sánh phân phối inertia 20 lần chạy của hai chiến lược (mean, std, max). K-Means++ ổn định hơn bao nhiêu?

Bài 5 — K-Means thất bại trên data phi cầu. Sinh make_moons(n_samples=300, noise=0.05, random_state=42). Chạy KMeans(n_clusters=2) và plot kết quả. Hai cluster KMeans tìm được có khớp hai vành trăng không? Giải thích bằng giả định cluster cầu của K-Means.

Bài 33: Đánh giá clustering — Elbow Method và Silhouette Score — đi sâu vào câu hỏi "chọn \( K \) bao nhiêu" và "kết quả clustering có tốt không". Elbow plot trên inertia, silhouette score \( \in [-1, 1] \), và khi nào hai phương pháp này không đồng ý nhau.