無監(jiān)督特征選擇的改進(jìn)稀疏主成分分析算法

范九倫，李維昊，羅緒瑞，支曉斌

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

在計(jì)算機(jī)視覺、數(shù)據(jù)挖掘、模式識別和機(jī)器學(xué)習(xí)領(lǐng)域的人臉識別、基因數(shù)據(jù)分析等應(yīng)用中，輸入的數(shù)據(jù)集位于數(shù)千維度的觀測空間中，高的數(shù)據(jù)維數(shù)限制了很多實(shí)際應(yīng)用，直接分析高維數(shù)據(jù)不僅計(jì)算成本高，處理難度也較大[1-5]。同時(shí)，伴隨數(shù)據(jù)維數(shù)增高，原數(shù)據(jù)中噪聲數(shù)據(jù)可能會顯著增加，導(dǎo)致對數(shù)據(jù)分析的結(jié)果出現(xiàn)偏差。因此，高效處理高維數(shù)據(jù)已成為亟需解決的問題。大量研究表明，降維是高維數(shù)據(jù)分析和處理的重要途徑之一。20世紀(jì)80年代Svante 首次提出主成分分析[6](Principal Component Analysis,PCA)，并將其用于數(shù)據(jù)降維。PCA作為非常流行的無監(jiān)督數(shù)據(jù)處理與降維方法，其主要思想是將n維數(shù)據(jù)特征映射到k維上(n>>k)，尋求原始高維數(shù)據(jù)特征的線性組合，從而獲得高維數(shù)據(jù)的有效低維表示[7-9]。然而，因?yàn)橛蒔CA得到的數(shù)據(jù)的新特征是數(shù)據(jù)原特征的線性組合形式，往往缺乏可解釋性。隨后，Zou等[10]提出了稀疏主成分分析算法(Sparse Principal Component Analysis，SPCA)，將PCA表述為一個(gè)回歸型的優(yōu)化問題，并引入稀疏正則化項(xiàng)，從而將PCA轉(zhuǎn)變?yōu)橐环N特征選擇方法。SPCA不僅可以用于常規(guī)數(shù)據(jù)分析，還可以被有效地應(yīng)用于基因表達(dá)陣列分析。但是，該算法是非凸的，難以得到全局最優(yōu)解，當(dāng)局部最優(yōu)解不為全局最優(yōu)時(shí)，性能很可能會發(fā)生非常顯著的變化。Chang等[11]提出的凸稀疏主成分分析(Convex Sparse Principal Component Analysis，CSPCA)通過在SPCA中引入低秩懲罰項(xiàng)，并用l2,1-范數(shù)取代SPCA損失函數(shù)中的F-范數(shù)，得到了一種新的SPCA算法。CSPCA是一種全局最優(yōu)的算法，在大量數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，CSPCA具有優(yōu)良的特征選擇性能和對噪聲的魯棒性[12]。但是，CSPCA存在的問題是算法求解涉及矩陣求逆運(yùn)算，當(dāng)數(shù)據(jù)維數(shù)較高時(shí)計(jì)算復(fù)雜度較高，運(yùn)行時(shí)間長，限制了CSPCA的應(yīng)用范圍。

針對CSPCA存在的上述問題，擬提出一種改進(jìn)SPCA(Improved Sparse Principal Component Analysis,ISPCA)算法。該算法首先分別由第一階段不加低秩懲罰項(xiàng)的SPCA和第二階段執(zhí)行帶低秩懲罰項(xiàng)的SPCA依次對數(shù)據(jù)進(jìn)行降維處理，然后在第一階段利用矩陣的廣義逆引理降低算法復(fù)雜度，從而提高整個(gè)算法的運(yùn)算效率。

1 預(yù)備知識

為了方便表述，下面介紹使用的符號和規(guī)范定義，以及簡要回顧經(jīng)典主成分分析[13]、稀疏主成分分析[14]和凸稀疏主成分分析[15]的主要相關(guān)工作。

1.1 符號定義

設(shè)X=[x1,x2,…,xn]∈d×n為原數(shù)據(jù)矩陣，xi∈n(1≤i≤n)是第i個(gè)數(shù)據(jù)，d為行數(shù)，n為樣本總數(shù)，XT表示X轉(zhuǎn)置。W表示X的回歸投影矩陣，對于矩陣W∈m×n，wi和wj分別代表W的第i行和第j列元素矩陣。Tr(W)表示矩陣W的跡，W的核范數(shù)被定義為

(1)

W的F-范數(shù)被定義為

(2)

W的l2,1-范數(shù)被定義為

(3)

1.2 主成分分析

PCA是一種數(shù)據(jù)降維的統(tǒng)計(jì)方法,旨在尋求原始高維數(shù)據(jù)變量的線性組合，從而獲得高維數(shù)據(jù)的低維表示。PCA可以描述為一個(gè)回歸型優(yōu)化模型[16]，即

