拓撲數(shù)據(jù)分析在機器學習中的應用

拓撲數(shù)據(jù) 機器學習數(shù)據(jù)分析人工智能

曾鳳 | 2016-05-06 15:36

【數(shù)據(jù)猿導讀】機器學習(ML)算法涉及概率論、統(tǒng)計學、逼近論、凸分析、算法復雜度理論等多門學科。它是人工智能的核心，是使計算機具有智能的根本途徑，其應用遍及人工智能的各個領域，它主要使用歸納、綜合而不是演繹。而“拓撲數(shù)據(jù)分析”作為機器學習的一種形式，已經(jīng)開始被廣泛應用。本文簡要介紹...

什么是拓撲學?

拓撲學是一種幾何學，但它研究的并不是大家所熟悉的普通幾何性質，而是一類特殊的幾何性質，這就是“拓撲性質”，即圖形在整體結構上的特性。它與幾何圖形的大小、形狀以及所含線段的曲直等無關。不過，最近拓撲學開始和數(shù)據(jù)分析相結合，用來發(fā)現(xiàn)大數(shù)據(jù)中的一些隱形的有價值的關系，我們將其稱為“拓撲數(shù)據(jù)分析”(Topological Data Analysis，簡稱TDA)。

拓撲學中有一個著名的定理Euler多面體定理。這個定理非常簡單：對于任意的一個凸多面體，它的面數(shù)為f，棱數(shù)為l，頂點數(shù)為v，那么其必然滿足下面的等式：

f-l+v=2

也就是說頂點數(shù)與面數(shù)之和比棱數(shù)多2。

2這個數(shù)字，是第一個拓撲數(shù)，它標記拓撲等價于球面的幾何體。所謂拓撲等價，指的是如果兩個幾何體可以通過連續(xù)拉伸、扭曲、旋轉等操作變換到對方(如圖1)，這些操作不能是粘合、撕裂，那么這兩個幾何體稱作是拓撲等價的。因此，也有人形象地將拓撲學稱為橡皮幾何學，因為它研究的性質在圖形做彈性形變時是不會改變的。

圖1 拓撲等價示例

TDA可以有效地捕捉高維數(shù)據(jù)空間的拓撲信息，已成功地運用到許多領域，例如腫瘤、神經(jīng)、圖像處理和生物物理學等。TDA的成功主要基于兩個事實：一是不同數(shù)據(jù)具有不同的結構，更形象地也可以稱之為形狀，即每個數(shù)據(jù)集都含有獨特的形狀;另一個是數(shù)據(jù)的形狀蘊藏著巨大的研究價值，它能反映數(shù)據(jù)的大部分特征。以下我們就著重討論如何刻畫“數(shù)據(jù)的形狀”。

從幾何的觀點來看，降維可看成是挖掘嵌入在高維數(shù)據(jù)中的低維線性或非線性流形。這種嵌入保留了原始數(shù)據(jù)的幾何特性，即在高維空間中靠近的點在嵌入空間中也互相靠近。舉個簡單的例子，如圖2，左邊是點云數(shù)據(jù)，它與坐標無關，看起來像只手，右邊是經(jīng)過拓撲分析后得到的圖像，看起來像“手的骨骼”。

圖2 拓撲分析示例

從左邊到右邊，就完成了拓撲分析“形狀的重構”。右圖用幾個點以及幾條邊就刻畫出了與原數(shù)據(jù)存在“幾分相似”的拓撲圖，而TDA要找的就是這“幾分相似”，因為這“幾分相似”會產(chǎn)生很多有用的信息。

從以上例子可以看出，TDA學習的是數(shù)據(jù)集的整體特征，對小誤差的容忍度很大——即便你的相似度概念在某種程度上存在缺陷，而且它完全不受坐標的限制，在發(fā)生變形時，仍能保持原有的性質，能很好地反映數(shù)據(jù)的形狀。這就是TDA的優(yōu)點-通用性。對于TDA，任何相似性概念都可以拿來使用，但對于ML，你需要一個(或更多)強化的相似性概念，與其他方法一起發(fā)揮作用。

與拓撲密不可分的“流形學習”

