聯(lián)合圖嵌入與特征加權(quán)的無監(jiān)督特征選擇

張 巍，張圳彬

（廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006）

伴隨著信息科技的飛快發(fā)展，在許多熱點研究領(lǐng)域， 如圖像、聲音、文本、視頻和基因工程等，人們通常需要面對體量龐大的高維度數(shù)據(jù)[1-2]。為此，降維方法中的特征選擇(Feature Selection)是處理此類數(shù)據(jù)的常規(guī)方法。根據(jù)某些指標(biāo)，在不改變數(shù)據(jù)原始表示的前提下，特征選擇從高維數(shù)據(jù)中挑選信息量最為豐富的維度構(gòu)成特征子集，該過程各特征原始物理意義將得到維持[3]，因此降維結(jié)果具備很好的解釋性。在大部分情形下對全部特征進(jìn)行采集將會是極其耗時耗力高開銷的或者是不可能的[4-5]，特征選擇只針對選擇的特征進(jìn)行采集，故特征選擇能減少待處理的數(shù)據(jù)量，有助于進(jìn)一步分析處理數(shù)據(jù)。

依據(jù)標(biāo)簽信息是否可用，特征選擇方法可分類為：無監(jiān)督(Unsupervised)、半監(jiān)督(Semi-supervised)和有監(jiān)督(Supervised)方法[6]。因為現(xiàn)實大部分?jǐn)?shù)據(jù)缺乏標(biāo)簽，對數(shù)據(jù)添加標(biāo)簽費力費時[7]。標(biāo)簽信息的缺乏使無監(jiān)督學(xué)習(xí)難于其他兩者。無監(jiān)督特征選擇可進(jìn)一步分為3類：過濾式(Filter)、包裹式(Wrapper)和嵌入式(Embedding)[8]。此處主要介紹嵌入式。嵌入式方法將數(shù)據(jù)分布先驗等數(shù)據(jù)屬性納入考慮，因此大多數(shù)情況下可以獲得較優(yōu)的特征信息。由于無監(jiān)督特征選擇具備捕獲數(shù)據(jù)隱藏結(jié)構(gòu)如局部流形結(jié)構(gòu)和全局結(jié)構(gòu)等的能力[9-10]，因此捕捉學(xué)習(xí)前者結(jié)構(gòu)的嵌入式無監(jiān)督特征選擇通常能得到良好的效果[11]。

目前特征選擇方法大多數(shù)采用嵌入式無監(jiān)督的方式構(gòu)建模型，但其中有些方法使得降維后的低維子空間特征判別性不強且存在冗余，導(dǎo)致選擇的特征不具有較強的代表性，影響模型的性能。本文通過將自適應(yīng)圖嵌入學(xué)習(xí)獲得的聚類指示矩陣在回歸中進(jìn)行擬合，并對低維的投影子空間施加正交約束，以此選擇出判別性強且非冗余的特征，并通過一個表征特征重要程度的特征權(quán)重對角矩陣，進(jìn)行特征選擇并形成特征子集，進(jìn)行后續(xù)任務(wù)處理。

1 國內(nèi)外研究現(xiàn)狀

國內(nèi)外學(xué)者對于無監(jiān)督特征選擇方法進(jìn)行了各種各樣的探索。Cai等[12]提出多簇特征選擇(Multi-Cluster Feature Selection， MCFS)，使用l1范數(shù)正則化來維持?jǐn)?shù)據(jù)的自然聚類的多簇結(jié)構(gòu)；Qian等[13]提出魯棒無監(jiān)督特征選擇(Robust Unsupervised Feature Selection， RUFS)，在無監(jiān)督聚類標(biāo)簽學(xué)習(xí)和特征學(xué)習(xí)過程同時利用最小化l2，1范數(shù)達(dá)到特征選擇的目的；Hou等[3]提出了聯(lián)合嵌入學(xué)習(xí)稀疏回歸(Joint Embedding Learning and Sparse Regression， JELSR)，使用譜聚類進(jìn)行數(shù)據(jù)聚類結(jié)構(gòu)學(xué)習(xí)，并使用系數(shù)回歸在同一過程完成特征選擇；Li等[14]提出了非負(fù)判別特征選擇(Nonnegative Discriminative Feature Selection， NDFS)，通過聯(lián)合非負(fù)譜分析和稀疏回歸統(tǒng)一學(xué)習(xí)以得到預(yù)想特征子集。