(4)

式中，r為矩陣W的秩，r(W)=k即矩陣W的秩數(shù)為k。

PCA是用最小二乘法求解，對噪聲極其敏感。當(dāng)數(shù)據(jù)含有噪聲時(shí)，PCA投影方向偏離所期望的最優(yōu)解。此外，PCA降低數(shù)據(jù)維數(shù)的同時(shí)，特征可能會發(fā)生變化，因此，其不能用于特征選擇。

1.3 稀疏主成分分析

矩陣的l2,1-范數(shù)被證明能夠使矩陣組稀疏化。因此，SPCA可描述為如下優(yōu)化模型[16]

(5)

式中，α為非負(fù)正則化參數(shù)。

1.4 凸稀疏主成分分析

(6)

式中，β為W核范數(shù)的正則化參數(shù)。

2 改進(jìn)的稀疏主成分分析算法

鑒于造成CSPCA計(jì)算復(fù)雜度高的原因主要是原子范數(shù)懲罰項(xiàng)的優(yōu)化計(jì)算，因此ISPCA算法分為兩階段：第一階段只用魯棒的SPCA對數(shù)據(jù)進(jìn)行無監(jiān)督特征選擇，以降低數(shù)據(jù)的維數(shù)，采用矩陣的廣義逆引理降低運(yùn)算復(fù)雜度；第二階段對降維數(shù)據(jù)采用完整的CSPCA再進(jìn)行一次特征選擇，從而最終實(shí)現(xiàn)對原數(shù)據(jù)的特征選擇。

ISPCA算法第一階段可以描述為如下的最小化問題

(7)

式中：W′∈d×d為第一階段權(quán)重矩陣，w′i表示W(wǎng)′的第i行，λ為的參數(shù)。因?yàn)樵撃繕?biāo)函數(shù)是凸的，所以利用式(7)對W′求導(dǎo)并令導(dǎo)數(shù)等于零，可得

(8)

令

(9)

(10)

考慮到D1∈n×n和D2∈d×d均為對角矩陣,因此式(8)的矩陣形式可表示為

XD1XTW′+λD2W′=XD1XT

(11)

簡化式(11)可得唯一的最優(yōu)W′為

W′=(XD1XT+λD2)-1(XD1XT)

(12)

直接計(jì)算(XD1XT+λD2)-1復(fù)雜度高，為O(d3)，因此為了提高計(jì)算效率，利用矩陣的廣義逆引理對其求解。

定理若矩陣A∈n×n為非奇異矩陣，B∈n×p，C∈p×n，則有[18]

(A+BC)-1=
A-1-A-1B(I+CA-1B)-1CA-1

(13)

根據(jù)式(13)，令A(yù)=λD2，B=XD1，C=XT，可得出W′新的求解形式為

W′=(λD2)-1-(λD2)-1XD1·
[I+XT(λD2)-1XD1]XT(λD2)-1

(14)

式(14)求解W′的矩陣規(guī)模小于式(12)，因此將式(14)所求的W′對原數(shù)據(jù)進(jìn)行一次特征選擇，得到新的降維數(shù)據(jù)Y。

在ISPCA算法第二階段，采用CSPCA算法，利用式(6)對第一階段得到的降維數(shù)據(jù)Y再進(jìn)行一次特征選擇，得到最終特征選擇后的數(shù)據(jù)Z。

ISPCA算法具體實(shí)現(xiàn)步驟如下。

輸出權(quán)重矩陣W′，第二階段特征選擇后的數(shù)據(jù)Z。

步驟1隨機(jī)初始化第一階段權(quán)重矩陣W′∈d×d。

步驟2利用式(9)和式(10)分別計(jì)算對角矩陣D1和D2。

步驟3將所求D1和D2代入式(14)求W′，得到第一次降維后的數(shù)據(jù)矩陣Y。

步驟4將數(shù)據(jù)Y代入式(6)，利用CSPCA再進(jìn)行一次特征選擇，得到最終特征選擇后的數(shù)據(jù)Z。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

選取人類肺癌[19](the human lung carcinomas,LUNG)、惡性神經(jīng)膠質(zhì)瘤[19](the malignant glioma，GLIOMA)、ALL/AML白血病數(shù)據(jù)[19](ALL/AML Leukemia，ALLAML)、結(jié)腸腫瘤[19](Colon Tumor，COLON)和前列腺癌基因表達(dá)[19-20](Prostate Cancer gene expression，PRO-GE) 等5個(gè)均為維度高的基因表達(dá)數(shù)據(jù)集，在Intel Core i5-1135G7 2.4 GHz CPU 16 GB中Windows 10操作系統(tǒng)上，利用仿真工具M(jìn)atlab 2017b完成實(shí)驗(yàn)。各數(shù)據(jù)集的相關(guān)特性如表1所示。

