一種魯棒主成分分析算法

1、系統(tǒng)工程理論與實踐 980124科技期刊系統(tǒng)工程理論與實踐SYSTEM ENGINEERING THEOR Y&PRACTICE1998年第18卷第1期一種魯棒主成分分析(PCA)算法王松夏紹瑋(清華大學(xué)自動化系，北京00084)摘要 主要研究了改善主成分分析(PCA)算法魯棒性的一種實現(xiàn)途徑，以提高PCA的精度。討論了 PCA魯棒性問題的兩種提法。修正PCA算法能夠在運行過程中自動地識別樣本集之中的“劣點”，從而通過迭代計算加以適當(dāng)處理來排除對運算精度的影響。對比仿真實驗 結(jié)果表明，魯棒PCA算法較之傳統(tǒng)的基于特征值分解的PCA算法在魯棒性上有了較大的改善。關(guān)鍵詞主成分分析魯棒主成分

2、分析劣點A Robust Prin cipal Comp onent An alysis(PCA) AlgorithmWang Song Xia Shaowei(Department of Automation ， Tsinghua University， Beijing 100084)Abstract One way to improve the robust ness of pr in cipal comp onent an alysis(PCA) is studied in order to in crease the accuracy of PCA algorithm . Two me

3、thods to an alyze the robust ness of PCA algorithm are proposed and compared. The new robust PCA algorithm can recognize the outliers in the sample set automatically and extermi nate their effects to the accuracy of the PCA algorithm through proper processing to the outliers . The comparison experim

4、ents are designed to show that robust PCA algorithm is better than the traditional statistical PCA algorithm based on eigenvalue decomposition.Keywordsprincipal component analysis(PCA) ; robust PCA ; outliers主成分分析(PCA)是統(tǒng)計分析法中的一種重要方法，在系統(tǒng)評價、故障診斷、質(zhì)量管理 和發(fā)展對策等許多方面都得到廣泛的應(yīng)用。這一方法利用數(shù)理統(tǒng)計方法找出系統(tǒng)中主要因 素和各因素之間的相互關(guān)

