李 霞，劉向陽

(河海大學 理學院，江蘇 南京 210098 )

基于逆冪法的組合稀疏約束主成分分析

李 霞，劉向陽

(河海大學 理學院，江蘇 南京 210098 )

討論了在標準主成分分析的基礎上增加L0罰，L1罰和L2罰約束條件，使主成分變得更加稀疏，以便于解釋實際問題，運用逆冪法給出了求解目標函數(shù)的迭代算法.數(shù)據(jù)模擬實驗展示了此算法在主成分的稀疏程度和累積貢獻率上都取得了很好的效果.

主成分分析； 稀疏主成分分析； 逆冪法； 非線性特征提取

主成分分析(Principal Component Analysis, PCA)[1]廣泛應用在數(shù)據(jù)降維和數(shù)據(jù)處理方面，其應用包括手寫數(shù)字識別和人臉識別等.盡管經(jīng)典的主成分分析算法有許多優(yōu)點，但是在實際應用中主成分分析卻存在著一些不足，主要表現(xiàn)在主成分依賴于所有的原始變量，很難給出其實際解釋，有時需要對主成分進行分析和解釋時，無法解釋每一個主成分對應的特征是什么.稀疏主成分分析就是為了解決此問題而引進的一個算法，會把主成分系數(shù)變的稀疏，即把大多數(shù)系數(shù)都變成零.通過此方式，可以把主成分的主要部分凸現(xiàn)出來.因此，主成分就會變得較為容易解釋.

實現(xiàn)主成分分析稀疏化最終會轉(zhuǎn)化為優(yōu)化問題，即對本來的主成分分析(PCA)中的問題增加一個懲罰函數(shù)，此懲罰函數(shù)包含有稀疏度的信息.最終得到的問題是NP-難題，為了解決其，就需要采用一些方法逼近此問題的解.最先提出的方法是簡單門限主成分[2]，但此方法被證明具有誤導性.之后又提出的方法主要基于主成分L1范數(shù)的懲罰項，包括ScoTLAS和SPCA[3-8]. D’Aspremont等人[9]根據(jù)L0約束公式提出了貪婪的算法來計算出全套好的候選方案，使得一個向量成為全局最優(yōu)解.Moghaddam等[10]用分支界限法來計算小問題實例的最優(yōu)解.另外，還有D.C.和基于EM方法.Journee等[11]提出2種方法，基于L0罰和L1罰的單一的個體(一個成分的計算)和二分區(qū)式(多個成分同時計算).Matthias等[12]根據(jù)L1罰和L2罰[13]約束公式提出使用逆冪法解決此問題.筆者基于文獻[12]的工作進一步添加L0約束條件，運用逆冪法給出求解目標函數(shù)的迭代算法，并且數(shù)據(jù)模擬實驗充分展示了該算法在主成分的稀疏程度和累積貢獻率上都取得了很好的效果.

1 稀疏主成分分析

(1)

現(xiàn)在考慮函數(shù)F的下面的形式

(2)

(3)

為了得到稀疏的主成分，Hein M[12]在分子上使用L1范數(shù)和L2范數(shù)的組合來代替L2范數(shù)，在此基礎上增加L0范數(shù)，把分子變?yōu)長0范數(shù)，L1范數(shù)和L2范數(shù)的線性組合使得主成分更加稀疏，函數(shù)變?yōu)?/p>

(4)

2 基于逆冪法的求解算法

2.1 稀疏主成分分析的分析解使用逆冪法求解公式(4)的特征值和特征向量.

獲取半正定對稱矩陣∑的最小特征向量的標準技術是逆冪法，其主要構(gòu)建模塊是使用迭代方案收斂到∑的最小特征向量.

定理1[11]假設R，S滿足上述的條件，那么f*是F的一個駐點的必要條件是

(5)

(6)

(7)

式(7)中，當‖f‖2，β=0時，對于與足夠大的α,必須使得f*(α)=0來獲取最大的稀疏度.因為

得到‖Xf‖2-α‖f‖1<0，對于所有非零向量f,α始終要嚴格大于‖xi*‖2.現(xiàn)在假定

α<‖xi*‖2，

(8)

