五邑大學(xué) 計算機(jī)學(xué)院，廣東 江門 529020

五邑大學(xué) 計算機(jī)學(xué)院，廣東 江門 529020

隨著科學(xué)技術(shù)的發(fā)展，人們不斷接觸到各種類型的數(shù)據(jù)，如圖像數(shù)據(jù)、文本數(shù)據(jù)、醫(yī)學(xué)信息數(shù)據(jù)、金融市場交易數(shù)據(jù)、天文數(shù)據(jù)等，大多數(shù)情況下這些數(shù)據(jù)具有多維空間屬性，在統(tǒng)計處理中稱之為“高維數(shù)據(jù)”，且具有數(shù)據(jù)流（Data Stream）性質(zhì)。數(shù)據(jù)的高維度和流的形式給數(shù)據(jù)處理帶來巨大的挑戰(zhàn)，例如，當(dāng)處理256×256的圖片序列時，通常將圖像數(shù)據(jù)拉成一個向量，這樣，得到一系列4 096維的數(shù)據(jù)序列，如果直接對這些數(shù)據(jù)進(jìn)行處理，巨大的計算量將使人們無法忍受，即“數(shù)據(jù)維災(zāi)”，同時這些數(shù)據(jù)通常沒有反映出數(shù)據(jù)的本質(zhì)特征，如果直接對它們進(jìn)行處理，不會得到理想的結(jié)果。所以需要對數(shù)據(jù)進(jìn)行降維，將數(shù)據(jù)的維數(shù)降到合適大小，同時盡可能多地保留原數(shù)據(jù)信息，然后對降維后的數(shù)據(jù)進(jìn)行處理[1]。

降維是將高維模式映射到低維子空間的過程，其主要目的有：

（1）壓縮數(shù)據(jù)以減少存儲量；

（2）去除噪聲的影響；

（3）從數(shù)據(jù)中提取特征以便于進(jìn)行分類或聚類；

（4）將數(shù)據(jù)投影到低維空間，便于理解數(shù)據(jù)分布。

本文討論了高維數(shù)據(jù)降維的定義及常用算法，接著對核主成分分析（KPCA）進(jìn)行研究，并提出一種計算效率更高的分組核主成分分析（GKPCA）算法，實驗數(shù)據(jù)表明，該算法能有效地對數(shù)據(jù)流進(jìn)行特征提取，實現(xiàn)高維數(shù)據(jù)降維。

1 降維的定義及算法

1.1 降維的定義

（1）高維數(shù)據(jù)空間，ΩD，通常為RD的某一個子集。

（2）降維空間（或稱低維表示空間），Ωd。

（3）映射函數(shù)φ稱 y為x的降維表示。

1.2 降維算法

目前，數(shù)據(jù)降維方法主要分為兩類[3]：線性降維和非線性降維。

線性降維包括：主成分分析（Principle Component Analysis，PCA）、獨立成分分析（Indispensable Component Analysis，ICA）、線性判別分析（Linear Discriminate Analysis，LDA）、投影尋蹤（Projection Pursuit，PP）等；PCA是一種基于二階統(tǒng)計的數(shù)據(jù)分析方法，該方法在各個變量之間相關(guān)系研究的基礎(chǔ)上，用一組較少的、互不相關(guān)的新變量代替原來較多的變量，而且使這些新變量盡可能多地保留原來復(fù)雜變量所反映的信息，具體計算步驟可參看文獻(xiàn)[4]。

非線性降維算法包括：核方法、多維尺度方法（Multidimensional Scaling，MDS）、等距離映射算法（ISOMAP）、局部線性嵌入（Locally Linear Embedding，LLE）[5]等。

核主成分分析作為PCA方法的在處理非線性問題時的擴(kuò)展，近年來得到了快速的發(fā)展，其主要思想是通過某種事先選擇的非線性映射函數(shù)將輸入矢量映射到一個高維線性特征空間，然后在特征空間中使用PCA方法計算主成分[6]。在具備了PCA所有數(shù)學(xué)特性的前提下，KPCA還有如下特征：KPCA比PCA提供更優(yōu)的識別性；KPCA的計算復(fù)雜度不因變換空間的維數(shù)增加而加大，僅與輸入空間的維數(shù)相關(guān)。目前KPCA的思想已經(jīng)被世界上廣大的科研人員所接受，廣泛應(yīng)用到特征提取、人臉識別[7]、圖像識別[8]、光譜降維分析[9-10]、數(shù)據(jù)分類聚類以及故障監(jiān)控診斷等領(lǐng)域。

