改進(jìn)的局部線性嵌入及其混成數(shù)據(jù)降維算法?

馬思遠(yuǎn) 賀 萍

（河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 石家莊 050061）

1 引言

隨著數(shù)據(jù)收集和數(shù)據(jù)存儲功能技術(shù)的發(fā)展，高維數(shù)據(jù)的處理已經(jīng)成為圖像、視頻、文本文檔等許多領(lǐng)域的重要問題。通常情況下，高維數(shù)據(jù)集中存在大量不相關(guān)和冗余的特征，這增加了數(shù)據(jù)處理、知識挖掘和模式分類的難度［1~2］。而降維可以將高維數(shù)據(jù)投影到低維子空間，濾除一些噪聲和冗余信息［3］。

主成分分析（PCA）是一種經(jīng)典的非監(jiān)督學(xué)習(xí)的機(jī)器學(xué)習(xí)算法，常用于解決數(shù)據(jù)降維、異常分析、算法加速和數(shù)據(jù)可視化等問題，已經(jīng)廣泛應(yīng)用于圖形分類、模式識別和機(jī)器視覺等領(lǐng)域；基于核的主成分分析是對主成分分析方法的一種線性推廣，與PCA 相比，核PCA 具有有效獲取數(shù)據(jù)的非線性特征、對原始空間中的數(shù)據(jù)分布情況無要求且計算復(fù)雜度基本沒有增加等優(yōu)點(diǎn)，這些特點(diǎn)使核PCA在諸多領(lǐng)域應(yīng)用后取得了很好的效果。局部線性嵌入（LLE）是一種廣泛使用的圖像降維方法，可以學(xué)習(xí)任意維度的局部線性的低維流形，實(shí)現(xiàn)簡單，計算量相對較小，可以保持?jǐn)?shù)據(jù)局部的幾何關(guān)系。

本文的創(chuàng)新點(diǎn)如下：1）對局部線性嵌入進(jìn)行了改進(jìn)，選擇最短路徑算法計算樣本點(diǎn)間的距離，改進(jìn)樣本點(diǎn)的相似度量方式；2）使用改進(jìn)的局部線性嵌入降維局部數(shù)據(jù)集，基于核的主成分分析降維整個數(shù)據(jù)集。在基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文提出的方法在一定程度上提高了PCA 對平移的魯棒性，表現(xiàn)出良好的分類性能。

2 相關(guān)工作

目前常用的降維方法可以分為兩種類型，包括基于特征選擇的方法［4~7］和基于特征變換的方法［8~10］。基于特征選擇的降維方法是根據(jù)特定條件對原始特征進(jìn)行排序，然后選擇排名最高的特征以形成子集。其中，基于Fisher 評分［11］、基于信息獲?。?2］、基于互信息［13］和基于基尼系數(shù)［14］進(jìn)行的特征選擇方法是經(jīng)典的特征選擇方法。特征選擇方法可以有效地去除不相關(guān)的特征，但原始集的潛在結(jié)構(gòu)將可能被破壞［15］。基于特征變換的降維方法的本質(zhì)是通過指定的變換函數(shù)將高維數(shù)據(jù)映射到低維空間，這種降維方法通常會保留要素之間的原始相對距離，并有助于覆蓋原始數(shù)據(jù)的潛在結(jié)構(gòu)，因此不會造成大量信息丟失。其中，主成分分析（Principle Component Analysis，PCA）［16］、局部線性嵌入（Local Linear Embedding，LLE）［17］、等距映射（Isometric Feature Mapping，Isomap）［18］、局部切空間排列（Local Tangent Space Alignment，LTSA）［19］、隨機(jī)近鄰嵌入（T-Distribution Stochastic Neighbour Embedding，t-SNE）［20］、拉普拉特映射（Laplacian Ei?genmap，LE）［21］是典型的基于特征變換的降維方法。

