集成聚类系列（三）：图聚类算法详解

2019-08-02 本文已影响0人人工智能遇见磐创

1. 图聚类算法研究现状

聚类分析是一种常用的机器学习技术，它的目的是将一个数据点划分为几个类。同一个类的数据之间具有较高的相似性，不同的类之间的相似度较低。
很多研究已表明图聚类是一种极具竞争力的聚类算法，图聚类是一种基于图划分理论的算法。与其他聚类算法相比，图聚类算法有些明显的优势。该方法可识别任意形状的聚类，使其在现实生活中得到广泛的应用。目前，在许多领域都成功地运用了图聚类算法，比如文本挖掘，网页划分，图像分割，视频分割，语音识别等

对图聚类算法仍处于初始阶段，还存在一些值得进一步研究的问题。尤其是以下方面：

如何选择合适的相似度矩阵，相似度矩阵的差异会对图聚类的性能有影响
真实数据的大部分数据是无标签数据，只有少部分数据是存在标签的，如何利用少量标签引导聚类
图聚类的计算时间复杂度比较高
如何自动确定聚类个数k,减少调参数的困扰

图聚类源于图划分理论，是近年来较为流行的聚类算法，图聚类算法的核心是将聚类问题看成图分割问题，并将图分割这个NP难问题，通过连续松弛化求解。本章研究涉及图聚类算法的三个相关技术：图划分理论，双随机矩阵，乘性更新。

2. 图划分理论

2.1. 图的 $Laplacian$ 矩阵

对于邻接矩,定义图G中子图a与子图b之间所有权的权值之和如下：

$A(a, b)=\sum_{i \in a, j \in b} A_{i j}$

其中A_{i j}定义数据点i,j之间的权重。定义与数据点i相连的所有边权值之和为度d_{i},全部度构成度向量D:

$d_{i}=\sum_{j=1}^{n} A_{i}$

构建拉普拉斯矩阵 $L=D-A$

别着急，下面我们来举个例子，看下拉普拉斯矩阵构建的过程。假设现在有6个数据点，如下图分布（可以是二维原始数据，也可以是基于某种相似规则计算了数据间的相似度量后所呈现的关联）

无向图连接

将此图转换为邻接矩阵的形式，记为矩阵A：

$A=\left(\begin{array}{cccccc}{0} & {1} & {0} & {0} & {0} & {0} \\ {1} & {0} & {1} & {0} & {1} & {0} \\ {0} & {1} & {0} & {1} & {0} & {0} \\ {0} & {0} & {1} & {0} & {1} & {1} \\ {0} & {1} & {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0}\end{array}\right)$

$D_{i}=\sum_{j=1}^{n} A_{i}$ ，度矩阵D为对角矩阵：
$D=\left(\begin{array}{cccccc}{1} & {0} & {0} & {0} & {0} & {0} \\ {0} & {3} & {0} & {0} & {0} & {0} \\ {0} & {0} & {2} & {0} & {0} & {0} \\ {0} & {0} & {0} & {3} & {0} & {0} \\ {0} & {0} & {0} & {0} & {2} & {0} \\ {0} & {0} & {0} & {0} & {0} & {1}\end{array}\right)$

构造的拉普拉斯矩阵 $L=D-A$ :

$L=\left(\begin{array}{cccccc}{1} & {-1} & {0} & {0} & {0} & {0} \\ {-1} & {3} & {-1} & {0} & {-1} & {0} \\ {0} & {-1} & {2} & {-1} & {0} & {0} \\ {0} & {0} & {-1} & {3} & {-1} & {-1} \\ {0} & {-1} & {0} & {-1} & {2} & {0} \\ {0} & {0} & {0} & {-1} & {0} & {1}\end{array}\right)$

一般常用的构造拉普拉斯矩阵的方法有如下几种：

$L=D-A$
$L_{s y s}=D^{-1 / 2} L D^{-1 / 2}=I-D^{-1 / 2} A D^{-1 / 2}$
$L_{n v}=D^{-1} L=I-D^{-1} A$

其中S为相似矩阵，D为度矩阵，I为单位矩阵。

矩阵L有如下性质:

L是对称半正定矩阵
L最小的特征值是0，所对应的特征向量是 $(1,1, \cdots, 1) \in R^{n \times 1}$
对于任意向量 $f \in R^{n}$ ，满足：

$f^{T} L f=\frac{1}{2} \sum_{i, j=1}^{n} A_{i j}\left(f_{i}-f_{j}\right)^{2}$

证明：

$\begin{array}{l}{f^{T} L f=f^{T} D f-f^{T} A f=\sum_{i=1}^{n} d_{i} f_{i}^{2}-\sum_{i, j=1}^{n} f_{i} f_{j} A_{i j}} \\ {=\frac{1}{2}\left(\sum_{i=1}^{n} d_{i} f_{i}^{2}-2 \sum_{i, j=1}^{n} f_{i} f_{j} A_{i j}+\sum_{j=1}^{n} d_{j} f_{j}^{2}\right)=\frac{1}{2} \sum_{i, j=1}^{n} A_{i j}\left(f_{i}-f_{j}\right)^{2}}\end{array}$

