谱聚类算法综述.pdfVIP

35№．7 计算机科学2008voL 谱聚类算法综述*) 蔡晓妍戴冠中杨黎斌 (西北工业大学自动化学院 西安710072) 摘要谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。谱聚类算法建立在谱图理论基础上，与传 统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。本文首先介绍了图论方法 用于聚类的基本理论，然后根据图划分准则对谱聚类算法进行分类，着重阐述了各类中的典型算法，并对算法进行了 比较分析，最后进行总结并提出了几个有价值的研究方向。 关键词谱聚类，谱图理论，图划分 CI璐teri呜AlgoritllII幅 Survey加Spectml DAI YANGLi-bin CAI)(ia伊yallGuaI卜zhong of (CollegeAut锄ti∞，NorthwestemPolytechni∞lUniversity，Ⅺ’肌710072，C11i舱) AbstnId are in thetraditionalcluste- Spectralclusteringalgorithmsnewlydevelopingtechniquerec朗t辨脚篙UIllike tosolvethe ofnorr00nvexof that 一ngalgo—th略，the鸵applyspectralgraphth∞ry clusterirlg spheres锄plespaceS，S0 canbe to hlthis b鸹edon isfirStin． convergedglobal clustering t11eory they optiⅡ“solutiorLpaper，t}le pTinciple graph of troduced，andthen torules spectralclusteringalgorithr璐arecategorizedaccording graphpartition，andtypicaIalgo一 ^th【lsare wellastheir and are indetaiL val- studied锄phaticall)r，asadvaJltagesdisadvantagespre跎nted Finally，some uabledirectionsforfurtherresearchare proposecL K‘舯砌ndsSpectralcIuste—119，Spectralgraphtheory，Graphpartition 类，详细研究了各类中的代表性算法，并对算法进行了比较分 1 引言 析；最后对本文进行总结，提出了几个有价值的研究方向。 聚类分析是机器学习领域中的一个重要分支[1]，是人们 2基本理论 认识和探索事物之间内在联系的有效手