Các thuật toán phân cụm

Tập dữ liệu học máy có thể có hàng triệu ví dụ, nhưng không phải thuật toán phân cụm nào cũng mở rộng quy mô hiệu quả. Nhiều thuật toán phân cụm tính toán độ tương đồng giữa tất cả các cặp ví dụ, nghĩa là thời gian chạy của chúng tăng lên theo bình phương của số lượng ví dụ $n$, được biểu thị là $O(n^2)$ theo ký hiệu độ phức tạp.Các thuật toán $O(n^2)$ không thực tế đối với các tập dữ liệu có hàng triệu ví dụ.

Thuật toán k-means có độ phức tạp là $O(n)$, nghĩa là thuật toán này mở rộng theo tỷ lệ tuyến tính với $n$. Thuật toán này sẽ là trọng tâm của khoá học này.

Các loại cụm

Để biết danh sách đầy đủ các phương pháp phân cụm, hãy xem bài viết A Comprehensive Survey of Clustering Algorithms (Khảo sát toàn diện về thuật toán phân cụm) của Xu, D. và Tian, Y. Ann. Data. Sci. (2015) 2: 165. Mỗi phương pháp phù hợp nhất với một cách phân phối dữ liệu cụ thể. Khoá học này thảo luận ngắn gọn về 4 phương pháp phổ biến.

Phân cụm dựa trên tâm điểm

Tâm điểm của một cụm là trung bình cộng của tất cả các điểm trong cụm. Nhóm dựa trên tâm điểm sắp xếp dữ liệu thành các cụm không phân cấp. Các thuật toán phân cụm dựa trên tâm điểm rất hiệu quả nhưng nhạy cảm với các điều kiện ban đầu và dữ liệu ngoại lai. Trong số này, k-means là phương pháp được sử dụng rộng rãi nhất. Phương pháp này yêu cầu người dùng xác định số lượng tâm điểm, k và hoạt động hiệu quả với các cụm có kích thước gần như bằng nhau.

Hình 1: Ví dụ về quy trình phân cụm dựa trên tâm điểm.

Phân cụm dựa trên mật độ

Tính năng cụm dựa trên mật độ kết nối các khu vực liền kề có mật độ ví dụ cao thành các cụm. Điều này cho phép khám phá số lượng cụm bất kỳ với hình dạng bất kỳ. Các giá trị ngoại lai không được chỉ định cho cụm. Các thuật toán này gặp khó khăn với các cụm có mật độ khác nhau và dữ liệu có kích thước cao.

Hình 2: Ví dụ về quy trình phân cụm dựa trên mật độ.

Phân cụm dựa trên phân phối

Phương pháp phân cụm này giả định dữ liệu được tạo thành từ các hàm phân phối xác suất, chẳng hạn như hàm phân phối Gaussian. Trong Hình 3, thuật toán dựa trên phân phối phân cụm dữ liệu thành ba phân phối Gaussian. Khi khoảng cách từ tâm của phân phối tăng lên, xác suất một điểm thuộc về phân phối sẽ giảm. Các dải này cho thấy mức giảm về xác suất. Khi không muốn giả định một phương thức phân phối cơ bản cụ thể của dữ liệu, bạn nên sử dụng một thuật toán khác.

Hình 3: Ví dụ về cụm dựa trên phân phối.

Phân cụm phân cấp

Hierarchical clustering (Nhóm phân cấp) tạo ra một cây gồm các cụm. Không có gì đáng ngạc nhiên khi phương pháp phân cụm phân cấp rất phù hợp với dữ liệu phân cấp, chẳng hạn như các hệ thống phân loại. Hãy xem bài viết So sánh 61 bộ gen Escherichia coli đã được giải trình tự của Oksana Lukjancenko, Trudy Wassenaar và Dave Ussery để biết ví dụ. Bạn có thể chọn số lượng cụm bất kỳ bằng cách cắt cây ở cấp độ phù hợp.

Hình 4: Ví dụ về cây phân cấp nhóm động vật.

Thuật ngữ quan trọng:

• Thuật toán k-means
• trung tâm
• Phân phối Gaussian