5、系，大大壓縮了處理的數(shù)據(jù)量丨1： O然而，普通的基于特征值分解的統(tǒng)計PCA方法存在嚴(yán)重的魯棒性問題，這大大影響了PCA的運算精度。一些學(xué)者已經(jīng)從不同的角度提出PCA的魯棒性問題，對此進行了研究，并且提出了各自的改進算法。本文首先對PCA魯棒性的兩種典型考慮角度進行分析和對比。然后從實際應(yīng)用出發(fā)，提出了一種實用的魯棒主成分分析算法。W= w1，w2,，wm%nXm維的變換矩陣(m v1 PCA的原理和魯棒性設(shè)輸入x為n維的零均值的隨機向量n）, y=WTx為變換后的隨機向量。則 y稱為隨機向量x的m維主成分，如果wc = arx ni<ixE（K/jr）2 并且n維向量vi滿足約束條件fi

6、le:/E|/qk/xtgcllysj/980124.htm（第 3 / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124file:/E|/qk/xtgcllysj/980124.htm（第 # / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124i=1,2,，m。w i稱為隨機向量x的第i主方向。其中E表示求期望。傳統(tǒng)上，變換矩陣 W可以通過對輸人隨機向量x的協(xié)方差矩陣進行特征值分解來獲得。設(shè)S=E xxT為x的協(xié)方差矩陣，由于 S是正定對稱矩陣，所以存在 n個不同的正特征值。不 妨設(shè)為入1>k 2>> 入n，眾所周知

7、第i主方向w i就是入）所對應(yīng)的單位特征向量。因此構(gòu) 成W的m個主方向滿足Sw i =入 iw i i=1,2,，m Xi，j=1，2，,在實際分析過程中，往往通過統(tǒng)計的辦法來估計。給定一個數(shù)據(jù)集N，可得x的協(xié)方差矩陣S的估計為file:/E|/qk/xtgcllysj/980124.htm（第 # / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124file:/E|/qk/xtgcllysj/980124.htm（第 # / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124a j S進行轉(zhuǎn)征值分解和排斥可以得劇入和W的估計值X和V*Sw

8、 i = i i = 1 *2 * 當(dāng)前對PCA魯棒性的考慮主要有兩個角度：一是考慮如何能夠達到輸出的各主成分之間相互獨立。這樣就可以把一個多輸入的問題分解為多個相互獨立的單輸入的問題來考慮。毫無疑問，無論輸入隨機向量x服從何種分布，上述基于特征值分解的統(tǒng)計 PCA算法得到的m個主成分之間一定是互不相關(guān)的。因為， 特征值分解相當(dāng)于將其協(xié)方差矩陣線性變換為一個對角矩陣，其非對角元（代表各主成分的相關(guān)程度）均為零。由概率論的知識易知，由上述PCA算法獲得的各主成分相互獨立當(dāng)且僅當(dāng)輸入x服從零均值、協(xié)方差陣為 S的n維高斯分布，即其密度函數(shù)file:/E|/qk/xtgcllysj/980124.h

9、tm（第 # / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124file:/E|/qk/xtgcllysj/980124.htm（第 # / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124當(dāng)輸入不服從高斯分布時，傳統(tǒng)PCA算法由于只考慮基于協(xié)方差陣的二階特性，因此得到file:/E|/qk/xtgcllysj/980124.htm（第 4 / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124的主成分只能做到互不相關(guān)，而不能做到相互獨立。因此，如何在非高斯分布輸入的情形 下實現(xiàn)各主成分相互獨立就成為PCA算法

10、魯棒性研究的一個主要方向?，F(xiàn)有的主要方法是根據(jù)已知的輸入樣本分布，引入適當(dāng)?shù)姆蔷€性處理環(huán)節(jié)，提出所謂 非線性PCA的算法。這樣，就考慮了輸入的高階統(tǒng)計特性，從而實現(xiàn)輸出主成分的相互獨 立。在此基礎(chǔ)上，有人提出了獨立成分分析(ICA)的概念3】，并且得到了高度的重視。二是考慮如何去除或減弱有限的訓(xùn)練樣本集中少量“劣點”樣本的影響從而獲得準(zhǔn)確 主方向。所謂“劣點”樣本，直觀上是指與樣本集中絕大部分樣本分布差異過大的極少量 樣本，它們的存在使得 PCA的計算結(jié)果會出現(xiàn)很大的誤差2】?！傲狱c”的產(chǎn)生原因是多方面的，例如突發(fā)的隨機噪聲，測量或者記錄的偶爾出錯等等。另外，由于樣本數(shù)是有限 的，即使所有樣本

11、都是由同一分布產(chǎn)生的，也有可能因為樣本數(shù)不足從而使得其中少量樣 本成為實際上的“劣點”樣本。因此，從克服“劣點”樣本的影響出發(fā)是算法魯棒性研究的另一個主要方向。顯然第一種研究方法有著重大的理論意義。它在信號分離理論這一研究領(lǐng)域已經(jīng)得到 高度的重視。但是在系統(tǒng)科學(xué)和系統(tǒng)工程領(lǐng)域，由于實際應(yīng)用中往往輸人樣本的分布是未 知的；同時由于樣本集有限，基于非高斯分布輸入的獨立成分分析方法不能很好地消 除“劣點”樣本對算法魯棒性的影響，難以獲得準(zhǔn)確的主方向。故而從消除或減弱“劣 點”的影響出發(fā)研究 PCA的魯棒性有著更為重要的實際意義。另外，在系統(tǒng)科學(xué)和系統(tǒng)工程的很多應(yīng)用領(lǐng)域中，找出樣本集中的少量“劣點”樣

12、本 本身也是很有意義的工作。例如對一段時間的股票數(shù)據(jù)進行的分析可以找到其最具特殊性 的時間段，從而能夠進行深入研究以發(fā)現(xiàn)其產(chǎn)生的規(guī)律和原因。因此，從去除“劣點”影 響的角度建立魯棒PCA算法拓寬了 PCA的應(yīng)用范圍。本文主要從去除“劣點”樣本影響的角度研究PCA的魯棒性問題。下面，首先建立“劣點”樣本的判據(jù)，然后據(jù)此建立魯棒PCA算法。2魯棒PCA算法為提高PCA算法的魯棒性，必須去除或者減少“劣點”樣本污染對算法的影響。很自 然地要考慮如何找出樣本集中的“劣點”樣本，在求解協(xié)方差矩陣時將其排除在外。因此 首先需要確定“劣點”樣本的判據(jù)。2. 1利用信號重構(gòu)誤差判別“劣點”樣本近年來，一些學(xué)者

