contrast, linear IMs are often random and/or order-sensitive [@Forgy65; @Jancey66; @MacQueen67; @Ball67; @Tou74; @Spath77; @Bradley98; @Arthur07], which renders their results unrepeatable. Su and Dy proposed two divisive hierarchical initialization methods named Var-Part and PCA-Part that are not only linear, but also deterministic and order-invariant [@Su07]. In this study, we propose a simple modification to these methods that improves their performance significantly.

The rest of the paper is organized as follows. Section \[sec\_init\_methods\] presents a brief overview of some of the most popular linear, order-invariant k-means IMs and the proposed modification to Var-Part and PCA-Part. Section \[sec\_exp\] presents the experimental results, while Section \[sec\_disc\] analyzes these results. Finally, Section \[sec\_conc\] gives the conclusions.

Linear, Order-Invariant Initialization Methods for K-Means {#sec_init_methods}
==========================================================

Overview of the Existing Methods
--------------------------------

Forgy’s method [@Forgy65] assigns each point to one of the $K$ clusters uniformly at random. The centers are then given by the centroids of these initial clusters. This method has no theoretical basis, as such random clusters have no internal homogeneity [@Anderberg73].

MacQueen [@MacQueen67] proposed two different methods. The first one, which is the default option in the Quick Cluster procedure of IBM SPSS Statistics [@Norusis11], takes the first $K$ points in ${{\mathcal X}}$ 