[DS Blog #37] Học Máy Không Giám Sát (Unsupervised Learning) & Giảm Chiều Dữ Liệu: Phân Cụm K-Means, DBSCAN, GMM, Giải Mã Toán Học PCA vs. t-SNE vs. UMAP & Isolation Forest

1. Bối cảnh thực tế (Context & Problem Statement)

Trong thực tế doanh nghiệp, phần lớn dữ liệu thu thập được ( $> 80\%$ ) đều hoàn toàn không có nhãn (Unlabeled Data):

Hàng triệu khách hàng giao dịch trên sàn thương mại điện tử nhưng không có nhãn "Khách hàng mua sắm bốc đồng" hay "Khách hàng săn sale chuyên nghiệp".
Hàng trăm nghìn log mạng server nhưng không có nhãn sẵn "Đây là cuộc tấn công DDoS".
Dữ liệu hình ảnh, gen y học hoặc văn bản có hàng nghìn chiều thuộc tính (High-Dimensional Data) gây ra "Lời nguyền số chiều" (Curse of Dimensionality): Không gian dữ liệu trở nên cực kỳ thưa thớt, khoảng cách Euclidean giữa mọi cặp điểm đều xấp xỉ bằng nhau, khiến các mô hình học máy bị mất hoàn toàn khả năng phân biệt.

Học máy không giám sát (Unsupervised Learning) và Giảm chiều dữ liệu (Dimensionality Reduction) ra đời để giải quyết bài toán:

Tự động khám phá các cấu trúc ẩn và phân cụm đối tượng tự nhiên (Clustering).
Nén không gian từ hàng nghìn chiều xuống 2D/3D để trực quan hóa mà vẫn bảo toàn tối đa thông tin (PCA, t-SNE, UMAP).
Tự động phát hiện các đối tượng cá biệt, gian lận hoặc lỗi hệ thống (Anomaly Detection).

2. Các Khái Niệm & Cơ Chế Cốt Lõi

2.1. Các Thuật Toán Phân Cụm Cốt Lõi (Clustering Algorithms)

1. K-Means & K-Means++ Initialization

Nguyên lý: Phân chia $N$ điểm dữ liệu thành $K$ cụm sao cho tối thiểu hóa tổng bình phương khoảng cách từ các điểm tới tâm cụm tương ứng (Inertia / Within-Cluster Sum of Squares - WCSS): $\mathcal{J} = \sum_{j=1}^{K} \sum_{x_i \in C_j} \| x_i - \mu_j \|^2$
Thuật toán Lloyd (Lặp 2 bước):
1. Gán nhãn (Assignment): Gán mỗi điểm $x_i$ vào cụm có tâm $\mu_j$ gần nhất.
2. Cập nhật tâm (Update): Tính lại tâm $\mu_j$ bằng trung bình cộng tọa độ các điểm trong cụm.
K-Means++ (Khởi tạo tâm thông minh): Chọn tâm đầu tiên ngẫu nhiên; các tâm tiếp theo được chọn với xác suất tỷ lệ thuận với bình phương khoảng cách tới tâm gần nhất đã chọn ( $D(x)^2$ ) $\rightarrow$ Tránh việc các tâm ban đầu nằm quá sát nhau, giúp thuật toán hội tụ nhanh gấp $2\times$ và tránh kẹt tại cực tiểu địa phương kém.
Xác định số cụm $K$ tối ưu:
- Elbow Method (Phương pháp điểm khuỷu tay): Tìm điểm uốn mà tại đó WCSS giảm chậm lại rõ rệt.
- Silhouette Score: Đo lường độ gắn kết nội cụm ( $a$ ) so với độ tách biệt ngoại cụm ( $b$ ): $s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \in [-1, 1]$ (Giá trị $s \approx 1$ chứng tỏ phân cụm cực kỳ rõ ràng; $s \le 0$ chứng tỏ điểm bị gán nhầm cụm).

2. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Khắc phục nhược điểm lớn nhất của K-Means: K-Means chỉ tìm được các cụm hình cầu lồi (Spherical shapes) và cực kỳ nhạy cảm với Outliers.

Nguyên lý: Phân cụm dựa trên Mật độ không gian với 2 tham số: Bán kính lân cận $\epsilon$ (Epsilon) và Số điểm tối thiểu trong vùng $MinPts$ .
Phân loại 3 loại điểm trong DBSCAN:
1. Core Point (Điểm lõi): Có ít nhất $MinPts$ điểm nằm trong bán kính $\epsilon$ .
2. Border Point (Điểm biên): Nằm trong bán kính $\epsilon$ của một Core Point, nhưng bản thân nó có $< MinPts$ điểm lân cận.
3. Noise Point (Điểm nhiễu / Outlier): Không phải Core Point cũng không phải Border Point $\rightarrow$ Tự động bị cô lập làm ngoại lai (Gán nhãn $-1$ ).
Ưu điểm vượt trội: Tự động xác định số lượng cụm $K$ , tìm được các cụm có hình dạng ngoằn ngoèo, hình vành khuyên phi tuyến phức tạp và tự động loại bỏ rác nhiễu!

K-MEANS (Chỉ chia được hình cầu tuyến tính):    DBSCAN (Tìm được hình dạng bất kỳ + Lọc nhiễu):
         +-------------+                                .   . (Noise: -1)
        /   Cluster 1   \                              (  Cụm hình chữ C  )
       |       (*)       |                              .                 . (Noise)
        \               /                                 ( Cụm hình tròn )
         +-------------+                                .

3. Gaussian Mixture Models (GMM - Phân Cụm Mềm)

Khác với K-Means là phân cụm cứng (Hard Clustering: 1 điểm chỉ thuộc về đúng 1 cụm), GMM là Phân cụm mềm (Soft Clustering / Probabilistic): Một điểm có xác suất $70\%$ thuộc Cụm 1 và $30\%$ thuộc Cụm 2.
Mỗi cụm được mô hình hóa bằng một phân phối chuẩn đa chiều $\mathcal{N}(\mu_k, \Sigma_k)$ với ma trận hiệp phương sai $\Sigma_k$ riêng (cho phép cụm có hình bầu dục elip nghiêng tùy ý).
Huấn luyện thông qua thuật toán Kỳ vọng - Tối đa hóa (Expectation-Maximization - EM).

2.2. Các Kỹ Thuật Giảm Chiều Dữ Liệu (Dimensionality Reduction)

[Dữ liệu gốc: 1,000 chiều]
             |
             +---> [PCA (Tuyến tính)] -------> Bảo toàn Phương sai toàn cục (Global Variance)
             |
             +---> [t-SNE (Phi tuyến)] ------> Bảo toàn Cấu trúc lân cận cục bộ (Local Manifold)
             |
             +---> [UMAP (Hình học Riemann)] -> Cân bằng Cả Cục bộ lẫn Toàn cục (Siêu nhanh)

1. Principal Component Analysis (PCA - Phân Tích Thành Phần Chính)

Bản chất toán học: Tìm một hệ trục tọa độ trực giao mới sao cho khi chiếu dữ liệu lên đó, phương sai của dữ liệu là lớn nhất (Bảo toàn tối đa lượng thông tin).
Quy trình 4 bước:
1. Chuẩn hóa dữ liệu về trung bình bằng $0$ (Zero-mean centering): $X_{\text{norm}} = X - \bar{X}$ .
2. Tính ma trận hiệp phương sai: $\Sigma = \frac{1}{n} X_{\text{norm}}^T X_{\text{norm}} \in \mathbb{R}^{d \times d}$ .
3. Phân rã giá trị riêng & vector riêng (Eigenvalue Decomposition) hoặc dùng SVD (Singular Value Decomposition): $\Sigma v_i = \lambda_i v_i$
4. Sắp xếp các vector riêng $v_i$ theo giá trị riêng $\lambda_i$ giảm dần. Chọn $K$ vector đầu tiên làm các Thành phần chính (Principal Components).

2. t-SNE vs. UMAP (Giảm Chiều Phi Tuyến Phục Vụ Trực Quan Hóa)

t-SNE (t-Distributed Stochastic Neighbor Embedding):
- Chuyển đổi khoảng cách Euclidean giữa các điểm trong không gian nhiều chiều thành Xác suất có điều kiện $p_{j|i}$ theo phân phối Gauss.
- Trong không gian 2D đích, sử dụng Phân phối Student-t với 1 bậc tự do (Cauchy Distribution) để tính xác suất $q_{ij}$ nhằm giải quyết triệt để "Vấn đề quá đông đúc" (Crowding Problem).
- Tối thiểu hóa độ phân kỳ Kullback-Leibler (KL Divergence): $\mathcal{L} = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}}$ .
UMAP (Uniform Manifold Approximation and Projection):
- Dựa trên nền tảng hình học vi phân Riemann và Topo đại số (Fuzzy Simplicial Sets).
- Vượt trội hơn t-SNE: Vừa bảo toàn cấu trúc cụm cục bộ (Local) vừa giữ được mối quan hệ khoảng cách vĩ mô toàn cục (Global Structure), đồng thời tốc độ tính toán nhanh hơn t-SNE từ $10\times$ đến $50\times$ !

