數據流形邊界及其分布條件的增量式降維算法

趙光華，楊燾,2，付冬梅,2

（1.北京科技大學 自動化學院, 北京 100083; 2.北京科技大學 順德創新學院, 廣東 佛山 528300）

近年來，流形學習在模式識別和機器學習中的應用越來越常見，如人臉識別[1]、文本檢索[2]、故障檢測[3]、以及隱私保護[4]等。流形學習是在流形假設的前提下，挖掘出高維數據的低維流形從而解決“維度災難”問題[5]。經典流形學習算法有主成分分析(principal component analysis, PCA)[6]、等度量映射(isometric mapping, ISOMAP)[7]、局部線性嵌入(locally linear embedding, LLE)[8]、拉普拉斯特征映射(Laplacian eigenmaps, LE)[9]、局部切空間對齊(local tangent space alignment, LTSA)[10]等。在現代流形學習算法中，t-分布隨機近鄰嵌入(t-distributed stochastic neighbor embedding, t-SNE)[11]和一致的流形近似和投影(uniform manifold approximation and projection, UMAP)[12]將高維數據的拓撲結構進行低維映射以獲得低維嵌入。此外，類似于變分自動編碼器(variational suto-rncoder,VAE)[13]和生成對抗網絡(generative sdversarial networks, GAN)[14]的深度生成模型，同樣能有效地描述高維數據的低維特征，因此，深度生成模型也被證實具有良好的降維性能。然而，上述算法都是離線式的批量流形學習算法，無法適用于在線式的數據增量式學習問題。

為了改進批量流形學習算法的不足，增量式流形學習作為一種新興的維數約簡技術而出現，其思想是在實時地獲得新數據后，通過構建與原數據的鄰域關系，提取新數據的低維特征。目前，增量式流形學習算法可以歸納為兩類。第一類是對新數據進行流形降維的同時，對原數據的低維表示進行同步更新，如Li 等[15]將增量降維問題轉化為矩陣的增量特征值計算問題，Bucak等[16]通過采用增量式非負矩陣分解理論，獲得高維數據的低維坐標，其本質仍是批量式學習。第二類是處理新數據時，不更新原數據的低維表示，如Zhao 等[17]基于字典學習提出了一種增量式降維算法，其實質是利用局部重構機制獲得新數據的低維坐標。

雖然對增量式流形學習的研究已取得了一定進展，但是仍存在兩個關鍵問題。一是當新數據分布于原數據所形成的流形形態之外時，即位于原流形形態的延伸結構上；二是數據受噪聲干擾。以上兩點均對增量式流形降維造成困難。針對上述問題，本文提出了一種新的增量式流形降維算法。該算法首先分析噪聲概率分布，同時對數據進行降噪處理，確定降噪數據的流形形態為主流形，并在主流形上表征出噪聲的分布形式，以此獲得近似的原數據流形邊界，然后基于流形邊界判別新數據的分布狀態。當新數據分布于原流形形態的延伸結構上時，根據新數據的局部空間位置構造映射函數，將新數據映射至低維空間；否則，通過構建與原數據的鄰域關系，在低維空間對新數據進行加權重構，以此學習新數據的低維坐標。

本文貢獻主要有以下兩點：

1) 提出一種分布狀態判別策略，根據新數據和流形邊界的分布關系，判別新數據的分布狀態；

2) 提出一種增量式降維算法，將不同分布狀態的新數據分別映射至低維空間，揭示與原數據的低維本質特征，同時加入降噪流程，抑制噪聲干擾。

1 IDR-DMBDS 的流程及原理

如圖1 所示，本文提出的算法分為3 個階段，包括：1）流形邊界提取：所提取的流形邊界以概率化表達方法描述數據；2）分布狀態判別：判別新數據的分布狀態；3）增量式流形降維：將不同分布狀態下的新數據分別映射至低維空間。

圖1 IDR-DMBDS 算法框架Fig.1 Frame of the IDR-DMBDS

1.1 流形邊界提取

假設在有限D維流形上，含噪數據表示為X={xi|i=1,2,···,N},xi∈RD。對原數據的流形邊界提取主要分為2 個步驟。

1.1.1 降噪

為減少噪聲干擾，采用相空間重構的投影算法，將高維歐式空間劃分為局部流形空間和局部流形切空間，并將局部流形切空間之中的含噪數據投影至主流形，從而達到降噪的目的，流程為：

1）擬合主流形。

