李 霞，劉向陽(yáng)

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

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

李 霞，劉向陽(yáng)

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

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

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

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

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

1 稀疏主成分分析

(1)

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

(2)

(3)

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

(4)

2 基于逆冪法的求解算法

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

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

定理1[11]假設(shè)R，S滿足上述的條件，那么f*是F的一個(gè)駐點(diǎn)的必要條件是

(5)

(6)

(7)

式(7)中，當(dāng)‖f‖2，β=0時(shí)，對(duì)于與足夠大的α,必須使得f*(α)=0來(lái)獲取最大的稀疏度.因?yàn)?/p>

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

α<‖xi*‖2，

(8)

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

(9)

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

(10)

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

2.2 算法步驟基于定理2，設(shè)計(jì)了類似于文獻(xiàn)[12]的算法步驟：

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

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

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

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

3 實(shí)驗(yàn)與分析

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

給出3個(gè)潛在的主成分V1，V2，V3，

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[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

國(guó)家自然科學(xué)基金(61001139)

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

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

1004-1729(2016)04-0338-05

TP 391

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