潛在多步馬爾可夫概率的魯棒無監(jiān)督特征選擇

過伶俐，陳秀宏

（江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院, 江蘇 無錫 214122）

隨著信息技術(shù)的發(fā)展，機(jī)器學(xué)習(xí)在實(shí)際應(yīng)用中受到越來越多的關(guān)注[1-5]。與此同時(shí)機(jī)器學(xué)習(xí)處理的數(shù)據(jù)維度也越來越高，高維數(shù)據(jù)中的冗余特征和噪聲也越來越多，因此有必要剔除數(shù)據(jù)中的冗余和不相關(guān)特征[6]。數(shù)據(jù)降維是一種尋找數(shù)據(jù)重要特征并降低維度的數(shù)據(jù)挖掘技術(shù)，通常數(shù)據(jù)降維方法有特征選擇[7]和特征提取[8]兩種。特征選擇根據(jù)學(xué)習(xí)規(guī)則從高維數(shù)據(jù)中選取重要特征子集[9]，因此不會(huì)改變數(shù)據(jù)的原始特征；特征提取是通過學(xué)習(xí)高維數(shù)據(jù)在低維空間中的轉(zhuǎn)換表達(dá)來降低數(shù)據(jù)維度[10]。根據(jù)有無數(shù)據(jù)標(biāo)簽，特征選擇方法可分為有監(jiān)督[11]、半監(jiān)督[12]和無監(jiān)督[13]3 種。本文中主要研究無監(jiān)督特征選擇方法。

無監(jiān)督特征選擇方法可分為過濾式[14]、包裹式[15]和嵌入式[16]3 種。過濾式特征選擇方法是根據(jù)評(píng)估指標(biāo)給特征賦權(quán)重，按權(quán)重大小選擇重要特征，整個(gè)過程獨(dú)立于學(xué)習(xí)算法，常見的評(píng)估指標(biāo)有拉普拉斯分?jǐn)?shù)(Laplacian score for feature selection, LS)[14]和特征相似度。包裹式特征選擇方法是根據(jù)學(xué)習(xí)器的性能從原始特征子集中選擇最優(yōu)特征子集。嵌入式特征選擇方法[17-18]是學(xué)習(xí)特征權(quán)重，然后根據(jù)排序后的特征權(quán)重選擇最優(yōu)特征子集。與前兩者方法相比，嵌入式方法考慮了不同的數(shù)據(jù)屬性，如流形結(jié)構(gòu)和數(shù)據(jù)的先驗(yàn)分布等，因而性能更好。

近年來，無監(jiān)督特征選擇方法得到迅速發(fā)展。例如，Cai 等[16]利用圖拉普拉斯算子的特征向量來捕獲數(shù)據(jù)的多簇類結(jié)構(gòu)，提出用于多類數(shù)據(jù)的特征選擇方法(unsupervised feature selection for multi-cluster data, MCFS)。但該方法會(huì)獨(dú)立進(jìn)行流形結(jié)構(gòu)表示和特征選擇，這樣特征選擇的性能在很大程度上取決于圖的構(gòu)造效率。因此Hou 等[13]提出一種基于聯(lián)合嵌入學(xué)習(xí)和稀疏回歸(joint embedding learning and sparse regression: a framework for unsupervised feature selection, JELSR)的無監(jiān)督特征選擇框架，通過學(xué)習(xí)稀疏變換矩陣來進(jìn)行特征選擇。Zhu 等[19]提出特征自表示模型(unsupervised feature selection by regularized self-representation, RSR)，通過對(duì)特征矩陣本身進(jìn)行表示，找出具有代表性的特征分量。為了使特征選擇過程不過度依賴最初學(xué)到的流形結(jié)構(gòu)，Nie 等[20]提出了自適應(yīng)的特征選擇方法(unsupervised feature selection with structured graph optimization, SOGFS)，該方法將特征選擇和局部結(jié)構(gòu)學(xué)習(xí)相結(jié)合。Li 等[21]則提出自適應(yīng)廣義不相關(guān)的無監(jiān)督特征選擇方法(generalized uncorrelated regression with adaptive graph for unsupervised feature selection, URAFS)，在廣義不相關(guān)模型中添加基于最大熵原理的圖正則化項(xiàng)，從而將數(shù)據(jù)局部幾何結(jié)構(gòu)嵌入流形學(xué)習(xí)中。目前大部分算法都是在歐氏距離的基礎(chǔ)上學(xué)習(xí)數(shù)據(jù)的流形結(jié)構(gòu)，而Min 等[22]通過多步馬爾可夫概率關(guān)系來描述數(shù)據(jù)結(jié)構(gòu)從而進(jìn)行無監(jiān)督特征選擇(unsupervised feature selection via multi-step Markov probability relationship, MMFS)。

