Các tập dữ liệu học máy có thể có hàng triệu nhưng không phải tất cả thuật toán phân cụm đều mở rộng một cách hiệu quả. Nhiều phân cụm các thuật toán tính toán điểm tương đồng giữa tất cả các cặp ví dụ, điều này có nghĩa là thời gian chạy của chúng tăng lên bình phương của số ví dụ \(n\), được biểu thị dưới dạng \(O(n^2)\) trong ký hiệu độ phức tạp. \(O(n^2)\) Các thuật toán không thực tế cho 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 của \(O(n)\), nghĩa là thuật toán mở rộng quy mô 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 kiểu phân cụm
Để có danh sách đầy đủ các phương pháp phân cụm khác nhau, hãy xem Khảo sát toàn diện về các thuật toán phân cụm Xu, D. & Tian, Y. An. Dữ liệu. Khoa học (2015) 2: 165. Mỗi phương pháp phù hợp nhất với phân phối dữ liệu cụ thể. Khoá học này thảo luận ngắn gọn 4 điểm thường gặp của chúng tôi.
Phân cụm dựa trên tâm
Trọng tâm của cụm là trung bình cộng của tất cả các điểm trong cụm. Phân cụm dựa trên Centroid sắp xếp dữ liệu thành các danh mục không phân cấp cụm. Các thuật toán phân cụm dựa trên Centroid rất hiệu quả nhưng nhạy cảm với các điều kiện ban đầu và các điểm ngoại lai. Trong số này, k-me là quan trọng nhất được sử dụng rộng rãi. Định nghĩa này yêu cầu người dùng xác định số trung tâm, k và hoạt động tốt với các cụm có kích thước gần như bằng nhau.
Phân cụm dựa trên mật độ
Phân cụm dựa trên mật độ kết nối các khu vực tiếp giáp có mật độ mẫu cao vào cụm. Điều này cho phép phát hiện ra số lượng bất kỳ các cụm có hình dạng bất kỳ. Các điểm ngoại lai không được gán cho các cụm. Những thuật toán này gặp khó khăn với các cụm có mật độ và dữ liệu khác nhau có kích thước lớn.
Phân cụm dựa trên phân phối
Phương pháp phân cụm này giả định rằng dữ liệu bao gồm dữ liệu theo xác suất phân phối, chẳng hạn như Phân phối Gaussian. Ngang bằng 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 Gaussian Google Cloud. Khi khoảng cách từ trung tâm phân phối tăng, xác suất mà một điểm thuộc phân phối giảm xuống. Chương trình biểu diễn của các ban nhạc xác suất giảm đó. Khi bạn không thoải mái khi giả định một phân phối cơ bản của dữ liệu, bạn nên sử dụng một thuật toán khác.
Phân cụm phân cấp
Phân cụm phân cấp tạo ra cây cụm. Phân cụm phân cấp, không có gì đáng ngạc nhiên, rất phù hợp với dữ liệu phân cấp, chẳng hạn như dữ liệu phân loại. Xem So sánh 61 bộ gen của Escherichia coli theo trình tự Tác giả: Oksana Lukjancenko, Trudy Wassenaar và Dave Ussery là 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.
