|||
聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术[1]。作为一种常见的数据分析工具和无监督机器学习方法,聚类的目的是把数据集合分成若干类(或簇),使得每个类中的数据之间最大限度地相似,而不同类中的数据最大程度地不同。根据聚类算法所采用的基本思想,大致可以将它们分为五种[2],即划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的聚类。目前对聚类算法的研究正在不断深入,其中核聚类算法和谱聚类算法是近年来受到广泛关注的两种算法[3]。
核聚类方法的主要思想是通过一个非线性映射,将输入空间中的数据点映射到高维特征空间中,并选取合适的Mercer核函数代替非线性映射的内积,在特征空间中进行聚类。该方法是普适的,它比经典的聚类方法有较大的改进。它通过非线性映射增加了数据点线性可分的概率,即能较好地分辨、提取并放大有用的特征,从而实现更为准确的聚类,算法收敛速度也较快。在经典聚类算法失效的情况下,核聚类算法常常能得到较好的聚类结果[4]。
支持向量聚类(Support Vector Clustering, SVC)属于核聚类的一种,它以支持向量机(Support Vector Machine, SVM)为工具进行聚类[5]。它是Ben-Hur等在基于高斯核的SVDD(Support Vector Domain Description)算法基础上进一步发展起来的无监督非参数型的聚类算法[6]。它的基本思想是:利用高斯核,将数据空间中的数据点映射到一个高维的特征空间中。再在特征空间中寻找一个能包围所有数据点象的半径最小的球,将这个球映回到数据空间,则得到了包含所有数据点的等值线集。这些等值线就是簇的边界。每一条闭合等值线包围的点属于同一个簇[7, 8]。SVC算法主要分为两个阶段:SVC训练阶段和聚类分配阶段。其中SVC训练阶段包括高斯核宽度系数的确定、核矩阵的计算、Lagrange乘子的计算、支持向量的选取和高维特征空间中特征球半径的计算。聚类分配阶段首先生成邻接矩阵,然后根据邻接矩阵进行聚类分配[9]。
SVC算法具有两大显著优势:能产生任意形状的簇边界;能分析噪声数据点且能分离相互交叠的簇。这是许多聚类算法无法做到的。但SVC算法仍存在两个瓶颈: Lagrange乘子的计算和邻接矩阵的计算。相对而言,后者需要消耗的计算时间远比前者多[9]。因此很多新的SVC算法都旨在提高邻接矩阵的计算效率[10, 11]。
参考文献
[1] Xu R, Wunsch D. Survey of Clustering Algorithms. IEEE Transaction on Neural Networks, 2005, 16(3): 645-678.
[2] Han J, Kamber M. Data Mining: Concepts and Techniques, Second Edition. Morgan Kaufmann,
[3] Filippone M, Camastra F, Masulli F, Rovetta S. A Survey of Kernel and Spectral Methods for Clustering. Pattern Recognition, 2008, 41(1): 176-190.
[4] 张莉,周伟达,焦李成. 核聚类算法. 计算机学报, 2002, 25(6): 587-590.
[5] Burges C J C. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 1998, 2(2): 121-167.
[6] Tax D M J, Duin R P W. Support Vector Domain Description. Pattern Recognition Letters, 1999, 20(11-13): 1191-1199.
[7] Ben-Hur A, Horn D, Siegelmann H T, Vapnik V. Support Vector Clustering. Journal of Machine Learning Research, 2001, 2(12): 125-137.
[8] Scholkopf B, Williamson R, Smola A, Shawe-Taylor J, Platt J. Support Vector Method for Novelty Detection. Advances in Neural Information Processing System 12. 2000: 582-588.
[9] 吕常魁,姜澄宇,王宁生. 一种支持向量聚类的快速算法. 华南理工大学学报. 2005, 33(1): 6-9.
[10] Lee J, Lee D. An Improved Cluster Labeling Method for Support Vector Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(3): 461-464.
[11] Camastra F, Verri A. A Novel Kernel Method for Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(5):801-805.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-8-17 05:43
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社