网易首页 > 网易号 > 正文 申请入驻

从拉普拉斯矩阵说到谱聚类

0
分享至

1、拉普拉斯矩阵
1.1 、Laplacian matrix的定义

拉普拉斯矩阵(Laplacian matrix)),也称为基尔霍夫矩阵, 是表示图的一种矩阵。给定一个有n个顶点的图,其拉普拉斯矩阵被定义为:

其中为图的度矩阵,为图的邻接矩阵。

举个例子。给定一个简单的图,如下:

把此“图”转换为邻接矩阵的形式,即为:

把的每一列元素加起来得到个数,然后把它们放在对角线上(其它地方都是零),组成一个的对角矩阵,记为度矩阵,如下图所示:

根据拉普拉斯矩阵的定义,可得拉普拉斯矩阵 为:

1.2、 拉普拉斯矩阵的性质

介绍 拉普拉斯矩阵的性质之前,首先定义两个概念,如下:

①对于邻接矩阵,定义图中A子图与B子图之间所有边的权值之和如下:

其中,定义为节点到节点的权值,如果两个节点不是相连的,权值为零。
②与某结点邻接的所有边的权值和定义为该顶点的度d,多个d 形成一个度矩阵 (对角阵)

拉普拉斯矩阵 具有如下性质:

  • 是对称半正定矩阵;

  • ,即 的最小特征值是0,相应的特征向量是 。证明: * = ( - ) * = 0 = 0 * 。(此外,别忘了,之前特征值和特征向量的定义:若数字和非零向量满足,则为的一个特征向量,是其对应的特征值)。

  • 有n个非负实特征值

  • 且对于任何一个属于实向量,有以下式子成立

其中,,,。

下面,来证明一下上述结论,如下:

2、谱聚类

所谓聚类(Clustering),就是要把一堆样本合理地分成两份或者K份。从图论的角度来说,聚类的问题就相当于一个图的分割问题。即给定一个图G = (V, E),顶点集V表示各个样本,带权的边表示各个样本之间的相似度,谱聚类的目的便是要找到一种合理的分割图的方法,使得分割后形成若干个子图,连接不同子图的边的权重(相似度)尽可能低,同子图内的边的权重(相似度)尽可能高。物以类聚,人以群分,相似的在一块儿,不相似的彼此远离。

至于如何把图的顶点集分割/切割为不相交的子图有多种办法,如

  1. cut/Ratio Cut

  2. Normalized Cut

  3. 不基于图,而是转换成SVD能解决的问题

目的是为了要让被割掉各边的权值和最小,因为被砍掉的边的权值和越小,代表被它们连接的子图之间的相似度越小,隔得越远,而相似度低的子图正好可以从中一刀切断。

本文重点阐述上述的第一种方法,简单提一下第二种,第三种本文不做解释,有兴趣的可以参考文献H. Zha, C. Ding, M. Gu, X. He, and H.D. Simon. Spectral relaxation for K-means clustering. Advances in Neural Information Processing Systems 14 (NIPS 2001). pp. 1057-1064, Vancouver, Canada. Dec. 2001。

2.1、 相关定义

为了更好的把谱聚类问题转换为图论问题,定义如下概念(有些概念之前已定义,权当回顾下):

  • 无向图,顶点集V表示各个样本,带权的边表示各个样本之间的相似度

  • 与某结点邻接的所有边的权值和定义为该顶点的度d,多个d 形成一个度矩阵(对角阵)

  • 邻接矩阵,A子图与B子图之间所有边的权值之和定义如下:

    其中,定义为节点到节点的权值,如果两个节点不是相连的,权值为零。

  • 相似度矩阵的定义。相似度矩阵由权值矩阵得到,实践中一般用高斯核函数(也称径向基函数核)计算相似度,距离越大,代表其相似度越小。

  • 子图A的指示向量如下:

2.2、 目标函数

