Efficient High-Dimensional Kernel k-Means++ with Random Projection

Applied Sciences

Jan Y. K. Chan¹  Alex Po Leung¹  Yunbo Xie¹ 

[1] Faculty of Information Technology, Macau University of Science and Technology, Taipa 999078, China;

关键词: kernel k-means;    k-means++;    random projection;    dimensionality reduction;    high dimensional data;   

DOI  :  10.3390/app11156963

来源: DOAJ

【 摘 要 】

Using random projection, a method to speed up both kernel k-means and centroid initialization with k-means++ is proposed. We approximate the kernel matrix and distances in a lower-dimensional space ${\mathbb{R}}^d$ before the kernel k-means clustering motivated by upper error bounds. With random projections, previous work on bounds for dot products and an improved bound for kernel methods are considered for kernel k-means. The complexities for both kernel k-means with Lloyd’s algorithm and centroid initialization with k-means++ are known to be $O\left(nkD\right)$ and $\Theta \left(nkD\right)$, respectively, with n being the number of data points, the dimensionality of input feature vectors D and the number of clusters k. The proposed method reduces the computational complexity for the kernel computation of kernel k-means from $O\left(n^{2}D\right)$ to $O\left(n^{2}d\right)$ and the subsequent computation for k-means with Lloyd’s algorithm and centroid initialization from $O\left(nkD\right)$ to $O\left(nkd\right)$. Our experiments demonstrate that the speed-up of the clustering method with reduced dimensionality $d=200$ is 2 to 26 times with very little performance degradation (less than one percent) in general.

【 授权许可】

Unknown