CurvatureFlow的个人博客分享 http://blog.sciencenet.cn/u/CurvatureFlow

博文

大数据拓扑分析的基础-同调理论

已有 13765 次阅读 2015-10-18 07:41 |系统分类:科普集锦


由庞加莱猜测,我们知道:相对于曲面而言,同伦群和同调群保留了相同的信息,因此彼此等价;对于三流形而言,同伦群反映的信息远远多于同调群,同伦群强于同调群。但是,同伦群本身为非阿贝尔群(非交换群),判定两个非阿贝尔群是否同构是非常繁难的问题。相反,同调群是同伦群的阿贝尔化,阿贝尔群的计算只需要线性代数。因此,同调论在大数据分析和物联网领域被广泛应用。


图0.同伦群是非阿贝尔群。


如图所示,环路无法在曲面上缩成一个点,因此同伦群中,同时,我们得到。因此亏格为2的曲面的同伦群不可交换。


我们记的中心交换子群为所有形如生成的正规子群,

那么商群

为一阿贝群,即为曲面的一维下同调群。换句话说,同调群是同伦群的阿贝尔化


环路在同伦群中不是单位元,但是在同调群中却是单位元。几何上来看,将曲面分成两个连通分支,是其中一个分支的边缘。这意味着,在同调群中,边缘环路被视为单位元。


同调群概念的要义在于:边的边为空,圈和边的差别就是同调


同调群的概念


单纯复形是曲面三角剖分的直接推广,但是单纯复形可以表示更为广泛的拓扑空间,例如非流形的空间。


单纯形 给定中一般位置的个点维单纯形是这些点构成的凸包(convex hull),

我们称为单纯形的顶点。如果另外一个单纯形包含在中,,我们称的一个面。


单纯形是有定向的,每一个单纯形有两个定向,单纯形的定向由其顶点的排列给出。我们考虑数列的所有排列,它们构成对称群,其中所有由偶次对换(即只交换两个数的位置)构成的子群记为。如果排列属于,则单纯形的定向为正,反之定向为负。


通常意义下的点,线段,三角形,四面体就是0到3维的单纯形。


单纯复形 单纯形粘贴在一起就构成单纯复形。所谓一个单纯复形就是一组单纯形的并集,满足两个条件,

  1. 如果一个单纯形属于,那么的所有面都属于

  2. 如果两个单纯形都属于,那么或者它们的交集为空,或者它们的交集是它们共同的一个面。


通常意义下,曲面的三角剖分就是单纯复形。


图1. 复形上的1维和2维链。


链群 给定一个单纯复形,一个维链就是所维单纯形的线性组合,如图1所示,

,

所有的维链在加法下成一阿贝尔群(可交换群),记为,

.

其中零元为的逆元为.



图2. 边缘算子。


边缘算子 维边缘算子是链群之间的一个同态

,

作用在单纯形上

,

作用在链上

直观上,边缘算子就是剥离每个链的边界。


通过直接计算,我们可得到

亦即边的边为空



图3. 闭链和开链。


同调群 维链被称为是闭链,如果。所有的闭链构成的一个子群,记为;如果存在一个维链,满足,那么被称为是恰当链,所有恰当链构成一个子群,记为。因为边的边为空,所以恰当链必为闭链,

给定单纯复形,我们得到链复形,


具有条件



图4. 恰当闭链和非恰当闭链。


综上所述,边(恰当链)一定是圈(闭链),圈可能不是边。圈和边的差别就是同调


如图4所示,左帧显示了恰当的闭链,每一个闭链都包围着一个曲面区域,因此是边缘。右帧是非恰当的闭链,这条链并不包围任何一个曲面区域。如果我们把曲面沿着切开,我们得到一个圆筒面,圆筒面有两个边缘曲线,

但是本身并不构成圆筒面的边界。


我们将单纯复形的所有同调群放在一起,记为


同调群的计算


曲面一维同调群的基底和曲面基本群基底相同,我们可以用基本群的组合算法来计算一维同调群基底。高维同调群的算法基于线性代数的矩阵特征值和特征向量算法。


我们可以将链群视为线性空间,边缘算子是线性算子,因此可以被表示为矩阵。假设复形所有的维单纯形为

它们线性张成维链群

复形所有的维单纯形为

它们线性张成维链群

。边缘算子具有矩阵表示,

,

这里连接数是一个整数,定义如下:如果,则为0;如果的一个边缘面,,则为+1;如果的一个边缘面,,则为-1。


如此,我们构造离散拉普拉斯算子:

,

的基底是的对应于0特征根的特征向量。


这里,是整数矩阵,存在Smith 标准型(Smith Normal Form):存在可逆整数矩阵, 为对角阵,

这里, 整除,并且

是所有阶子矩阵行列式的最大公因子。



大数据的拓扑分析



图5.持续同调(Persistent Homology)。


同调理论在大数据拓扑分析中举足轻重,近些年来Persistent Homology方法被工业界广泛应用。一般商业数据,多半表示成高维空间中的点云。比如我们研究一位病患,我们将每一项检测指标作为一个维度,将病人表示成空间中的一个点。假如我们有高维空间中的点云数据,围绕每个采样点,我们做一个半径为的小球。如果两个小球相交,我们加上一条连接两个采样点的边,这样我们得到一个Cech复形(Cech Complex),记为。Cech复形中k-完全子图被视为k维单纯形,因此,Cech复形成为一个单纯复形。我们可以计算其同调群。那么的生成元代表了Cech复形各个维数的“孔洞”。我们然后变化半径,从而得到一系列的同调群,和一系列的“孔洞”。依随半径的变化,如果有些“孔洞”出现后迅速消失,则这些孔洞多半是噪声;如果有些孔洞持续存在,则它们应该是真正的拓扑特征。



图6. 无线传感器网络-空洞检测。


同调理论在物联网领域也有广泛应用。如图6所示,我们计划用无线传感器网络来完全覆盖一个平面区域。每个传感器覆盖一个半径为的圆盘,那么它们的并集是否存在孔洞。这可以用Persistent Homology类似的手法求出。如果一维同调群非平庸,则必有孔洞存在。孔洞的边缘也可以精确求出。


讨论


为了计算的便利,同调群舍弃了空间的大量拓扑信息。同调群同构的空间不一定拓扑同胚。那么,如何刻画同调群同构的空间呢?我们会在后面章节予以彻底揭示。




【老顾谈几何】邀请国内国际著名纯粹数学家,应用数学家,理论物理学家和计算机科学家,讲授现代拓扑和几何的理论,算法和应用。




https://blog.sciencenet.cn/blog-2472277-928920.html

上一篇:山外青山-浅谈不动点类理论
下一篇:万变不离其中-布劳威尔不动点
收藏 IP: 98.116.113.*| 热度|

3 雷娜 韦玉程 刘熠

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-5 15:22

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部