雖然以上無監(jiān)督特征選擇方法在各種應(yīng)用中取得一定的效果，但是這些方法還存在一些不足。首先，這些方法都假設(shè)數(shù)據(jù)是獨(dú)立同分布的，然而現(xiàn)實(shí)中的數(shù)據(jù)來源不同，即使同源數(shù)據(jù)也會(huì)受到外部條件（如光照、角度）影響，因而真實(shí)的數(shù)據(jù)實(shí)例不僅與高維特征相關(guān)，還與數(shù)據(jù)之間的內(nèi)在聯(lián)系有關(guān)。其次，大多數(shù)方法都是度量原始數(shù)據(jù)空間中的特征重要性，這些方法的性能通常受到噪聲特征和樣本的影響。而且，這些方法在數(shù)據(jù)流形學(xué)習(xí)中都只利用相鄰數(shù)據(jù)點(diǎn)之間的信息，忽略不相鄰數(shù)據(jù)對(duì)之間可能存在的關(guān)聯(lián)?；谝陨蠁栴}，本文提出了一種新穎且簡潔的潛在多步馬爾可夫概率的魯棒無監(jiān)督特征選擇方法。

該方法借助多步馬爾可夫轉(zhuǎn)移概率構(gòu)造數(shù)據(jù)間的親和矩陣，充分挖掘數(shù)據(jù)之間的流形結(jié)構(gòu)。然后利用對(duì)稱非負(fù)矩陣分解(symmetric nonnegative matrix factorization, SymNMF)學(xué)習(xí)原始數(shù)據(jù)的潛在表示，最后將潛在表示學(xué)習(xí)嵌入到稀疏回歸模型(sparse regression model)中進(jìn)行特征選擇。多步馬爾可夫轉(zhuǎn)移概率矩陣可以描述數(shù)據(jù)與相鄰數(shù)據(jù)點(diǎn)和非相鄰數(shù)據(jù)點(diǎn)之間的關(guān)系，在基于這種關(guān)系構(gòu)造的潛在表示空間中進(jìn)行特征選擇，不僅能選擇重要特征還能去除冗余特征和噪聲，增強(qiáng)算法的魯棒性。

1 相關(guān)工作

1.1 符號(hào)的定義

在本文中，矩陣用粗斜體大寫字母表示，向量用粗斜體小寫字母表示。X=[x1x2···xn]∈Rd×n是數(shù)據(jù)矩陣，d是樣本維度，即特征數(shù)，n是樣本個(gè)數(shù)。對(duì) 于 任 意 矩 陣X∈Rd×n，xij是X的 第i行 第j列元素，矩陣XT為X的轉(zhuǎn)置矩陣， tr(X)為X的跡。X的F-范數(shù)定義為的L2,1范數(shù)定義為

1.2 多步馬爾可夫轉(zhuǎn)移概率

高維空間中數(shù)據(jù)點(diǎn)可視為一個(gè)節(jié)點(diǎn)或狀態(tài)，數(shù)據(jù)xi到數(shù)據(jù)xj的一步轉(zhuǎn)移概率定義為

其中

式中D是歐氏距離矩陣。式（1）和（2）有兩點(diǎn)值得注意：1）任意數(shù)據(jù)點(diǎn)的自轉(zhuǎn)移概率為0，即Pii=0；2）隨著數(shù)據(jù)維度的增加歐氏距離并不能很好反映所有數(shù)據(jù)點(diǎn)之間的關(guān)系，但流形的局部微小結(jié)構(gòu)同構(gòu)于歐氏空間，因此非常接近的數(shù)據(jù)點(diǎn)之間的一步轉(zhuǎn)移概率是可以借助歐氏距離來計(jì)算的。從式(1)和式(2)可知兩個(gè)數(shù)據(jù)的關(guān)系越近，數(shù)據(jù)的一步轉(zhuǎn)移概率越大。由定理1 得數(shù)據(jù)的u步轉(zhuǎn)移概率為

定理1設(shè) {Xu,u∈T}為馬爾可夫鏈，則對(duì)任意整數(shù)u≥0,i,j∈I，u步轉(zhuǎn)移概率具有性質(zhì)P(u)=P(u-1)P(1)。