由于KPCA的計算復(fù)雜度是和樣本數(shù)密切相關(guān)的，對于一個 N×N的核矩陣（N為樣本數(shù)），其時間復(fù)雜度為O(N3)，當(dāng)N很大時，KPCA的計算代價會快速增長，因此需要對KPCA算法進(jìn)行優(yōu)化，文獻(xiàn)[11]介紹了一種將求解PCA的期望最大算法（EM）推廣到求解KPCA，但該算法占用存儲空間較大，且收斂性不能保證。下面將著重介紹核主成分分析方法與在此基礎(chǔ)上的改進(jìn)算法。

2 核方法與基于KPCA降維算法的改進(jìn)

2.1 核方法

核方法一種由線性到非線性之間的橋梁，起源于20世紀(jì)初葉，是一系列先進(jìn)性數(shù)據(jù)處理技術(shù)的總稱，共同點是這些方法中都用到了核映射。核函數(shù)方法的基本原理是通過非線性函數(shù)把輸入空間映射到高維空間，在特征空間中進(jìn)行數(shù)據(jù)處理，其關(guān)鍵在于通過引入核函數(shù)，把非線性變換后的特征空間內(nèi)積運算轉(zhuǎn)換為原始空間的核函數(shù)計算，從而簡化了計算量。其操作過程如圖1所示。

圖1 核方法框架示意圖

實質(zhì)上，核方法實現(xiàn)了數(shù)據(jù)空間、特征空間、類別空間之間的非線性變換。圖1中，xi和xj為數(shù)據(jù)空間中的樣本點，數(shù)據(jù)空間到特征空間的映射函數(shù)為φ，核函數(shù)的基礎(chǔ)是實現(xiàn)向量的內(nèi)積變換：

在滿足Mercer條件[12]下，設(shè)輸入空間的數(shù)據(jù)為 xi∈(i=1，2，…，N)，對于任意對稱連續(xù)的函數(shù) K(xi，xj)，存在一個Hilbert空間，對映射φ:→H ，有：

其中dF為H的空間維數(shù)。這進(jìn)一步說明，輸入空間的核函數(shù)實際上與特征空間的內(nèi)積是等價的，由于在核方法的各種實際應(yīng)用中，只需要應(yīng)用特征空間的內(nèi)積，而不需要了解具體映射φ的具體形式，即：在使用核方法時只需要考慮如何選定一個合適的核函數(shù)，無需關(guān)心與之對應(yīng)的映射φ是否具有復(fù)雜的表達(dá)式。具體核函數(shù)的性質(zhì)及其構(gòu)造方法可參看文獻(xiàn)[13]。

2.2 KPCA基本原理

對于經(jīng)典的PCA算法，通過求解特征方程 λν=Cν，λ為C的一個特征值，ν為相應(yīng)的特征向量，以此來獲得貢獻(xiàn)率較大的特征值和與之對應(yīng)的特征向量?，F(xiàn)引入非線性映射函數(shù)φ，使輸入空間中樣本點 x1，x2，…，xM變換為特征空間中的樣本點 φ(x1)，φ(x2)，…，φ(xM)，假設(shè)：

則在特征空間F中，其協(xié)方差矩陣為：

因此，特征空間F的特征值和特征向量求解即求解方程：

從而有：

特征向量ν可以線性表示為：

由式（3）（5）（6）得：

定義M×M的矩陣K：

則式（7）可轉(zhuǎn)化為：

求解式（9）即可獲得映射空間上的特征值和特征向量。測試樣本在F空間向量Vk上的投影為：

如果特征空間中數(shù)據(jù)不滿足中心化條件，則需要對和矩陣進(jìn)行修正，用下式中的K代替式（9）中的K：

式（11）中，對于所有的 i，j，li，j=1[14]。

2.3 KPCA實現(xiàn)步驟

（1）從數(shù)據(jù)流中獲取m條數(shù)據(jù)記錄（每條記錄有n個屬性），將其表示成m×n維的矩陣：

（2）選取適當(dāng)?shù)暮撕瘮?shù)，計算核矩陣K，本文中選取高斯徑向基（RBF）核函數(shù)：

（3）修正核矩陣 K，得 KL。

（4）計算 KL 的特征值 λ1，λ2，…，λn和特征向量 ν1，ν2，…，νn。

（5）將特征值按降序排列，并調(diào)整與其對應(yīng)的特征向量。

（6）利用Gram-Schmidt正交法單位化特征向量，得到α1，α2，…，αn。

