The global kernel k-means algorithm for clustering in feature space.

Area of Science:

• Machine Learning
• Data Mining
• Computational Statistics

Background:

• Standard k-means clustering struggles with nonlinearly separable data.
• Kernel k-means extends k-means for nonlinear patterns but suffers from initialization sensitivity.
• Existing methods often fall into local optima, limiting clustering performance.

Purpose of the Study:

• To propose a novel, initialization-independent kernel-based clustering algorithm.
• To address the limitations of standard kernel k-means, particularly its sensitivity to initial cluster centroids.
• To develop a robust method for identifying nonlinearly separable clusters.

Main Methods:

• Introduced the global kernel k-means algorithm, a deterministic and incremental approach.
• Employed a global search procedure involving multiple kernel k-means executions with suitable initializations.
• Developed modifications to reduce computational cost without significant impact on solution quality.
• Extended the algorithm to handle weighted data points for graph partitioning applications.

Main Results:

• The global kernel k-means algorithm demonstrates independence from initial cluster configurations.
• The method successfully identifies nonlinearly separable clusters.
• Experimental results show favorable comparisons against kernel k-means with random restarts.
• The algorithm effectively avoids poor local minima, achieving near-optimal solutions.

Conclusions:

• The proposed global kernel k-means algorithm provides a robust and effective solution for kernel-based clustering.
• It overcomes critical initialization challenges inherent in kernel k-means.
• The algorithm's efficiency and effectiveness are suitable for complex datasets and graph partitioning tasks.