2.3. Phát Hiện Bất Thường Với Isolation Forest (iForest)

Triết lý đảo ngược độc đáo: Thay vì xây dựng mô hình mô tả dữ liệu bình thường rồi xem điểm nào khác biệt, Isolation Forest chủ động "cô lập" các điểm bất thường.
Cơ chế hoạt động:
1. Điểm bất thường (Outlier) có 2 đặc tính: Rất ít và Nằm cách xa số đông.
2. Thuật toán liên tục chọn ngẫu nhiên một thuộc tính và chọn ngẫu nhiên một giá trị cắt (Random Split Threshold).
3. Điểm bất thường sẽ bị cô lập vào một lá cây rất nhanh sau rất ít lần cắt (Độ dài đường đi $h(x)$ trên cây rất ngắn).
4. Ngược lại, các điểm dữ liệu bình thường nằm dày đặc sẽ cần rất nhiều lần cắt sâu mới cô lập được.
Điểm bất thường (Anomaly Score): $s(x, n) = 2^{-\frac{\mathbb{E}(h(x))}{c(n)}}$ (Nếu $s(x) \approx 1 \rightarrow$ Chắc chắn là điểm bất thường; nếu $s(x) < 0.5 \rightarrow$ Điểm hoàn toàn bình thường).

CÔ LẬP ĐIỂM BẤT THƯỜNG (iForest):
Điểm Outlier (Ngoại lai) ---> Chỉ cần 2 lần cắt ngẫu nhiên là bị CÔ LẬP! (Độ sâu h = 2)
Điểm Normal (Bình thường) -> Cần tới 12 lần cắt ngẫu nhiên mới cô lập được! (Độ sâu h = 12)

