摘  要： 提出一種快速算法，該算法利用貪心算法構(gòu)造卷數(shù)據(jù)降維矩陣，在保持點(diǎn)與點(diǎn)之間“核距離”不變的情況下，把待分解矩陣變換成一個(gè)低維矩陣。在沒(méi)有偏差的情況下，將對(duì)原始大矩陣的分解變成對(duì)這個(gè)低維矩陣的分解，大幅降低了時(shí)間復(fù)雜度，減少了對(duì)內(nèi)存的使用率的同時(shí)增加了算法的穩(wěn)定性。
關(guān)鍵詞： 主成分分析；貪心算法；卷數(shù)據(jù)降維矩陣；時(shí)間復(fù)雜度

　自從1986年美國(guó)人提出PCA[1]的有關(guān)思想以后，PCA就成了一個(gè)強(qiáng)有力的工具。由于PCA具有最大化方差、最小化冗余、最小化損失等優(yōu)良特性，它可以廣泛地應(yīng)用在多源融合、數(shù)據(jù)降維、模式識(shí)別以及分析數(shù)據(jù)互相關(guān)性等方面。如最近發(fā)表的基于小波和PCA的火炮輸彈系統(tǒng)故障診斷研究[2]和基于L2，1范數(shù)的PCA維數(shù)約簡(jiǎn)算法[3]，PCA在其中起了提取主元和維數(shù)約簡(jiǎn)預(yù)處理的重要作用。雖然以后出現(xiàn)了大量的其他方法，如CMS[4]、RP[5]和一些非線性的算法，如Isomap[6]、LLE[7]、LTSA[8]等算法，并廣泛地應(yīng)用在各個(gè)領(lǐng)域，如機(jī)器學(xué)習(xí)、圖像檢索、模式識(shí)別和人工智能等方面。但是PCA作為一種基本的線性方法，其地位是其他方法所無(wú)法比擬的。
　近年來(lái)，由于計(jì)算機(jī)技術(shù)高速發(fā)展，各種數(shù)據(jù)量以指數(shù)級(jí)的速度增加，各種大規(guī)模數(shù)據(jù)廣泛地出現(xiàn)在各個(gè)計(jì)算機(jī)領(lǐng)域，如圖像處理中的圖像的分辨度越來(lái)越高，數(shù)據(jù)庫(kù)也越來(lái)越大。但是目前計(jì)算機(jī)硬件的發(fā)展仍然滿足不了數(shù)據(jù)處理的要求。比如在人臉識(shí)別中，圖像的尺寸為128×128，而整個(gè)圖片集又有3 000張，那么在圖像分類(lèi)中把圖片當(dāng)成一個(gè)列的大矩陣的尺寸將是16 384×3 000，這是非常大的矩陣，計(jì)算復(fù)雜度高，其中最費(fèi)時(shí)部分就是在最后一步分解矩陣來(lái)求得特征向量和特征值。鑒于此提出了一種基于貪心算法[7-8]的快速算法——貪心快速主成分分析，簡(jiǎn)稱PCA-G。該算法在保持與PCA相同的處理效果的同時(shí)，降低了時(shí)間復(fù)雜度，增加了算法穩(wěn)定性減少了內(nèi)存使用率，從而使計(jì)算時(shí)間大大縮短。
1 PCA算法簡(jiǎn)述
　統(tǒng)計(jì)學(xué)上PCA的定義為：用幾個(gè)較少的綜合指標(biāo)來(lái)代替原來(lái)較多的指標(biāo)，而這些較少的綜合指標(biāo)既能盡量多地反映原來(lái)較多指標(biāo)的有用信息，且相互之間又是無(wú)關(guān)的。作為一種建立在統(tǒng)計(jì)最優(yōu)原則基礎(chǔ)上的分析方法，主成分分析具有較長(zhǎng)的發(fā)展歷史。在1901年，Pearson首先將變換引入生物學(xué)領(lǐng)域，并重新對(duì)線性回歸進(jìn)行了分析，得出了變換的一種新形式。Hotelling于1933年則將其與心理測(cè)驗(yàn)學(xué)領(lǐng)域聯(lián)系起來(lái)，把離散變量轉(zhuǎn)變?yōu)闊o(wú)關(guān)聯(lián)系數(shù)。在概率論理論建立的同時(shí)，主成分分析又單獨(dú)出現(xiàn)，由Karhunen于1947年提出，隨后Loeve于1963年將其歸納總結(jié)。因此，主成分分析也被稱為K-L變換。
PCA運(yùn)算就是一種確定一個(gè)坐標(biāo)系統(tǒng)的直交變換，在這個(gè)新的坐標(biāo)系統(tǒng)下，變換數(shù)據(jù)點(diǎn)的方差沿新的坐標(biāo)軸得到了最大化。這些坐標(biāo)軸經(jīng)常被稱為是主成分。PCA運(yùn)算是一個(gè)利用了數(shù)據(jù)集的統(tǒng)計(jì)性質(zhì)的特征空間變換，這種變換在無(wú)損或很少損失數(shù)據(jù)集信息的情況下降低了數(shù)據(jù)集的維數(shù)。


