·406 智能系统学报 第6卷 谱聚类（如文献[3,5,18-19]等）和增量谱聚类（如 0.关于图论的基本知识，可参考最新版图论教 文献[20-21]等)：2)从是否具有约束条件或者先验 程21 知识的角度，可以将其分为无监督谱聚类和约束谱 I B C 聚类（如文献[22]等）；3)按优化目标的个数可以将 其分为单目标优化（绝大多数）和双目标优化（如文 献[23]等)；4)从运行环境上，可将其分为串行谱聚 (a)无向无权图 b)无向加权图 类和并行谱聚类（如文献[24]等）. 迄今为止，谱聚类技术已经得到长足的发展，总 A B C A「010 结和理清已有研究之间的关系，揭示未来的研究方 B001 -89 向是十分有必要的.已出现的综述文章各有侧重 cCL100 2●CCL30 Vema等人[s]主要从实验的角度比较了几种典型 c)有向无权图 d有向加权图 的谱聚类算法的性能，并提出若干改进算法.Lx 图1图及其邻接矩阵 burg等人[2w]从统计学习的理论高度比较了典型的 Fig.I Examples of graphs and adjacent matrices 归一化和非归一化谱聚类算法，并总结了相似图构 代数图论是图论、线性代数以及矩阵计算理论 建方法和簇数估计等问题.Maurizio等人[21调查了 相结合的交叉领域，其研究较早始于19世纪50年 基于核的聚类方法和谱方法，并得出这2种方法的 代.它是图论的分支之一，旨在利用代数方法来研究 共同本质是迹最优化问题.国内方面，关于该领域较 图，将图的特性转化为代数特性，然后利用代数特性 好的综述如文献[28]，其从算法层面上较为全面地 和代数方法推导关于图的定理.事实上，代数图论的 进行了比较 主要内容是图的谱，粗略地说，谱指的是矩阵的特征 本文尽管与上述综述文献在内容上有一些重叠 值连同其多重解(multiplicites).最早的关于代数图 之处，但却包含了一些新的内容.一方面，涉及的内 论的研究如：Fiedler3oj得出了图的连通性的代数判 容更全面、脉络关系更清楚，如从图论到代数分割特 据，即根据拉氏矩阵的第二小特征值是否为零可以 性的发展、从图割目标函数到谱图聚类算法的演变、 判断图是否连通，与第二小特征值对应的特征向量 谱图聚类算法的本质等.另一方面，讨论的问题更深 后来被命名为Fiedler向量，它包含了二分一个图所 入，如图的构建、边权的度量、簇数的估计、复杂性与 需要的指示信息.另外，Donath和Hoffman31] 扩充性、半监督谱学习.最后，总结了有待澄清的一 Bamest21和Donath3]等的理论工作建立了图的谱 些的理论和实际问题，指出了谱图聚类算法的研究 和图割之间的另一些关联.关于代数图论较全面的 趋势， 介绍可参考文献[34-36]. 1基本理论 1.2矩阵与谱 大多数的谱聚类算法是基于拉普拉斯矩阵（以 1.1图论与代数图论 下简称“拉氏矩阵”)的谱来进行的.拉氏矩阵分为 图论是数学的一个重要分支，是以1736年大数 非归一化的(L)和归一化的2种.归一化的又包括 学家欧拉关于Konigsberg七桥问题的论文为里程碑 对称方式（记作L。)和随机游走方式（记作L,),表 开始发展的.它研究的是关于图(aph)的理论和方 达式分别如下： 法.简单来说，图是点集和边集或弧集构成的图形 L.D-LD-1 其中边或弧用来表示一对节点间存在某种关系，边 L.=D-L. 或弧可以赋予权值，权值用来量化节点之间的关系， 文献[37-38]给出了非归一化拉氏矩阵的部分 根据是否加权，图可分为无权图和加权图；根据边是 特性，文献[36]进一步给出了归一化拉氏矩阵的部 否具有方向，可将图分为有向图和无向图. 分特性.拉氏矩阵的谱对于图的分割提供了极为有 常用的图的表示方法有邻接矩阵（记作A)和 用的信息，例如，基于Fiedler向量o可直接进行图 拉普拉斯矩阵（记作L).无权图的邻接矩阵表示法 的二分，基于多个主要特征向量可以进行图的k分 如图1(a)、(c)所示，用0表示一对顶点间无边，用 关于拉氏矩阵的特性，Luxburg391对其进行了较全 1表示一对顶点间存在一条边.加权图是用某个实 面的概括，在此不再赘述.关于到底应该采用非归一 数来反映顶点之间关系之不同，如图1(b)、(d)所 化拉氏矩阵还是归一化拉氏矩阵的问题上目前存在 示.拉普拉斯矩阵L=D-A,其中D为对角阵，对角 着较大的分歧.采用归一化拉氏矩阵的如文献[5， 线上的数值等于A的行和的绝对值，非对角元素为 23,40],非归一化拉氏矩阵的如文献[4142].从实