can be alleviated by using a more general distance function such as the Mahalanobis distance, which permits the detection of hyperellipsoidal clusters [@Mao96]. Third, due its utilization of the squared Euclidean distance, it is sensitive to noise and outlier points since even a few such points can significantly influence the means of their respective clusters. This can be addressed by outlier pruning [@Zhang03] or using a more robust distance function such as City-block ($\mathcal{L}_1$) distance. Fourth, due to its gradient descent nature, it often converges to a local minimum of the criterion function [@Selim84]. For the same reason, it is highly sensitive to the selection of the initial centers [@Celebi13a]. Adverse effects of improper initialization include empty clusters, slower convergence, and a higher chance of getting stuck in bad local minima [@Celebi11]. Fortunately, except for the first two, these drawbacks can be remedied by using an adaptive initialization method (IM).

A large number of IMs have been proposed in the literature [@Pena99; @He04; @Celebi11; @Celebi13a]. Unfortunately, many of these have superlinear complexity in $N$ [@Lance67; @Astrahan70; @Hartigan79; @Kaufman90; @Likas03; @AlDaoud05; @Redmond07; @AlHasan09; @Cao09; @Kang09], which makes them impractical for large data sets (note that k-means itself has linear complexity). In 