Như đã đề cập trước đó, nhiều thuật toán phân cụm không mở rộng theo quy mô cho các tập dữ liệu được sử dụng trong học máy, thường có hàng triệu ví dụ. Ví dụ: các thuật toán phân cụm phân cấp hợp nhất hoặc phân chia xem xét tất cả các cặp điểm và có độ phức tạp tương ứng là \(O(n^2 log(n))\) và \(O(n^2)\).
Khoá học này tập trung vào k-means vì thuật toán này có tỷ lệ theo \(O(nk)\), trong đó \(k\)là số cụm do người dùng chọn. Thuật toán này nhóm các điểm thành các cụm\(k\) bằng cách giảm thiểu khoảng cách giữa mỗi điểm và tâm của cụm (xem Hình 1).
Do đó, k-means xử lý hiệu quả dữ liệu như được tạo thành từ một số phân phối hình tròn gần đúng và cố gắng tìm các cụm tương ứng với các phân phối này. Tuy nhiên, dữ liệu thực tế chứa các giá trị ngoại lai và cụm dựa trên mật độ và có thể không khớp với các giả định cơ bản của k-means.
Thuật toán phân cụm k-means
Thuật toán này tuân theo các bước sau:
Cung cấp một giá trị dự đoán ban đầu cho \(k\). Bạn có thể sửa đổi giá trị này sau. Trong ví dụ này, chúng ta chọn \(k = 3\).
Chọn ngẫu nhiên \(k\) trung tâm.
Hình 1: k-means tại thời điểm khởi tạo. Gán mỗi điểm cho tâm điểm gần nhất để nhận được \(k\) các cụm ban đầu.
Hình 2: Các cụm ban đầu. Đối với mỗi cụm, hãy tính toán một tâm mới bằng cách lấy vị trí trung bình của tất cả các điểm trong cụm. Các mũi tên trong Hình 4 cho thấy sự thay đổi về vị trí tâm.
Hình 3: Tính lại trọng tâm. Chỉ định lại từng điểm cho tâm mới gần nhất.
Hình 4: Các cụm sau khi chỉ định lại. Lặp lại bước 4 và 5, tính toán lại trọng tâm và thành viên cụm cho đến khi các điểm không còn thay đổi cụm. Trong trường hợp tập dữ liệu lớn, bạn có thể dừng thuật toán trước khi hội tụ dựa trên các tiêu chí khác.
Vì các vị trí trọng tâm ban đầu được chọn ngẫu nhiên, nên k-means có thể trả về kết quả khác biệt đáng kể trong các lần chạy liên tiếp. Để giải quyết vấn đề này, hãy chạy k-means nhiều lần và chọn kết quả có chỉ số chất lượng tốt nhất. (Chúng ta sẽ mô tả các chỉ số chất lượng ở phần sau của khoá học này.) Bạn sẽ cần một phiên bản k-means nâng cao để chọn các vị trí trọng tâm ban đầu tốt hơn.
Mặc dù bạn không cần phải hiểu rõ toán học, nhưng đối với những người tò mò, k-means là một trường hợp đặc biệt của thuật toán tối đa hoá kỳ vọng. Xem ghi chú bài giảng về chủ đề này của UPenn.