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

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

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

0 引 言

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

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

1 相關工作

1.1 主成分分析

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

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

Y=A′X

(1)

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

1.2 信息熵

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

(2)

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

1.3 類內和類間距離

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

定義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)可以求得樣本數據X的邊界，如式(8)所示

(8)

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

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

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

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

根據式(8)，可以得出，實現類內距離最小化和類間距離最大化就是實現低維空間的樣本數據邊界最大，如式(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)數據降維算法較好實現了最小化同類樣本間的最大距離，最大化不同類樣本間的最小距離。借助MDP算法的優化目標函數[12]，如式(14)所示。通過求解目標函數中的投影矩陣V，即可實現投影后矩陣邊界最大化

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

(14)

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

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

2.1 算法基本思想

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

圖2 IOPCA數據降維算法的基本思想

2.2 算法主要內容

2.2.1 算法流程

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

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

2.2.2 算法介紹

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

輸入：數據矩陣Pd×n，n表示樣本數目，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分解技術對數據矩陣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值不作為參數輸入，r值的確定與特征值的貢獻率f有關，IOPCA算法中貢獻率計算與PCA算法中一樣，指的是選取屬性值與樣本中的所有屬性值的和的比值。計算公式如下所示

(20)

3 實 驗

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

3.1 環境和數據集

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

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

3.2 結果及分析

(1)降維結果

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

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

(2)分類精確度

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

表2 4種數據集的樣本數量

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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