在對(duì)待大量的輸入數(shù)據(jù)分析的問題上，為了簡(jiǎn)化問題，同時(shí)又不降低性能，通常使用降維來減少輸入的數(shù)據(jù)量，其中，主成分分析[1]是最受歡迎的方法之 一。在主成分分析中，試圖找到一組能夠最大化給定數(shù)據(jù)的方差的投影。這些投影構(gòu)成一個(gè)低維線性子空間，在此空間中，保留了原始的輸入空間中的數(shù)據(jù)結(jié)構(gòu)。
　　摘要：魯棒性不足是傳統(tǒng)的基于L2-范數(shù)的主成分分析（L2-PCA）的主要問題。為此，提出了一種基于新的L1-范數(shù)優(yōu)化技術(shù)的主成分分析（L1-PCA）方法。該方法使用了對(duì)異常值和旋轉(zhuǎn)不太敏感的L1-范數(shù)。L1-范數(shù)優(yōu)化技術(shù)是直觀的、簡(jiǎn)單的和易于實(shí)現(xiàn)的，事實(shí)上，L1-范數(shù)優(yōu)化技術(shù)也被證明是找到本地最大值的一種解決方法。在一些數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了基于L1-范數(shù)優(yōu)化技術(shù)的主成分分析算法的有效性。

　　關(guān)鍵詞：PCA-L1,L1-范數(shù),優(yōu)化,主成分分析,魯棒性

　　0引言

　　雖然基于L2范數(shù)的PCA（簡(jiǎn)稱L2-PCA）已成功地解決了許多問題，但是它很容易出現(xiàn)異常值，因?yàn)長(zhǎng)2范數(shù)會(huì)夸大一個(gè)大范數(shù)下的異常值的影響力。為了減輕這一問題并實(shí)現(xiàn)魯棒性，很多研究者已經(jīng)進(jìn)行了許多研究[2-7]。在文獻(xiàn)[5-7]中，假定每個(gè)投影和原始數(shù)據(jù)點(diǎn)之間的誤差主要是遵循拉普拉斯分布而不是高斯分布，通過最大似然估計(jì)所給定的數(shù)據(jù)來制定L1范數(shù)PCA（L1-PCA）。為獲得L1-PCA的解決方法，文獻(xiàn)[5]使用了啟發(fā)式估計(jì)來解決了一般的L1問題，與此同時(shí)，文獻(xiàn)[6，7]提出了加權(quán)中值法和凸面編程法。盡管L1-PCA具有魯棒性，但它還有一些缺點(diǎn)。首先，由于它是基于線性或二次規(guī)劃，計(jì)算量大；其次，它對(duì)旋轉(zhuǎn)是可變的。在文獻(xiàn)[4]中，丁等人提出了融合了L1-PCA、L2-PCA的優(yōu)點(diǎn)的R1-PCA。不像L1-PCA，R1-PCA正如L1-PCA那樣成功地抑制了異常值的影響，并且是旋轉(zhuǎn)不變式。然而，該方法是高度依賴于被找到的m維子空間。例如，在m=1時(shí)獲得的投影向量不可能是在m=2獲得的子空間。此外，因?yàn)樗�是一個(gè)基于一個(gè)連續(xù)使用功率法[8]的迭代算法，對(duì)于一個(gè)大維數(shù)的輸入空間，它需要花費(fèi)很多的時(shí)間來實(shí)現(xiàn)收斂。

　　然而，上述方法都試著在原始的輸入空間對(duì)投影和原始數(shù)據(jù)點(diǎn)之間的誤差最小化。如果L2-范數(shù)作為距離測(cè)量，這個(gè)目標(biāo)可以通過奇異值分解實(shí)現(xiàn)[8]，奇異值分解相當(dāng)于通過在特征空間中最大化方差來找到投影。在本文中，不是使用基于L2-范數(shù)最大化方差，而是使用了一種能夠最大限度提高特征空間的L1-范數(shù)、實(shí)現(xiàn)穩(wěn)健和旋轉(zhuǎn)不變的主成分分析方法。實(shí)驗(yàn)表明，基于L1-范數(shù)的PCA算法具有好的降維分類性能。

　　1基于L1-范數(shù)最大化的PCA

　　1.1理論分析

