Fast kernel k-means clustering using incomplete Cholesky factorization

Highlights：

• The fast kernel k -means clustering algorithm using InCF is proposed. This new algorithm uses low-rank approximation version of the full kernel matrix and linear k -means clustering algorithm to accelerate kernel k -means clustering and save memory space.

• We prove that the clustering error by our fast kernel k -means clustering using InCF method reduces exponentially as the rank of the approximate matrix increases.

• Experimental results show that the performance of the proposed algorithm is similar to that of the kernel k -means clustering algorithm, but our method can deal with large-scale datasets.

摘要

•We prove that Incomplete Cholesky Factorization (InCF) can generate a rank s approximate matrix for kernel matrix after s iterations, and the approximation error decreases exponentially as the number of iterations increases when the eigenvalues of kernel matrix decay exponentially sufficiently fast.•The fast kernel k -means clustering algorithm using InCF is proposed. This new algorithm uses low-rank approximation version of the full kernel matrix and linear k -means clustering algorithm to accelerate kernel k -means clustering and save memory space.•We prove that the clustering error by our fast kernel k -means clustering using InCF method reduces exponentially as the rank of the approximate matrix increases.•Experimental results show that the performance of the proposed algorithm is similar to that of the kernel k -means clustering algorithm, but our method can deal with large-scale datasets.