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