張素智，陳小妮，楊 芮，李鵬輝，蔡 強

(1.鄭州輕工業(yè)大學 計算機與通信工程學院，河南 鄭州 450002；2.北京工商大學 食品安全大數(shù)據技術北京市重點實驗室，北京 100048)

0 引 言

近年來，隨著信息技術的不斷發(fā)展，數(shù)據信息爆炸式增長，導致數(shù)據的復雜度越來越大，數(shù)據類型多種多樣，進而引發(fā)了數(shù)據的“維數(shù)災難”。傳統(tǒng)的數(shù)據挖掘技術在處理這樣的高維數(shù)據中面臨著巨大挑戰(zhàn)，無論從資源上還是時效上，都需要更高的要求[1]。大數(shù)據降維算法就是要研究一種有效、簡單的數(shù)據表示，將數(shù)據的維數(shù)降到適合處理的大小，從而消除數(shù)據冗余，使數(shù)據分析處理和存儲變得高效低耗。通過數(shù)據降維得到高維數(shù)據的低維表示，是大數(shù)據分析的關鍵問題。

數(shù)據降維算法廣泛應用于遺傳學、醫(yī)學和生物信息學等領域[2]。目前，國內外研究人員針對數(shù)據降維算法已經進行了大量的研究。文獻[3]詳細介紹了PCA算法的基本思想以及具體算法實現(xiàn)。由于傳統(tǒng)的PCA算法存在占內存較大的問題，文獻[4]引入了信息熵的思想，提出了基于信息熵的主成分分析(E-PCA)算法。在數(shù)據采用PCA算法降維之前，先利用信息熵先對數(shù)據進行特征篩選，不僅提高了降維結果，同時降低了內存占用，減少了運行時間。E-PCA算法雖然在某種程度上對PCA算法進行了改進，但其降維后數(shù)據的判別性能較低。對此，文獻[5]針對超光譜圖像高維和計算復雜兩個特點，提出了一種基于超光譜圖像的帶監(jiān)督提取技術，該方法具有較好的分類精度和Kappa系數(shù)；文獻[6]提出了一種邊界判別MDP算法，通過最大化類間最大距離，最小化類內最小距離，從而提升了數(shù)據低維表示的判別能力，但其對于高維數(shù)據的降維效果不太理想。因此，如何在保證降維效果的前提下，同時提高數(shù)據低維表示的判別能力是值得進一步研究的。針對以上問題，本文將類內和類間距離的思想引入E-PCA算法中，提出了一種基于類內和類間距離的主成分分析算法—IOPCA。

1 相關工作

1.1 主成分分析

主成分分析(PCA)算法是一種常用的數(shù)據降維方法[7]。該方法的基本思想是將n維特征映射到k維。這k維特征被稱為主成分，是在原有n維特征基礎上重新構造出來的特征，而且所包含信息與原n維特征所包含的信息基本一致。

假設樣本數(shù)據集X∈Rn，其中X={x1，x2，…，xn}，每一個樣本數(shù)據xi(i=1，2，…，n)包含m個特征屬性，即(l1，l2，…，lm)。經過PCA線性變換后，轉換到主成分空間的數(shù)據Y由k維的主成分組成。其中Y和X的關系可以用式(1)表示

Y=A′X

(1)

PCA算法的基本原理：首先將原始數(shù)據轉換為矩陣，并實現(xiàn)矩陣的零均值化；之后計算矩陣的協(xié)方差矩陣，求出協(xié)方差矩陣的特征值和特征向量；然后將特征向量按對應的特征值大小從上到下排列成矩陣，選取矩陣的前k行組成的新矩陣即為算法的投影矩陣；最后利用式(1)求解出的矩陣就是降維后矩陣[8]。

1.2 信息熵

信息熵表示對信源考慮所有可能情況的平均不確定性。例如：一個信源發(fā)出n種取值的信號，記為W={w1，w2，…，wn}，n種信號對應的概率分別為P={p1，p2，…，pn}，并且所有概率之和為1。那么，信源的平均不確定性為單個信號的不確定性的統(tǒng)計平均值，稱為信息熵，如式(2)所示

(2)

信息熵在不同的領域具有不同的含義，對于一個系統(tǒng)來說，信息熵的大小可以用來衡量該系統(tǒng)的有序或混亂程度，具體來說，一個系統(tǒng)越有序，則該系統(tǒng)的信息熵越低；相反，一個系統(tǒng)越混亂，則信息熵越高[9]。對于數(shù)據特征來說，信息熵的大小可以用來表示該屬性所提供的信息量的大小。如果一個屬性的信息熵越大，則該屬性所包含的信息量越大；反之，則包含的信息量越小[10]。基于以上所述，可以將信息熵引入主成分分析(PCA)算法中，通過與信息熵閾值a比較，來判斷該屬性是否剔除。從而減小算法的計算量以及數(shù)據內存空間占用量。