相較于以往方法，上述方法效果得到提升，但在降維過程中沒有考慮對學(xué)習(xí)的投影子空間施加正交約束，以減少冗余特征的影響，提高選擇特征的判別性。因此本文通過圖嵌入局部結(jié)構(gòu)學(xué)習(xí)，對數(shù)據(jù)間的相似圖進(jìn)行自適應(yīng)調(diào)節(jié)，并將學(xué)習(xí)到的聚類指示矩陣作正交回歸擬合，最后通過權(quán)重矩陣選擇出判別性特征，該過程統(tǒng)一局部結(jié)構(gòu)學(xué)習(xí)和特征選擇在一個無監(jiān)督框架中同時進(jìn)行。

2 相關(guān)技術(shù)

2.1 圖嵌入局部結(jié)構(gòu)學(xué)習(xí)

根據(jù)局部距離，圖嵌入局部結(jié)構(gòu)學(xué)習(xí)為各個數(shù)據(jù)點自適應(yīng)分配最優(yōu)近鄰，以此來學(xué)習(xí)相似度矩陣，并挖掘潛在幾何結(jié)構(gòu)。

本文采用歐氏距離作為距離度量，默認(rèn)向量為列向量。已知數(shù)據(jù)集X=[x1，x2，···xn]T∈Rn×d，其中n，d分別表示樣本數(shù)和特征維度；S∈Rn×n表示相似度矩陣，其元素sij表示xi，xj之間的相似度，si∈Rn表示xi與全體樣本的相似度；DS表示關(guān)∑于S的度矩陣(Degree Matrix)，其第i個對角元素為j(si j+sji)/2，LS=DS-(S+ST)/2 表 示關(guān)于S的拉普拉斯矩陣(Laplacian Matrix)。

由于S與LS，DS直接相關(guān)，式(1)中的秩約束難以求解。Nie等[15]根據(jù)r ank(LS)=n-c，等價于理想情況下LS具 有前小c個 和為0 的 特征值，記σv(LS)表 示LS前小v個特征值，并由樊畿定理(Ky Fan's Theorem)，得式(2)。

其中，Ic為 單位矩陣，規(guī)格為Rc×c，F(xiàn)表示樣本的低維嵌入，將式(2)跡約束替代式(1)秩約束，以便于求解，最終如式(3)所示，其中α ，β均為正則化參數(shù)。

2.2 特征加權(quán)正交回歸

為了在投影子空間中保留關(guān)于數(shù)據(jù)樣本更多的判別信息[16]并避免平凡解[17]，對最小二乘回歸(Least Square Regression， LSR)模型中的投影矩陣施加正交約束，得到正交回歸模型(Orthogonal Regression)。對于該模型，W∈Rd×c表示投影矩陣，b∈Rc表示偏置向量，Y∈Rc×n表示數(shù)據(jù)樣本標(biāo)簽矩陣，如式(4)所示。

3 JGEFW模型

3.1 模型構(gòu)建

將式(3)與式(5)聯(lián)立，得到本文的目標(biāo)函數(shù)，參見式(6)。式(6)將圖嵌入局部結(jié)構(gòu)學(xué)習(xí)與特征加權(quán)正交回歸結(jié)合起來，獲得一個統(tǒng)一的目標(biāo)函數(shù)。其中：第一、二部分為圖嵌入局部結(jié)構(gòu)學(xué)習(xí)，自適應(yīng)學(xué)習(xí)局部流形結(jié)構(gòu)，即數(shù)據(jù)樣本間的相似度矩陣；第三部分約束學(xué)習(xí)到的數(shù)據(jù)之結(jié)構(gòu)圖的連通分量個數(shù)與自然聚類的簇個數(shù)完全相等，以學(xué)習(xí)到更好的數(shù)據(jù)樣本圖結(jié)構(gòu)；第四部分將局部流形結(jié)構(gòu)學(xué)習(xí)得到的聚類指示矩陣在正交回歸中擬合并獲得權(quán)重矩陣。

進(jìn)行聯(lián)合學(xué)習(xí)是為了保留更多的判別信息并得到表征各個特征重要性的權(quán)重矩陣。整體框架模型參見式(6)。

3.2 模型求解

根據(jù)變量b的極值條件，有b=(1/n)(FT1n-WTΩXT1n) ，其中H=In-(1/n)1n1Tn∈Rn×n為中心化矩陣，故目標(biāo)函數(shù)可簡化為

原問題轉(zhuǎn)換為

其中， d iag(?) 表示以向量? 的元素為對角元素的方陣。由增廣拉格朗日乘子法[18](Augmented Lagrangian Multiplier Method， ALM)，可求解得ω 。

重復(fù)步驟①～③直到收斂。

基于上述算法，交替更新F，S，W，ω，直到收斂。

4 實驗

為驗證本文提出的JGEFW的有效性，根據(jù)文獻(xiàn)[21]將JGEFW與幾種常見的無監(jiān)督特征選擇算法，包括拉普拉斯分?jǐn)?shù)(Laplacian Score， LS)、多簇特征選擇(MCFS)、無監(jiān)督判別特征選擇(Unsupervised Discriminative Feature Selection， UDFS)、雙自表示和流形正則化的魯棒無監(jiān)督特征選擇(Dual Selfrepresentation and Manifold Regularization， DSRMR)以及包含所有特征的基線模型(Baseline)進(jìn)行對比。

根據(jù)文獻(xiàn)[21]選擇在4個公開數(shù)據(jù)集YALE、TOX、ISOLET和COIL上進(jìn)行比較，且設(shè)定選擇特征數(shù)范圍均為{ 20， 30， 40， 50， 60， 70， 80， 90， 100}。對于不同的選擇特征數(shù)均采用30次k均值(k-means)聚類取平均值以減少隨機效應(yīng)的影響，并記錄各評估指標(biāo)的最優(yōu)結(jié)果來表征對所選擇的特征的評估。實驗設(shè)備具體配置為Core(TM) i9-9900K CPU@3.60GHz，RAM 32GB。

4.1 評估指標(biāo)

實驗評估指標(biāo)包括聚類準(zhǔn)確率(Accuracy， ACC)和標(biāo)準(zhǔn)化互信息(Normalized Mutual Information，NMI)。這兩者取值范圍均為[ 0，1]，且數(shù)值越大代表聚類效果越好。

4.2 數(shù)據(jù)集介紹

實驗采用的4個公開數(shù)據(jù)集簡介，如表1所示。

表1 數(shù)據(jù)集簡要信息Table 1 Brief information of datasets

YALE數(shù)據(jù)集屬于人臉圖像數(shù)據(jù)集，其包含15個人共165張的灰度圖像，每個人包含11張不同面部表情和環(huán)境的圖像，包括中心光、左光、右光、快樂、正常、悲傷、困倦、驚訝、戴眼鏡和眨眼[23]。

TOX數(shù)據(jù)集屬于生物數(shù)據(jù)集，共包含4個類別的171個樣本，每個樣本維度為5 748維。

ISOLET數(shù)據(jù)集是從30個測試者每人讀出兩次全部英文字母收集而來，樣本共1 560個，維度為617。

COIL數(shù)據(jù)集包含1 440張圖像，共20類物品，每個物品有72張圖像，其來源于相機以固定間隔5°的角度拍攝得到每類物品的圖像，裁剪大小為32×32像素，故維度為1 024維。

4.3 各算法參數(shù)設(shè)置

4.4 實驗結(jié)果與分析

4.4.1 評估指標(biāo)最優(yōu)結(jié)果

