机器学习中谱聚类方法的研究维普资讯.pdfVIP

维普资讯 计算机科学2007Vo1．34No．2 机器学习中谱聚类方法的研究 ) 高 琰 谷士文 唐 琏 蔡自兴 (中南大学信息科学与工程学院 长沙410075) 摘 要 最近几年，谱聚类方法在模式识另4中得到了广泛的应用。与传统的聚类方法比较，它具有能在任意形状的样 本空间上聚类，且收敛于全局最优解的优点。本文着重介绍了谱方法的基本原理、相应的算法、研究状况及其在模式 识别领域 中的应用，同时指 出了它的关键问题与未来的研究方向。 关键词 谱聚类，机器学习，图划分 ResearchonSpectralClusteringinMachineLearning GAOYah GUShiWen TANGJin CAIZi—Xing (CollegeofInformationScienceandEngineering，CentralSouthUniversity，Changsha410075) Abstract Recentlyspectralclusteringhaswideapplicationinpatternrecognition．Comparing、thtraditionalclustering methods。ithas“global”optimasolution．Thispaperintroducestheprinciple，algorithmsofspectralclustering，andthe applicationinpatternrecognition．Andalsoitpointsoutthekeyproblemsandfuturedirection． Keywords Spectralclustering，Machinelearning，Graphpartition 于样本相似度的无向加权图：G(V，E)。那么在图G中，我们 1 引言 可将聚类问题转变为如何在图G上的图划分 问题。划分的 聚类分析是机器学习的经典问题。它是通过抽取数据的 原则是：子图内的连权重最大化和各子图间的边权重最小化。 “潜在”结构，将相似数据组成类或类的层次结构。它不需要 针对这个问题，Shi和MalikEz]提出了基于将图划分为两 先验知识和假设，故它也称作是无监督学习。传统的聚类算 个子图的2-way目标函数Ncut： 法主要是k-means算法和EM算法。这些算法都是建立在凸 min (A，B)一 + (1) 球形的样本空间上。当样本空间不为凸时，算法会陷入 “局 vol(A)= ∑∑ (2) 部”最优。 iEA ～j ‘ cut(A，B)= ∑ d (3) 为了能在任意形状的样本空间上聚类，且收敛于全局最 ． iC-A，j∈B 。 优解，研究学者最近开始利用谱方法来聚类。谱方法聚类是 其中cut(A，B)是子图A，B间的边，又叫 “边切集”。 由数据点间相似