定義1若隨機(jī)過程{Xu,u∈T}對(duì)于任意的非負(fù)整數(shù)u∈T和任意的i0,i1,···,iu+1∈I，其條件概率滿足

則稱 {Xu,u∈T}為馬爾可夫鏈。

定義1 中馬爾可夫過程 {Xu,u∈T}的參數(shù)集T是離散的時(shí)間集合，即T={0,1,2,···}，Xu取值的狀態(tài)空間是離散的狀態(tài)集I={i0,i1,i2,···}。

定理1 證明：利用全概率公式及定義1 中的馬爾可夫性，有：

令l=1，根據(jù)定義2 及矩陣乘法的運(yùn)算法則得P(u)=P(u-1)P(1)，定理1 得證。

定義2若對(duì)任意的i,j∈I，馬爾可夫鏈{Xu,u∈T} 的 轉(zhuǎn)移概率p(iuj)與u無 關(guān)，則稱馬爾可夫鏈{Xu,u∈T} 是 齊次的，并記為pij。

設(shè)P(1)為一步轉(zhuǎn)移概率所組成的矩陣，且狀態(tài)空間T={1,2,···}，那么系統(tǒng)狀態(tài)的一步轉(zhuǎn)移概率為

數(shù)據(jù)xi和數(shù)據(jù)xj的t步最小多步馬爾可夫轉(zhuǎn)移概率為

V1描 述了數(shù)據(jù)點(diǎn)與其他u步可達(dá)的數(shù)據(jù)點(diǎn)之間的最小轉(zhuǎn)移關(guān)系，即松散關(guān)系。而數(shù)據(jù)間的最大多步馬爾可夫轉(zhuǎn)移概率關(guān)系，即緊密關(guān)系為

詳細(xì)過程可見算法1，算法中學(xué)習(xí)數(shù)據(jù)流形結(jié)構(gòu)的核心是多步馬爾可夫轉(zhuǎn)移概率，一定步數(shù)可達(dá)的最大馬爾可夫轉(zhuǎn)移概率描述了該數(shù)據(jù)對(duì)間的緊湊結(jié)構(gòu)，而在一定步數(shù)可達(dá)的最小馬爾可夫轉(zhuǎn)移概率則描述該數(shù)據(jù)對(duì)間的松散結(jié)構(gòu)。因此馬爾可夫步[23]描述兩個(gè)數(shù)據(jù)樣本間的松緊關(guān)系，可進(jìn)一步應(yīng)用到聚類或分類任務(wù)中。

MMFS[22]方法在獲得多步馬爾可夫轉(zhuǎn)移概率矩陣V1或V2后，直接將其應(yīng)用于特征選擇模板F1=V1XT或F2=V2XT中選擇特征。該方法雖然能自然地表征數(shù)據(jù)的流形結(jié)構(gòu)，但是算法的特征選擇能力很容易受噪聲或異常值的影響，隨著數(shù)據(jù)維度和特征維度的不斷增加，從原始數(shù)據(jù)空間選擇的特征質(zhì)量會(huì)下降。如果從潛在表示空間中選擇特征，就能很好地減弱噪聲對(duì)算法模型的影響，提高算法的魯棒性。

算法1求數(shù)據(jù)X的u步最大馬爾可夫轉(zhuǎn)移概率關(guān)系矩陣V2

輸入數(shù)據(jù)矩陣X∈Rd×n，馬爾可夫步數(shù)u

初始化馬爾可夫步數(shù)t=0，

計(jì)算數(shù)據(jù)間的歐氏距離D∈Rn×n；

計(jì)算一步馬爾可夫轉(zhuǎn)移概率P(1)：

其中Pii=0且Pij=0, ifxj?Nk(xi)

Whilet＜udo

1)P(t)=P(t-1)P(1)；

3)t=t+1

End while

輸出 關(guān)系矩陣V2

1.3 潛在表示學(xué)習(xí)

潛在表示學(xué)習(xí)[24](latent representation learning,LRL)有利于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)任務(wù)，特別是對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的處理。非負(fù)矩陣分解(nonnegative matrix factorization, NMF)[25-26]主要是圍繞具有線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行聚類，但其并不適用于所有類型的數(shù)據(jù)聚類，例如，一組圖像會(huì)形成多個(gè)一維非線性流形。

