改進的局部線性嵌入及其混成數據降維算法?

馬思遠 賀 萍

（河北經貿大學信息技術學院 石家莊 050061）

1 引言

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

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

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

2 相關工作

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

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

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

3 基本概念

3.1 PCA算法

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

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

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

Step1：用U的每一維進行均值化，即減去這一維的均值。

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

Step3：對矩陣C進行特征分解，求出協方差矩陣特征值λi及對應的特征向量qi。

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

輸出：V=PTU，V為U降到r維后的數據。

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

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

3.2 核PCA

核方法采用非線性映射將原始數據由數據空間映射到特征空間，進而在特征空間進行對應的線性操作。設xm和xn為數據空間中的樣本點，數據空間到特征空間的映射函數為ψ，核方法的原理是實現向量的內積變換，如式（3）所示。

應用比較廣泛的核函數有以下幾種形式：

1）線性核函數

2）高斯徑向基核函數（RBF）

3）多層感知器核函數（MLP）

4）P階多項式核函數

核PCA是標準PCA 的一種核化形式，核PCA將數據投影到非線性函數的特征空間，可以實現輸入空間到特征空間的轉換，非線性主成分可以通過核函數進行定義，如線性核函數、徑向基核函數、多層感知器核函數、以及P階多項式核函數。因為徑向基核函數有良好的可控性和代表性，所以它作為本文中核PCA的核函數，如式（8）所示。

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

4 KPCA-L算法

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

4.1 LLE算法

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

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

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

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

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

對xi的k個近鄰進行局部加權重建獲得重構矩陣W，如式（11）~（12）。

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

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

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

其中I是單位矩陣。

4.2 改進的LLE（DLLE）

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

算法1 DLLE

輸入：初始數據集X。輸出：降維后數據集Y。

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

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

3）fori=1toN

7）end。

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

//尋找每個樣本點xi的k個近鄰點

//計算重構權值矩陣W

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

//計算半正定矩陣

11）calculate_value(M)；

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

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

13）end。

DLLE算法的詳細描述如下：

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

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

步驟3：計算重構權值矩陣W。

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

4.3 KPCA-L算法

KPCA-L算法的詳細描述如下：

步驟1：將數據集X按照4.2節中DLLE算法對數據進行降維預處理。

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

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

算法2 KPCA-L

輸入：初始數據集X。

輸出：降維后數據集V。

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

2）DLLE()；

//用DLLE對數據集進行預處理

//將數據集進行核函化

4）decentrate()；

//在高維空間進行去中心化處理

6）calculatevalue()；

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

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

8）returnV；

9）end。

5 實驗

在本節中，本文提出的KPCA-L 算法將執行在3 個基準數據集上，通過與其他幾種方法相比較，驗證算法的有效性。

5.1 數據集

1）Isolet數據集

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

2）Yale數據集

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

3）ORL數據集

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

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

表1 樣本數據信息

5.2 比較算法

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

1）PCA［16］，它是一種廣泛使用的無監督降維方法，目的是找到低秩矩陣。當數據點位于高維空間中時，可以通過線性或非線性投影來獲得數據的結構。

2）LLE［17］，它是一種非線性降維方法，能夠使降維后的數據較好地保持原有流行結構。

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

4）SDSPCAAN［28］，它保留全局和局部數據結構，集成監督性稀疏PCA 和帶有自適應的聚類投影。

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

6）KPCA-L，一種非線性降維方法，將LLE與核PCA 結合，降低算法復雜性，保持數據原有流行結構。

5.3 實驗結果

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

圖1 三個數據集上不同降維算法的分類準確性

6 結語

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