　　令為給定的數(shù)據(jù)，n和d分別表示樣本的數(shù)量和維數(shù)的原始輸入空間。在L2-PCA試圖通過最小化誤差找到一個(gè)m（⑴計(jì)算

　　⑴

　　式⑴中，是投影矩陣的列構(gòu)成m維線性子空間（即特征空間），是系數(shù)矩陣，（i，j）組件vij對(duì)應(yīng)著xj的第i個(gè)坐標(biāo)中的m維特征空間W，是L2-范數(shù)的矩陣或向量的表示。

　�、魄蠼饽繕�(biāo)函數(shù)

　�、�

　　式⑵中，Sx=XXT是協(xié)方差矩陣X和Im的m×m單位矩陣。

　　通常L2-范數(shù)是敏感的異常值，為此文獻(xiàn)[5-7]提出將問題轉(zhuǎn)化為找到一個(gè)W使得接下來的誤差函數(shù)能最小化：

　�、�

　　這里，表示L1-范數(shù)的矩陣或向量。

　　雖然公式⑶減少了異常值的影響，但是它并不是固定不變的旋轉(zhuǎn)，并且一個(gè)等距離表面的形狀變得非常扭曲。文獻(xiàn)[4]提出了基于R1-范數(shù)近似地解決誤差函數(shù)最小化的方案，即：⑷

　　公式⑷中子空間L1-范數(shù)估計(jì)迭代算法是很困難的，在文獻(xiàn)[4]中使用了胡貝爾的M-估計(jì)技術(shù)。

　　在本文中，我們?cè)谔卣骺臻g中L1分散使用L1-范數(shù)最大化，即：

　�、�

　　式⑸中，約束條件WTW=Im是為了確保投影矩陣的正交性。

　　公式⑸存在一個(gè)問題：最優(yōu)的第i個(gè)投影在R1-PCA中隨著不同的值m而不同，在m>1時(shí)找到一個(gè)全局最優(yōu)的解決方案是困難的。為了解決這個(gè)問題，我們通過使用一種貪婪的搜索方法簡(jiǎn)化公式⑸中m=1的問題。如果令m=1，公式⑸就變成了以下的優(yōu)化問題：

　�、�

　　1.2算法步驟

　�、懦跏蓟�：選擇任意的w（0），令，t=0。

　�、茦O性檢驗(yàn)：對(duì)于所有的i∈{1，2，…，n}，如果wT（t）xi<0，pi（t）=-1，否則pi（t）=1。

　�、欠�轉(zhuǎn)和最大化：令t←t+1，·w（t）←w（t）/。

　　⑷收斂性檢驗(yàn)：

　�。╝）如果w（t）≠w（t-1），則執(zhí)行第二步；

　�。╞）否則如果存在i使得wT（t）xi=0，令w（t）←（w（t）+Δw）/，繼續(xù)執(zhí)行第二步（這里的Δw是一個(gè)小的非零隨機(jī)向量）；

　�。╟）否則，令w*=w（t），最后終止。

　　2實(shí)驗(yàn)

　　2.1實(shí)驗(yàn)數(shù)據(jù)

　　本文采用了部分UCI數(shù)據(jù)集，具體描述如下表1所示。

　　表1實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集

　　[數(shù)據(jù)集＼&維數(shù)＼&類數(shù)＼&樣本數(shù)＼&Australian＼&14＼&2＼&690＼&Balance＼&4＼&3＼&625＼&Breastcancer＼&9＼&2＼&683＼&Dermatology＼&34＼&6＼&358＼&Heartdisease＼&13＼&2＼&297＼&Ionosphere＼&33＼&2＼&351＼&Liver＼&6＼&2＼&345＼&Sonar＼&60＼&2＼&208＼&]

　　2.2實(shí)驗(yàn)結(jié)果與分析

　　實(shí)驗(yàn)采用最近鄰分類（1-NN）。對(duì)于每個(gè)數(shù)據(jù)集，我們進(jìn)行了20次實(shí)驗(yàn)并計(jì)算平均分類率。實(shí)驗(yàn)前，對(duì)每個(gè)輸入變量進(jìn)行標(biāo)準(zhǔn)化，它們具有零均值和單位方差。測(cè)試組中的變量也被標(biāo)準(zhǔn)化。圖1給出了具體的實(shí)驗(yàn)結(jié)果。