提到拓撲，就不得不說“流形學習”。“流形”就是在局部與歐氏空間同胚的空間。換言之，它是局部具有歐氏空間性質的空間，能用歐氏距離來進行距離計算。這給降維方法帶來了很大的啟發(fā)：若低維流形嵌入到高維空間中，則數(shù)據(jù)樣本在高維空間的分布雖然看上去非常復雜，但在局部上仍具有歐氏空間的性質。因此可以容易地局部建立降維映射關系，然后設法將局部映射推廣到全局。如果將維度降到2或3維，就能對數(shù)據(jù)進行可視化展示，因此流形學習也可被用于可視化。

“流形學習”是一類借鑒了拓撲流形概念的降維方法，分為線性的和非線性兩種：

線性的流形學習方法，如我們熟知的主成份分析(PCA)。

非線性的流形學習方法，包括等距映射(Isomap)、拉普拉斯特征映射(Laplacian Eigenmaps，簡稱LE)、局部線性嵌入(Locally-linear Embedding，簡稱LLE)。

本文主要介紹一種比較新的流形學習方法：t-分布鄰域嵌入算法(t-Distributed Stochastic Neighbor Embedding，簡稱t-SNE)。

t-SNE主要基于這樣的思想：如果兩個數(shù)據(jù)點在原始空間中距離較近，但它們的兩個映射點距離較遠，它們就會相互吸引;當它們的兩個映射點距離較，則他們會相互排斥。當達到平衡時得到最后的映射，完成原始高維空間與低維映射空間之間的映射關系。

TDA經(jīng)常與t-SNE算法相結合使用，能達到比較好的效果。下面通過一個TDA與t-SNE處理高維數(shù)據(jù)的案例來說明。

樣本如圖3，為MNIST手寫數(shù)字識別庫，它是美國中學生手寫的數(shù)字數(shù)據(jù)庫，總共有1797張圖片，每張圖片的大小為8*8，展開之后就是64維，每張圖片代表一個樣本點，所以樣本數(shù)據(jù)大小為(1797，64)?？紤]到高維數(shù)據(jù)計算余弦距離最快，我們采用余弦距離表示每個樣本點的相似度。

圖3 MNIST手寫數(shù)字識別庫

圖4 t-SNE與TDA相結合的計算結果

圖5 t-SNE與TDA相結合的計算結果

利用t-SNE與TDA相結合的算法進行計算，結果如圖4和圖5所示。點越大說明該集合所含的樣本點越多，有邊連接的部分說明兩個集合相似度比較高。不同的顏色代表原始高維空間與低維映射空間之間的不同映射關系。

簡單查看結果，可以發(fā)現(xiàn)TDA確實把相似度高的集合連接在了一起，而相似度較低的集合被分開了。從這個例子可以看出，利用TDA做可視化也是一個不錯的選擇。

TDA的應用比較廣泛，Gurjeet Singh的文章[1]中給出了很多有關TDA的應用，例如圖6，第一列和第三列代表3D數(shù)據(jù)，與它們相對應的拓撲圖分別放置在第二列和第四列。它們簡明地向我們解釋著數(shù)據(jù)中隱藏的形狀，從中我們可以得到很多有用信息，這是傳統(tǒng)方法無法識別的。

圖6 TDA可以簡明地解釋數(shù)據(jù)中隱藏的形狀

另外，瀚思在幫助客戶利用TDA對用戶行為進行分析時，發(fā)現(xiàn)它的計算時間也相當快。測試樣本數(shù)據(jù)大小為10w*10w，計算時間約為五分鐘，而且錯誤率僅僅為1.3%。這相比傳統(tǒng)的方法，看起來相當可觀。

總結

TDA是機器學習中一個非常強大的工具，TDA與機器學習方法可以一起使用，得到的效果比使用單個技術更好。更重要的是，它從很大程度上改變了我們分析數(shù)據(jù)的方式，將拓撲這個純數(shù)學領域的學科與數(shù)據(jù)分析相結合，是一個很前沿和大膽的技術。筆者相信未來會有更多基于TDA與機器學習的相關算法被提出，并能夠成功應用到信息安全領域。

來源：極客頭條

收藏分享

聲明：數(shù)據(jù)猿尊重媒體行業(yè)規(guī)范，相關內容都會注明來源與作者；轉載我們原創(chuàng)內容時，也請務必注明“來源：數(shù)據(jù)猿”與作者名稱，否則將會受到數(shù)據(jù)猿追責。