（7）計算特征值的累積貢獻(xiàn)率 B1，B2，…，Bn，根據(jù)給定的提取效率 p，如果 Bt≥p，則提取 t個主分量 α1，α2，…，αt。

（8）計算已修正的核矩陣KL，在提取出的特征向量上的投影Y=KL·α ，其中 α=(α1，α2，…，αt)；所得的投影Y 即為數(shù)據(jù)經(jīng)KPCA降維后所得數(shù)據(jù)。

2.4 GKPCA算法的提出

由于KPCA是基于樣本的，算法的時間復(fù)雜度和空間復(fù)雜度與數(shù)據(jù)流維數(shù)無關(guān)，但是與樣本記錄數(shù)目卻密切相關(guān)，對于小型高維數(shù)據(jù)流，KPCA能夠很好地完成降維，隨著樣本記錄數(shù)目的增多，KPCA的時間復(fù)雜度和空間復(fù)雜度也會增加。

為了降低計算時間與內(nèi)存消耗，提出一種分組的KPCA算法，即將原始樣本先分成若干組，對每一組數(shù)據(jù)進(jìn)行過濾，然后再運用KPCA算法。

設(shè)原始樣本記錄數(shù)為N，現(xiàn)將其分為G組，則每組記錄數(shù)目為：

第i(i=1，2，…，G)組中與第一投影方向相對應(yīng)的系數(shù)向量為αi：

對每一組進(jìn)行數(shù)據(jù)過濾，設(shè)過濾閾值為ζ，αi按降序排列，設(shè)排序后為 β，β滿足：β1≥β2≥…≥βG，經(jīng)過數(shù)據(jù)過濾后，設(shè)保留下來的記錄數(shù)目為 Lefti(i=1，2，…，G)，則Lefti由下式?jīng)Q定：

ζ越大，過濾掉的樣本記錄越少，否則越多。這樣，每組數(shù)據(jù)過濾后形成新的樣本集，并對新樣本集進(jìn)行KPCA算法，形成最終的投影方向。GKPCA算法的實現(xiàn)步驟為：

（1）重新采樣并進(jìn)行分組，形成G組樣本。

（2）對每一組執(zhí)行KPCA，并對樣本進(jìn)行過濾。

（3）組合過濾后的樣本，形成新的樣本數(shù)據(jù)集，并再次執(zhí)行KPCA算法，對樣本進(jìn)一步過濾。

（4）獲得GKPCA的特征投影。

3 實驗與分析

表1 數(shù)據(jù)集Spect降維結(jié)果

實驗環(huán)境：本文在Matlab下對PCA、KPCA和GKPCA進(jìn)行模擬仿真，配置環(huán)境為Pentium4，2.8 GHz CPU，內(nèi)存1 GB，Windows XP操作系統(tǒng)，采用的數(shù)據(jù)流為“SPECTF心臟數(shù)據(jù)”（http：//archive.ics.uci.edu/ml/machine-learningdatabases/spect/），該數(shù)據(jù)集來源為美國俄亥俄州醫(yī)學(xué)院，曾應(yīng)用在“知識發(fā)現(xiàn)方法自動心臟顯像診斷”（Artificial Intelligence in Medicine）。數(shù)據(jù)集描述心臟單個質(zhì)子發(fā)射計算機(jī)斷層顯像（SPECT）影像診斷。每個病人分為兩類：正常（1）和不正常（0）。測試數(shù)據(jù)集包含了187條實例，每條實例有45個屬性，一組二進(jìn)制數(shù)據(jù)和44組連續(xù)數(shù)據(jù)，連續(xù)數(shù)據(jù)取值為[0，100]。

測試結(jié)果：實驗選取提取效率 p=0.95，過濾閾值ζ= 0.8，分組數(shù)為3，分析了PCA、KPCA和GKPCA算法的降維效果和計算時間，并進(jìn)行了對比，圖2～圖5分別顯示了原始數(shù)據(jù)集分布、PCA降維后數(shù)據(jù)分布、KPCA降維后數(shù)據(jù)分布和GKPCA降維后的數(shù)據(jù)分布。

通過降維結(jié)果分布圖的對比與分析，可以看出，三種算法都有效地實現(xiàn)了數(shù)據(jù)降維，且相對于PCA和KPCA算法，GKPCA算法的降維效果更好。

表1對比了三種算法降維后的數(shù)據(jù)集維數(shù)和計算時間，從表1中可以看出，KPCA算法有效地實現(xiàn)了數(shù)據(jù)降維，但時間開銷較大，GKPCA算法不僅實現(xiàn)了數(shù)據(jù)簡約，而且縮短了計算時間。

