# Efficient High-Dimensional Kernel k-Means++ with Random Projection
## 1 Introduction  
The clustering problem is one of the oldest and most important problems in machine learning. k-means clustering has attracted increasing attention recently. It can be used in many fields, such as market segmentation, social network analysis, and astronomical data analysis. k-means clustering is an NP-hard problem. In this problem, we are given \(n\) data points,  
\[\mathbf{X}=\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\} \tag{1}\]  
in the \(D\)-dimensional space. The goal is to separate the points \(\mathbf{X}\) into \(k\) clusters \(\mathbf{C}\),  
\[\mathbf{C}=\{\mathbf{C}_{1},\mathbf{C}_{2},\ldots,\mathbf{C}_{k}\} \tag{2}\]  
where \(\mathbf{C}_{i}\) denotes the \(i\)-th cluster, so as to minimize the potential function, which is the total sum of squared distances between each point to its closest center. That is,  
\[\operatorname*{arg\,min}_{C}\sum_{i=1}^{k}\sum_{\mathbf{x}\in\mathbf{C}_{i}} \|\mathbf{x}-\mathbf{c}_{i}\|^{2} \tag{3}\]  
where \(\mathbf{c}_{i}\) denotes the center point of the \(i\)-th cluster. Data in high dimensionality has become an increasingly frequent problem in machine learning. Memory and the computational cost would be reduced if dimensionality can be reduced. To deal with this issue, plenty of techniques have been proposed, such as locally linear embedding, principle component analysis (PCA), ISOMAP, and multidimensional scaling. However, high computational training overheads and complex proceduresare involved with a lot of the proposed methods, especially with very high-dimensional data. Because of this, there has been a surge of interest in new, simple and more computationally efficient techniques using random projection for very high-dimensional data, for example, [3; 4; 5]. In addition, kernel k-means is a popular method due to the fact that k-means clustering utilizes the Euclidean distance metric to calculate the similarity between data points, implying that only linearly separable clusters in the original input space can be found. Obviously, the measure is not suitable for just any dataset. With kernel methods, data in the original input space is explicitly mapped into a different feature space through the user-specified kernel function. Features in data points are mapped to higher dimensional feature spaces. Putting data points in higher dimensional spaces after they have been mapped is a reasonable approach without the assumption that data points are linearly separable, which is also applicable for traditional k-means clustering. This advantage has made kernel k-means popular in recent years [6; 7]. Kernel k-means, which is an extension of k-means, computes kernels instead of the Euclidean distance for point-wise distances. Kernel k-means projects data points into high-dimensional kernel space and performs k-means clustering in the mapped feature space to allow non-linearly separable clusters. In kernel k-means, it is required to compute an \(n\times n\) kernel matrix with feature vectors in the original space, and the computation cost is a function of \(n\) and the \(D\). To improve the performance with centroid initialization, the k-means++ seeding algorithm [8] is used to obtain \(k\) initial centers, which give the expected \(O(log\ k)\) approximation ratio, as shown by [PERSON] and [PERSON]. In [8], the k-means++ algorithm is introduced, which is a seeding algorithm for k-means to replace the uniform distribution of Lloyd's initialization with a probability distribution given by the points' squared distances from the closest chosen centers as the weights, i.e., the weight for data point \(\mathbf{x}\) is \(\frac{Dist(\mathbf{x})^{2}}{\sum_{\mathbf{x}\in\mathbf{X}}Dist(\mathbf{x})^{2}}\) with \(Dist(\mathbf{x})\) denoting the shortest distance to the closest center already chosen. k-means++ provides a performance guarantee of only a constant factor from the optimum and is proven to be \(O(log\ k)\)-competitive.