因此,如何切割图则成为问题的关键。换言之,如何切割才能得到最优的结果呢?

举个例子,如果用一张图片中的所有像素来组成一个图 ,并把(比如,颜色和位置上)相似的节点连接起来,边上的权值表示相似程度,现在要把图片分割为几个区域(或若干个组),要求是分割所得的 Cut 值最小,相当于那些被切断的边的权值之和最小,而权重比较大的边没有被切断。因为只有这样,才能让比较相似的点被保留在了同一个子图中,而彼此之间联系不大的点则被分割了开来。

设为图的几个子集(它们没有交集) ,为了让分割的Cut 值最小,谱聚类便是要最小化下述目标函数:

其中k表示分成k个组, 表示第i个组,表示 的补集,表示第 组与第组之间的所有边的权重之和(换言之,如果要分成K个组,那么其代价就是进行分割时去掉的边的权值的总和)。

为了让被切断边的权值之和最小,便是要让上述目标函数最小化。但很多时候,最小化cut 通常会导致不好的分割。以分成2类为例,这个式子通常会将图分成了一个点和其余的n-1个点。如下图所示,很明显,最小化的smallest cut不是最好的cut,反而把{A、B、C、H}分为一边,{D、E、F、G}分为一边很可能就是最好的cut:

为了让每个类都有合理的大小,目标函数尽量让A1,A2...Ak 足够大。改进后的目标函数为:

其中|A|表示A组中包含的顶点数目。

或:

其中,。

2.3、最小化RatioCut 与最小化 等价

下面,咱们来重点研究下RatioCut 函数。

目标函数:
定义向量,且:

根据之前得到的拉普拉斯矩阵矩阵的性质,已知

现在把的定义式代入上式,我们将得到一个非常有趣的结论!推导过程如下:

是的,我们竟然从推出了RatioCut,换句话说,拉普拉斯矩阵L 和我们要优化的目标函数RatioCut 有着密切的联系。更进一步说,因为是一个常量,所以最小化RatioCut,等价于最小化。

同时,因单位向量的各个元素全为1,所以直接展开可得到约束条件:且,具体推导过程如下:

最终我们新的目标函数可以由之前的,写成:

其中,,且因,所以有:f'f = n(注:f是列向量的前提下,f'f是一个值,实数值,ff'是一个N*N的矩阵)。

继续推导前,再次提醒特征向量和特征值的定义:

  • 若数字和非零向量满足,则为的一个特征向量,是其对应的特征值。

假定 = ,此刻,是特征值, 是 的特征向量。两边同时左乘,得到 = ,而f'f=n,其中n为图中顶点的数量之和,因此 = n,因n是个定值,所以要最小化,相当于就是要最小化。因此,接下来,我们只要找到 的最小特征值及其对应的特征向量即可。

但到了这关键的最后一步,咱们却遇到了一个比较棘手的问题,即由之前得到的拉普拉斯矩阵的性质“最小的特征值为零,并且对应的特征向量正好为”可知:其不满足的条件,因此,怎么办呢?根据论文“A Tutorial on Spectral Clustering”中所说的Rayleigh-Ritz 理论,我们可以取第2小的特征值,以及对应的特征向量。

更进一步,由于实际中,特征向量 里的元素是连续的任意实数,所以可以根据 是大于0,还是小于0对应到离散情况下的,决定 是取,还是取。而如果能求取 的前K个特征向量,进行K-means聚类,得到K个簇,便从二聚类扩展到了K 聚类的问题。

而所要求的这前K个特征向量就是拉普拉斯矩阵的特征向量(计算拉普拉斯矩阵的特征值,特征值按照从小到大顺序排序,特征值对应的特征向量也按照特征值递增的顺序排列,取前K个特征向量,便是我们所要求的前K个特征向量)!

