第4卷第2期 智能系统学报 Vol 4 Ng 2 2009年4月 CAA I Transactions on Intelligent Systems Apr 2009 基于模糊K-har monic means的谱聚类算法 汪中2，刘贵全2，陈恩红2 (1中国科学技术大学计算机科学与技术学院，安徽合肥230027,2安徽省计算与通讯软件重点实验室，安徽合肥230027) 摘要：谱聚类作为一种有效的方法广泛应用于机器学习.通过分析谱聚类初始化敏感的实质，引入对初值不敏感 的模糊K-hamonic means算法来克服这一缺点，提出一种基于模糊K-hamonic means的谱聚类算法(FKM-SC).与 传统谱聚类算法以及对初值敏感的Kmeans.FCM算法相比，改进算法不仅可以识别有挑战性的人工数据，并且可以 得到稳定的聚类中心和聚类结果，同时提高了聚类的精确度.实验结果表明了该算法的有效性和可行性 关键词：谱聚类；模糊K-hamonic means初始化敏感；聚类中心 中图分类号：IP311文献标识码：A文章编号：1673-4785(2009)02-0095-05 A spectral clusterng a lgor ithm ba sed on fuzzy K-hamm on ic means WANG Zhong2,L U Gui-quan'2,CHEN En-hong' (1.School of Computer Science,University of Science and Technobgy of China,Hefei 230027,China;2 Key Laborabry of Sofware in Computing and Communication,Hefei 230027,China) A bstract:Spectral clustering is an effective method that is widely used in machine leaming After analyzing the es- sence of initialization sensitivity in spectral clustering,the fuzzy K-hamonic means (FKHM)algorithm was consid- ered to conquer spectral clustering's shortcom ings,then an spectral clustering algorithm based on FKHM was de- veloped Compared with the traditional spectral algorithm and the fuzzy cmeans (FCM)algorithm,the suggested algorithm is more sensitive to initial values The suggested algorithm can not only identify challenging artificial da- ta,but also find stable cluster centers and clustering results,considerably mproving clustering precision Experi- ments showed that it is an effective and feasible way to mprove the perfomance of spectral clustering algorithms Keywords:spectral clustering fuzzy K-hamonic means initialization sensitivity,cluster centers 聚类分析是数据挖掘、机器学习、模式识别等众聚类判据在放松了的连续域中的全局最优解.谱聚 多领域的重要工具.它在执行过程中没有任何关于类算法适用于非测度空间，算法与数据点维数无关， 类别的先验知识和假设，因而被称作是一种无监督而仅与数据点个数有关，因而可以避免由特征向量 的学习方法.近年来产生了大量解决该问题的相关的过高维数所造成的奇异性问题.谱聚类算法尽管 算法，现有的基于产生式模型和基于中心的聚类方 在实践中取得了很好的效果，但是算法本身仍存在 法仅在具有凸形结构的数据上有好的效果，且容易 许多值得研究的问题.文献[2]指出当聚类数目大 陷入局部最优 于实际聚类数时，多路谱聚类方法的效果很差； 为了能在任意形状的样本结构上聚类，且收敛 Fischet等提出了依赖于背景的相似性度量方法和尺 于全局最优，谱聚类算法被广泛应用.谱聚类的思想 度参数问题：由于谱方法的计算复杂度相当高， 来源于谱图划分山，是一种流行的高性能计算方 Fow lkes等提出使用Nystrom逼近方法减少求解特 法.该方法基于两点间的相似关系，利用数据的相似征问题的计算复杂度！：针对谱聚类初始化敏感的 矩阵的特征向量进行聚类，通过特征分解可以获得 特点，Ekn等提出使用对初始值不敏感的方法[) 收稿日期：2008-12-16 本文提出一种基于模糊K-hamonic means的谱 基金项目：国家自然科学基金资助项目(60775037)：教育部新世纪优 聚类算法，其主要思想是：首先分析不同数据输入顺 秀人才支持计划资助项目(NCET050549). 通信作者：汪中.Emai让wzpb@mail ustc edu cn 序对相似性矩阵、构造矩阵和生成矩阵的影响，得出 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 4卷第 2期 智 能 系 统 学 报 Vol. 4 №. 2 2009年 4月 CAA I Transactions on Intelligent System s Ap r. 2009 基于模糊 K2har monic means的谱聚类算法 汪 中 1, 2 , 刘贵全 1, 2 , 陈恩红 1, 2 (1. 中国科学技术大学 计算机科学与技术学院 ,安徽 合肥 230027; 2.安徽省计算与通讯软件重点实验室 ,安徽 合肥 230027) 摘 要 :谱聚类作为一种有效的方法广泛应用于机器学习. 通过分析谱聚类初始化敏感的实质 ,引入对初值不敏感 的模糊 K2harmonic means算法来克服这一缺点 ,提出一种基于模糊 K2harmonic means的谱聚类算法 ( FKHM2SC). 与 传统谱聚类算法以及对初值敏感的 K2means、FCM算法相比 ,改进算法不仅可以识别有挑战性的人工数据 ,并且可以 得到稳定的聚类中心和聚类结果 ,同时提高了聚类的精确度. 实验结果表明了该算法的有效性和可行性. 关键词 :谱聚类 ;模糊 K2harmonic means;初始化敏感 ;聚类中心 中图分类号 : TP311 文献标识码 : A 文章编号 : 167324785 (2009) 0220095205 A spectral cluster ing algor ithm based on fuzzy K2harmon ic means WANG Zhong 1, 2 , L IU Gui2quan 1, 2 , CHEN En2hong 1, 2 (1. School of Computer Science, University of Science and Technology of China, Hefei 230027, China; 2. Key Laboratory of Software in Computing and Communication, Hefei 230027, China) Abstract:Spectral clustering is an effective method that iswidely used in machine learning. After analyzing the es2 sence of initialization sensitivity in spectral clustering, the fuzzy K2harmonic means (FKHM) algorithm was consid2 ered to conquer spectral clustering’s shortcom ings, then an spectral clustering algorithm based on FKHM was de2 veloped. Compared with the traditional spectral algorithm and the fuzzy c2means (FCM) algorithm, the suggested algorithm is more sensitive to initial values. The suggested algorithm can not only identify challenging artificial da2 ta, but also find stable cluster centers and clustering results, considerably imp roving clustering p recision. Experi2 ments showed that it is an effective and feasible way to imp rove the performance of spectral clustering algorithm s. Keywords: spectral clustering; fuzzy K2harmonic means; initialization sensitivity; cluster centers 收稿日期 : 2008212216. 基金项目 :国家自然科学基金资助项目 (60775037) ;教育部新世纪优 秀人才支持计划资助项目 (NCET20520549). 通信作者 :汪 中. E2mail: wzspb@mail. ustc. edu. cn. 聚类分析是数据挖掘、机器学习、模式识别等众 多领域的重要工具. 它在执行过程中没有任何关于 类别的先验知识和假设 ,因而被称作是一种无监督 的学习方法. 近年来产生了大量解决该问题的相关 算法 ,现有的基于产生式模型和基于中心的聚类方 法仅在具有凸形结构的数据上有好的效果 ,且容易 陷入局部最优. 为了能在任意形状的样本结构上聚类 ,且收敛 于全局最优 ,谱聚类算法被广泛应用. 谱聚类的思想 来源于谱图划分 [ 1 ] ,是一种流行的高性能计算方 法. 该方法基于两点间的相似关系 ,利用数据的相似 矩阵的特征向量进行聚类 ,通过特征分解可以获得 聚类判据在放松了的连续域中的全局最优解. 谱聚 类算法适用于非测度空间 ,算法与数据点维数无关 , 而仅与数据点个数有关 ,因而可以避免由特征向量 的过高维数所造成的奇异性问题. 谱聚类算法尽管 在实践中取得了很好的效果 ,但是算法本身仍存在 许多值得研究的问题. 文献 [ 2 ]指出当聚类数目大 于实际聚类数时 ,多路谱聚类方法的效果很差 ; Fischer等提出了依赖于背景的相似性度量方法和尺 度参数问题 [ 3 ] ;由于谱方法的计算复杂度相当高 , Fowlkes等提出使用 Nystrom 逼近方法减少求解特 征问题的计算复杂度 [ 4 ] ;针对谱聚类初始化敏感的 特点 , Ekin等提出使用对初始值不敏感的方法 [ 5 ] . 本文提出一种基于模糊 K2harmonic means的谱 聚类算法 ,其主要思想是 :首先分析不同数据输入顺 序对相似性矩阵、构造矩阵和生成矩阵的影响 ,得出