而SymNMF模型不僅繼承了NMF的可解釋性[27]，還挖掘了數(shù)據(jù)的潛在聚類結(jié)構(gòu)。假設(shè)同類數(shù)據(jù)的相似度更大，異類數(shù)據(jù)的相似度更小，越小，非負(fù)矩陣H捕捉的聚類結(jié)構(gòu)越完整。SymNMF 過程就是對(duì)數(shù)據(jù)進(jìn)行潛在表示學(xué)習(xí)的過程，其目標(biāo)是將相似性矩陣A∈Rn×n進(jìn)行對(duì)稱非負(fù)分解，分解為低維潛在空間中非負(fù)矩陣H與其轉(zhuǎn)置矩陣HT的乘積：

式中：H∈Rn×c是n個(gè)數(shù)據(jù)的潛在表示矩陣；c是潛在因子數(shù)，且c＜min{d,n}；

其中 σ ＞0為寬度參數(shù)。

由于SymNMF 模型在線性和非線性流形上都能獲得更好的聚類結(jié)構(gòu)，因此可以借用該思想從數(shù)據(jù)樣本的親和矩陣中學(xué)習(xí)潛在表示并進(jìn)行無監(jiān)督特征選擇。

2 模型和算法

2.1 模型建立

在潛在表示中，潛在因子對(duì)樣本的一些隱藏屬性進(jìn)行編碼，而這些隱藏屬性與數(shù)據(jù)樣本的某些特征（或?qū)傩裕┦窍嚓P(guān)的。因此，對(duì)潛在表示矩陣進(jìn)行稀疏多元線性回歸模型得：

式中：W∈Rd×c是回歸系數(shù)矩陣；矩陣H∈Rn×c可作為偽標(biāo)簽矩陣，可為特征選擇提供判別信息。參數(shù) α控制模型稀疏度。

將潛在表示學(xué)習(xí)的式(9)與稀疏回歸模型式(11)相結(jié)合，得到基于稀疏正則化的潛在表示學(xué)習(xí)的特征選擇模型：

式中：A是如式(10) 定義的數(shù)據(jù)相似性對(duì)稱矩陣。但是，這種相似性矩陣A只保留了鄰接數(shù)據(jù)點(diǎn)之間的相似關(guān)系，而沒有考慮非鄰接數(shù)據(jù)對(duì)之間可能存在的關(guān)系，即相似矩陣不能真實(shí)反映數(shù)據(jù)實(shí)例之間的關(guān)系。

前文提到最大多步馬爾可夫轉(zhuǎn)移概率在保留任意數(shù)據(jù)對(duì)的局部流形結(jié)構(gòu)的同時(shí)，還能描述該數(shù)據(jù)與較遠(yuǎn)點(diǎn)數(shù)據(jù)間的緊密關(guān)系。因此最大馬爾可夫轉(zhuǎn)移概率矩陣比相似性矩陣更適合潛在表示學(xué)習(xí)?；谝陨戏治?，本文將最大多步馬爾可夫轉(zhuǎn)移概率與潛在表示的稀疏回歸模型相結(jié)合，給出一個(gè)簡潔新穎的無監(jiān)督特征選擇模型(unsupervised feature selection via multi-step Markov probability and latent representation, MMLRL)：

式中V∈Rn×n是最大多步馬爾可夫轉(zhuǎn)移概率關(guān)系矩陣，可由算法學(xué)習(xí)得到。

2.2 優(yōu)化算法

式(13)用交替方向法（alternatingdirection minimizing,ADM）求解[28]，使用交替迭代優(yōu)化策略逐個(gè)迭代更新模型中的變量。

2.2.1 固定W更新H

當(dāng)W固定時(shí)，目標(biāo)函數(shù)(式(11))改寫為

于是，使用拉格朗日乘子法求解問題(式(14))。設(shè)約束H≥0的 拉格朗日乘子為 Θ ∈Rc×n，則式(14)中目標(biāo)函數(shù)的拉格朗日函數(shù)為

對(duì)L(H,Θ) 關(guān)于H求導(dǎo)數(shù)并令其等于0 得:

由Kuhn-Tucker 條件 Θi jHij=0 及 定理2 得H的更新規(guī)則為[29]

其中 ←是賦值符號(hào)。

定理2如果H是式(14)中目標(biāo)函數(shù)的一個(gè)局部最小值，那么：

其中 ?為Hadamard 積。

證明Θ ∈Rc×n為約束H≥0的拉格朗日乘子，拉格朗日函數(shù)為L(H,Θ)，Kuhn-Tucker 條件有：