以上測試是在小規(guī)模數(shù)據(jù)集上進(jìn)行的，對于較大的數(shù)據(jù)集，采用了“阿拉伯口語數(shù)字?jǐn)?shù)據(jù)集”（http：//archive.ics. uci.edu/ml/machine-learning-databases/00195/），該數(shù)據(jù)集顯示了阿拉伯口語數(shù)字的梅爾頻率倒普系數(shù)時間序列，數(shù)據(jù)來自阿拉伯本地的44位男性和44位女性。該數(shù)據(jù)集曾應(yīng)用于語音識別等領(lǐng)域[15]。數(shù)據(jù)集包含兩部分，一部分用于實驗測試，共有87 063條實例，另一部分用于實驗訓(xùn)練，共有269 856條實例，兩個數(shù)據(jù)集中每行都含有13個梅爾頻率屬性。本實驗截取測試數(shù)據(jù)集的部分?jǐn)?shù)據(jù)，逐步增加測試用例，來檢驗PCA、KPCA與GKPCA的運行效率。

實驗分別采取了189×n(1≤n≤7)個測試樣例，選取提取效率 p=0.95，過濾閾值ζ=0.8，分組數(shù)為9，時間消耗如圖6所示，降維效果如表2所示。

由圖6可以看出，隨著數(shù)據(jù)量的增大，PCA算法處理時間基本上沒有發(fā)生變化，但KPCA的時間消耗呈指數(shù)級增長，在時間效率上，GKPCA對KPCA改進(jìn)很大。由表2可以看出，PCA降維效果比較差，由原來的13維降為11或12維，KPCA比PCA降維效果好，但是時間消耗大，也不是理想的選擇，GKPCA在保證時間消耗可以接受的范圍內(nèi)，有效地實現(xiàn)了數(shù)據(jù)流降維。

圖2 原始數(shù)據(jù)分布圖

圖4 經(jīng)過KPCA降維后的數(shù)據(jù)分布

圖3 經(jīng)過PCA降維后的數(shù)據(jù)分布

圖5 經(jīng)過GKPCA降維后的數(shù)據(jù)分布

表2 測試樣例的降維結(jié)果

圖6PCA、KPCA與GKPCA時間耗用圖

4 結(jié)束語

KPCA其特點是特征提取速度快、特征信息保留充分，被廣泛應(yīng)用在信息處理中。實質(zhì)上是在特征空間中進(jìn)行PCA分析，在特征空間中，它有著和PCA相同的特性，既保留了PCA的優(yōu)點，又有處理非線性問題的能力。KPCA又與PCA有著本質(zhì)的區(qū)別：PCA是基于指標(biāo)的，KPCA是基于樣本的。KPCA不僅適合于解決非線性特征提取問題，而且還能獲取比PCA更多的主分量。對于m條記錄的n維樣本，PCA能獲取n個主分量，KPCA能獲取m-1個主分量。

提出的GKPCA算法是KPCA算法的改進(jìn)，主要在時間復(fù)雜度和空間復(fù)雜度上進(jìn)行優(yōu)化，提出樣本分組和過濾策略，從而簡化樣本。實驗表明，GKPCA算法在保證貢獻(xiàn)率不降低的前提下，縮短了高維數(shù)據(jù)流降維時間，提高了降維效率。但核函數(shù)與樣本參數(shù)都需要人為選擇，這就容易對降維造成主觀性誤差，且隨著數(shù)據(jù)量的增大，GKPCA仍然不會達(dá)到PCA的時間標(biāo)準(zhǔn)，KPCA算法仍有待改進(jìn)。

[1]De Backer S，Naud A，Scheunders P.Non-linear dimensionality reduction techniques for unsupervised feature extraction[J]. Pattern Recognition Letters，1998，19：711-720.

[2]譚璐.高維數(shù)據(jù)的降維理論及應(yīng)用[D].長沙：國防科技大學(xué)，2005：7-8.

[3]吳玲達(dá)，賀玲，蔡益朝.高維索引機(jī)制中的降維方法綜述[J].計算機(jī)應(yīng)用研究，2006，23（12）：4-7.

[4]Jolliffe I T.Principal component analysis[M].2nd ed.New York：Springer，2002.

[5]Saul L K，Roweis S T.An introduction to locally linear embedding[EB/OL].（2001-03-14）.http：//www.cs.nyu.edu/～roweis/lle/ publications.html.