13、發(fā)現(xiàn)式 (1)和式(2)所定義的主方向有多種其他的等價定義方式 4: < 基于信號重構(gòu)誤差最小準(zhǔn)則便是其中最常用的一種。其一般原理如圖1所示，令n維隨機向量u = Wy為輸入x的信號重構(gòu)，則e=x-u為信號重構(gòu)誤差。定義能量函數(shù) J1(W)J1(W)=E ell 2二E H x-u II 2(7)對于具體的樣本集，其估計表達式為JjlWr 春 £ li 巧一 |E (8)其中W的列向量是單位向量且線性無關(guān)?？梢姡瑑?yōu)化能量函數(shù)的目標(biāo)是盡量減少降維處理 對原信號造成的損失。定理1 4J1(W)最小所對應(yīng)的矩陣 W就是輸入隨機向量x的m維PCA子空間，即W各列向量構(gòu)成的子空間的就是

14、x的前m個主方向所張成的子空間。從定理1容易得出，當(dāng)m=1時，式(1)和式(8)的最優(yōu)解是完全等價的，這就是輸入的最大 王萬向。圖1主成分提取和信號重構(gòu)這樣，可以利用重構(gòu)誤差的大小作為“劣點”的判據(jù)。當(dāng)某樣本重構(gòu)誤差太大時，就認為 其是“劣點”。避免它在整個樣本集中對J1(W)的優(yōu)化起支配作用。定義1設(shè)輸人隨機向量x的前m個主方向構(gòu)成矩陣 W，z>0為給定的闊值，一個實際樣 本xi稱為“劣點”樣本，如果：II xi-WWTxi |> z(9)在上述定義的基礎(chǔ)上就可以對原 PCA算法進行修正，提出新的魯棒的PCA算法。2. 2魯棒的PCA算法利用定義1來找出樣本集中的“劣點，問題主要

15、在于它是在預(yù)知實際的W的基礎(chǔ)上定義的，這在實際應(yīng)用中是不可能的。通常只能給出一個W的估計值，利用其估計值判別“劣點”樣本并在算法中加以排除從而獲得更準(zhǔn)確的W的估計值，由此 W再去重新判別樣本集中的“劣點”樣本。如此迭代下去就可以直到收斂。另外，閾值z的大小也是難以確定的，選得過大過小都不合適。在下面的算法中換一個角度去處理。求出樣本集所有樣本的重構(gòu)誤差，重構(gòu)誤差相對大的一部分樣本就確定 為“劣點”樣本。對于給定的樣本集 E= xi， i=1， 2，N，魯棒的PCA算法可以描述如下：1) 初始化迭代步數(shù)k = 0,設(shè)定樣本集E中“劣點”樣本數(shù)L(k)=0，也就是說待處理樣 本集F = E;2)

16、利用式(4)和式(5)對樣本集F進行主成分分析，得到本步估計矩陣W(k);3) 根據(jù)上面得到的PCA變換矩陣W(k)，利用式(8)計算原始樣本集E中每個樣本Xi在本步的重構(gòu)誤差I(lǐng)I ei(k) | = | Xi-W(k)W(k)Txji=1 , 2,，N; (10)4) 迭代步數(shù)k+1，設(shè)樣本集E中“劣點”樣本數(shù)L(k+1)=L(k)+1,也就是從樣本集E中刪除上一步重構(gòu)誤差最大的 L(k+1)個樣本，并由剩下的樣本構(gòu)成新的待處理樣本集F;5) 判斷W(k+1)是否滿足收斂條件，若滿足則迭代結(jié)束，否則轉(zhuǎn)第2步。由定義1可以看出，“劣點”樣本能否準(zhǔn)確判別關(guān)鍵在于PCA變換矩陣W的估計值是否準(zhǔn)確。