對(duì)式(19)等號(hào)兩邊關(guān)于H求導(dǎo)得：

等式(21)兩邊同時(shí)與H進(jìn)行Hadamard 積運(yùn)算得：

由式(20)的 Θ?H=0得：

2.2.2 固定H更新W

當(dāng)H固定時(shí)，可得以下關(guān)于W的優(yōu)化問題：

對(duì)于問題式（24）使用迭代加權(quán)（iterative reweighted least-squares, IRLS）最小二乘法[19,30]求解。先引入對(duì)角矩陣 Λ(t)∈Rd×d，如果因此式(24)轉(zhuǎn)化為以下問題：

式(25)中的目標(biāo)函數(shù)的第一項(xiàng)為

然后對(duì)式(25)中的目標(biāo)函數(shù)所有項(xiàng)關(guān)于W求導(dǎo)并令其為0 解得：

以上求解H和W過程交替地重復(fù)進(jìn)行，直到滿足終止條件，詳細(xì)過程見算法2。在求得矩陣之后，可根據(jù)其行向量的2-范數(shù)來衡量數(shù)據(jù)中對(duì)應(yīng)特征的重要性，如果中某行的2-范數(shù)趨于0，則對(duì)應(yīng)的特征為冗余或不相關(guān)特征。因此將所有行向量的2-范數(shù)進(jìn)行排序，值越大代表數(shù)據(jù)相應(yīng)特征越重要。最后，對(duì)特征選擇后所得到的樣本進(jìn)行聚類或分類。

算法2MMLRL 用于求解問題式(13)

輸入數(shù)據(jù)矩陣X∈Rd×n，馬爾可夫步數(shù)u，正則化參數(shù) α ，β

初始化W(0)∈In×n，隨機(jī)矩陣H(0)∈Rn×c，迭代次數(shù)t=0

根據(jù)算法1 計(jì)算X的u步最大馬爾可夫轉(zhuǎn)移概率關(guān)系矩陣V；

While 不收斂 do

1) 計(jì)算對(duì)角矩陣Λ(t)

2) 根據(jù)乘法法則式(17)更新H(t+1)；

3) 根據(jù)式(27)更新W(t+1)

4)t=t+1

End while

輸出 變換矩陣=W(t+1)∈Rd×c

3 實(shí)驗(yàn)分析

本節(jié)將MMLRL 算法在7 個(gè)公開數(shù)據(jù)集上進(jìn)行特征選擇實(shí)驗(yàn)，并與8 個(gè)特征選擇算法對(duì)比，全面評(píng)估和驗(yàn)證MMLRL 算法的性能和有效性。

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

實(shí)驗(yàn)中的數(shù)據(jù)集包括兩個(gè)人臉數(shù)據(jù)集ORL-32[31]和warpAR10P[19]，物體數(shù)據(jù)集COIL-20[32],手寫字體數(shù)據(jù)集USPS[33],語音數(shù)據(jù)集Isolet[34]以及兩個(gè)生物數(shù)據(jù)集Lung[35]和CLL_SUB_111[36]。數(shù)據(jù)集的具體信息如表1 所示。

表1 數(shù)據(jù)集具體信息Table 1 Specific information of data sets

3.2 對(duì)比算法及實(shí)驗(yàn)設(shè)置

多聚類特征選擇(MCFS)[16]、嵌入式稀疏正則化(JELSR)[13]；自表示特征選擇(RSR)[19]、結(jié)構(gòu)圖優(yōu)化(S OGFS)[20]、廣義不相關(guān)的自適應(yīng)圖特征選擇(URAFS)[21]、潛在表示與流形正則化(unsuper-實(shí)驗(yàn)中的對(duì)比算法包括：拉普拉斯算子(LS)[14]、vised featureselection via latent representationlearningand manifold regularization, LRLMR)[37]、基于多步馬爾可夫概率的無監(jiān)督特征選擇(MMFS)[22]。

為保證實(shí)驗(yàn)公正性，近鄰數(shù)k設(shè)置為5，通過網(wǎng)格搜索策略確定每個(gè)算法的最優(yōu)參數(shù)組，參數(shù)范圍為{10-3,10-2,10-1, 1, 10,102,103}。除了USPS 數(shù)據(jù)集的特征選擇范圍為{50, 80, 110, 140,170, 200}，其余數(shù)據(jù)集上特征選擇的范圍為{50,100, 150, 200, 250, 300}。

