Efficient error minimization in kernel k-means clustering

Abstract Kernel k -means extends the k -means algorithm to identify non-linearly separable clusters but is inherently sensitive to cluster initialization. To address this challenge, we first formulate the kernel k-means ++ method, which conveys the efficient center initialization strategy of k -means++ from Euclidean to kernel space. Building on this, we propose global kernel k-means ++ ( $$\text {GK}k\text {M}$$ ++), a novel clustering algorithm designed to balance clustering error minimization with reduced computational cost. $$\text {GK}k\text {M}$$ ++ extends the well-established global kernel k -means algorithm by incorporating the stochastic initialization strategy of kernel k -means++. This approach significantly reduces computational complexity while preserving superior clustering error minimization capabilities akin to traditional global kernel k -means. The experimental results on synthetic, real, and graph datasets indicate that $$\text {GK}k\text {M}$$ ++ consistently outperforms both kernel k -means with random initialization and kernel k -means++, while achieving solutions comparable to those provided by the exhaustive and computational intensive global kernel k -means method.