谱聚类算法改进及在社交网络中的应用

《谱聚类算法改进及在社交网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、谱聚类算法改进及在社交网络中的应用专业名称：’计算机应用技术申请人：严俊指导教师：张师超教授论文答辩委员会主席：委员：谱聚类算法改进及在社交网络中的应用渊年级：2011级导师：张师超教授研究生：严俊专业：计算机应用技术方向：数据挖掘摘要聚类分析是将数据划分成多个簇(或类)的过程。与有监督的分类技术相比，聚类分析是无监督学习，它是在没有训练的情况下将数据对象划分为若干个簇，数据对象属于哪个簇以及分为几个簇取决于数据本身。传统的聚类算法中，高效的k-means算法和EM算法得到了广泛的应用。然而，这两种传统聚类算法只能发现凸球形的样本空间，当样本空间不为凸球形时，算法将陷

2、入局部最优解。谱聚类算法近几年受到了研究人员的广泛的关注，它是数据挖掘和机器学习领域的又一个研究热点。与传统的聚类算法相比，谱聚类算法能够在任意形状的样本空间中发现正确聚类，且最终收敛在全局最优解。谱聚类算法以谱图理论为基础，通过Laplacian矩阵将原数据空间进行重构，降低聚类分析对象的维度，这使得数据在子空间上的分布结构更为清楚。能得到优秀聚类结果的同时，谱聚类算法也存在很多问题，为了使算法应用更广泛，谱聚类算法本身还有很多需要研究人员对其进行优化的地方。本文将对这些问题做简要介绍。针对传统谱聚类算法对高斯核函数参数仃敏感的问题，受密度敏感相似性度量的启发，本文

3、设计了两种相似性度量方法，这两种相似性度量方法都没有引入高斯核函数参数，两种方法的主要区别在于第一种引入了最短路径，而第二种没有，实验证明第二种相似性度量综合性能更佳，通过实验验证了其提高了整个算法的稳定性。谱聚类算法为配对算法，算法最后一阶段是利用k．means(或其他传统聚类算法)对选择的特征向量进行聚类，而k．means算法对初始聚类中心敏感，因此本文同时还设计了一种简单却很有效的优化初始聚类中心的k-means算法，将该方法应用到本文改进的谱聚类算法，实验证明进一步使聚类结果更加稳定。最后本文结合改进的谱聚类算法提出了一种应用于社交网络聚类的算法框架。它包括一

4、种有效的抽样技术，能够选择一个最优的代表子图，既保证了训练阶段的聚类质量又减少了计算时间。此外，运用模块性选择最佳的聚类模型(即选择合适的相关参数，比如聚类个数k)，通过实验证明了该算法框架的有效性。关键词：聚类分析；谱聚类；社交网络ImprovedspectralclusteringalgorithmanditsapplicationinsocialnetworksGrade：201Tutor：ZhangShichaoProfessorName·YanJunMajor：ComputerApplicationTechnologyResearchDirection：Da

5、taMiningAbstractClusteranalysisistodividethedataintoapluralityofclusters(orclass)oftheprocess．Comparedwiththesupervisedclassification，clusteringanalysisisunsupervisedleaming，whichisthecaseintheabsenceofthetraining，dataobjectisdividedintoapluralityofclusters，thedataobjectbelongstowhichcl

6、usteranddividedintoseveralclustersdependsonthedataitself．Intraditionalclusteringalgorithms，efficientk-meansalgorithmandtheEMalgorithmhasbeenwidelyused．However,bothtraditionalclusteringalgorithmscanonlyfindaconvexsphericalsamplespace，whenthesamplespaceisnotconvexspherical，thealgorithmwil

7、lfallintolocaloptimalsolution．Inrecentyears，spectralclusteringalgorithmreceivedextensiveattentionbytheresearchers，itwasanotherhottopicindataminingandmachinelearningfields．Comparedwithtraditionalclusteringalgorithms，spectralclusteringalgorithmcanfindthecorrectclusteringinthesamp