3. Các Bảng Markdown So Sánh Chi Tiết

📊 Bảng 1: So Sánh Toàn Diện Các Thuật Toán Phân Cụm (Clustering)

Tiêu chí	K-Means / K-Means++	DBSCAN	Gaussian Mixture Models (GMM)	Hierarchical (Agglomerative)
Cần chỉ định trước số cụm $K$ ?	Bắt buộc ( $K$ )	Không cần (Tự tìm theo mật độ)	Bắt buộc ( $K$ )	Không cần (Cắt theo Dendrogram)
Hình dạng cụm có thể tìm	Chỉ tìm được hình cầu lồi (Spherical)	Bất kỳ hình dạng ngoằn ngoèo nào	Hình bầu dục / Elip định hướng	Đa dạng tùy theo Linkage criterion
Độ nhạy với Outliers / Nhiễu	Rất nhạy cảm (Bị kéo lệch tâm)	Tự động loại bỏ nhiễu ( $100\%$ Outlier-robust)	Trung bình (Bị ảnh hưởng bởi Outlier)	Khá nhạy cảm
Loại hình phân cụm	Phân cụm cứng (Hard: $0$ hoặc $1$ )	Phân cụm cứng	Phân cụm mềm (Xác suất $P(C_k \mid x)$ )	Phân cụm phân cấp cây
Độ phức tạp thuật toán	$O(N \cdot K \cdot d \cdot I)$ (Siêu nhanh)	$O(N \log N)$ với Spatial Index	$O(N \cdot K \cdot d^3)$ (Khá chậm)	$O(N^2 \log N)$ (Rất chậm trên data lớn)
Trường hợp sử dụng tối ưu	Phân khúc khách hàng đơn giản, Cỡ mẫu lớn	Dữ liệu địa lý GPS, Nhận diện cụm hình học, Lọc nhiễu	Dữ liệu có các cụm lồng ghép gối lên nhau	Xây dựng cây phân loại sinh học, Phân cấp tổ chức

