Loading...
墨滴

张春成

2021/09/27  阅读:29  主题:默认主题

有图必有谱

有图必有谱

谱聚类是针对“图”的节点分割算法。 理想的谱聚类需要解决NP-Hard问题: 分割导致解空间不连续; 而节点搜索导致计算规模随着数据规模而扩大。 因此,谱聚类算法是寻找一个可行的近似解。


谱聚类的问题描述

我们希望有这样一种算法, 它能够根据图中各个节点的连接度, 对它们进行分割。 这样,在对它们进行可视化的时候, 用户可以不再纠结把每个节点放在哪里, 而是可以通过一个简单的物理力学模拟, 达到将它们放置在合适位置的效果。

【这是一段棒到不行的视频】

感兴趣可以移步我的交互式Notebook[1]

可以看到, 用户只需要做一些简单的拖拽, 就可以得到一张看得过去的可视化图结构。

图的拉普拉斯矩阵

对于 个顶点构成的连接图, 总可以用 矩阵表示这些顶点之间的连接关系。 其中, 代表节点 之间的连接强度。 此时,由于缺乏合适的定义方式, 该矩阵主对角线上的值均未定, 我们暂定它们为零。

为了补全矩阵对角上的值, 我们计算每个节点的“连接度”, 构造新的对角阵

此时,我们可以通过 矩阵补全 矩阵, 从而构造“拉普拉斯”矩阵

这个矩阵是谱聚类的基础。

指示向量

先不纠结物理意义, 我们直接构造一个指示向量

这是一种比较绕的表示方法。 简单来说, 它是一个由 组成的 维列向量。 其中, 代表正常数,在数值上它等于 向量的非零值数量的倒数

其中, 代表狄利克雷函数。

基于这个指示向量, 我们构造它的二次型

如果你熟悉矩阵的乘法规则, 可以容易看到二次型的值即是矩阵 相应行和列所有元素之和

VtLV
VtLV

它具有极其明确的物理意义, 代表按照指示向量 的要求对图进行切割之后, 所有不同组的节点之间的连接强度之和。

对于 个类别的分割, 谱聚类问题可以等价于找到 个相互独立的 指示向量, 使其满足

其中, 代表求矩阵的迹, 我们同时要求指示向量相互正交,

它的物理意义为

找到图的 组的分割,这个分割满足两个条件

  1. 不同组节点之间的连接强度尽量小,即切掉尽量少(不重要)的边;
  2. 组内节点之间的连接强度尽量大,即保留尽量多(重要)的边。

根据这些指示向量的非零值, 我们可以对不同类的节点进行染色, 得到的效果如下图所示

Cluster1
Cluster1

图中的颜色代表不同组的节点, 线条代表节点之间的连接。

NP-Hard

回顾我们对指示向量的要求,可以概括为两点

  1. 所有值非零即正,且正元素的值等于“非零值数量”的倒数;
  2. 不同的指示彼此独立,即所有指示向量的非零值位置不能重合。

这意味着解空间不是连续的,而是离散的; 为了求解这些指示向量,需要进行每个节点取舍的遍历。 这显然是一个NP-Hard问题。 因此,我们需要求它的近似解。

谱聚类的近似求解

近似求解的思路是一个两步走的思路

  1. 放松对离散值的要求, 利用特征值分解算法,求解连续空间中的替代指示向量;
  2. 放松对损失函数的要求, 利用K均值算法,将替代向量转化为严格的指示向量。

最后,我们将看到, 即使经过了两步放松, 我们找到的解也还是对全局最优解的合理估计。

特征值分解

这里利用到一个简明的数学原理,即

实对称矩阵相似于实对角阵

其中, 为对角矩阵,且 为特征向量按列构成的对称矩阵

矩阵中,其对角线上的值为矩阵 的特征值, 我们可以将从小到大进行排列。 排列后,选择其中较小的 个特征值对应的特征向量 , 就对应着使谱聚类损失函数最小的一组连续向量。

只可惜,它们尚不满足指示向量的离散要求。 但它们是我们在下一步,继续寻找指示向量的关键,

因此,我们暂时称 为替代指示向量(矩阵),简称替代向量(矩阵)。 由于在这里无须严格区分具体的某一个指示向量和它们构成的矩阵, 因此暂时采用这种模糊的表达,而不致产生歧义。

K均值

下面我们将从连续的替代向量,求解得到离散的指示向量, 首先明确替代向量构成的矩阵的形式

其中, 代表节点数量, 代表我们选取的较小的 个特征值的特征向量。

首先构造二次型,并考虑它的迹

其中, 代表矩阵的迹, 是矩阵每个行向量的二范数。

从二范数的思路开展扩展,考虑K均值算法的损失函数

其中, 代表第 类的聚类中心, 代表第 个节点。

虽然看上去有些架空,但我们稍微将二次型进行变形, 引入满足指示向量规则的新向量组 , 则K均值算法的损失函数,可以用如下方式进行表达

其中, 代表按 矩阵扩展得到的矩阵扩展方法是将 个列, 按非零值的位置扩展成行。 去除上式中的不变项,我们得到

这里,给 脱掉 的原因是这个扩展方法在失去 要求的条件下, 在计算上等价于每个独立的列只计算一次。

可以看到,从形式上, 指示向量构成的矩阵 与替代向量 具有一一对应的关系。 先给出推论,这些K均值算法找到的向量就是我们要找的指示向量。 下面将进行简要分析。

误差估计

先从特征值分解的损失函数(第一次近似)开始,以它为核构造二次型。

这里,我们相当于把其中的 替换成了K均值算法损失函数(第二次近似)中的

由于 矩阵的正交性,它进一步可以简化为

由最小化K均值算法损失函数的计算原理可知, 即是使谱聚类损失函数取得极小值的一个近似解。

误差主要考虑两点

  1. 这种近似的误差出现在哪里呢?

    就在替换 对角阵的过程中。 具体来说,当 矩阵与对角阵越相似, 即在归一化之后,它主对角线上的值越相近, 则近似效果越好。

  2. 这种误差会造成什么影响呢?

    这个问题不是很大,因为一般来说, 我们要处理的图只要不是过于奇葩, 它的特征值在尾部的分布,一般都偏向于差异不大, 也就是说, 矩阵与 矩阵的差异一般不大。

所以这种近似方法,通常可以得到满意的结果。

参考资料

[1]

Notebook: https://observablehq.com/@listenzcc/spectral-clustering

张春成

2021/09/27  阅读:29  主题:默认主题

作者介绍

张春成