基于流行學(xué)習(xí)的降維算法研究

陳小軍

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

0 引言

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

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

1 流行學(xué)習(xí)概念

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

2 流行學(xué)習(xí)的主要算法

2.1 邊緣Fisher 分析算法

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

2.2 NPE 算法

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

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

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

2.3 NDP 算法

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

2.4 LDE 算法

其中v是方程中最大特征值對(duì)應(yīng)的特征向量,嵌入向量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ù)的排斥力構(gòu)建類內(nèi)圖G,將原始數(shù)據(jù)的潛在低緯流行嵌入其高維數(shù)據(jù)空間中。 假設(shè)在原始數(shù)據(jù)中每個(gè)點(diǎn)都存在相互作用,兩個(gè)數(shù)據(jù)點(diǎn)相互作用會(huì)隨著距離增大而變小。 如果一個(gè)數(shù)據(jù)點(diǎn)近鄰點(diǎn)都屬于同一類,則該近鄰點(diǎn)是類內(nèi)點(diǎn);如果其近鄰點(diǎn)全部屬于類間點(diǎn),則該點(diǎn)稱為奇異點(diǎn)。 奇異點(diǎn)被不同類的數(shù)據(jù)點(diǎn)隔離,只受局部的類間排斥力。 還有一種數(shù)據(jù)點(diǎn),其近鄰點(diǎn)包括類間點(diǎn)和類內(nèi)點(diǎn),稱為邊緣點(diǎn)。 邊緣點(diǎn)同時(shí)受到類間的排斥力以及類內(nèi)的吸引力。

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

3 流水學(xué)習(xí)算法分析與比較

3.1 MFA 算法與LDE 算法

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

3.2 NDP 算法與LLE 算法

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

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

3.3 LDE 算法和LPP 算法

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

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

4 結(jié)語

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

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