Học không giám sát: K-means & PCA

Mở đầu: khi không ai chấm điểm đúng/sai cho bạn

Ba bài trước đều có một thứ xa xỉ: đáp án đúng đi kèm mỗi điểm dữ liệu — giá nhà thật (Bài 1), nhãn đậu/rớt thật (Bài 3). Nhưng phần lớn dữ liệu một doanh nghiệp thu thập được — log truy cập, lịch sử mua hàng, ảnh chưa gắn thẻ — không có đáp án nào đi kèm cả. Không ai ngồi gắn nhãn "khách hàng nhóm A" cho hàng triệu giao dịch. Câu hỏi đổi hẳn: không còn là "dự đoán con số/nhãn cho trước", mà là "tự tìm cấu trúc ẩn trong đống dữ liệu thô".

Bài này học hai công cụ nền tảng nhất của học không giám sát. K-means tự động gom điểm dữ liệu thành các nhóm (cụm) mà không cần ai chỉ trước nhóm nào là nhóm nào — và bạn sẽ thấy nó chắc chắn hội tụ nhưng không chắc chắn đúng, một phân biệt tinh tế sẽ ám ảnh mọi thuật toán lặp bạn gặp sau này. PCA giải bài toán ngược lại: dữ liệu có hàng chục cột, làm sao nén còn vài cột mà không mất thông tin quan trọng? Cả hai đều được xây từ số 0, kết thúc bằng demo k-means chạy từng bước bạn tự bấm, và một đám mây điểm 3D bạn tự xoay để thấy PCA "nhìn thấy" mặt phẳng ẩn bên trong.

1. Ba nhánh học máy nhìn từ dữ liệu

Điểm phân biệt ba nhánh học máy không nằm ở thuật toán — nó nằm ở dữ liệu cho máy được gì:

Vì sao học không giám sát quan trọng đến vậy: phần lớn dữ liệu doanh nghiệp thực tế không có nhãn. Gắn nhãn tay cho hàng triệu bản ghi là công việc tốn kém, chậm, và thường bất khả thi ở quy mô lớn — trong khi dữ liệu thô (không nhãn) gần như miễn phí, sinh ra liên tục từ mọi tương tác. Học không giám sát là cách duy nhất để khai thác phần dữ liệu áp đảo này.

2. K-means từng bước: gán rồi cập nhật, lặp lại

Bài toán: cho $N$ điểm dữ liệu và một số $k$ (số cụm muốn có), tìm $k$ "tâm cụm" (centroid) sao cho mỗi điểm ở gần tâm cụm của nó hơn mọi tâm cụm khác. Thuật toán K-means giải bài này bằng một vòng lặp hai bước cực đơn giản, lặp tới khi ổn định:

1. Assign (gán): mỗi điểm dữ liệu được gán vào cụm có centroid gần nó nhất (khoảng cách Euclid).
2. Update (cập nhật): mỗi centroid dời tới đúng vị trí trung bình của mọi điểm vừa được gán vào cụm đó.

Lặp lại 2 bước cho tới khi không còn điểm nào đổi cụm. Đại lượng theo dõi mức độ "gọn" của cách chia hiện tại gọi là inertia — tổng bình phương khoảng cách từ mỗi điểm tới centroid của nó:

$$\text{inertia} = \sum_{i=1}^{N} \|x_i - c_{\text{gan}(i)}\|^2$$

function kmeansStep(points, centroids) {
  // 1. Assign: moi diem ve centroid gan nhat (khoang cach Euclid binh phuong)
  const assign = points.map(p => {
    let best = -1, bd = Infinity;
    centroids.forEach((c, k) => {
      const d = (p.x-c.x)**2 + (p.y-c.y)**2;
      if (d < bd) { bd = d; best = k; }
    });
    return best;
  });
  // 2. Update: centroid moi = trung binh cong cac diem vua duoc gan
  const sums = centroids.map(() => ({x:0, y:0, n:0}));
  points.forEach((p, i) => { const s=sums[assign[i]]; s.x+=p.x; s.y+=p.y; s.n++; });
  const newCentroids = sums.map((s, k) => s.n ? {x: s.x/s.n, y: s.y/s.n} : centroids[k]);
  return { assign, centroids: newCentroids };
}
// Goi lap lai toi khi assign khong doi nua -> inertia CHAC CHAN da hoi tu