聚類實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)通常有聚類精度(clustering accuracy, ACC)和標(biāo)準(zhǔn)化互信息(normalized mutual information, NMI)，ACC 的定義如下：

式中：qi為數(shù)據(jù)xi的聚類標(biāo)簽，pi為xi的真實(shí)標(biāo)簽。當(dāng)x=y時(shí) ， δ(x,y)=1， 否則 δ(x,y)=0。 map(qi)為最佳映射函數(shù)，該函數(shù)通過最大權(quán)匹配(Kuhn-Munkres)算法將聚類標(biāo)簽與真實(shí)標(biāo)簽進(jìn)行匹配。NMI 表示聚類結(jié)果與真實(shí)標(biāo)簽的同一性，其定義為

式中：H(P)和H(Q) 分別為變量P和變量Q的熵，聚類中P和Q分別為聚類結(jié)果和真實(shí)標(biāo)簽，IM(P,Q)為P和Q的互信息。

式中：P(pi) 為 樣本屬于pi類的概率，P(qj)為樣本屬于qj類的概率。P(pi,qj) 為樣本同屬于pi類和qj類的聯(lián)合概率。

分類實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)為分類精度(classification accuracy, ACA)，定義如下：

式中：yi是 數(shù)據(jù)xi的真實(shí)標(biāo)簽，是 數(shù)據(jù)xi的預(yù)測標(biāo)簽。T是測試樣本數(shù)，yi=時(shí)，=1，否則=0。

3.3 聚類性能與分析

算法獲取帶有重要特征的數(shù)據(jù)后，用K均值方法對(duì)這些數(shù)據(jù)進(jìn)行聚類，通過聚類效果反映算法的性能。通常用聚類精度和標(biāo)準(zhǔn)化互信息來衡量聚類效果，ACC 值或NMI 值越大，算法聚類性能越好。實(shí)驗(yàn)重復(fù)運(yùn)行20 次K 均值聚類，從而消除初始點(diǎn)對(duì)聚類效果的影響。

表2 和表3 分別列出了所有算法在不同數(shù)據(jù)集上進(jìn)行特征選擇的ACC 和NMI 的平均值和標(biāo)準(zhǔn)差，以及取得最好效果時(shí)所選的特征數(shù)，最優(yōu)結(jié)果用粗體突出標(biāo)示，次優(yōu)結(jié)果用下劃線標(biāo)出。

表2 不同方法在6 個(gè)數(shù)據(jù)集上的聚類精度(ACC±std)及所選特征數(shù)Table 2 Clustering accuracies (ACC ± std) and the numbers of selected features of different algorithms on six datasets %

表3 不同方法在6 個(gè)數(shù)據(jù)集上的歸一化互信息(NMI±std)及所選特征數(shù)Table 3 NMI values (NMI ± std) and the number of selected features of different algorithms on six datasets %

由表2 和表3 可知，MMLRL 除了在ORL 數(shù)據(jù)集上取得次優(yōu)的ACC 和較優(yōu)的NMI 外，在其他數(shù)據(jù)集上均取得最好的ACC 和NMI。這是因?yàn)镸MLRL 算法通過多步馬爾可夫轉(zhuǎn)移概率不僅得到數(shù)據(jù)點(diǎn)與其相鄰點(diǎn)間的關(guān)系，還得到了該數(shù)據(jù)點(diǎn)與其較遠(yuǎn)點(diǎn)之間的關(guān)系，充分利用和保持了流形上的數(shù)據(jù)結(jié)構(gòu)；同時(shí)在純凈的潛在表示空間中選擇特征，減少了噪聲或異常值的影響。

其次，考慮特征選擇數(shù)對(duì)聚類精度的影響，圖1 給出6 種算法在不同數(shù)據(jù)集上選擇不同特征數(shù)時(shí)ACC 值的變化曲線。由圖1 可見，隨著特征選擇數(shù)的增加，MMLRL 算法的聚類精度穩(wěn)定地優(yōu)于其他對(duì)比算法，從而可以通過選擇合適的特征個(gè)數(shù)來獲得比其他算法更好的聚類精度。尤其在COIL_20 數(shù)據(jù)集上，不管選擇多少數(shù)目的特征，其ACC 都優(yōu)于其他對(duì)比算法，這說明可以選擇最小的特征數(shù)來得到最好的聚類效果，從而減少計(jì)算時(shí)間。

圖1 不同方法選擇不同特征數(shù)時(shí)的聚類精度(ACC)Fig.1 ACC of all the algorithms for different numbers of selected features on the six datasets

