7.6.2 谱聚类分割法学习视频在线视频

同学们好，今天我们给大家介绍

另外一种聚类分割的方法，就是谱聚类分割方法

谱聚类是一种基于图论的方法，那么图论是沿何而来的呢？

要回答这个问题，我们先回顾一个18世纪古典的数学问题

哥尼斯堡七桥问题，在哥尼斯堡的一个公园里

有七座桥将这个普雷格尔河中两个岛以及岛和河岸相连接

那问题就是问是否可以从这四块陆地中的任意一块陆地出发

恰好通过每座桥一次，最终再回到起点，这个问题

看似很简单，人人都乐意去测试一下自己的智力

可是全城的人加在一起，也没有找到一条合适的路线

这个问题传开以后，许多欧洲有学问的人也参与思考

同样是一筹莫展

这个问题吸引了天才的数学家欧拉

他以独具的慧眼看出了这个似乎是趣味几何问题的潜在意义

公元1736年，欧拉向圣彼得堡科学院提交了一份论文

论文的题目就是哥尼斯堡的七座桥

他在论文的开头这样写到

讨论长短大小的几何学分支，一直被人们热心的研究着

但是还有一个至今几乎完全没有探索过的分支

莱布尼兹最先提到过它，称之为位置的几何学

这个几何学分支只讨论与位置有关系的关系

那么研究位置的性质，它不去考虑长短大小

也不牵扯到量的计算，但是至今为止

从未有过令人满意的定义

来刻画这门位置几何学的课题和方法

在这篇论文中，欧拉运用娴熟的变换技巧

把哥尼斯堡的七桥问题转换成大家所熟悉的一笔画问题

欧拉是这样子来解决这个问题的

他不考虑四个地区的大小形状

把这四个地区看成是连接桥梁的4个点

而且不考虑桥梁的曲直、长短

把这四个桥梁看成是连接4个点的7条直线

于是哥尼斯堡的古城在欧拉的笔下

就形成了一个结构简单的几何图形

那么这个时候，七桥问题就变成了一个一笔画问题

就是用笔不重复的画出这个几何图形的问题

那我们知道如果可以一笔画画出一个几何图形

那么必然有一个起点和一个终点

如果这两个点不重合，那么起点和终点相交的线呢

必须是奇数条，这样的点我们称作是奇点

如果起点和终点重合

那么与之相交的线必须是偶数条，我们称作偶点

而除了起点和终点以外，其它的点也必须是偶点

根据以上的分析，如果一个图形可以一笔画出来

必须满足两个条件

第一图形必须是联通的，第二图中的奇点只能是0或者是2

那么哥尼斯堡七桥问题我们可以看到

所有的点都是奇点，所以这个问题就是无解的

也就是说这个问题，我们不可能用一笔画来画出来

欧拉当时发表这一结论的时候，震惊了当时的数学界

随后人们又发明了多种类似的游戏

比如说，我们现在看到的在1857年

英国的数学家哈密尔顿，他发明了一种游戏

他用一个实心的正12面体代表一个地球

正12面体一共有20个顶点，这20个顶点分别代表世界上20座名城

那么他要求游戏者从一个城市出发，寻找一条路径

在这条路径上经过了20座城市

并且，这20座城市每次只经过一次

这个问题呢叫做哈密尔顿回路

在同一时间，还有许多诸如迷宫问题、博弈问题

还有运筹学中的中国邮差问题、另外还有著名的货郎担问题等等

这些都吸引了许多的学者 这些看起来无足轻重的游戏

却引出了许多有实用意义的新问题

从而开辟了一个新的学科 图论

那么什么是图呢？

图就是由若干个点以及连接两点的线所构成一个图形

通常用来描述某些事物之间的某种关系

用点来代表事物，用线来表示对应的两个事物间具有某种关系

比如说，我们在屏幕上显示的一个图

那么一共有6个顶点，分别用1、2、3、4、5、6来表示

在这6个点中，有一些点之间是有连线的

比如说1和2之间呢有一条连线，上面标记了一个0.8

那么就表明顶点1和2之间关系密切

而1和5之间有一条连线，但是上面只标记了0.1

说明1和5之间它的联系是不那么紧密的

我们用G来表示一个无向图

G中有两个集合，一个是V， 一个是E

其中的V里面的元素叫做顶点，E中的元素叫做边

我们用Wij表示第i个顶点和第j个顶点之间的关系

把这个Wij称作是权重，对于无向图来讲

Wij和Wji是相等的

那么对图的划分，就是指将图完全划分成若干个子图像

各个子图像之间没有交集，对图的划分必须要满足两个条件

第一个条件就是子图内的点相似度较高

第二个就是不同的子图之间的点相似度是比较低的

因此，我们来看一下

对于刚才我们给大家的这6个顶点所构成的图

在这个图中1、2、3这3个顶点

我们可以看到联系是比较紧密的

而4、5、6这三个点联系比较紧密

1和5、3和4之间的联系是不那么紧密的

所以我们就可以把这个图划分成两个子图

在划分的时候，子图之间被截断的边的权重和

我们有一个参数，用这个参数Cut来表示