1.2 主成分分析的實(shí)現(xiàn)步驟
　基于上述主成分分析的基本原理，可以得出主成分分析的計(jì)算步驟如下所示：
?。?）將所獲得的n個(gè)指標(biāo)（每一指標(biāo)有m個(gè)樣品）的一批數(shù)據(jù)寫(xiě)成一個(gè)（m×n）維數(shù)據(jù)矩陣：
　
2 基于貪心算法的PCA快速算法
　從式（4）可以看出PCA主要是求樣本協(xié)方差矩陣的特征向量和特征值。所以在程序中PCA就轉(zhuǎn)化為對(duì)原始矩陣的SVD分解或者是特征分解。且PCA最費(fèi)時(shí)的就在這一步，針對(duì)這一步矩陣分解做出改進(jìn)。正如現(xiàn)在矩陣正變得越來(lái)越大，當(dāng)矩陣的行數(shù)和列數(shù)都很大時(shí)，無(wú)論如何變換矩陣，能降低的時(shí)間復(fù)雜度都是非常有限的。一般PCA的時(shí)間復(fù)雜度可以達(dá)到O（n3）[9]（其中n為協(xié)方差矩陣的行數(shù)），所以在遇到行數(shù)和列數(shù)都很大的協(xié)方差矩陣分解時(shí)往往很費(fèi)時(shí)。但是要求的往往只是整個(gè)矩陣分解出來(lái)的幾個(gè)特征值或者特征向量，于是找到一個(gè)低維矩陣，它保持了降維核上各點(diǎn)距離不變的性質(zhì)，使最后分解出來(lái)的主要特征值和特征向量與原始高維矩陣分解出的主要特征值和特征向量相等。
　算法分為以下三步：


3 時(shí)間復(fù)雜度分析
　標(biāo)準(zhǔn)的PCA內(nèi)置Matlab代碼中eigs函數(shù)的時(shí)間復(fù)雜度高達(dá)O（n3）（其中n為協(xié)方差矩陣的行數(shù)），算法中第一步的時(shí)間復(fù)雜度等價(jià)于O（n），第二步的時(shí)間復(fù)雜度為O（m2×n），第三步為m2×n，所以總的時(shí)間復(fù)雜度為O（n2），而標(biāo)準(zhǔn)的SVD算法時(shí)間復(fù)雜度為O（n3），所以算法時(shí)間復(fù)雜度要比標(biāo)準(zhǔn)的算法低一階。
4 實(shí)驗(yàn)對(duì)比
　所有的實(shí)驗(yàn)都是在惠普康柏筆記本上進(jìn)行的，它的配置是Intel（R）core（TM）i3 M330 2.13 GHz，內(nèi)存是2 GB，操作系統(tǒng)是Windows 7旗艦版7.0，算法由matlab實(shí)現(xiàn)。實(shí)驗(yàn)主要用來(lái)計(jì)算算法在各種大規(guī)模矩陣上計(jì)算的快速性，用隨機(jī)函數(shù)產(chǎn)生n×n矩陣來(lái)衡量計(jì)算所需要的運(yùn)行時(shí)間。為了進(jìn)行實(shí)驗(yàn)，使每次計(jì)算的n取不同值，且m的值應(yīng)遠(yuǎn)大于d的值，以保證矩陣充分保留了原矩陣的某些特征。這里的d和m取不同的值。在此情況下比較了新算法和標(biāo)準(zhǔn)PCA算法在保證矩陣分解質(zhì)量前提下的快速性。實(shí)驗(yàn)結(jié)果如表1~表12所示。
5 實(shí)驗(yàn)分析與結(jié)論
　可以從實(shí)驗(yàn)中看到以下幾點(diǎn)：
?。?）當(dāng)矩陣規(guī)模比較大時(shí)，當(dāng)n在3 000甚至以上時(shí)（見(jiàn)表1~表4），算法在保持分解質(zhì)量即特征值不變（篇幅有限取最大的前三個(gè)）的前提下，速度至少比標(biāo)準(zhǔn)的PCA算法快一倍多。

　（2）當(dāng)所構(gòu)建的低維空間的維數(shù)減小時(shí)，如小于12倍的d（見(jiàn)表5~表8），盡管此時(shí)運(yùn)算速度會(huì)加快，但是與標(biāo)準(zhǔn)算法相比會(huì)出現(xiàn)偏差，當(dāng)運(yùn)算精度要求不高，運(yùn)算時(shí)間比較珍貴時(shí)，可以采取此法。

?。?）當(dāng)矩陣規(guī)模較小時(shí)（見(jiàn)表9~表12），算法和標(biāo)準(zhǔn)PCA差別不大，而當(dāng)構(gòu)造空間維數(shù)降低時(shí)，偏差同樣會(huì)出現(xiàn)。
　通過(guò)以上分析可以看出，算法在應(yīng)用到大規(guī)模矩陣時(shí)（尤其n當(dāng)大于3 000時(shí)）優(yōu)越性比較明顯，能明顯地加快算法的處理速度。所以在數(shù)據(jù)規(guī)模越來(lái)越大的今天，快速算法有廣泛的用武之地。
參考文獻(xiàn)
[1] JOLLIFFE I T． Principal Component Analysis[M]． New York， USA： Springer-Verlag，1986.
[2] 張鵬軍，薄玉成，王惠源，等.基于小波和ＰＣＡ的火炮輸彈系統(tǒng)故障診斷研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（12）：4746-4750.
[3] 劉麗敏，樊曉平，廖志芳，等.一種基于Ｌ２，１范數(shù)的ＰＣＡ維數(shù)約簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用與研究，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.