3.4 運(yùn)行時(shí)間

本節(jié)比較了8 種算法在ORL、COIL_20、USPS、Isolet 和Lung5 個(gè)數(shù)據(jù)集上進(jìn)行聚類實(shí)驗(yàn)的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如表4 所示。從表4 可以看出，本文提出的算法MMLRL 同MCFS、SOGFS 和MMFS算法相比，運(yùn)行時(shí)間更短，與其他對(duì)比算法相比運(yùn)行時(shí)間相當(dāng)。MMLRL 算法在學(xué)習(xí)非鄰接數(shù)據(jù)點(diǎn)間的流形關(guān)系時(shí)會(huì)消耗些許時(shí)間，但增加的時(shí)間很少，而且這步有利于數(shù)據(jù)潛在表示學(xué)習(xí)。因此以很少的時(shí)間換取更好的特征選擇效果是可取的。

表4 不同方法運(yùn)行時(shí)間Table 4 Running time of different methods

3.5 分類性能與分析

本節(jié)通過KNN 分類法對(duì)6 個(gè)數(shù)據(jù)集上的多類數(shù)據(jù)進(jìn)行分類。除了USPS 數(shù)據(jù)集，其他數(shù)據(jù)集都隨機(jī)選擇每類的7 個(gè)樣本作為訓(xùn)練集，為了防止過擬合現(xiàn)象，在USPS 數(shù)據(jù)集中會(huì)隨機(jī)選擇每類的70 個(gè)樣本做為測試集，剩余的樣本作為測試集。由于CLL_SUB 數(shù)據(jù)集的類別數(shù)較少，因此將該數(shù)據(jù)集替換為10 類的warpAR10P 數(shù)據(jù)集。同時(shí)為了消除數(shù)據(jù)集劃分過程中可能存在的誤差，會(huì)隨機(jī)劃分?jǐn)?shù)據(jù)集5 次，然后取5 次結(jié)果的平均值作為最終結(jié)果。通常平均分類精度(ACA)用于衡量分類效果，ACA 值越大說明算法分類越精確。表5 給出了不同方法在6 個(gè)數(shù)據(jù)集上的分類精度(ACA)以及對(duì)應(yīng)的特征數(shù)，最好的結(jié)果用粗體表示。圖2 則為不同算法在6 個(gè)數(shù)據(jù)集上選擇不同特征數(shù)時(shí)的分類精度曲線。從表5 和圖2 可以看出，MMLRL 方法在COIL_20、USPS 和Isolet 數(shù)據(jù)集上取得顯著的分類效果，這說明該方法在預(yù)處理多類數(shù)據(jù)時(shí)更具優(yōu)勢。

圖2 6 個(gè)數(shù)據(jù)庫上選擇不同特征數(shù)時(shí)的分類精度Fig.2 ACA of all the algorithms for different numbers of features on the six datasets

表5 不同方法在6 個(gè)數(shù)據(jù)集上的分類精度(ACA±std)及所選特征數(shù)Table 5 Classification accuracies (ACA ± std) and the numbers of selected features of different algorithms on six datasets %

3.6 噪聲對(duì)聚類精度的影響

為驗(yàn)證MMLRL 算法在噪聲下的魯棒性，本節(jié)研究算法在噪聲數(shù)據(jù)集中聚類精度的變化情況，主要有兩種噪聲：在圖像中隨機(jī)加不同像素大小的遮擋塊和不同比例的點(diǎn)噪聲（如椒鹽噪聲），以COIL_20 數(shù)據(jù)集和Isolet 數(shù)據(jù)集為例。表6給出了9 種算法在有遮擋塊的COIL_20 數(shù)據(jù)集上的聚類精度變化情況，表7 則是8 種方法在包含不同比例椒鹽噪聲的Isolet 數(shù)據(jù)集上的聚類結(jié)果。

表6 不同算法在有遮擋塊的COIL_20 數(shù)據(jù)集上的聚類精度(ACC)Table 6 Clustering accuracies of different methods to block occlusion with different sizes on COIL_20dataset %

表7 不同方法在有點(diǎn)噪聲的Isolet 數(shù)據(jù)集上的聚類精度(ACC)Table 7 Clustering accuracies of different methods to different densities of salt and pepper noise on Isolet dataset %

