谱聚类-图的概念

2024-08-26 17:38
文章标签 概念 聚类

本文主要是介绍谱聚类-图的概念,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转自:http://guoxinmiao8.blog.sohu.com/159956578.html
这里面,最简单的一个概念就是“图”(Graph),它用于表示事物之间的相互联系。每个图有一批节点(Node),每个节点表示一个对象,通过一些边 (Edge)把这些点连在一起,表示它们之间的关系。就这么一个简单的概念,它对学术发展的意义可以说是无可估量的。几乎所有领域研究的东西,都是存在相互联系的,通过图,这些联系都具有了一个统一,灵活,而又强大的数学抽象。因此,很多领域的学者都对图有着深入探讨,而且某个领域关于图的研究成果,可以被其它领域借鉴。

矩阵表示:让代数进入图的世界

在数学上,一种被普遍使用的表达就是邻接矩阵(Adjacency Matrix)。一个有N个节点的图,可以用一个N xN的矩阵G表示,G(i,j)用一个值表示第i个节点和第j个节点的联系,通常来说这个值越大它们关系越密切,这个值为0表示它们不存在直接联系。这个表达,很直接,但是非常重要,因为它把数学上两个非常根本的概念联系在一起:“图”(Graph)和“矩阵”(Matrix)。矩阵是代数学中最重要的概念,给了图一个矩阵表达,就建立了用代数方法研究图的途径。数学家们几十年前开始就看到了这一点,并且开创了数学上一个重要的分支——代数图论 (Algebraic GraphTheory)。

代数图论通过图的矩阵表达来研究图。熟悉线性代数的朋友知道,代数中一个很重要的概念叫做“谱”(Spectrum)。一个矩阵的很多特性和它的谱结构——就是它的特征值和特征向量是密切相关的。因此,当我们获得一个图的矩阵表达之后,就可以通过研究这个矩阵的谱结构来研究图的特性。通常,我们会分析一个图的邻接矩阵(Adjacency Matrix)或者拉普拉斯矩阵(LaplaceMatrix)的谱——这里多说一句,这两种矩阵的谱结构刚好是对称的。

谱:“分而治之”的代数

谱,这个词汇似乎在不少地方出现过,比如我们可能更多听说的频谱,光谱,等等。究竟什么叫“谱”呢?它的概念其实并不神秘,简单地说,谱这个概念来自“分而治之”的策略。一个复杂的东西不好直接研究,就把它分解成简单的分量。如果我们把一个东西看成是一些分量叠加而成,那么这些分量以及它们各自所占的比例,就叫这个东西的谱。所谓频谱,就是把一个信号分解成多个频率单一的分量。

矩阵的谱,就是它的特征值和特征向量,普通的线性代数课本会告诉你定义:如果A v = c v,那么c就是A的特征值,v就叫特征向量。这仅仅是数学家发明的一种数学游戏么?——也许有些人刚学这个的时候,并一定能深入理解这么个公式代表什么。其实,这里的谱,还是代表了一种分量结构,它为使用“分而治之”策略来研究矩阵的作用打开了一个重要途径。这里我们可以把矩阵理解为一个操作 (operator),它的作用就是把一个向量变成另外一个向量:y = A x。对于某些向量,矩阵对它的作用很简单,A v = cv,相当于就把这个向量v拉长了c倍。我们把这种和矩阵A能如此密切配合的向量v1, v2, ... 叫做特征向量,这个倍数c1, c2,...叫特征值。那么来了一个新的向量x 的时候,我们就可以把x 分解为这些向量的组合,x = a1 v1 + a2 v2 +...,那么A对x的作用就可以分解了:A x = A (a1 v1 + a2 v2 + ...) = a1 c1 v1 + a2 c2 v2... 所以,矩阵的谱就是用于分解一个矩阵的作用的。

这里再稍微延伸一点。一个向量可以看成一个关于整数的函数,就是输入i,它返回v( i)。它可以延伸为一个连续函数(一个长度无限不可数的向量,呵呵),相应的矩阵 A变成一个二元连续函数(面积无限大的矩阵)。这时候矩阵乘法中的求和变成了积分。同样的,A的作用可以理解为把一个连续函数映射为另外一个连续函数,这时候A不叫矩阵,通常被称为算子。对于算子,上面的谱分析方法同样适用(从有限到无限,在数学上还需要处理一下,不多说了)——这个就是泛函分析中的一个重要部分——谱论(Spectral Theory)。

马尔可夫过程——从时间的角度理解图

回到“图”这个题目,那么图的谱是干什么的呢?按照上面的理解,似乎是拿来分解一个图的。这里谱的作用还是分治,但是,不是直观的理解为把图的大卸八块,而是把要把在图上运行的过程分解成简单的过程的叠加。如果一个图上每个节点都有一个值,那么在图上运行的过程就是对这些值进行更新的过程。一个简单,大家经常使用的过程,就是马尔可夫过程(Markov Process)。

