一個解決大數(shù)據(jù)集問題的核主成分分析算法

1、一個解決大數(shù)據(jù)集問題的核主成分分析算法史衛(wèi)亞郭躍飛：薛向陽（復(fù)旦大學(xué)計算機(jī)科學(xué)與技術(shù)系，上海200433）An efficient Kernel Principal Component Analysis Algorithm for large-scale data setShi Weiya, Guo Yue-Fei+, Xue Xiangyang（Department of Computer Science and Technology, Fudan University, Shanghai 200433, China）+ Corresponding author: Phn: +86-21-6

2、5643922, Fax:+86-21-65643922, E-mail: .cAbstract : Kernel principal component analysis （KPCA） is a popular nonlinear feature extraction method in the field of machine learning. It uses eigen-decomposition technique to extract the principal components. But the method is infeasible for l

3、arge-scale data set because of the store and computational problem. To overcome these disadvantages, a new covariance-free method of computing kernel principal components is proposed. First, a matrix, called Gram-power matrix, is constructed using the original Gram matrix. It is proven by the theore

4、m of linear algebra that the eigenvectors of newly constructed matrix are the same as the ones of the Gram matrix. Therefore, we can treat each column of the Gram matrix as the input sample for the covariance-free algorithm. Thus, the kernel principle components can be iteratively computed without t

5、he eigen-decomposition. The space complexity of proposed method is only O（/H ,the time complexity is reduced to O（pkm） .The effectiveness of proposed method is validated from experimental results. More important, it still can be used even if traditional eigen-decomposition technique cannot be applie

6、d when faced with the extremely large-scale data set.Key words :KPCA; Gram matrix; large-scale data set; covariance-free; eigen-decomposition摘要：核主成分分析是一種流行的非線性特征提取方法。一般情況下它使用特征分解技術(shù)提取核主成分，但是在大數(shù)據(jù)集情況下因為儲存和計算問題是不可行的。為了解決這個問題，本文提岀一種大數(shù)據(jù)集求解核主成 分的計算方法。首先使用Gram矩陣生成一個Gram-power矩陣，根據(jù)線性代數(shù)的理論可知新形成的矩陣和原先的Gra m矩陣具

7、有相同的特征向量。因此，我們可以把Gra m矩陣的每一列看成核空間迭代算法的輸入樣本，通過迭代計算岀核主成分。提岀的算法的空間復(fù)雜度只有，在大數(shù)據(jù)集的情況下時間復(fù)雜度也降低為<.。實驗結(jié)果證明了所提岀算法的有效性。更為重要的是當(dāng)傳統(tǒng)的特征分解技術(shù)無法使用的情況下，所提岀的方法仍然可以提取非線性特征。關(guān)鍵詞：核主成分分析;Gram矩陣;大數(shù)據(jù)集；協(xié)方差無關(guān)；特征分解中圖法分類號：TP301 文獻(xiàn)標(biāo)識碼：A主成分分析是一種用于特征提取和維度減少的經(jīng)典方法1。該方法一般使用具有較大方差的主成分而忽略較少重要的成分。盡管主成分分析成功用于維度減少，但是在非線性數(shù)據(jù)分布情況下該方法不是太好。通常使

8、 用核方法2將其推廣到核空間使用。其主要思想是把數(shù)據(jù)映射到高維的特征空間，在映射的特征空間中，可以 使用傳統(tǒng)的線性算法而實現(xiàn)非線性特征的特征提取。其中不用知道映射函數(shù)而采用核技巧就可以計算數(shù)據(jù)之間 的內(nèi)積。提取的非線性特征被用于許多復(fù)雜的應(yīng)用中，例如人臉識別，圖像壓縮等。在標(biāo)準(zhǔn)的核主成分計算過程中，需要儲存所有數(shù)據(jù)形成的Gram矩陣3，其空間復(fù)雜度為（：（，-.，其中m? t he Key Project of the Ministry of Education of China under Grant No.104075（教育部科學(xué)技術(shù)研究重點(diǎn)項目 ）;the National Key Te

