The Global Kernel k-Means Algorithm for Clustering in Feature Space

Kernel k-means is an extension of the standard k-means clustering algorithm that identifies nonlinearly separable clusters. In order to overcome the cluster initialization problem associated with this method, we propose the global kernel k-means algorithm, a deterministic and incremental approach to...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on neural networks 2009-07, Vol.20 (7), p.1181-1194
Main Authors: Tzortzis, G.F., Likas, A.C.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial Intelligence
Clustering
Clustering algorithms
Clusters
Computational complexity
Computational efficiency
Computer science
control theory
systems
Computer Simulation
Connectionism. Neural networks
Costs
Data Interpretation, Statistical
Data processing. List processing. Character string processing
Exact sciences and technology
graph partitioning
Iterative algorithms
k -means
Kernel
kernel k -means
Kernels
Mathematical models
Memory organisation. Data processing
Neural networks
Neural Networks (Computer)
Optimization methods
Partitioning algorithms
Pattern Recognition, Automated
Searching
Signal Processing, Computer-Assisted
Software
Software Validation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kernel k-means is an extension of the standard k-means clustering algorithm that identifies nonlinearly separable clusters. In order to overcome the cluster initialization problem associated with this method, we propose the global kernel k-means algorithm, a deterministic and incremental approach to kernel-based clustering. Our method adds one cluster at each stage, through a global search procedure consisting of several executions of kernel k-means from suitable initializations. This algorithm does not depend on cluster initialization, identifies nonlinearly separable clusters, and, due to its incremental nature and search procedure, locates near-optimal solutions avoiding poor local minima. Furthermore, two modifications are developed to reduce the computational cost that do not significantly affect the solution quality. The proposed methods are extended to handle weighted data points, which enables their application to graph partitioning. We experiment with several data sets and the proposed approach compares favorably to kernel k-means with random restarts.
ISSN:1045-9227
1941-0093
DOI:10.1109/TNN.2009.2019722