在流形學習理論中，若干具有線性結構的局部流形被拼接成分段線性流形，于是我們合理地將局部流形近似為超平面H，然后通過擬合超平面來獲得主流形。為擬合超平面，首先借用k-近鄰算法獲得含噪數據xi的近鄰點Ni={xij|j=1,2,···,k},。然后，最小化重建距離保證近鄰點至超平面H的距離之和最小，即

式中d(xij,H)表 示xij至H的歐氏距離。

2）投影降噪過程。

擬合好超平面H之后，計算H的法線方向并將其表示為S。然后，計算xi沿法線方向S至超平面的歐氏距離，并表示為d(xi,H)。最后，將含噪數據xi沿著法線方向S投影至超平面H從而達到降噪的目的。將該過程表示為

1.1.2 提取流形邊界

如圖2 所示，為了能更直觀地描述噪聲對不同流形空間位置的損傷程度，本文使用Parzen窗模型[18]對噪聲進行概率分析，以此確定噪聲在不同位置的均值μ和標準差 σ，并在主流形上表征出噪聲的分布形式，以此獲得近似的原數據流形邊界[19]。

圖2 流形邊界提取過程Fig.2 Process of extracting manifold boundary

1.1.3 原數據的流形降維

增量式流形學習同樣需要原數據的低維特征，本文使用UMAP 算法對原數據進行降維，其核心是利用圖布局算法，將構建在高維空間的加權k-近鄰圖映射至低維空間，在低維空間挖掘出與其最相似的圖。具體流程為：

1）圖構造(graph construction)。在高維空間構建加權k-近 鄰圖G=(V,E,w)， 其中V表示圖中對應于原數據X的節點集合，E={(xi,xij)|1 ≤i≤N, 1 ≤j≤k}表示圖中的邊集合，并定義連接xi與它近鄰點Ni={xij|j=1,2,···,k}邊 的權重wij為

式中：d(xi,xij)表 示xi和xij的 歐氏 距 離， ρi和 σi為兩個超參數：

2）圖布局(graph layout)。定義目標函數：

其 中wh(·)和wl(·)分 別 表 示 在 高 維 和 低 維 空 間 之 中的邊的權重集合。為了能在降維后盡可能保留原k-近鄰圖蘊含的數據特征，利用梯度下降法最小化式（6），以此獲得原數據的低維表示，記為Y={yi|i=1,2,···,N},yi∈Rd。

1.2 分布狀態判別

假設新數據表示為Xnew={xniew|i=1,2,···,T},xniew∈RD。通常，新數據和原數據具有獨立同分布特性，新數據可能分布于原數據所形成的流形形態上，也可能分布于原流形形態的延伸結構上。因此，對新數據進行增量式流形降維前，需要先判別新數據的分布狀態。

為了有效判別新數據的分布狀態，本文基于流形邊界進行新數據的離群點檢測。為避免因遍歷所有新數據帶來的計算量問題，利用k-means算法對新數據Xnew進行聚類，得到t個聚類中心點Xc={xci|i=1,2,···,t},xci∈RD作為新數據的代表點。離群點檢測采用局部異常因子檢測算法(local outlier hactor,LOF)[20]，通過量化聚類中心點與流形邊界的密度差異進行離群點檢測，并通過局部離群因子系數 Score(·) 表 征密度差異大小， Score(xci)為1 的聚類中心點將被識別為離群點。

當聚類中心點被判別為離群點時，說明新數據分布于原流形形態的延伸結構上。

1.3 增量流形降維

對于分布于原流形形態之上的新數據，需保持降維前后表征數據距離的權值大小，而當新數據分布于原流形形態的延伸結構上時，則期望能夠保持兩者共同形成的全局低維流形結構不變。對新數據的增量流形降維的流程如下。

當新數據分布于原流形形態上時：首先，在原數據X中尋找新數據xniew的近鄰點Ni={xij|j=1,2,···,k}，Ni的低維表示為Yi。然后，根據式（3）計算xniew與Ni的權重wij。最后，假設在高維歐式空間中，xniew由Ni中的數據加權構成，并且xniew的低維表示與Yi同樣保持這種權重關系。于是新數據的低維表示為

當新數據分布于原流形形態的延伸結構上時：首先，在原數據X中尋找新數據的近鄰點Ni={xi j|j=1,2,···,k}，Ni的低維表示為Yi。然后，設線性映射函數F(·):RD→Rd，該函數將Ni從高維空間線性映射至低維空間，且得到的低維表示F(Ni) 與Yi差異最小，于是定義損失函數

將映射函數 F(·) 寫為映射矩陣B，損失函數的矩陣形式為

