特征空间属性加权模糊核聚类算法

特征空间属性加权模糊核聚类算法 特征空间属性加权模糊核聚类算法 第26卷第8期 2006年8月 计算机应用 ComputerApplications V0l_26No.8 Aug.2006 文章编号:1001—9081(2006)08—1888—02 特征空间属性加权模糊核聚类算法 范新南,沈红斌,陈学忠 (1.河海大学计算机及信息工程学院,江苏常州213022; 2.上海交通大学图像处理与模式识别研究所,上海2o003O) (fanxn@hhuc.edu.an) 摘要:充分考虑了属性间的不平衡性,通过Mercer核把原始的观察空间映射到高维特征空间, 提出了一种新的特征空间中的加权模糊核聚类算法WFKCA.众多实例表明,WFKCA比传统的聚类 算法具有更好的性能,且对于高维数据具有很好的聚类效果. 关键词:模糊聚类;核;模式识别 中图分类号:TP3l1.13l文献标识码:A Newmercer-kernelbasedFuzzyclusteringalgorithm withattributeweightsinfeaturespace FANXin—nan,SHENHong—bin',CHENXue—zhong (1.CollegeofCompmerandInformationEngineering,HohaiUniversity;ChangzhouJiangs u213022,China; 2.InstituteofImageProcessingandPatternRecognhion,ShanghaiJiaotongUniversity,Shan ghai200030,China) Abstract:Consideringtheimbalancebetweentheattributesfully,anewweightedfuzzykerne l—clusteringalgorithm namedWFKCAwaspresented.WFKCAperformsclusteringinhighfeaturespacemappedb ymercerkernels.Lotsofexamples demonstratethatWFKCAisausefulclusteringtoo1. Keywords:Fuzzyclustering;kernel;patternrecognition 0引言 聚类分析是数据分析,理解与数据可视化的有效工 具.给定一个数据集厂={.,,…,}CR,聚类 分析的目的在于根据某种相似性原则将厂分成C个类别.聚 类分析是统计理论,数据挖掘和模式识别领域中的一个重要 课题.J.聚类分析理论已经在众多领域得到了广泛应用:在 商业竞争中,聚类分析能帮助商家在客户数据库中根据客户 的购物模式发现不同的组别,从而更优地决策;在信息迅速增 长的今天,聚类算法能有效的进行文本分类;作为数据挖掘的 有效工具,聚类分析能帮助理解数据的不同分布,观察各个类 别的不同性质,从而对其中感兴趣的类别进行进一步的分析. 对于常用的基于分割的聚类算法而言,其一般的方法是用c 个类中心向量(=1,2,…,C)?R来代表每个类,根据相 似性原则把样本五分到射类别中. 假设每个数据样本有个属性:={d,,…,l, 传统的聚类算法,如K—means,FCM等都假设样本的属性对每 个类别是平等重要的.但实际上,不同的属性对于不同类别 的贡献可能是不相同的.文献[5]提出了在聚类分析之前进 行特征选择的方法选择重要的特征进行聚类.由于文献[5] 在聚类分析之前就确定了重要的属性,因此聚类结果的好坏 与产生数据样本的物理背景将密切相关;另外,它假设所有的 类别都具有相同的重要属性集合,而实际上,不同的类别的重 要属性集合可能并不是一致的. 为了解决这一问题,可以在聚类过程中根据不同类的具 体特性动态计算各个属性对于不同类别的重要性.文献[6] 提出了观察空间加权距离度量的硬聚类算法;文献[7]提出 了两个观察空间加权距离度量的模糊聚类算法SCADI, SCAD2.文献[6,7]所阐述的算法都存在和FCM一样的缺 点:它们适用于团状数据集,但对于非团状的一般高维数据集 的聚类则往往得不到理想的结果.一个解决非团状数据集的 聚类方法是用核函数把数据从观察空间映射到高维特征空 间Is.9].但传统的核聚类算法存在两个缺点:1)核聚类算 法的聚类中心很难理解和表示;2)忽略了特征空间中的属性 不平衡性.为此,本文提出了加权模糊核聚类算法WFKCA, 在聚类分析中动态计算属性问的不平衡性.实验结果表明, 对如高维非团状数据集,WFKCA比传统的聚类算法具有更 好的效果. 1加权模糊核聚类算法WFKCA 假设咖为一非线性映射函数,咖:p一咖(p)?HS,其中 P?OS,是观察空间的一个样本,表示映射以后的高维特 征空间.我们提出以下WFKCA的目标函数: CL 嗍以ll咖()一咖()ll() C s.t.?[0,1]And?=11??N(2)i:t L 埘?[0,1]And?埘=ll?i?C(3)=1 其中c为类别数,=(.,,…,)是第i类中心, 表示第广样本属于第类的隶属度;tt,代表第k个属性对 收稿日期:2006—02—16;修订日期:2006—04—14 作者简介:范新南(1964一),男,江苏常州人,副教授,博士,主要研究方向:图形图像处 理,计算机网络通信;沈红斌(1979一),男,江苏镇 江人,博士,主要研究方向:模式识别,生物信息学;陈学忠(1968一),男,江苏常州人, 副教授,主要研究方向:数据挖掘,图像处理. 第8期范新南等:特征空间属性加权模糊核聚类算法1889 于第i类的权重,rt'b>1,>1. 根据式(1)可以得到: ll()一()=().()一2().()+ ().() = K(,)一2K(x~,)+K(,) (4) 其中,K(x,Y)=(b()?(b(y)为用户定义的核映射函数. 如果采用常用的高斯核函数: K(x,歹)…p() 那么K(,):1,则(1)就演变为: -,,=2???(1一K(xsk)) =2 耋砉砉L_ti1i11(一exp(二1/1/=2???(1一ex11=…,, (5) 式(5)对求偏导得: OJwFKCA = 4b' …p ()) = 0(6) 解式(6)得: m … 1. …j=l芦Or?…1 根据W的不同取值,得到: fv=0ifW.k=0 ??K(xjk,)? 上—————一if?0 ??K(,)』=1 (8) C 由?=1,根据拉格朗日方程得到以下无限制方程:i=l ?A(?一1)j:li=l 其中,为拉各朗日系数. 式(9)对,并最终解得: 1 = r=l L ?wq~(1一(~Vil,))I=l , ?以(1一K(xs,,))k:l 同理,由?W=1得到以下的无限制函数:'=l C, "=2???以(1一K(,))一…111 C, ?A(?一1) 解得: 1 (1一(,)) (1一(,)) (9) (10) (12) (1),(8),(10),(12)构成了WFKCA聚类算法. 2实例分析 2.1IRIS数据集测试 这个实例中,我们用标准数据集IRIS来测试FCM, SCAD1,SCAD2和WFKCA算法的性能.IRIS数据集共有150个样本,分成3类,其中,每个样本有4个属性=.,, .,}.设定参数m:2,JB=2,为标准方差. 表1给出了各算法在100次实验中的平均性能,除了 SCAD2外所有算法的起始中心点为随机产生.实验结果发 现,SCAD2对起始中心的选择非常敏感,表1给出了随机选 择中心SCAD2—1以及把FCM迭代10次后的中心点作为起 始中心点的SCAD2_2的性能比较,可以发现,SCAD2_2性能 比SCAD2—1有很大提高. 表l各算法在IRIS标准数据集的性能比较 从表1可以看出,WFKCA最终的聚类结果在四个算法中 是最好的.同时,表1也证明了WFKCA,SCAD1及SCAD2的 算法收敛迭代次数要比FCM少,这和WFKCA,SCAD1和 SCAD2的权重系数在迭代过程中所产生的引导作用密切相关. 2.2高维数据聚类分析 本实例采用文献[11]中鉴别宋代官汝窑器与民汝窑器 . 的数据作为测试数据集,该数据集中每个样本有10个属性表2给出了各算法在100次试验中在该数据集上的平均聚类 结果.从结果可以看出来,WFKCA具有最好的性能.这表明 WFKCA算法在处理高维数据集中同样存在着优势. 表2高维数据各算法性能比较 3结语 传统的聚类算法,如FCM等对于"非团状"的数据集很 难得到理想的聚类结果,主要是由于下面的原因: (1)算法在观察空间中进行聚类分析,对"团状"数据集 有效,但对一些更一般的数据集,特别是高维数据集将不能得 到理想的结果; (2)传统的聚类算法,如FCM等,忽略了属性间的不平 衡性,而这一点在实际生活中常常存在. 本文基于核函数,将数据集从观察空间映射到高维特征 空间,提出了特征空间中新的属性加权模糊核聚类算法 WFKCA.实验表明,对于一般高维数据集,WFKCA能更好地 反映属性间的不平衡性,并得到很好的聚类结果. (下转第1915页) 一 一 以 ? ? 2 =一 ,, 扣一 Il 第8期黎升洪等:线性时态逻辑中的特性模式1915 3)将特性LTL公式翻译为一个自动机. 4)计算自动机与全局有限状态自动机的同步积,形成一 个自动机. 5)检查最后这个自动机的语言是否为空.如果为非空, 则所描述的进程满足指定的特性模式. 6)SPIN中,m公式用来描述坏的特性模式,如果自动 机的语言为非空,则知道描述的系统不能满足特性模式要求, 此时可以发现反例,这对调试非常有用. Global BeforeR AfterO BetweenOandR AfterOuntilR QQRQ 图2特性作用范围 图3特性模式的分类 这里,给出一个如图3所示的状态图,其对应的SPIN代 码如下所示. intx=0,Y=0; prectypopl()I d0 =atomic【(Y<2)&&(x<3)一>x=x+1) od1 proctypop2()I d0 =atomic【(x+y)==3一>x=0) =atomic【(xY)==4一>Y=0) od1 proctypop3()I d0 =atomic【(Y<2)&&(x<3)一>x=x+1) od1 initI runpl(); runp2(); runp3()) 在SPIN4.2.5下,分别验证其下列特性: 1)安全性示例:验证系统是否满足L1.L公式口?(+Y) =1,通过SPIN验证和仿真功能,发现(x,y)的冲突序列为: (0,0),(1,0),(2,0),(2,1),[(2,2),(0,2),(1,2)]}. 2)活性示例:验证系统是否满足口(2x>Y),通过SPIN 验证和仿真功能,发现冲突序列为:(0,0). 3)响应性示例:验证系统是否满足口((+y= 1)等?(+Y=3),通过SPIN验证功能,特性可满足. 6结语 高层次的定义和抽象是自动编写形式化规格说明的重要 方法,线性时态逻辑特性模式特别适用于有限状态验证工具 SPIN中的规格说明.本文从特性模式的分类和作用范围描 述LTL公式,对自动编写系统规格说明特性有很大帮助,如 文献[7]给出了SPIN中常用的特性模式是其应用的一个方 面. 参考文献: 【11CLARKEEM,SCHLINGLOFFBH.MedelChecking[AI.Handbook ofAutomatedReasoning[C1.BandII,S.Elsevier,2001.1637— 179o. [21BI~RARDB,BIDOITM,FINKELA.SystemsandSoftwareVerifiea- fion:Model?CheckingTechniquesandTools[MI.Berlin:Springer, 1999. 【31KRIPKESA.Semanticalconsiderationsonmedallogic【J1.Acta PhilesophieaFenniea,1963,16:83—94. 【41PNUELIA.TheTemporalSemanticsofConcm'rentPrograms【A】. ProceedingsoftheInternationalSympoisumonSemanticsofConcur- rentComputation,LectureNotesInComputerScience[C1.Springer- Verlag,1979,Vol70. 【51BEN—ARIM,PNUELIA,MANNAZ.TheTemporalcofBranch— ingTime[J1.ActaInformatica,1983,20(3):207—226. 【61EMERSONEA,HALPERNJY."Sometimes"and"NotNever" visited:onbranchingverBuslineartimetemporallogic[J1.Joumal oftheACM,1986,33(1):151—178. 【71HOLZMANNGJ.SpinModelChecker:.ThePrimerandReference Manual[MI.NewYork:AddisonWesley,2003.608. 【81HOLZMANNGJ.Designandvalidationofcomputerprotocols[MI. 78. London:PRENTICE?HALL,1991.22— 【91HOLZMANNGJ.TheModelCheckerSPIN[J1.IEEEtrausactionson softwareengineering,1997,23(5). (上接第1889页) 参考文献: H0PPERF.Fuzzyclusteranalysis【M】.Chichester:JohnWiley, l999. HANJW,KAMBERM.Datamining:ConceptandTechniques【M】. SanMatco:MorganKanfnlann,2001. BEZDEKJC.Patternrecognitionwithfuzzyobjectivefunctionalgo- rithms【M】.NewYork:HenumPress,1981. 沈红斌,王士同.离群模糊核聚类算法【J】.软件,2004,15 (7):1021—1029. YEUNGDS,WANGXZ.ImprovingPerformanceofSimilarity?Based ClusteringbyFeatureWeiShtLearning【J】.IEEETransactionsOn 队MI,2002,24(4):556—561. CHANAEY,CHINGAWK.Anoptimizationalgorithmforclustering usingweighteddissimilaritymeas~【J】.PatternRecognition,2004, 37(5):943—952. 【7】FRIGUIH,NASRAOU10.Unsupervisedlearningofprototypesand attributeweights【J】.PatternRecognition,2004,37:567—581. 【8】张莉,周伟达,焦李成.核聚类算法【J】.计算机,2002,25 (6):587—590. 【9】GIROLAMIM.MemerKernel?BasedClusteringinFeatureSpace 【J】.IEEETransactionsonNeuralNe~orks,2O02,13(3):780— 784. 【10】沈红斌,杨杰,王士同.基于信息理论的合作模糊聚类算法研 究【J】.计算机,2005,8:1287—1294. 【ll】王煜,陆文聪.宋代汝窑古瓷的微量元素——支持向量机算法 研究【J】.计算机与应用化学,2OO4,2:191—194. …