学过随机过程的朋友都了解马尔可夫过程。概念很简单——“将来只由现在决定,和过去无关”。考虑一个图,图上每个点有一个值,会被不断更新。每个点通过一些边连接到其它一些点上,对于每个点,这些边的值都是正的,和为1。在图上每次更新一个点的值,就是对和它相连接的点的值加权平均。如果图是联通并且非周期(数学上叫各态历经性, ergodicity),那么这个过程最后会收敛到一个唯一稳定的状态(平衡状态)。

图上的马尔可夫更新过程,对于很多学科有着非常重要的意义。这种数学抽象,可以用在什么地方呢?(1)Google对搜索结果的评估 (PageRank)原理上依赖于这个核心过程,(2)统计中一种广泛运用的采样过程MCMC,其核心就是上述的转移过程,(3)物理上广泛存在的扩散过程(比如热扩散,流体扩散)和上面的过程有很重要的类比,(4) 网络中的信息的某些归纳与交换过程和上述过程相同(比如RandomGossiping),还有很多。非常多的实际过程通过某种程度的简化和近似,都可以归结为上述过程。因此,对上面这个核心过程的研究,对于很多现象的理解有重要的意义。各个领域的科学家从本领域的角度出发研究这个过程,得出了很多实质上一致的结论,并且很多都落在了图的谱结构的这个关键点上。

图和谱在此联姻

根据上面的定义,我们看到邻接矩阵A其实就是这个马尔可夫过程的转移概率矩阵。我们把各个节点的值放在一起可以得到一个向量v,那么我们就可以获得对这个过程的代数表示, v(t+1) = A v(t)。稳定的时候,v = Av。我们可以看到稳定状态就是A的一个特征向量,特征值就是1。这里谱的概念进来了。我们把A的特征向量都列出来v1, v2, ...,它们有 Avi = ci vi。vi其实就是一种很特殊,但是很简单的状态,对它每进行一轮更新,所有节点的值就变成原来的ci倍。如果0 < ci< 1,那么,相当于所有节点的值呈现指数衰减,直到大家都趋近于0。

一般情况下,我们开始于一个任意一个状态u,它的更新过程就没那么简单了。我们用谱的方法来分析,把u分解成 u = v1 +c2 v2 + c3 v3 + ...(在数学上可以严格证明,对于上述的转移概率矩阵,最大的特征值就是1,这里对应于平衡状态v1,其它的特征状态v2, v3, ...,对应于特征值1 > c2 > c3 > ... > -1)。那么,我们可以看到,当更新进行了t 步之后,状态变成u(t) = v1 + c2^t v2 + c3^t v3 + ...,我们看到,除了代表平衡状态的分量保持不变外,其它分量随着t增长而指数衰减,最后,其它整个趋近于平衡状态。

从上面的分析看到,这个过程的收敛速度,其实是和衰减得最慢的那个非平衡分量是密切相关的,它的衰减速度取决于第二大特征值c2,c2的大小越接近于1,收敛越慢,越接近于0,收敛越快。这里,我们看到了谱的意义。第一,它帮助把一个图上运行的马尔可夫过程分解为多个简单的字过程的叠加,这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二,它指出平衡状态是对应于最大特征值1的分量,而收敛速度主要取决于第二大特征值。

我们这里知道了第二大特征值c2对于描述这个过程是个至关重要的量,究竟是越大越好,还是越小越好呢?这要看具体解决的问题。如果你要设计一个采样过程或者更新过程,那么就要追求一个小的c2,它一方面提高过程的效率,另外一方面,使得图的结构改变的时候,能及时收敛,从而保证过程的稳定。而对于网络而言,小的c2有利于信息的迅速扩散和传播。

聚类结构——从空间的角度理解图

c2的大小往往取决于图上的聚类结构。如果图上的点分成几组,各自聚成一团,缺乏组与组之间的联系,那么这种结构是很不利于扩散的。在某些情况下,甚至需要O(exp(N))的时间才能收敛。这也符合我们的直观想象,好比两个大水缸,它们中间的只有一根很细的水管相连,那么就需要好长时间才能达到平衡。有兴趣的朋友可以就这个水缸问题推导一下,这个水缸系统的第二大特征值和水管流量与水缸的容积的比例直接相关,随比例增大而下降。

对于这个现象进行推广,数学上有一个重要的模型叫导率模型(Conductance)。具体的公式不说了,大体思想是,节点集之间的导通量和节点集大小的平均比例和第二大特征值之间存在一个单调的上下界关系。导率描述的是图上的节点连接的空间结合,这个模型把第二特征值c2和图的空间聚集结构联系在一起了。