1.3 類內和類間距離

為了增強原始數(shù)據低維表示的判別能力，本文在PCA算法的基礎上引入了類內和類間距離[11]。通過實現(xiàn)類間距離最大化，類內距離最小化，來提高低維數(shù)據對分類的貢獻。樣本間的類內距離和類間距離一般指的是歐式距離，具體定義如下。

定義1 假設有兩個任意給定的樣本，記為x1和x2，則該樣本之間的距離d(x1，x2)為式(3)所示

(3)

定義2 假設有兩個不同類別的樣本集合，分別記為cm和cn，分別在兩個類別中選取兩個樣本點xi(?xi∈cm)和xj(?xj∈cn)，則d(cm，cn)為兩個類別間的距離，又稱類間距離，如式(4)所示

(4)

定義3 給定同一個類別ci的任意兩個樣本點，分別記為xa(?xa∈ci)和xb(?xb∈ci)，則d(ci)為類別內的距離，又稱類內距離，如式(5)所示

(5)

(6)

(7)

根據式(4)和式(5)可以求得樣本數(shù)據X的邊界，如式(8)所示

(8)

其中，J代表樣本數(shù)據邊界，m表示樣本的類別數(shù)，ci和cj屬于不同的類別。

一般通過最大化不同類樣本邊界距離和最小化同類樣本邊界距離，來實現(xiàn)數(shù)據低維表示的類間距離最大化和類內距離最小化。具體思想如圖1所示。

圖1 類內距離最小化和類間距離最大化的基本思想

其中，圖1中圓形表示一個類別，方形表示不同于圓形的另一個類別。實線表示類間距離，虛線表示類內距離，虛線和實線連接的樣本點統(tǒng)稱為邊界樣本點。從圖1中可以看出，變換后實線變長，虛線變短，邊界距離增強。因此可以分析出，變換后的樣本數(shù)據具有較強的可分性。

根據式(8)，可以得出，實現(xiàn)類內距離最小化和類間距離最大化就是實現(xiàn)低維空間的樣本數(shù)據邊界最大，如式(9)

(9)

其中，?(ci,cj)、?(ci)分別是低維空間的類間距離和類內距離。

在此引入正交約束，如式(10)，根據定義4和定義5，可以將?(ci,cj)，?(ci)分別展開，如式(11)和(12)所示

VTV=I

(10)

(11)

(12)

結合式(10)，將式(11)和式(12)代入到式(9)得到式(13)。通過求解式(13)，找到滿足低維空間類內距離最小化、類間距離最大化的投影矩陣V

(13)

邊界判別投影(MDP)數(shù)據降維算法較好實現(xiàn)了最小化同類樣本間的最大距離，最大化不同類樣本間的最小距離。借助MDP算法的優(yōu)化目標函數(shù)[12]，如式(14)所示。通過求解目標函數(shù)中的投影矩陣V，即可實現(xiàn)投影后矩陣邊界最大化

maxtr(VT(S(b)-S(w))V)

(14)

其中，S(b)=XL(b)XT，S(w)=XL(w)XT，L(b)和L(w)是Laplacian矩陣，分別代表樣本數(shù)據同類樣本間的近鄰關系和異類樣本間的近鄰關系。

2 基于類內和類間距離的主成分分析算法

2.1 算法基本思想

數(shù)據維數(shù)的不斷提高，形式也越來越復雜。從而使對高維數(shù)據進行分析處理越來越難。為了在盡量保留數(shù)據信息的情況下降低數(shù)據的維度，同時增強數(shù)據低維表示的判別能力，使低維表示的數(shù)據更有利于分類。因此，本文引入信息熵、類間距離和類內距離的思想。提出了基于類間和類內距離的數(shù)據降維(IOPCA)算法。該算法思想如圖2所示，圖中左側是原始數(shù)據分布，右側是降維后的數(shù)據分布。圖中的不同形狀代表不同的類別，實線代表同類間樣本點的距離，虛線代表異類間樣本點的距離。從圖中可以看出，數(shù)據經過降維處理后，從高維變?yōu)榈途S，同時類內距離變小，類間距離變大。

圖2 IOPCA數(shù)據降維算法的基本思想

2.2 算法主要內容

2.2.1 算法流程