PCA算法是一種常用的降維算法，具有去除噪聲、無參數(shù)限制、簡化計算過程等優(yōu)點(diǎn)。近年來提出了許多與PCA 結(jié)合提高數(shù)據(jù)分類性能的改進(jìn)算法。Meng 等［15］利用聚類策略與混合運(yùn)算相結(jié)合的方法，提出一種基于特征選擇和分組特征提取的新型快速混合降維算法。該方法使用兩種不同的特征選擇方法刪除不相關(guān)的特征，利用特征之間的冗余度將特征分組為一定數(shù)量的簇，使用PCA對簇進(jìn)行提取保留有效特征，該方法不僅可以去除數(shù)據(jù)的無關(guān)信息和冗余信息，而且考慮了集合的潛在結(jié)構(gòu)、數(shù)據(jù)大小和維度的多樣性。為了解決判別分析（Linear Discriminant Analysis，LDA）小樣本問題，一些研究者將PCA 與LDA 結(jié)合，首先使用PCA 提取特征，刪除原始數(shù)據(jù)的空間，然后使用LDA 實(shí)現(xiàn)進(jìn)一步的維數(shù)縮減［22］，但此方法將降維過程分為兩個獨(dú)立的部分，忽略了PCA對LDA的影響。Zhao等［23］在此基礎(chǔ)上提出了一種組合PCA 和LDA 的降維算法（JPCDA），用規(guī)則參數(shù)γ平衡PCA和LDA對模型的影響，使用正規(guī)化項(xiàng)提取對LDA 重要的有效信息，該方法不僅不需要考慮類內(nèi)散布矩陣的奇異性，還解決了LDA的小樣本問題。藍(lán)雯飛等［24］為了降低數(shù)據(jù)集降維時間，提出了一種融合PCA和LLE的降維算法（PCA_LLE），既保留了數(shù)據(jù)的全局結(jié)構(gòu)，同時保持高維的數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)在低維中不變。

但PCA的缺陷在于其空間復(fù)雜度比較高［25］，且不能應(yīng)用于非線性降維。為了將PCA 成熟的思想更好地應(yīng)用于非線性降維，且在一定程度上減少核PCA［26］的高計算復(fù)雜度，本文提出了一種基于LLE思想與核PCA 相結(jié)合的方法，在該算法中首先對LLE 進(jìn)行了改進(jìn)，使用最短路徑算法計算兩個樣本點(diǎn)間的測地距離；在此基礎(chǔ)上使用局部線性嵌入與核主成分分析（KPCA）混成的降維算法對數(shù)據(jù)集進(jìn)行降維。最后在基準(zhǔn)數(shù)據(jù)集上進(jìn)行了算法性能對比，在Isolet 以及Yale 數(shù)據(jù)集上取得較好的實(shí)驗(yàn)效果。

3 基本概念

3.1 PCA算法

主成分分析又稱主元分析、K-L 變換，它由Pearson于1931年首次提出。PCA 的基本思想是提取原始數(shù)據(jù)中的主元，減少數(shù)據(jù)冗余，使得數(shù)據(jù)可以在低維特征空間被處理，同時保持原始數(shù)據(jù)的絕大部分信息，從而解決高維數(shù)據(jù)存在的問題。

