Phân cụm Dữ liệu Vector K-Means++ & Đánh giá Inertia

Mục tiêu kiến thức

• Hiểu sâu và tự cài đặt thuật toán Phân cụm K-Means kinh điển (Thuật toán Lloyd).
• Khắc phục nhược điểm nhạy cảm với khởi tạo ban đầu bằng kỹ thuật khởi tạo thông minh K-Means++ (Arthur & Vassilvitskii, 2007).
• Tối ưu hóa tính toán ma trận khoảng cách giữa các điểm dữ liệu và các tâm cụm bằng Broadcasting NumPy O(1) loop.
• Tính toán chỉ số đánh giá độ kết tụ của cụm: Tổng bình phương khoảng cách nội cụm (Inertia / WCSS).

Mô tả bài toán

Phân cụm K-Means là thuật toán học máy không giám sát (Unsupervised Learning) cốt lõi dùng để phân nhóm khách hàng, phân đoạn ảnh, hoặc nén vector dữ liệu (Vector Quantization). Khởi tạo ngẫu nhiên thông thường rất dễ bị rơi vào cực tiểu cục bộ (Local Minima). K-Means++ giải quyết triệt để vấn đề này bằng cách chọn các tâm cụm trải rộng tối đa trong không gian.

Hãy xây dựng lớp:

class VectorizedKMeans:
    def __init__(self, n_clusters: int = 3, max_iter: int = 100, tol: float = 1e-4, random_state: int = 42):
        ...
    def fit(self, X: np.ndarray) -> "VectorizedKMeans":
        ...
    def predict(self, X: np.ndarray) -> np.ndarray:
        ...
    @property
    def cluster_centers_(self) -> np.ndarray:
        ...
    @property
    def inertia_(self) -> float:
        ...

Quy trình thuật toán:

• Khởi tạo K-Means++:
• Thiết lập rng = np.random.RandomState(random_state).
• Chọn ngẫu nhiên tâm cụm đầu tiên c₀ từ tập X theo phân phối đều.
• Với các tâm tiếp theo c₁, …, c_K-1:
• Với mỗi điểm dữ liệu x_i, tính khoảng cách bình phương nhỏ nhất tới các tâm đã chọn:

D(x_i)² = min_{j < k} |x_i - c_j|²

• Tính xác suất chọn điểm tiếp theo: P(x_i) = D(x_i)²∑_m=1^N D(x_m)².
• Chọn tâm tiếp theo bằng rng.choice(N, p=P).
• Vòng lặp tối ưu hóa Lloyd:
• Ở mỗi bước lặp:
• Gán nhãn (Assignment): Tính khoảng cách bình phương từ mỗi điểm X tới tất cả các tâm hiện tại C bằng broadcasting. Gán nhãn cho mỗi điểm:

labels_i = argmin_k |x_i - c_k|²

• Cập nhật tâm (Update): Tính tâm mới bằng trung bình cộng các điểm trong cụm:

c_k^new = mean(X[labels == k], axis=0) *(Nếu một cụm không có điểm nào rơi vào, gán lại tâm đó bằng một điểm ngẫu nhiên trong X)*.

• Kiểm tra hội tụ: Tính khoảng cách di chuyển cực đại của các tâm:

shift = max_k |c_k^new - c_k|₂. Nếu shift ≤ tol, dừng vòng lặp sớm. Cập nhật tâm cụm và lặp tiếp tối đa max_iter lần.

• Tính quán tính (Inertia):
• Quán tính (Within-Cluster Sum of Squares) là tổng khoảng cách bình phương từ mọi điểm tới tâm cụm tương ứng của nó:

Inertia = ∑_i=1^N |x_i - c_labelsi|²

• Lưu trữ dưới dạng thuộc tính self.inertia_ (kiểu float làm tròn số học).

Ràng buộc

• Số cụm K ≥ 1, số điểm dữ liệu N ≥ K.
• Tuyệt đối không dùng thư viện ngoài ngoại trừ numpy.