k-có nghĩa là cụm trống

Question

Tôi cố gắng triển khai k-means làm bài tập về nhà. Bản tập thể dục của tôi cung cấp cho tôi nhận xét sau về các trung tâm trống:

Trong bất kỳ trung tâm cụm nào không có điểm dữ liệu liên kết với nó, hãy thay thế bằng một điểm dữ liệu ngẫu nhiên.

Điều đó gây nhầm lẫn cho tôi một chút, trước hết Wikipedia hoặc các nguồn khác tôi đọc không đề cập đến điều đó chút nào. Tôi tiếp tục đọc về một vấn đề với 'chọn một k tốt cho dữ liệu của bạn' - làm thế nào là thuật toán của tôi phải hội tụ nếu tôi bắt đầu thiết lập các trung tâm mới cho cụm mà có sản phẩm nào.

Nếu tôi bỏ qua các cụm trống mà tôi hội tụ sau 30-40 lần lặp lại. Có sai khi bỏ qua các cụm trống không?

Answer 1

Bạn không nên bỏ qua các cụm trống nhưng thay thế nó. k-means là thuật toán chỉ có thể cung cấp cho bạn mức tối thiểu địa phương và các cụm trống là các mức tối thiểu địa phương mà bạn không muốn. chương trình của bạn sẽ hội tụ ngay cả khi bạn thay thế một điểm bằng một điểm ngẫu nhiên. Hãy nhớ rằng ở đầu thuật toán, bạn chọn ngẫu nhiên điểm K ban đầu. nếu nó có thể hội tụ, làm thế nào đến K-1 hội tụ điểm với 1 điểm ngẫu nhiên có thể không? chỉ cần một vài lần lặp lại là cần thiết.

Answer 2

"Chọn k tốt cho dữ liệu của bạn" đề cập đến vấn đề chọn đúng số cụm. Vì thuật toán k-means hoạt động với số lượng trung tâm cụm được xác định trước, nên số của chúng phải được chọn lúc đầu. Việc chọn sai số có thể làm cho việc chia các điểm dữ liệu thành các cụm hoặc các cụm trở nên khó có thể trở nên nhỏ và vô nghĩa.

Tôi không thể cung cấp cho bạn câu trả lời về việc có nên bỏ qua các cụm trống không. Nếu bạn làm như vậy, bạn có thể kết thúc với một số cụm nhỏ hơn bạn đã xác định ở đầu. Điều này sẽ gây nhầm lẫn cho những người mong đợi k-phương tiện để làm việc một cách nhất định, nhưng nó không nhất thiết phải là một ý tưởng tồi.

Nếu bạn định vị lại bất kỳ trung tâm cụm trống nào, thuật toán của bạn có thể sẽ hội tụ nếu điều đó xảy ra với số lần giới hạn. Tuy nhiên, nếu bạn phải di chuyển quá thường xuyên, có thể xảy ra thuật toán của bạn không chấm dứt.

Answer 3

Kiểm tra ví dụ này về cách các cụm trống có thể xảy ra: http://www.ceng.metu.edu.tr/~tcan/ceng465_f1314/Schedule/KMeansEmpty.html Về cơ bản có nghĩa là 1) ngẫu nhiên có hiệu lực hoặc 2) số cụm k sai. Bạn nên lặp qua một vài giá trị khác nhau cho k và chọn tốt nhất. Nếu trong khi lặp lại, bạn sẽ gặp phải một cụm trống, đặt một điểm dữ liệu ngẫu nhiên vào cụm đó và tiếp tục. Tôi hy vọng điều này đã giúp cho bài tập về nhà của bạn năm ngoái.

Answer 4

Xử lý cụm trống không phải là một phần của thuật toán k-means nhưng có thể dẫn đến chất lượng cụm tốt hơn. Nói về hội tụ, nó không bao giờ chính xác nhưng chỉ được bảo đảm về mặt heuristically và do đó tiêu chí hội tụ được mở rộng bằng cách bao gồm một số lần lặp tối đa.

Về chiến lược giải quyết vấn đề này, tôi sẽ nói ngẫu nhiên chỉ định một số điểm dữ liệu cho nó không phải là rất thông minh vì chúng tôi có thể ảnh hưởng đến chất lượng cụm. Một heuristic cho trường hợp này sẽ là chọn điểm xa nhất từ ​​cụm lớn nhất và di chuyển cụm trống đó, sau đó làm như vậy cho đến khi không có cụm trống.