谱聚类算法 算法简介
谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域,最近才开始用于机器学习中,并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。
算法步骤
谱聚类算法将数据集中的每个对象看作是图的顶点V,将顶点间的相似度量化作为相应顶点连接边E的权值,这样就得到一个基于相似度的无向加权图G(V, E),于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大,子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法,谱聚类算法有着不同的具体实现方法,但是这些实现方法都可以归纳为下面三个主要步骤: 1) 构建表示对象集的相似度矩阵W; 2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量,构建特征向量空间; 3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架,由于划分准则、相似度矩阵计算方法等因素的差别,具体的算法实现同样会有所差别,但其本质依然是图划分问题的连续放松形式。
划分准则
谱聚类算法将聚类问题就可以转化为图的划分问题之后,基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut,Average cut,Normalized cut,Min-max cut,Ratio cut,MNcut等。
最小割集准则
在对图像分割中产生了较好的效果,但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。
规范割集准则
在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数,此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。
比例割集准则
对于超大规模集成电路设计中的电路层次设计和分支划分问题,最大流最小割算法能够发现其中的类结构(clustering structure),但是在实际中该算法通常会产生规模非常不一致的电路分支;Kemighan-Lin算法采用固定参数的方式可以得到规模具有一定可比性的分支划分,由于电路中的分支倾向于自然结合的形成,所以通过预先设定分支规模进行划分的方法存在明显的局限。针对以上的现象Wei和Cheng提出了比例割集准则。
平均割集准则
在计算机视觉中,图像原始像素条理有序地分组可以通过寻找场景结构图(Scene Structure Graph)中松散耦合的结点来完成,于是原始像素的聚合问题就转化为场景结构图的分割。Sarkar和Soundararajan[62]提出了一种最小化两两分割之间相似度的计算方法并把它命名为平均割集准则。
最小最大割集准则
Mini cut准则容易出现分割出只包含几个顶点的较小子图的歪斜分割现象,Ratio cut和Normalized cut等在一定程度上可以避免这种现象,但是当类间重叠严重时歪斜分割现象仍
后 续篇 幅安排如下 : 2部 分介绍 了图论方法 用 于聚类 第的基本理论 ; 3部分根据 图划分准则 ,第 将谱聚类算法分为两 *) 基金项 目: 国家 836 计划...
本文首先介绍了图论方法 用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了 比较分析,最后进行总结并提出了几...
图 3.4 tNNSC 计算时间和聚类质量 图 3.4 描述论文第二章第三节所介绍的 稀疏化矩阵法近似谱聚类算法实验结果,目的也是 作为参照与所提出的 ASC 谱聚类实验...
该文旨在对谱聚类算法进行综述,总结了不同的图划分准则及其性能,介绍了经典的谱聚类算法,最后分析总结了谱聚类算法的优缺点。ISN O904SIO—34 E—ieu@CC.e. ...
后续篇幅安排如下: 第 2 部分 介绍了 图论方 法用于 聚类 的基本理论; 第 3 部分根据图划分准则, 将谱聚类算法分为两 * ) 基金项目: 国家 863 计划资助...
一种新的层次谱聚类算法_林学_农林牧渔_专业资料 暂无评价
结合LSA的中文谱聚类算法研究_计算机软件及应用_IT/计算机_专业资料。结合LSA的中文...2 谱聚类算法介绍谱聚类算法的思想来源于谱图划分理论。 假定将每个数 据样本...
和很多其他距离算法相比有很多优点,下文会详述此点,同样的,谱聚类也适合解决图切...谱聚类算法 暂无评价 21页 1下载券 谱聚类算法 算法简介 4页 1下载券 MCL聚类...
考虑空间格局的谱聚类算法及其应用_天文/地理_自然科学_专业资料。第3 4卷第 5期 201 3年 1 0月 河南科技大学学报 :自然科学版 Journal of Henan Unive 第...
使用谱聚类算法解决文本聚类集成问题_计算机硬件及网络_IT/计算机_专业资料。采用...本节介绍解决文本聚类集成问题的 2 个谱聚类 算法,2 个算法都需要把簇标签集...
热门文档