馬 麗 董唯光 安志龍

（1.陜西鐵路工程職業(yè)技術(shù)學(xué)院電氣與信息工程系 渭南 714000）

（2.蘭州交通大學(xué)自動(dòng)化與電氣工程系 蘭州 730070）（3.陜西鐵路工程職業(yè)技術(shù)學(xué)院管理工程系 渭南 714000）

1 引言

隨著5G 信息技術(shù)的不斷發(fā)展與更新，人類收集和處理高維度數(shù)據(jù)的能力越來(lái)越強(qiáng)。而通過(guò)海量數(shù)據(jù)如何實(shí)現(xiàn)重要價(jià)值的提取，是數(shù)據(jù)處理研究的主要瓶頸。因此，數(shù)據(jù)降維尤為重要。數(shù)據(jù)降維，一方面可以解決“維數(shù)災(zāi)難，降低數(shù)據(jù)復(fù)雜度；另一方面可以更好地學(xué)習(xí)數(shù)據(jù)中的信息。

作為信息科學(xué)領(lǐng)域研究熱點(diǎn)之一，流形學(xué)習(xí)，主要用于數(shù)據(jù)維數(shù)約簡(jiǎn)。流形學(xué)習(xí)是從高維采樣數(shù)據(jù)中恢復(fù)低維流形本質(zhì)結(jié)構(gòu)，即找到高維空間中的低維流形并求出相應(yīng)的嵌入映射，實(shí)現(xiàn)維數(shù)約簡(jiǎn)或數(shù)據(jù)可視化。經(jīng)典的非線性流形學(xué)習(xí)算法有等距特征映射算法（Isometric map，Isomap）［1］、局部線性嵌入算法（Locally Linear Embedding，LLE）［2］、Laplacian 特征映射算法（Laplacian Eigenmaps，LE）［3］、Hessian 特征映射算法（Hessian-based Locally Linear Embedding，HLLE）［4］和局部切空間排列算法（Local Tangent Space Alignment，LTSA）［5］等。

針對(duì)局部降維算法中近鄰參數(shù)K 的選取問(wèn)題，很多研究者提出了自適應(yīng)選擇近鄰算法［9～12］。但這些算法計(jì)算復(fù)雜度在處理非均勻分布的數(shù)據(jù)流形時(shí)，歐氏距離作為相似性度量無(wú)法反映樣本的全局一致性，而流形距離［15］能有效反映樣本固有的全局一致性信息。故本文提出一種基于流形距離的鄰域選擇算法，通過(guò)流形距離作為樣本間相似性度量的測(cè)度，對(duì)空間分布復(fù)雜的流形結(jié)構(gòu)的數(shù)據(jù)具有更好的性能。

受到壓縮感知（Compressive Sensing，CS）理論［16～18］的啟發(fā)，提出基于壓縮感知理論的核稀疏表示投影（Kernel Sparse Representation Projections based on Compressive Sensing，CS-KSRP）。該思想首先將數(shù)據(jù)映射到更高維的特征空間，然后利用壓縮感知理論在高維特征空間中進(jìn)行核函數(shù)的稀疏表示。因?yàn)樵肼暡痪哂邢∈栊裕?0］，在局部線性嵌入算法中引入該稀疏投影［19，21］，可以實(shí)現(xiàn)對(duì)原始數(shù)據(jù)的降噪過(guò)程。將上述兩種思想相結(jié)合，提出了流形距離與壓縮感知核稀疏投影相結(jié)合的局部線性嵌入算法。從實(shí)驗(yàn)數(shù)據(jù)集的降維效果可以得出本文所提出的算法能有效避免對(duì)鄰域參數(shù)的敏感并能達(dá)到降噪的目的。

2 局部線性嵌入算法