Sự thật toán học đẹp và quan trọng nhất bài: mỗi bước assign-rồi-update không bao giờ làm inertia tăng — assign luôn chọn centroid gần nhất (không thể làm tổng khoảng cách tệ hơn), và update dời centroid về đúng điểm cực tiểu hoá tổng bình phương khoảng cách của cụm đó (trung bình cộng chính là điểm tối ưu này). Vì inertia giảm dần (hoặc đứng yên) và có cận dưới ($\geq 0$), thuật toán chắc chắn dừng lại sau hữu hạn bước. Chạy trên bộ dữ liệu 24 điểm — 3 cụm Gaussian thật quanh $(2,2)$, $(8,2)$, $(5,8)$ — với centroid khởi tạo gần đúng 3 cụm, self-test đối chiếu:

Chỉ 2 bước để hội tụ, inertia giảm đơn điệu đúng như lý thuyết dự đoán. Nhưng "chắc chắn dừng" và "chắc chắn tìm được cách chia TỐT NHẤT" là hai điều hoàn toàn khác nhau.

Câu hỏi còn bỏ ngỏ: chọn $k$ bao nhiêu? Vẽ inertia tốt nhất tìm được (nhiều lần khởi tạo lại) theo từng giá trị $k$ — phương pháp elbow (khuỷu tay) — trên đúng bộ dữ liệu 3 cụm:

Từ $k=2 \to 3$, inertia rơi mạnh ($169 \to 25$, giảm gần $7$ lần) — đúng lúc số cụm chạm số cụm THẬT của dữ liệu. Từ $k=3$ trở đi, mỗi lần tăng $k$ chỉ gọt thêm chút ít ($25 \to 18 \to 16 \to 12$) vì đang chia nhỏ những cụm vốn đã hợp lý — đó là "khuỷu tay" của đồ thị, điểm mà lợi ích biên giảm hẳn tốc độ. Giới hạn thật của elbow method: với dữ liệu đời thực (không sạch như 3 cụm Gaussian tách biệt), khuỷu tay hiếm khi rõ ràng — đường cong tụt dần đều đặn, người dùng phải tự phán đoán chủ quan, và hai người nhìn cùng một đồ thị có thể chọn hai giá trị $k$ khác nhau.

3. K-means thất bại khi nào

K-means chia không gian bằng mặt phẳng phân giới giữa các centroid (mỗi điểm thuộc về centroid gần nhất) — hình dạng cụm nó tìm được luôn có xu hướng hình cầu/lồi. Với dữ liệu thật sự có cấu trúc dạng đó, k-means gần như hoàn hảo, như 3 cụm Gaussian ở trên. Nhưng thử áp k-means ($k=2$) lên hai vòng tròn đồng tâm (vòng trong bán kính $\approx 1$, vòng ngoài bán kính $\approx 4$, cùng tâm) — về mặt thị giác con người, đây là 2 nhóm rõ ràng:

// 20 diem vong trong (r~1) + 20 diem vong ngoai (r~4), cung tam
const result = kmeans(ringPoints, [{x:1,y:0}, {x:-1,y:0}]);
// Centroid cuoi: (~1.57, 0.24) va (~-1.57, -0.24) - CHIA THEO TRAI/PHAI
// Purity moi cum: 10 vong trong + 10 vong ngoai (50/50) - THAT BAI HOAN TOAN