17、上述魯棒PCA算法幵始一段時間內(nèi) W的估計值顯然與實際值有著很大的誤差，此時 判別的“劣點”樣本也是不夠準(zhǔn)確的。有可能將一些非劣的樣本當(dāng)成“劣點”樣本，而有 一些對算法精度影響很大的“劣點樣本卻未能挑選出來。基于此，在算法的第4)步米用重新在整個樣本集E中挑選和刪除“劣點”樣本，而不是在上一次循環(huán)得到的樣本集F中繼續(xù)處理。這樣可以改善算法的收斂性。判斷是否結(jié)束迭代的收斂條件有多種規(guī)則，下面給出常用的幾種并作簡要分析。規(guī)則1:固定總的迭代步數(shù)，達到給定的迭代步數(shù)便停止。這是最簡單也是比較常用的 一種規(guī)則。這種規(guī)則實際上就是預(yù)先確定樣本集中的“劣點”數(shù)目，通過相應(yīng)步數(shù)的迭代 進行處理。雖然實際情況

18、中樣本集中“劣點”數(shù)目通常是未知的，但往往只占樣本集中總 樣本數(shù)的一個很小的比例，例如3%-10 %之間。將總迭代步數(shù)設(shè)定得稍高于實際“劣點”數(shù)一般也不會帶來問題。因為非劣樣本的數(shù)目很大，即使將其中一部分當(dāng)成“劣點”樣本而 未加考慮也對最終結(jié)果的精度影響不大。規(guī)則2:根據(jù)規(guī)則1中的分析可以看出，當(dāng)?shù)欢ú綌?shù)找出所有“劣點”后，進一步 迭代下去，W(k)的在一定步數(shù)內(nèi)會保持相應(yīng)的穩(wěn)定性，變化比較小。直至將過多的非劣樣 本當(dāng)成“劣點”樣本導(dǎo)致剩下的樣本不足以體現(xiàn)實際的主方向。這一特征可以用來判斷算 法是否達到收斂從而停止迭代。如c 工 ilwto 1)| <?iQi)max |- W(i

19、- 1) |(12)&一就是兩種合適的判別準(zhǔn)則。其中，k為當(dāng)前迭代步數(shù)，n 1和n 2為事先規(guī)定的精度，M為考慮精度的長度，最小可以取 M=1。規(guī)則3：同時利用規(guī)則1和規(guī)則2來判斷是否應(yīng)該停止迭代，只要滿足二者之一就終止算 法。這種規(guī)則主要針對規(guī)則 1和規(guī)則2各自的優(yōu)缺點而言的。規(guī)則 1不能保證算法的精度：若 設(shè)定的總迭代次數(shù)過小，剩下的一部分“劣點”樣本仍然會影響PCA算法精度；若設(shè)定的總迭代次數(shù)過大，會將過多的非劣樣本當(dāng)成“劣點”樣本加以排除從而影響PCA算法精度。規(guī)則2的主要問題是當(dāng)事先規(guī)定的精度過高時會導(dǎo)致算法不收斂情形；而事先規(guī)定的精 度過低也會降低算法的精度。將二者結(jié)合起來

20、，會有效地克服各自缺點，從而獲得比較理 想的結(jié)果。另外，上述算法每迭代一步多找一個“劣點”樣本。在樣本集很大和“劣點”樣本數(shù) 目較多的情況下顯然會出現(xiàn)收斂很慢的現(xiàn)象。此時可以采取每迭代一步找出多個“劣 點”的方法。具體做法就是在算法第 4步中，設(shè)定整個樣本集E中“劣點”數(shù)為迭代步數(shù) k的 整數(shù)倍，而不是完全相等的關(guān)系，即L(k+1)=L(k)+a(a> 1)(13)更進一步，為改進收斂速度，可以把a取為迭代步數(shù)k的函數(shù)a(k):隨著k的增加，不斷減小a(k)直至 a(k) = 1 o當(dāng)然，針對具體的情況，若是已知樣本集中“劣點”樣本的一些先驗信息，還可以采取更多的和更有效的收斂判據(jù)。3仿

21、真實驗和結(jié)果分析仿真實驗分別采用基于式和式的傳統(tǒng)PCA算法和修正后的魯棒PCA算法，對不含“劣點”和包含“劣點”的樣本集進行主成分分析。用對比結(jié)果來說明魯棒PCA算法的性能。在這里考慮輸人為 2維樣本，提取其最大主成分，即n=2，m= 1。f _1L T隨機均勻產(chǎn)生500個主方向為S的零均值二維樣本集，記為樣本集A(如圖2)；在樣本集A中隨機插入10個與原分布差異很大的“劣點”，記為樣本集B(如圖3)。首先用式(4)和式(5)所示的傳統(tǒng)的PCA算法對樣本集A，B分別進行統(tǒng)計主成分分析，得到的主方 向分別為 WA= 0. 7117，7024 T和WB= 0. 9020，4317: To 可以看出