图上的聚类结构越明显, c2越大;反过来说,c2越大,聚类的结构越明显,(c2 =1)时,整个图就断裂成非连通的两块或者多块了。从这个意义上说,c2越大,越容易对这个图上的点进行聚类。机器学习中一个重要课题叫做聚类,近十年来,基于代数图论发展出来的一种新的聚类方法,就是利用了第二大特征值对应的谱结构,这种聚类方法叫做谱聚类(SpectralClustering)。它在Computer Vision里面对应于一种著名的图像分割方法,叫做NormalizedCut。很多工作在使用这种方法。其实这种方法的成功,取决于c2的大小,也就是说取决于我们如何构造出一个利于聚类的图,另外c2的值本身也可以作为衡量聚类质量,或者可聚类性的标志。遗憾的是,在paper里面,使用此方法者众,深入探讨此方法的内在特点者少。

归纳起来

  • 图是表达事物关系和传递扩散过程的重要数学抽象
  • 图的矩阵表达提供了使用代数方法研究图的途径
  • 谱,作为一种重要的代数方法,其意义在于对复杂对象和过程进行分解
  • 图上的马尔可夫更新过程是很多实际过程的一个重要抽象
  • 图的谱结构的重要意义在于通过它对马尔可夫更新过程进行分解分析
  • 图的第一特征值对应于马尔可夫过程的平衡状态,第二特征值刻画了这个过程的收敛速度(采样的效率,扩散和传播速度,网络的稳定程度)。
  • 图的第二特征分量与节点的聚类结构密切相关。可以通过谱结构来分析图的聚类结构。

马尔可夫过程代表了一种时间结构,聚类结构代表了一种空间结构,“谱”把它们联系在一起了,在数学刻画了这种时与空的深刻关系。

这篇关于谱聚类-图的概念的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1109233

相关文章

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering) Power Iteration Clustering (PIC) 是一种基于图的聚类算法,用于在大规模数据集上进行高效的社区检测。PIC 算法的核心思想是通过迭代图的幂运算来发现数据中的潜在簇。该算法适用于处理大规模图数据,特别是在社交网络分析、推荐系统和生物信息学等领域具有广泛应用。Spa

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR(重复时间,repetition time)是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言,TR 是施加一个 RF(射频)脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位,主要控制后续脉冲之前的纵向弛豫程度(T1 弛豫),使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)

计算机网络基础概念 交换机、路由器、网关、TBOX

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、VLAN是什么?二 、交换机三、路由器四、网关五、TBOXTelematics BOX,简称车载T-BOX,车联网系统包含四部分,主机、车载T-BOX、手机APP及后台系统。主机主要用于车内的影音娱乐,以及车辆信息显示;车载T-BOX主要用于和后台系统/手机APP通信,实现手机APP的车辆信息显示与控

用Pytho解决分类问题_DBSCAN聚类算法模板

一:DBSCAN聚类算法的介绍 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,DBSCAN算法的核心思想是将具有足够高密度的区域划分为簇,并能够在具有噪声的空间数据库中发现任意形状的簇。 DBSCAN算法的主要特点包括: 1. 基于密度的聚类:DBSCAN算法通过识别被低密

01 Docker概念和部署

目录 1.1 Docker 概述 1.1.1 Docker 的优势 1.1.2 镜像 1.1.3 容器 1.1.4 仓库 1.2 安装 Docker 1.2.1 配置和安装依赖环境 1.3镜像操作 1.3.1 搜索镜像 1.3.2 获取镜像 1.3.3 查看镜像 1.3.4 给镜像重命名 1.3.5 存储,载入镜像和删除镜像 1.4 Doecker容器操作 1.4

【机器学习-一-基础概念篇】

机器学习 定义分类算法 应用 定义 机器学习最早是被Arthur Samuel 提出的一个概念,指计算机无需明确编程即可学习的研究领域。1950年他发明的跳棋程序,这个人机对弈游戏让他的声名鹊起,机器学习这个概念才进入大众的是视线。 在这个跳棋程序里,他编程了一种算法,这个程序与Arthur下了数万次跳棋,计算机逐渐学会了下在哪里有更大的可能会赢得比赛,哪里会输,通过这种方法,最

【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念?

大家好,我是锋哥。今天分享关于 【说说 Redis 哈希槽的概念?】面试题,希望对大家有帮助; 说说 Redis 哈希槽的概念? Redis 集群没有使用一致性 hash,而是引入了哈希槽的概念,Redis 集群有 16384 个哈希槽,每个 key 通过 CRC16 校验后对 16384 取模来决定放置哪个槽, 集群的每个节点负责一部分 hash 槽。

AI辅助编程里的 Atom Group 的概念和使用

背景 在我们实际的开发当中,一个需求往往会涉及到多个文件修改,而需求也往往有相似性。 举个例子,我经常需要在 auto-coder中需要添加命令行参数,通常是这样的: /coding 添加一个新的命令行参数 --chat_model 默认值为空 实际上这个需求涉及到以下文件列表: /Users/allwefantasy/projects/auto-coder/src/autocoder/auto