PCA是線性降維方法，該方法通過分析計算矩陣的特征值、特征向量，將n維特征映射到r(n

輸入：數(shù)據(jù)集U為m個n維的樣本u1,u2,…,um。

Step1：用U的每一維進(jìn)行均值化，即減去這一維的均值。

Step2：用式（1）計算樣本的協(xié)方差矩陣。

Step3：對矩陣C進(jìn)行特征分解，求出協(xié)方差矩陣特征值λi及對應(yīng)的特征向量qi。

Step4：將特征向量qi按對應(yīng)特征值λi降序排列成矩陣，取前r行組成矩陣P。

輸出：V=PTU，V為U降到r維后的數(shù)據(jù)。

為了縮小投影的誤差，需要選取合適的r值，可用式（2）確定r值。

其中m表示特征的個數(shù)，式（2）中計算的是數(shù)據(jù)原始點(diǎn)與投影后的點(diǎn)的距離總和。εerror表示誤差，誤差越小說明保留的主成分越多，降維的效果越好。

3.2 核PCA

核方法采用非線性映射將原始數(shù)據(jù)由數(shù)據(jù)空間映射到特征空間，進(jìn)而在特征空間進(jìn)行對應(yīng)的線性操作。設(shè)xm和xn為數(shù)據(jù)空間中的樣本點(diǎn)，數(shù)據(jù)空間到特征空間的映射函數(shù)為ψ，核方法的原理是實(shí)現(xiàn)向量的內(nèi)積變換，如式（3）所示。

應(yīng)用比較廣泛的核函數(shù)有以下幾種形式：

1）線性核函數(shù)

2）高斯徑向基核函數(shù)（RBF）

3）多層感知器核函數(shù)（MLP）

4）P階多項(xiàng)式核函數(shù)

核PCA是標(biāo)準(zhǔn)PCA 的一種核化形式，核PCA將數(shù)據(jù)投影到非線性函數(shù)的特征空間，可以實(shí)現(xiàn)輸入空間到特征空間的轉(zhuǎn)換，非線性主成分可以通過核函數(shù)進(jìn)行定義，如線性核函數(shù)、徑向基核函數(shù)、多層感知器核函數(shù)、以及P階多項(xiàng)式核函數(shù)。因?yàn)閺较蚧撕瘮?shù)有良好的可控性和代表性，所以它作為本文中核PCA的核函數(shù)，如式（8）所示。

其中σ2表示帶寬參數(shù)，可以通過式（9）的取中值尺度估計公式計算。

4 KPCA-L算法

傳統(tǒng)的核PCA 算法的基本思想是通過核函數(shù)將低維空間中線性不可分的數(shù)據(jù)映射到更高維的空間中，使其在高維空間中線性可分。為了提高降維速度以及復(fù)雜度，KPCA-L 算法在原始數(shù)據(jù)映射之前首先對原始數(shù)據(jù)進(jìn)行預(yù)處理，接著使用改進(jìn)的LLE 方法對原始數(shù)據(jù)進(jìn)行局部降維，再使用核PCA進(jìn)行全局降維。

4.1 LLE算法

LLE 算法是一種局部特征保持算法，基本思想是假定高維觀測空間中每個數(shù)據(jù)樣本點(diǎn)與其鄰近點(diǎn)位于流形的一個線性局部領(lǐng)域，則每個數(shù)據(jù)點(diǎn)可以由其領(lǐng)域中的近鄰點(diǎn)線性表示，保持每個數(shù)據(jù)點(diǎn)與領(lǐng)域中的近鄰點(diǎn)線性關(guān)系不變，將高維觀測空間中的數(shù)據(jù)映射到低維空間中。設(shè)給定特征向量集合X={x1,x2,…,xN}，xi?RD，N代表特征向量個數(shù)，通過LLE 算法降維后得到輸出向量Y={y1,y2,…,yN}，yi?Rd，其中d?D。LLE 算法步驟如下。

步驟1：計算出每個特征向量xi的k個近鄰點(diǎn)，選取距離每個特征向量xi最近的k個特征向量作為樣本點(diǎn)xi的k個近鄰點(diǎn)。

步驟2：計算重構(gòu)權(quán)值矩陣，對于每個特征向量xi計算由k個近鄰點(diǎn)得到的近鄰權(quán)值矩陣，定義誤差函數(shù)ε(w) ，如式（10）所示。

其中xj(j=1,2,…,k)是xi的k個 近 鄰 點(diǎn)，wij(i=1,2,…,N;j=1,2,…,k)是xi和xj之間的權(quán)值且滿足式。

矩陣化公式（10）需滿足如下約束條件：當(dāng)xj不是xi的近鄰點(diǎn)時，wij=0；反之則。

對xi的k個近鄰進(jìn)行局部加權(quán)重建獲得重構(gòu)矩陣W，如式（11）~（12）。

其中為k×k矩陣，如式（13）。

