# Efficient High-Dimensional Kernel k-Means++ with Random Projection
## 3 Our Method
### Efficient Initialization  
The k-means++ initialization algorithm is a popular initialization method for k-means with lower performance bounded by the statistical guarantee in [8]. We used random projection to approximate distances in the k-means++ algorithm to reduce the time complexity of \(O(nkD)\). We let \(Dist(\mathbf{x})\) denote the shortest distance from a data point \(\mathbf{x}\) to the closest center already chosen. Since the preservation of point-wise distances in random projection is guaranteed by the JL lemma [28], the dimensionality of the input data can be reduced for \(Dist(\mathbf{x})\) to remain close to its original value. The computation of the initialization can be reduced significantly, especially when the original dimensionality is very high.  
An expensive step in the k-means++ algorithm is to compute the weights \(Dist(\mathbf{x})^{2}\), which takes a new center \(\mathbf{c}_{i}\) and chooses \(\mathbf{x}\in\mathbf{X}\) with probability  
\[\frac{Dist(\mathbf{x})^{2}}{\sum_{\mathbf{x}\in\mathbf{X}}Dist(\mathbf{x})^{2}} \tag{8}\]Like kernel methods, after random projection, we do not need to have access to \(\mathbf{x}\) directly as \(Dist(\mathbf{x})^{2}\) is only required to be computed for choosing the initial center. We approximate \(Dist(\mathbf{x})^{2}\) as the original dimensionality of \(\mathbf{x}\), which can be very high and obtaining \(Dist(\mathbf{x})^{2}\) can be expensive.  
Unlike the work done by [PERSON] and [PERSON] et al. (2010, 2012); [PERSON] et al. (2010), our idea is to find a good approximation to \(Dist(\mathbf{x})^{2}\), which can be shown to be sufficiently close to the original value of \(Dist(\mathbf{x})^{2}\) and at the same time, computationally simple. By approximating \(Dist(\mathbf{x})^{2}\) in the k-means++ algorithm, we obtain an approximate algorithm to k-means++ with a complexity of \(O(nk)\). The approximation to \(Dist(\mathbf{x})^{2}\) can be obtained through random projections without perturbing the distances too much. We empirically show that these algorithms perform well on real-world datasets.  
It has been shown that k-means++ is \(O(log\ k)\)-competitive with the optimal clustering. The algorithm has been shown to improve both the speed and the accuracy of Lloyd's algorithm for k-means. We take advantage of the performance guarantee of k-means++ provided by Theorem 3.1, which states that \"if \(\mathbf{C}\) is constructed with k-means++, then the corresponding potential function satisfies, \(E[\phi]8(\ln k+2)\phi_{OPT}\).\" [8].  
Our proposed method for initialization is shown in Algorithm 3, which is called subroutine Algorithm 2. Algorithm 2 generates one of three types of random matrices for k-means++ with random projection, i.e., fixed random matrices, different random matrices for each iteration, and buffered random matrices (kmFRP, kmIRP, and kmBRP). Algorithm 3 obtains the random matrix generated in Algorithm 2, which computes the projected vectors with random projection and finds initial centers using data points projected into a lower-dimensional space in matrix \(\mathbf{X}^{proj}\).  
```
Input: type is the type of the random matrix, which can be kmFRP, kmIRP or kmBRP \(\mathbf{b}\) is required for the buffer size if type is kmBRP Output: \(\mathbf{R}\in\mathbb{R}^{D\times d}\) random matrix
1 Create buffer \(\mathbf{B}\) for the first time this subroutine is called such that \(\mathbf{B}:=\{\mathbf{R}_{1},\mathbf{R}_{2},\ldots,\mathbf{R}_{b}\}\) with the loop: for\(i\in 1,\ldots,b\)do\(\mathbf{R}_{i}=\overrightarrow{N}(0,1)\cdot\frac{1}{\sqrt{d}}\)2 end for if type is kmIRPthen\(\mathbf{R}=\overrightarrow{N}(0,1)\cdot\frac{1}{\sqrt{d}}\) elseif type is kmBRPthen i = (random integer mod \(b\)) +1 \(\mathbf{R}\leftarrow\mathbf{R}_{i}\) return \(\mathbf{R}\)
```  
**Algorithm 2**Proposed function to generate random matrix.