基于密度和相關分量分析的局部線性嵌入算法

王 楠，賈永利，韓淑運，楊 裔，李 廉，李彩虹

(蘭州大學 信息科學與工程學院，甘肅 蘭州 730000)

0 引 言

近年來，高維數據降維算法在人工智能和數據挖掘[1]等領域受到關注，是數據分析過程[2](如特征提取、模式識別和可視化)必不可少的處理步驟[3]，傳統(tǒng)的降維算法對本質結構為非線性分布的高維數據降維效果并不理想。流形學習是一種重要的非線性降維方法[4]，該方法在保留原有結構特征的基礎上，提取出高維空間中數據流形的結構特征，進而在低維空間中表示出數據關系。LLE算法作為一種經典的流形學習算法[5]，成功地應用于數據挖掘和機器學習等鄰域。初始鄰域值和相似性度量的選取[6]是影響LLE算法降維的關鍵，初始鄰域值一般基于經驗或盲目性選取沒有考慮高維空間數據集的密度分布情況[7]，使得LLE算法的降維效果對初始鄰域值的依賴很大。原始的LLE算法[8]是以歐式距離作為樣本間的相似性度量，但沒有引入樣本的類別信息，不能準確衡量流形上樣本間相對位置關系。

針對上述問題本文根據高維空間的密度分布和RCA相似性度量，提出一種基于密度和相關分量分析的局部線性嵌入算法，計算密度縮放因子自適應調整初始鄰域值，用RCA度量代替歐氏距離用于計算LLE算法的樣本間相似性，從而改善初始鄰域值選取盲目和流形上樣本間位置關系是否準確的問題，通過對本文算法和其它LLE改進算法在Swiss roll、Swiss roll hole和ORL數據庫上進行對比，驗證了本文算法的降維效果和識別性能優(yōu)于其它算法。

1 LLE算法

LLE算法的核心是將輸入的高維數據映射到具有較低維度的單個全局坐標系中。LLE算法圖示說明如圖1所示，算法步驟簡要描述如下：

圖1 LLE算法圖示說明

算法1： LLE算法

輸入： 高維數據X={x1,x2,x3,…,xn}∈Rd*n

輸出： 降維后數據Y={y1,y2,y3,…,yn}∈Rm*n， 其中m?d

(1) 近鄰集的選取， 根據初始鄰域值k， 選擇每個樣本點的k個近鄰集Ni={xi1,xi2,xi3,…xik}。

(2) 每個樣本點由其近鄰集加權線性表示， 在重建誤差函數最小的近鄰局部重建權值矩陣。其重建誤差函數為

(1)

其中，wij表示樣本點xi和樣本點xj之間的權值，若xj?N(xi)，wij=0。

(3) 高維到低維的映射中保持所有樣本點與近鄰集的空間位置關系不變， 即線性重構之后保持wij不變， 低維重建誤差最小

(2)

其中，I是單位矩陣。

2 密度縮放因子和相關分量分析方法距離度量

2.1 密度縮放因子

LLE算法對鄰域參數k值的選取沒有考慮高維數據集的密度分布，導致算法性能一直受領域值選擇盲目性的制約。針對LLE算法人為選取k值的敏感問題，本文算法根據高維空間中的數據密度分布計算每個樣本點的密度縮放因子，做到自適應調整鄰域值大小，具體計算步驟如下：

算法2：密度縮放因子算法

(1)確定每個樣本點的局部密度ρi， 該值取決于樣本點之間的距離dij， 局部密度可定義為

(3)

(2)確定每個樣本點的密度縮放因子αi， 該值取決于每個樣本點的局部密度，密度縮放因子可定義為

(4)

以Swiss roll數據集的部分樣本點為例計算樣本點的局部密度和密度縮放因子，其中Swiss roll數據集的部分樣本點空間關系如圖2所示，列舉出圖中標注的觀測點計算其局部密度和密度縮放因子見表1。

表1 觀測樣本的局部密度和密度縮放因子

圖2 空間點的幾何描述

2.2 相關分量分析方法的計算