9、chnology R&D Program of China under Grant No.2007BAH09B03（國家科技支撐計劃課題 ）;the National High Technology Research and Development Program of China under Grant No. 2007AA01Z176 （國家高技術(shù)研究發(fā)展計劃資助項目（ 863計劃）表示樣本數(shù)。另外，對 Gram矩陣進(jìn)行特征分解的時間復(fù)雜度為.,，；。因為有限的內(nèi)存容量，當(dāng)大數(shù)據(jù)集情況下該方法是不可行的。鄭4提岀把數(shù)據(jù)集分成若干小的數(shù)據(jù)集，然后分別處理。貪婪的核主成分分析方法5通過

10、采樣訓(xùn)練集而近似求解特征向量。但是這些方法仍然存在較大的儲存問題。在6中，通過把傳統(tǒng)的廣義Hebbia n算法擴(kuò)展到核空間迭代的求解核主成分，可以避免儲存問題，但是這種方法的收斂性不能保證。本文提岀了一種大數(shù)據(jù)集情況下有效的求解核主成分的方法。主要思想是利用線性代數(shù)中對稱矩陣的性 質(zhì)，首先使用初始的Gram矩陣創(chuàng)建一個新的Gram-power矩陣。因為新構(gòu)成的矩陣和原先的矩陣具有相同的特征 向量，所以我們可以把 Gram矩陣的每一列看成核空間迭代算法7的輸入樣本。通過若干迭代后，可以很容易的求岀核主成分。所提岀的方法不需要事先存儲Gram矩陣，空間復(fù)雜度從（:.減少到；。另外算法的快速收斂性已

11、經(jīng)被證明8。更為重要的是處理非常大數(shù)據(jù)集情況下，傳統(tǒng)的特征分解技術(shù)沒法使用，所提岀的方法仍然可以較好的提取非線性特征。通過在人工合成的數(shù)據(jù)集以及真實的數(shù)據(jù)上進(jìn)行實驗，充分證明了所提岀 算法的有效性。下一部分對核主成分的實現(xiàn)過程進(jìn)行回顧，同時把常用的一些迭代算法進(jìn)行比較；在第二部分詳細(xì)描述本 文所提岀的方法；然后給岀實驗結(jié)果證明提岀算法的有效性；最后給予總結(jié)。1核主成分分析的回顧和迭代算法分析1 1核主成分分析的回顧假定-|是輸入空間的數(shù)據(jù)集，其中| ：是d維向量，m是數(shù)據(jù)集中的總樣本數(shù)。存在一個函數(shù).把數(shù)據(jù)映射到高維（甚至無限維）的希爾伯特空間。6 :陽一> F屮（1）（“2伸g沖。一個

12、核函數(shù)被<<:，這樣在映射（2）（3）向量和特征值。因為解I可以用全部數(shù)據(jù)集的召T啊兀）使用這個映射函數(shù)，我們可以得到特征空間的數(shù)據(jù)集用于計算這些映射數(shù)據(jù)樣本之間的內(nèi)積，這個核函數(shù)定義為的特征空間協(xié)方差定義為：它符合特征方程：CV = X.V其中丫和L分別對應(yīng)協(xié)方差矩陣的特征（"2他（旺）神區(qū)），沖 O 張程表示為：將公式3和4代到公式2中，可以推導(dǎo)出下面的公式：- =（5）其中"是張程系數(shù)，人是Gram矩陣，定義為/.|.| :1.；。該矩陣的元素為理論證明9Gram矩陣是半正定的。為了計算核主成分，一般都是對Gram矩陣采用特征分解的方法。這樣得到特征向量M

