近年来，谱聚类算法在聚类分析和图划分等方面得到了成功的应用［102，132，163⁃165］。与传统的建立在凸分布基础上的聚类算法（如K⁃means，EM 等）相比，谱聚类（spectral clustering）依赖于数据相似度矩阵的特征结构，当数据分布空间不为凸时，基于谱图理论的谱聚类算法也能收敛于全局最优。下面将对谱聚类的相关概念进行简单的描述。

（1）图的基本概念

（2）构建邻接图

将数据集合x1，x2，…，xn及对应的顶点与顶点之间相似度wij或顶点与顶点之间距离dij转换到图结构的常用方法如下：

1）ε⁃近邻图

根据顶点与顶点间距离小于ε 进行构建，由此构建的图为无加权图。由于所有连接顶点与顶点之间的距离都不超过ε，对图中边的加权不会在图中引入更多关于数据的信息。

2）k⁃近邻图

如果顶点vj是顶点vi的k 近邻，则连接顶点vi和vj。但是，由于近邻关系的不对称特性，由其得到k⁃近邻图是有向图。下面将介绍两种将有向图转换为构建无向图的方法。

①通过忽略边的方向性进行构建，即如果vj是顶点vi的k 近邻或vi是顶点vj的k 近邻，用无向边连接vi和vj得到k⁃近邻图。

②通过相互k⁃近邻构建，即如果vj是顶点vi的k 近邻且vi是顶点vj的k 近邻，则连接vi和vj。(www.daowen.com)

3）全连接图

通过计算顶点与顶点之间的相似度来进行构建，用wij对边进行加权。如通过Gaussian 相似度函数wij＝exp（－｜｜xi－xj｜｜2／σ2）对相似度进行计算，得到能够表征局部近邻关系似度矩阵。其中，参数σ 的作用与ε⁃近邻中的ε 的作用类似，用于控制近邻的宽度。

（3）图的Laplacian 及其性质

谱聚类的思想源于谱图理论，是一类技术基于图拉普拉斯矩阵特征值分解的方法，利用图的Laplacian 矩阵前k 个最小特征值所对应的特征向量，在谱映射空间Rk中利用某种聚类算法（如K⁃means）将图结点聚类成k 个簇。图拉普拉斯矩阵有未规范化的图Laplacian、规范化且对称的图Laplacian 和规范化且非对称的图Laplacian 矩阵3 种形式。

1）未规范化的图Laplacian

未规范化的Laplacian 矩阵定义为L ＝D－W［166］，该矩阵不依赖于连接矩阵W 对角线上的元素。如果连接矩阵对角线之外的元素与W 相同的话，则得到相同的未规范化的图Laplacian 矩阵L。

2）规范化图Laplacian

规范化的图Laplacian 又可分为对称和非对称的Laplacian 矩阵两类。规范且对称的图Laplacian 矩阵定义为：Lsym＝D－1／2LD－1／2＝I－D－1／2WD－1／2；规范且非对称的Laplacian 矩阵定义为：Lrw＝D－1L＝I－D－1W。

实验和统计结果表明，规范化且对称的Laplacian 矩阵优于其他两种，尤其是当聚簇数据倾斜分布时（有些聚簇密集，有些聚簇稀疏）［167⁃168］对于谱聚类而言，Lsym和Lrw是等效的［169］