มีปัญหาต่างๆ ของ K-Means Algorithm ดังนี้ −
Handling Empty Clusters (การจัดการคลัสเตอร์ว่าง) − ปัญหาแรกของ K-means แบบพื้นฐานคือ empty clusters อาจเกิดขึ้นถ้าไม่มี points ถูก assign ให้กับ cluster ใน assignment phase ถ้าเกิดขึ้น ต้องมีวิธีเลือก replacement centroid เพราะ squared error จะใหญ่กว่าที่ควรจะเป็น
วิธีหนึ่งคือเลือก point ที่อยู่ไกลที่สุดจาก centroid บางตัว หากนี่ลบ point ที่มีส่วนทำให้ total squared error เพิ่มขึ้น อีกวิธีคือเลือก replacement centroid จาก cluster ที่มี SSE สูงสุด โดยทั่วไปจะแบ่ง cluster และลด total SSE ของ clustering หากมีหลาย empty clusters กระบวนนี้ทำซ้ำได้หลายครั้ง
Outliers (ค่าผิดปกติ) − เมื่อใช้ squared error criterion outliers อาจดึงดูด clusters ที่ค้นพบให้เกินจริง โดยเฉพาะเมื่อมี outliers centroids ที่ได้ (prototypes) อาจไม่เป็นตัวแทนที่ดี และ SSE จะสูงขึ้นเช่นกัน ควรค้นหาและลบ outliers ก่อนประมวลผล แต่ต้องระวังบาง application เช่น data compression ต้อง cluster ทุก point หรือ financial analysis outliers เช่น ลูกค้าที่ทำกำไรผิดปกติอาจเป็นจุดที่น่าสนใจ
Reducing the SSE with Postprocessing (ลด SSE ด้วย Postprocessing) − วิธีลด SSE คือหา clusters มากขึ้น คือใช้ K ใหญ่ขึ้น ในบางกรณี อาจปรับปรุง SSE ได้โดยไม่ต้องเพิ่มจำนวน clusters เพราะ K-means มัก収敛到 local minimum มีหลายวิธี "fix-up" clusters ที่ได้ เพื่อให้ clustering ที่มี SSE ต่ำกว่า วิธีหนึ่งเน้นที่ individual clusters เพราะ total SSE เป็นผลรวมของ SSE ของแต่ละ cluster สามารถเปลี่ยน total SSE โดยดำเนินการกับ clusters เช่น splitting หรือ merging clusters
วิธีหนึ่งคือใช้ alternate cluster splitting and merging procedure ใน splitting phase clusters ถูกแบ่ง ใน merging phase clusters ถูกรวม วิธีนี้สามารถหลุดพ้น local SSE minima และสร้าง clustering solution ด้วยจำนวน clusters ที่ต้องการได้