對式（9）進行最小化可得

最后，將新數據映射至低維空間，其低維表示為

本文所提算法的流程如下。

1.4 計算復雜度分析

本算法將原數據X={xi|i=1,2,···,N},xi∈RD和新數據Xnew={xniew|i=1,2,···,T},xniew∈RD降 至d維包含5 個步驟，其各自的計算復雜度以及總的計算復雜度分析如下。

降噪：k-近鄰搜索的平均計算成本為O(Dlog(k)·Nlog(N)) ，其中，k為近鄰數。超平面擬合的計算成本為O(ND3)。含噪數據的投影過程的計算成本為O(N)；流形邊界提取：流形邊界提取的計算成本為O(N)；原數據的流形降維：原數據借用UMAP算法進行降維，其計算成本為O(N1.14)；分布狀態判別：利用k-means 算法獲取新數據t個聚類中心點的計算復雜度為O(TDt)，利用局部異常檢測算法進行分布狀態判別的計算復雜度為O(2Nt)；增量流形降維：獲取新增數據的低維坐標的計算復雜度為O(Tk3)。

綜上所述，本算法的總計算復雜度為O(Dlog(k)·Nlog(N))+O(ND3)+2O(N)+O(N1.14)+O(TDt)+O(Tk3)。

2 實驗結果與分析

2.1 實驗設置

1）數據集說明。

為評估所提出算法的性能，我們選擇兩組具有可視化效果的合成數據集、一組文本數據集以及三組多類分圖像數據集進行算法實現，數據集包括：

瑞士卷和“S”型數據集為服從流形結構的三維合成數據集；

MR 數據集包含5 000 條電影評論，涉及正面/負面評論。

MNIST 數據集是美國國家標準與技術研究院收集整理的大型手寫數字數據庫。其含有60 000個訓練樣本和10 000 個測試樣本，包含了0～9 共10 類手寫數字圖片，圖像都做了尺寸歸一化，為28 像素×28 像素大小的灰度圖；

FASHION-MNIST 數據集由Zalando 旗下的研究部門提供。其含有60 000 個訓練樣本和10 000個測試樣本，涵蓋了來自10 種類別商品的正面圖片，圖像都為28 像素×28 像素大小的灰度圖；

DSPRITES 數據集是由6 個不相關因素按程序產生的2D 形狀（心形、橢圓形和方形）圖像數據集，這些因素包括顏色、形狀、比例、方向、X坐標位置和Y坐標位置，圖像大小都為64 像素×64 像素。

本文實驗所用數據的信息描述如表1 所示。

表1 實驗數據信息描述Table 1 Description of the experimental data

2）對照算法說明。

本文實驗選取4 種降維算法作為對照算法。

ISOMAP：通過保持降維前后樣本之間的“測地線”距離不變，挖掘出嵌入在高維空間的低維流形。加入增量新數據后，通過保持新增數據和原數據的測地距離來實現增量降維；

LLE：一種非線性降維算法，通過保持數據的局部線性結構來提取低維流形。加入增量新數據后，通過更新代價矩陣實現增量降維；

PCA：一種線性降維算法，依據樣本在空間中的位置分布，保持樣本點在多維空間中的最大方差并獲得投影方向，實現維數約簡。加入增量新數據后，重新計算均值向量并進行奇異值分解，更新特征值和特征向量實現增量降維；

UMAP：基于黎曼幾何和代數拓撲的理論框架，將高維數據的拓撲結構進行低維映射以達到降維目的。本文通過局部加權重構算法實現對增量新數據的增量降維。

3）評估指標說明。

對于合成數據集，對實驗結果進行可視化，以直觀地展示算法流程以及降維性能。對于圖像數據集，由于數據集為多類分數據集，使用高斯混合模型作為分類器對降維后的新數據進行分類，并將分類準確率作為評估指標，計算形式如下：

4）涉及算法的參數設置。

k-近鄰算法：近鄰點個數設置為15；k-means算法：聚類數設置為20；LOF 算法：近鄰點個數設置為15，異常值比例設置為0.05；ISOMAP：該算法的近鄰點個數設置為15；LLE：近鄰點個數設置為15；UMAP：近鄰點個數設置為15，低維空間中點之間的最小距離設置為0.2；高斯混合模型：在3 個圖像數據集的實驗中，生成的聚類數分別設置為3、10、10。

2.2 合成數據集的實驗結果分析

本節在2 個合成數據集上評估所提算法的性能，圖3 對加入噪聲的新數據和原數據進行可視化展示，圖3(a)和圖3(b)中的新數據分布于原流形形態之上，圖3(c)和圖3(d)中的新數據分布于原流形形態的延伸結構上。

