Thuật toán phân cụm K-Means thuần vector hóa với khoảng cách ma trận

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

• Triển khai thuật toán K-Means lặp lại 2 bước: Gán nhãn cụm gần nhất (Expectation) và Cập nhật tâm cụm (Maximization).
• Tính khoảng cách từ N điểm đến K tâm cụm bằng cơ chế Broadcasting 3D (N, 1, D) - (1, K, D) không dùng vòng lặp lồng.
• Kiểm tra điều kiện hội tụ khi khoảng cách dịch chuyển của các tâm cụm nhỏ hơn ngưỡng dung sai tol.

Mô tả bài toán

Viết hàm kmeans_cluster(X: np.ndarray, k: int, max_iter: int = 50, tol: float = 1e-4, initial_centroids: np.ndarray | None = None) -> tuple[np.ndarray, np.ndarray, int]:

• X: Ma trận dữ liệu (N, D).
• Kiểm tra tính hợp lệ:
• Nếu k ≤ 0 hoặc k > N hoặc len(X) == 0, raise ValueError("Tham so k hoac du lieu khong hop le").
• Khởi tạo tâm cụm:
• Nếu initial_centroids is not None, sử dụng initial_centroids.copy().
• Nếu initial_centroids is None, lấy k mẫu đầu tiên: centroids = X[:k].copy().
• Vòng lặp tối đa max_iter:
• Bước 1 (Gán nhãn):
• Khoảng cách bình phương Euclide: dists = np.sum((X[:, np.newaxis, :] - centroids[np.newaxis, :, :]) ** 2, axis=2) có kích thước (N, K).
• Nhãn của mỗi điểm: labels = np.argmin(dists, axis=1) kích thước (N,).
• Bước 2 (Cập nhật tâm cụm):
• Với mỗi cụm j ∈ [0, k-1], nếu cụm có điểm gán vào (np.sum(labels == j) > 0), tâm mới là trung bình cộng X[labels == j].mean(axis=0). Nếu cụm rỗng, giữ nguyên tâm cũ.
• Bước 3 (Kiểm tra hội tụ):
• Dịch chuyển tâm: shift = np.max(np.linalg.norm(new_centroids - centroids, axis=1)).
• Cập nhật centroids = new_centroids.
• Nếu shift < tol, dừng vòng lặp sớm.
• Trả về (centroids, labels, iterations_run).

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.