Có nhiều vấn đề của thuật toán K-Means như sau:
Xử lý cụm rỗng (Handling Empty Clusters)
Vấn đề đầu tiên với thuật toán K-means cơ bản cho trước là các cụm rỗng (null clusters) có thể được thu được nếu không có điểm nào được phân bổ cho một cụm trong giai đoạn gán (assignment phase). Nếu điều này xảy ra, thì một phương pháp cần thiết để chọn centroid thay thế (replacement centroid), vì sai số bình phương (squared error) sẽ lớn hơn cần thiết.
Một phương pháp là chọn điểm xa nhất từ một số centroid gần đây. Nếu điều này loại bỏ điểm hiện đóng góp một số tổng sai số bình phương. Phương pháp khác là chọn centroid thay thế từ cụm có SSE lớn nhất. Điều này thường sẽ chia cụm và giảm tổng SSE của việc phân cụm. Nếu có nhiều cụm rỗng, quy trình này có thể lặp lại nhiều lần.
Giá trị ngoại lai (Outliers)
Khi phương pháp sai số bình phương được dùng, các giá trị ngoại lai (outliers) có thể ảnh hưởng quá mức đến các cụm được khám phá. Cụ thể, khi ngoại lai hiện diện, các centroid cụm (prototypes) kết quả không thể đại diện tốt như chúng có thể, và do đó, SSE cũng sẽ cao hơn.
Có lợi để tìm ngoại lai và loại bỏ chúng trước. Thiết yếu để trân trọng rằng có ứng dụng phân cụm cụ thể mà ngoại lai không nên bị loại bỏ. Khi phân cụm được dùng cho nén dữ liệu (data compression), mỗi điểm nên được phân cụm, và trong một số trường hợp, bao gồm phân tích tài chính, các ngoại lai có thể, ví dụ, người dùng bất thường có lợi nhuận (unusually profitable users), có thể là các điểm thú vị.
Giảm SSE bằng Hậu xử lý (Reducing the SSE with Postprocessing)
Phương pháp giảm SSE là tìm thêm cụm, tức là dùng K lớn hơn. Trong các trường hợp như vậy, có khả năng cải thiện SSE, nhưng không muốn tăng số lượng cụm. Điều này có thể vì K-means thường hội tụ đến cực tiểu cục bộ (local minimum).
Nhiều phương pháp được dùng để "sửa chữa" (fix-up) các cụm kết quả để tạo ra phân cụm có SSE thấp hơn. Phương pháp là tập trung vào các cụm riêng lẻ vì tổng SSE dễ dàng là tổng của SSE đóng góp bởi mỗi cụm. Có thể thay đổi tổng SSE bằng cách thực hiện một số phép toán trên các cụm, bao gồm chia (splitting) hoặc gộp (merging) cụm.
Một phương pháp là dùng quy trình chia và gộp cụm thay thế nhau (alternate cluster splitting and merging procedure). Trong quy trình chia, các cụm bị chia, trong khi trong quy trình gộp, các cụm được kết hợp. Trong phương pháp này, có thể thoát khỏi cực tiểu cục bộ SSE và tạo ra giải pháp phân cụm với số lượng cụm nắm bắt được. Sau đây là một số phương pháp dùng trong giai đoạn chia và gộp: