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

過伶俐，陳秀宏

（江南大學 人工智能與計算機學院, 江蘇 無錫 214122）

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

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

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

雖然以上無監督特征選擇方法在各種應用中取得一定的效果，但是這些方法還存在一些不足。首先，這些方法都假設數據是獨立同分布的，然而現實中的數據來源不同，即使同源數據也會受到外部條件（如光照、角度）影響，因而真實的數據實例不僅與高維特征相關，還與數據之間的內在聯系有關。其次，大多數方法都是度量原始數據空間中的特征重要性，這些方法的性能通常受到噪聲特征和樣本的影響。而且，這些方法在數據流形學習中都只利用相鄰數據點之間的信息，忽略不相鄰數據對之間可能存在的關聯。基于以上問題，本文提出了一種新穎且簡潔的潛在多步馬爾可夫概率的魯棒無監督特征選擇方法。

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

1 相關工作

1.1 符號的定義

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

1.2 多步馬爾可夫轉移概率

高維空間中數據點可視為一個節點或狀態，數據xi到數據xj的一步轉移概率定義為

其中

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

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

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

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

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

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

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

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

設P(1)為一步轉移概率所組成的矩陣，且狀態空間T={1,2,···}，那么系統狀態的一步轉移概率為

數據xi和數據xj的t步最小多步馬爾可夫轉移概率為

V1描 述了數據點與其他u步可達的數據點之間的最小轉移關系，即松散關系。而數據間的最大多步馬爾可夫轉移概率關系，即緊密關系為

詳細過程可見算法1，算法中學習數據流形結構的核心是多步馬爾可夫轉移概率，一定步數可達的最大馬爾可夫轉移概率描述了該數據對間的緊湊結構，而在一定步數可達的最小馬爾可夫轉移概率則描述該數據對間的松散結構。因此馬爾可夫步[23]描述兩個數據樣本間的松緊關系，可進一步應用到聚類或分類任務中。

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

算法1求數據X的u步最大馬爾可夫轉移概率關系矩陣V2

輸入數據矩陣X∈Rd×n，馬爾可夫步數u

初始化馬爾可夫步數t=0，

計算數據間的歐氏距離D∈Rn×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

輸出 關系矩陣V2

1.3 潛在表示學習

潛在表示學習[24](latent representation learning,LRL)有利于數據挖掘和機器學習任務，特別是對于網絡數據的處理。非負矩陣分解(nonnegative matrix factorization, NMF)[25-26]主要是圍繞具有線性結構的數據進行聚類，但其并不適用于所有類型的數據聚類，例如，一組圖像會形成多個一維非線性流形。

而SymNMF模型不僅繼承了NMF的可解釋性[27]，還挖掘了數據的潛在聚類結構。假設同類數據的相似度更大，異類數據的相似度更小，越小，非負矩陣H捕捉的聚類結構越完整。SymNMF 過程就是對數據進行潛在表示學習的過程，其目標是將相似性矩陣A∈Rn×n進行對稱非負分解，分解為低維潛在空間中非負矩陣H與其轉置矩陣HT的乘積：

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

其中 σ ＞0為寬度參數。

由于SymNMF 模型在線性和非線性流形上都能獲得更好的聚類結構，因此可以借用該思想從數據樣本的親和矩陣中學習潛在表示并進行無監督特征選擇。

2 模型和算法

2.1 模型建立

在潛在表示中，潛在因子對樣本的一些隱藏屬性進行編碼，而這些隱藏屬性與數據樣本的某些特征（或屬性）是相關的。因此，對潛在表示矩陣進行稀疏多元線性回歸模型得：

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

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

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

前文提到最大多步馬爾可夫轉移概率在保留任意數據對的局部流形結構的同時，還能描述該數據與較遠點數據間的緊密關系。因此最大馬爾可夫轉移概率矩陣比相似性矩陣更適合潛在表示學習。基于以上分析，本文將最大多步馬爾可夫轉移概率與潛在表示的稀疏回歸模型相結合，給出一個簡潔新穎的無監督特征選擇模型(unsupervised feature selection via multi-step Markov probability and latent representation, MMLRL)：

式中V∈Rn×n是最大多步馬爾可夫轉移概率關系矩陣，可由算法學習得到。

2.2 優化算法

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

2.2.1 固定W更新H

當W固定時，目標函數(式(11))改寫為

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

對L(H,Θ) 關于H求導數并令其等于0 得:

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

其中 ←是賦值符號。

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

其中 ?為Hadamard 積。

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

對式(19)等號兩邊關于H求導得：

等式(21)兩邊同時與H進行Hadamard 積運算得：

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

2.2.2 固定H更新W

當H固定時，可得以下關于W的優化問題：

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

式(25)中的目標函數的第一項為

然后對式(25)中的目標函數所有項關于W求導并令其為0 解得：

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

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

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

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

根據算法1 計算X的u步最大馬爾可夫轉移概率關系矩陣V；

While 不收斂 do

1) 計算對角矩陣Λ(t)

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

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

4)t=t+1

End while

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

3 實驗分析

本節將MMLRL 算法在7 個公開數據集上進行特征選擇實驗，并與8 個特征選擇算法對比，全面評估和驗證MMLRL 算法的性能和有效性。

3.1 數據集

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

表1 數據集具體信息Table 1 Specific information of data sets

3.2 對比算法及實驗設置

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

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

聚類實驗的評價指標通常有聚類精度(clustering accuracy, ACC)和標準化互信息(normalized mutual information, NMI)，ACC 的定義如下：

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

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

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

分類實驗的評價指標為分類精度(classification accuracy, ACA)，定義如下：

式中：yi是 數據xi的真實標簽，是 數據xi的預測標簽。T是測試樣本數，yi=時，=1，否則=0。

3.3 聚類性能與分析

算法獲取帶有重要特征的數據后，用K均值方法對這些數據進行聚類，通過聚類效果反映算法的性能。通常用聚類精度和標準化互信息來衡量聚類效果，ACC 值或NMI 值越大，算法聚類性能越好。實驗重復運行20 次K 均值聚類，從而消除初始點對聚類效果的影響。

表2 和表3 分別列出了所有算法在不同數據集上進行特征選擇的ACC 和NMI 的平均值和標準差，以及取得最好效果時所選的特征數，最優結果用粗體突出標示，次優結果用下劃線標出。

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

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

由表2 和表3 可知，MMLRL 除了在ORL 數據集上取得次優的ACC 和較優的NMI 外，在其他數據集上均取得最好的ACC 和NMI。這是因為MMLRL 算法通過多步馬爾可夫轉移概率不僅得到數據點與其相鄰點間的關系，還得到了該數據點與其較遠點之間的關系，充分利用和保持了流形上的數據結構；同時在純凈的潛在表示空間中選擇特征，減少了噪聲或異常值的影響。

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

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

3.4 運行時間

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

表4 不同方法運行時間Table 4 Running time of different methods

3.5 分類性能與分析

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

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

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

3.6 噪聲對聚類精度的影響

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

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

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

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

3.7 特征選擇圖

圖3 給出了6 種算法關于ORL 數據集側臉圖像的特征選擇圖。

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

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

3.8 參數對聚類精度的影響

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

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

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

4 結束語

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

以上模型是在數據空間中學習潛在表示的，為進一步提高特征選擇和聚類的性能，也可以在特征空間中學習潛在表示，從而同時學習數據和特征的內在互聯信息。因此可以對模型結構進行擴展以提高聚類效果。