K-Means tính tâm cụm bằng trung bình cộng các điểm trong cụm, nên vị trí tâm dễ bị kéo lệch khi có dữ liệu ngoại lai và thuật toán chỉ dùng được với khoảng cách Euclid. K-Medoids khắc phục hai hạn chế này bằng cách chọn chính một điểm dữ liệu quan sát làm tâm đại diện (medoid). Nhờ vậy, tâm cụm luôn là một đối tượng có thật, còn thuật toán tối thiểu hóa trực tiếp tổng khoảng cách bậc một (không bình phương) và làm việc được với mọi độ đo khoảng cách.

Trở ngại lớn nhất của K-Medoids nằm ở chi phí tính toán. Thuật toán PAM cổ điển phải duyệt qua mọi cặp điểm với độ phức tạp $O(k(n-k)^2)$, trong khi các phương pháp lấy mẫu như CLARA lại dễ rơi vào cực tiểu cục bộ. CLARANS giải quyết bằng cách tìm kiếm trên đồ thị hoán đổi, trước khi FastCLARANS cùng thư viện scikit-clarans rút ngắn thời gian chạy nhờ cơ chế đánh giá đồng thời $k$ medoid trong khi giữ bộ nhớ ở mức $O(n)$.

Lộ trình các bài viết

Bài 1: K-Medoids và giới hạn của tâm cụm trung bình trong K-Means

Bài mở đầu đối chiếu hàm mất mát của K-Medoids với K-Means, giải thích vì sao K-Means bị lệch tâm khi gặp nhiễu và khi nào bài toán thực tế đòi hỏi tâm cụm phải là một quan sát có thật.

Bài 2: Các thuật toán K-Medoids: Từ PAM, CLARA, CLARANS đến FastCLARANS

Từ chi phí tính toán bậc hai của PAM và nhược điểm lấy mẫu trong CLARA, bài viết đi sâu vào mô hình đồ thị hoán đổi của CLARANS cùng cơ chế đánh giá nhanh $k$ medoid trong một lượt duyệt dữ liệu của FastCLARANS.

Bài 3: Tích hợp scikit-clarans vào Pipeline của Scikit-Learn

Phần này hướng dẫn thiết kế code theo chuẩn Scikit-Learn để ghép scikit-clarans vào pipeline tiền xử lý dữ liệu, chọn số cụm $k$ qua Silhouette Score, tìm siêu tham số bằng GridSearchCV và trích xuất đặc trưng khoảng cách tới các medoid bằng hàm transform().

Bài 4: Phân khúc khách hàng trên dữ liệu hỗn hợp với khoảng cách phi Euclid

Trên tập dữ liệu khách hàng có cả biến liên tục lẫn biến phân loại, ta sẽ thử nghiệm K-Medoids với khoảng cách Manhattan, Cosine và Euclid, sau đó lấy chính các medoid tìm được làm hồ sơ khách hàng đại diện cho từng phân khúc.

Bài 5: Phát hiện bất thường trong dữ liệu chuỗi thời gian telemetry

Với dữ liệu cảm biến IoT từ bộ Numenta NAB, K-Medoids giúp xác định các mẫu vận hành chuẩn thông qua tập medoid, từ đó tính điểm bất thường không giám sát dựa trên khoảng cách từ mỗi quan sát tới medoid gần nhất.

Bài 6: Phân cụm văn bản với ma trận thưa TF-IDF

Khi làm việc với dữ liệu văn bản nhiều chiều, FastCLARANS kết hợp cùng khoảng cách Cosine có thể gom nhóm bài viết trực tiếp trên ma trận thưa scipy.sparse mà không làm tràn bộ nhớ do chuyển đổi sang mảng đầy đủ.

Bài 7: Phân cụm đồ thị và mạng lưới bằng ma trận khoảng cách tính trước

Từ ma trận khoảng cách đường đi ngắn nhất trên mạng xã hội hoặc mạng lưới giao thông, thuật toán có thể phân cụm trực tiếp các nút mạng và chỉ ra những đỉnh trung tâm làm medoid.

Bài 8: Kháng ngoại lai và xử lý dữ liệu khuyết thiếu trong y tế

Bài viết kiểm nghiệm mức độ lệch tâm của K-Means và FastCLARANS khi dữ liệu xuất hiện các điểm ngoại lai cực đoan, đồng thời áp dụng khoảng cách nan_euclidean để phân cụm hồ sơ bệnh án bị khuyết thiếu giá trị.

Bài 9: Tiêu chí lựa chọn thuật toán và triển khai trong thực tế

Bài cuối đặt K-Medoids cạnh K-Means, DBSCAN và Hierarchical Clustering để làm rõ ưu nhược điểm của từng phương pháp, cách chọn độ đo khoảng cách theo kiểu dữ liệu và những lưu ý về tài nguyên phần cứng khi chạy trên tập dữ liệu lớn.

Mã nguồn và tài nguyên tham khảo

Bạn có thể cài đặt thư viện qua câu lệnh pip install scikit-clarans. Toàn bộ mã nguồn được lưu trữ trên GitHub, đi kèm tài liệu hướng dẫn trên Read the Docs và sổ tay thực hành Google Colab.