摘 要： 提出一種快速算法，該算法利用貪心算法構造卷數據降維矩陣，在保持點與點之間“核距離”不變的情況下，把待分解矩陣變換成一個低維矩陣。在沒有偏差的情況下，將對原始大矩陣的分解變成對這個低維矩陣的分解，大幅降低了時間復雜度，減少了對內存的使用率的同時增加了算法的穩定性。
關鍵詞： 主成分分析；貪心算法；卷數據降維矩陣；時間復雜度
自從1986年美國人提出PCA[1]的有關思想以后，PCA就成了一個強有力的工具。由于PCA具有最大化方差、最小化冗余、最小化損失等優良特性，它可以廣泛地應用在多源融合、數據降維、模式識別以及分析數據互相關性等方面。如最近發表的基于小波和PCA的火炮輸彈系統故障診斷研究[2]和基于L2，1范數的PCA維數約簡算法[3]，PCA在其中起了提取主元和維數約簡預處理的重要作用。雖然以后出現了大量的其他方法，如CMS[4]、RP[5]和一些非線性的算法，如Isomap[6]、LLE[7]、LTSA[8]等算法，并廣泛地應用在各個領域，如機器學習、圖像檢索、模式識別和人工智能等方面。但是PCA作為一種基本的線性方法，其地位是其他方法所無法比擬的。
近年來，由于計算機技術高速發展，各種數據量以指數級的速度增加，各種大規模數據廣泛地出現在各個計算機領域，如圖像處理中的圖像的分辨度越來越高，數據庫也越來越大。但是目前計算機硬件的發展仍然滿足不了數據處理的要求。比如在人臉識別中，圖像的尺寸為128×128，而整個圖片集又有3 000張，那么在圖像分類中把圖片當成一個列的大矩陣的尺寸將是16 384×3 000，這是非常大的矩陣，計算復雜度高，其中最費時部分就是在最后一步分解矩陣來求得特征向量和特征值。鑒于此提出了一種基于貪心算法[7-8]的快速算法——貪心快速主成分分析，簡稱PCA-G。該算法在保持與PCA相同的處理效果的同時，降低了時間復雜度，增加了算法穩定性減少了內存使用率，從而使計算時間大大縮短。
1 PCA算法簡述
統計學上PCA的定義為：用幾個較少的綜合指標來代替原來較多的指標，而這些較少的綜合指標既能盡量多地反映原來較多指標的有用信息，且相互之間又是無關的。作為一種建立在統計最優原則基礎上的分析方法，主成分分析具有較長的發展歷史。在1901年，Pearson首先將變換引入生物學領域，并重新對線性回歸進行了分析，得出了變換的一種新形式。Hotelling于1933年則將其與心理測驗學領域聯系起來，把離散變量轉變為無關聯系數。在概率論理論建立的同時，主成分分析又單獨出現，由Karhunen于1947年提出，隨后Loeve于1963年將其歸納總結。因此，主成分分析也被稱為K-L變換。
PCA運算就是一種確定一個坐標系統的直交變換，在這個新的坐標系統下，變換數據點的方差沿新的坐標軸得到了最大化。這些坐標軸經常被稱為是主成分。PCA運算是一個利用了數據集的統計性質的特征空間變換，這種變換在無損或很少損失數據集信息的情況下降低了數據集的維數。
1.2 主成分分析的實現步驟
基于上述主成分分析的基本原理，可以得出主成分分析的計算步驟如下所示：
（1）將所獲得的n個指標（每一指標有m個樣品）的一批數據寫成一個（m×n）維數據矩陣：
2 基于貪心算法的PCA快速算法
從式（4）可以看出PCA主要是求樣本協方差矩陣的特征向量和特征值。所以在程序中PCA就轉化為對原始矩陣的SVD分解或者是特征分解。且PCA最費時的就在這一步，針對這一步矩陣分解做出改進。正如現在矩陣正變得越來越大，當矩陣的行數和列數都很大時，無論如何變換矩陣，能降低的時間復雜度都是非常有限的。一般PCA的時間復雜度可以達到O（n3）[9]（其中n為協方差矩陣的行數），所以在遇到行數和列數都很大的協方差矩陣分解時往往很費時。但是要求的往往只是整個矩陣分解出來的幾個特征值或者特征向量，于是找到一個低維矩陣，它保持了降維核上各點距離不變的性質，使最后分解出來的主要特征值和特征向量與原始高維矩陣分解出的主要特征值和特征向量相等。
算法分為以下三步：
3 時間復雜度分析
標準的PCA內置Matlab代碼中eigs函數的時間復雜度高達O（n3）（其中n為協方差矩陣的行數），算法中第一步的時間復雜度等價于O（n），第二步的時間復雜度為O（m2×n），第三步為m2×n，所以總的時間復雜度為O（n2），而標準的SVD算法時間復雜度為O（n3），所以算法時間復雜度要比標準的算法低一階。
4 實驗對比
所有的實驗都是在惠普康柏筆記本上進行的，它的配置是Intel（R）core（TM）i3 M330 2.13 GHz，內存是2 GB，操作系統是Windows 7旗艦版7.0，算法由matlab實現。實驗主要用來計算算法在各種大規模矩陣上計算的快速性，用隨機函數產生n×n矩陣來衡量計算所需要的運行時間。為了進行實驗，使每次計算的n取不同值，且m的值應遠大于d的值，以保證矩陣充分保留了原矩陣的某些特征。這里的d和m取不同的值。在此情況下比較了新算法和標準PCA算法在保證矩陣分解質量前提下的快速性。實驗結果如表1~表12所示。
5 實驗分析與結論
可以從實驗中看到以下幾點：
（1）當矩陣規模比較大時，當n在3 000甚至以上時（見表1~表4），算法在保持分解質量即特征值不變（篇幅有限取最大的前三個）的前提下，速度至少比標準的PCA算法快一倍多。
（2）當所構建的低維空間的維數減小時，如小于12倍的d（見表5~表8），盡管此時運算速度會加快，但是與標準算法相比會出現偏差，當運算精度要求不高，運算時間比較珍貴時，可以采取此法。
（3）當矩陣規模較小時（見表9~表12），算法和標準PCA差別不大，而當構造空間維數降低時，偏差同樣會出現。
通過以上分析可以看出，算法在應用到大規模矩陣時（尤其n當大于3 000時）優越性比較明顯，能明顯地加快算法的處理速度。所以在數據規模越來越大的今天，快速算法有廣泛的用武之地。
參考文獻
[1] JOLLIFFE I T． Principal Component Analysis[M]． New York， USA： Springer-Verlag，1986.
[2] 張鵬軍，薄玉成，王惠源，等.基于小波和ＰＣＡ的火炮輸彈系統故障診斷研究[J].計算機工程與設計，2012，33（12）：4746-4750.
[3] 劉麗敏，樊曉平，廖志芳，等.一種基于Ｌ２，１范數的ＰＣＡ維數約簡算法[J].計算機應用與研究，2012，30（1），39-41.
[4] YOUNG F W. Encyclopedia of statistical sciences[J]. Multidimensio-nal scaling. John Wiley & Sons，Inc，1985，5.
[5] ACHLIOPTAS D. Database-friendly random projections[C]. Proc.20th PODS，2001.
[6] TENENBAUM J B， DE SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction. Science[J]. 2000，290（5500）：2319-2323.
[7] ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science 2000，290（5500），2323-2326.
[8] ZHANG Z Y， ZHA H Y. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J]. SIAM J.Sci.Comput， 2004，26（1）：313-338.
[9] WANG J. Geometric structure of high-dimensional data and dimensionality reduction[M]. Springer， 2012.
[10] CHUI C， WANG J. Dimensionality reduction of hyper-spectral imagery data for feature classification[C]. In：W.Freeden， Z. Nashed， T. Sonar（eds.） handbook of Geomathematics.Springer，berlin，2010.
[11] CHUI C， WANG J. Randomized anisotropic transform for nonlinear dimensionality reduction[J]. International Journal on Geomathematics，2010，1（1）：23-50.