K-means chia dữ liệu thành nửa trái / nửa phải (centroid cuối cùng nằm đối xứng qua tâm theo trục ngang) — hoàn toàn phớt lờ cấu trúc "trong/ngoài" mà mắt người thấy ngay lập tức. Mỗi cụm kết quả chứa đúng $50\%$ điểm vòng trong và $50\%$ điểm vòng ngoài — độ tinh khiết (purity) chỉ ngang mức đoán ngẫu nhiên. Lý do sâu xa: hai vòng tròn không thể tách bằng một đường thẳng/mặt phẳng nào — mà k-means, giống hệt decision boundary tuyến tính của Bài 3, về bản chất chỉ vẽ được ranh giới thẳng giữa các centroid.

Bài học rút ra: k-means là baseline nhanh và dễ hiểu, không phải câu trả lời vạn năng cho mọi bài toán phân cụm. Dữ liệu có cấu trúc phi tuyến (vòng tròn, xoắn ốc) cần thuật toán khác (DBSCAN, spectral clustering — ngoài phạm vi series này) hoặc cần biến đổi dữ liệu trước (ví dụ chuyển toạ độ Cartesian sang toạ độ cực biến bán kính thành một trục riêng).

4. PCA: nén dữ liệu theo hướng giữ nhiều thông tin nhất

Bài toán ngược của k-means: thay vì nhóm các điểm, PCA (phân tích thành phần chính) nén các cột (đặc trưng). Với dữ liệu nhiều chiều, câu hỏi là: nếu chỉ được giữ lại 1 hoặc 2 hướng chiếu, hướng nào giữ được nhiều thông tin nhất? "Thông tin" ở đây được đo bằng phương sai (độ trải rộng) — hướng nào dữ liệu trải rộng nhất chính là hướng phân biệt các điểm rõ nhất, nên là hướng đáng giữ lại nhất khi phải bỏ bớt chiều.

Hướng phương sai lớn nhất chính là eigenvector ứng với eigenvalue lớn nhất của ma trận hiệp phương sai (covariance matrix) của dữ liệu. Không cần đại số tuyến tính hình thức để tìm nó — power iteration làm được bằng một phép lặp cực đơn giản: nhân lặp đi lặp lại một vector với ma trận rồi chuẩn hoá về độ dài 1:

$$v_{t+1} = \frac{Av_t}{\|Av_t\|}$$

function powerIteration(cov, iters) {
  let v = [1, 0];                          // vector khoi dau bat ky, khac 0
  for (let i = 0; i < iters; i++) {
    const Av = [cov.cxx*v[0] + cov.cxy*v[1], cov.cxy*v[0] + cov.cyy*v[1]];
    const norm = Math.sqrt(Av[0]**2 + Av[1]**2);
    v = [Av[0]/norm, Av[1]/norm];          // chuan hoa ve do dai 1 moi buoc
  }
  return v;                                // hoi tu ve eigenvector eigenvalue LON NHAT
}

Trực giác: mỗi lần nhân, thành phần của $v$ nằm dọc hướng eigenvalue lớn nhất được "khuếch đại" nhiều hơn mọi hướng khác — lặp đủ nhiều, $v$ bị kéo về gần sát hướng đó. Tính tay trên ma trận đối xứng $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ (eigenvector đúng đã biết trước: $(0{,}7071,\ 0{,}7071)$ ứng với eigenvalue $3$), xuất phát từ $v_0=(1,0)$:

Chỉ sau 6 bước nhân-rồi-chuẩn-hoá, $v$ đã bám sát $(0{,}7071,\ 0{,}7071)$ và Rayleigh quotient khớp chính xác eigenvalue $3$ — không cần công thức đại số nào phức tạp hơn phép nhân ma trận-vector. Áp đúng kỹ thuật này lên một bộ 40 điểm dữ liệu 2D tương quan thật (kéo dài theo hướng $\approx 30°$), power iteration cho ra vector $(0{,}8831,\ 0{,}4692)$ — góc thực tế $\approx 28°$, khớp hướng đã tạo dữ liệu — với eigenvalue $7{,}4104$, chiếm $94{,}4\%$ tổng phương sai. Giữ lại đúng 1 chiều (thay vì 2) mà vẫn giữ được hơn $94\%$ thông tin — đó là sức mạnh của PCA.

