斯坦福CS224W 图与机器学习5】Spectral Clustering
第五节概述了谱聚类方法，并将其应用于上一节讨论的内容中。此外，还进一步探讨了基于motif的谱聚类方法，并将其分为两大部分。
-
谱聚类算法
-
基于motif的谱聚类
谱聚类算法
Part1 问题定义
给定一个图
如上图所示, 谱聚类就是一个bi-partition的任务, 其目标是将数据划分为两个群体A和B, 使得各组内部的样本具有最大的相似度, 各组之间的差异最大化。
那么怎么定义一个“好”的划分？怎样快速找到这样的划分呢？
Part2 评价指标
在上一节所介绍的社区检测算法中, 采用模块度作为评估标准来评估社区划分的结果, 那么对于谱聚类来说, 又该如何进行评估呢?
对于一个合理的划分方案来说，在理论上最直观的一种想法本质上就是旨在最大化内部节点之间的连接数量的同时最小化不同分区之间的连接数量。
因此，利用“edge cut”来定义划分：
，其中
是边权重，上图中
但是，在试图最小化 cut 的时候存在一个问题：如图所示，在某个节点度数为 1 的情况下切割这条边会使 cut 达到 1 的值；然而这并不是最优的划分结果；直观上来说应该是用蓝色线条来表示的划分方案才是最优解。
因此，考虑做归一化，评价指标为Conductance：
其中
在划分组A中计算所有节点的度数之和。考虑到分母中的最小值被设置为1，在示意图所示的情况下（minimum cut），这会导致conductance值增大。这表明这种划分并非最佳选择。通过归一化处理后，将有助于实现两个组内节点度数的均衡分配。
小结：可以利用Conductance作为谱聚类的评价指标
那么怎样快速找到划分呢？
Part3 谱图划分
先说结论，对于谱聚类，可以分为以下三步：
- 数据预处理：利用图的邻接矩阵A，度矩阵D，计算拉普拉斯矩阵
- 分解：计算拉普拉斯矩阵的特征值和特征向量，其中第二小特征值为
，对应的特征向量为
3. 分组：对上述特征向量
对数据进行分组，在实际应用中可以选择基于正负值或中位数值来进行分类。如图所示，在节点123的情况下, 其特征向量呈正值并归入一类;而在节点456的情况下, 则呈现负值并归入另一类。
按照以下三个步骤即可完成谱聚类算法的构建：首先进行数据预处理；其次优化算法参数；最后验证聚类效果。关于这一过程的具体实现方式及理论依据，请问以下几点：数据预处理的具体方法是什么？算法参数的设置有哪些特殊要求？结果解读的关键指标有哪些？
Q1：拉普拉斯矩阵有怎样的性质？
Q2：为什么是第二小特征值对应的特征向量？（为什么不是最小的？）
Q3：为什么用特征向量聚类来实现划分？这样的划分为什么是合理的？
Part3.1 拉普拉斯矩阵
拉普拉斯矩阵：
有这样几个性质：
-
所有特征值非负
， 即
是半正定的
证明：
所以拉普拉斯矩阵是半正定矩阵，上述三个性质均成立。另外一方面，由于
，当
时，
，则
由于该数值属于拉普拉斯矩阵的一个特征值，并且考虑到拉普拉斯矩阵的所有特性均为非负数性质，在此情况下最小的数值必定是零。这种情况下其对应的向量自然也就成为系统的关键解。
Part3.2 第二小特征值意义
首先，给出一个结论：对于任意对称矩阵M，有
，其中
是矩阵M第二小特征值，
为矩阵M第一小特征值对应的特征向量。
证明：不妨限制特征向量
均为单位向量，记
则W为正交矩阵，且有
,另
,则
，即
。则有：
由于当
时，
，则
Part3.3 特征值&谱聚类
上述两个部分有什么意义呢？由上述两个部分，我们得到了两个结论：
(把part3.2中M替换为拉普拉斯矩阵L）
为了满足上面两式，我们需要限制两个条件：
- x是单位向量：
，由于在拉普拉斯矩阵中，最小特征值为0，对应的特征向量为
，则有
现在回到谱聚类问题中，由于
则x必定同时具有正负值（如图所示），在坐标轴两侧分布着一些数据点，在谱聚类算法中我们期望最大化同一类内的连接数量的同时最小化不同类别之间的连接数量即尽量减少数据跨越零点的可能性从数学表达式上讲我们希望
。联合上式，我们有
。
为什么不是利用
呢，因为
在恒定等于零的情况下，在这种情况下图必定是不连通的状态下进行操作是无意义的行为；因此需要设定一定的约束条件后才能利用第二小的特征值及其对应的特征向量来进行划分。
通过上述三个部分，就简单解释了谱图聚类三个步骤的意义~
再补充一些提到的其他问题：
- 可以证明，如果将图G划分为A和B两个部分，且
那么对于评价指标conductance
:
，有
，即我们找到的这种划分标准是conductance的下界
证明：另
（可以证明
)
假设
,e=#edges from A to B，则：
- 上述方法中，是划分为两类，那么怎样划分为k类呢？
-
方法一：Recursive bi-partitioning 递归利用二分算法，将图划分为多类
-
方法二：该方法通过聚类多个特征向量实现降维目的；从所提取的特征集中系统性地选取前k大能量的特征向量；通过应用聚类算法（例如基于距离的聚类算法）将这些选定的特征向量划分为若干类别
基于motif的谱聚类
在第三节中阐述了有关motif的概念。通过将整个网络分解为若干个子图的形式进行审视，在这一过程中,motif概念赋予了网络一个全新的定义框架。我们可以从motif的角度切入进行谱图聚类分析,以揭示角色信息的本质。
Motif Conductance
类比edge cut和conductance，针对motif可以如下定义：
这个问题就转化为：对于给定的一个motif M和一个图G，在不影响其基本结构的前提下，在其基础上构造一个新的子图H=(V_H,E_H)，使得其motif Conductance达到最小值；其中确定最小motif Conductance属于NP难问题范畴，在此之后我们采用的方法属于近似算法范畴
Motif Spectral Clustering
类比上文谱图聚类，基于motif的聚类也分为三步：
- 数据预处理：
在 motif M 中出现的次数，在如图所示的情况下，则基于 motif 对图边权重进行了重新定义：即每条边的权重被设定为其所涉及的 motif 出现次数。
分解：与经典的谱图聚类方法类似，在本研究中我们首先通过构建拉普拉斯矩阵，并求解其相应的特征值和特征向量；但实际上是基于一个新的图结构
3. 分组：采用Sweep procedure方法将特征向量x的各个元素按照从小到大的顺序重新排列以完成排序任务
,另集合
评估各个划分下的motif conductance值，并选取具有最低motif conductance值的划分方案（如图所示）。其中参数r设置为5时取得最优效果。
从下图可以看出，在食物链网络中基于右下角 motif 的谱图聚类结果中可以看到，在每一类结果中都捕捉到了特定 motif 的结构特征，在每一类内部都包含较多特定 motif 的实例（即具有相同功能或作用），而不同类别之间共享 motif 的数量较少。
系列文章：