基于L1—范數(shù)最優(yōu)化的主成分分析

摘 要： 魯棒性不足是傳統(tǒng)的基于L2-范數(shù)的主成分分析（L2-PCA）的主要問題。為此，提出了一種基于新的L1-范數(shù)優(yōu)化技術(shù)的主成分分析（L1-PCA）方法。該方法使用了對異常值和旋轉(zhuǎn)不太敏感的L1-范數(shù)。L1-范數(shù)優(yōu)化技術(shù)是直觀的、簡單的和易于實現(xiàn)的，事實上，L1-范數(shù)優(yōu)化技術(shù)也被證明是找到本地最大值的一種解決方法。在一些數(shù)據(jù)集上的實驗驗證了基于L1-范數(shù)優(yōu)化技術(shù)的主成分分析算法的有效性。

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

中圖分類號：TP391.4 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2012）12-03-03

Principal component analysis based on L1-norm optimization

Zhang Congcong1， Chen Qi1， Xu Jiaheng2， Ji Binqiong1， Xu Shuhua1

（1. School of Maths and Physics， Shaoxing College， Shaoxing， Zhejiang 312000， China； 2. School of Engineering， Shaoxing College）

Abstract： Lacking robustness is a main problem of the traditional L2-norm （L2-PCA）. In this paper， a method of principal component analysis （PCA） based on a new L1-norm optimization technique is introduced. L1-norm is used， which is less sensitive to abnormal values and rotations. The proposed L1-norm optimization technique is intuitive， simple and easy to be implemented. It is also proven to be a solution to find a local maximum. Simulations on several databases are conducted to verify the validity of L1-PCA.

Key words： PCA-L1； L1-norm； optimization； principal component analysis； robustness

0 引言

在對待大量的輸入數(shù)據(jù)分析的問題上，為了簡化問題，同時又不降低性能，通常使用降維來減少輸入的數(shù)據(jù)量，其中，主成分分析[1]是最受歡迎的方法之一。在主成分分析中，試圖找到一組能夠最大化給定數(shù)據(jù)的方差的投影。這些投影構(gòu)成一個低維線性子空間，在此空間中，保留了原始的輸入空間中的數(shù)據(jù)結(jié)構(gòu)。

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

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

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

1.1 理論分析

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

⑴ 計算

⑴

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

⑵ 求解目標(biāo)函數(shù)

⑵

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

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

⑶

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

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

⑷

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

在本文中，我們在特征空間中L1分散使用L1-范數(shù)最大化，即：

⑸

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

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

⑹

1.2 算法步驟

⑴ 初始化：選擇任意的w（0），令，t=0。

⑵ 極性檢驗：對于所有的i∈{1，2，…，n}，如果wT（t）xi<0，pi（t）=-1，否則pi（t）=1。

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

⑷ 收斂性檢驗：

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

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

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

2 實驗

2.1 實驗數(shù)據(jù)

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

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

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

2.2 實驗結(jié)果與分析

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

（a） Australian （b） Balance

（c） Breast cancer （d） Dermatology

（e） Heart disease （f） Ionosphere

（g） Liver （h） Sonar

圖1 多個UCI數(shù)據(jù)集的實驗結(jié)果

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

表2 UCI數(shù)據(jù)集的計算時間和平均迭代次數(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＼Breast cancer＼0＼547＼266＼45.44＼9.78＼Dermatology＼62＼750＼750＼45.47＼12.82＼Heart disease＼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＼]

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

3 結(jié)束語

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

參考文獻(xiàn)：

[1] I.T. Jolliffe， Principal Component Analysis， Springer-Verlag，1986.

[2] F. De la Torre and M.J. Black， “A framework for robust subspace

learning，” International Journal of Computer Vision，2003.54（1-3）：117-142

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

factorization，” IEEE Transactions on Pattern Analysis and Machine Intelligence，2002.24（9）：1215-1225

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

invariant l1-norm principal component analysis for fobust subspace factorization，” in Proc. International Conference on Machine Learning， Pittsburgh， PA， June 2006.

[5] A. Baccini， P. Besse， and A.D. Falguerolles， “A l1-norm pca and a

heuristic approach，” inOrdinal and Symbolic Data Analysis， E. Diday， Y. Lechevalier， and P. Opitz， Eds，1996.1：359-368

[6] Q. Ke and T. Kanade， “Robust subspace computation using l1

norm，”Tech. Rep.CMU-CS-03-172，Carnegie Mellon University，http：//citeseer.ist.psu.edu/ke03robust.html，2003.8.

[7] Q. Ke and T. Kanade， “Robust l1 norm factorization in the

presence of outliers and missing data by alternative convex programming，” inProc. IEEE Conference on Computer Vision and Pattern Recognition，2005.6.

[8] G. Golub and C.V. Loan， Matrix Computation， Johns Hopkins

University Press，3 edition，1996.