所以,问题就转换成了:求拉普拉斯矩阵的前K个特征值,再对前K个特征值对应的特征向量进行 K-means 聚类。而两类的问题也很容易推广到 k 类的问题,即求特征值并取前 K 个最小的,将对应的特征向量排列起来,再进行 K-means聚类。两类分类和多类分类的问题,如出一辙。

就这样,因为离散求解很困难,但RatioCut 巧妙地把一个NP难度的问题转换成拉普拉斯矩阵特征值(向量)的问题,将离散的聚类问题松弛为连续的特征向量,最小的系列特征向量对应着图最优的系列划分方法。剩下的仅是将松弛化的问题再离散化,即将特征向量再划分开,便可以得到相应的类别。不能不说妙哉!

2.4、谱聚类算法过程

综上可得谱聚类的算法过程如下:

  1. 根据数据构造一个Graph,Graph的每一个节点对应一个数据点,将各个点连接起来(随后将那些已经被连接起来但并不怎么相似的点,通过cut/RatioCut/NCut 的方式剪开),并且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出来,即为 。

  2. 把的每一列元素加起来得到个数,把它们放在对角线上(其他地方都是零),组成一个的对角矩阵,记为度矩阵,并把 - 的结果记为拉普拉斯矩阵。

  3. 求出的前个特征值(前个指按照特征值的大小从小到大排序得到),以及对应的特征向量。

  4. 把这个特征(列)向量排列在一起组成一个的矩阵,将其中每一行看作维空间中的一个向量,并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的各数据点分别所属的类别。


或许你已经看出来,谱聚类的基本思想便是利用样本数据之间的相似矩阵(拉普拉斯矩阵)进行特征分解( 通过Laplacian Eigenmap 的降维方式降维),然后将得到的特征向量进行 K-means聚类。

此外,谱聚类和传统的聚类方法(例如 K-means)相比,谱聚类只需要数据之间的相似度矩阵就可以了,而不必像K-means那样要求数据必须是 N 维欧氏空间中的向量。

—THE END—

文章推荐

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
CBA又一顶级伯乐!把2个铁板凳培养成大腿 让失意神塔复苏

CBA又一顶级伯乐!把2个铁板凳培养成大腿 让失意神塔复苏

体娱天下
2024-12-25 10:06:52
买房选层大忌:宁愿住4楼14楼,也别碰这6个楼层,缺点让人崩溃!

买房选层大忌:宁愿住4楼14楼,也别碰这6个楼层,缺点让人崩溃!

巢客HOME
2024-12-25 06:40:02
阿塞拜疆客机坠毁,30多人奇迹生还,向英雄机长致敬

阿塞拜疆客机坠毁,30多人奇迹生还,向英雄机长致敬

明话直说
2024-12-25 22:11:03
国家队暂停托市!12月27日,今日凌晨的四大消息全面发酵!

国家队暂停托市!12月27日,今日凌晨的四大消息全面发酵!

风口招财猪
2024-12-26 02:00:53
《蜗居》要不是海藻拿出避孕T,扔给苏淳,你永远不知道,一脸清纯的她是如何吊上宋思明的

《蜗居》要不是海藻拿出避孕T,扔给苏淳,你永远不知道,一脸清纯的她是如何吊上宋思明的

青苔同学
2024-12-18 16:04:51
749局高人揭秘:人死后大概率轮回为畜生,活人进入轮回永不超生

749局高人揭秘:人死后大概率轮回为畜生,活人进入轮回永不超生

飞云如水
2024-11-16 13:10:04
老人再婚后第一次圆房有何感想?67岁老人倾诉:她给了我很多惊喜

老人再婚后第一次圆房有何感想?67岁老人倾诉:她给了我很多惊喜

热心柚子姐姐
2024-12-23 18:30:12
海南一空姐被穷打工仔追求,婚后一个月,她才得知丈夫真实身份

海南一空姐被穷打工仔追求,婚后一个月,她才得知丈夫真实身份