13、后，可以使用公式4計算核主成分丫。對于任何一個測試樣本 A'，其非線性特征為：W4）=2円他（舛網(wǎng)）MO”)史衛(wèi)亞等：一個解決大數(shù)據(jù)集問題的核主成分分析算法在上面的推導(dǎo)中是假定所有數(shù)據(jù)具有零均值的，如果不是的，可以得到°，其中：。1 2迭代算法分析因為傳統(tǒng)的特征分解方法需要非常大的內(nèi)存。為了克服這個不便，一些計算主成分的迭代方法被提岀，例 如GHA 10, APEX 11。但是這些方法一般收斂速度較慢。翁7利用統(tǒng)計學(xué)上的效能估計概念提出了一個增量的協(xié)方差無關(guān)的方法，該方法不是像傳統(tǒng)方法一樣特征分解協(xié)方差矩陣I,而是循環(huán)地輸入樣本向量.V.，與其它迭代方法相比起來，收斂速度快，

14、而且計算復(fù)雜度很低。因此我們選用這種方法作為 所提岀算法的迭代工具。2提出的核主成分算法一般情況下，映射函數(shù)是不知道的，因此，特征空間的樣本向量沒法明確表示，這樣在核空間就沒有辦法 使用上述迭代方法計算核主成分。為了解決這個問題并給岀我們的方法，首先給岀一個線性代數(shù)的定理1213。定理：矩陣一T和；，具有相同的特征向量和不同的特征值。 證明：假定山和八分別是矩陣的特征向量和特征值，,5 - . -（7）（8）因此，矩陣二 的特征向量和特征值即為 U.I和，。2 1提出的方法因為Gram矩陣人是半正定的，可以得到. _二，因此可以構(gòu)造一個矩陣Gram-power ，定義為=.:V V =。根據(jù)前

15、面的定理，新構(gòu)造的矩陣 （；的特征向量； 與Gram矩陣打的特征向量'相同，但有不同的特征值，和，（；.=；：*）。=（K 聞Kg）（K 鼬）KQr其中 編.訃 十.因此，我們可以把矩陣 二的每一列：，作為迭代算法7的輸入樣 本，這樣經(jīng)過一些迭代后，就可以迅速得到矩陣仃的特征向量。而不用像傳統(tǒng)方法那樣對 Gram矩陣打特征分解。因為在實際計算中，我們每次只需計算：，從而有效地解決了大樣本需要存儲 Gra m矩陣的問題。下面，我們具體給出求解矩陣G的特征向量的算法過程。根據(jù)定義，新構(gòu)造的Gram-power矩陣的特征向量和特征值,符合下面的公式：(10)其中冷打是特征向量在第n時刻估計，

16、在得到特征向量后，可以很容易的計算特征向量；：| ' | ：.|和特征值。因為現(xiàn)在的 輸入樣本"為爪：；衣 I. |：，因此可以依次將樣本 .、輸入到迭 代算法中，這樣在n時刻第i階核主成分的估計.i 可以表示為：(兀)（ii）u s -1）11叫（科一1）117(崔-1)II "-1)11(丹 -1) + K (兀)K, (x)H其中.是計算第i階核主成分時在t時刻的輸入樣本。其它高階特征向量可以用殘留的數(shù)據(jù)向量計算。而殘留的數(shù)據(jù)向量是用最初數(shù)據(jù)減去其在低階特征向量的投影（<0r(M)(!>.(/»)I卩5)1 I迪何I這樣通過迭代計算就可以

17、得到需要的特征向量和特征值。算法概括如下：1 使用前補(bǔ)個樣本初始化前階特征向量.2 lteration=1: p進(jìn)行下面計算3 ： _:.進(jìn)行下面計算4 ; 進(jìn)行下面計算5 對每個輸入樣本，計算相應(yīng)的I，作為輸入向量6 使用公式11和12計算前乂階主成分7 轉(zhuǎn)到步驟48 轉(zhuǎn)到步驟39 轉(zhuǎn)到步驟210輸岀特征向量和特征值/2 2算法的復(fù)雜度分析整個計算過程中，不需要特征分解Gram矩陣，因為這樣空間復(fù)雜度是< n ：.，時間復(fù)雜度是 0（）相反，在每一步只處理樣本 -， 其復(fù)雜度只有:， 這樣經(jīng)過一些迭代后就可以得到核主成分。因為算法需要經(jīng)過一些迭代，總的時間復(fù)雜度為< 1（，其中-

