Tại sao k-means lại cho kết quả khác nhau trong các lần chạy khác nhau?

Hàm mục tiêu của nó không lồi, vì vậy thuật toán hội tụ đến một cực tiểu cục bộ phụ thuộc vào các tâm ban đầu ngẫu nhiên; việc chạy nó nhiều lần và giữ lại kết quả tốt nhất là một thực hành tiêu chuẩn.

Làm thế nào để chọn số lượng cụm k?

Các phương pháp kinh nghiệm phổ biến bao gồm điểm uốn (elbow) trong tổng bình phương khoảng cách trong cụm, thống kê khoảng cách (gap statistic) và độ rộng silhouette trung bình, mặc dù không có phương pháp nào là tuyệt đối và kiến thức chuyên môn thường hướng dẫn lựa chọn.

Phân cụm K-Means

Phân cụm K-means phân chia các quan sát thành một số cụm cố định bằng cách giảm thiểu tổng bình phương khoảng cách từ các quan sát đến tâm cụm trong mỗi cụm.

Tìm chủ đề với PaperMindSắp ra mắtFind papers & topics

Tools & resources

Tải xuống bản trình chiếu

Learn & explore

VideoSắp ra mắt

Definition

Phân cụm K-means là một phương pháp phân vùng đặt một số lượng tâm cụm được chỉ định trước và gán mỗi quan sát vào tâm cụm gần nhất của nó nhằm giảm thiểu tổng bình phương khoảng cách Euclidean từ các quan sát đến các tâm cụm được gán.

Scope

Chủ đề này bao gồm mục tiêu tổng bình phương khoảng cách trong cụm, thuật toán gán và cập nhật lặp lại xen kẽ giữa việc gán các điểm cho tâm cụm gần nhất và tính toán lại tâm cụm, sự phụ thuộc vào khởi tạo và các cực tiểu cục bộ thu được, lựa chọn số lượng cụm, cũng như các giả định và hạn chế của phương pháp.

Core questions

Làm thế nào để phân chia các quan sát nhằm giảm thiểu sự phân tán trong cụm?
Tại sao thuật toán chỉ hội tụ đến một cực tiểu cục bộ và làm thế nào để khắc phục điều này?
Làm thế nào để chọn số lượng cụm?
Phương pháp này ngầm giả định các hình dạng và tỷ lệ cụm nào?

Key theories

Giảm thiểu tổng bình phương khoảng cách trong cụm: K-means tìm kiếm phân vùng và tập hợp các tâm cụm nhằm giảm thiểu tổng bình phương khoảng cách từ các điểm đến tâm cụm của chúng, một mục tiêu mà phép lặp gán-cập nhật xen kẽ làm giảm tiêu chí một cách đơn điệu.
Tính nhạy cảm với cực tiểu cục bộ: Vì hàm mục tiêu không lồi, thuật toán hội tụ đến một cực tiểu cục bộ phụ thuộc vào các tâm ban đầu; điều này thúc đẩy việc chạy lại nhiều lần và khởi tạo cẩn thận.

Clinical relevance

K-means là một phương pháp mặc định nhanh chóng, có khả năng mở rộng để phân vùng các tập dữ liệu lớn và được sử dụng trong lượng tử hóa vector, giảm màu hình ảnh, phân khúc khách hàng và làm khởi tạo cho các mô hình phức tạp hơn.

History

Ý tưởng phân vùng dựa trên tâm cụm đã được MacQueen chính thức hóa, người đã đặt tên k-means vào năm 1967, dựa trên thuật toán lượng tử hóa trước đó của Lloyd. Nó trở thành một trong những phương pháp phân cụm được sử dụng rộng rãi nhất nhờ sự đơn giản và tốc độ của nó.

Debates

Các giả định ngầm của k-means: Việc giảm thiểu bình phương khoảng cách Euclidean ưu tiên các cụm có hình cầu, kích thước tương đương, vì vậy k-means có thể gây hiểu lầm khi các cụm kéo dài, có kích thước không đều hoặc không lồi, điều này thúc đẩy các lựa chọn thay thế dựa trên mô hình hoặc dựa trên mật độ.

Key figures

James MacQueen
Stuart Lloyd

Seminal works

hastie2009
everitt2011
macqueen1967

Frequently asked questions

Tại sao k-means lại cho kết quả khác nhau trong các lần chạy khác nhau?: Hàm mục tiêu của nó không lồi, vì vậy thuật toán hội tụ đến một cực tiểu cục bộ phụ thuộc vào các tâm ban đầu ngẫu nhiên; việc chạy nó nhiều lần và giữ lại kết quả tốt nhất là một thực hành tiêu chuẩn.
Làm thế nào để chọn số lượng cụm k?: Các phương pháp kinh nghiệm phổ biến bao gồm điểm uốn (elbow) trong tổng bình phương khoảng cách trong cụm, thống kê khoảng cách (gap statistic) và độ rộng silhouette trung bình, mặc dù không có phương pháp nào là tuyệt đối và kiến thức chuyên môn thường hướng dẫn lựa chọn.