基于密度和相關(guān)分量分析的局部線性嵌入算法

王 楠，賈永利，韓淑運(yùn)，楊 裔，李 廉，李彩虹

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

0 引 言

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

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

1 LLE算法

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

圖1 LLE算法圖示說明

算法1： LLE算法

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

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

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

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

(1)

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

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

(2)

其中，I是單位矩陣。

2 密度縮放因子和相關(guān)分量分析方法距離度量

2.1 密度縮放因子

LLE算法對(duì)鄰域參數(shù)k值的選取沒有考慮高維數(shù)據(jù)集的密度分布，導(dǎo)致算法性能一直受領(lǐng)域值選擇盲目性的制約。針對(duì)LLE算法人為選取k值的敏感問題，本文算法根據(jù)高維空間中的數(shù)據(jù)密度分布計(jì)算每個(gè)樣本點(diǎn)的密度縮放因子，做到自適應(yīng)調(diào)整鄰域值大小，具體計(jì)算步驟如下：

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

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

(3)

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

(4)

以Swiss roll數(shù)據(jù)集的部分樣本點(diǎn)為例計(jì)算樣本點(diǎn)的局部密度和密度縮放因子，其中Swiss roll數(shù)據(jù)集的部分樣本點(diǎn)空間關(guān)系如圖2所示，列舉出圖中標(biāo)注的觀測點(diǎn)計(jì)算其局部密度和密度縮放因子見表1。

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

圖2 空間點(diǎn)的幾何描述

2.2 相關(guān)分量分析方法的計(jì)算

高維數(shù)據(jù)集包含著不同類別的樣本集，數(shù)據(jù)空間結(jié)構(gòu)的不同會(huì)導(dǎo)致不同類別的樣本集數(shù)據(jù)在各維度間的相關(guān)性存

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

根據(jù)參考文獻(xiàn)[9,10]關(guān)于相關(guān)分量分析算法定義如下：

算法3：相關(guān)分量分析算法

(1)對(duì)于每個(gè)同類訓(xùn)練樣本的子集包含的樣本減去該同類訓(xùn)練樣本的子集中所有樣本的均值。

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

(5)

任意兩個(gè)數(shù)據(jù)樣本間的相似度

(6)

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

3.1 算法思想

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

3.2 算法步驟

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

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

算法4：初始鄰域值的自適應(yīng)調(diào)整算法

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

β值計(jì)算如下

(7)

(8)

(9)

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

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

樣本點(diǎn)的初始鄰域值ki可自適應(yīng)調(diào)整如下

(10)

圖2所示Swiss roll數(shù)據(jù)集的部分樣本點(diǎn)為例設(shè)定初始鄰域值進(jìn)行鄰域值大小的調(diào)整，數(shù)據(jù)集Swiss roll的理想鄰域值為15。在初始鄰域值k=5和k=40時(shí)進(jìn)行鄰域值的調(diào)整，列舉出圖中標(biāo)注的觀測點(diǎn)經(jīng)過初步調(diào)整和密度縮放因子調(diào)整后的鄰域值見表2。

表2 初始鄰域值k=5、k=40時(shí)DRLLE自適應(yīng)調(diào)整鄰域值

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

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

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

算法5：DRLLE算法

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

初始鄰域值k；

低維空間維數(shù)d。

輸出：數(shù)據(jù)集X在低維空間d的投影；

(1) 根據(jù)式(3)計(jì)算每個(gè)樣本點(diǎn)的局部密度，式(4) 計(jì)算每個(gè)樣本點(diǎn)的密度縮放因子αi；

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

(3) 自適應(yīng)調(diào)整鄰域，根據(jù)每個(gè)樣本點(diǎn)的密度縮放因子按照式(10)自適應(yīng)調(diào)整其鄰域大小直至滿足限制條件，使得高密度樣本點(diǎn)的鄰域參數(shù)減小低密度樣本點(diǎn)的鄰域參數(shù)增大；

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

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

4 實(shí)驗(yàn)與分析

本節(jié)將標(biāo)準(zhǔn)LLE算法[11]和DRLLE算法分別應(yīng)用于人工生成的Swiss roll數(shù)據(jù)集、帶空洞的Swiss roll hole數(shù)據(jù)集[12]進(jìn)行實(shí)驗(yàn)分析，將標(biāo)準(zhǔn)LLE算法，基于測地距離的LLE算法[13]和DRLLE算法分別應(yīng)用于ORL人臉數(shù)據(jù)集[14]，并對(duì)算法的性能進(jìn)行比較分析。

4.1 Swiss roll數(shù)據(jù)集和Swiss roll hole數(shù)據(jù)集的實(shí)驗(yàn)及分析

本節(jié)選取了人工生成的Swiss roll數(shù)據(jù)集和帶空洞的Swiss roll with hole數(shù)據(jù)集對(duì)標(biāo)準(zhǔn)LLE算法和DRLLE算法進(jìn)行實(shí)驗(yàn)分析，圖3(a)為選取1000個(gè)采樣點(diǎn)的Swiss roll數(shù)據(jù)集；圖3(b)為帶空洞的Swiss roll hole數(shù)據(jù)集，同樣選取1000個(gè)采樣點(diǎn)，流形表面缺失的空洞部分會(huì)影響領(lǐng)域點(diǎn)的選取。

圖3 相關(guān)數(shù)據(jù)集

好的降維效果會(huì)使Swiss roll數(shù)據(jù)在不同維度的樣本能夠較好的分離，帶空洞的Swiss roll hole數(shù)據(jù)展開可恢復(fù)缺失的空洞部分。初始鄰域值k的大小對(duì)數(shù)據(jù)集的降維效果有很大的影響，首先驗(yàn)證在不同初始鄰域值k下，標(biāo)準(zhǔn)LLE算法對(duì)Swiss roll數(shù)據(jù)集和帶空洞的Swiss roll with hole數(shù)據(jù)集的降維效果。

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

圖4 標(biāo)準(zhǔn)LLE算法在不同k值的降維效果

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

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

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

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

表4 不同初始k值下的自適應(yīng)結(jié)果

4.2 ORL人臉數(shù)據(jù)庫上的實(shí)驗(yàn)及分析

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

圖6 ORL數(shù)據(jù)庫部分人臉圖像樣本

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

表5 ORL數(shù)據(jù)庫訓(xùn)練集和測試集描述

圖7 3種算法在ORL數(shù)據(jù)庫上識(shí)別率對(duì)比

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

5 結(jié)束語

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