📊 Bảng 2: So Sánh Các Thuật Toán Giảm Chiều Dữ Liệu (Dimensionality Reduction)

Tiêu chí	PCA (Principal Component Analysis)	t-SNE	UMAP	Autoencoders (Deep Learning)
Bản chất phép biến đổi	Tuyến tính thuần túy (Linear)	Phi tuyến tính (Non-linear)	Phi tuyến tính (Non-linear)	Phi tuyến tính sâu (Deep Non-linear)
Cấu trúc bảo toàn	Bảo toàn Phương sai toàn cục (Global Variance)	Bảo toàn Cấu trúc lân cận cục bộ (Local)	Bảo toàn CẢ Cục bộ lẫn Toàn cục	Phụ thuộc vào hàm Loss và Kiến trúc
Tốc độ tính toán	Siêu tốc ( $O(d^3)$ hoặc SVD $O(N d^2)$ )	Rất chậm ( $O(N^2)$ )	Nhanh ( $O(N \log N)$ )	Chậm (Cần huấn luyện mạng nơ-ron)
Khả năng biến đổi dữ liệu mới	Có hỗ trợ (`transform(X_new)`)	Không (Phải chạy lại từ đầu khi có data mới)	Có hỗ trợ (`transform(X_new)`)	Có hỗ trợ
Mục đích sử dụng chính	Tiền xử lý cho ML, Nén giảm nhiễu, Tránh đa cộng tuyến	Trực quan hóa đồ thị 2D/3D cụm dữ liệu phức tạp	Trực quan hóa 2D/3D, Tiền xử lý cụm cho Vector Embeddings	Nén biểu diễn phi tuyến phức tạp (Ảnh, Âm thanh)

📊 Bảng 3: So Sánh Các Phương Pháp Phát Hiện Bất Thường (Anomaly Detection)

Thuật toán	Cơ chế hoạt động	Độ phức tạp tính toán	Khả năng mở rộng (Scalability)	Xử lý dữ liệu đa chiều
Isolation Forest (iForest)	Cô lập ngẫu nhiên qua cây quyết định	$O(N \log N)$ (Siêu nhanh)	Xuất sắc nhất trên Big Data	Rất tốt
Local Outlier Factor (LOF)	So sánh mật độ cục bộ của điểm với $K$ lân cận	$O(N^2)$ (Chậm do tính khoảng cách)	Kém trên tập dữ liệu lớn	Kém do lời nguyền số chiều
One-Class SVM	Tìm siêu phẳng bao bọc tập dữ liệu bình thường	$O(N^2 - N^3)$	Kém trên tập dữ liệu lớn	Tốt (Nhờ Kernel Trick)
Statistical Z-Score / IQR	Đo độ lệch chuẩn so với giá trị trung bình	$O(N)$	Vô hạn	Chỉ dùng cho từng cột đơn lẻ (Univariate)

4. Best Practices & Kỹ Thuật Triển Khai Thực Chiến (Pro-Tips)

💡 Quy Tắc Bắt Buộc: Luôn Chuẩn Hóa Dữ Liệu Trước Khi Chạy PCA & K-Means

Tại sao? Phép tính khoảng cách Euclidean trong K-Means và phép tính phương sai trong PCA cực kỳ nhạy cảm với thang đo (Scale).
Nếu cột Thu_Nhap có giá trị từ $10,000,000$ đến $100,000,000$ trong khi cột Tuoi chỉ từ $18$ đến $65$ , thành phần chính của PCA và khoảng cách của K-Means sẽ bị chi phối $99.9\%$ bởi cột Thu Nhập, biến cột Tuổi thành vô nghĩa!
Khắc phục: Luôn sử dụng StandardScaler (hoặc RobustScaler nếu có nhiều Outlier) trước khi áp dụng:

