## 3 New Algorithms
### Sk-Means\(\|\)  
The first new initialization method for K-means clustering, Subset K-means\(\|\) (SK-means\(\|\)), is described in Algorithm 2. The method is based on \(S\) randomly sampled non-disjoint subsets \(\{\mathbf{X}_{1},\mathbf{X}_{2},...,\mathbf{X}_{S}\}\) from \(\mathbf{X}\) of approximately equal size, such as \(\mathbf{X}=\cup_{i=1}^{S}\mathbf{X}_{i}\). First, K-means\(\|\) is applied in each subset, which gives the corresponding set of initial prototypes \(\mathbf{C}_{i}\). Next, each initial prototype set \(\mathbf{C}_{i}\) in \(\mathbf{X}_{i}\) is refined with \(T_{init}\) Lloyd's iterations. \(T_{init}\) is assumed to be significantly smaller than the number of Lloyd's iterations needed for convergence. Then, SSE is computed locally for each \(\mathbf{C}_{i}\) in \(\mathbf{X}_{i}\). Differently from the earlier work [30], this locally computed SSE is now used as the selection criteria for the initial prototypes instead of the global SSE. Computation of SSE for \(\mathbf{X}_{i}\) in Step 3 is obviously much faster than to compute it for the whole \(\mathbf{X}\). However, a drawback is that if the subsets are too small to characterize the whole data, the selection of the initial prototypes might fail.  
Therefore, \(S\) should be selected such that the subsets are sufficiently large. For example, if \(S\) is close to the number of samples in the smallest cluster, then this cluster will appear as an anomaly for most of the subsets. On the other hand, this property can also be beneficial to exclude anomalous clusters already in the initialization phase. Currently, there are no systematic comparisons in the literature on the size of the subsets in sampling-based clustering approaches [39]. In [35], the number of subsets was set to 10. Based on [30; 35], this selection appears reasonable for the sampling-based clustering initialization approaches.  
```
Input: Subsets \(\{\mathbf{X}_{1},\mathbf{X}_{2},...,\mathbf{X}_{S}\}\), #clusters \(K\), and #Lloyd's iterations \(T_{init}\). Output: Set of prototypes \(\mathbf{C}=\{\mathbf{c}_{1},\mathbf{c}_{2},...,\mathbf{c}_{K}\}\).
1:\(\mathbf{C}_{i}\leftarrow\) for each subset \(\mathbf{X}_{i}\) run K-means\(\parallel\).
2:\(\mathbf{C}_{i}\leftarrow\) for each subset \(\mathbf{X}_{i}\) run \(T_{init}\) Lloyd's iterations initialized with \(\mathbf{C}_{i}\).
3: Compute local SSE for each \(\mathbf{C}_{i}\) in \(\mathbf{X}_{i}\).
4:\(\mathbf{C}\leftarrow\) select prototypes corresponding to smallest local SSE.
```  
**Algorithm 2**SK-means\(\parallel\)  
The convergence rate of K-means is fast and the most significant improvements in the clustering error are achieved during the first few iterations [40; 41]. Therefore, for the initialization purposes, \(T_{init}\) can restricted, e.g., to 5 iterations. Moreover, since the number of Lloyd's iterations needed for convergence might vary significantly (e.g., [4]), a restriction on the number of Lloyd's iterations helps in synchronization, when a parallel implementation of the SK-means\(\parallel\) method is used.  
The computational complexity of the K-means\(\parallel\) method is of the order \(\mathcal{O}(rINM)\), where \(r\) is the number of initialization rounds. Therefore, SK-means\(\parallel\) also has the complexity of the order \(\mathcal{O}(rINM)\) in Step 1. In addition, SK-means\(\parallel\) runs \(T_{init}\) Lloyd's iterations with the complexity of \(\mathcal{O}(T_{init}KNM)\), and computes local SSE with the complexity of \(\mathcal{O}(KNM)\). Hence, the total complexity of SK-means\(\parallel\) is of the order \(\mathcal{O}(rINM+T_{init}KNM)\).