基于核主成分分析的數據流降維研究

五邑大學 計算機學院，廣東 江門 529020

五邑大學 計算機學院，廣東 江門 529020

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

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

（1）壓縮數據以減少存儲量；

（2）去除噪聲的影響；

（3）從數據中提取特征以便于進行分類或聚類；

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

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

1 降維的定義及算法

1.1 降維的定義

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

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

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

1.2 降維算法

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

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

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

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

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

2 核方法與基于KPCA降維算法的改進

2.1 核方法

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

圖1 核方法框架示意圖

實質上，核方法實現了數據空間、特征空間、類別空間之間的非線性變換。圖1中，xi和xj為數據空間中的樣本點，數據空間到特征空間的映射函數為φ，核函數的基礎是實現向量的內積變換：

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

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

2.2 KPCA基本原理

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

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

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

從而有：

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

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

定義M×M的矩陣K：

則式（7）可轉化為：

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

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

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

2.3 KPCA實現步驟

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

（2）選取適當的核函數，計算核矩陣K，本文中選取高斯徑向基（RBF）核函數：

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

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

（5）將特征值按降序排列，并調整與其對應的特征向量。

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

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

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

2.4 GKPCA算法的提出

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

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

設原始樣本記錄數為N，現將其分為G組，則每組記錄數目為：

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

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

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

（1）重新采樣并進行分組，形成G組樣本。

（2）對每一組執行KPCA，并對樣本進行過濾。

（3）組合過濾后的樣本，形成新的樣本數據集，并再次執行KPCA算法，對樣本進一步過濾。

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

3 實驗與分析

表1 數據集Spect降維結果

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

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

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

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

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

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

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

圖2 原始數據分布圖

圖4 經過KPCA降維后的數據分布

圖3 經過PCA降維后的數據分布

圖5 經過GKPCA降維后的數據分布

表2 測試樣例的降維結果

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

4 結束語

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

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

[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]譚璐.高維數據的降維理論及應用[D].長沙：國防科技大學，2005：7-8.

[3]吳玲達，賀玲，蔡益朝.高維索引機制中的降維方法綜述[J].計算機應用研究，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].中國機械工程，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]王瀛，郭雷，梁楠.基于優選樣本的KPCA高光譜圖像降維方法[J].光子學報，2011，40（6）：847-851.

[10]Burgers K，Fessehatsion 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]王國勝.核函數的性質及其構造方法[J].計算機科學，2006：172-178.

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

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

基于核主成分分析的數據流降維研究

高宏賓，侯 杰，李瑞光

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

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

核主成分分析；數據流；降維

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.

廣東省自然科學基金（No.S2011010003681）。

高宏賓（1960—），男，在讀博士，副教授，碩士生導師，主要研究領域為數據挖掘與分布式計算、算法設計與分析；侯杰（1986—），男，碩士研究生，CCF會員，研究方向為數據挖掘與分布式計算、算法設計與分析；李瑞光（1985—），男，碩士研究生，研究方向為數據挖掘與分布式計算、算法設計與分析。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