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

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

在計算機視覺、數(shù)據(jù)挖掘、模式識別和機器學(xué)習(xí)領(lǐng)域的人臉識別、基因數(shù)據(jù)分析等應(yīng)用中，輸入的數(shù)據(jù)集位于數(shù)千維度的觀測空間中，高的數(shù)據(jù)維數(shù)限制了很多實際應(yīng)用，直接分析高維數(shù)據(jù)不僅計算成本高，處理難度也較大[1-5]。同時，伴隨數(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]。然而，因為由PCA得到的數(shù)據(jù)的新特征是數(shù)據(jù)原特征的線性組合形式，往往缺乏可解釋性。隨后，Zou等[10]提出了稀疏主成分分析算法(Sparse Principal Component Analysis，SPCA)，將PCA表述為一個回歸型的優(yōu)化問題，并引入稀疏正則化項，從而將PCA轉(zhuǎn)變?yōu)橐环N特征選擇方法。SPCA不僅可以用于常規(guī)數(shù)據(jù)分析，還可以被有效地應(yīng)用于基因表達(dá)陣列分析。但是，該算法是非凸的，難以得到全局最優(yōu)解，當(dāng)局部最優(yōu)解不為全局最優(yōu)時，性能很可能會發(fā)生非常顯著的變化。Chang等[11]提出的凸稀疏主成分分析(Convex Sparse Principal Component Analysis，CSPCA)通過在SPCA中引入低秩懲罰項，并用l2,1-范數(shù)取代SPCA損失函數(shù)中的F-范數(shù)，得到了一種新的SPCA算法。CSPCA是一種全局最優(yōu)的算法，在大量數(shù)據(jù)集上的實驗結(jié)果表明，CSPCA具有優(yōu)良的特征選擇性能和對噪聲的魯棒性[12]。但是，CSPCA存在的問題是算法求解涉及矩陣求逆運算，當(dāng)數(shù)據(jù)維數(shù)較高時計算復(fù)雜度較高，運行時間長，限制了CSPCA的應(yīng)用范圍。

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

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個數(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)計方法,旨在尋求原始高維數(shù)據(jù)變量的線性組合，從而獲得高維數(shù)據(jù)的低維表示。PCA可以描述為一個回歸型優(yōu)化模型[16]，即

(4)

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

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

1.3 稀疏主成分分析

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

(5)

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

1.4 凸稀疏主成分分析

(6)

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

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

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

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

(7)

式中：W′∈d×d為第一階段權(quán)重矩陣，w′i表示W(wǎng)′的第i行，λ為的參數(shù)。因為該目標(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)

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

定理若矩陣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算法具體實現(xiàn)步驟如下。

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

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

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

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

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

3 實驗結(jié)果與分析

3.1 實驗設(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個均為維度高的基因表達(dá)數(shù)據(jù)集，在Intel Core i5-1135G7 2.4 GHz CPU 16 GB中Windows 10操作系統(tǒng)上，利用仿真工具M(jìn)atlab 2017b完成實驗。各數(shù)據(jù)集的相關(guān)特性如表1所示。

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

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

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

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

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

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

3.4 運算效率分析

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

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

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

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

4 結(jié)語

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