基于類間和類內距離的數(shù)據降維(IOPCA)算法的基本處理流程如圖3所示。首先，在對高維數(shù)據降維前，通過采用信息熵進行屬性篩選，降低算法的計算量，減小數(shù)據的占內存空間；然后，用基于類間和類內距離思想的數(shù)據降維目標函數(shù)求解投影矩陣，代替PCA算法利用協(xié)方差矩陣求解主成分，從而得到PCA算法的優(yōu)化算法；最后，將屬性篩選后的矩陣用PCA算法的優(yōu)化算法進行降維。

圖3 基于類內和類間距離的主成分分析算法流程

2.2.2 算法介紹

基于類內和類間距離的PCA數(shù)據降維(IOPCA)算法與E-PCA算法，相同之處在于對數(shù)據進行降維之前都將屬性的信息熵與信息熵閾值a對比，進行了一次特征篩選；不同之處在于IOPCA算法在對篩選后數(shù)據的降維過程中充分考慮了類間距離和類內距離，從而實現(xiàn)了投影到低維空間數(shù)據的類間距離最大化，類內距離最小化。具體算法步驟如下。

輸入：數(shù)據矩陣Pd×n，n表示樣本數(shù)目，d代表樣本維度，每個樣本對應的類別為label(xi)∈C，其中C={c1,c2,…,ck}，信息熵閾值a，貢獻率f。

輸出：降維結果。

(1)計算每個屬性的信息熵值，通過與閾值a比較，進行特征篩選。

(2)進行樣本矩陣中心化，計算得矩陣Xd×n

X=A-repmat(mean(A,2),1,n)

(15)

(3)計算Laplacian矩陣L

L=L(b)-L(w)

(16)

(4)采用不完全Cholesky分解技術對數(shù)據矩陣X進行QR分解，分解結果如式(17)所示

X=QR

(17)

(5)求解矩陣Z=RLRT，計算Z的特征值(eigenVa-lue)和特征向量(eigenVector)。

(6)對矩陣Z特征分解，求得矩陣U=[u1,u2,…,ur]，其中，ui是矩陣Z的第r個最大特征值λi對應的特征向量。

(7)選定投影矩陣V。投影矩陣如下公式所示

V=QU

(18)

(8)計算降維結果Y

Y=VTX=(QU)TQR=UTR

(19)

(9)算法結束。

IOPCA算法中的r值不作為參數(shù)輸入，r值的確定與特征值的貢獻率f有關，IOPCA算法中貢獻率計算與PCA算法中一樣，指的是選取屬性值與樣本中的所有屬性值的和的比值。計算公式如下所示

(20)

3 實 驗

為了驗證IOPCA算法的有效性，本文將IOPCA算法與PCA、E-PCA、LDA算法，從降維結果以及降維后數(shù)據經過KNN、SVM算法的分類精確度上進行比較。

3.1 環(huán)境和數(shù)據集

實驗環(huán)境：本文在MATLAB R2014a下對PCA、E-PCA、LDA和IOPCA進行模擬仿真，配置環(huán)境為Pen-tium4，2.8 GHz CPU，內存1 GB，Windows XP系統(tǒng)。

數(shù)據集：為了更全面分析4種降維算法的性能，本文從UCI標準數(shù)據庫[13]中選取4種數(shù)據集進行實驗，包括：Iris數(shù)據集，150個樣本，4個屬性，3個類；Soybean(large)數(shù)據集，307個樣本，35個屬性，18個類；Sonar數(shù)據集，208個樣本，2個類，60個特征；SPECTF incorrect數(shù)據集，269個樣本，2個類，44個特征。

3.2 結果及分析

(1)降維結果

通過對4種數(shù)據集采用PCA、E-PCA、LDA和IOPCA降維方法在MATLAB進行實驗，設置PCA、E-PCA、IOPCA的貢獻率f=0.95，在實驗過程中信息熵閾值根據數(shù)據集的屬性信息熵來選取。實驗得到的降維結果見表1。從表1可以看出，當E-PCA算法中的信息熵閾值為0時，E-PCA等價于PCA。另外，對于Iris數(shù)據集，本文方法和PCA、E-PCA方法的降維結果一樣，優(yōu)于LDA方法；然而，對于其它3種數(shù)據集，本文方法的降維結果均優(yōu)于PCA、E-PCA和LDA方法。

表1 4種數(shù)據集在不同降維方法下的降維結果

(2)分類精確度

分別將4種數(shù)據集通過PCA、E-PCA、LDA和IOPCA進行降維處理，按照表2所示的測試集樣本數(shù)和訓練集樣本數(shù)來分配，采用KNN和SVM算法進行分類，并與4種原始數(shù)據采用KNN和SVM進行分類的分類精確度進行對比。分類實驗均重復10次取精確度平均值。實驗結果見表3～表6。