谱聚类就是通过对样本数据的拉普拉斯矩阵的

特征向量进行聚类

那数据的拉普拉斯矩阵，我们用L来表示

L等于D-W，其中的D和W分别是两个矩阵

W是权重矩阵，D称作是度矩阵，它是一个对角阵

对角阵中对角线上的元素就是这个权重矩阵中

每一行的元素和构成的就是这样的一个度矩阵

下面，我们通过具体的例子来看一下

这个权重矩阵和度矩阵如何来进行定义

比如说，我们现在给大家这样的一个图，一共6个顶点

然后顶点和顶点之间我们有边连接起来

那权重矩阵我们来看一下

在1和2之间有一条连线是0.8，那么我们在这个权重矩阵中

1和2 第一行第二列和第二行第一列就分别用0.8来表示

然后第1和第3中间有一个0.6

所以一行三列和三行一列分别都是0.6，以此类推

那么度矩阵刚才说了

它的构成就是在权重矩阵中每一行的元素和作为

度矩阵中对角线上的元素 那我们看一下

在这个权重矩阵中第一行是0.8 0.6和0.1，加在一起是1.5

第二行是0.8 0.8，加在一起是1.6，依次类推

这样，我们就构成了一个度矩阵

我们刚才讲过对图的划分

就是要使对同一个子图内的点相似度高

而不同的子图的点相似度比较低

因此最简单的一种方法就是把连接最不紧密的边断开

使我们刚才定义的这个参数Cut最小，这就是最小割的方法

比如说，我们在屏幕上给大家显示了一个图

那么从这个图中我们直观的是希望能够分成这样子的两类

4、5、6是一类 1、3、2、7分成一类

但实际上，如果我们采用的是最小割的方法

我们并不能够得到这样的划分

实际上得到的划分是这个样子的，原因很简单

最小割呢，我们刚才说了是

要使得我们的那个断开的边的权重和是最小的

按照刚才我们这样子的分割方式

断开了两条边分别是0.2、0.2，它的权重和等于0.4

而我们如果是这样断开的权重和是0.3

显然这样子断开的权重和最小

所以，我们就可以看出来，这样子的一个目标函数

由于它忽略了孤立点的存在，因而划分是不合理的

那我们希望得到更好的分割结果

为了避免这样子的现象，使得我们类别数量要相对均衡

人们引入了Rcut的方法

我们先来看一下Rcut的目标函数

通过这个目标函数我们可以看出来

它不仅仅考虑了要剪断的边的权重和

而且我们还考虑了各个类别中样本数量的一个均衡

其中这个n1和n2分别表示的是我们划分到

子图1和子图2里面的顶点的个数

因此，我们可以看出来 如果一组中包含了顶点的数目越少

那么它的值就是越大的，在一个最小化问题中

这就相当于进行了惩罚，也就是说不鼓励将组分的太小

那么，上述的两种方法中

其实都没有考虑到子图内部的一个权重系数

因此人们又提出了Ncut的方法，在这种方法中

目标函数里加入了对子图内部的一个权重

我们可以看到这是Ncut的目标函数

其中的d1和d2表示的是子图1和子图2里面的权重和

这就是我们给大家介绍的三种的不同分割原则

下面，我们来看一下谱聚类的具体步骤

首先，我们要建立样本的权重矩阵

然后，根据权重矩阵，我们计算拉普拉斯矩阵

第二步，计算拉普拉斯矩阵

然后，第三步对刚才得到的拉普拉斯矩阵进行分解

得到特征值以及特征向量

第四步，在这个特征向量中

我们取特征值最小的那k个特征值所对应的特征向量

把这些特征向量构成一个新的矩阵

然后把新的矩阵的行向量，拿出来进行一个聚类

最终得到了k类，也就是说分成了k个子类

其中的第四步相当于是我们进行了一个降维处理

把原来的数据从n维降到了k维

在谱聚类中需要注意两点

第一就是对k的选择，我们可以采用启发式的方法

比如说，我们发现在特征值中

从第1个特征值到第m个特征值都比较小

但是到了第m+1个就突然变成比较大的数了

这样我们就可以选择这个k值就等于m

另外，刚才我们在第四步中说，对矩阵的行向量要进行聚类

在这种聚类中，聚类方法我们既可以采用k-means聚类的方法

也可以采用其它的聚类方法

下面在屏幕上，我们给出了用谱聚类方法进行图像分割的示例

一共给了三个示例，上面是原始图像

下面是我们对应的分割结果

相比较而言，谱聚类算法比传统的k-means算法要好

因为谱聚类是用特征向量的元素来表示原来的数据

这种特征向量具有更好的表示形式

同时，谱聚类的计算复杂度比k-means要小

这个在高维数据上表现的尤为明显

好，到这里我们就把第七章给大家介绍完了

第七章要求我们掌握的是图像分割的定义和方法

掌握图像分割的依据、边缘点检测以及

Hough变换法检测直线的原理和过程

了解门限化分割区域分割的原理和方法

最后掌握聚类分割的基本方法

好，今天的内容就给大家介绍到这里

谢谢大家 再见