表2～3分別展示幾種無監(jiān)督特征選擇算法在各數(shù)據(jù)集上，經(jīng)參數(shù)搜索后選取最優(yōu)參數(shù)且選取各特征選擇數(shù)情況下的最佳聚類結(jié)果及相應(yīng)的標(biāo)準(zhǔn)差，同時表2～3最后一行為各個算法在全部數(shù)據(jù)集上的平均聚類效果。表中加粗項表示在該數(shù)據(jù)集效果最優(yōu)，下劃線項表示在該數(shù)據(jù)集上效果次優(yōu)，對比算法結(jié)果均由文獻(xiàn)[21]給出。

表2 幾種無監(jiān)督特征選擇算法在各數(shù)據(jù)集聚類準(zhǔn)確率(%)± 標(biāo)準(zhǔn)差(%)比較Table 2 Results on clustering evaluation metric of ACC(%)± std(%) of all compared unsupervised feature selection methods on all datasets

由表2可知，本方法在各數(shù)據(jù)集和平均聚類準(zhǔn)確率上效果均為最優(yōu)，同時在YALE、ISOLET、COIL和平均聚類準(zhǔn)確率與次優(yōu)效果相比均有較大的提升。由表3可知，本方法在YALE上效果為最優(yōu)，且與次優(yōu)效果相比有較大的提升，而在TOX、ISOLET和平均標(biāo)準(zhǔn)化互信息為次優(yōu)，由于Baseline模型對全部特征進(jìn)行利用而不加以選擇，因此對于某些包含噪聲和冗余特征較少的數(shù)據(jù)集而言，該做法有時也能獲得較好的效果，但并無包含降維操作。

表3 幾種無監(jiān)督特征選擇算法在各數(shù)據(jù)集標(biāo)準(zhǔn)化互信息(%)± 標(biāo)準(zhǔn)差(%)比較Table 3 Results on clustering evaluation metric of NMI(%)± std(%) of all compared unsupervised feature selection methods on all datasets

4.4.2 評估指標(biāo)隨各特征選擇數(shù)的變化

圖1～2分別表示在不同聚類指標(biāo)下幾種不同的特征選擇算法在各數(shù)據(jù)集上選擇不同特征數(shù)時的聚類效果。圖中橫坐標(biāo)表示不同的選擇選擇數(shù)，縱坐標(biāo)分別表示以聚類準(zhǔn)確率(ACC，%)和標(biāo)準(zhǔn)化互信息(NMI，%)作為聚類指標(biāo)時的值。由于文獻(xiàn)[21]并無給出對比算法在各選擇特征數(shù)的實際數(shù)值，故該部分?jǐn)?shù)據(jù)是根據(jù)該論文設(shè)置，實際運行代碼獲得的，得到的各對比算法實際最優(yōu)效果允許與表2～3存在差距。

由圖1可知，本方法在YALE上聚類準(zhǔn)確率變動較為波動，與其他對比算法情況相似，且在大多數(shù)選擇特征數(shù)范圍優(yōu)于其他對比算法；在TOX上聚類準(zhǔn)確率大致呈整體上升趨勢，且在大多數(shù)選擇特征數(shù)范圍效果均優(yōu)于LS、MCFS和DSRMR；在ISOLET上隨著選擇特征數(shù)增加，效果大致呈上升趨勢，與大多數(shù)對比算法變化趨勢一致，且在選擇特征數(shù)為 90時聚類準(zhǔn)確率為所有對比算法下的最優(yōu)；在COIL上隨著選擇特征數(shù)增加，聚類準(zhǔn)確率在多數(shù)選擇特征數(shù)范圍均優(yōu)于其他對比算法，且在選擇特征數(shù)為 70時聚類準(zhǔn)確率為所有對比算法下的最優(yōu)。

圖1 各數(shù)據(jù)集幾種算法不同特征選擇數(shù)的聚類準(zhǔn)確率(%)比較Fig.1 Results on clustering evaluation metric of ACC (%) of different numbers of selected features of all compared unsupervised feature selection methods on all datasets

