5. 算法的稳定性

稳定性的分析由矩阵的扰动理论给出. 这也将给出上述算法 3 中归一化行向量的需要.

5.1特征空间的扰动理论

此小节参考自 Rajendra Bhatia 的 Matrix Analysis 一书中 Section VII.1-3.

对复规范阵 $A$ [normal matrix/operator] ($A{A}^H=A^{H}A$) 及 $S\subset \mathbb{C}$, 以 $P_S(A)$ 表示到 $A$ 在 $S$ 中特征值对应特征向量所张成子空间的正交投影 [orthogonal projection] .

对于不相交的 $S_1,S_2\subset \mathbb{C}$, 由复规范变换的特征分解, 可知 $P_{S_1}(A)$ 与 $P_{S_2}(A)$ 的像是正交的. 当另一个复规范阵 $B$ 接近 $A$ 时, 我们理所当然地期待 $E:=P_{S_1}(A)$ 与 $F:=P_{S_2}(B)$ 的像接近正交.

若确实如此, 这两个投影算子复合应当得到接近于 0 的算子. 因此我们考虑用 $\Vert A-B\Vert$ 对 $\Vert EF\Vert$ 进行估计, 有如下结果:

定理 5.1.1. 若 $S_1,S_2$ 被一个宽为 $\delta$ 的圆环分离, 则对矩阵的任一保酉变换的范数 $\Vert \cdot \Vert$, 我们有$$\Vert EF\Vert \le \frac{1}{\delta }\Vert E(A-B)F\Vert \le \frac{1}{\delta }\Vert A-B\Vert .$$

注 5.1.2. 常见的 Frobenius 范数 (数值分析中讲过在 Givens 变换下不变) 、2-范数 (矩阵的最大奇异值) 都是保酉变换的.

证明. 首先, 根据 $A$ 的特征分解 $A=U\Lambda U^H$, 我们可以将 ${\mathbb{C}}^n$ 中的任意向量表示为$$x={\alpha }_1{u}_1+\cdots +{\alpha }_n{u}_n,$$从而$$AEx=\sum _{i:{\lambda }_i\in S_1}{\alpha }_{i}A{u}_i=\sum _{i:{\lambda }_i\in S_1}{\alpha }_i{\lambda }_i{u}_i=E\left(\sum _{i=1}^n{\alpha }_i{\lambda }_i{u}_i\right)=EAx,\forall x\in {\mathbb{C}}^n,$$于是 $AE=EA.$ 同理可以得到 $BF=FB$, 从而要证明的第一个不等式即为$$\Vert EF\Vert \le \frac{1}{\delta }\Vert AEF-EFB\Vert .\text{\hspace{1em}(1)}$$令 $X=EF{|}_{R(F)}$, $\tilde{A}=A{|}_{R(E)}$, $\tilde{B}=B{|}_{R(F)}$, $Y=\tilde{A}X-X\tilde{B}:R(F)\to R(E)$, 则由$$\sigma (\tilde{A})\subset S_1,\sigma (\tilde{B})\subset S_2$$被一宽为 $\delta$ 的圆环分离, 可设 $S_2\subset B_{\rho }(0)$, 从而 $S_1^c\subset B_{\rho +\delta }(0)$, 因此 $\tilde{A}$ 可逆, 有$$\begin{array}{rl}& X={\tilde{A}}^{-1}(Y+X\tilde{B})⟹\Vert X\Vert \le \Vert {\tilde{A}}^{-1}\Vert \left(\Vert Y\Vert +\Vert X\Vert \Vert \tilde{B}\Vert \right)\\ ⟹& \frac{\delta }{\rho +\delta }\Vert X\Vert =\left(1-\frac{\rho }{\rho +\delta }\right)\Vert X\Vert \le \left(1-\Vert {\tilde{A}}^{-1}\Vert \Vert \tilde{B}\Vert \right)\Vert X\Vert \le \Vert {\tilde{A}}^{-1}\Vert \Vert Y\Vert \le \frac{1}{\rho +\delta }\Vert Y\Vert \\ ⟹& \Vert X\Vert \le \frac{1}{\delta }\Vert Y\Vert .\end{array}$$由此, 根据正交投影的性质, 我们有$$\Vert EF\Vert =\Vert E{F}^2\Vert =\Vert XF\Vert \le \Vert X\Vert \Vert F\Vert =\Vert X\Vert \le \frac{1}{\delta }\Vert Y\Vert =\frac{1}{\delta }\Vert (AEF-EFB){|}_{R(F)}\Vert \le \frac{1}{\delta }\Vert AEF-EFB\Vert ,$$这就证明了 $(1)$ 式, 第一个不等式成立; 第二个不等式由 $\Vert E\Vert =\Vert F\Vert =1$ 即可得到.