步驟3：將圖像所有的特征向量投影到低維空間中，使輸出數(shù)據(jù)在低維空間中保持原有的結(jié)構(gòu)。由特征向量xi的近鄰局部重建權(quán)值矩陣和其近鄰點(diǎn)特征向量，計算出特征向量xi在低維嵌入空間的輸出向量yi，其中投影過程中使得代價函數(shù)?(Y)達(dá)到最小，如式（14）所示。

其中yi是xi的輸出向量，yi(j=1,2,…,k)是yi的k個近鄰點(diǎn)，且

其中I是單位矩陣。

4.2 改進(jìn)的LLE（DLLE）

傳統(tǒng)的LLE 方法中需要計算樣本點(diǎn)之間的歐氏距離來查找k個近鄰點(diǎn)，低維空間中使用歐氏距離計算簡單，但高維空間中的復(fù)雜性會使歐氏距離作為兩個樣本點(diǎn)的相似度量不可靠［27］，因此在此使用最短路徑算法計算兩個樣本點(diǎn)的距離，從而改進(jìn)傳統(tǒng)的LLE方法。具體DLLE算法如算法1所示。

算法1 DLLE

輸入：初始數(shù)據(jù)集X。輸出：降維后數(shù)據(jù)集Y。

1）X={x1,x2,…,xN},xi?RD×N；//輸入數(shù)據(jù)集

2）Bellman-Ford()； //用最短路徑算法計算樣本點(diǎn)xi和xl之間距離

3）fori=1toN

7）end。

8）xi(j=1,2,…,k)；

//尋找每個樣本點(diǎn)xi的k個近鄰點(diǎn)

//計算重構(gòu)權(quán)值矩陣W

10）M=(I-W)T(I-W)；

//計算半正定矩陣

11）calculate_value(M)；

//求解特征值和特征向量

12）Return Y； //Y為M矩陣第2 至第d+1 最小特征值對應(yīng)的特征向量

13）end。

DLLE算法的詳細(xì)描述如下：

步驟1：輸入數(shù)據(jù)集X，用Bellman-Ford 算法計算樣本點(diǎn)xi和xl之間的測地距離，按距離的升序排列。

步驟2：計算樣本點(diǎn)xi和xl的非對稱距離，尋找每個樣本點(diǎn)xi的k個近鄰點(diǎn)。

步驟3：計算重構(gòu)權(quán)值矩陣W。

步驟4：計算半正定矩陣M，輸出矩陣Y。

4.3 KPCA-L算法

KPCA-L算法的詳細(xì)描述如下：

步驟1：將數(shù)據(jù)集X按照4.2節(jié)中DLLE算法對數(shù)據(jù)進(jìn)行降維預(yù)處理。

步驟2：降維后數(shù)據(jù)集Y進(jìn)行核函數(shù)處理映射到高維空間，使數(shù)據(jù)線性可分，然后對矩陣進(jìn)行去中心化處理，計算協(xié)方差矩陣，求解特征值與特征向量。

步驟3：將特征向量按特征值由大到小排列，保留前r個特征向量構(gòu)成矩陣P，最后輸出降維后的數(shù)據(jù)集V。

算法2 KPCA-L

輸入：初始數(shù)據(jù)集X。

輸出：降維后數(shù)據(jù)集V。

1）X={x1,x2,…,xN},xi?RD×N；//輸入數(shù)據(jù)集

2）DLLE()；

//用DLLE對數(shù)據(jù)集進(jìn)行預(yù)處理

//將數(shù)據(jù)集進(jìn)行核函化

4）decentrate()；

//在高維空間進(jìn)行去中心化處理

6）calculatevalue()；

//求解特征值與特征向量

7）calculater()； //計算非線性主成分

8）returnV；

9）end。

5 實(shí)驗(yàn)

在本節(jié)中，本文提出的KPCA-L 算法將執(zhí)行在3 個基準(zhǔn)數(shù)據(jù)集上，通過與其他幾種方法相比較，驗(yàn)證算法的有效性。

5.1 數(shù)據(jù)集

