下载文档原格式
谱聚类算法的改进及其在滑坡领域的应用谱聚类算法的改进及其在滑坡领域的应用引言：在滑坡领域，对地质灾害的预测和防范一直是一个重要课题。
谱聚类算法是一种常用的聚类算法，可以用于挖掘数据集中的潜在成分，通过对数据进行聚类分析，可以发现潜在的滑坡特征。
然而，传统的谱聚类算法在处理大规模数据时存在效率低下和异常点敏感的问题。
本文将介绍谱聚类算法的改进方法，并基于改进后的算法，探讨其在滑坡领域的应用。
一、谱聚类算法的基本原理谱聚类算法是一种基于图论的聚类方法，其基本原理如下：1. 构建相似度矩阵：对给定的数据集，计算每个数据点之间的相似度。
常用的相似度计算方法有欧氏距离、余弦相似度等。
2. 构建拉普拉斯矩阵：根据相似度矩阵，构建拉普拉斯矩阵，用于描述数据集的拓扑结构。
3. 特征值分解：对拉普拉斯矩阵进行特征值分解，得到特征向量和特征值。
4. K-means聚类：根据前面得到的特征向量，将数据集进行K-means聚类。
二、谱聚类算法的改进方法针对传统的谱聚类算法存在的问题，研究者们提出了多种改进方法，以提高算法的效率和鲁棒性。
以下是几种常见的改进方法：1. 快速谱聚类算法：传统的谱聚类算法在进行特征值分解时，需要计算整个数据集的拉普拉斯矩阵的特征向量和特征值，计算复杂度较高。
快速谱聚类算法通过采用代表性样本点或者使用K近邻图的方法，降低了算法的计算复杂度。
2. 线性代数方法：传统的谱聚类算法需要对拉普拉斯矩阵进行特征值分解，计算复杂度很高。
线性代数方法通过使用线性代数技巧，如矩阵的特征值分解、矩阵的特征值投影等，简化了算法的计算过程。
3. 分布式谱聚类算法：传统的谱聚类算法对于大规模数据集的处理效率较低。
分布式谱聚类算法将数据集划分为若干个子集，分布式地进行谱聚类计算，提高了算法的处理效率。
三、谱聚类算法在滑坡领域的应用滑坡的发生往往与地质结构、降雨量、地表形态等因素密切相关。
谱聚类算法可以通过对滑坡相关数据的聚类分析，挖掘出滑坡的潜在特征，有助于滑坡的预测和防范。
谱聚类算法转载⾃：1、问题描述 谱聚类(Spectral Clustering, SC)是⼀种基于图论的聚类⽅法——将带权⽆向图划分为两个或两个以上的最优⼦图(sub-Graph)，使⼦图内部尽量相似，⽽⼦图间距离尽量距离较远，以达到常见的聚类的⽬的。
对于图的相关定义如下：对于⽆向图G = (V,E)，V表⽰顶点集合，即样本集合，即⼀个顶点为⼀个样本；E表⽰边集合。
设样本数为n，即顶点数为n。
权重矩阵：W，为n*n的矩阵，其值w i,j为各边的权值，表⽰顶点 i，j（样本）之间的相似性。
对于任意w i,j = w j,i ，w i,i=0，即对⾓线上元素为0。
通常情况下，相似性⼩于某⼀阈值的两个顶点不相连，否则连接两顶点的边的权值为两个样本的相似性度量函数的值。
定义n*n的矩阵：D，其第 i ⾏，第 i 列的元素（对⾓线上）元素为W第 i ⾏所有元素的和，即 i 顶点与其他所有顶点的相似性之和。
将图G分割为⼦图G1,G2，所要断开的边的权重之和为损失函数：如下图给出⼀个六个样本所对应的图：此例中对应的损失函数为 w1,5 + w3,4 = 0.3。
谱聚类的⽬的就是找到⼀个较好的划分准则，将整个样本空间形成的图分成为各个⼦图(sub-Graph)，⼀个⼦图即为⼀个类别。
根据分割⼦图的准则，可以将其分为不同的谱聚类（Minimum Cut、Ratio Cut and Normalized Cut等）。
讲具体算法之前，回顾⼀些线性代数有关的结论，不清楚的可以查阅相关资料：Ax = λx ，则λ为A的特征值，x为对应λ的特征向量。
对于实对称矩阵A，其特征向量正交。
即当i ≠ j时， <x i T,x j> = 0（<,>表⽰内积）。
对于正定矩阵，其所有特征值都⼤于0；对于半正定矩阵，其所有特征值都⼤于等于02、问题转化 ⾸先看看这个损失函数，对其进⾏如下变换：1、定义q i如下：当顶点 i 属于⼦图G1中时，q i = c1。
谱聚类算法综述一、本文概述谱聚类算法是一种基于图理论的机器学习技术，它在数据分析和模式识别中发挥着重要作用。
本文旨在对谱聚类算法进行全面的综述，从理论基础、算法流程、应用领域以及最新进展等多个方面进行深入的探讨。
我们将简要介绍谱聚类算法的基本概念和原理，包括图论基础、拉普拉斯矩阵、特征值分解等关键知识点。
然后，我们将详细阐述谱聚类算法的基本流程和主要步骤，包括数据预处理、构建相似度矩阵、计算拉普拉斯矩阵、求解特征向量和聚类等。
接下来，我们将重点分析谱聚类算法在不同领域中的应用，如图像处理、社交网络分析、机器学习等，并探讨其在这些领域中取得的成果和优势。
我们还将对谱聚类算法的性能进行评估，包括其时间复杂度、空间复杂度以及聚类效果等方面。
我们将对谱聚类算法的最新研究进展进行综述，包括新的算法模型、优化方法以及应用领域的拓展等方面。
通过对这些最新进展的梳理和总结，我们可以更好地了解谱聚类算法的发展趋势和未来研究方向。
本文旨在对谱聚类算法进行全面的综述和分析，为读者提供一个清晰、系统的认识框架，同时也为该领域的研究者提供有价值的参考和启示。
二、谱聚类算法的基本原理谱聚类算法是一种基于图理论的聚类方法，它通过将数据点视为图中的节点，数据点之间的相似性视为节点之间的边的权重，从而构建出一个加权无向图。
谱聚类的基本原理在于利用图的拉普拉斯矩阵（Laplacian Matrix）的特征向量来进行聚类。
构建相似度矩阵：需要计算数据点之间的相似度，这通常通过核函数（如高斯核函数）来实现，从而构建出一个相似度矩阵。
构建图的拉普拉斯矩阵：根据相似度矩阵，可以构建出图的度矩阵和邻接矩阵，进而得到图的拉普拉斯矩阵。
拉普拉斯矩阵是相似度矩阵和度矩阵之差，它反映了数据点之间的局部结构信息。
求解拉普拉斯矩阵的特征向量：对拉普拉斯矩阵进行特征分解，得到其特征向量。
这些特征向量构成了一个新的低维空间，在这个空间中，相似的数据点更接近，不相似的数据点更远。
谱聚类拉普拉斯算法
谱聚类是一种常用的聚类算法，通过将数据集转化为图形模型，利用图的谱分析方法来进行聚类。
其中，拉普拉斯算法是谱聚类的一种基本算法，其主要思想是将数据集转化为图形模型后，通过计算拉普拉斯矩阵来得到聚类结果。
具体来说，拉普拉斯算法分为两种类型：标准拉普拉斯算法和对称拉普拉斯算法。
标准拉普拉斯算法通过计算拉普拉斯矩阵的特征向量来进行聚类，而对称拉普拉斯算法则通过计算对称拉普拉斯矩阵的特征向量来进行聚类。
两种算法的主要区别在于拉普拉斯矩阵的构造方式不同。
在实现拉普拉斯算法时，需要先构造数据集的邻接矩阵和度矩阵，然后根据不同的算法类型计算拉普拉斯矩阵，并求解其特征向量。
最后，通过对特征向量进行聚类，即可得到最终的聚类结果。
总之，拉普拉斯算法是谱聚类中比较基础的算法之一，通过对数据集进行图形模型转化，可以有效地进行聚类。
在实际应用中，需要根据数据集的特点选择不同的算法类型，并根据具体情况进行参数调整，才能得到更加准确的聚类结果。
- 1 -。
＊)基金项目:国家863计划资助项目(2005AA147030)。
蔡晓妍 博士生,主要研究方向为智能信息处理、网络与信息安全;戴冠中 教授,博士生导师,主要研究领域为自动控制、信息安全;杨黎斌 博士生,研究方向为网络与信息安全、嵌入式系统。
计算机科学2008V ol .35№.7 谱聚类算法综述＊)蔡晓妍 戴冠中 杨黎斌(西北工业大学自动化学院 西安710072)摘 要 谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。
谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
本文首先介绍了图论方法用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向。
关键词 谱聚类,谱图理论,图划分 Survey on Spectral C lustering AlgorithmsCA I Xiao -yan DA I Guan -zho ng YA N G Li -bin(C ollege of Autom ation ,Northw estern Polytechnical University ,Xi 'an 710072,China )A bstract Spectral clustering alg orithms a re new ly dev elo ping technique in recent year s .Unlike the traditional cluste -ring alg orithms ,these apply spect ral g raph theo ry to solve the clustering of no n -co nv ex sphere of sample spaces ,so that they can be conver ged to g lo bal o ptimal solution .In this paper ,the clustering principle based o n g raph theory is first in -troduced ,and then spectra l clustering alg orithms are catego rized acco rding to rules of g raph pa rtition ,and typical alg o -rithms are studied emphatically ,as well as their advantage s and disadvantage s are presented in de tail .F inally ,some v al -uable directions fo r fur ther research are pro po sed .Keywords Spec tral clustering ,Spectral g raph theo ry ,G raph par titio n 1 引言聚类分析是机器学习领域中的一个重要分支[1],是人们认识和探索事物之间内在联系的有效手段。
1. 谱聚类给你博客园上若干个博客，让你将它们分成K类，你会怎样做？想必有很多方法，本文要介绍的是其中的一种——谱聚类。
聚类的直观解释是根据样本间相似度，将它们分成不同组。
谱聚类的思想是将样本看作顶点，样本间的相似度看作带权的边，从而将聚类问题转为图分割问题：找到一种图分割的方法使得连接不同组的边的权重尽可能低（这意味着组间相似度要尽可能低），组内的边的权重尽可能高（这意味着组内相似度要尽可能高）。
将上面的例子代入就是将每一个博客当作图上的一个顶点，然后根据相似度将这些顶点连起来，最后进行分割。
分割后还连在一起的顶点就是同一类了。
更具体的例子如下图所示：在上图中，一共有6个顶点（博客），顶点之间的连线表示两个顶点的相似度，现在要将这图分成两半（两个类），要怎样分割（去掉哪边条）？根据谱聚类的思想，应该去掉的边是用虚线表示的那条。
最后，剩下的两半就分别对应两个类了。
根据这个思想，可以得到unnormalized谱聚类和normalized谱聚类，由于前者比后者简单，所以本文介绍unnormalized谱聚类的几个步骤（假设要分K个类）：(a)建立similarity graph，并用W 表示similarity graph的带权邻接矩阵(b)计算unnormalized graph Laplacian matrix L(L = D - W, 其中D是degree matrix)(c)计算L的前K个最小的特征向量(d)把这k个特征向量排列在一起组成一个N*k的矩阵，将其中每一行看作k维空间中的一个向量，并使用K-means 算法进行聚类2. 算法原理解析这一节主要从大体上解释unnormalized谱聚类的四个步骤是怎么来的，不涉及具体的公式推导。
(a)谱聚类的思想就是要转化为图分割问题。
因此，第一步就是将原问题转化为图。
转为图有两个问题要解决：一是两个顶点的边要怎样定义；二是要保留哪些边。
对于第一个问题，如果两个点在一定程度上相似，就在两个点之间添加一条边。
一种尺度参数与初始中心自适应的谱聚类算法随着数据挖掘和机器学习技术的发展，对于信息检索和分类应用已经越来越广泛，谱聚类算法受到了越来越多的关注。
它是一种提取数据内部结构、划分数据的聚类算法，基于数据的降维来提取数据的高维相似性并将其归类为若干簇。
目前，研究者为了改进谱聚类算法，有许多方法，如尺度参数与初始中心自适应的谱聚类算法。
谱聚类算法是基于图划分理论发展起来的，其前提是将数据集抽象成一个图，然后进行划分。
算法的核心是基于拉普拉斯矩阵（Laplacian matrix），它是一种描述图的矩阵，可以表示节点之间的关系以及节点的重要性。
谱聚类算法的目的是寻找拉普拉斯矩阵的最小特征值和对应的最小特征向量，并以这些特征向量为聚类的基础来实现聚类。
尺度参数与初始中心自适应的谱聚类算法（Spectral clustering with adaptive scale parameter and initial center）是一种改进的谱聚类算法，它引入了尺度参数，可以有效地提高算法的聚类效果。
此外，它还可以自动选择聚类中心，可以提供更高的准确度和稳定性。
因此，该算法受到了越来越多的关注。
该算法的工作流程主要分为三个步骤：第一步是构造拉普拉斯矩阵。
首先，根据相似度计算数据之间的关系，从而建立拉普拉斯矩阵。
拉普拉斯矩阵是一种描述图的矩阵，它可以表示节点之间的关系以及节点的重要性。
第二步是计算拉普拉斯矩阵的最小特征值和对应的最小特征向量，并用这些特征向量作为聚类的基础。
在这一步，尺度参数与初始中心自适应的谱聚类算法可以有效地改进谱聚类算法，并且可以自动选择聚类中心。
最后一步是执行传统的K聚类算法，根据算法得到的特征向量进行分类。
K-means算法可以用来从这些特征向量中计算K个聚类的中心，然后将数据分配到最近的中心点，从而实现聚类。
总之，尺度参数与初始中心自适应的谱聚类算法是一种改进的谱聚类算法，它可以有效提高算法的聚类效果，并且可以提供更高的准确度和稳定性。
基于谱聚类算法的图像分割研究随着数字图片的大量产生，图像分割已成为计算机视觉领域中的重要问题。
其目的就是把一张图片划分为多个有意义的部分，以便于进一步的处理和分析。
图像分割可以应用于自然语言处理、图像识别、医学图像处理等领域。
目前，基于谱聚类算法的图像分割研究，正在得到越来越多领域的重视。
一、谱聚类算法简介谱聚类是一种基于图论的图像分割算法，它能够把图像划分为多个子集，每个子集中的像素具有相似的特征。
谱聚类算法的原理比较简单，主要分为以下几步：1. 构建相似度矩阵：首先，我们需要构建一张图像的相似度矩阵，该矩阵用于描述每个像素与其他像素之间的相似度。
一旦得到这个矩阵，我们就可以把原始图像看做一个由像素节点组成的图。
2. 生成拉普拉斯矩阵：接下来，我们需要生成图像的拉普拉斯矩阵。
拉普拉斯矩阵是描述图像内部像素之间关系的矩阵，它的值为每个像素点与其相邻像素点距离的差值之和。
这个矩阵的特点是对称正定，可以通过特征分解得到特征向量。
3. 特征向量分解：将拉普拉斯矩阵通过特征分解得到一组特征向量，特征向量被用于表示原始图像的子集。
根据图像的特征向量将其分为不同的子集。
谱聚类算法具有较强的可扩展性，处理大量像素时，其算法的时间复杂度并不高，可以快速地进行图像分割处理。
二、谱聚类算法的优点与传统的图像分割算法相比，谱聚类算法具有以下优点：1. 支持高维数据：谱聚类可以在高维空间中进行图像分割，并且在这种情况下表现优异。
2. 扩展性强：谱聚类对于一般的图像分割问题有很强的可扩展性，可以适应不同规模和形状的图像。
3. 相对简单：谱聚类算法易于实现，不需要大量的参数调整和前期的训练阶段。
4. 鲁棒性强：谱聚类算法的结果对噪声点不敏感，并且对于某些形状的图像分割处理效果尤其好。
三、基于谱聚类的图像分割实验为了验证谱聚类算法的效果，我们设计了一组实验：1. 实验数据我们选取了一张经典的Lena图像作为实验数据，该图像大小为256*256。
Sklearn（Scikit-learn）是一个基于Python的机器学习库，提供了许多常用的机器学习算法和工具。
谱聚类（Spectral Clustering）算法作为Sklearn库中的一个重要组成部分，是一种基于图论和谱理论的聚类算法，能够有效地处理非凸形状的数据集并对高维数据进行聚类分析。
本文将对Sklearn中的谱聚类算法进行深入探讨，并对其理论、实现细节和应用展开详细介绍。
一、谱聚类算法的理论基础谱聚类算法是一种基于图论和谱理论的聚类算法，其主要思想是将数据集表示为图的形式，利用图的谱分解来实现聚类分析。
在进行谱聚类之前，首先需要构建数据样本的相似度矩阵或者距离矩阵，并基于这个矩阵构建相应的图模型，常用的图模型包括ε-邻近图、全连接图等。
接下来，利用图的拉普拉斯矩阵进行特征分解，得到其特征向量，并通过对特征向量进行聚类操作，最终得到数据的聚类结构。
谱聚类算法的理论基础主要包括图论、谱图理论以及聚类理论等多个方面的知识，需要深入理解这些理论知识才能正确地运用谱聚类算法进行数据分析。
在Sklearn库中，谱聚类算法提供了丰富的参数设置和优化方法，能够灵活地适应不同数据情况和需求，是实现谱聚类算法的一个重要工具。
二、谱聚类算法的实现细节Sklearn中的谱聚类算法主要基于Python语言实现，其具体的实现细节涵盖了图模型构建、谱分解、特征向量聚类等多个方面。
在进行实际的数据分析时，需要关注谱聚类算法的几个关键参数，包括图模型的构建方法、相似度矩阵的计算方式、谱分解的方法、特征向量聚类的算法等。
图模型的构建方法是谱聚类算法中的一个关键步骤，常用的方法包括ε-邻近图、全连接图等，不同的方法会对聚类结果产生不同的影响，需要根据具体的数据情况选取合适的方法。
另外，相似度矩阵的计算方式也会影响到谱聚类的结果，可以选择基于距离的相似度计算方法或者基于核函数的相似度计算方法。
谱分解的方法通常包括最大化拉普拉斯特征值、最小化拉普拉斯特征值等多种方法，需要根据具体应用需求选择合适的方法。
谱聚类算法算法简介 谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。
谱聚类算法最初用于计算机视觉、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等。
最小割集准则 在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。
谱聚类算法(Spectral Clustering)谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。
其中的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)，也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。
图1 谱聚类无向图划分——Smallest cut和Best cut 这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。
1 理论基础对于如下空间向量item-user matrix：如果要将item做聚类，常常想到k-means聚类方法，复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数：1 如果M足够大呢？2 K的选取？3 类的假设是凸球形的？4 如果item是不同的实体呢？5 Kmeans无可避免的局部最优收敛？……这些都使常见的聚类问题变得相当复杂。
1.1 图的表示如果我们计算出item与item之间的相似度，便可以得到一个只有item的相似矩阵，进一步，将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)，这样便得到我们常见的图的概念。
对于图的表示(如图2)，常用的有：邻接矩阵：E，e ij表示v i和v i的边的权值，E为对称矩阵，对角线上元素为0，如图2-2。
Laplacian矩阵：L = D – E，其中d i (行或列元素的和)，如图2-3。
图2 图的表示1.2 特征值与L矩阵先考虑一种最优化图像分割方法，以二分为例，将图cut为S和T两部分，等价于如下损失函数cut(S, T)，如公式1所示，即最小(砍掉的边的加权和)。
谱聚类算法算法简介谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。
谱聚类算法最初用于计算机视觉、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等。
最小割集准则在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。
谱聚类（spectralclustering）原理总结 谱聚类（spectral clustering）是⼴泛使⽤的聚类算法，⽐起传统的K-Means算法，谱聚类对数据分布的适应性更强，聚类效果也很优秀，同时聚类的计算量也⼩很多，更加难能可贵的是实现起来也不复杂。
在处理实际的聚类问题时，个⼈认为谱聚类是应该⾸先考虑的⼏种算法之⼀。
下⾯我们就对谱聚类的算法原理做⼀个总结。
1. 谱聚类概述 谱聚类是从图论中演化出来的算法，后来在聚类中得到了⼴泛的应⽤。
它的主要思想是把所有的数据看做空间中的点，这些点之间可以⽤边连接起来。
距离较远的两个点之间的边权重值较低，⽽距离较近的两个点之间的边权重值较⾼，通过对所有数据点组成的图进⾏切图，让切图后不同的⼦图间边权重和尽可能的低，⽽⼦图内的边权重和尽可能的⾼，从⽽达到聚类的⽬的。
乍⼀看，这个算法原理的确简单，但是要完全理解这个算法的话，需要对图论中的⽆向图，线性代数和矩阵分析都有⼀定的了解。
下⾯我们就从这些需要的基础知识开始，⼀步步学习谱聚类。
2. 谱聚类基础之⼀：⽆向权重图 由于谱聚类是基于图论的，因此我们⾸先温习下图的概念。
对于⼀个图G，我们⼀般⽤点的集合V和边的集合E来描述。
即为G(V,E)。
其中V即为我们数据集⾥⾯所有的点(v_1, v_2,...v_n)。
对于V中的任意两个点，可以有边连接，也可以没有边连接。
我们定义权重w_{ij}为点v_i和点v_j之间的权重。
由于我们是⽆向图，所以w_{ij} = w_{ji}。
对于有边连接的两个点v_i和v_j，w_{ij} > 0,对于没有边连接的两个点v_i和v_j，w_{ij} = 0。
对于图中的任意⼀个点v_i，它的度d_i定义为和它相连的所有边的权重之和，即d_i = \sum\limits_{j=1}^{n}w_{ij} 利⽤每个点度的定义，我们可以得到⼀个nxn的度矩阵D,它是⼀个对⾓矩阵，只有主对⾓线有值，对应第i⾏的第i个点的度数，定义如下：\mathbf{D} = \left( \begin{array}{ccc} d_1 & \ldots & \ldots \\ \ldots & d_2 & \ldots \\ \vdots & \vdots & \ddots \\ \ldots & \ldots & d_n\end{array} \right) 利⽤所有点之间的权重值，我们可以得到图的邻接矩阵W，它也是⼀个nxn的矩阵，第i⾏的第j个值对应我们的权重w_{ij}。
＊)基金项目:国家863计划资助项目(2005AA147030)。
蔡晓妍 博士生,主要研究方向为智能信息处理、网络与信息安全;戴冠中 教授,博士生导师,主要研究领域为自动控制、信息安全;杨黎斌 博士生,研究方向为网络与信息安全、嵌入式系统。
计算机科学2008V ol .35№.7 谱聚类算法综述＊)蔡晓妍 戴冠中 杨黎斌(西北工业大学自动化学院 西安710072)摘 要 谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。
谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
本文首先介绍了图论方法用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向。
关键词 谱聚类,谱图理论,图划分 Survey on Spectral C lustering AlgorithmsCA I Xiao -yan DA I Guan -zho ng YA N G Li -bin(C ollege of Autom ation ,Northw estern Polytechnical University ,Xi 'an 710072,China )A bstract Spectral clustering alg orithms a re new ly dev elo ping technique in recent year s .Unlike the traditional cluste -ring alg orithms ,these apply spect ral g raph theo ry to solve the clustering of no n -co nv ex sphere of sample spaces ,so that they can be conver ged to g lo bal o ptimal solution .In this paper ,the clustering principle based o n g raph theory is first in -troduced ,and then spectra l clustering alg orithms are catego rized acco rding to rules of g raph pa rtition ,and typical alg o -rithms are studied emphatically ,as well as their advantage s and disadvantage s are presented in de tail .F inally ,some v al -uable directions fo r fur ther research are pro po sed .Keywords Spec tral clustering ,Spectral g raph theo ry ,G raph par titio n 1 引言聚类分析是机器学习领域中的一个重要分支[1],是人们认识和探索事物之间内在联系的有效手段。
所谓聚类(clus -te ring )就是将数据对象分组成为多个类或簇(cluste r ),使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。
传统的聚类算法,如k -means 算法、EM 算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。
为了能在任意形状的样本空间上聚类,且收敛于全局最优解,学者们开始研究一类新型的聚类算法,称为谱聚类算法(Spec tral Clustering A lg o rithm )。
该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。
谱聚类算法最初用于计算机视觉[3]、V LSI 设计[4]等领域,最近才开始用于机器学习中[5],并迅速成为国际上机器学习领域的研究热点。
谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。
但由于其涉及的理论知识较多,应用也还处于初级阶段,因此国内这方面的研究报道非常少。
本文作为一篇综述性文章,旨在向读者介绍这种新型的聚类算法,使研究人员尽可能详细地总结该领域的研究现状。
后续篇幅安排如下:第2部分介绍了图论方法用于聚类的基本理论;第3部分根据图划分准则,将谱聚类算法分为两类,详细研究了各类中的代表性算法,并对算法进行了比较分析;最后对本文进行总结,提出了几个有价值的研究方向。
2 基本理论2.1 图划分准则谱聚类算法的思想来源于谱图划分理论[2]。
假定将每个数据样本看作图中的顶点V ,根据样本间的相似度将顶点间的边E 赋权重值W ,这样就得到一个基于样本相似度的无向加权图G =(V ,E )。
那么在图G 中,就可将聚类问题转化为在图G 上的图划分问题。
基于图论的最优划分准则就是使划分成的两个子图内部相似度最大,子图之间的相似度最小[5]。
划分准则的好坏直接影响到聚类结果的优劣。
常见的划分准则有M inimum cut ,A verag e cut ,No rmalized cut ,M in -max cut ,Ratio cut ,M N cut 等。
下面我们将分别介绍这几种准则。
2.1.1 最小割集准则[6](M inimum cut )谱图理论中,将图G 划分为A ,B 两个子图(其中A ∪B =V ,A ∩B = )的代价函数为:cut (A ,B )=∑u ∈A ,v ∈Bw (u ,v )(1)W u 和Leahy 提出最小化上述剪切值来划分图G ,这一划分准则被称为最小割集准则。
他们用这个准则对一些图像进行分割,并产生了较好的效果,同时他们也注意到,该准则容易出现歪斜(即偏向小区域)分割。
Shi 和M a lik 提出的规范割集准则及Hag en 和K ahng 提出的比例割集准则均可避免这种情况的发生。
2.1.2 规范割集准则[5](No rmalized cut )Shi 和M alik 在2000年根据谱图理论建立了2-way 划分的规范割目标函数(N cut ):N cut (A ,B )=cut (A ,B )assoc (A ,V )+cut (A ,B )assoc (B ,V )其中assoc (A ,V )=∑u ∈A ,t ∈Vw (u ,t )(2)最小化N cut 函数被称为规范割集准则。
该准则不仅能够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。
Shi 和M alik 同时还提出了规范关联目标函数(N asso c ):N assoc (A ,B )=assoc (A ,A )assoc (A ,V )+assoc (B ,B )assoc (B ,V )(3)assoc (A ,A )与assoc (B ,B )分别是子图A ,B 内所有顶点之间的连接权值之和。
这一无偏函数进一步反映了类内样本间互相连接的紧密程度。
同时,可以看出N cut 函数与N as -soc 函数是相关的,它们满足关系:N cut (A ,B )=2-N assoc (A ,B )。
因此,最小化N cut 函数等价于最大化Nassoc 函数,但通常情况下都是通过最小化N cut 函数获取图的最优划分。
2.1.3 比例割集准则[7](Ratio cut )Hag en 和K ahng 提出了比例割目标函数(Rcut ):Rcut =cut (A ,B )min ( A , B )(4)其中 A , B 分别表示子图A ,B 中顶点的个数。
最小化Rcut 函数只考虑了类间相似性最小,减小了过分割的可能性,但运行速度较慢。
2.1.4 平均割集准则[8](Av erag e cut )平均割目标函数为:Av cut (A ,B )=cut (A ,B ) A +cut (A ,B )B(5)可以看出A vcut 和N cut 函数都表示无向图G 中边界损失与分割区域相关性的比值之和,因此最小化A vcut 与N cut 目标函数都能产生较准确的划分。
其共同缺点是倾向于欠分割且易分割出只包含几个顶点的较小子图。
文献[5]通过实验发现,当把No rmalized cut 和A verag e cut 准则分别用于同一图像的分割问题时,No rmalized cut 准则能够产生更好的划分结果。
2.1.5 最小最大割集准则[9](M in -max cut )最小最大割集准则要求最小化cut (A ,B )的同时,最大化assoc (A ,A )与assoc (B ,B )。
该准则可通过最小化下面的目标函数得以实现:Mcut =cut (A ,B )assoc (A ,A )+cut (A ,B )assoc (B ,B )(6)我们将这个目标函数称为最小最大割函数,或简称为M cut 函数。
最小化该函数可避免分割出仅包含几个顶点的较小子图,因此它倾向于产生平衡割集,但实现速度较慢。
M cut 与N cut 一样满足类间样本间的相似度小而类内样本间的相似度大的原则,与N cut 具有相似的行为,但当类间重叠较大时,M cut 比N cut 更加高效。
2.1.6 多路规范割集准则[10](M ultiw ay N o rmalized cut )上述五种划分准则所使用的目标函数都是将图G 划分为2个子图的2-w ay 划分函数,M eila 提出一种可以将图G 同时划分为k 个子图的k -w ay 规范割目标函数:MN cut =cut (A 1,V -A 1)assoc (A 1,V )+cut (A 2,V -A 2)assoc (A 2,V )+…+cut (A k ,V -A k )assoc (A k ,V )(7)M elia 指出Ncut 和M Ncut 的差异之处仅在于所使用的谱映射不同,并且当k =2时,M N cut 与N cut 等价。
多路规范割集准则在实际应用中合理有效,但其优化问题通常难以解决。
2.2 相似矩阵、度矩阵及Laplacian 矩阵由于图划分问题的本质,求图划分准则的最优解是一个N P 难问题。
一个很好的求解方法是考虑问题的连续放松形式,这样便可将原问题转换成求解相似矩阵或Laplacian 矩阵的谱分解,因此将这类方法统称为谱聚类,可以认为谱聚类是对图划分准则的逼近[11]。