5. Thực hành: K-means từng bước & PCA xoay 3D

Demo A — đúng bộ 3 cụm Gaussian của Mục 2. Chọn cách khởi tạo (Tốt/Xấu), rồi bấm Bước để chạy từng vòng assign–update một, xem inertia giảm dần (hoặc mắc kẹt) qua từng lần bấm:

Demo B — 60 điểm 3D gần như nằm phẳng trên một mặt phẳng nghiêng (không trùng trục nào), cộng thêm chút nhiễu vuông góc mặt phẳng đó. Kéo chuột để xoay đám mây điểm, quan sát nó gần như "phẳng" từ đúng góc nhìn; bấm Chiếu xuống 2D để xem PCA lột bỏ chiều nhiễu:

Đối chiếu công nghiệp: hệ sinh thái Python cho học máy cổ điển (k-means, PCA, hồi quy phi-deep-learning) là scikit-learn (sklearn) — khác với PyTorch chuyên cho deep learning mà series dùng từ Bài 6 trở đi. Bản 1-1 với hai demo trên:

# Doi chieu 1-1 voi Demo A/B - cai dat: pip install scikit-learn
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
import numpy as np

# Demo A: k-means (sklearn dung k-means++ mac dinh - tranh dung cach khoi tao XAU)
X = np.array([...])  # 24 diem, 3 cum Gaussian
km = KMeans(n_clusters=3, init="k-means++", n_init=10, random_state=7)
km.fit(X)
print(km.inertia_)          # ~25.17 - khop Demo A voi khoi tao TOT

# Demo B: PCA giu lai 2 chieu nhieu thong tin nhat trong du lieu 3D
X3d = np.array([...])  # 60 diem gan phang trong khong gian 3D
pca = PCA(n_components=2)
X2d = pca.fit_transform(X3d)
print(pca.explained_variance_ratio_.sum())  # ~0.9842 - khop Demo B (giu 98.42%)

Tóm lược

• ✅ 3 nhánh học máy phân biệt bởi dữ liệu cho máy được gì: có nhãn, không nhãn, hay chỉ phần thưởng thưa — phần lớn dữ liệu doanh nghiệp thuộc nhánh không nhãn.
• ✅ K-means hội tụ CHẮC CHẮN (inertia không bao giờ tăng, có cận dưới $0$) nhưng không chắc chắn tối ưu toàn cục — khởi tạo xấu khiến kết quả tệ hơn tới $7{,}6$ lần dù thuật toán chạy hoàn toàn đúng; k-means++ và nhiều lần khởi tạo lại là cách giảm rủi ro.
• ✅ Elbow method chọn $k$ bằng cách tìm điểm lợi ích biên giảm mạnh — hữu ích nhưng chủ quan trên dữ liệu đời thực không sạch.
• ✅ K-means thất bại trên cụm phi lồi (vòng tròn đồng tâm cho purity $50/50$, ngang đoán ngẫu nhiên) vì nó chỉ vẽ được ranh giới thẳng — baseline nhanh, không phải câu trả lời vạn năng.
• ✅ PCA tìm hướng phương sai lớn nhất bằng power iteration (nhân lặp ma trận-vector, không cần đại số tuyến tính hình thức) — 6 bước hội tụ chính xác trên ví dụ tính tay; giữ 2/3 chiều mà vẫn giữ $98{,}42\%$ thông tin trên dữ liệu 3D gần phẳng.
• ✅ Quên chuẩn hoá trước PCA khiến cột đơn vị lớn (lương tính bằng đồng) nuốt chửng hoàn toàn cột đơn vị nhỏ (tuổi) — luôn z-score hoá trước khi chạy PCA trên dữ liệu đa đơn vị.