由表6 可知，給COIL_20 數(shù)據(jù)集圖像隨機(jī)添加遮擋塊時(shí)，算法的聚類精度受到較大的影響，尤其是對(duì)RSR 算法的影響，到后期ACC 值降低到很小，而MMLRL 算法得到的ACC 值減少幅度很小，且能持續(xù)取得高于對(duì)比算法的聚類精度。表7 則表明，隨著Isolet 數(shù)據(jù)集中噪聲比例不斷加，MMLRL算法取得的ACC 值波動(dòng)很小，而且聚類效果優(yōu)于其他對(duì)比算法。這說明 MMLRL 算法學(xué)習(xí)有噪聲數(shù)據(jù)樣本的特征時(shí)具有一定的魯棒性，在噪聲特征或數(shù)據(jù)中依然能選擇出重要特征。

3.7 特征選擇圖

圖3 給出了6 種算法關(guān)于ORL 數(shù)據(jù)集側(cè)臉圖像的特征選擇圖。

圖3 不同算法對(duì)ORL 數(shù)據(jù)集的特征選擇圖Fig.3 Feature selected images of partial ORL data set by different algorithms

圖3(a)是原始側(cè)臉圖像，(b)～(g)是不同算法在原始圖像上選擇不同特征數(shù)時(shí)的圖像，特征選擇的范圍為{200, 250, 300, 350, 400, 450, 500}。觀察圖3(b)～(d)得知， LS 和SOGFS 算法的特征選擇效果最差，隨著特征選擇數(shù)的增加，只選擇面部特征，而重要五官特征都未被選擇。在圖3(c)～(e)中，MCFS 和LRLMR算法雖然選擇特征均勻，但不是重要的五官特征。相比于其他算法，MMLRL算法最后能選出重要的五官特征（眼、口、鼻），這也是MMLRL 算法在不同數(shù)據(jù)集上取得較好聚類效果的原因。

3.8 參數(shù)對(duì)聚類精度的影響

本節(jié)討論模型式(11)中正則化參數(shù) α 與 β對(duì)聚類精度的影響，圖4 給出了MMLRL 算法在不同數(shù)據(jù)集上取不同參數(shù)值時(shí)聚類精度圖。

圖4 不同參數(shù)組合下MMLRL 在6 個(gè)數(shù)據(jù)集上聚類精度Fig.4 Clustering accuracy of MMLRL algorithm with respect to α and β on six data sets

觀察圖4 得知，在除ORL 和Isolet 數(shù)據(jù)集外的其他數(shù)據(jù)集上，一個(gè)參數(shù)固定而另一參數(shù)變化時(shí)，ACC 都相對(duì)穩(wěn)定，這說明在大部分情況下MMLRL 算法受參數(shù)的影響較小。在ORL 數(shù)據(jù)集上，當(dāng) α ≥1，β ≤0.1時(shí)參數(shù)對(duì)算法的學(xué)習(xí)效果影響較小；在Isolet 數(shù)據(jù)集上，參數(shù)對(duì)聚類效果的影響較大。從以上分析可知，在實(shí)際情況下應(yīng)選擇合適的參數(shù)組來提高平均聚類精度。

4 結(jié)束語

本文提出了一種更為簡潔的潛在多步馬爾可夫概率的無監(jiān)督特征選擇模型。該模型利用多步馬爾可夫概率學(xué)習(xí)數(shù)據(jù)更為廣義的流形結(jié)構(gòu)，在學(xué)習(xí)相鄰數(shù)據(jù)點(diǎn)流形信息的同時(shí)充分挖掘非相鄰數(shù)據(jù)點(diǎn)之間的結(jié)構(gòu)信息；通過對(duì)稱非負(fù)矩陣分解模型來學(xué)習(xí)數(shù)據(jù)的潛在表示，并在潛在表示空間中選擇數(shù)據(jù)特征。模型在參數(shù)少和結(jié)構(gòu)更為簡單的情況下能取得更好的聚類效果。實(shí)驗(yàn)表明，MMLRL 算法能快速而有效地選擇數(shù)據(jù)的重要特征，降低噪聲或異常值的影響，證明了所提算法的有效性。

以上模型是在數(shù)據(jù)空間中學(xué)習(xí)潛在表示的，為進(jìn)一步提高特征選擇和聚類的性能，也可以在特征空間中學(xué)習(xí)潛在表示，從而同時(shí)學(xué)習(xí)數(shù)據(jù)和特征的內(nèi)在互聯(lián)信息。因此可以對(duì)模型結(jié)構(gòu)進(jìn)行擴(kuò)展以提高聚類效果。