A Conscience On-line Learning Approach for Kernel-Based Clustering

Chang-Dong Wang, Jian-Huang Lai, Jun-Yong Zhu

Abstract

Kernel-based clustering is one of the most popular methods for partitioning nonlinearly separable dataset. However, exhaustive search for the global optimum is NP-hard. Iterative procedure such as k-means can be used to seek one of the local minima. Unfortunately, it is easily trapped into degenerate local minima when the prototypes of clusters are ill-initialized. In this paper, we restate the optimization problem of kernel-based clustering in an on-line learning framework, whereby a conscience mechanism is easily integrated to tackle the ill-initialization problem and faster convergence rate is achieved. Thus, we propose a novel approach termed conscience on-line learning (COLL). For each randomly taken data point, our method selects the winning prototype based on the conscience mechanism to bias the ill-initialized prototype to avoid degenerate local minima, and efficiently updates the winner by the on-line learning rule. Therefore, it can more efficiently obtain smaller distortion error than k-means with the same initialization. Experimental results on synthetic and large-scale real-world datasets, as well as that in the application of video clustering, have demonstrated the significant improvement over existing kernel clustering methods.
BibTeX
@inproceedings{wang2010conscience,
  author = {Chang-Dong Wang and Jian-Huang Lai and Jun-Yong Zhu},
  title = {{A Conscience On-line Learning Approach for Kernel-Based Clustering}},
  booktitle = {ICDM},
  year = {2010},
  doi = {10.1109/icdm.2010.57},
}

Loading related content...

Figure