## 4 Empirical Evaluation of Proposed Algorithms
### Experiments with High-Dimensional Synthetic Datasets  
Finally, to strengthen the evaluation, we next summarize experiments with novel synthetic datasets, where symmetric, spherical clusters are hidden in a very high-dimensional space. Comparison of K-means initialization methods for datasets with assured spherical shape is clearly relevant because K-means restores such geometries during the clustering process [4; 6; 44]. Please note that using SSE for high-dimensional data can be ambiguous [52]. As we will next demonstrate, the SSE error difference of good and bad clustering results in a high-dimensional space can be surprisingly small. To show this, we also analyze the final clustering accuracy with normalized mutual information (NMI) [53] with the actual entropies. Please note that it would have been uninformative to use NMI as a quality measure for datasets in Section 4.1 because there we had no information on the cluster geometry. Mutual Information (MI) can be defined as  
\[\text{MI}(\textbf{L},\textbf{L})=\sum_{k=1}^{K}\sum_{i=1}^{K^{*}}\frac{n_{k}^{ (i)}}{n}\log_{2}\frac{\frac{n_{k}^{(i)}}{n}}{\frac{n^{(i)}}{n}\frac{n_{k}}{n}}, \tag{2}\]  
Figure 1: Scalability. where **I** refers to the cluster labels, **L** to the ground truth labels, \(K^{*}\) to the number of unique ground truth labels, and \(n\) denotes labels' frequency counts. Then, NMI can be defined as  
\[\text{NMI}(\textbf{I},\textbf{L})=\frac{2\text{MI}(\textbf{I},\textbf{L})}{H( \textbf{I})+H(\textbf{L})}, \tag{3}\]  
where \(H(\textbf{I})=\text{log}_{2}(K)\) and \(H(\textbf{L})=\text{log}_{2}(K^{*})\) denote the entropies of the cluster labels and ground truth labels. Details of the six generated datasets with Algorithm 4 are summarized in Table 5. The generated datasets are referred as M-spheres. For each dataset, we set \(N_{K}=10,000\), \(K=10\), and \(d_{r}=1\). To demonstrate interesting effects in the clustering initialization, we varied the nearest cluster center distance as \(d_{c}=\{0.05,0.1,0.2\}\) and the data dimension as \(M=\{1000,10,000\}\). We set \(d_{c}\) values to much smaller than \(d_{r}\) in order to increase the difficulty of the clustering problems. In Figure 2, PCA projections on the three largest principal components show that the clusters are more separated for \(M=10,000\) than for \(M=1000\). For the M-spheres datasets, we used the serial implementations of the initialization methods with the same settings as before. Results for the final clustering accuracy using NMI with 100 repeats are shown in Figure 3. Clearly, SRPK-means\(\parallel\) outperforms other methods in terms final clustering accuracy for all the synthetic datasets. Moreover, if we compare the results between the datasets with \(M=1000\) and \(M=10,000\), we observe that the clustering accuracy for SRPK-means\(\parallel\) is improved when the dimensionality increases. The most significant difference is obtained for the M-spheres-M10k-\(d_{c}0.05\) dataset, where K-means\(\ast\)+ has a total breakdown of the accuracy while SRPK-means\(\parallel\) is able find the near optimal clustering result out of 100 repeats. Moreover, the accuracy of K-means\(\ast\)+ is clearly worse compared to K-means\(\parallel\) and SK-means\(\parallel\) for very high-dimensional datasets. We tested K-means with random initialization for this dataset and observed from the statistical testing that K-means++, K-means\(\parallel\) and SK-means\(\parallel\) are no better than the random initialization in terms of NMI. These results demonstrate that the use of distances in the K-means++ type of initialization strategies can become meaningless in very high-dimensional spaces. In Figure 4, scatter plots of SSE and NMI values show that the relative SSE difference between worst possible clustering result (\(\text{NMI}=0\)) and the optimal clustering result (\(\text{NMI}=1\)) can be surprisingly small for very high-dimensional data.