## 3 New Algorithms
### SRPK-Means\(\parallel\)  
The second novel proposal, Subset Random Projection K-means\(\parallel\) (SRPK-means\(\parallel\)), adds RPs to SK-means\(\parallel\). Since SK-means\(\parallel\) mainly uses time in computing distances in Steps 1 and 2, it is reasonable to speed up the distance computation with RP. The RP-based method is presented in Algorithm 3. Generally, SRPK-means\(\parallel\) computes a set of candidate initial prototypes in a lower-dimensional space and then evaluates these in the original space. As with Algorithm 2, the best set of prototypes based on the local SSE are selected. ```
Input: Subsets \(\{\mathbf{X}_{1},\mathbf{X}_{2},...,\mathbf{X}_{S}\}\), #clusters \(K\), #Lloyd's iterations \(T_{init}\), and random projection dimension \(P\). Output: Set of prototypes \(\mathbf{C}=\{\mathbf{c}_{1},\mathbf{c}_{2},...,\mathbf{c}_{K}\}\). 1:\(\mathbf{R}_{i}\leftarrow\) for each subset \(\mathbf{X}_{i}\) generate \(M\times P\) random matrix. 2:\(\widetilde{\mathbf{X}}_{i}\leftarrow\) for each subset \(\mathbf{X}_{i}\) compute \(\frac{1}{\sqrt{P}}\mathbf{X}_{i}\mathbf{R}_{i}\)
3:\(\widetilde{\mathbf{C}}_{i}\leftarrow\) for each \(\widetilde{\mathbf{X}}_{i}\) run K-means\(\parallel\). 4:\(\mathbf{I}_{i}\leftarrow\) for each \(\widetilde{\mathbf{X}}_{i}\) run \(T_{init}\) Lloyd's iterations initialized with \(\widetilde{\mathbf{C}}_{i}\). 5: For each partitioning \(\mathbf{I}_{i}\) compute prototypes \(\mathbf{C}_{i}\) in original space \(\mathbf{X}_{i}\). 6: Compute local SSE for each \(\mathbf{C}_{i}\) in \(\mathbf{X}_{i}\). 7:\(\mathbf{C}\leftarrow\) select prototypes corresponding to smallest local SSE. ```  
**Algorithm 3**SRPK-means\(\parallel\)  
The proposal first computes a unique random matrix for each subset \(\mathbf{X}_{i}\). Then, the \(P\)-dimensional random projected subset \(\widetilde{\mathbf{X}}_{i}\) is computed in each subset \(\mathbf{X}_{i}\). Steps 3-4 are otherwise the same as the Steps 1-2 in Algorithm 2, but these steps are applied for the lower-dimensional subsets \(\{\widetilde{\mathbf{X}}_{1},\widetilde{\mathbf{X}}_{2},...,\widetilde{ \mathbf{X}}_{S}\}\). Next, the labels \(\mathbf{I}_{i}\) for partitioning each subset are used to compute \(\mathbf{C}_{i}\) in the original space \(\mathbf{X}_{i}\). Finally, the local SSEs are computed, and the best set of prototypes are returned as the initial prototypes. Please note that the last two steps in Algorithm 3 are the same as Steps 3-4 in Algorithm 2. SRPK-means\(\|\) computes projected data matrices, which require a complexity of \(\mathcal{O}(PNM)\) (naive multiplication) [17]. Execution of K-means\(\|\) in the lower-dimensional space requires \(\mathcal{O}(rlNP)\), and \(T_{init}\) Lloyd's iterations requires \(\mathcal{O}(T_{init}KNP)\) operations. Step 6 requires \(\mathcal{O}(KNM)\) operations, since it computes the local SSEs in the original space, so that the total computational complexity of the SRPK-means\(\|\) method is \(\mathcal{O}(PNM+rlNP+T_{init}KNP+KNM)\). Typically, applications of RP are based on the assumption \(P<<M\). Thus, when the dimension of data \(M\) is increased, the contribution of the second and the third term of the total computational complexity start to diminish. Moreover, when both \(M\) and \(K\) are large compared to \(P\), the last term dominates the overall computational complexity. Therefore, in terms of running time, SRPK-means\(\|\) is especially suited for clustering large-scale data with very high dimensionality into a large number of clusters. [PERSON] and [PERSON] [18] noted that clustering with RP produces highly unstable and diverse clustering results. However, this can be exploited in clustering to find different candidate structures of data, which then can be combined into a single result [18]. The proposed initialization method in this paper uses a similar idea as it tries to find structures from multiple lower-dimensional spaces that minimize the local SSE.