from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline

# Luôn đóng gói vào Pipeline chuẩn mực:
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('pca', PCA(n_components=0.95)) # Giữ lại 95% tổng phương sai
])
X_pca = pipeline.fit_transform(X_raw)

💡 Kết Hợp Hoàn Hảo Giữa UMAP và HDBSCAN Cho Dữ Liệu Văn Bản / Vector Embeddings

Trong các bài toán gom cụm chủ đề tài liệu (Topic Modeling như Top2Vec, BERTopic):

Bước 1: Nén vector nhúng $1536$ -chiều (OpenAI Embeddings) xuống $5 - 10$ chiều bằng UMAP (loại bỏ nhiễu và nén cấu trúc hình học phi tuyến).
Bước 2: Chạy HDBSCAN trên không gian 5 chiều đó để tự động phân cụm chủ đề và gom các tài liệu rác vào nhóm nhiễu (Noise).

5. Góc Ôn Luyện Phỏng Vấn (Interview Corner)

❓ Câu hỏi 1: Giải thích nguyên lý toán học của Principal Component Analysis (PCA). Tại sao các thành phần chính (Principal Components) luôn trực giao đôi một với nhau và làm thế nào để chọn số lượng thành phần chính tối ưu bằng phương pháp Cumulative Explained Variance?

Gợi ý trả lời:
- Nguyên lý toán học:
  - PCA tìm kiếm các trục chiếu sao cho phương sai của dữ liệu trên trục đó là cực đại.
  - Về mặt đại số tuyến tính, các trục thành phần chính chính là các vector riêng (Eigenvectors) của Ma trận hiệp phương sai $\Sigma$ của tập dữ liệu đã chuẩn hóa.
  - Do ma trận hiệp phương sai $\Sigma = \frac{1}{n} X^T X$ là một Ma trận đối xứng thực (Symmetric Matrix), theo Định lý Phổ (Spectral Theorem), tất cả các vector riêng ứng với các giá trị riêng khác nhau của một ma trận đối xứng thực bắt buộc phải trực giao đôi một với nhau ( $v_i \cdot v_j = 0$ với $i \ne j$ ).
- Ý nghĩa của tính trực giao: Đảm bảo rằng mỗi thành phần chính mới mang lại lượng thông tin hoàn toàn độc lập, triệt tiêu $100\%$ hiện tượng đa cộng tuyến (Multicollinearity) giữa các biến.
- Cách chọn số chiều $K$ tối ưu (Cumulative Explained Variance):
  - Tỷ lệ phương sai giải thích của thành phần thứ $i$ là: $\text{EVR}_i = \frac{\lambda_i}{\sum_{j=1}^{d} \lambda_j}$ .
  - Vẽ biểu đồ đường tích lũy $\sum_{i=1}^{K} \text{EVR}_i$ theo $K$ .
  - Chọn giá trị $K$ nhỏ nhất sao cho tổng phương sai giải thích đạt được ngưỡng mong muốn (chuẩn công nghiệp thường chọn giữ lại $80\% - 95\%$ lượng thông tin gốc).

❓ Câu hỏi 2: So sánh K-Means và DBSCAN. Hãy phân tích 2 trường hợp thực tế mà K-Means hoàn toàn thất bại và giải thích tại sao DBSCAN lại giải quyết triệt để?

