动机
数据群可以沿弯曲形状伸展,单一质心未必能代表它。图提供另一种描述:相近观测以强边连接,合理分组应尽量少切断强边。这没有消除建模选择,而是把选择放到距离、邻域与相似度尺度之中。
只最小化切断的总权重,可能把一个弱连接观测单独分出。归一化割把每群的向外割权重除以群的总加权度数,减少这种偏好。但离散问题仍难解。谱方法先把指示向量放宽成实数坐标,以特征向量精确解松弛问题,再把坐标转回标签。这些步骤各自回答不同问题,不能合并成一个未经证明的最优性声明。
本节处理直接分成多群的版本。特别要先检查图,才做矩阵归一化;有孤立点时,某些常见公式根本没有定义。完整算法必须包含这些决定,以及最后的离散化规则。
定义
定义 5.1.1
(相似度、度数、体积与归一化割)
设 对称,、。定义 、、。对不交集合 ,令 ,以及 。把顶点分为正体积的非空群 ,定义
两群情形,同一跨群权重在两项出现,但分母不同,这是定义的一部分。体积不是顶点数:内部边两端皆在群内,所以计入两次。归一化割平衡的是图体积,不是强制每群人数相同。
所有度数皆正时,定义对称归一化拉普拉斯(Laplace)与随机游走矩阵
与 相似,但其右特征向量要把对称矩阵的向量乘以 。这些向量的正交性用 内积表达,并非普通欧氏(Euclid)正交。先说明正在使用哪一个矩阵,才能避免归一化错配。
体积分母还有概率意义。游走由 到 的概率是 ,度数比例分布为平稳分布,因对称性使每点流入量恰等于其度数除以总体积。在此分布下条件于目前位于 ,下一步离开 的概率,正是向外割除以体积。归一化割把各群这种条件逃逸概率相加。这个解释不需要非周期性;若要声称任意初始分布最终收敛到平稳分布,则还需要其他假设。
定义 5.1.2
(建图也是模型的一部分)
一种选择是对 设 , 固定。稀疏版本可只保留半径内或近邻间的边。若近邻关系有方向,就要选择对称化规则:任一方向成立便留边,或两个方向都成立才留边。两者会产生不同的图。
不同单位的坐标应按明确度量处理,不能让数值较大的单位自动主宰距离。高斯(Gauss)带宽太小,图在数值上可能近乎断开;太大则各边近乎一样。互为近邻的稀疏图更可能产生孤立点。特征值求解器不能判断这些现象代表真实结构,还是相似度选得不合适。
定理/命题
定理 5.1.3
(归一化割的迹形式)
假设度数皆正。对一个分割,若 ,设 ,否则为零。则 ,而
令 ,目标就是 ,限制有 ,也有 特有的离散指示结构。
定理 5.1.4
(多路谱松弛与理想分量恢复)
假设每个度数均为正且 。设 的特征值为 。在所有满足 的实 矩阵中,
由最小 个特征值对应的正交特征向量可达到此值,因此它是每个离散归一化割的下界。若图恰有 个连通分量且没有孤立点,任意正交零空间基的每行除以自身范数后,同一分量映到同一单位向量,不同分量映到互相正交的向量。
最后一句是精确的理想情形,不表示只要有小特征值,就存在唯一有意义的分组。若第 与第 特征值很接近,所选子空间可对扰动敏感;最后分组的距离若接近并列,标签也可能在子空间稳定时仍改变。
证明思路或证明
证明
(由边能量推到特征值下界)
对称性给 。取 ,只有跨界边留下,得 。指示列支撑互不重叠,故 ;把各列二次型相加,便得到迹恒等式。代入 即得归一化形式。
对角化 ,令 ,则 。记 为 第 行范数平方。 是正交投影,所以 ,且 。因此
因为两组质量 与 相等,前组特征值皆不小于 ,后组皆不大于它。选前 个特征向量便达等号。证明只放宽指示结构,没有直接产生标签。
证明
(行归一化为何找回分量)
边能量恒等式说明, 的核由各连通分量上常数的向量组成。故 的一组正交基是 。恰有 个分量时,其他正交基皆可写成 ,其中 正交。若 ,第 行就是 第 行乘正数 。行归一化消去此倍数,同群所有点完全重合,不同群内积为零、距离平方为二。
证明透视
松弛与离散化有不同责任
把指示矩阵换成所有正交列矩阵,得到精确可解的特征值问题及下界。行归一化后再作 k-means,是额外的离散化程序。离散标签转回的指示矩阵,通常不再是原松弛问题的最小矩阵。要保证某种离散化质量,必须有额外假设与证明,不能只引用 Rayleigh 论证。
实际算法先建立对称图,再处理度数为零的孤立点:可标为未指派、另列单点群,或重建图,但要明示政策。直接在每个度数加小常数会改变算子,不能称为原图的精确归一化。
在其余正度数图上数连通分量 。若 ,必须合并互不连接的分量,而图没有跨分量边去支持某个优先合并。应记录歧义或加入其他信息。以下取 :计算 最小 个特征值的正交向量,包含完整零空间,组成 。第 行限于完整零空间各列的平方范数为其所属分量 的 ,即零空间投影矩阵相应的对角项。因此整行非零。设 ,在这些行上以明确初始化和重启政策作 k-means,再把标签交还原顶点。最后计算原图割值,检查图参数与重启的敏感性。这给出一份结果,不是全局最优证书。
例题详解
例题 5.1.5
(边权差一百倍的两个分量)
顶点一、二间有权重一的边;三、四间有权重一百的边,其他皆零。度数为 ,归一化邻接矩阵有两个相同区块 。可取零空间基,使第一分量两行皆为 ,第二分量皆为 。行归一化后成 与 ,即使体积差很大也能恢复两群。基向量整体旋转不改变距离或此结论。
例题 5.1.6
(三点路径的真实松弛间隙)
单位权重路径 的度数为 ,归一化特征值为 。前两向量可取 与 ,故两群松弛值为一。分割 的割为一,体积为一与三,归一化割为 ;对称分割亦然,单独分出中心则为二。因此连最好的离散分割也严格高于松弛值。行归一化所得点为 、、,对称性容许任一端点与中心同群。
例题 5.1.7
(孤立点使原比值失去定义)
在两条边的例中加入第五个孤立顶点。其度数为零,故单点割比值是 ,没有定义。可以移除它,把其他四点分两群,再报它未指派;也可另定一种延伸目标,把它列作单点群。不能直接把比值当零,再宣称原定义已决定它的标签。加自环是另一张图,也没有提供它与其他观测的相似信息。
常见错误
反例模式
所有边乘同一正数不改变分组问题
把 换成 ,,每个割与体积都乘 ,归一化割不变。同时 ,故嵌入不变,仅容许基的惯例差异。因此把全部相似度乘大,并不会令本算法发现更强群组。改高斯带宽则通常改变相对边权,与共同倍数不同。
常见错误
(最大或最小必须连同矩阵说明)
的最小特征向量对应归一化邻接矩阵按代数值排序的最大特征向量,并非按绝对值排序。二顶点分量的邻接特征值是一与负一;负向量表示交替符号,不是第二个连通分量。混淆排序会把不同几何信息放进嵌入。
思想史
多特征向量与独立行归一化
Ng、Jordan 与 Weiss 的 2001 年原论文 指定归一化相似度的特征向量、行归一化及其后的分组。它同时使用多个向量,而非只反复二分。原文称作 的矩阵是归一化邻接矩阵;本节以 表示拉普拉斯,阅读时要辨清。
总结
归一化割以群体积比较向外权重。拿掉指示限制,迹问题可由最小特征向量解出。完整零空间加行归一化能精确识别断开分量;一般图则还要交代建图、孤立点、群数及离散化。特征值下界与最终标签质量始终是不同结论。
练习
快速检查
(对三顶点单位路径,把两端放同群、中心另成一群,计算归一化割,并与端点分割和谱下界比较。)
用度数体积,而不是群的顶点数。
解答 · 答案
端点集合体积二,中心体积亦二;两条边都跨界,割为二。因此归一化割为 。端点分割为 ,而前两特征值和为一。 分别是松弛下界、最佳离散值及较差分割。
快速检查
(直接证明各元素为度数平方根的向量,是归一化拉普拉斯的零特征向量。为何它通常不是常数?)
先乘归一化邻接矩阵。
解答 · 答案
令 ,有 ,故 。元素是 ,只有度数相同时才相等。单位化除以 。换到随机游走坐标,,解释两算子的平凡方向为何外观不同。
快速检查
(将正交嵌入 U 右乘正交矩阵 R,证明行归一化及任意两点距离只随同一旋转改变。)
正交映射保留范数及内积。
解答 · 答案
非零行 满足 ,所以其归一化行成为 。差向量范数 不变。每个群均值亦同时旋转,故任意指定分割的 k-means 目标不变;坐标可不同,几何分组问题相同。
快速检查
(三个正度数连通分量只要求两群,为何两个零特征向量可能产生全零行?要唯一合并还缺什么信息?)
选只支撑在前两个分量的基向量。
解答 · 答案
零空间是三维。若只取第一、二分量的归一化指示向量,第三分量的每行皆零,不能除以其范数。其他选基可能避开零行,但仍是任意的同值解。跨分量权重全零,图没有偏好哪两群合并;需要外加距离、领域规则,或明确承认任意政策。求解器输出的基不是额外的科学证据。