高維數據集包含著不同類別的樣本集，數據空間結構的不同會導致不同類別的樣本集數據在各維度間的相關性存

在差異[9]，因此使用歐式距離計算多類別樣本間的相似性度量并不可靠[10]。相關分量分析方法使得在新的特征空間里賦予相關特征較大的權重以減小樣本間距離，賦予不相關的特征較小的權重增大樣本間距離，保證在最大化異類樣本間距離的同時最小化樣本間距離。用相關分量分析代替歐式距離使得LLE算法在尋找近鄰點時每個樣本的近鄰大多是同類別點，確保LLE算法在低維嵌入時的準確性。

根據參考文獻[9,10]關于相關分量分析算法定義如下：

算法3：相關分量分析算法

(1)對于每個同類訓練樣本的子集包含的樣本減去該同類訓練樣本的子集中所有樣本的均值。

(2)計算協(xié)方差矩陣：假設p個樣本形成k個同類訓練樣本的子集，每個同類訓練樣本的子集包含nj個樣本，均值為mj，xji表示第j個同類訓練樣本的子集的第i個數據，協(xié)方差矩陣計算公式為

(5)

任意兩個數據樣本間的相似度

(6)

3 基于密度和相關分量分析的局部線性嵌入算法

3.1 算法思想

由于傳統(tǒng)的LLE算法沒有考慮到高維空間數據集的密度分布，導致鄰域值的選取具有盲目性，并且將歐式距離作為樣本間的相似性度量不能準確衡量流形上兩點間相對位置關系。針對上述問題，本文算法根據高維空間樣本點的密度和距離度量的思想提出了基于密度和RCA距離度量的局部線性嵌入算法，首先引入密度的思想對初始鄰域值進行調整，樣本點根據自身密度的大小自適應調整鄰域范圍，使得高密度樣本點的鄰域值減小，而低密度樣本點的鄰域值增大，避免了鄰域參數選取的盲目性。算法在計算樣本距離時引入RCA方法，對相關的特征賦予更大的權重，對不相關的特征賦予較小的權重，使得每個樣本的近鄰大部分是同類別點，保證了在低維嵌入時算法的準確性。最后，DRLLE算法使用自適應調整后的鄰域值和RCA距離作為相似性度量計算每個樣本點的近鄰集進行降維處理。

3.2 算法步驟

本節(jié)詳細描述基于密度和相關分量分析的局部線性嵌入算法框架，算法主要分為自適應調整鄰域參數和相關分量分析度量兩部分，引入密度縮放因子對初始鄰域值進行調整，計算RCA距離代替歐式距離用于LLE算法的相似性度量。

高維樣本點的空間密度分布影響其鄰域大小，本節(jié)首先引入密度縮放對初始鄰域值大小進行自適應調整，具體計算步驟如下：

算法4：初始鄰域值的自適應調整算法

(1)計算β值判斷初始鄰域值k是否為過大或過小的極值情況。

β值計算如下

(7)

(8)

(9)

計算調整后鄰域值的β值，若滿足臨界值調整條件繼續(xù)進行步驟(1)的調整，直到調整后的鄰域值k不再是極值情況再進行基于密度縮放因子的調整。

(2)每一個樣本點通過其局部密度ρi計算密度縮放因子αi， 根據其密度縮放因子的大小自適應調整鄰域范圍，使得高密度樣本點的鄰域參數減小低密度樣本點的鄰域參數增大，直到滿足 |β-αi|>δ， 使得樣本點的鄰域值得到合理的調整。

樣本點的初始鄰域值ki可自適應調整如下

(10)

圖2所示Swiss roll數據集的部分樣本點為例設定初始鄰域值進行鄰域值大小的調整，數據集Swiss roll的理想鄰域值為15。在初始鄰域值k=5和k=40時進行鄰域值的調整，列舉出圖中標注的觀測點經過初步調整和密度縮放因子調整后的鄰域值見表2。

表2 初始鄰域值k=5、k=40時DRLLE自適應調整鄰域值