局部線性嵌入算法（LLE）［2］主要是通過(guò)在低維嵌入空間中保持每個(gè)數(shù)據(jù)點(diǎn)的近鄰重構(gòu)系數(shù)來(lái)保持整個(gè)數(shù)據(jù)的流形結(jié)構(gòu)，即以重構(gòu)權(quán)值矩陣作為高維觀測(cè)空間與低維嵌入空間的聯(lián)系橋梁。由于流形上的局部可以認(rèn)為是一個(gè)局部歐式空間，因此每個(gè)樣本點(diǎn)與其近鄰樣本之間是線性關(guān)系，可以用其近鄰樣本的線性組合來(lái)重構(gòu)。

LLE算法包含以下三個(gè)基本步驟：

1）構(gòu)造近鄰域：在高維數(shù)據(jù)空間對(duì)于給定的數(shù)據(jù)集X=[x1，x2，…，xn]∈RD×n，通過(guò)歐氏距離尋找與每個(gè)樣本點(diǎn)最近的k個(gè)近鄰，xi的k個(gè)近鄰集合為N(xi)={xi1，xi2，…，xik}。

2）計(jì)算高維空間中的局部線性表示：權(quán)值矩陣W對(duì)于每個(gè)樣本點(diǎn)xi及其近鄰集N(xi)={xi1，xi2，…，xik}。權(quán)值矩陣W是通過(guò)最小二乘法極小化每個(gè)樣本點(diǎn)的重構(gòu)誤差得到，即：

其中權(quán)值wij反映了樣本點(diǎn)xj對(duì)xi重構(gòu)的貢獻(xiàn)。

3）求低維嵌入Y：在低維空間用各個(gè)樣本點(diǎn)的近鄰重構(gòu)其本身，即求Y=[y1，y2，…，yN]，使得重構(gòu)誤差最小，設(shè)置誤差函數(shù)為

E=(I-W)T(I-W) ，最終求得。

為實(shí)現(xiàn)選擇最近鄰點(diǎn)的準(zhǔn)確選擇，圖1 中（b），（c），（d）為用LLE 算法對(duì)實(shí)驗(yàn)數(shù)據(jù)集 Swiss-roll 進(jìn)行K近鄰算法構(gòu)建鄰域圖，最近鄰點(diǎn)數(shù)k=8，10，12，所得到的二維嵌入結(jié)果。從圖中看到隨著k 值的變化，會(huì)有不同的低維嵌入圖形，說(shuō)明LLE 算法對(duì)鄰域參數(shù)的選擇比較敏感。故本文提出了一種基于流形距離度量相似性的近鄰選擇算法，根據(jù)流形距離計(jì)算樣本間的相似性，較好地解決了LLE算法的鄰域選擇問(wèn)題。

3 基于流形距離的鄰域選取

3.1 流形距離

由于用歐氏距離來(lái)選擇最近鄰域時(shí)，選擇的近鄰點(diǎn)不能準(zhǔn)確地表征流形上的真正鄰域結(jié)構(gòu)。為實(shí)現(xiàn)數(shù)據(jù)最近鄰點(diǎn)的選擇，提出一種新的相似度度量來(lái)計(jì)算數(shù)據(jù)點(diǎn)間的最短距離。

定義1.流形上兩點(diǎn)xi，xj的線段長(zhǎng)度定義為

d(xi，xj)表示xi，xj之間的歐氏距離，τ是可調(diào)參數(shù)。

定義2.將數(shù)據(jù)點(diǎn)看作是圖G=（V，E）的頂點(diǎn)，令p∈Vl，表示圖上的一個(gè)長(zhǎng)度為l=|p|-1的連接點(diǎn)p1與的路徑，其中邊 (pk，pk+1)，1 ≤k＜|p|。令Pij表示連接數(shù)據(jù)點(diǎn)xi，xj的所有路徑的集合，則xi與xj之間的流形距離如下：

其中，L(a，b)表示兩點(diǎn)間流形上的線段長(zhǎng)度。流形距離滿足以下四個(gè)條件：

1）對(duì)稱性：MD(xi，xj)=MD(xj，xi)；

2）非負(fù)性：MD(xi，xj)≥0 ；

3）三角不等式：對(duì)任意的xi，xj，xk，有MD(xi，xj)≤MD(xi，xk)+MD(xk，xj)；