$\square$

此外, 上述 $R(E)$ 与 $R(F)$“接近正交” 也可以通过它们的 “夹角” 来表述, 这将给出两个子空间的距离定义, 详见参考书, 此处不再赘述.

5.2稳定性分析

此小节参考自文章 A Tutorial on Spectral Clustering 的 Section 7.

最简单的情形: 当相似度图恰好有 $K$ 个连通分支时, 其 Laplace 矩阵 $L$ 恰好有 $K$ 个 0 特征向量, 由此直接给出了聚类方式. 加上扰动之后, 设新的 Laplace 矩阵为 $\tilde{L}=L+H$, 我们希望当 $H$ 较小时, 其前 $K$ 个特征向量比较接近原来 $K$ 个分支的指示向量.

一般而言, 由于 $L,\tilde{L}$ 都是实对称阵, 其特征值均为实数 ($L_{rw}$ 与 $L_{sym}$ 具有相同的特征值, 也都是实数) , 因此要利用上述定理, 我们需要找到一个有限区间 $S_1$ 同时包含 $L$ 和 $\tilde{L}$ 的前 $K$ 个特征值. 直观上看, 当 $H$ 越小、$L$ 的第 $K$ 个特征值与第 $K+1$ 个特征值的距离 $|{\lambda }_K-{\lambda }_{K+1}|$ [eigengap] 越大时, 区间 $S_1$ 就越容易取. 一旦取出, $L$ 和 $\tilde{L}$ 的特征空间之距离即可被上界 $\Vert H\Vert /d({\lambda }_{K+1},S_1)$ 所控制, 故可见扰动越小、特征值距离越大, 算法的误差越小, 从而越稳定.

根据这个观察, 我们可以得到:

•

选取聚类数 $K$ 的一个准则: 尽量让 $|{\lambda }_K-{\lambda }_{K+1}|$ 较大. 为此, 我们经常画出 $L$ 的特征值图 (俗称手肘图/崖底碎石图) , 通过图象的 “拐点” 来确定较好的 $K$;

•

在上述最简单的情形中, $\tilde{L}$ 的前 $K$ 个特征向量确实接近于 $1_{A_k}$, 故可以按照分量的大小 (接近 1 或者接近 0) 有效地给出聚类方式; 同理, 我们由$$f^T{L}_{sym}f=f^T{D}^{-1/2}L{D}^{-1/2}f=\frac{1}{2}\sum _{i,j=1}^N{w}_{ij}{\left(\frac{f_i}{\sqrt{d_i}}-\frac{f_j}{\sqrt{d_j}}\right)}^2$$可以得到 $L_{sym}$ 的前 $K$ 个特征向量为 $D^{1/2}{1}_{A_k}$, 从而 $L_{rw}$ 的前 $K$ 个特征向量为 $1_{A_k}$ (见 2.4 末尾的推导) . 由此可见, 当图中存在度很小的顶点 $i$ 时, 虽然 $L_{sym}$ 有一个特征向量 $u_k=D^{1/2}{1}_{A_k}$ 使得 $u_{ik}>0$, 但其值很小, 会导致扰动之后与其余 $u_{jk}=0$ 的扰动混淆, 从而会出现误判. 因此, 若使用 $L_{sym}$ 进行谱聚类, 我们要求对特征向量组成矩阵 $U$ 的各行进行归一化, 以减弱这种不稳定性因素 (对 3.2 的补充) . 然而在实际中, 可能其余 $u_{il}=0$ 在扰动后还是与 $u_{ik}$ 相当, 归一化之后会变得更大, 因此在这种极端情形下, 用 $L_{sym}$ 进行谱聚类的方法是不稳定的.