當初始鄰域值k=5時經式(7)判斷初始鄰域值過小需要經過式(8)初步調整增大鄰域值，再將初步調整后的鄰域值轉入式(10)基于密度縮放因子調整，其中樣本點a、d的密度縮放因子大于1為較高密度樣本點，其鄰域參數自適應減少，觀測樣本b、c、e、f、g的密度縮放因子小于1為較低密度樣本點，其鄰域參數自適應增加調整，調整后的所有樣本點的平均鄰域值為15；當初始鄰域值k=40 時經式(7)判斷初始鄰域值過小需要經過式(9)減小鄰域值再根據樣本的密度縮放因子自適應調整，調整后所有樣本點的平均鄰域值為15。

根據自適應調整后的鄰域值，然后本節(jié)以算法3計算RCA距離代替歐式距離用于樣本間的相似性度量，對相關的特征賦予較大的權重，對不相關的特征賦予較小的權重，使得在尋找近鄰點時每個樣本的近鄰大部分是同類別點，這樣可以保證在低維嵌入時算法的精確性，使得LLE算法具有較好的降維效果。

DRLLE算法的具體操作過程如算法5所示

算法5：DRLLE算法

輸入：原始數據集X={x1,x2,x3,…,xn}∈Rd*n；

初始鄰域值k；

低維空間維數d。

輸出：數據集X在低維空間d的投影；

(1) 根據式(3)計算每個樣本點的局部密度，式(4) 計算每個樣本點的密度縮放因子αi；

(2) 通過式(7)判斷初始鄰域值是否為過大過小的極值情況；若是極值情況，通過式(8)或式(9)進行鄰域值過大過小的調整再轉入(3)；若不是極值情況，轉入(3)；

(3) 自適應調整鄰域，根據每個樣本點的密度縮放因子按照式(10)自適應調整其鄰域大小直至滿足限制條件，使得高密度樣本點的鄰域參數減小低密度樣本點的鄰域參數增大；

(4) 通過式(6)計算RCA距離度量作為樣本間相似性度量，根據每個樣本點調整后的鄰域大小kinew和RCA距離度量篩選每個樣本點xi的kinew個近鄰集N′i={xi1,xi2,xi3,…xik}；

(5) 利用得到的近鄰集，代入式(1)重建誤差函數和式(2)計算LLE算法降維結果。

4 實驗與分析

本節(jié)將標準LLE算法[11]和DRLLE算法分別應用于人工生成的Swiss roll數據集、帶空洞的Swiss roll hole數據集[12]進行實驗分析，將標準LLE算法，基于測地距離的LLE算法[13]和DRLLE算法分別應用于ORL人臉數據集[14]，并對算法的性能進行比較分析。

4.1 Swiss roll數據集和Swiss roll hole數據集的實驗及分析

本節(jié)選取了人工生成的Swiss roll數據集和帶空洞的Swiss roll with hole數據集對標準LLE算法和DRLLE算法進行實驗分析，圖3(a)為選取1000個采樣點的Swiss roll數據集；圖3(b)為帶空洞的Swiss roll hole數據集，同樣選取1000個采樣點，流形表面缺失的空洞部分會影響領域點的選取。

圖3 相關數據集

好的降維效果會使Swiss roll數據在不同維度的樣本能夠較好的分離，帶空洞的Swiss roll hole數據展開可恢復缺失的空洞部分。初始鄰域值k的大小對數據集的降維效果有很大的影響，首先驗證在不同初始鄰域值k下，標準LLE算法對Swiss roll數據集和帶空洞的Swiss roll with hole數據集的降維效果。

圖4展示了標準LLE算法在初始k值設定為5、10、15、20、40、80時Swiss roll和Swiss roll hole數據集的降維效果。圖4(a)展示出Swiss roll數據集在k=15時降維后得到較好的二維展開圖降維效果最好，圖4(b)展示出帶空洞的Swiss roll hole數據集在k=10時降維后恢復出流形表面缺失的空洞降維效果最好，所以k=15為標準LLE算法對Swiss roll數據集的理想鄰域值，k=10為標準LLE算法對Swiss roll hole數據集的理想鄰域值。當初始k值偏離理想領域值，標準的LLE算法的降維效果較差，即標準的LLE算法對初始鄰域選取依賴很大，自適應能力較差。接下來將不同的初始k值帶入DRLLE算法對Swiss roll數據庫和Swiss roll hole數據庫進行降維，對比在不同鄰域值的情況下DRLLE算法的自適應效果。