注意到在‖Xf*(α)‖2的值和稀疏解f*(α)有一個權衡.懲罰參數(shù)α被引用在上敘的2個極端的情形，其取值范圍在區(qū)間[0,‖xi*‖2)上，依賴于在實際應用中稀疏度和解釋方差的重要性.基于這些考慮，認為式(7)的解是X的稀疏主成分，其分析解由定理2給出.使用記號x+=max{0,x}.

(9)

證明假設目標函數(shù)是正一次的，最優(yōu)化要么是0，插入在之前的迭代程序中，要么是負數(shù)，在此情況下最優(yōu)解在邊界取得.因此不失一般性，假設‖f‖2=1，所以目標函數(shù)(7)就變?yōu)?/p>

(10)

由于式(9)里的s僅僅是個換算系數(shù)，在執(zhí)行算法過程中可以忽略掉，從而獲得簡單又有效的方案來計算稀疏主城分.

2.2 算法步驟基于定理2，設計了類似于文獻[12]的算法步驟：

輸出：特征值λk+1，特征向量fk+1.

步驟1初始化向量f0隨機，S(fk)=1,λ0=F(fk)，迭代次數(shù)k=1；

步驟4計算λk+1=(-α-β)‖fk+1‖2+α‖fk+1‖1+β‖fk+1‖0；

在文獻[12]的基礎上，筆者在算法中添加了L0約束條件，運用L0范數(shù)表示向量中非零元素的個數(shù)的屬性來進行稀疏編碼和特征選擇，通過最小化L0范數(shù)，來尋找最少最優(yōu)的稀疏特征項，為稀疏表示最直接最理想的方案，不足的是容易引發(fā)NP難題，所以用L0范數(shù)，L1范數(shù)和L2范數(shù)的線性組合來得到L0的最優(yōu)凸近似.

3 實驗與分析

3.1 實驗數(shù)據(jù)及參數(shù)設置采用與文獻[5]相同的數(shù)據(jù)模擬實驗進行模擬，具體模擬數(shù)據(jù)產(chǎn)生方法如下

給出3個潛在的主成分V1，V2，V3，

V1～N(0,290),V2～N(0,300),V3=-0.3V1+0.925V2+ε，

其中，ε～N(0,1)且V1，V2和ε相互獨立.

接下來產(chǎn)生10個變量，其構(gòu)造如下

在實驗中，本文算法中α，β稀疏控制參數(shù)由動態(tài)來確定.另外，主成分的非零個數(shù)控制為4個.

3.2 實驗結(jié)果及分析

表1 PCA，SPCA和SPCA(InvPow)的模擬結(jié)果

為了避免模擬的隨機性，用精確的協(xié)方差陣(X1，…，X10)來運行PCA，SPCA, SPCA(InvPow).

3個潛在主成分的方差分別是290，300和283.8，3個主成分相關變量的數(shù)量分別是4，4和2.SPCA,IPM和SPCA(InvPow)提取的前2個主成分分別共解釋了總方差的99.6%，86.6%和99.8%，說明僅僅需要考慮2個派生變量.事實上，在正交約束下如果依次最大化前2個派生向量的方差，控制非零載荷的數(shù)量為4個，那么SPCA的第一個派生向量統(tǒng)一的在(X5，X6，X7，X8)上賦值非零荷載，第二個派生向量統(tǒng)一的在(X1，X2，X3，X4)上賦值非零荷載，而IPM和SPCA(InvPow) 的第一個派生向量統(tǒng)一的在(X7，X8，X9，X10)上賦值非零荷載，第二個派生向量統(tǒng)一的在(X1，X2，X3，X4)上賦值非零荷載.

由以上數(shù)據(jù)分析可以得到

1) 從稀疏程度方面，SPCA，IPM和SPCA(InvPow)都能給出稀疏形式的主成分，并且給出的稀疏程度相似，都是是通過預言信息執(zhí)行的，理想的稀疏表示是僅僅4個變量.事實上，SPCA，IPM和SPCA(InvPow)都實現(xiàn)了前2個主成分的理想稀疏表示.

2) 從方差貢獻率方面，PCA的累積貢獻率達99.6%， SPCA的累積貢獻率只有80.4%，IPM的累積貢獻率達83.6%，SPCA(InvPow)的累積貢獻率為99.8%，SPCA和IPM提取的主成分的信息損失較大，SPCA(InvPow)相對來說降低了信息的損失.

