K-means thường hội tụ về cực tiểu cục bộ. Trong các phiên bản cải tiến của K-means, k-means++ nổi tiếng với việc đạt được nghiệm khá tối ưu nhờ chiến lược khởi tạo cụm và hiệu quả tính toán cao. K-means gia tăng được công nhận vì hội tụ về cực tiểu toàn cục theo kinh nghiệm nhưng có độ phức tạp cao do việc bước qua số cụm K. Bài báo giới thiệu K-means** với chiến lược nhân đôi trên K. Các kỹ thuật bổ sung, bao gồm chỉ nhân đôi các cụm đủ lớn, bước K cho một vài giá trị cuối và tìm kiếm trên các ứng viên khác cho K cuối, được sử dụng để giúp K-means** có độ phức tạp O(K logK), thấp hơn độ phức tạp của K-means gia tăng, và vẫn hội tụ về cực tiểu toàn cục theo kinh nghiệm. Trên một tập dữ liệu tổng hợp và thực tế, K-means** đạt kết quả tối thiểu trong hầu hết các trường hợp kiểm thử. K-means** nhanh hơn nhiều so với K-means gia tăng và có tốc độ tương đương k-means++.