Ưu và nhược điểm của phương tiện k

K-means hữu ích và hiệu quả trong nhiều ngữ cảnh học máy, nhưng có một số điểm yếu riêng biệt.

Ưu điểm của thuật toán k trung bình

Tương đối dễ triển khai.

Điều chỉnh theo quy mô cho các tập dữ liệu lớn.

Luôn hội tụ.

Cho phép khởi động ấm các vị trí của tâm điểm.

Thích ứng liền mạch với các ví dụ mới.

Có thể được khái quát hoá cho các cụm có nhiều hình dạng và kích thước, chẳng hạn như cụm hình elip.

Tổng quát hoá k-means

Việc triển khai k-means một cách đơn giản có thể gặp khó khăn với các cụm có mật độ và kích thước khác nhau. Phía bên trái của Hình 1 cho thấy các cụm mà chúng ta dự kiến sẽ thấy, còn phía bên phải cho thấy các cụm do k-means đề xuất.

Hình 1: Ví dụ về k-means chưa tổng quát.

Để có hiệu suất tốt hơn trên các cụm không cân bằng như các cụm trong Hình 1, bạn có thể khái quát hoá, tức là điều chỉnh k-means. Hình 2 cho thấy 3 tập dữ liệu khác nhau được nhóm lại với 2 khái quát khác nhau. Tập dữ liệu đầu tiên cho thấy k-means mà không tổng quát hoá, trong khi tập dữ liệu thứ hai và thứ ba cho phép các cụm thay đổi về chiều rộng.

Hình 2: Nhóm k-means có và không có quá trình tổng quát hoá.

Khoá học này không đề cập đến cách tổng quát hoá k-means, nhưng những người quan tâm nên xem Clustering – k-means Gaussian mixture models (Nhóm – mô hình hỗn hợp Gaussian k-means) của Carlos Guestrin từ Đại học Carnegie Mellon.

Nhược điểm của phương pháp k-means

Bạn phải chọn$k$ theo cách thủ công.

Kết quả phụ thuộc vào giá trị ban đầu.

Đối với $k$thấp, bạn có thể giảm thiểu sự phụ thuộc này bằng cách chạy k-means nhiều lần với các giá trị ban đầu khác nhau và chọn kết quả tốt nhất. Khi $k$ tăng lên, bạn cần gieo hạt k-means để chọn tâm điểm ban đầu tốt hơn. Để thảo luận đầy đủ về việc gieo hạt k-means, hãy xem bài viết "Nghiên cứu so sánh về các phương thức khởi tạo hiệu quả cho thuật toán phân cụm K-means" của M. Emre Celebi, Hassan A. Kingravi và Patricio A. Vela.

Khó phân cụm dữ liệu có kích thước và mật độ khác nhau mà không tổng quát hoá.

Khó phân cụm các giá trị ngoại lai.

Các giá trị ngoại lai có thể kéo tâm điểm hoặc các giá trị ngoại lai có thể tạo ra cụm riêng thay vì bị bỏ qua. Cân nhắc việc xoá hoặc cắt bỏ các điểm ngoại lai trước khi tạo cụm.

Khó khăn trong việc mở rộng quy mô theo số lượng phương diện.

Khi số lượng phương diện trong dữ liệu tăng lên, một chỉ số tương đồng dựa trên khoảng cách sẽ hội tụ thành một giá trị không đổi giữa bất kỳ ví dụ cụ thể nào. Giảm số chiều bằng cách sử dụng PCA trên dữ liệu đặc điểm hoặc bằng cách sử dụng phân cụm theo quang phổ để sửa đổi thuật toán phân cụm.

Lời nguyền về thứ nguyên và cụm quang phổ

Trong ba biểu đồ này, hãy lưu ý cách khi các phương diện tăng lên, độ lệch chuẩn về khoảng cách giữa các ví dụ sẽ thu hẹp tương ứng với khoảng cách trung bình giữa các ví dụ. Sự hội tụ này có nghĩa là k-means trở nên kém hiệu quả hơn trong việc phân biệt giữa các ví dụ khi số chiều của dữ liệu tăng lên. Đây được gọi là lời nguyền về số chiều.

Hình 3: Minh hoạ lời nguyền về số chiều. Mỗi biểu đồ cho thấy khoảng cách giữa các cặp điểm ngẫu nhiên giữa 200 điểm.

Bạn có thể tránh sự sụt giảm hiệu suất này bằng cách nhóm các giá trị theo phổ, tức là thêm các bước trước khi nhóm vào thuật toán. Cách thực hiện quá trình phân cụm quang phổ:

1. Giảm số chiều của dữ liệu đặc điểm bằng cách sử dụng PCA.
2. Ánh xạ tất cả các điểm dữ liệu vào không gian con có kích thước thấp hơn.
3. Nhóm dữ liệu trong không gian con này bằng thuật toán mà bạn đã chọn.

Xem Hướng dẫn về tính năng Nhóm theo phổ của Ulrike von Luxburg để biết thêm thông tin về tính năng nhóm theo phổ.

Thuật ngữ quan trọng:

• phân cụm theo phổ