陳小軍

(貴陽銀行股份有限公司,貴州 貴陽 550081)

0 引言

隨著M2M(Machine to Machine,M2M)、SNS(Social Networking Services,SNS)、移動互聯(lián)網(wǎng)的興起,人工智能(Artificial Intelligence, AI)、 模式識別( Pattern Recognition)、機器學習ML(Machine Learning,ML)、人工神經(jīng)網(wǎng)絡ANN(Artificial Neural Network,ANN 、深度學習(Deep Learning)、數(shù)據(jù)挖掘(Data Mining)、計算機視覺(Computer Vision)等已成為眾多學者的研究熱點。由于原始數(shù)據(jù)經(jīng)常是Web 數(shù)據(jù)、圖像、視頻等半結構化、非結構化的高維數(shù)據(jù),如果直接對原始數(shù)據(jù)進行清洗、分析, 很容易造成維數(shù)災難問題(Dimension Disaster)。 因此需對高維的原始數(shù)據(jù)進行降維。 通過降維,能有效地避免維數(shù)災難問題,提高計算效率、節(jié)省計算資源[1-3]。

現(xiàn)有的經(jīng)典降維算法主要分為線性降維算法和非線性降維算法, 其中線性鑒別算法LDA (Linear Discriminant Analysis, LDA) 與主成分分析 PCA(Principal Component Analysis,PCA)算法是兩種經(jīng)典的線性降維算法[1]。 LDA 算法是對原始數(shù)據(jù)的類別進行降維,屬于有監(jiān)督降維算法,PCA 算法是對原始數(shù)據(jù)的維度直接進行維數(shù)約簡,屬于無監(jiān)督算法。 LDA 算法和PCA 算法需要假設原始數(shù)據(jù)服從高斯分布,降維時存在小樣本SSS(Small Sample Size,SSS)問題以及樣本外(Out of Sample)問題。 非線性降維算法主要是流行學習降維算法、張量降維算法。 本文主要介紹基于流行學習(Manifold Learning)的經(jīng)典降維算法,并進行分析和比較。

1 流行學習概念

流行學習(Manifold Learning)是借鑒了拓撲流行概念的一種降維方法。 流行是位于局部與歐氏空間同胚的空間,高維數(shù)據(jù)樣本雖然在全局空間不具有歐氏空間的性質(zhì),但是在局部空間中仍具有歐氏空間的特點,因此可以在局部歐氏空間建立映射關系,用低維流行嵌入到高維空間中然后再設法將此映射推廣至全局。 邊緣Fisher 算法(Margin Fisher Analysis,MFA)、近鄰鑒別投影NDP(Neighborhood Discriminant Projection,NDP)、NPE 算法(Neighborhood Preserving Embedding,NPE)、LDE(Local Discriminant Embedding,LDE)等算法屬于流行學習算法中較為經(jīng)典的算法。

2 流行學習的主要算法

2.1 邊緣Fisher 分析算法

邊緣 Fisher 分析 MFA 算法(Margin Fisher Analysis,MFA)主要是利用圖嵌(Graph Embedding,GE)方法來構建本征圖和懲罰圖,本征圖是用于描述類內(nèi)數(shù)據(jù)的緊密性,懲罰圖是用于描述類間數(shù)據(jù)的分離性。 本征圖是由每個樣本點的最近同類KNN(KNearest Neighbors,KNN)構成,在KNN 圖中,每個點對應于一個樣本數(shù)據(jù),如果KNN 點是該樣本點的KNN 近鄰點,且屬于同一類別,則兩點之間添加一條邊。 以此方法,遍歷所有樣本點的所有KNN 同類樣本點。 懲罰圖是由每個樣本點的異類KNN 近鄰點構成,懲罰圖中的每個點對應一個樣本數(shù)據(jù),如果KNN 點是該樣本點的所對應的KNN 近鄰點,并且屬于異類,則在懲罰圖中的兩點之間添加一條邊。

2.2 NPE 算法

近鄰保持嵌入NPE (Neighborhood Preserving Embedding,NPE)算法屬于子空間流行學習算法,通過保存數(shù)據(jù)原始流形空間的局部近鄰結構來實現(xiàn),即每個數(shù)據(jù)點都能用其近鄰點線性表示,能較好地解決樣本外(out of sample)的問題。 NPE 算法的主要思想:設定原始數(shù)據(jù)空間中有m個數(shù)據(jù),每個數(shù)據(jù)對應一個節(jié)點,第i個節(jié)點對應原始數(shù)據(jù)空間中的第i個數(shù)據(jù)。 鄰接圖通過KNN 和ε鄰域兩種方法來構建,如果用KNN方法構建鄰接圖,則該鄰接圖是有向圖;如果用ε鄰域方法構建鄰接圖,則該鄰接圖是無向圖。

NPE 算法用KNN 方法構建鄰接圖,每個數(shù)據(jù)用其余KNN 數(shù)據(jù)來表示,該算法的重點是計算KNN 近臨數(shù)據(jù)或節(jié)點之間的權重系數(shù)。 在低維的子流形空間中,通過每個數(shù)據(jù)點的近鄰及其線性相關系數(shù)重構高緯子空間的局部幾何特性。 數(shù)學表達式:

Wij是xi用xj近似線性表示的權重系數(shù)。 為了消除在投影子空間中遠距離的點,加入任意縮放因子:XMXTa=λXXTa,M矩陣是對稱半正定矩陣,約束條件yTy=1,即aTXXTa,其中M=(I-W)T(I-W),I是單位矩陣E,利用SVD 奇異值分解求得最優(yōu)特征向量與特征值,得到由最優(yōu)特征向量構成的投影子空間[4]。 當使用NPE 算法進行降維時,KNN 近鄰中的K以及ε兩個參數(shù),需要根據(jù)模型多次訓練的結果不斷進行調(diào)整。

2.3 NDP 算法

關于類間子流形,構建類間圖G′,使不同類間的投影向量相互遠離。 類間圖G′與類內(nèi)圖G的構圖過程類似,其權重系數(shù)是熱核函數(shù),即wij′=exp(-‖xi-xj‖2/t)。 在類間圖G′中,權重系數(shù)wij′ 說明樣本數(shù)據(jù)的距離情況,如第i個節(jié)點與第j個節(jié)點之間有邊相連,則wij′ =1,反之,則wij′ =0;如果不同類間的數(shù)據(jù)點距離很遠,則wij′ 很小,也可以近似等于0。 數(shù)學表達式:

2.4 LDE 算法

其中v是方程中最大特征值對應的特征向量,嵌入向量zi=VTxi,V=[v1v2…vl][6]。

2.5 DNE 算法

鑒別近鄰嵌入DNE(Discriminant Neighborhood Embedding,DNE)算法根據(jù)類內(nèi)同類數(shù)據(jù)的緊密性以及異類間的分離性,即類內(nèi)數(shù)據(jù)的吸引力和類間數(shù)據(jù)的排斥力構建類內(nèi)圖G,將原始數(shù)據(jù)的潛在低緯流行嵌入其高維數(shù)據(jù)空間中。 假設在原始數(shù)據(jù)中每個點都存在相互作用,兩個數(shù)據(jù)點相互作用會隨著距離增大而變小。 如果一個數(shù)據(jù)點近鄰點都屬于同一類,則該近鄰點是類內(nèi)點;如果其近鄰點全部屬于類間點,則該點稱為奇異點。 奇異點被不同類的數(shù)據(jù)點隔離,只受局部的類間排斥力。 還有一種數(shù)據(jù)點,其近鄰點包括類間點和類內(nèi)點,稱為邊緣點。 邊緣點同時受到類間的排斥力以及類內(nèi)的吸引力。

約束條件PTP=I,I是單位矩陣[7]。

3 流水學習算法分析與比較

3.1 MFA 算法與LDE 算法

MFA 算法具有以下特點:(1)獲得較大的投影向量,其維度值由懲罰圖KNN 中的K值來決定,即所選擇的類內(nèi)、類間KNN 近鄰點最小值所決定;(2)無須假設原始高維數(shù)據(jù)分布情況;(3)類間樣本點的分離性由每個樣本點的KNN 異類樣本點之間歐式距離求和來描述;(4)MFA 算法更具有一般性和廣泛的適用性。 LDE算法和MFA 算法都是用PCA 算法處理小樣本問題SSS問題,但LDE 算法可能會丟失一些重要的鑒別信息[8]。

3.2 NDP 算法與LLE 算法

NDP 算法通過合成類間的近鄰信息以及類內(nèi)的近鄰信息構成類內(nèi)子流形以及類間子流形保存高維原始數(shù)據(jù)空間的近鄰信息,使得樣本數(shù)據(jù)中不同類的投影向量遠離,同類的投影向量相互靠近。 類內(nèi)子流形由樣本內(nèi)用于表征本征近鄰幾何結構的權重系數(shù)重構,其權重系數(shù)由類似LLE 的方法來計算。 類間子流形由樣本數(shù)據(jù)的類間權重系數(shù)構建,其權重系數(shù)根據(jù)拉普拉斯特征映射方法計算。

NDP 算法考慮了類內(nèi)子流形和類間子流形,所到的投影線性子空間不僅保存了類內(nèi)的近鄰幾何結構,也保存了樣本數(shù)據(jù)不同類的投影向量。 LLE 算法是通過歐氏空間的線性表示重構,由于沒有考慮原始數(shù)據(jù)的類別信息,因此會丟失數(shù)據(jù)的類別信息。

3.3 LDE 算法和LPP 算法

LPP 算法保存局部的近鄰距離信息,不僅對于訓練樣本數(shù)據(jù)有效,對于新的樣本數(shù)據(jù)也有一定的效果,解決了很多非線性降維算法存在的樣本外(out of sample)問題,但是沒有利用類別標簽信息,不利于降維分類。 LDE 算法在構建鄰接圖時,充分地利用了類別信息,構建了類內(nèi)鄰接圖以及類間鄰接圖,從而在低維子空間中,利用KNN 近鄰類別信息進行分類,但LDE算法忽略了將會對LDE 算法總的代價函數(shù)產(chǎn)生影響的相距較遠的數(shù)據(jù)點,從而降低分類性能。

當訓練樣本的數(shù)量小于樣本維度時,LDE 算法和LPP 算法都存在有奇異矩陣的問題。

4 結語

文中所述的降維算法,在其投影子空間中,求最優(yōu)特征值以及特征向量的時間開銷較大,學者在研究上述算法過程中,對其進行拓展,在原始算法思想的基礎上,引入核函數(shù)或張量,將其升維,常用的核函數(shù)有線性核函數(shù)、高斯核函數(shù)、拉普拉斯核函數(shù)、高斯核函數(shù)等,本文對其衍生的核函數(shù)化或張量化后的算法沒有涉及。

本文詳細介紹了流行學習中的經(jīng)典算法,并對其優(yōu)劣進行了比較,同時指出各算法在降維應用時所需的假設條件以及存在的問題,如小樣本問題也即奇異值問題,樣本外問題等。 目前基于流行學習的降維、分類算法仍在研究中,但有幾個問題值得學者關注和研究:(1)在降維過程中,采用KNN 或ε領域方法來構建鄰域時,參數(shù)怎么確定;(2)流行學習算法大多為局部方法,如何提高算法的以及算法的魯棒性。