第5期 李建元，等：谱图聚类算法研究进展 ·409· 设v是矩阵B的特征向量4：的线性组合，即 可以验证，比率割下的k分割问题与平均割的 v=∑1a:4,则有a=u·y,于是有 情况类似，规范割的分割问题需要将式(9)中的 Q=ΣauBa4 拉氏矩阵L替换为归一化拉氏矩阵L,模块度的 分割问题需要将式(9)中的拉氏矩阵L替换为模块 另存在关系By=Av,故可得 度矩阵B. Q=又amya两 可见，这些最优化问题，均可运用谱方法来解 决.不同的是，比率割、最小最大割、平均割派生出非 又因为当ij时有4·4=0，而4·4：=1，故进一 归一化的谱聚类算法，而规范割派生出归一化的谱 步得到 聚类算法，模块度派生出一种新的谱分割算法，然 =2c世4=宫x, 而，它们共同的本质是约束条件下的迹最优化问 题[6]，只不过针对的矩阵不同。 若将'的取值宽松到实数域，则可得当入：取最 大特征值且ⅴ平行于其对应的特征向量时，Q取最 4谱图聚类中的几个关键问题 大值.但是网络社区分割问题仍为离散最优化问题， 4.1构图与加权 故依然需要离散化步骤.Newman的方法是使得v 令0g为点i和点j之间的边权，一种最典型的 的各分量与：的各分量符号一致，也就是使二者尽 加权方式是利用高斯衰减公式，即0= 量平行 ex即(（-I-x‖2/σ2).在给定的一个点集上建立 3.2图的k分割 相似图是谱聚类中最基本的问题，主要的方法如下， 以平均割目标函数为例，来说明图的k分割问 题的谱宽松解决方法39] 1)e图（即阈值图）：当‖：-x‖2<e时，相似 度取0，否则取w,其中e为正实数. 假定点集V可以分割为k个子集A1,A2,…,Ak, 2)k近邻图：当点i(或点)是点（或点）的k 定义指示向量h=(h,h2i,…,h)T,其中： 个邻近点之一时，相似度取0，否则取0. r1/1A:l,i∈A 3)互为k近邻图：当i点和j点互相落在对方的 0, 其他. k邻域时，相似度取0，否则设为0. 然后，令H是一个n行k列的矩阵，其列即为不同 4)b-匹配图[6s1:在度约束的前提下最小化图的 的指示向量.因为矩阵丑的各列向量是相互正交 总权值得到的一类图，可利用信任扩散方法求解其 的，即满足HH=L.于是有 权矩阵。 hZh,=2C.(4,a,) 5)拟合图]：以重构误差为优化目标，节点加 权度不小于1为约束条件，利用二次规划求得的矩 并存在 阵和图. k:Lh;=(HLH) 阈值图能够确保节点间的相邻关系几何对称， 综上可得 但阈值的选取比较困难.在一些情况下，甚至难以设 定一个恰当的阈值得到一个既连通又稀疏的图.相 对较好的选择应该是k近邻图，k容易选取也容易 2t(HLH). 1 保证得到的是一个稀疏图，但是k近邻图一般是不 故最小化平均割的问题可以等价为在约束条件 对称的，即有向图.为了使得邻近关系对称，通常的 H'H=I下求解，min,tr(HLH).若允许H中的 做法是简单地消除方向.但是这样将导致连接度的 1,2“k 不均衡性，即存在若干hub节点，从而可能对聚类问 项取任意实数，该问题可以宽松为在HH=I约束 题产生一定的负面干扰，另外，互为近邻图，虽然 下求解 能保证几何对称，可以用于捕捉那些最“重要”的 min tr(HLH), (9) 簇，但其缺点是不容易得到稀疏连通图（当参数k 即迹最小化问题.取拉氏矩阵的前k个特征向量作 较小时).b-匹配图就拓扑结构而言是规则的，在部 为列便可得到矩阵丑.然而此处H中的项在实数域 分场合下是优于：近邻图的，主要原因是其不存在 中，需要离散化才能达到分类的目的.最简单的离散 hub节点，不会造成簇间的边过分稠密的问题；其缺 化方法是在实数域解H上采用K-means算法或者 点是构建一个b-匹配图时间约为O(bn),难以扩展 其他基准算法进行子空间上的聚类， 其处理大规模的问题.拟合图是一种最新的研究成