as the centers. An obvious drawback of this method is its sensitivity to data ordering. The second method chooses the centers randomly from the data points. The rationale behind this method is that random selection is likely to pick points from dense regions, i.e., points that are good candidates to be centers. However, there is no mechanism to avoid choosing outliers or points that are too close to each other [@Anderberg73]. Multiple runs of this method is the standard way of initializing k-means [@Bradley98]. It should be noted that this second method is often mistakenly attributed to Forgy [@Forgy65].

The maximin method [@Gonzalez85] chooses the first center ${{\bf c}}_1$ arbitrarily and the $i$-th ($i \in \{2, 3, \dotsc, K\}$) center ${{\bf c}}_i$ is chosen to be the point that has the greatest minimum-distance to the previously selected centers, i.e., ${{\bf c}}_1, {{\bf c}}_2, \dotsc, {{\bf c}}_{i-1}$. This method was originally developed as a $2$-approximation to the $K$-center clustering problem[^1].

The k-means++ method [@Arthur07] interpolates between MacQueen’s second method and the maximin method. It chooses the first center randomly and the $i$-th ($i \in \{ 2, 3, \dotsc, K \}$) center is chosen to be ${{\bf x}}' \in {{\mathcal X}}$ with 