3) 從收斂速度方面，SPCA(InvPow)達到收斂所需的迭代次數(shù)要比IPM要少，收斂速度更快.

4 結(jié)束語

通過實驗分析的數(shù)據(jù)可以得到標準PCA雖然信息損失量較小，但是給出的每個主成分自變量Xi的載荷系數(shù)都不為零，難以給出其實際解釋.SPCA,IPM和SPCA(InvPow)都能給出稀疏形式的主成分，雖然在稀疏程度上有相似的的結(jié)果，SPCA(InvPow)減少了信息損失量.

盡管SPCA(InvPow)方法在模擬實驗中顯示了其良好的性能，但是仍然需要做進一步的研究，有待于在未來的問題中得到廣泛應用.例如在處理實際問題時，參數(shù)的選擇，約束條件的選取等，將來可進一步嘗試將其加入到其他典型的相關分析應用當中.

[1] Jolliffe I T. Principal Component Analysis [M]. 2nd ed.New York: Springer, 2002: 167-198.

[2] Cadima J, Jolliffe I T. Loading and correlations in the interpretation of principal components [J]. Journal of Applied Statistics, 1995, 22(1): 203-204.

[3] Zou H, Hastie T, Tibsgirani R. Sparse principal component analysis [J]. Journal of Computational and Graphical Statistics, 2006, 15(2): 262-286.

[4] Shao W, Zhu L P, Liu Q P, et al. Sparse principal component analysis for symmmetrical matrix and application in sufficient dimension reduction [J]. Journal of Shandong University, 2012, 47(4): 116-120.

[5] Shen N J, Li J, Zhou P Y, et al. Extraction method based on sparse principal component for gene expression data [J]. Computer Science, 2015, 42(6A): 453-458.

[6] Liao R H, Li Y F, Liu H. Face recognition based on robust principal component analysis and kernel sparse representation [J]. Computer Engineering, 2016, 42(2): 200-205.

[7] Xiang K. Sparsity in principal component analysis [J]. Acta Electronica Sinica, 2012,40(12): 2 525-2 532.

[8] Zhao Q, Meng D Y. Robust sparse principal component analysis [J]. Science China (Information Sciences),2014,40(2): 175-188.

[9] D’Aspremont A, Bach F, Ghaoui L E I. Optimal solutions for sparse principal component analysis [J]. Journal of Machine Learning Research, 2008, 9(4): 1 269-1 294.

[10] Moghaddam B, Weiss Y, Avidan S. Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms [M]. New York: MIT Press, 2006:915-922.

[11] Journee M, Nesterov Y, Richtarik P, et al. Generalized power method for sparse principal component analysis [J]. Journal of Machine Learning Research, 2010, 11(3): 5 117-5 153.

[12] Hein M, Buhler T. An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA [J]. Journal of Machine Learning Research, 2010,9(4): 847-855.

[13] Ding M, Jia W M,Yao M L.A projection algorithm with local preservation based on L2norm [J]. Journal of Xi’an JiaoTong University, 2016, 50(2): 33-37.

Sparse Principal Component Analysis with Sparsity Constraints Based on the Inverse Power Method

Li Xia，Liu Xiangyang

(College of Science, Hohai University, Nanjing 210098, China)

In the report, based on the standard principal components analysis, in order to explain the practical problems, L0penalty, L1penalty, and L2penalty constraint conditions were added, which made the principal components more sparse. The inverse power method was used to obtain the iterative algorithm for solving the objective function. The data simulation experiment results suggested that our algorithm has achieved good effects on the sparse degree and the cumulative contribution rate of the principal component.

principal component analysis; sparse principal component analysis; the inverse power method; nonlinear feature extraction

2016-05-18

國家自然科學基金(61001139)

李霞(1989-)， 女, 山西晉中人，河海大學2014級碩士研究生, 研究方向：稀疏主成分分析，E-mail:1294301102@qq.com

劉向陽(1977-)， 男，博士，副教授, 研究方向：圖像與視頻分析、數(shù)據(jù)分析和機器學習， E-mail: liuxy@hhu.edu.cn

1004-1729(2016)04-0338-05

TP 391

A DOl：10.15886/j.cnki.hdxbzkb.2016.0051