[6]梁勝杰，張志華，崔立林.主成分分析法與核主成分分析法在機(jī)械噪聲數(shù)據(jù)降維中的應(yīng)用比較[J].中國機(jī)械工程，2011，22（1）：80-83.

[7]Tamilnadu S，Tamilnadu C.Enhancing face recognition using improved dimensionality reduction and feature extraction algorithms-an evaluation with orldatabase[J].International Journal of Engineering Science and Technology，2010，2（6）：2288-2295.

[8]Teixeira A R，Tomé A M，Stadlthanner K，et al.KPCA denoising and the pre-image problem revisited[J].DigitalSignal Processing，2008，18（4）：568-580.

[9]王瀛，郭雷，梁楠.基于優(yōu)選樣本的KPCA高光譜圖像降維方法[J].光子學(xué)報，2011，40（6）：847-851.

[10]Burgers K，F(xiàn)essehatsion Y，Rahmani S，et al.A comparative analysis of dimension reduction algorithms on hyperspectraldata[EB/OL].（2009-07-28）.http：//www.math.ucla.edu/～wittman.

[11]Rosipal R，Girolami M.An expectation-maximization approach to nonlinear componentanalysis[J].NeuralComputation，2001，13（1）：505-510.

[12]Baudat G，Anouar F.Generalized discriminant analysis using akernelfunction[J].NeuralComputing，2000，12（10）：2385-2404.

[13]王國勝.核函數(shù)的性質(zhì)及其構(gòu)造方法[J].計算機(jī)科學(xué)，2006：172-178.

[14]高緒偉.核PCA特征提取方法及其應(yīng)用研究[D].南京：南京航空航天大學(xué)，2009：15-17.

[15]HammamiN，BeddaM.Improved tree model for arabic speechre cognition[C]//Proc IEEE ICCSIT10 Conference，2010.

基于核主成分分析的數(shù)據(jù)流降維研究

高宏賓，侯 杰，李瑞光

GAO Hongbin,HOU Jie,LI Ruiguang

School of Computer Science and Technology,Wuyi University,Jiangmen,Guangdong 529020,China

Theory and implementation of two data stream dimension reduction algorithms,PCA and KPCA,are analyzed.Due to linear PCA and KPCA can not effectively reduce data stream dimension when applied over large scale stream data,a new dimension reduction technique called GKPCA is proposed.With GKPCA,data sets are first partitioned into groups,and then KPCA is applied over each group.Data sets are filtered and regrouped into a new dataset.KPCA is again evaluated over the new data sets.This process is preceding recursively when some reduction threshold is reached which simplifies data stream sampling space and reduces time and space complexity of KPCA.Experimental analysis over different datasets illustrates that GKPCA can reduce data stream dimension excellently with less time consumption.

Kernel Principal Component Analysis（KPCA）;data stream;dimension reduction

分析了數(shù)據(jù)流降維算法PCA和KPCA的原理和實現(xiàn)方法。針對在大型數(shù)據(jù)集上PCA線性降維無法有效實現(xiàn)降維且KPCA的降維效率差，提出了一種新的降維策略GKPCA算法。該算法將數(shù)據(jù)集先分組，對每一組執(zhí)行KPCA，然后過濾重新組合數(shù)據(jù)集，再次應(yīng)用KPCA算法，達(dá)到簡化樣本空間，降低了時間復(fù)雜度和空間復(fù)雜度。實驗分析表明，GKPCA算法不僅能取得良好的降維效果，而且時間消耗少。

核主成分分析；數(shù)據(jù)流；降維

A

TP39

10.3778/j.issn.1002-8331.1110-0295

GAO Hongbin,HOU Jie,LI Ruiguang.Research on dimension reduction of data stream based on kernel principal component analysis.Computer Engineering and Applications,2013,49（11）：105-109.

廣東省自然科學(xué)基金（No.S2011010003681）。

高宏賓（1960—），男，在讀博士，副教授，碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)挖掘與分布式計算、算法設(shè)計與分析；侯杰（1986—），男，碩士研究生，CCF會員，研究方向為數(shù)據(jù)挖掘與分布式計算、算法設(shè)計與分析；李瑞光（1985—），男，碩士研究生，研究方向為數(shù)據(jù)挖掘與分布式計算、算法設(shè)計與分析。E-mail：tn10000@126.com

2011-10-17

2011-12-06

1002-8331（2013）11-0105-05

CNKI出版日期：2012-03-08 http://www.cnki.net/kcms/detail/11.2127.TP.20120308.1521.046.html