由圖2可知，本方法在YALE上標(biāo)準(zhǔn)化互信息變動較為波動，與其他對比算法情況相似，但在選擇特征數(shù)為30時標(biāo)準(zhǔn)化互信息為所有對比算法下的最優(yōu)，表明JGEFW在選擇特征數(shù)較小時便能選擇出判別性強的信息；在TOX上標(biāo)準(zhǔn)化互信息大致呈上升趨勢，與其他對比算法趨勢完全不同，且當(dāng)選擇特征數(shù)在大于70的范圍內(nèi)，標(biāo)準(zhǔn)化互信息均為所有對比算法下的最優(yōu)；在ISOLET上隨著選擇特征數(shù)增加，標(biāo)準(zhǔn)化互信息大致呈提升趨勢，與其他絕大多數(shù)對比算法變化趨勢相同，且在選擇特征數(shù)為100時標(biāo)準(zhǔn)化互信息優(yōu)于Baseline的效果；在COIL上隨著選擇特征數(shù)增加，標(biāo)準(zhǔn)化互信息在Baseline算法上下波動，表明本算法能有效學(xué)習(xí)到數(shù)據(jù)間的潛在幾何結(jié)構(gòu)，并對判別力強的特征加以選擇。

圖2 各數(shù)據(jù)集幾種算法不同特征選擇數(shù)的標(biāo)準(zhǔn)化互信息(%)比較Fig.2 Results on clustering evaluation metric of NMI (%) of different numbers of selected features of all compared unsupervised feature selection methods on all datasets

4.4.3 參數(shù)敏感性分析

為探究算法的性能，進(jìn)行參數(shù)敏感性分析實驗(Parameter Sensitivity)，以考慮各參數(shù)變動對模型的影響。此處以COIL數(shù)據(jù)集為例，在最優(yōu)聚類準(zhǔn)確率效果中先固定 β=10， 變化γ，觀察算法的聚類準(zhǔn)確率變化，再固定γ =0.1， 變化 β，觀察算法的聚類準(zhǔn)確率變化；在最優(yōu)標(biāo)準(zhǔn)化互信息效果中先固定 β=103，變化γ ，觀察算法的標(biāo)準(zhǔn)化互信息變化，再固定γ =105，變化 β，觀察算法的標(biāo)準(zhǔn)化互信息變化。

由圖3可知，JGEFW的聚類準(zhǔn)確率隨著選擇特征數(shù)、 β 和γ 的改變略有波動，而JGEFW的標(biāo)準(zhǔn)化互信息則隨著選擇特征數(shù)、 β 和γ 的改變總體上較為平穩(wěn)，具有一定的魯棒性。

圖3 本方法在COIL的參數(shù)敏感性分析實驗結(jié)果Fig.3 Parameters sensitivity analysis about clustering evaluation metric of the proposed method on COIL dataset

4.4.4 收斂性實驗證明

此處以COIL數(shù)據(jù)集為例，其他數(shù)據(jù)集上的收斂情況與此相似，目標(biāo)函數(shù)值的收斂曲線如圖4所示。由圖4可知，隨著迭代次數(shù)逐漸增加，目標(biāo)函數(shù)值不斷減少，最后趨于一個穩(wěn)定值，表明該算法是收斂的。

圖4 本方法在COIL數(shù)據(jù)集上的收斂結(jié)果示意Fig.4 Result of convergence experiments of the proposed method on COIL dataset

5 結(jié)束語

本文給出了一種改進(jìn)的無監(jiān)督特征選擇算法，稱為JGEFW。通過局部結(jié)構(gòu)學(xué)習(xí)自適應(yīng)地調(diào)節(jié)數(shù)據(jù)的相似圖，使其滿足自然聚類的簇的要求，提高圖構(gòu)造的準(zhǔn)確度。并通過加權(quán)特征回歸的方法，使圖構(gòu)造的聚類指示矩陣在正交回歸中擬合以學(xué)習(xí)權(quán)重矩陣，并挑選出權(quán)重值大的判別特征和非冗余特征形成特征子集。實驗結(jié)果表明，JGEFW的性能在平均情況下優(yōu)于其他對比的特征選擇方法。未來工作將嘗試提高模型的聚類性能和迭代速度。