Gợi ý trả lời:
- 2 Trường hợp K-Means thất bại hoàn toàn:
  1. Trường hợp 1 - Cụm có hình dạng phi tuyến tính phức tạp (Non-globular shapes):
    - Ví dụ: Cụm hình vành khăn (hình tròn đồng tâm lồng nhau) hoặc hai dải hình bán nguyệt lồng vào nhau.
    - Lý do K-Means thất bại: K-Means phân chia không gian dựa trên sơ đồ Voronoi lồi (đường phân cách tuyến tính phẳng). Nó luôn cố gắng ép các cụm thành hình cầu, khiến một dải hình bán nguyệt bị chặt đôi thành 2 cụm khác nhau.
    - DBSCAN giải quyết: DBSCAN chỉ quan tâm đến tính liên tục của mật độ các điểm liền kề ( $\epsilon$ -neighborhood). Nó lần theo chuỗi các Core Points để nhận diện trọn vẹn dải hình bất kỳ.
  2. Trường hợp 2 - Dữ liệu chứa nhiều điểm nhiễu và ngoại lai (Outliers & Background Noise):
    - Lý do K-Means thất bại: K-Means bắt buộc mọi điểm dữ liệu đều phải thuộc về một cụm nào đó. Một vài điểm ngoại lai ở rất xa sẽ kéo lệch vị trí tâm cụm $\mu_k$ đi hàng trăm đơn vị, làm méo mó toàn bộ kết quả phân cụm.
    - DBSCAN giải quyết: Bất kỳ điểm nào không đủ $MinPts$ lân cận trong bán kính $\epsilon$ đều bị gán nhãn là Nhiễu (Label $-1$ ) và bị loại bỏ hoàn toàn khỏi các cụm chính.

❓ Câu hỏi 3: Thuật toán Isolation Forest hoạt động dựa trên nguyên lý nào? Tại sao nó lại có tốc độ xử lý nhanh vượt trội ( $O(N \log N)$ ) và tiêu tốn ít bộ nhớ hơn nhiều so với các thuật toán phát hiện bất thường dựa trên khoảng cách (như KNN hay LOF)?

Gợi ý trả lời:
- Nguyên lý cốt lõi:
  - Thay vì mô hình hóa vùng dữ liệu bình thường dày đặc, Isolation Forest tận dụng tính chất của điểm bất thường: Ít về số lượng và có giá trị thuộc tính cách biệt xa so với số đông.
  - Thuật toán xây dựng một tập hợp các cây nhị phân ngẫu nhiên (iTrees). Tại mỗi nút, nó chọn ngẫu nhiên một thuộc tính và một điểm cắt ngẫu nhiên trong dải $[\min, \max]$ .
  - Do nằm cô lập ở vùng thưa thớt, các điểm bất thường sẽ bị chia cắt và rơi vào nút lá ở độ sâu rất nông ( $h(x)$ rất nhỏ). Trong khi các điểm bình thường nằm cụm với nhau sẽ cần rất nhiều lần cắt sâu.
- Lý do tốc độ vượt trội ( $O(N \log N)$ ):
  - Các thuật toán dựa trên khoảng cách (KNN, LOF): Bắt buộc phải tính toán ma trận khoảng cách giữa mọi cặp điểm với nhau $\rightarrow$ Độ phức tạp $O(N^2 \cdot d)$ , cực kỳ chậm và tốn bộ nhớ khi $N > 100,000$ .
  - Isolation Forest: Chỉ cần xây dựng cây nhị phân ngẫu nhiên có độ sâu tối đa $O(\log N)$ . Hơn nữa, thuật toán chỉ cần lấy mẫu con ngẫu nhiên (Sub-sampling với kích thước mặc định $n = 256$ điểm cho mỗi cây) là đã đủ để phát hiện ngoại lai cực kỳ chính xác $\rightarrow$ Tốc độ thực thi siêu tốc, xử lý hàng triệu bản ghi trong vài giây trên Big Data.

6. Tóm Tắt Ghi Nhớ Nhanh (Key Takeaways)

K-Means++ tối ưu cho phân cụm hình cầu lồi với tốc độ nhanh; xác định $K$ bằng Elbow Method và Silhouette Score.
DBSCAN là vua phân cụm mật độ, tìm được hình dạng bất kỳ và tự động loại bỏ $100\%$ điểm nhiễu (Noise).
Luôn chuẩn hóa dữ liệu (StandardScaler) trước khi chạy PCA hoặc K-Means để tránh thiên lệch thang đo.
PCA bảo toàn phương sai toàn cục (Global); t-SNE/UMAP bảo toàn cấu trúc cụm cục bộ (Local) phục vụ trực quan hóa 2D/3D.
Isolation Forest là lựa chọn số 1 cho bài toán phát hiện bất thường (Anomaly Detection) quy mô lớn nhờ độ phức tạp siêu tốc $O(N \log N)$ .