基于L1—范數最優化的主成分分析

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

關鍵詞： PCA-L1； L1-范數； 優化； 主成分分析； 魯棒性

中圖分類號：TP391.4 文獻標志碼：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 引言

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

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

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

1 基于L1-范數最大化的PCA

1.1 理論分析

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

⑴ 計算

⑴

式⑴中，是投影矩陣的列構成m維線性子空間（即特征空間），是系數矩陣，（i，j）組件vij對應著xj的第i個坐標中的m維特征空間W，是L2-范數的矩陣或向量的表示。

⑵ 求解目標函數

⑵

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

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

⑶

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

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

⑷

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

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

⑸

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

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

⑹

1.2 算法步驟

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

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

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

⑷ 收斂性檢驗：

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

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

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

2 實驗

2.1 實驗數據

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

表1 實驗中使用的UCI數據集

[數據集＼維數＼類數＼樣本數＼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 實驗結果與分析

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

（a） Australian （b） Balance

（c） Breast cancer （d） Dermatology

（e） Heart disease （f） Ionosphere

（g） Liver （h） Sonar

圖1 多個UCI數據集的實驗結果

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

表2 UCI數據集的計算時間和平均迭代次數

[＼ 平均時間（毫秒）＼平均迭代次數＼數據集＼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個的投影矢量與提取的特征數量的變化有關，所以計算的時間和R1-PCA迭代次數是提取不同數目的特征平均值。另一方面，L2-PCA和PCA-L1的時間和迭代提取的特征的數目等于輸入變量個數時獲得的數據。例如， R1-PCA時間為25500毫秒=750毫秒×34，而L2-PCA和PCA-L1的平均時間分別為62毫秒和750毫秒。在表2中，我們可以看出在許多情況下用PCA-L1的時間少于R1-PCA，并且在波形的數據集中PCA-L1的迭代次數少于15次。

3 結束語

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

參考文獻：

[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.