表2 4種數(shù)據集的樣本數(shù)量

Iris數(shù)據集降維前后經過KNN、SVM算法的分類精確度見表3。通過表3可以看出，將Iris數(shù)據集經過PCA、E-PCA算法降維后的數(shù)據，作為KNN、SVM算法的輸入，分類精確度略有降低；而將Iris數(shù)據集經過LDA算法降維后的數(shù)據，作為KNN、SVM算法的輸入，分類精確度分別提高約1.6和0.67個百分點，同樣采用IOPCA算法降維，分類精確度分別提高約5.41和1.89個百分點。

表3 Iris數(shù)據集降維后經過KNN、SVM算法的分類精確度/%

Soybean(large)數(shù)據集降維前后經過KNN、SVM算法的分類精確度見表4。分析表4可以得出，該數(shù)據集采用PCA、E-PCA降維后的數(shù)據經過KNN、SVM算法的分類精確度均降低約0.5～1.0個百分點，采用LDA降維后的數(shù)據經過KNN、SVM算法的分類精確度分別提高約11.43和0.57個百分點，同樣的采用IOPCA算法，分類精確度分別提高約13.14和1.86個百分點。

表4 Soybean(large)數(shù)據集降維后經過KNN、SVM算法的分類精確度/%

Sonar數(shù)據集降維前后經過KNN、SVM算法的分類精確度見表5。從表5中可以看出，Sonar數(shù)據集相比于SVM更加適合使用KNN算法進行分類。另外，該數(shù)據集采用PCA、E-PCA降維后的數(shù)據經過KNN、SVM算法的分類精確度均降低約0.5～1.0個百分點，采用LDA算法降維后的數(shù)據經過KNN、SVM算法的分類精確度分別提高約10.25和2.5個百分點，同樣的采用IOPCA算法，分類精確度分別提高約14.46和5.44個百分點。

SPECTF incorrect數(shù)據集降維前后經過KNN、SVM算法的分類精確度見表6。從表6中可以看出，該數(shù)據集采用PCA、E-PCA降維后的數(shù)據經過KNN、SVM算法的分類精確度均降低約2個百分點，采用LDA算法降維后的數(shù)據經過KNN、SVM算法的分類精確度分別提高約0.8和1.66個百分點，同樣采用IOPCA算法，分類精確度分別提高約2.94和3.58個百分點。

表5 Sonar數(shù)據集降維后經過KNN、SVM算法的分類精確度/%

表6 SPECTF incorrect數(shù)據集降維后經過KNN、SVM算法的分類精確度/%

為了更直觀衡量算法的有效性，單獨比較數(shù)據集降維處理前以及采用4種方法降維處理后分別經過KNN和SVM算法的分類精確度。結果如圖4和圖5所示。

圖4 4種數(shù)據集采用KNN算法的分類精確度

圖5 4種數(shù)據集采用SVM算法的分類精確度

綜合分析表3～表6和柱狀圖4、圖5可得，PCA和E-PCA算法雖然實現(xiàn)了數(shù)據維度減少的結果，但是同時也降低了數(shù)據的分類能力，原因在于將數(shù)據從高維空間向低維空間映射時，沒有對類間距離做太多的考慮。而LDA和IOPCA算法在有效降低數(shù)據維度的同時，提高了數(shù)據的分類能力。因此，從降維后數(shù)據的分類判別能力上來說，本文所提出的IOPCA算法相對其它3類降維算法較好。

4 結束語

由于傳統(tǒng)的主成分分析數(shù)據降維方法提取的低維表示的判別性能較低，本文給出了基于類內和類間距離的主成分分析數(shù)據降維方法，該方法將類內和類間距離的思想引入到PCA算法中，通過最大化不同類別間的最小距離，同時最小化同類別間的最大距離，來增強數(shù)據低維表示的判別性能。在MATLAB環(huán)境中，通過與PCA、E-PCA、LDA方法進行對比,結果表明IOPCA算法不僅提高了數(shù)據的降維效果，同時提高了降維后低維數(shù)據的判別性能。但是在實驗過程中，只將該方法與數(shù)據降維的其它幾種線性方法進行了比較，而且實驗所用數(shù)據集類型覆蓋面不夠廣。因此，下一步工作，將本文提出的IOPCA方法與幾種非線性數(shù)據降維方法進行比較，如：Laplacian Eigenmaps(LE)、局部線性嵌入(LLE)等，從而對本文所提算法更加全面地做出評價，并做出進一步改進。