　�。╝）Australian（b）Balance

　　（c）Breastcancer（d）Dermatology

　�。╡）Heartdisease（f）Ionosphere

　�。╣）Liver（h）Sonar

　　圖1多個(gè)UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

　　此外，考慮到計(jì)算成本，表2給出了L2-PCA，R1-PCA和PCA-L1所需的平均時(shí)間和平均迭代次數(shù)。

　　表2UCI數(shù)據(jù)集的計(jì)算時(shí)間和平均迭代次數(shù)

　　[＼&平均時(shí)間（毫秒）＼&平均迭代次數(shù)＼&數(shù)據(jù)集＼&L2-PCA＼&R1-PCA＼&PCA-L1＼&R1-PCA＼&PCA-L1＼&Australian＼&0＼&583＼&343＼&42.29＼&7.14＼&Balance＼&0＼&36＼&47＼&2.00＼&1.00＼&Breastcancer＼&0＼&547＼&266＼&45.44＼&9.78＼&Dermatology＼&62＼&750＼&750＼&45.47＼&12.82＼&Heartdisease＼&0＼&239＼&141＼&36.61＼&6.53＼&Ionosphere＼&64＼&816＼&625＼&47.30＼&10.15＼&Liver＼&0＼&125＼&79＼&24.67＼&5.67＼&Sonar＼&47＼&1533＼&734＼&34.50＼&10.30＼&]

　　通過分析可以得出，因?yàn)镽1-PCA的第i個(gè)的投影矢量與提取的特征數(shù)量的變化有關(guān)，所以計(jì)算的時(shí)間和R1-PCA迭代次數(shù)是提取不同數(shù)目的特征平均值。另一方面，L2-PCA和PCA-L1的時(shí)間和迭代提取的特征的數(shù)目等于輸入變量個(gè)數(shù)時(shí)獲得的數(shù)據(jù)。例如，R1-PCA時(shí)間為25500毫秒=750毫秒×34，而L2-PCA和PCA-L1的平均時(shí)間分別為62毫秒和750毫秒。在表2中，我們可以看出在許多情況下用PCA-L1的時(shí)間少于R1-PCA，并且在波形的數(shù)據(jù)集中PCA-L1的迭代次數(shù)少于15次。

　　3結(jié)束語

　　本文提出了基于L1范數(shù)的主成分分析方法的優(yōu)化。該方法使用了對(duì)異常值和旋轉(zhuǎn)不太敏感的L1-范數(shù)，最大限度地提高L1范數(shù)的預(yù)計(jì)，而不是傳統(tǒng)的L2范數(shù)的空間。在UCI的實(shí)驗(yàn)表明，與基于傳統(tǒng)的L2范數(shù)的PCA相比，本文所提出的方法計(jì)算復(fù)雜度正比于樣品數(shù)量、輸入空間的維數(shù)和迭代的次數(shù)。迭代的次數(shù)不依賴于輸入空間的維數(shù)，該方法對(duì)像圖像處理那樣的高維輸入問題具有更好的降維分類和計(jì)算性能。L1-規(guī)范優(yōu)化技術(shù)是直觀的，故相對(duì)簡(jiǎn)單和容易實(shí)現(xiàn)。此外，它雖然成功地抑制了異常值，但帶來的負(fù)面影響是不變的旋轉(zhuǎn)。如何克服這個(gè)缺陷是我們下一步的研究工作。參考文獻(xiàn)：

　　[1]I.T.Jolliffe，PrincipalComponentAnalysis，Springer-Verlag，1986.

　　[2]F.DelaTorreandM.J.Black，“Aframeworkforrobustsubspace

　　learning，”InternationalJournalofComputerVision，2003.54（1-3）：117-142

　　[3]H.Aanas，R.Fisker，K.Astrom，andJ.Carstensen，“Robust

　　factorization，”IEEETransactionsonPatternAnalysisandMachineIntelligence，2002.24（9）：1215-1225

　　[4]C.Ding，D.Zhou，X.He，andH.Zha，“R1-pca：rotational

---

轉(zhuǎn)載請(qǐng)注明來自：http://www.jinnzone.com/jisuanjiwangluolw/27304.html