4）自反性：MD(xi，xj)=0 ，當(dāng)且僅當(dāng)xi=xj。

數(shù)據(jù)點(diǎn)間相似度可以用距離來(lái)表示，相似度越高，距離在越小。因此，定義xi，xj，間的相似度為

定義樣本自身的相似度為0，即當(dāng)i=j時(shí)，σij=0。

3.2 基于流形距離的鄰域選擇

根據(jù)定義，數(shù)據(jù)集中任意兩點(diǎn)間的流形距離，算法流程如下：

步驟1：由式（1）構(gòu)建線段長(zhǎng)度矩陣L；

步驟2：利用式（2）計(jì)算數(shù)據(jù)點(diǎn)對(duì)之間的流形距離，根據(jù)式（3）計(jì)算數(shù)據(jù)點(diǎn)對(duì)間的相似度。

步驟3：根據(jù)步驟2 計(jì)算出的相似度選擇樣本點(diǎn)xi的近鄰點(diǎn)數(shù)。

4 基于壓縮感知的稀疏表示投影

壓縮感知（CS）理論的核心內(nèi)容是：在某一稀疏基Ψ=[ψ1，ψ2，…，ψN]上具有m稀疏表示的進(jìn)行N采樣的信號(hào)x∈RN，即

假設(shè)通過(guò)非線性映射φ將樣本xi∈RN(i=1，2，…，N) 映射到高維特征空間，即φ(xi)(i=1，2，…，N) 表示非線性映射后的特征樣本向量。令R=[φ(x1)，φ(x2)，…，φ(xN)]，則下式可以描述高維特征空間的稀疏表示問(wèn)題：

其中，φ(y)是由原空間任一樣本數(shù)據(jù)y映射到高維特征空間的象。問(wèn)題（4）的近似解可以通過(guò)求解以下的約束最優(yōu)化問(wèn)題得到：

其中，g表示高維特征空間中的稀疏表示稀疏向量。

利用核方法計(jì)算高維特征空間數(shù)據(jù)的內(nèi)積，得：

對(duì)目標(biāo)函數(shù)（6）進(jìn)行數(shù)學(xué)理論推導(dǎo)：

給定約束條件uTRRTu=1，則優(yōu)化目標(biāo)函數(shù)為

上式可等價(jià)于以下最大優(yōu)化目標(biāo)函數(shù)：

最大化目標(biāo)函數(shù)（7）可以轉(zhuǎn)化為求解以下特征方程：

其中，投影向量u=Rp，將其代入方程（8），可得：

對(duì)上述特征方程進(jìn)行化簡(jiǎn)，得：

pi(i=1，2，…，d)為方程（9）對(duì)應(yīng)的d個(gè)最大特征值的特征向量。

5 流形距離與壓縮感知核稀疏投影的局部線性嵌入

算法步驟如下：

步驟1：構(gòu)造近鄰域，利用流形距離計(jì)算鄰域點(diǎn)數(shù)。

步驟2：計(jì)算在高維空間權(quán)值矩陣W。

步驟4：求解特征方程K(G+GT-GGT)Kp=λK2p的前d個(gè)最大特征值對(duì)應(yīng)的特征向量p1，p2，…，pd.

步驟5：求低維嵌入Y

6 實(shí)驗(yàn)仿真