表1 5個(gè)數(shù)據(jù)集的相關(guān)特性

3.2 收斂性分析

ISPCA算法的兩階段目標(biāo)函數(shù)均單調(diào)遞減，在第一階段是凸優(yōu)化問題，因此對第二階段的收斂性進(jìn)行分析?？紤]到正則化參數(shù)調(diào)整范圍的中值為1，將α和β設(shè)定為1，不同數(shù)據(jù)集下ISPCA算法的目標(biāo)函數(shù)值的收斂分析曲線如圖1所示。由圖1可以看出，ISPCA算法的目標(biāo)函數(shù)值隨迭代次數(shù)是單調(diào)遞減的，并且在所有數(shù)據(jù)集上均能在15次迭代內(nèi)快速收斂。

圖1 收斂性曲線

3.3 聚類精度分析

ISPCA是無監(jiān)督特征選擇算法，為了驗(yàn)證ISPCA算法的有效性，分別將ISPCA算法與CSPCA、無監(jiān)督判別特征選擇[21](Unsupervised Discriminative Feature Selection，UDFS)、多集群特征選擇[22](Multi-Cluster Feature Selection，MCFS)、高斯拉普拉斯算法[22](Laplacian of Gaussian Algorithm，LGA)和具有多子空間隨機(jī)化和協(xié)作的無監(jiān)督特征選擇[23](Unsupervised Feature Selection with Multi-Subspace Randomization and Collaboration，SRCFS)等無監(jiān)督特征選擇算法進(jìn)行對比。利用K-means聚類算法對特征選擇后得到的數(shù)據(jù)進(jìn)行聚類，將聚類精度作為特征選擇算法性能評價(jià)的指標(biāo)。實(shí)驗(yàn)中對每組數(shù)據(jù)設(shè)置隨機(jī)重復(fù)聚類30次，并選其最佳聚類精度作為最終聚類精度。

實(shí)驗(yàn)中所有算法參數(shù)都將在集合{10-6,10-4,10-2,1,102,104,106}中選擇，分別對表1中的數(shù)據(jù)集進(jìn)行20%和40%的特征選擇。當(dāng)選擇20%特征時(shí)，6種算法在5個(gè)數(shù)據(jù)集上的最優(yōu)聚類精度如表2所示。ISPCA算法在第一階段選擇80%，第二階段選擇25%的特征，保證最終選擇的特征范圍為20%。

表2 特征選取20%時(shí)6種算法的最優(yōu)聚類精度/%

當(dāng)選擇40%特征時(shí)，6種算法在5個(gè)數(shù)據(jù)集上的最優(yōu)聚類精度對比如表3所示。ISPCA算法在第一階段選擇80%，第二階段選擇50%特征,保證最終選擇特征為40%。

表3 特征選取40%時(shí)6種算法的最優(yōu)聚類精度/%

由表2及表3可知，當(dāng)特征選擇范圍為20%和40%時(shí)，ISPCA相較于CSPCA算法，聚類精度都有不同程度提升，并且在6種算法中聚類精度結(jié)果最優(yōu)。

3.4 運(yùn)算效率分析

當(dāng)數(shù)據(jù)特征分別選取20%和40%時(shí)，6個(gè)算法在最優(yōu)精度下的運(yùn)行時(shí)間分別如表4和表5所示。

表4 特征選取20%時(shí)6種算法最優(yōu)精度對應(yīng)的運(yùn)行時(shí)間/s

表5 特征選取40%時(shí)6種算法最優(yōu)精度對應(yīng)的運(yùn)行時(shí)間/s

由表4和表5可知，特征選擇范圍為20%和40%時(shí)，ISPCA算法相較于CSPCA算法而言，總體計(jì)算運(yùn)行時(shí)間減少，并且當(dāng)特征選擇范圍為40%時(shí)，ISPCA的運(yùn)行時(shí)間整體少于UDFS及MCFS算法。在特征選擇范圍為20%時(shí)，ISPCA在COLON和PRO-GE數(shù)據(jù)集的運(yùn)行時(shí)間少于UDFS及MCFS算法，即ISPCA的運(yùn)行復(fù)雜度低于UDFS及MCFS算法。

4 結(jié)語

將改進(jìn)的稀疏主成分分析法ISPCA應(yīng)用于無監(jiān)督特征選擇中，分別在第一階段引入矩陣廣義逆引理和第二階段采用低秩懲罰項(xiàng)的稀疏主成分分析對數(shù)據(jù)進(jìn)行降維處理，從而降低算法的復(fù)雜度。在5個(gè)真實(shí)數(shù)據(jù)集上的對比性實(shí)驗(yàn)結(jié)果表明，ISPCA算法不僅在聚類精度優(yōu)于CSPCA算法，而且在運(yùn)行速度上表現(xiàn)更優(yōu)。