Can I read Efficient High-Dimensional Kernel k-Means++ with Random Projection on EtoBox?

Efficient High-Dimensional Kernel k-Means++ with Random Projection by Chan, Jan Y. K. (author);Leung, Alex Po (author);Xie, Yunbo (author) is a Engineering article available to read on EtoBox.

What is Efficient High-Dimensional Kernel k-Means++ with Random Projection about?

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 Rd 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(nkD) and Θ(nkD), 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(n2D) to O(n2d) and the subsequent computation for k-means with Lloyd’s algorithm and centroid initialization from O(nkD) to O(nkd). 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.

Who reads Efficient High-Dimensional Kernel k-Means++ with Random Projection?

Author

Chan, Jan Y. K. (author);Leung, Alex Po (author);Xie, Yunbo (author)

Publisher

MDPI AG

Published

2021

Language

EN

Field

Engineering (Physical Sciences)