無監督特征選擇的改進稀疏主成分分析算法

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

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

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

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

1 預備知識

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

1.1 符號定義

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

(1)

W的F-范數被定義為

(2)

W的l2,1-范數被定義為

(3)

1.2 主成分分析

PCA是一種數據降維的統計方法,旨在尋求原始高維數據變量的線性組合，從而獲得高維數據的低維表示。PCA可以描述為一個回歸型優化模型[16]，即

(4)

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

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

1.3 稀疏主成分分析

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

(5)

式中，α為非負正則化參數。

1.4 凸稀疏主成分分析

(6)

式中，β為W核范數的正則化參數。

2 改進的稀疏主成分分析算法

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

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

(7)

式中：W′∈d×d為第一階段權重矩陣，w′i表示W′的第i行，λ為的參數。因為該目標函數是凸的，所以利用式(7)對W′求導并令導數等于零，可得

(8)

令

(9)

(10)

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

XD1XTW′+λD2W′=XD1XT

(11)

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

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

(12)

直接計算(XD1XT+λD2)-1復雜度高，為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)

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

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

(14)

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

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

ISPCA算法具體實現步驟如下。

輸出權重矩陣W′，第二階段特征選擇后的數據Z。

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

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

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

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

3 實驗結果與分析

3.1 實驗設置

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

表1 5個數據集的相關特性

3.2 收斂性分析

ISPCA算法的兩階段目標函數均單調遞減，在第一階段是凸優化問題，因此對第二階段的收斂性進行分析。考慮到正則化參數調整范圍的中值為1，將α和β設定為1，不同數據集下ISPCA算法的目標函數值的收斂分析曲線如圖1所示。由圖1可以看出，ISPCA算法的目標函數值隨迭代次數是單調遞減的，并且在所有數據集上均能在15次迭代內快速收斂。

圖1 收斂性曲線

3.3 聚類精度分析

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

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

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

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

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

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

3.4 運算效率分析

當數據特征分別選取20%和40%時，6個算法在最優精度下的運行時間分別如表4和表5所示。

表4 特征選取20%時6種算法最優精度對應的運行時間/s

表5 特征選取40%時6種算法最優精度對應的運行時間/s

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

4 結語

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