18、分別為迭代次數(shù)，特征向量數(shù)目和總的樣本數(shù)。在大樣本數(shù)據(jù)集情況下，迭代次數(shù)和提取向量的數(shù)目遠(yuǎn)小于樣本數(shù)目。因此所提岀算法時間復(fù)雜度也大大 降低。史衛(wèi)亞等：一個解決大數(shù)據(jù)集問題的核主成分分析算法 3實驗結(jié)果和討論為驗證提出算法的有效性，我們使用標(biāo)準(zhǔn)的KPCA算法和提出的方法在一個具有 3聚類，2維的簡單問題上進(jìn)行實驗。除此之外，還使用 USPS數(shù)據(jù)集在圖像降噪和分類上驗證提出算法的可行性。實驗中如果沒有明確說 明，核函數(shù)使用高斯核 （耳y）=円（"丁削） （疔 是核函數(shù)的寬度參數(shù)，一般需要通過交叉驗證而確2cr2定）。§ Eig0nvalue=5.GG6I 呂 Eig8nval

19、uB=4.950D1Fig. 1 Contour image of first 3 principal components obtained from proposed method （the top row） and standard KPCA （the bottom row）.圖.1使用提岀的方法（上行）與標(biāo)準(zhǔn)的方法（下行）產(chǎn)生的前三個主成分的輪廓圖。模擬問題：2維的數(shù)據(jù)集含有三個聚類，每個聚類有三十個樣本，都具有高斯分布，其均值分別為-0.5-0.2, 0 0.6, 0.5 0，標(biāo)準(zhǔn)方差為0.1，核參數(shù) 宀為0.1.前3個特征值123嘉5.5564.950.247入托22.55820.

20、9364.648Table1 Experiment result of the first 3 eigenvalues （ '：r）表.1使用兩種方法得到的前三個特征值（福（入/彷）圖1給岀了實驗結(jié)果，它表征了兩種方法提取的前三個核主成分的輪廓圖，灰度值代表測試樣本投影的非線性特征值。所得到的對應(yīng)特征值在表1中列岀。其中/和二 分別是用提岀方法和標(biāo)準(zhǔn)的方法得到的特征值。從結(jié)果可以清晰的看到，提岀方法可以得到與標(biāo)準(zhǔn)方法類似的結(jié)果。另外，我們還比較兩種方法產(chǎn)生的前3個特征向量的平均內(nèi)積隨迭代次數(shù)的變化，結(jié)果見圖2,從圖中可以觀察到，經(jīng)過一些迭代后，所提岀的方法得到的特征向量非常好的收斂到標(biāo)

21、準(zhǔn)方法產(chǎn)生的特征向量。9 B 7 G 5 O.D.6O.O.ICqumA uwm-mw希 4口 -unpcuEl.一口口丄IIIIIIIIII102030409060700090100HEiatianf'M)Fig.2 Average dot product of first 3 principal components obtained from standard KPCA and the proposed method.圖.2使用標(biāo)準(zhǔn)方法和提岀方法所得到的前三個特征向量的平均內(nèi)積。USPS數(shù)據(jù)集：接下來我們在一些標(biāo)準(zhǔn)數(shù)據(jù)集上測試提出的方法。USPS數(shù)據(jù)集是256維的字符向量，含有7

22、291個訓(xùn)練樣本和2007個測試樣本。在這個實驗中核參數(shù) ，丫設(shè)置為一 -汀/,其中d是數(shù)據(jù)向量的維度，c設(shè) 置為數(shù)據(jù)平均方差的兩倍。Fig.3 De-nosing results obtained by different methods. First row: original image; Second row: noisy image; Third row: de-noising result by batch KPCA; Fourth row: de-noising result by proposed method.圖.3使用兩種方法得到的圖像降噪結(jié)果。從上到下分別為原圖像、加噪圖