圖3 數據集的可視化展示Fig.3 Visual display of the datasets

首先，對原數據進行投影降噪并獲得流形邊界，同時使用UMAP 算法將降噪數據降至2 維。然后，對新數據進行k-means 聚類，得到新數據的聚類中心點，圖4 為聚類中心點與流形邊界的分布關系，并基于流形邊界判別新數據的分布狀態。最后，根據判別結果，利用式（7）和式（11）對新數據進行降維，圖5 對降維后的新數據和原數據進行可視化展示。

圖4 聚類中心點與流形邊界的分布關系Fig.4 Distribution relationship between cluster centers and manifold boundary

圖5 新數據和原數據的低維特征Fig.5 Low-dimensional features of the new and original data

由圖4 可知：當新數據分布于原流形形態上時，提取的流形邊界能將聚類中心點包含進來，使用LOF 算法對聚類中心點進行離群點檢測，其都被判別為正常值。當新數據分布于原流形形態的延伸結構上時，聚類中心點分布于流形邊界之外，因與周圍的流形邊界有較為明顯的密度差異而被判別為離群點。

由圖5 可知：當新數據分布于原流形形態上時，對新數據進行降維后，其形態結構與原數據的保持一致，并且數據之間的權值關系也得以保留。當新數據分布于原流形形態的延伸結構上時，新數據降維之后的形態結構同樣是對原數據的結構延伸，從而能夠保持新數據和原數據的全局流形結構不變。

2.3 文本數據集的實驗結果分析

本節在MR 數據集上評估所提算法的降維性能。本實驗首先統計不同文本之間，兩詞在所有文本中相鄰的次數，通過共現矩陣用于發現主題，解決詞向量相近關系的表示[21]，然后使用本文算法將共現矩陣的行向量降至300 維獲得詞向量，最后使用Text CNN 模型[22]進行文本分類，并將分類準確率與文獻[22]中的結果進行對比(文獻[22]使用公開可用的word2vec 詞向量)，對比結果如圖6 所示。

圖6 MR 數據集的分類準確率Fig.6 Classification accuracy of the MR dataset

由圖6 可知，本文算法在降維后能夠保留更多的分類特征，在使用Text CNN 模型進行分類后，具有更高的分類準確率。

2.4 圖像數據集的實驗結果分析

在3 個圖像數據集上來評估所提算法的性能，圖7 給出了3 個數據集的部分圖像示例。實驗流程與合成數據集相同，用所提算法以及4 種對照算法將數據降至3、5、10、80 和200 維，圖8對算法獲取的3 維低維特征進行可視化。然后使用高斯混合模型對不同維度的低維表示進行分類，計算分類準確率。并將包括本文算法在內的5 種不同算法的實驗結果進行對比，圖9 給出對比結果。

圖7 數據集的圖像示例Fig.7 Examples of images in the datasets

圖9 5 種算法在數據集的分類準確率Fig.9 Classification accuracy of five algorithms for the datasets

由圖8 可知：與原數據相同類別的新數據，在降維后數據分布呈現類內聚斂的特性，而與原數據不同類別的新數據，在降維后呈現類間分離的特性，從而體現出較大的類別區分度。因此，在多類分含噪圖像數據集上，本文提出的算法表現出較好的分類性能。

由圖9 可知：由于加入了投影降噪這一流程，相較于其他算法，本文算法在3 個數據集上都取得了評估指標的最優值，尤其在MNIST 數據集上，各個維度上的分類準確率均高于其他算法10%以上。另外，隨著維度升高，LLE 算法的分類準確率呈現逐漸降低的趨勢，而本文的算法未出現這種問題。綜上所述，在面對多類分含噪圖像數據集時，本文算法具有更好的抗噪能力。

3 結束語

本文針對含噪數據的增量式降維問題，提出一種新的流形降維算法。該算法引入投影降噪理論，將含噪數據投影至主流形，從而抑制噪聲干擾；同時，基于流形邊界判斷新數據的分布狀態，將不同分布狀態下的新數據分別映射至低維空間，進而揭示與原數據的低維本質特征。實驗表明，相較于其他流形降維算法，該算法能夠適用于在線的增量式降維問題處理，同時表現出更好的分類性能和抗噪能力。另外，無論新數據分布于原流形形態之上或者是延伸結構之上，該算法都能揭示新數據和原數據共同蘊含的低維特征。進一步的研究將應用本文算法解決實際工程問題。