近邻传播的文本聚类集成谱算法_卢志茂

第33卷第7期哈尔滨工程大学学报Vol．33ɴ．72012年7月Journal of Harbin Engineering UniversityJul．2012近邻传播的文本聚类集成谱算法卢志茂1，李纯1，2，张琦1（1．哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001；2．中国人民解放军91685部队，海南陵水572400）摘要：针对现有聚类集成谱算法聚类结果不稳定的问题，引入近邻传播聚类思想，设计了基于近邻传播的聚类集成谱算法（APCESA ）．该算法先由聚类集成和谱分得到空间结构相对简单的文本低维嵌入，然后通过近邻传播算法得到最终的聚类结果．在谱分解过程中，采用矩阵变换方法，避免了谱算法中特征值分解的高昂计算代价．对真实文本数据集的实验结果表明，所提算法比对比算法聚类更稳定，且聚类结果的NMI 值和ANMI 值均高于对比算法．关键词：近邻传播；聚类集成；文本聚类；谱聚类；矩阵变换doi ：10．3969/j．issn．1006-7043．201109001网络出版地址：http ：//www．cnki．net /kcms /detail /23．1390．U．20120617．2134．015．html 中图分类号：TP391文献标志码：A文章编号：1006-7043（2012）07-0899-07A document cluster ensemble spectral algorithmbased on affinity propagationLU Zhimao 1，LI Chun 1，2，ZHANG Qi 1（1．College of Information and Communication Engineering ，Harbin Engineering University ，Harbin 150001，China ；2．The P．L．A 91685Troops ，Lingshui 572400，China ）Abstract ：The existing cluster ensemble spectral algorithm are mostly unstable．To solve this problem ，an affinitypropagation-based cluster ensemble spectral algorithm was proposed ，which brings in the idea of affinity propagationclustering．The algorithm utilized cluster ensemble and spectral analysis to achieve the low dimensional embedding of documents ，and obtained the final clustering results by using an affinity propagation clustering algorithm．To a-void the high computational cost of eigenvalue decomposition in a spectral algorithm ，matrix transformation was used in this paper．Experiments using real-world document sets show that the proposed algorithm is more stable than thecompared methods ，both NMI and ANMI values of the clustering result are higher than that of the comparison method．Keywords ：affinity propagation algorithm ；cluster ensemble ；document clustering ；spectral clustering ；matrix trans-formation收稿日期：2011-09-01．网络出版时间：2012-6-1721：34．基金项目：国家自然科学基金资助项目（60975042）．作者简介：卢志茂（1972-），男，教授，博士生导师；李纯（1984-），男，助理工程师，硕士．通信作者：李纯，E-mail ：lichun5431@163．com．随着网络的迅速发展，快速有效地获取信息成为人们的迫切需要，因此，如何提高信息获取的效率已成为研究人员广泛关注的课题．文本作为信息的重要表达形式之一，针对文本的处理研究显得尤为必要．文本聚类可以有效地识别无结构文本集中的“潜在概念”，并用这些概念和潜在关联性得到文本集的概要或簇划分等有意义的模式表达，这些模式信息对组织、搜索和管理大规模文本集具有重要意义［1］．2002年，Strehl 等［2］将集成学习引入到聚类分析中，提出了聚类集成算法．较之传统的聚类算法，聚类集成算法具有鲁棒性、新颖性、稳定性、并行及可扩展性等诸多优点［3］．作为传统聚类算法的重要扩展，聚类集成已经引起众多研究者的关注，成为机器学习领域的研究热点之一．谱聚类算法对数据集的簇形状不做强的假设，且算法不会陷入局部最优［4］，是解决非凸数据集聚类问题较有效的算法．谱聚类算法的缺点也不容忽视：1）其计算复杂度为O （n 3）；2）谱聚类要求对相似度图的参数精确设置，且在参数设置方面没有相应的理论指导；3）谱聚类虽可有效识别理想分离和接近理想分离的簇，但真实文本数据集的簇分布往往与理想状态相差甚远，多数真实的文本数据集在空间分布上类别边界不明显．文献［5］将聚类集成和谱聚类结合起来提出了2个聚类集成的谱算法，并在多组数据集上获得了较好的实验效果．然而，上述算法在对谱分解得到的文本低维嵌入的聚类的过程中使用了K-means算法，由于K-means算法对初始点的敏感性会导致最终的聚类结果的不稳定．针对该问题，本文研究如何进一步提高聚类集成谱算法的稳定性和聚类质量．考虑到造成聚类结果不稳定的原因在于K-means算法对于初始点的敏感性，所以本文引入近邻传播聚类思想，设计了一种新的聚类集成谱算法，并通过多组实验验证了本文算法的有效性．1近邻传播聚类算法近邻传播（affinity propagation，AP）［6］聚类算法与其他基于中心点聚类方法相比，该方法无需指定初始的聚类中心和类别数，且具有较好的稳定性．同时它对相似矩阵的对称性不作要求，并在处理多类数据集时运算速度更快，所以性能更好．但是，由于AP算法也是基于中心的聚类算法，它和其他的中心聚类算法一样，仅在紧凑的具有球形分布的数据集上具有较好的聚类性能，对于一些簇分布比较复杂的数据集，其空间结构可能非凸，使得AP算法只能收敛于局部最优解［7-8］．因此，AP算法并不适合任意空间形状的聚类问题和具有多重尺度的数据［9］，所以直接将AP算法用于结构复杂的文本数据是不可行的，本文的实验也证明了这一点．对于AP算法存在的不足，学者分别从半监督［7］、偏置参数控制［8］、指定类别数［9］、相似度矩阵的构造［10］等方面进行了改进．鉴于AP算法的优点和存在的问题，本文结合文献［5］的思想，从改善数据集空间结构角度入手，通过“集成+谱分解”来实现文本的降维和空间结构转化，以得到空间结构更简单的文本低维嵌入，为AP算法提供更好的输入，克服了AP算法在复杂数据集上聚类效果不理想的缺点．同时AP算法无须指定初始点，避免了传统谱聚类算法中由于K-means算法对初始点的敏感性造成聚类结果不稳定的问题．2聚类集成算法聚类集成一般分为2步，首先使用一种或多种聚类算法，对数据集进行聚类，得到多个聚类结果（聚类成员），这一步称为聚类成员的生成阶段；然后把得到的多个聚类成员作为新的输入，通过集成算法对它们进行组合，输出最终的聚类结果，这一步称为成员集成阶段．在聚类成员生成的过程中，常用的方法是使用K-means算法［11-13］，随机选择初始点运行m次，以获得m个聚类成员．该方法的优点在于其计算复杂度低，实现起来简单方便，适合于大规模数据集应用．目前聚类集成问题的主要解决方法之一是基于图划分的方法．Strehl等［2］提出了3种基于图划分的聚类集成算法，基于簇的相似度划分算法（cluster-based similarity partitioning algorithm，CSPA）、超图划分算法（hyper graph partitioning algo-rithm，HGPA）以及元聚类算法（meta-clustering algo-rithm，MCLA）算法．CSPA通过聚类成员的共联矩阵构造超图，再由图划分算法METIS［14］给出聚类结果，算法的计算复杂度虽为O（n2），但是它调用了高效的METIS算法，极大地提高了算法的效率；HGPA 算法先构造一个超图，再由超图划分算法HME-TIS［15］进行聚类，得到最终的聚类结果；MCLA算法用二元Jaccard系数来度量超边之间的相似度，随后通过METIS算法对超边进行断裂操作，以获得最终的簇划分．此外，Fern等［16］使用二部图模型建模对点和簇同时建模，提出了混合二部图模型（hybrid bipartite graph formulation，HBGF）算法．上述4种算法在聚类过程中都使用了图划分算法，图划分的算法虽然对簇的形状不做强的假设，但是为避免算法收敛到平凡解，对簇的规模做了潜在的平衡性约束，即假定每个簇内的样本点数大致相等．当数据集的平衡性不理想时，算法的聚类性能难以得到保证．3近邻传播的聚类集成谱算法文献［17］从矩阵扰动理论角度对谱聚类算法进行了解释，并给出了权矩阵（相似度矩阵S、正则化拉普拉斯矩阵L sym和L rw、非正则化拉普拉斯矩阵L以及图上的随机游动对应的转移概率矩阵P）的特征值与簇个数之间的对应关系以及特征向量与簇之间的关系．当数据集的各簇理想分离时，以相似度矩阵的前k个单位正交特征向量为列向量组成矩阵的行向量，可以看作是原待聚数据集的低维嵌入，根据各行向量之间的夹角可以用来对原数据集进行聚类．据此思想，为进一步提高算法性能及稳定性，本文在聚类集成谱算法得到的文本低维嵌入聚类阶段引入近邻传播聚类思想，设计了一种新的聚类集成·009·哈尔滨工程大学学报第33卷算法，本文称之为近邻传播的聚类集成谱算法（af-finity propagation based cluster ensemble spectral algo-rithm，APCESA）．3．1AP算法的基本原理AP算法从相似度矩阵S=［s（i，j）］nˑn出发，并引入了2个重要的信息参量矩阵，分别为代表度矩阵R=［r（i，j）］nˑn和适选度矩阵A=［a（i，j）］nˑn．算法的迭代过程就是这2个信息量竞争交替更新的过程，2个信息量代表了不同的竞争目的．r（i，j）从点x i指向点x j，它为类代表点x j搜集证据，表示x j 适合作为x i的类代表点的代表程度．a（i，j）是从点xj指向点x i，它为类代表点x i搜集证据，表示x i选择x j作为类代表点的合适程度．AP算法的核心步骤为2个信息量的交替更新过程，设当前迭代次数为t，则更新公式如下：r'（i，j）←（1－β）｛s（i，j）－maxj's，t j'≠j（a t－1（i，j'）+s（i，j'））｝+βr t－1（i，j），（1）d（i，j）←（1－β）ˑmin｛0，r t－1（j，j）+Σi's，t i' （i，j）max（0，r t（i'，j））｝+βd－1（i，j），（2）a t（j，j）←（1－β）ˑ｛Σi's，t i'≠jmax（0，r'（i'，j）｝+βa t－1（j，j）．（3）式中：β为阻尼因子，其作用是防止算法在迭代过程中发生震荡．各样本点通过反复迭代竞争，迭代结束后，具有高的r（j，j）+a（j，j）的样本为竞争得到的最终类代表点．对于任意数据点x i，计算所有数据点的代表程度r（i，j）和适选程度a（i，j）之和，其类代表点为x j：arg maxj［r（i，j）+a（i，j）］，依此将各非类代表点样本点分配给其所属的类代表点即可得到聚类结果．3．2近邻传播的聚类集成谱算法设B=｛b1，b2，…，b n｝为文本集，F=｛F（1），…，F（m）｝为对其划分得到的m个聚类标签（聚类成员）组成的集合．先把各簇标签F（i）变为超图表示H（i），则超图的nˑt的邻接矩阵H=｛H（1），…，H（r）｝，其中n为超图的顶点数，t=mk为超边数．若采用余弦相似度，则相似度矩阵S=［s（i，j）］nˑn=HH T/m．其中s（i，j）表示m个聚类成员中样本点i和样本点j 属于一个簇的次数比例，以此作为2个样本点的相似度，得到超图的相似度矩阵作为谱聚类的权矩阵，避免了传统谱聚类算法中精确参数设计．这里m为常数，对矩阵分解无意义可舍弃不予考虑，则相似度矩阵S可简化为S=HH T．更重要的是，由此方法得到的相似度矩阵S的特征值分解问题可通过小矩阵Q=H T H进行间接求解．APCESA算法的主要步骤概括如下：输入：dˑn的词－文本共现矩阵W，（d为文本集的特征词数，n为文本集的样本数），簇个数k．1）对W中的每个行向量（对应于文本集中的一个文本）根据TF-IDF（term frequency-inverse docu-ment frequency）加权，经标准化后，随机选取初始点，运行K-means算法m次，以得到m个聚类成员．由m个聚类成员构建超图的邻接矩阵H，构造相似度矩阵S=［s（i，j）］nˑn=HH T．2）计算S的前k个最大特征值λ1，…，λk对应的特征向量u1，…，u k．构造矩阵U=［u1，…，u k］，设u i∈R k为U的第i个行向量，Y=｛u i|i=1，…，n｝即为文本集B对应的低维嵌入．3）计算低维嵌入的相似度矩阵S'=［s'（i，j）］nˑn，设置初始偏执参数P，初始化代表度矩阵R=［r（i，j）］nˑn和适选度矩阵A=［a（i，j）］nˑn．4）按式（1） （3）进行迭代至收敛，得到对应的类别数k'，判断k'是否等于k，是则输出聚类结果，给出对应的簇划分C1，…，C k；不是则调节偏执参数p继续搜索．5）依行向量的簇划分将对应的文本归入到相应的簇中，得到最终的聚类结果B1，…，B k，其中Bi=｛bj|zj∈C i，b j∈B｝，1≤i≤k．输出：文本簇B1，…，Bk．本文在求相似度矩阵的特征值分解的过程中使用了近似间接求解的方式．考虑特征值分解方程：Sx=λx，把S=HH T代入方程，得到HH T x=λx．设H的秩为p=rank（H）≤t，矩阵H的SVD定义如下：H=UΣV T．（4）式中：UU T=VV T=I，Σ=diag（σ1，…，σn），σi为H 的奇异值，且有当1≤i≤p时，σi=0，当i≥p+1时，σi=0．由式（4）可得H T=VΣU T，HH T=UΣ2U T，H T H=VΣV T，因此H的左、右奇异向量分别等于HH T和H T H的p个非0特征值对应的特征向量，而奇异值等于HH T和H T H的特征值的非负平方根．为降低计算误差，SVD一般都转化为对称矩阵的特征值分解，将式（4）两边同时右乘VΣ+，其中Σ+为Σ的广义逆，也称伪逆或Moore-Penrose逆：Σ+=diag（σ－11，σ－12，…，σ－1p，0，…，0p+1→t）．（5）经过整理可得U=HVΣ+．依此变换，避免了n·109·第7期卢志茂，等：近邻传播的文本聚类集成谱算法阶方阵S的特征值分解问题．APCESA算法的巧妙之处在于：1）该算法先通过聚类集成为谱分解提供有意义的相似度矩阵，避免了谱聚类算法在处理高维数据集时由于对数据集的簇分布缺乏先验知识导致相似度图参数设置困难的问题；2）由谱分解得到的文本低维嵌入在空间结构分布上更简单，以此作为AP算法的输入，有效的克服了AP算法在空间结构复杂的数据集上聚类不理想的缺点；3）在低维嵌入聚类阶段，AP算法由于无需指定初始点，从而避免了传统谱算法中由于K-means算法对于起始点的敏感性造成的聚类结果不稳定问题，保证了算法的稳定性．4算法有效性验证实验为验证APCESA算法的有效性，本文先将APC-ESA算法与凝聚层次聚类（agglomerative hierarchical clustering：AHC）、K-means算法以及本文引入的原始AP算法进行了对比试验．为使对比实验更客观，算法效率更高，实验中相似度均采用余弦相似度．各样本点的向量表示经归一化后其模长为1，样本点xi和x j之间的余弦相似度s（i，j）定义如下式：s（i，j）=cos（θ（xi ，xj））=xi·xj‖x i‖‖x j‖=x i ·xj=xix Tj．（6）此时，2个样本点间相似度可简化为2个对应向量的点积，这样就可以有效提高聚类算法的执行效率．为进一步证明APCESA算法在聚类集成算法中的优越性，本文还将APCESA算法与文献［5］中提到的5种聚类集成算法进行了比较．由于文献［5］中提出的2种谱聚类集成算法性能大致相当，基于相似度矩阵的谱算法（similarity matrix-based spectral algorithm，SMSA）算法性能略优于基于超边相似度矩阵的谱算法（hyperedges＇similarity matrix-based spectral algorithm，HSMSA）算法，所以在本文的实验中略去与HSMSA算法的比较．4．1实验数据集及评价指标本文实验使用的6个数据集都为真实的文本数据集，各数据集的样本数、特征、真实的类别数如表1所示．其中，数据集tr31和tr41分别源于文本集TREC-6［18］和TREC-7［18］，数据集re0和re1源于Reuters-21578文本分类测试集［19］；数据集hitech和reviews是对San Jose Mercury报纸不同领域的收录，它们也是TREC［18］文本集其中的一部分（TIPSTER Vol．3）；hitech收录了关于电子、计算机、健康、医疗、科技和研究6个方面的文章；reviews包含了关于电影、美食、音乐、广播和饭店5个方面的文章．6个文本集中所有文本的类别标签唯一．每个数据集，经过停用词表去停用词，并去掉少于在2个文本中出现的稀有词，再经词频统计得到对应的词－文本共现矩阵，以此作为本文实验的输入．表1实验数据集描述Table1Description of experimental datasets数据集文档数特征词数类别数tr31927101287tr41878745410re01504288613re11657375825hitech2301131706reviews4069232205由于各文本集的类别标签已知，且文本集的类别数k作为算法的已知输入，本文采用源自信息论中的标准化互信息量（normalized mutual informa-tion，NMI）［2］来度量聚类结果和已知类别标签的匹配程度．相比于纯度和熵等指标，NMI值对k值的选取无倾向性，可以更客观地衡量聚类效果的优劣，也是近年来使用最多的评价指标之一．当聚类标签与真实的类别标签完全一致时，NMI值达到其最大值1．在APCESA算法与5种聚类集成算法的对比中，本文还使用了平均标准互信息量（average normal-ized mutual information，ANMI）［2］来度量各聚类集成算法的集成性能，ANMI值通过计算最终的聚类结果和m个聚类成员之间的平均标准互信息量得到，ANMI值越大，表明聚类集成算法搜索识别各聚类成员间一致性的能力越强，ANMI值也是近年来聚类集成算法的一个有效度量指标．4．2实验结果及分析4．2．1实验1：与主流聚类算法的对比实验APCESA算法与凝聚层次聚类、K-means算法以及AP算法的对比试验结果如表2所示（4种算法在各数据集上得到的关键值用加粗突出）．实验中K-means算法由于对初始点的选择的随机性使得聚类结果不稳定，在实验中取运行10次指标的均值作为实验的参考指标；reviews数据集在使用AHC算法的过程中，由于AHC算法空间复杂度过大发生了内存溢出错误，没能得到聚类结果，在表中用“—”表示．·209·哈尔滨工程大学学报第33卷表24种聚类算法的NMI值对比Table2Comparison of NMI scores among4algorithms 数据集AHC K-means AP APCESAtr310．5310．5890．3990．701tr410．6350．6650．5020．692re00．3270．3930．3010．413re10．4830．5740．4860．597hitech0．2530．3100．1850．332reviews—0．5200．3390．582avg0．4460．5080．3660．553从表2可以看出：1）APCESA算法在6个数据集上都得到了最高的NMI值，且在6个数据集上的平均值也比其用于产生聚类成员的K-means算法的平均指标提高了8．86%，这体现了该聚类集成算法对用于产生聚类成员的基聚类算法的改善效果，也说明将AP算法用于聚类集成谱算法中解决文本聚类集成问题是可行的．2）在AHC、K-means和AP这3种单聚类算法的对比中可以看出，各数据集上AHC和K-means算法得到的结果都要优于AP算法，这反映了AP算法在空间结构复杂的文本数据集上的聚类性能的不足，所以直接将AP算法用于文本聚类是不合理的．3）从各数据集的对比中可以发现，在数据集tr41上各聚类算法都得到了较好的聚类效果，且AHC、K-means算法以及APCESA算法得到的结果比较接近，这说明该数据集的类别边界相对明显．相反，在数据集hitech上各算法的聚类结果都不理想．究其原因，这和该数据集本身的空间结构有很大的关系，hitech收录了包含计算机、电子、健康、医疗、研究和科技6个方面的文章，其中计算机、电子、科技文章的相似性极高，而且健康和医疗2类也相互穿插，这种相似性反映到向量空间模型中则表现为空间结构的复杂性和簇边界的模糊．随着这种复杂性的增加，必然导致聚类难度的增加和聚类质量的下降，这也从侧面说明了聚类分析的困难性．这种空间结构复杂性的增加使得AP算法的性能下降明显，然而在该数据集上，APCESA算法依然取得了相对较好的聚类结果，这反映了APCESA算法的鲁棒性．4）在AP算法和APCESA算法的对比中可以看到，AP算法在6个数据集上的结果都很不理想，然而通过与聚类集成谱算法的结合APCESA算法得到的聚类结果不但稳定，而且聚类质量也明显改善，说明了AP算法和聚类集成谱算法的结合是有效的．4．2．2实验2：与几种聚类集成算法的对比实验为进一步证明APCESA算法的有效性，本文还将APCESA算法与CSPA、HGPA、MCLA、HBGF以及文献［5］中提出的SMSA这5种聚类集成算法进行了对比实验．6种聚类集成算法在6个数据集得到的NMI值和ANMI值如图1、2所示．因为在HGPA 算法中调用了HMETIS算法，而HMETIS只能得到局部最优解，所以HGPA算法获得的聚类结果不稳定，这里取运行10次评价指标的平均值；调用图划分算法METIS的CSPA和MCLA获得的聚类结果比较稳定；SMSA算法由于在低维嵌入聚类过程中使用了K-means算法，得到的聚类结果也存在一定的随机性，同样取运行10次评价指标的平均值．考虑到聚类集成算法的效率，聚类成员的数量不宜太多，实验中取5个聚类成员，即算法中m取5．此外，为使实验更客观，6种聚类集成算法在各数据集上使用相同的聚类成员，以免由于聚类成员的质量不统一对算法的性能对比造成干扰．图16种集成算法的NMI值对比Fig．1Comparison of NMI scores among6algorithms由图1和图2可以看出：1）本文提出的APCESA算法除了在reviews数据集上得到的NMI值和ANMI值与SMSA和HBGF 相当外，在其他所有数据集上都得到了高于其他对比算法的NMI和ANMI值．同时，APCESA算法在6个数据集上得到的NMI和ANMI的平均值也是最高的，证明了APCESA算法的有效性．2）在6种聚类集成算法中，APCESA、SMSA和HBGF在集成过程中都使用了谱聚类算法，上述3个聚类集成算法除了HBGF在hitech上得到的NMI 值略低于CSPA算法外，在其他数据集上都得到了·309·第7期卢志茂，等：近邻传播的文本聚类集成谱算法图26种集成算法的ANMI值对比Fig．2Comparison of ANMI scores among6algorithms 较好的NMI值和ANMI值，这说明了谱聚类算法对聚类集成算法的性能改进效果是明显的．与SMSA 和HBGF2种算法相比，APCESA算法有更好的稳定性，且在tr31、tr41、re0和re1这4个数据集上的优势明显，在reviews和hitech上也得到了不低于上述2种谱算法的NMI值和ANMI值，所以在聚类性能和稳定性上APCESA算法略优于上述2种算法．同时，在CSPA、HGPA、MCLA3种方法的对比中，CSPA 得到的聚类结果最好，而HGPA和MCLA的NMI值互有高低，这一实验结果与文献［2］中的结论吻合．3）6种算法在hitech数据集上的NMI值和AN-MI值都不太理想，究其原因，这和该数据集复杂的空间结构有很大的关系，在上文APCESA算法与3种单聚类算法的对比中也体现了这一点．在该数据集上，APCESA算法得到的NMI值和ANMI值也略高于5种对比集成算法，这说明了通过聚类集成和谱分解在数据空间结构上的转化是有效的，较好地克服了AP算法在结构复杂数据集上的不足，也说明APCESA算法比其他5种算法鲁棒性更好．4）理论上算法的ANMI值和NMI值是一致的，但实验中存在少数例外情况．例如CSPA在数据集tr31上得到的NMI值比MCLA高，但其ANMI值却较MCLA低．这从侧面说明了聚类的复杂性，一个理论上可行的聚类准则未必能得到最优解，而同一个准则函数又很难在所有数据集上都得到好的聚类结果．5）从总体上看，不同算法获得的NMI值和AN-MI值有很大的联系，即高的ANMI值一般能得到较高的NMI值，6种算法在6个文本数据集上得到的平均NMI值和平均ANMI值的也正是这种对应关系．这正说明了聚类集成的有效性，即聚类集成可以通过融合聚类成员达到提高聚类质量的目的，聚类集成算法发现聚类成员的一致性能力越强，得到的聚类效果越好．APCESA得到了最高的平均NMI值和平均ANMI值，且在其中4个数据集上都得到的NMI值和ANMI值优势明显，说明了APCESA算法在聚类性能和集成性能上优于对比算法，证明了算法的有效性．APCESA算法在文本低维嵌入聚类过程中由于无需指定初始的聚类中心，当聚类成员确定后，得到的最终聚类结果唯一，所以相对SMSA和HBGF2种聚类集成算法，APCESA更稳定．同时，由于聚类成员有多个，虽然每个聚类成员由于初始点的不同具有一定的随机性，但是聚类集成的结果正好是反映为这多个聚类成员的统计性．且APCESA 算法的稳定性仅与聚类成员的数量有关，在应用中可根据需求进行调节，不受数据集的限制．5结束语本文引入近邻传播思想，设计了一种APCESA 算法．该算法克服了聚类集成谱算法在数据集簇分布为非理想分离时由于K-means算法的使用造成聚类结果不稳定的问题，同时，在一定程度上提高了算法的聚类质量．该算法通过聚类集成和谱分解得到文本的低维嵌入，间接实现了文本数据集的降维和空间结构转化，为AP算法提供较好的输入，克服了AP算法在复杂数据集上聚类不理想的缺点．在文本低维嵌入的聚类过程中，AP算法由于无需指定初始点，有效的避免了K-means算法由于初始点敏感性造成的算法不稳定问题．在TREC和Reuters文本集上的实验，证明了该算法的有效性．APCESA算法突破了传统谱算法利用K-means算法得到最终结果的限制，是对聚类集成谱算法的一种扩展和改进；从AP算法的角度来看，利用聚类集成和谱分解来优化数据集的空间结构的思想为AP算法在复杂数据集上的扩展应用提供一种的思路．参考文献：［1］TAN P N，STEINBACH M，KUMAR V．Introduction to da-ta mining［M］．Toronto：Addison-Wesley Longman，2005：20-23．［2］STREHL A，GHOSH J．Cluster ensemblesdash—a knowl-edge reuse frame-work for combining partitionings［J］．Journal of Machine Learning Research，2002，3：583-617．［3］TOPCHY A，JAIN A K，PUNCH W．A mixture model for clustering ensembles［C］//Proceedings of the4th SIAM In-ternational Conference on Data Mining．Florida，2004：379-390．·409·哈尔滨工程大学学报第33卷［4］DING Shifei，ZHANG Liwen，YU Zhang．Research on spectral clustering algorithms and prospects［C］//20102ndInternational Conference on Computer Engineering andTechnology．Chengdu，2010：149-153．［5］徐森，卢志茂，顾国昌．解决文本聚类集成问题的两个谱算法［J］．自动化学报，2009，35（7）：997-1002．XU Sen，LU Zhimao，GU Guochang．Two spectral algo-rithms for ensembling document clusters［J］．Acta Auto-matica Sinica，2009，35（1）：997-1002．［6］FREY B J，DUECK D．Clustering by passing messages be-tween data points［J］．Science，2007，315（5814）：972-976．［7］肖宇，于剑．基于近邻传播算法的半监督聚类［J］．软件学报，2008，19（11）：2803-2813．XIAO Yu，YU Jian．Semi-supervised clustering based on affinity propagation［J］．Journal of Software，2008，19（11）：2803-2813．［8］王开军，张军英，李丹，等．自适应仿射传播聚类［J］．自动化学报，2007，33（12）：1242-1246．WANG Kaijun，ZHANG Junying，LI Dan，et al．Adaptive affinity propagation clustering［J］．Acta Automatica Sinica，2007，33（12）：1242-1246．［9］ZHANG Xiangliang，WANG Wei，Kjetil N，et al．K-AP：generation specified k cluster by efficient affinity propagation ［C］//2010IEEE International Conference on Data Min-ing．Sydney，Australia，2010，107：1187-1192．［10］董俊，王锁萍，熊范纶．可变相似性度量的近邻传播聚类［J］．电子与信息学报，2010，32（3）：509-514．DONG Jun，WANG Suoping，XIONG Fanlun．Affinitypropagation clustering based on variable-similarity measure［J］．Journal of Electronics＆Information Technology，2010，32（3）：509-514．［11］FRED A L，JAIN A K．Combining multiple clusterings u-sing evidence accumulation［J］．IEEE Transactions onPattern Analysis and Machine Intelligence，2005，27（6）：835-850．［12］AYAD H，BASIR O A，KAMEL M．A probabilistic model using information theoretic measures for cluster ensembles［C］//Proceedings of the5th International Workshop onMultiple Classifier Systems．Cagliari，Italy，2004：144-153．［13］FERN X Z，LIN W．Cluster ensemble selection［J］．Sta-tistical Analysis and Data Mining，2008，1（3）：128-141．［14］KARYPIS G，KUMAR V．A fast and high quality multi-level scheme for partitioning irregular graphs［J］．SIAMJournal on Scientific Computing，1998，20（1）：359-392．［15］KARYPIS G，AGGARWAL R，KUMAR V，et al．Multi-level hypergraph partitioning：applications in VLSI domain［J］．IEEE Transactions on Very Large Scale Integration，1999，7（1）：69-79．［16］FERN X Z，BRODLEY C E．Solving cluster ensemble problems by bipartite graph partitioning［C］//Proceed-ings of the21st International Conference on MachineLearning．New York：ACM，2004：36．［17］TIAN Z，LI X B，JU Y W．Spectral clustering based on matrix perturbation theory［J］．Science in China Series F：Information Sciences，2007，50（1）：63-81．［18］National Institute of Stangdards and Technology．Text Re-trieval Conference［EB/OL］．［2010-11-20］．http：//trec．nist．gov．［19］LEWIS D D．Reuters-21578text categorization test collec-tion distribution1．0［EB/OL］．［2010-11-20］．http：//www．research．att．com/ lewis．［责任编辑：王亚秋］·509·第7期卢志茂，等：近邻传播的文本聚类集成谱算法。