The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no guaranteed accuracy, its simplicity and speed are very appealing in practice. In this paper, we present a way of initializing k-means by choosing random starting centers with very specific probabilities. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is (log k)-competitive with the optimal clustering. Preliminary experiments show that the augmentation improves both the speed and the accuracy of k-means. © 2012 IEEE.