圖4 標準LLE算法在不同k值的降維效果

圖5可以看出當初始k值偏離理想k值時，Swiss roll數據集降維后仍得到較好的二維展開圖，Swiss roll hole數據集降維對出流形表面缺失的空洞結構有很好的恢復。由此可見，DRLLE算法受初始鄰域值的影響較小有較好降維效果，可以為LLE算法提供較為理想的鄰域。

圖5 DRLLE算法在不同k值的降維效果

流形上的所有樣本點的理想鄰域大小受高維空間密度的影響，DRLLE算法根據初始鄰域值自適應調整到每個樣本點的理想鄰域。表4統(tǒng)計了在不同的初始鄰域值下，基于標準LLE和DRLLE算法得到Swiss roll數據庫和Swiss roll hole數據庫所有樣本點的平均鄰域值。

由表4可以看出，對于數據庫Swiss roll和帶空洞的Swiss roll hole當初始k值偏離理想k值時，標準LLE算法的鄰域值和降維的理想鄰域值有較大的誤差，本文方法的自適應結果對于數據庫Swiss roll基本維持在14、15和16，對于數據庫Swiss roll hole基本維持在9、10和11接近理想鄰域值。本文提出的DRLLE算法在任意的初始鄰域值下都能得到一個理想的鄰域大小，具有一定的穩(wěn)定性和可靠性。

表4 不同初始k值下的自適應結果

4.2 ORL人臉數據庫上的實驗及分析

ORL人臉數據庫1992年4月到1994年4月拍攝于英國劍橋Olivetti實驗室，是使用最廣泛的標準人臉數據庫，由40個不同年齡、不同性別和不同種族的對象在不同的時間改變光線、面部表情和面部細節(jié)共計有400幅圖像，每個圖像的大小為112×92像素，每個像素有256個灰度級，該數據庫是使用最廣泛的標準人臉數據庫。部分對象的圖像樣本如圖6所示。

圖6 ORL數據庫部分人臉圖像樣本

把圖像分為訓練集和測試集，每個對象的50%-60%的圖像作為訓練集，剩余圖像作為測試集，具體描述見表5。分別采用以歐式距離、測地距離和RCA距離作為相似性度量的標準LLE算法、基于測地距離的LLE算法和DRLLE算法計算ORL數據庫的識別率。識別率受初始k值、相似性度量和降維后維數d的影響，降維后維數d可以由高維數據和低維數據距離矩陣的線性關系判斷，分別計算不同的初始k值和維數d下3種算法的識別率。維度d取值為40、50、60、70，對每個d取初始鄰域值為5、10、20、40、80進行實驗，實驗結果如圖7所示。

表5 ORL數據庫訓練集和測試集描述

圖7 3種算法在ORL數據庫上識別率對比

圖7為3種算法在不同維度，不同初始近鄰值時在ORL人臉數據庫上的識別率，對于標準LLE算法和DLLE算法在近鄰數k=5時取得較好的識別率保持在92%左右，當近鄰數的取值偏離k=5時ORL人臉數據集的識別率明顯降低，而DRLLE算法的識別率在94%以上高于其它兩種算法。表明本文算法受初始近鄰值的影響較小并且以RCA度量作為相似性度量更為可靠。

5 結束語

針對LLE算法存在初始鄰域值大小選取盲目性和相似性度量的選取問題，本文提出DRLLE算法，利用密度將每個樣本點的初始鄰域值大小調整至理想鄰域值，使用RCA距離代替歐式距離計算樣本間相似性，在Swiss roll、Swiss roll hole數據集和ORL人臉數據庫的對比實驗結果表明，DRLLE算法在Swiss roll和Swiss roll hole數據集的降維效果最好，對ORL人臉數據庫識別率最高，表明DRLLE算法具有很好的降維效果。