## 2 Existing Algorithms
### K-Means Clustering Problem and the Basic Algorithms  
Let \(\mathbf{X}=\{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{N}\}\) be a dataset such that \(\mathbf{x}_{i}\in\mathbb{R}^{M}\ \forall 1\leq i\leq N\), where \(M\) denotes the dimension, and let \(\mathbf{C}=\{\mathbf{c}_{1},\mathbf{c}_{2},...,\mathbf{c}_{K}\}\) be a set of prototypes, where each prototype also belongs to \(\mathbb{R}^{M}\). The goal of the K-means clustering algorithm is to find a partition of \(\mathbf{X}\) into \(K\) disjoint subsets, by minimizing the sum-of-squares error (SSE) defined as  
\[\text{SSE}(\mathbf{C})=\sum_{\mathbf{x}\in\mathbf{X}}\min_{\mathbf{c}\in \mathbf{C}}\|\mathbf{c}-\mathbf{x}\|^{2}. \tag{1}\]  
An approximate solution to the minimization problem with (1) is typically computed by using the Lloyd's K-means algorithm [1]. Its popularity is based on simplicity and scalability. Even if the cost function in (1) is mathematically nondifferentiable because of the min-operator, it is easy to show that after the initialization, the K-means type of iterative relocation algorithm converges in finite many steps [4]. Prototype-based clustering algorithms, such as K-means, are initialized before the prototype relocation (search) phase. The classical initialization algorithm, readily proposed in [33], is to randomly generate the initial set of prototypes. A slight refinement of this strategy is to select, instead of random points (from appropriate value ranges), random indices and use the corresponding observations in data as initialization [34]. Because of this choice, there cannot be empty clusters in the first iteration. [PERSON] and [PERSON] [35] proposed an initialization method where \(J\) randomly selected subsets of the data are first clustered with K-means. Next, it forms a superset of the \(J\times K\) prototypes obtained from the subset clustering. Finally, the initial prototypes are achieved as the result of K-means clustering of the superset. [PERSON] and [PERSON] [5] introduced the K-means++ algorithm, which improves the initialization of K-means clustering. The algorithm selects first prototype at random, and then the remaining \(K-1\) prototypes are sampled using probabilities based on the squared distances to the already selected set, thus favoring distant prototypes. The generalized form of such an algorithm with different \(l_{p}\)-distance functions and the corresponding cluster location estimates was depicted in [4]. The parallelized K-means++ method, called K-means\(\|\), was proposed by [PERSON] et al. [6] (see Algorithm 1). In Algorithm 1, and from here onwards, symbol \"\(\psi\)\" denotes 'number of'. In the algorithm, sampling from \(\mathbf{X}\) is conducted in a slightly different fashion compared to K-means++. More precisely, the sampling probabilities are multiplied with the over-sampling factor \(l\) and the sampling is done independently for each data point. The initial SSE for the first sampled point \(\psi\) determines the number of sampling iterations. K-means\(\|\) runs \(O(log(\psi))\) sampling iterations. For each iteration, the expected number of points is \(l\). Hence, after \(O(log(\psi))\) iterations, the expected number of points added to \(\mathbf{C}\) is \(O(l\log(\psi))\). Finally, weights representing the accumulation of data around the sampled points are set and the result of the weighted clustering then provides the \(K\) initial prototypes. K-means++ can be used to cluster the weighted data (see Algorithm 1 in [36]). Selecting \(r=5\) instead of \(O(log(\psi))\) rounds and setting the over-sampling factor to \(2K\) were demonstrated to be sufficient in [6]. Recently, [PERSON] et al. [36] proved theoretically that small \(r\) instead of \(O(log(\psi))\) iterations is sufficient in K-means\(\|\). A modification of K-means\(\|\) for initializing robust clustering was described and tested in [37]. ```
Input: Dataset X, #clusters \(K\), and over-sampling factor \(l\). Output: Set of prototypes \(\mathbf{C}=\{\mathbf{c}_{1},\mathbf{c}_{2},...,\mathbf{c}_{K}\}\).