Clustering 聚类
谱聚类
上文我们引入了是聚类, 并介绍了第一种聚类算法 K-means. 今天, 我们来介绍一种流行的聚类算法 -- 谱聚类(Spectral Clustering), 它的实现简单, 而且效果往往好于传统的聚类算法, 如 k-means, 但是其背后的原理涉及了很多重要而复杂的知识, 如图论, 矩阵分析等. 别担心, 今天小编就带你一举攻克这些难关, 拿下谱聚类算法.
Q: 什么是谱聚类?
A: 谱聚类是最流行的聚类算法之一, 它的实现简单, 而且效果往往胜过传统的聚类算法, 如 K-means. 它的主要思想是把所有数据看作空间中的点, 这些点之间用带权重的边相连, 距离较远的点之间的边权重较低, 距离较近的点之间边权重较高, 通过对所有数据点和边组成的图进行切图, 让切图后不同子图间边权重和尽可能低, 而子图内边权重和尽可能高来达到聚类的目的.
接下来我们先介绍图的基础知识以及图拉普拉斯, 然后引入谱聚类算法, 最后从图分割的角度来解释谱聚类算法.
图的概念
对于一个图 G, 我们通常用 G(V,E)来表示它, 其中 V 代表数据集合中的点{v1,v2,...vn},E 代表边集(可以有边相连, 也可以没有). 在接下来的内容中我们用到的都是带权重图(即两个顶点 vi 和 vj 之间的连边带有非负权重 wij>0). 由此可以得到一个图的加权邻接矩阵 W=(Wij)i,j=1,...n. 如果 Wij=0 代表两个顶点之间无边相连. 无向图 G 中 wij=wji, 所以权重矩阵是对称的.
对于图中的任意一个点 vi, 定义它的度为与它相连的所有边的权重之和, 即. 度矩阵就是对角元素分别为每个点的度, 非对角元素为 0 的矩阵.
给定点的一个子集 A 属于 V, 定义 A 的补集为 A 的指示向量为 如果 fi=1, 则顶点 vi 在子集 A 中, 否则为 0. 为了方便, 在下文中, 我们使用 来表示顶点 i 在集合 A 中. 对于两个不相交子集 A,B 属于 V, 我们定义 表示两个子集之间的权重和.
有两种度量 V 中子集 A 大小的方法:|A | 表示 A 中顶点的个数, vol(A)表示 A 中顶点的度的和.
相似图
思考我们构建相似性图的目的是什么? 是为了对点之间的局部邻域关系建模. 那么根据我们所关注的邻域关系, 相似性图的定义也可以不同, 以下提到的图都经常在谱聚类中使用:
ε邻域图: 将所有距离小于ε的点相连, 由于有边相连的点之间都差不多, 加权边不会包含关于图中数据点更多的关系, 因此, 这种图常常是无权重的;
k 近邻图: 将 vi 与它前 k 近的顶点相连, 要注意, 这种定义的图是有向图, 因为 k 近邻关系并不是对称的(A 是 B 的 k 近邻, 而 B 不一定是 A 的 k 近邻). 我们可以通过两种方式将它变成无向图: 一种是只要 A 是 B 的 k 近邻, AB 之间就会连一条边; 另一种是必须同时满足 A,B 是彼此的 k 近邻, 才能在 AB 之间连一条边. 在构建好图之后, 在根据点的相似性给边赋权重;
全连接图: 任意两点之间都连一条边, 并根据两点之间的相似性给边赋权重. 由于图必须能代表局部邻居关系, 所以使用的相似性度量方法必须能对这种关系建模. 比如, 高斯相似性方程, 其中参数σ控制邻域的宽度(作用类似ε邻域图中的ε参数).
图拉普拉斯矩阵及其基本性质
图拉普拉斯矩阵是谱聚类的主要工具, 对这些矩阵的研究有一个专门的领域, 叫做谱图理论, 感兴趣的同学可以去了解下. 在这章中我们定义不同的图拉普拉斯并介绍它们最重要的性质.
在接下来的介绍中, 我们定义的图 G 是无向的, 带权重的(权重矩阵为 W), 我们假定所有特征向量都是标准化的(如常向量 C 和 aC 是一样的), 特征值是有序且可重复的, 如果提到了前 k 个特征向量, 就意味着这 k 个特征向量对应 k 个最小的特征值. D 代表上文提到的度矩阵, W 代表权重矩阵.
非规范化图拉普拉斯矩阵:
非规范化图拉普拉斯矩阵定义为 L:D-W, 它具有如下重要特性:
1. 对于任意特征向量, 有:
;
证明:
2. L 是对称半正定的;
证明: D,W 都是对称的, 且特性 1 的证明表明 L 是半正定的;
3. L 的最小特征值是 0, 对应的特征向量是单位向量;
4. L 有 n 个非负的实值特征向量:
证明: 由前三个特性可以直接得出;
注意非规范化图拉普拉斯矩阵以及它的特征向量, 特征值可以被用在描述图的很多特性, 其中在谱聚类中的一个重要性质如下:
连通分量数与 L 的普: G 是一个非负权重无向图, 那么 L 的特征值 0 的重数 k 就等于图中联通分量 A1,...Ak 的个数, 特征值 0 的特征空间由这些联通分量的指示向量 表示;
证明: 以 k=1 为例, 代表这是一个连通图, 假设特征值 0 对应的特征向量为 f, 则
, 由于权重 w 是非负的, 要使和为 0 当且仅当每一项都为 0. 因此, 如果两个顶点 vi 和 vj 有边相连(wij>0),fi 必须等于 fj, 从这里可以看出如果图中的顶点可以有一条路径相连, 那么 f 必须是常向量. 此外, 由于无向图中连通分量的所有顶点都可以通过一条路径相连, 所以 f 在整个连通分量上必须是常数. 因此在只有一个连通分量的图中, 只有一个常向量作为 0 的特征向量(作为唯一一个联通部分的指示向量).
现在考虑 k 大于 1 的场景, 不失一般性, 我们假设顶点是按照它们所属的连通分量排序的, 在这种情形下, 邻接权重矩阵 W 可以写成分块对角矩阵的形式, 同样, L 可以写作
注意, 每一个块 Li 也是一个图拉普拉斯矩阵, 分别对应图的第 i 个连通分量, L 的普就由 Li 的普组合而成, 而且 L 对应的特征向量就是 Li 的特征向量. 由于 Li 一个连通图的图拉普拉斯矩阵, 而每一个 Li 有重数为 1 的特征值 0, 也就是对应第 i 个联通子图的常向量.
规范化图拉普拉斯矩阵
规范化图拉普拉斯矩阵有如下两种定义:
我们先来介绍它们的性质:
1. 对任意特征向量, 我们有:
;
2. λ是 Lrw 的特征向量 u 的特征值 当且仅当 λ是 Lsym 的特征向量 的特征值;
3. λ是 Lrw 的特征向量 u 的特征值当且仅当λ和 u 满足 Lu=λDu;
4. 0 是 Lrw 的常数特征向量 的特征值, 那么 0 也是 Lsym 的特征向量 的特征值.;
5. Lsym 和 Lrw 是半正定的且有 n 个非负的实特征值;
与非规范化图拉普拉斯矩阵相同, Lsym 和 Lrw 的 0 特征值的重数 k 就等于图中联通分量的个数, 证明与上面类似, 不再赘述.
谱聚类算法
现在我们来介绍最常见的谱聚类算法.
解释: 首先构建相似性图, 并用 W 表示权重邻接矩阵, 构建度矩阵 D, 求出拉普拉斯矩阵 L; 计算 L 的前 m 个特征向量, 以这 m 个特征向量作为列组成 n*m 的矩阵 U, 其中每一行作为一个 m 维的样本, 共 n 个, 对这 n 个行向量进行 kmeans 聚类.
对于规范化的谱聚类有两种不同的版本, 依赖于两种标准化图拉普拉斯矩阵.
第一种是:
注意这里使用的是 generalized eigenvectors(广义特征向量), 即矩阵 Lrw 对应的特征向量, 所以这一算法针对的是标准化的拉普拉斯矩阵 Lrw.
下一个算法也是标准化的谱聚类, 不过用的是 Lsym, 该算法介绍了一种额外的行标准化步骤:
上面三种算法的步骤其实都差不多, 只不过是使用的拉普拉斯矩阵有差别. 在算法中, 主要的工作就是将 x 抽象表征为 k 维的数据点(降维), 接下来我们将揭晓为什么这样做能提高聚类的效果. 我们将从图分割的角度来介绍谱聚类的工作原理.
图切分的观点
聚类算法的思想就是根据数据点之间的相似性将它们划分到不同组. 当我们的数据以相似性图的形式给出时, 聚类问题又可以这样解释: 我们想要找到图的一种划分, 不同组点的边之间有很低的权重而同一个组中点之间的边有较高的权重. 在本节中, 我们将介绍如何将谱聚类问题近似于图的划分问题.
给定一个相似性图, 邻接权重矩阵 W, 最简单直接的方法来创建一个图的分割就是解决最小割问题. 前面我们已经提到过 和 A 的补集的概念. 给定子集个数 k, 最小割方法就是选择一种划分 A1,...,Ak 使得 最小. 特别是对 k=2, 最小割问题相对是一个简单的问题, 可以被有效地解决. 然而在实际中, 最小割的解并不能很好地将图划分, 因为它只是简单地将一个独立的点从剩余的图中划分出来, 这显然不符合聚类的需求. 解决这种问题的一种方法是必须保证子集 A1,...,Ak 足够大, 实现这一限制的最常见的目标函数有两种: RatioCut 和 Ncut.RatioCut 用子集 A 中点的个数表示 A 的大小, Ncut 用子集 A 中边的权重和来度量 A 的大小, 它们的定义分别如下:
假如簇 Ai 不是特别小, 两个目标函数的值都会有较小的值, 因此这两种函数都试图达到聚类的平衡, 但是, 引入这一 "平衡" 条件使得之前简单的最小割问题变成了 np 难问题. 谱聚类就是解决这一问题的一种松弛版本, 我们将看到松弛 Ncut 将会导致规范化谱聚类, 而松弛 RatioCut 将导致非标准化谱聚类.
从 RatioCut 切图的角度解释谱聚类算法
我们先讨论 k=2 的情形, 我们的目标函数是, 首先重写这个问题. 给定子集 A, 我们定义向量, 其中
现在 RatioCut 目标函数可以写作非规范化图拉普拉斯矩阵的形式:
而,
最后, 由于 f 满足
所以, 优化问题重写为:
这是一个离散优化问题因为仅允许解向量 f 中的每一个值只能是两个特殊值, 仍是 Np 难问题. 最常用的松弛就是将离散条件改为 fi 可以取任意实数, 松弛后的目标函数为
根据 Rayleigh-Ritz 理论, 问题的解 f 为拉普拉斯矩阵 L 的第二小的特征值所对应的特征向量(最小的特征值为 0, 对应常向量). 所以我们可以通过求 L 的第二特征向量来解决 RatioCut 问题. 然而我们得到的 f 是实值向量, 要把它转化为离散的指示向量, 最简单的方式就是使用 sign,
推广到 k>2 的场景, 将 V 划分成 k 个子集 A1,...Ak, 我们定义 k 个指示向量 , 其中
代表每个点的划分情况. 定义矩阵 作为以 k 个指示向量为列向量的矩阵, 显然 H 中的列相互正交, 于上面的计算类似, 我们可以得到, 进而, 然后得到 RatioCut 问题的定义:
Tr 表示矩阵的迹, 所以最小化 RatioCut 问题可以写作
同样的, 我们运行 H 中的取值为任意实数, 松弛后的问题为:
这是迹极小化问题的标准形式, 同样根据 Rayleigh-Ritz 理论, 问题的解就是选择包含 L 的前 k 个特征向量作为列而组成的 H 矩阵. 其实矩阵 H 就是上面非标准化谱聚类算法中提到的矩阵 U. 然后将实值矩阵转化成离散的形式. 最后用 kmeans 对 U 的每一行进行聚类.
从 NCut 的角度解释谱聚类算法:
与在 RatioCut 中用到的相似的技术同样可以用到规范化谱聚类作为最小化 Ncut 的松弛. 当 k=2 时我们定义聚类的指示向量 f 中的每个元素为
和上面类似我们可以检查 ,, 以及 因此, 可以重写最小化 Ncut 问题为
然后对问题进行松弛:
定义, 有
其中 , 是 Lsym 的第一特征向量, vol(V)是常数. 因此, 上述目标函数符合 Rayleigh-Ritz 理论, 最优解 g 就是 Lrw 的第二特征向量.
推广到 k>2 的场景, 我们定义指示向量, 且
定义 H 为包含 k 个指示向量 (作为列) 的矩阵. 显然,
那么最小化 Ncut 问题可以写作
, 松弛后为
这又是一个标准的迹最小化问题, 问题的解 T 是包含 Lsym 的前 k 个特征向量为列向量的矩阵. 再将 代入, 可以发现 H 包含矩阵 Lrw 的前 k 个特征向量.
谱聚类算法总结
谱聚类的优点:
1. 对于处理稀疏数据的聚类效果很有效;
2. 使用了降维, 在处理高维数据聚类时比传统聚类好;
3. 当聚类的类别个数较小的时候, 谱聚类的效果会很好;
4. 谱聚类算法建立在谱图理论上, 与传统的聚类算法相比, 具有能在任意形状的样本空间上聚类且收敛于全局最优解.
谱聚类的缺点:
1. 谱聚类对相似图和聚类参数的选择非常敏感;
2. 谱聚类适用于均衡分类问题, 即簇之间点的个数差别不大, 对于簇之间点的个数相差悬殊的问题不适用.
来源: https://www.cnblogs.com/PJQOOO/p/11830838.html