基于图划分的谱聚类算法在文本挖掘中应用7.pdf

《基于图划分的谱聚类算法在文本挖掘中应用7.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第19卷．第期计算机技术与发展Vo1．19No．52009年5月COMUTERTECHNOLOGYANDDFVEI．OPMENTMav2009基于图划分的谱聚类算法在文本挖掘中应用沈亚田，沈夏炯，张磊(河南大学计算机与信息工程学院，河南开封475001)摘要：传统文本挖掘算法都是建立在凸球形的样本空间上，当样本空间不为凸时，算法就陷入“局部”最优。为了满足“全局”最优，引进了无向图结构表示文档之间的相似关系，由无向图建立文档之间的相邻接矩阵，谱聚类算法是通过对邻接矩阵进行分析，导出聚类对象的新特征，利用新的特征对原数据进行聚类。通过实验对该算法和其他的

2、文本挖掘的算法进行分析比较，实验结果表明该算法聚类效果比传统数据挖掘方法好。最后指出谱聚类的不足和进一步的研究方向。关键词：谱聚类；邻接矩阵；文本挖掘；正则割；Laplancian矩阵中图分类号：TP301．6文献标识码：A文章编号：1673—629X(2009)05—0096—03ApplicationofSpectralClusterAlgorithmBasedonGraphPartitioninTextMiningSHENYa-tian，SHENXia-jiong，ZHANGLei(CollegeofComputer&Info．Eng．，Hena

3、nUniversity，Kaifeng475001，China)Abstract：Traditionaltextminingalgorithmsarebasedonthesampleofsphericalconvexspace，whensamplespaceisnotconvex，thealgo—rithmperfl0manceona“local”optimization，introducednodirectiongraphtomapsimilarrelationshipbetweendocuments，thensetupad—jacentmatrix

4、betweendocuments，spectralclusteringalgorithmanalysisadjacentmatrixt0getthenewclusterf~tures，thenusethenewfeatur~tocluser，thenitiscomparedwithotheralgorithmofthetextminingbyexperimentalmethods．Theresultsshowedthatthespec-traldusteralgorithmproducedgoodeffect．Atlast。descriptsshort

5、ageandfurtherresearchdirectionsofspectralclusteralgorithm．Keywords：spectralcluster；adjacentmatrix；textmining；normalizedcutS：LaplancianmatrixO引言了解决这种问题，能够在任意的样本空间上聚类，且聚文本挖掘是近几年来数据挖掘领域中一个新兴的类的结果收敛于全局最优解。最近，研究学者们开始分支，它是多种学科，比如计算语言学、统计学、计算机利用基于图划分的谱聚类方法。谱聚类是一种基于谱图分解的算法，是图论和矩阵的谱分解理论在

6、聚类方科学、信息学等的融合。文本挖掘与传统数据挖掘不面的结合。该算法有良好的理论基础和简结的数学模同。传统数据挖掘的对象集中于有结构的数据，如关型，近年来得到广泛的关注。系型和事务型等，其特征的维数有限；而文本数据是无结构的，特征维也不是固定的，因此文本挖掘的技术既1算法和原理有传统数据挖掘方法的共性，又有自己的特性。1．1图的划分和聚类聚类分析是传统的数据挖掘的方法，其目的是根所谓的聚类，是将对象划分成若干个组，使得组内据样本的相似性对数据集进行合理的分割。它不需要的对象之间很相似，而组间的对象不相似。在谱聚类先验知识和假设，是一种无监督的学习。传统

7、的聚类中，人们用图来对集合中的对象以及他们之间的相互方法很多，如k—means算法、最大似然估计、无监督贝关系进行建模：用图中的顶点来代表集合中的对象，用叶斯学习等。这些算法都是建立在凸球形的样本空间图中的边来表示对象间关系，而关系的强弱则用边的上，当样本空间不为凸时，算法就陷人“局部”最优。为权重来表示。由此，图G：(V，E)的顶点集V={1，2，⋯，}表示对象，边集E：{<，>l，∈V}收稿日期：2008—08—15表示关系，而边<，>的权重E表示关系的强弱。基金项目：河南省自然科学基金项目(0311011700)在此基础上可以定义关系图的邻接矩阵

8、M：作者简介：tt亚田(1982一)，男，硕士研究生，研究方向为文本挖掘fE若()∈E和信息检