# Efficient High-Dimensional Kernel k-Means++ with Random Projection
## 4 Experiments
### Findings  
#### 4.6.1 Performance of Our Method for Centroid Initialization  
We first evaluated the initialization performance when the k-means++ was run in the projected subspace with our method. We compared the average performance in WCSS of our proposed k-means++ approximation method, with the average performance of the original version of the k-means++. Both Figures 2 and 3 show that the initialization performance in WCSS by our method is close to the baseline. The WCSS by our k-means++ approximation is always within the error bar (i.e., one standard deviation) of the WCSS distribution by the original k-means++. When the \(k\) is increasing, the error bar of the WCSS distribution by the original k-means++ is narrowing down, and the performance in WCSS by our k-means++ approximation method is still close to the baseline and falls within the error bar. Figure 3: WCSS of initial centers with the SMK-187 Dataset. Figure 2: WCSS of initial centers with the GLI-85 Dataset. We then evaluated the difference in initialization performance from our method against the baseline. We evaluated the degradation of the average performance of our proposed k-means++ approximation algorithms by comparing them with the original version of k-means++. The degradation of the average performance \(\epsilon\) in our experiment is defined as,  
\[\frac{|WOSS_{rp}-WOSS_{orig}|}{WOSS_{orig}} \tag{10}\]  
where \(WOSS_{rp}\) is the distance from our method after random projection and \(WOSS_{orig}\) is the distance from the original version of k-means++. The values \(\epsilon\) and the execution time are compared for different methods in Tables 1 and 2, respectively, to show the seeding performance on GLI-85, SMK-187 and the Reuters-21578 dataset. Throughout the experiments on the bioinformatics datasets of GLI-85, SMK-187, and the Reuters-21578 dataset, it is found that the dimensionality reduction using random projection does not induce any significant increase to the \(\epsilon\) of the center point initialization. The figures also show that the dimensionality could be reduced down to 10% of the original dimensionality, and the center point initialization still performs well with a small \(\epsilon\). In general, it is also found that the larger the number of clusters (i.e., the \(k\)), the smaller the \(\epsilon\) induced by our approximation. In the experiment on the Reuters-21578 dataset, since it is the largest dataset among three datasets, (i.e., \(n=21,578,D=2003\)), time improvement on the center point ini \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Dataset** & **d** & **k = 8** & **k = 10** & **k = 20** & **k = 50** \\ \hline \multirow{4}{*}{Reuters-21578 (D = 2003)} & baseline & 20.48 & 33.47 & 141.22 & 920.74 \\  & 200 & 8.61 & 11.49 & 26.28 & 135.16 \\  & 300 & 10.65 & 14.39 & 32.59 & 132.22 \\  & 401 & 13.03 & 17.89 & 41.63 & 175.59 \\ \hline \multirow{4}{*}{GLI-85 (D = 22283)} & baseline & 3.77 & 5.93 & 22.44 & 142.02 \\  & 2228 & 4.77 & 5.33 & 8.68 & 33.63 \\ \cline{1-1}  & 3342 & 6.7 & 7.24 & 11.21 & 37.07 \\ \cline{1-1}  & 4457 & 8.85 & 9.30 & 13.34 & 40.89 \\ \hline \multirow{4}{*}{SMK-187 (D = 19993)} & baseline & 5.96 & 8.88 & 32.27 & 194.97 \\ \cline{1-1}  & 1999 & 5.92 & 6.35 & 9.86 & 31.76 \\ \cline{1-1}  & 2999 & 8.48 & 8.97 & 12.97 & 38.41 \\ \cline{1-1}  & 3999 & 10.99 & 11.56 & 16.07 & 44.94 \\ \hline \end{tabular} The larger the dataset, the bigger the time improvement. There is a computational advantage for the proposed method with reduced execution time when k \(\geq\) 20 in general.  
\end{table} 
Table 2: Training time comparison.