1）Isolet數(shù)據(jù)集

Isolet 數(shù)據(jù)集中包含來自30 個主題的1560 個樣本，每個樣本都有617個特征描述。

2）Yale數(shù)據(jù)集

Yale 數(shù)據(jù)集中包含15 個不同主題的165 張灰度面部圖像。每個對象有11 張圖像，這些圖像具有不同的面部表情或配置：中心光，戴眼鏡，快樂，左光，不戴眼鏡，正常；右光，悲傷，困倦，驚訝和眨眼。

3）ORL數(shù)據(jù)集

ORL數(shù)據(jù)集中包括40個人的400張圖像，每個人有10 張圖像，這些圖像是在不同的時間，不同的光線下拍攝，有各種面部表情，例如微笑或不笑，睜眼或閉眼等。

在此實(shí)驗(yàn)中所有圖像都將降采樣為32×32 的大小。每個數(shù)據(jù)集隨機(jī)劃分為一個訓(xùn)練集（60%）和一個測試集（40%），表1為樣本的數(shù)據(jù)信息。

表1 樣本數(shù)據(jù)信息

5.2 比較算法

我們比較了五種不同維度降維方法的性能：

1）PCA［16］，它是一種廣泛使用的無監(jiān)督降維方法，目的是找到低秩矩陣。當(dāng)數(shù)據(jù)點(diǎn)位于高維空間中時，可以通過線性或非線性投影來獲得數(shù)據(jù)的結(jié)構(gòu)。

2）LLE［17］，它是一種非線性降維方法，能夠使降維后的數(shù)據(jù)較好地保持原有流行結(jié)構(gòu)。

3）KPCA［26］，它是一種非線性降維方法，解決PCA不能處理非線性數(shù)據(jù)的問題。

4）SDSPCAAN［28］，它保留全局和局部數(shù)據(jù)結(jié)構(gòu)，集成監(jiān)督性稀疏PCA 和帶有自適應(yīng)的聚類投影。

5）JPCDA［23］，它是一種PCA 聯(lián)合LDA 的方法，避免小樣本量問題。

6）KPCA-L，一種非線性降維方法，將LLE與核PCA 結(jié)合，降低算法復(fù)雜性，保持?jǐn)?shù)據(jù)原有流行結(jié)構(gòu)。

5.3 實(shí)驗(yàn)結(jié)果

圖1 顯示了三個數(shù)據(jù)集上所有降維方法的分類精度結(jié)果。從圖中可以看出與其他方法相比，在Isolet 數(shù)據(jù)集上KPCA-L 方法相對PCA、LLE、KP?CA、SDSPCAAN 和JPCDA 分 別 提 高 了12.49%、2.86%、3.52%、4.67%和0.77%；在Yale 數(shù)據(jù)集上相對于PCA、LLE、KPCA、SDSPCAAN 和JPCDA 分別提高了21.7%、4.56%、5.27%、3.47%和2.07%；在ORL 數(shù)據(jù)集上KPCA-L 方法相對PCA、KPCA、SD?SPCAAN 和JPCDA 分別提高了18.44%、2.94%、25.75%和0.38%。從圖中可以看出本文所提出的方法的分類準(zhǔn)確性有明顯地提高，在Isolet 數(shù)據(jù)集上尤其明顯。從圖中可以看出KPCA-L 方法優(yōu)于PCA 方法，因而LLE 和KPCA 的有效結(jié)合可提取出更具有代表性的特征。

圖1 三個數(shù)據(jù)集上不同降維算法的分類準(zhǔn)確性

6 結(jié)語

高維數(shù)據(jù)降維一直是圖像、視頻、文本文檔等領(lǐng)域研究的熱點(diǎn)，本文將改進(jìn)的LLE 與核PCA 結(jié)合，有效提取非線性特征，LLE 采用局部線性逼近非線性，保持了數(shù)據(jù)整體的幾何性質(zhì)。在基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該方法在一定程度上能提高PCA對平移的魯棒性，提高分類的準(zhǔn)確率。