為了驗(yàn)證所提算法的性能，本文采用經(jīng)典實(shí)驗(yàn)數(shù)據(jù)集Swiss roll，Swiss hold，Gaussion，Corner Planes 來(lái)說(shuō)明本文提出的算法能夠有效地處理非線性流形數(shù)據(jù)集。數(shù)據(jù)集的采樣點(diǎn)數(shù)N=2000，分別選取鄰域參數(shù)k=14，k=20，k=26。實(shí)驗(yàn)結(jié)果如圖1，2，3 所示。圖中分別給出了數(shù)據(jù)集 Swiss roll，Swiss hold，Gaussion，Corner Planes 在不同鄰域參數(shù)k下的低維嵌入結(jié)果。從圖中可以看出改進(jìn)的LLE算法較原LLE算法性能有所改善，能夠得到良好的低維嵌入結(jié)果，在一定范圍內(nèi)低維嵌入結(jié)果具有穩(wěn)定性，對(duì)鄰域參數(shù)K 敏感度低。如圖2 所示為不同鄰域參數(shù)下改進(jìn)的LLE 方法的降維效果，其中（a）為加入噪聲的Swiss roll 數(shù)據(jù)集，與圖1 所示的不同鄰域參數(shù)下LLE 方法的降維效果相比較可得出本文提出的算法對(duì)含噪數(shù)據(jù)集Swiss roll 有良好的降維結(jié)果，能夠很好地發(fā)現(xiàn)Swiss roll數(shù)據(jù)集的內(nèi)在流形結(jié)構(gòu)。如圖3 所示，（a1），（a2），（a3）為其他三種經(jīng)典的含噪數(shù)據(jù)集。改進(jìn)的LLE 算法對(duì)四種經(jīng)典數(shù)據(jù)集的降維不依賴于鄰域參數(shù)的變化而變化，即對(duì)鄰域參數(shù)的選取不太敏感，可以達(dá)到很好的降維效果，而且對(duì)Swiss hold 數(shù)據(jù)集可以很好地反映數(shù)據(jù)集中的空洞，對(duì)不同的參數(shù)k 可以達(dá)到穩(wěn)定的降維效果，如圖3（b1），（c1），（d1）所示，橫坐標(biāo)為x軸，縱坐標(biāo)為y軸。該算法對(duì)實(shí)驗(yàn)數(shù)據(jù)集Gaussian、Corner Planes 等也具有良好的二維嵌入結(jié)果。說(shuō)明流形距離的測(cè)試能有效克服原始LLE 算法對(duì)鄰域參數(shù)的敏感問(wèn)題，能夠創(chuàng)建正確反映流形結(jié)構(gòu)的領(lǐng)域圖；基于壓縮感知的核稀疏投影可以實(shí)現(xiàn)低維嵌入時(shí)的降噪過(guò)程，并且可以很好地發(fā)現(xiàn)Swiss hold、Swiss hold、Gaussian、Corner Planes 四種數(shù)據(jù)集的內(nèi)在流形結(jié)構(gòu)。

圖1 不同鄰域參數(shù)下LLE方法的降維效果

圖2 不同鄰域參數(shù)下改進(jìn)的LLE方法的降維效果

圖3 不同鄰域參數(shù)下改進(jìn)的LLE方法的降維效果

7 結(jié)語(yǔ)

本文針對(duì)局部線性嵌入算法中鄰域參數(shù)選擇問(wèn)題，提出了一種基于流形距離的鄰域選擇算法，該算法用流形距離代替?zhèn)鹘y(tǒng)的歐氏距離作為相似性度量，利用流形距離測(cè)度合理地選取各個(gè)樣本的近鄰點(diǎn)。采用基于壓縮感知理論的核稀疏投影作為高維觀測(cè)空間到低維嵌入空間的映射。結(jié)合上述兩種思想對(duì)局部線性嵌入算法進(jìn)行改進(jìn)，實(shí)現(xiàn)高維數(shù)據(jù)的降維。實(shí)驗(yàn)結(jié)果表明，本文提出的流形距離與壓縮感知核稀疏投影相結(jié)合的局部線性嵌入算法可以有效避免原始局部線性嵌入算法對(duì)選取近鄰參數(shù)K 的不確定性及對(duì)噪聲的敏感性，可以很好地發(fā)現(xiàn)高維數(shù)據(jù)集上的內(nèi)在流形結(jié)構(gòu)。

稀疏投影作為一種高維空間到低維空間的映射，可以實(shí)現(xiàn)數(shù)據(jù)集在稀疏采樣時(shí)的鄰域選擇問(wèn)題。后續(xù)工作將主要研究稀疏采樣時(shí)鄰域的選取并將核稀疏投影引入到其他幾種經(jīng)典的流形學(xué)習(xí)算法中。