22、，傳統(tǒng) PCA算法對于無“劣點”的樣本集計算精度還是很高的，WA基本等于實際主方向。但是魯棒性很差，只要樣本集中存在少量的“劣點”樣本，主方向計算結(jié)果誤差非常大，也就是 說，對樣本分布的影響非常敏感。這里僅僅2%的“劣點”樣本引起主方向的誤差接近20 °,這在實際應(yīng)用中明顯是難以接受的。圖2樣本集A 圖3樣本集B采用本文提出的的魯棒 PCA算法對樣本集A和B分別進行迭代主成分分析。固定選代步數(shù)為20,每一步多找一個“劣點”樣本。圖 4是魯棒PCA算法對無“劣點”的樣本集 A的主成分 分析結(jié)果。橫坐標(biāo)表示迭代步數(shù)，縱坐標(biāo)表示當(dāng)前的W(k)的與實際的主方向之間的夾角，也就是誤差角度。圖5

23、是魯棒PCA算法對有“劣點”的樣本集 B的迭代主成分分析結(jié)果。其坐標(biāo)定義同圖4。圖4樣本集A的仿真結(jié)果圖5樣本集B的仿真結(jié)果從圖4和圖5所示的仿真結(jié)果可以看出修正的魯棒 PCA算法能夠有效地排除少數(shù)“劣點”樣 本的不良影響，最終收斂到正確結(jié)果并且保持很高的計算精度。即使原樣本集中不含或者 只含少量“劣點”樣本，魯棒 PCA算法也能獲得理想的結(jié)果。其原因正如上面所分析的， 由于“劣點”樣本所占的比例相對較小，從而把少量非劣樣本當(dāng)成“劣點”樣本處理并不 對計算結(jié)果產(chǎn)生太大的影響。同時還可以發(fā)現(xiàn)，修正后的算法收斂速度很快。這些都說明 本文的修正算法有著很強的實用性。在仿真實驗中還發(fā)現(xiàn)，魯棒 PCA算

24、法成功地找出了對算法精度影響較大的“劣點”樣 本。這本身有著很重要的意義。因為找出“劣點”樣本這也是統(tǒng)計數(shù)據(jù)處理的一個研究領(lǐng) 域。4結(jié)論和展望本文從消除“劣點”的角度對傳統(tǒng)的PCA算法進行修正。基于信號重構(gòu)的思想給出一種“劣點”樣本的判據(jù)。在此基礎(chǔ)上提出了一種迭代的魯棒PCA算法。分析了算法收斂的特征和判別規(guī)則。實驗仿真的結(jié)果表明修正算法較傳統(tǒng)PCA算法在魯棒性上有了明顯的改進。主成分分析已經(jīng)在系統(tǒng)科學(xué)的各個領(lǐng)域得到廣泛的應(yīng)用。魯棒PCA算法的引人將有助file:/E|/qk/xtgcllysj/980124.htm（第 10 / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐

25、 980124于克服原有PCA算法的缺點，拓寬其應(yīng)用的前景。同時，魯棒PCA算法在計算過程中自動識別“劣點”樣本，這一點本身在實際應(yīng)用中也有著一定的意義。進一步的工作包括兩方 面：一是建立含“劣點”樣本庫的隨機模型，從而能夠?qū)︳敯鬚CA算法的收斂性進行嚴(yán)格的理論分析；另一方面值得研究的便是到實際應(yīng)用中去驗證和改進算法。參 考 文 獻1夏紹瑋，楊家本，楊振斌.系統(tǒng)工程概論.北京：清華大學(xué)出版社，1995, 73-832 Xu Lei，Yuille A L . Robust principal component analysis by self-organizing rules based on statistical physics approach. IEEE Trans on Neural Networks ， 1995， 6(1)： 131-1433 Comon P. Independent component analysis，a new concept?. Signal Processing，1