近邻传播半监督聚类算法分析与改进.doc

近邻传播半监督聚类算法的分析与改进
1682010,46(36)ComputerEngineeringandApplications计算机工程与应用
近邻传播半监督聚类算法的分析与改进
赵宪佳,王立宏
ZHAOXian-jia,WANGLi-hong
,tlJ东青岛266071

,QingdaoUniversity,Qingdao,Shandong266071,China ,YantaiUniversity,Yantai,Shandong264005,China
ZHAOXian~-—
supervisedclusteringalgorithmbasedonaffinity
(36):168—170.
Abstract:(SAP)is
appliedonsmalldataset,andthentheexemplarjudgmentcriterion,(k,)>0inthedecision
matrixE,,propertiesofaffinitypropag~ionalgorithmareanalyzedandtheoccurrencereason
,animprovedalgorithmisproposedtosolutethisproblem.
Keywords:affinitypropagation;exemplar;semi—supervisedlearning
摘要:近邻传播半监督聚类算法SAP在小数据集上运行时可能会出现并列类代表
点的现象,'-3出现并列类代表点时,依据决策

播算法的性质,找出了并列类代表点的出现
原因,并针对此现象给出了改进算法.
关键词:近邻传播;类代表点;半监督学习
DOI:.:1002—8331(2010)36—0168—
03文献标识码:A中图分类~J':TP301
1引言
,聚类分析 能将数据分成合适的簇,使簇内数据点之间尽可能相似,而不 ,如果能找出 每个类的合适的类代表点(exemplar), 的寻找类代表点的方法是,随机地选择初始类代表点集合,然 后迭代调整类代表点,直到类代表点不再发生明显改变时结 束,其聚类结果会受到初始类代表点选择的影响".文献[3] 提出了一种近邻传播(AffinityPropagation,AP)聚类算法,该 算法通过数据点之间的信息交换,为每个数据点找到类代表 点, 为基础,将所有的数据点都看作是潜在的类代表点,通过数据 点之间交换信息, [4-5]指出:AP算法每个簇只有一个类代表点,因此只适合表 达球形簇,忽略了簇的内部结构及层次结构;AP算法还要求 []提出了 软约束条件,在类代表点的寻找和优化过程中允许一个类代 表点不是自己的类代表点,并由此提出新的信息传递算法. 另一方面,文献[6]在文献[3]的基础上添加了半监督思想,利 用成对点约束信息对相似度矩阵进行调整,然后利用文献[3] ,近邻传播聚类算法就变成了基于近 邻传播的半监督聚类算法(
onAffinityPropagation,SAP). 文献[3] 文首先通过一个小的算例指出在小数据集上运行SAP聚类算
法代码时可能会