作者:曾凤 责任编辑:周建丁(zhoujd@csdn.net) 本文为《程序员》原创文章,未经允许不得转载,更多精彩文章请订阅2016年《程序员》http://dingyue.programmer.com.cn
机器学习(ML)算法涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域,它主要使用归纳、综合而不是演绎。而“拓扑数据分析”作为机器学习的一种形式,已经开始被广泛应用。本文简要介绍“拓扑数据分析”在机器学习中的应用以及优势。
拓扑学是一种几何学,但它研究的并不是大家所熟悉的普通几何性质,而是一类特殊的几何性质,这就是“拓扑性质”,即图形在整体结构上的特性。它与几何图形的大小、形状以及所含线段的曲直等无关。不过,最近拓扑学开始和数据分析相结合,用来发现大数据中的一些隐形的有价值的关系,我们将其称为“拓扑数据分析”(Topological Data Analysis,简称TDA)。
拓扑学中有一个著名的定理Euler多面体定理。这个定理非常简单:对于任意的一个凸多面体,它的面数为f,棱数为l,顶点数为v,那么其必然满足下面的等式:
f-l+v=2
也就是说顶点数与面数之和比棱数多2。
2这个数字,是第一个拓扑数,它标记拓扑等价于球面的几何体。所谓拓扑等价,指的是如果两个几何体可以通过连续拉伸、扭曲、旋转等操作变换到对方(如图1),这些操作不能是粘合、撕裂,那么这两个几何体称作是拓扑等价的。因此,也有人形象地将拓扑学称为橡皮几何学,因为它研究的性质在图形做弹性形变时是不会改变的。
图1 拓扑等价示例
TDA可以有效地捕捉高维数据空间的拓扑信息,已成功地运用到许多领域,例如肿瘤、神经、图像处理和生物物理学等。TDA的成功主要基于两个事实:一是不同数据具有不同的结构,更形象地也可以称之为形状,即每个数据集都含有独特的形状;另一个是数据的形状蕴藏着巨大的研究价值,它能反映数据的大部分特征。以下我们就着重讨论如何刻画“数据的形状”。
从几何的观点来看,降维可看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性,即在高维空间中靠近的点在嵌入空间中也互相靠近。举个简单的例子,如图2,左边是点云数据,它与坐标无关,看起来像只手,右边是经过拓扑分析后得到的图像,看起来像“手的骨骼”。
图2 拓扑分析示例
从左边到右边,就完成了拓扑分析“形状的重构”。右图用几个点以及几条边就刻画出了与原数据存在“几分相似”的拓扑图,而TDA要找的就是这“几分相似”,因为这“几分相似”会产生很多有用的信息。
从以上例子可以看出,TDA学习的是数据集的整体特征,对小误差的容忍度很大——即便你的相似度概念在某种程度上存在缺陷,而且它完全不受坐标的限制,在发生变形时,仍能保持原有的性质,能很好地反映数据的形状。这就是TDA的优点-通用性。对于TDA,任何相似性概念都可以拿来使用,但对于ML,你需要一个(或更多)强化的相似性概念,与其他方法一起发挥作用。
提到拓扑,就不得不说“流形学习”。“流形”就是在局部与欧氏空间同胚的空间。换言之,它是局部具有欧氏空间性质的空间,能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发:若低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然看上去非常复杂,但在局部上仍具有欧氏空间的性质。因此可以容易地局部建立降维映射关系,然后设法将局部映射推广到全局。如果将维度降到2或3维,就能对数据进行可视化展示,因此流形学习也可被用于可视化。
“流形学习”是一类借鉴了拓扑流形概念的降维方法,分为线性的和非线性两种:
本文主要介绍一种比较新的流形学习方法:t-分布邻域嵌入算法(t-Distributed Stochastic Neighbor Embedding,简称t-SNE)。
t-SNE主要基于这样的思想:如果两个数据点在原始空间中距离较近,但它们的两个映射点距离较远,它们就会相互吸引;当它们的两个映射点距离较,则他们会相互排斥。当达到平衡时得到最后的映射,完成原始高维空间与低维映射空间之间的映射关系。
TDA经常与t-SNE算法相结合使用,能达到比较好的效果。下面通过一个TDA与t-SNE处理高维数据的案例来说明。
样本如图3,为MNIST手写数字识别库,它是美国中学生手写的数字数据库,总共有1797张图片,每张图片的大小为8*8,展开之后就是64维,每张图片代表一个样本点,所以样本数据大小为(1797,64)。考虑到高维数据计算余弦距离最快,我们采用余弦距离表示每个样本点的相似度。
图3 MNIST手写数字识别库
图4 t-SNE与TDA相结合的计算结果
图5 t-SNE与TDA相结合的计算结果
利用t-SNE与TDA相结合的算法进行计算,结果如图4和图5所示。点越大说明该集合所含的样本点越多,有边连接的部分说明两个集合相似度比较高。不同的颜色代表原始高维空间与低维映射空间之间的不同映射关系。
简单查看结果,可以发现TDA确实把相似度高的集合连接在了一起,而相似度较低的集合被分开了。从这个例子可以看出,利用TDA做可视化也是一个不错的选择。
TDA的应用比较广泛,Gurjeet Singh的文章[1]中给出了很多有关TDA的应用,例如图6,第一列和第三列代表3D数据,与它们相对应的拓扑图分别放置在第二列和第四列。它们简明地向我们解释着数据中隐藏的形状,从中我们可以得到很多有用信息,这是传统方法无法识别的。
图6 TDA可以简明地解释数据中隐藏的形状
另外,瀚思在帮助客户利用TDA对用户行为进行分析时,发现它的计算时间也相当快。测试样本数据大小为10w*10w,计算时间约为五分钟,而且错误率仅仅为1.3%。这相比传统的方法,看起来相当可观。
TDA是机器学习中一个非常强大的工具,TDA与机器学习方法可以一起使用,得到的效果比使用单个技术更好。更重要的是,它从很大程度上改变了我们分析数据的方式,将拓扑这个纯数学领域的学科与数据分析相结合,是一个很前沿和大胆的技术。笔者相信未来会有更多基于TDA与机器学习的相关算法被提出,并能够成功应用到信息安全领域。
[1] Gurjeet Singh, Facundo Meoli and Gunnar Carlsson. Topological methods for the analysis of high dimensional data sets and 3D object recognition. 2007.
曾凤,瀚思Hansight算法工程师,负责机器学习和数据挖掘工作,为Hansight的数据产品和服务提供支持。主要关注异常检测算法、分类/聚类算法、图算法等。