A Support Vector and K-Means Based Hybrid Intelligent Data Clustering Algorithm

Liang SUN  Shinichi YOSHIDA  Yanchun LIANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.11   pp.2234-2243
Publication Date: 2011/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.2234
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
data clustering,  kernel methods,  support vector clustering,   K-Means clustering,  

Full Text: PDF(3MB)
>>Buy this Article


Summary: 
Support vector clustering (SVC), a recently developed unsupervised learning algorithm, has been successfully applied to solving many real-life data clustering problems. However, its effectiveness and advantages deteriorate when it is applied to solving complex real-world problems, e.g., those with large proportion of noise data points and with connecting clusters. This paper proposes a support vector and K-Means based hybrid algorithm to improve the performance of SVC. A new SVC training method is developed based on analysis of a Gaussian kernel radius function. An empirical study is conducted to guide better selection of the standard deviation of the Gaussian kernel. In the proposed algorithm, firstly, the outliers which increase problem complexity are identified and removed by training a global SVC. The refined data set is then clustered by a kernel-based K-Means algorithm. Finally, several local SVCs are trained for the clusters and then each removed data point is labeled according to the distance from it to the local SVCs. Since it exploits the advantages of both SVC and K-Means, the proposed algorithm is capable of clustering compact and arbitrary organized data sets and of increasing robustness to outliers and connecting clusters. Experiments are conducted on 2-D data sets generated by mixture models and benchmark data sets taken from the UCI machine learning repository. The cluster error rate is lower than 3.0% for all the selected data sets. The results demonstrate that the proposed algorithm compared favorably with existing SVC algorithms.