小月文史
2024-11-19 21:11:58
台军刚到货的M1A2T主战坦克还没有焐热,中国保利集团就贴脸开大

台军刚到货的M1A2T主战坦克还没有焐热,中国保利集团就贴脸开大

星辰故事屋
2024-12-22 22:29:05
火药味升级,库里回击詹姆斯!

火药味升级,库里回击詹姆斯!

田先生篮球
2024-12-25 15:34:32
看2025央视春晚彩排路透,网友吐槽:该来的没来,不该来的却来了

看2025央视春晚彩排路透,网友吐槽:该来的没来,不该来的却来了

风语励志情
2024-12-25 15:26:59
成都美女被强奸暴打,致终生挂粪袋:错的婚姻,真要命啊

成都美女被强奸暴打,致终生挂粪袋:错的婚姻,真要命啊

李月亮
2024-12-25 20:36:21
暴涨21%!中国芯片出口突破9000亿,台积电:或将暂停供货!

暴涨21%!中国芯片出口突破9000亿,台积电:或将暂停供货!

美人茶话会
2024-12-26 04:04:25
千万级劣迹网红再被封禁!

千万级劣迹网红再被封禁!

鲁中晨报
2024-12-25 20:59:05
深圳前市长8年卷走20亿,花天酒地包养女星,落马时只剩三千块

深圳前市长8年卷走20亿,花天酒地包养女星,落马时只剩三千块

文史旺旺旺
2024-12-24 20:42:21
江宏杰参加女儿圣诞活动,7岁女儿高1米4,网友:和福原爱一个样

江宏杰参加女儿圣诞活动,7岁女儿高1米4,网友:和福原爱一个样

小盖纪实
2024-12-24 16:08:29
江苏常州公安破获母女被杀案,嫌疑人潜逃31年后被抓

江苏常州公安破获母女被杀案,嫌疑人潜逃31年后被抓

新京报
2024-12-24 13:11:54
官方发文,工资将迎来上涨!从2024年11月正式实施,你能受益吗?

官方发文,工资将迎来上涨!从2024年11月正式实施,你能受益吗?

社保小达人
2024-11-19 09:15:03
重磅!日本正式放宽中国人赴日签证!首设10年签!团签逗留时间延长至30天!

重磅!日本正式放宽中国人赴日签证!首设10年签!团签逗留时间延长至30天!

东京新青年
2024-12-25 18:47:19
2012年,用U型锁砸日系车并重伤车主的蔡洋早已出狱,现状如何?

2012年,用U型锁砸日系车并重伤车主的蔡洋早已出狱,现状如何?

就一点
2024-12-24 00:11:52
2024-12-26 07:11:00
算法与数学之美 incentive-icons
算法与数学之美
分享知识,交流思想
4847文章数 64529关注度
往期回顾 全部

科技要闻

理想CEO:我为啥买了不能自动驾驶的法拉利

头条要闻

哈萨克斯坦:将与坠毁客机制造商合作调查飞机失事原因

头条要闻

哈萨克斯坦:将与坠毁客机制造商合作调查飞机失事原因

体育要闻

一度消失的欧洲之王,重新燃起了欧冠梦想

娱乐要闻

2025春晚彩排路透曝光!“春晚混子”再登台

财经要闻

住房城乡建设工作会议:推动地产止跌回稳

汽车要闻

全网都在吐槽萤火虫丑 为何李斌心态稳如老司机

态度原创

本地
时尚
手机
公开课
军事航空

本地新闻

好吃潮州|尝一口,这里的美食有点“潮”

中年女人的穿衣哲学:裙子过膝,鞋子带跟,轻轻松松能美到老

手机要闻

OPPO Reno 13 标准版手机将推出“超级纯正的白色”版本

公开课

李玫瑾:为什么性格比能力更重要?

军事要闻

乌方称一枚俄导弹飞越摩尔多瓦和罗马尼亚领空 涉事两国回应

无障碍浏览 进入关怀版