一種魯棒主成分分析算法

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

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)評價、故障診斷、質量管理 和發(fā)展對策等許多方面都得到廣泛的應用。這一方法利用數(shù)理統(tǒng)計方法找出系統(tǒng)中主要因 素和各因素之間的相互關

5、系，大大壓縮了處理的數(shù)據(jù)量丨1： O然而，普通的基于特征值分解的統(tǒng)計PCA方法存在嚴重的魯棒性問題，這大大影響了PCA的運算精度。一些學者已經從不同的角度提出PCA的魯棒性問題，對此進行了研究，并且提出了各自的改進算法。本文首先對PCA魯棒性的兩種典型考慮角度進行分析和對比。然后從實際應用出發(fā)，提出了一種實用的魯棒主成分分析算法。W= w1，w2,，wm%nXm維的變換矩陣(m v1 PCA的原理和魯棒性設輸入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é)方差矩陣進行特征值分解來獲得。設S=E xxT為x的協(xié)方差矩陣，由于 S是正定對稱矩陣，所以存在 n個不同的正特征值。不 妨設為入1>k 2>> 入n，眾所周知

7、第i主方向w i就是入）所對應的單位特征向量。因此構 成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進行轉征值分解和排斥可以得劇入和W的估計值X和V*Sw

8、 i = i i = 1 *2 * 當前對PCA魯棒性的考慮主要有兩個角度：一是考慮如何能夠達到輸出的各主成分之間相互獨立。這樣就可以把一個多輸入的問題分解為多個相互獨立的單輸入的問題來考慮。毫無疑問，無論輸入隨機向量x服從何種分布，上述基于特征值分解的統(tǒng)計 PCA算法得到的m個主成分之間一定是互不相關的。因為， 特征值分解相當于將其協(xié)方差矩陣線性變換為一個對角矩陣，其非對角元（代表各主成分的相關程度）均為零。由概率論的知識易知，由上述PCA算法獲得的各主成分相互獨立當且僅當輸入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當輸入不服從高斯分布時，傳統(tǒng)PCA算法由于只考慮基于協(xié)方差陣的二階特性，因此得到file:/E|/qk/xtgcllysj/980124.htm（第 4 / 8 頁）2010-3-23 11:50:28系統(tǒng)工程理論與實踐 980124的主成分只能做到互不相關，而不能做到相互獨立。因此，如何在非高斯分布輸入的情形 下實現(xiàn)各主成分相互獨立就成為PCA算法

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

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

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

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

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

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

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

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

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

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

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

21、真實驗和結果分析仿真實驗分別采用基于式和式的傳統(tǒng)PCA算法和修正后的魯棒PCA算法，對不含“劣點”和包含“劣點”的樣本集進行主成分分析。用對比結果來說明魯棒PCA算法的性能。在這里考慮輸人為 2維樣本，提取其最大主成分，即n=2，m= 1。f _1L T隨機均勻產生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基本等于實際主方向。但是魯棒性很差，只要樣本集中存在少量的“劣點”樣本，主方向計算結果誤差非常大，也就是 說，對樣本分布的影響非常敏感。這里僅僅2%的“劣點”樣本引起主方向的誤差接近20 °,這在實際應用中明顯是難以接受的。圖2樣本集A 圖3樣本集B采用本文提出的的魯棒 PCA算法對樣本集A和B分別進行迭代主成分分析。固定選代步數(shù)為20,每一步多找一個“劣點”樣本。圖 4是魯棒PCA算法對無“劣點”的樣本集 A的主成分 分析結果。橫坐標表示迭代步數(shù)，縱坐標表示當前的W(k)的與實際的主方向之間的夾角，也就是誤差角度。圖5

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

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

25、 980124于克服原有PCA算法的缺點，拓寬其應用的前景。同時，魯棒PCA算法在計算過程中自動識別“劣點”樣本，這一點本身在實際應用中也有著一定的意義。進一步的工作包括兩方 面：一是建立含“劣點”樣本庫的隨機模型，從而能夠對魯棒PCA算法的收斂性進行嚴格的理論分析；另一方面值得研究的便是到實際應用中去驗證和改進算法。參 考 文 獻1夏紹瑋，楊家本，楊振斌.系統(tǒng)工程概論.北京：清華大學出版社，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