23、像、使用標(biāo)準(zhǔn)方法以及本方法經(jīng)過降噪處理后得到的圖像。首先使用提取的特征進(jìn)行降噪實驗。隨機(jī)取3000個訓(xùn)練樣本用標(biāo)準(zhǔn)的KPCA和提出方法進(jìn)行訓(xùn)練，提取前 64個主成分。測試樣本用均值為 0,方差為0.5的高斯噪聲迭加。利用提取的非線性特征進(jìn)行重組圖像，實驗結(jié)果見 圖3,從圖中可以看到兩種方法重組的圖像都獲得了很好的降噪效果。為了進(jìn)一步驗證提岀的方法，我們使用所有的訓(xùn)練樣本來提取非線性特征，實驗中使用多項式核（d為多項式度）。在這種情況下Gram矩陣的大小為7291x7291，如果用標(biāo)準(zhǔn)的KPCA方法因為樣本數(shù)目太大，沒法進(jìn)行計算。但是我們提岀的方法仍然可以提取核主成分。測試樣本在提取的前64個主

24、成分上進(jìn)行投影，然后用最近鄰方法進(jìn)行分類，表2給岀了分類的誤差率。數(shù)據(jù)表明提岀的方法在大樣本情況下獲得了較好的分類效果。提取的主成分?jǐn)?shù)d=23456645.886.136.577.067.25Table 2 Error rate of 2007 testing sample of USPS data set using the proposed method （%）.表2使用本方法在USPS數(shù)據(jù)集上用全部訓(xùn)練樣本訓(xùn)練，使用最近鄰分類方法得到的測試樣本的誤 差率（%）.史衛(wèi)亞等：一個解決大數(shù)據(jù)集問題的核主成分分析算法4結(jié)束語本文提出了一種大數(shù)據(jù)集情況下提取核主成分的有效方法。方法首先利用Gram

25、矩陣構(gòu)造一個Gram-power矩陣，因為兩個矩陣有相同的特征向量，因此不需要像傳統(tǒng)方法一樣特征分解Gram矩陣，而是用Gram矩陣的每一列作為每一步迭代算法的輸入樣本。這樣可以有效解決傳統(tǒng)方法在大數(shù)據(jù)集下無法使用的問題。提岀的方法空間復(fù)雜度減少為，時間復(fù)雜度也降低為.。更為重要的是，當(dāng)樣本數(shù)目非常大時，所提岀方法仍然可以提取非線性特征。References:1 Kirby 丫 and Sirovich L. Application of the Karhunen-loeve Procedure for the Characterization of Human Faces. IEEE Tra

26、ns. Pattern Anal.Mach. Intell., 1990,12(1):103108.2 Scholkopf B and Smola A. Learning with kernel: Support Vector Machines,Regularization,Optimization and Beyond.,London,England, MIT Press, 2002,25-553 Scholkopf B, Smola A, and Muller KR. Nonlinear component analysis as a kernel eigenvalue problem.

27、Neural computation,1998,10 , 1299-1319.4 Zheng W, Zou C and Zhao L. An improved Algorithm for Kernel Principal Components Analysis. Neural Processing Letters, 2005,22, 49-56.5 France V and Hlavac V. Greedy algorithm for a training set reduction in the kernel methods. in: Proc. Int.conf.Computer Anal

28、ysis of Images and patterns,2003, 426-433.6 Kim KI, Franz MO, and Scholkopf B. Iterative kernel component analysis for image modeling. IEEE Trans Pattern Analysis. Machine. Intelligent,2005, 27(9):1351-1366.7 Weng J, Zhang 丫 and Huang WS. Candid covariance-free incremental principal component analysis. IEEE Trans Pattern Analysis. Machine. In