通常，对于2-way划分准则，我们可以求取拉普拉斯矩阵特征值的第二小的特征向量即Fiedler向量，Fiedler向量也是图划分的势函数，用来进行聚类。势函数是表示样本归属于某个子集的指示型向量，势函数表示为：
$q_{i}=\left\{\begin{array}{l}{1, i \in a} \\ {0, i \in b}\end{array}\right.$

通俗的说，就是如果样本势函数为1，那么此样本归属为a划分。如果是0，那么此样本归属为b划分。

2.2. 图划分准则

图聚类问题的实质是图划分问题，聚类的过程其实就是对图划分过程的优化。优化的目的是使子图间的相似度变小，子图内的相似度变大。一般地，通过切割图G的边，将图划分为a,b两个不相交子图，子图a与子图b之间共边的权重值之和称之为割（cut），A代表连通图的邻接矩阵，其中 $a \cap b=\phi$ ，则子图划分的目标函数为：

$\operatorname{cut}(a, b)=\sum_{u \in a, V \in b} A(u, V)$

2.2.1. 最小割

最小割是由wu等人1993年提出，原理是最小化该目标函数: $\operatorname{cut}(a, b)$ ,它将连通图A划分成两个子图a和b，使得子图间的公共连接权重值最小。但是最小割由于没有对类规模进行限制而仅考虑了聚类的外部连接，从而使得最小割容易使得子图划分出现歪斜分割不均匀现象（将原图分割后，某个子图含有样本量特别小，其他的子图含有样本量特别大，分割的子图不均衡）。为了解决这个问题，后来的标准都是引入了不同的平衡条件，以此获得更优的聚类准则。

2.2.2. 正则割

正则割是由Shi和Malik在2000年提出:
$\operatorname{Ncut}(a, b)=\frac{\operatorname{cut}(a, b)}{\operatorname{assoc}(a, V)}+\frac{\operatorname{cut}(a, b)}{\operatorname{assoc}(b, V)}$

其中， $assoc$ (a , V)表示a中所有点与图中所有点相连的权重

$\operatorname{assoc}(a, V)=\sum_{u \in a, t \in V} A(u, t)$

正则割不单单加入了所有与节点相关的边权值进行计算，而且还考虑连接每个子图部分后的权值和。正则割为了考虑类间互相连接，从而引入容量的概念来规范类间相关。并针对正则割进行优化，提出了与之相关的规范关联目标函数：

$\operatorname{Nassoc}(a, b)=\frac{\operatorname{assoc}(a, a)}{\operatorname{assoc}(a, V)}+\frac{\operatorname{assoc}(b, b)}{\operatorname{assoc}(b, V)}$

其中， $assoc$ (a , a)表示划分a部分中所有的节点之间的边权总和，assoc(a , b)表示划分后a,b两部分的连接边的权值总和。

2.2.3. 最小最大割

CHQ Ding等在2001年提出最小最大割集准则为：

$\operatorname{MMcut}(a, b)=\frac{\operatorname{cut}(a, b)}{\operatorname{assoc}(a, a)}+\frac{\operatorname{cut}(a, b)}{\operatorname{assoc}(b, b)}$

最小最大割能够同时最小化类间相似度，最大化类内相似度。

2.2.4. 平均割

Soundararajian等在2001年提出平均割集的准则函数为：
$\operatorname{Avcut}(a, b)=\frac{\operatorname{cut}(a, b)}{|a|}+\frac{\operatorname{cut}(a, b)}{|b|}$

2.2.5. 比例割

Hagen和Kahng在2002年提出了比例割集准则函数为：

$R c u t=\frac{\operatorname{cut}(a, b)}{\min (|a|,|b|)}$

比例割可以最小化类间相似性，主要依赖在目标函数中引入类平衡项。在式中|a|,|b|分别表示子图a,b的顶点数目，比例割能够在一定程度上避免分割不均匀的问题。

上述多个准则划分都是将图划分为两个部分，一般记作2-way划分，为了将图划分为k个子图，引入了多路规范割（MNcut）,我们有以下目标函数：

$M N c u t=\frac{\operatorname{cut}\left(a_{1}, V-a_{1}\right)}{\operatorname{assoc}\left(a_{1}, V\right)}+\frac{\operatorname{cut}\left(a_{2}, V-a_{2}\right)}{\operatorname{assoc}\left(a_{2}, V\right)}+\cdots+\frac{\operatorname{cut}\left(a_{k}, V-a_{k}\right)}{\operatorname{assoc}\left(a_{k}, V\right)}$

当k=2时，MNcut等价于NCut。

当类与类之间容易分开时，上述多种准则都能给出不错的聚类结果；当类与类不容易分开时，正则割能相对给出不错的聚类结果；当类与类严重重叠时，可以使用最小最大割给出子图相对平衡的聚类效果。很多实验表明正则割相对于其他准则具有相对稳定的性能，故一般图聚类首选正则割。

本章就介绍到这，计算最优图分割的公式推导，会在下一章给出。

集成聚类系列（三）：图聚类算法详解

1. 图聚类算法研究现状

2. 图划分理论

2.1. 图的 $Laplacian$ 矩阵