基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量非監(jiān)督特征選擇方法

林筠超，萬 源

（武漢理工大學理學院，武漢 430070）

（*通信作者電子郵箱wanyuan@whut.edu.cn）

0 引言

隨著數(shù)據(jù)采集技術(shù)的飛速發(fā)展，在計算機視覺、數(shù)據(jù)挖掘、生物醫(yī)學等許多鄰域中產(chǎn)生了大量未標記的高維數(shù)據(jù)［1］。高維數(shù)據(jù)通常包含很多噪聲，處理分析過程中會帶來高昂的計算成本和維數(shù)災難，因此非監(jiān)督特征選擇成為高維數(shù)據(jù)降維中重要且具有挑戰(zhàn)的問題［2-3］。

由于沒有標簽信息作為參考，相較于有監(jiān)督方法，非監(jiān)督特征選擇方法更具有挑戰(zhàn)性。高維度空間的特征選擇降維方法的相關(guān)研究表明，應(yīng)該通過選擇出的特征來保持原始數(shù)據(jù)的重要信息［4-5］，這些信息包括數(shù)據(jù)的全局結(jié)構(gòu)和局部流形結(jié)構(gòu)。拉普拉斯分數(shù)法（Laplacian Score，LapScore）［6］通過圖拉普拉斯算法來選擇特征，使數(shù)據(jù)的局部流形結(jié)構(gòu)得以保留。受流形學習和l1正則化子集選擇模型的啟發(fā)，UDFS（Unsupervised Discriminative Feature Selection）［7］將判別分析和l2，1范數(shù)最小化合并到非監(jiān)督特征選擇的聯(lián)合框架之中。文獻［8］中提出的多聚類特征選擇方法（Multi-Cluster Feature Selection，MCFS），通過譜分析和l1范數(shù)正則化來保留多簇結(jié)構(gòu)以選擇特征，而非獨立地評估每個特征的分數(shù)。非負判別特征選擇（Nonnegative Discriminative Feature Selection，NDFS）方法［9］將判別信息和特征間的相互性合并于一個聯(lián)合框架中，充分利用了魯棒非負矩陣分解、局部學習和魯棒特征學習的優(yōu)勢。JELSR（Joint Embedding Learning and Sparse Regression）［10］則考慮聯(lián)合嵌入學習和稀疏回歸，而非用圖拉普拉斯來表征高維數(shù)據(jù)結(jié)構(gòu)。結(jié)構(gòu)化最優(yōu)圖特征選擇（Structured Optimal Graph Feature Selection，SOGFS）［11］則提出了一種局部結(jié)構(gòu)學習的同時進行特征選擇的方法。這些特征選擇方法都能很好地解決通過全局結(jié)構(gòu)構(gòu)造相似矩陣所帶來的弊端。依賴指導的非監(jiān)督特征選擇（Dependence Guided Unsupervised Feature Selection，DGUFS）方法［12］提出了兩個依賴關(guān)系指導項，一項增加了所需聚類標簽對原始數(shù)據(jù)的依賴性，而另一項使所選特征對聚類標簽的依賴性最大化，以指導特征選擇過程，特別地，提出了一種基于l2，0范數(shù)相等約束的無投影特征選擇模型。自適應(yīng)近鄰特征選擇（Adaptive Neighbors Feature Selection，ANFS）方法［13］通過自適應(yīng)重構(gòu)圖來描述局部結(jié)構(gòu)，并通過在相應(yīng)的拉普拉斯矩陣上施加秩約束來同時考慮多簇結(jié)構(gòu)。自加權(quán)多視角聚類（Self-weighted Multiview Clustering，SwMC）方法［14］在學習視角權(quán)重的同時實現(xiàn)對多視角數(shù)據(jù)的聚類，并且提出權(quán)重可以通過引入一個超參數(shù)來學習。

然而，由于沒有標簽信息作為參考，上述非監(jiān)督特征選擇方法都是使用某一種度量方法來表示數(shù)據(jù)點之間的相似度?？紤]到各方法構(gòu)造相似矩陣的標準并不統(tǒng)一，如何從多種度量標準中總結(jié)出一種統(tǒng)一度量標準是值得研究的；另外，通過常規(guī)的K最近鄰（K-Nearest Neighbors，K-NN）法分配得到的相似矩陣，難以確保其具有理想的連通分量數(shù)［11］。

針對上述兩個問題，本文將不同的度量函數(shù)自適應(yīng)地融合為統(tǒng)一的相似性度量，并將圖結(jié)構(gòu)優(yōu)化嵌入非監(jiān)督特征選擇之中，提出了一種基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量非監(jiān)督特征選擇（Self-Adaptive Multi-measure unsupervised feature selection with Structured Graph Optimization，SAM-SGO）方法，為了能根據(jù)統(tǒng)一的相似度得到相關(guān)子空間，本文將基于圖的降維問題合并于目標函數(shù)之中，并引入稀疏性l2，0正則化約束以避免噪聲樣本和特征帶來的影響。與已有的算法相比，本文方法能更好地保留圖的結(jié)構(gòu)信息，并使獲得的稀疏投影能高效地進行特征選擇；通過對多種度量標準進行自適應(yīng)融合，有效地避免了單一度量標準對相似矩陣的構(gòu)造所帶來的偏差。

1 相關(guān)工作

1.1 局部保留投影

文獻［15］中提出的局部保留投影（Locality Preserving Projections，LPP）法被廣泛應(yīng)用在降維方法USSL（Unified Sparse Subspace Learning）［16］、FSSL（joint Feature Selection and Subspace Learning）［17］、FSASL（unsupervised Feature Selection with Adaptive Structure Learning）［18］等算法中。

對于給定數(shù)據(jù)集X={xi|xi∈Rd×1；i=1，2，…，n}，相關(guān)的數(shù)據(jù)矩陣表示為X=[x1，x2，…，xn]，xi∈Rd，其中d為數(shù)據(jù)維數(shù)，n為數(shù)據(jù)的樣本數(shù)。構(gòu)造一個無向圖G={X，S}，頂點由數(shù)據(jù)集X構(gòu)成，邊由相似矩陣S∈Rn×n構(gòu)成。圖G 的每條邊，表示近鄰點之間相互連接。對于無向圖G，其極大連通子圖稱為G的連通分量（connected component）［19］。令Sij為第i個數(shù)據(jù)點與第j個數(shù)據(jù)點之間的相似度，其值與頂點間距離成反比。對角矩陣D定義為，?i，拉普拉斯矩陣L定義為L=D-

一個特征的重要性取決于其表達圖結(jié)構(gòu)信息的能力［15］。為簡化說明，假設(shè)向量y=[y1，y2，…，yn]T為圖G 頂點的低維表示，即yi是數(shù)據(jù)點xi的低維表示。為在各頂點之間找到一組低維向量，以最好地表征頂點對之間的相似關(guān)系，可以通過最小化下列目標函數(shù)來獲得較優(yōu)的特征：

為實現(xiàn)最小化目標函數(shù)，當樣本xi和xj之間相似性越大，對應(yīng)地yi和yj之間距離應(yīng)該越小，反之亦然。進一步，為構(gòu)造拉普拉斯特征映射的線性逼近，假設(shè)用于表示數(shù)據(jù)的低維向量yi通過線性映射yi=WTxi表示，W∈Rd×m是投影矩陣，d和m分別為數(shù)據(jù)投影前后的維數(shù)。則式（1）目標函數(shù)變?yōu)椋?/p>

為避免目標函數(shù)的平凡解，通常增加約束WTW=I［21］。

1.2 l2，0范數(shù)稀疏約束

在實際應(yīng)用中，為了讓獲得的投影矩陣W保持行稀疏，Cai 等［22］提出，將稀疏l2，0誘導約束引入圖嵌入問題（2），使稀疏特征選擇問題有效地嵌入于圖降維問題中，優(yōu)化問題（2）改進為：

增加的約束||W||2，0=r使得正交投影W僅具有r個非零行，且這r個非零行即為所選特征。求解時，優(yōu)化問題（3）等價于其對偶問題（4）：

其中：r是預設(shè)常數(shù)，β是正則化參數(shù)。顯然，當β足夠大時，問題（4）等價于問題（3）。

2 SAM-SGO算法

非監(jiān)督特征選擇方法通常分為兩個獨立的步驟，首先通過局部結(jié)構(gòu)構(gòu)造相似矩陣，然后通過稀疏正則化選擇較優(yōu)特征，如USSL［16］、FSSL［17］、DGUFS［12］等，這些方法所構(gòu)造的相似矩陣是獨立于特征選擇的，即從原始數(shù)據(jù)中得出的相似矩陣在之后的步驟中保持不變，但實際數(shù)據(jù)必然包含噪聲特征，從而導致相似矩陣不可靠。針對這個問題，F(xiàn)SASL 方法［18］提出了一種自適應(yīng)結(jié)構(gòu)學習方法，通過迭代優(yōu)化思想反復構(gòu)造相似矩陣，避免了固定的相似矩陣對特征選擇的影響。

然而在構(gòu)造相似矩陣的過程中，這些方法所采用的度量標準僅限于某一種，而忽略了數(shù)據(jù)點之間的相似性程度，且通過常規(guī)的K近鄰法得到的相似矩陣，難以確保其具有理想的連通分量數(shù)［14］。本文提出一種基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量融合方法，將多種度量函數(shù)自適應(yīng)地融合為統(tǒng)一的相似性度量，解決了單一方法對譜圖的構(gòu)建所帶來的偏差，并增加拉普拉斯矩陣秩約束，以保證相似矩陣的連通分量數(shù)是理想的。

2.1 自適應(yīng)多度量融合

在機器學習中，對高維數(shù)據(jù)進行降維的主要目的是希望找到一個合適的低維空間。而尋找合適的空間，實質(zhì)上就是在尋找一個合適的距離度量［23］。令ft為第t個給定的度量函數(shù)，對于數(shù)據(jù)矩陣X，ft(X) ∈Rn×n表示為基于度量函數(shù)ft所構(gòu)造的相似矩陣。為評價樣本點之間的相似性，根據(jù)數(shù)據(jù)的特性的不同，LapScore、MCFS 選擇高斯核函數(shù)度量［8］，DGUFS 使用歐氏加權(quán)函數(shù)［12］，SOGFS 使用的是基于概率鄰域的相似矩陣度量法［24］，LMNN（Large Margin Nearest Neighbor）算法使用的是夾角余弦法［25］等。

然而，上述方法所采用的距離度量都是固定且單一的，沒有可調(diào)節(jié)參數(shù)，難以通過對樣本數(shù)據(jù)的學習來加以改善。因此，針對這個問題，本文考慮用多種度量自適應(yīng)融合成的統(tǒng)一度量方法，相較于上述的單一度量方法，本文所構(gòu)造的相似矩陣能更好地表達數(shù)據(jù)之間的聯(lián)系。為了將多種度量方法進行統(tǒng)一，本文構(gòu)造下列目標函數(shù)：

其中I=(1，1，…，1)T∈Rn×1。為有效融合所有選定的度量，將自適應(yīng)權(quán)重ht分配給每項，以便對其重新加權(quán)。式（5）重新寫為：

在式（6）中，自適應(yīng)權(quán)重ht通過ht迭代更新。其優(yōu)勢在于，對于相似矩陣S與各度量標準計算得到的相似矩陣ft(X)之差，差額較大的項自動分配較小的權(quán)重ht，同樣地，較大的權(quán)重ht將自適應(yīng)地分配給差額較小的項。因此，對于任意給定數(shù)據(jù)，本方法能自適應(yīng)地將權(quán)重分配給各度量，從而減輕了單一度量標準對實驗所帶來的偏差。

2.2 結(jié)構(gòu)最優(yōu)圖

理想情況下，在將數(shù)據(jù)劃分為c個簇的聚類任務(wù)中，相似矩陣S應(yīng)含有c個連通分量，然而在多數(shù)情況下，通過局部保留投影方法LPP 所獲得的相似矩陣S，其具有的連通分量數(shù)不能達到理想情況［11］，很容易出現(xiàn)所構(gòu)成的無向圖僅有一個連通分量的情況［24］，這表明得到的相似矩陣不夠優(yōu)秀。因此，需要對該圖的結(jié)構(gòu)進行進一步優(yōu)化，使得其連通分量數(shù)滿足要求。

假設(shè)相似矩陣S非負，首先給出關(guān)于拉普拉斯矩陣L所滿足的定理［20］：

定理對于拉普拉斯矩陣L，特征值為0的重根數(shù)為c（即矩陣L的秩為n-c），等價于相似矩陣S包含c個連通分量。

該定理表明，若拉普拉斯矩陣L滿足rank(L)=n-c，則原始數(shù)據(jù)所構(gòu)成的相似矩陣S可被劃分為c個簇，從而能夠得到具有最優(yōu)結(jié)構(gòu)的無向圖G。因此，通過增加對于拉普拉斯矩陣L的秩約束，可使得相似矩陣S能包含準確個數(shù)的連通分量，使得無向圖G的結(jié)構(gòu)信息更為準確。

綜上所述，通過融合了自適應(yīng)多度量思想，并在l2，0范數(shù)稀疏約束的圖嵌入非監(jiān)督特征選擇中增加了優(yōu)化圖結(jié)構(gòu)的約束項rank(L)=n-c，本文方法SAM-SGO 所得到的目標函數(shù)為：

3 算法求解

目標函數(shù)（7）中包含l2，0范數(shù)正則化、秩約束以及3 個未知變量，同時優(yōu)化求解這幾個變量較為困難，本文引入交替迭代更新的思想，在優(yōu)化某個變量時固定其他所有變量，反復對變量進行迭代更新直至收斂，最終得到目標函數(shù)的最優(yōu)解。

對于問題（7），考慮到拉普拉斯矩陣L=及其秩rank(L)=n-c的值都取決于相似矩陣S。令σi(L)表示L的第i個最小特征值，由于L為半正定矩陣，其每個特征值均非負，即σi(L) ≥0，進而約束rank(L)=n-c等價于根據(jù)Ky Fan’s定理［26］有：

通過定理將原式中拉普拉斯矩陣L的秩約束轉(zhuǎn)化為跡，于是式（7）可優(yōu)化為：

顯然，在式（9）中，當λ足夠大，項Tr(FTLF)將趨于0。在每次迭代過程中，當連通分量比c小，可以相應(yīng)地增加λ，反之亦然，直至趨于收斂。通過此方法，將矩陣秩的約束轉(zhuǎn)變?yōu)檑E，使得問題變得更易解決。

3.1 固定S和F，優(yōu)化投影矩陣W

當S和F固定時，僅保留含有W的項，于是目標函數(shù)（9）式可以變換為：

由于l2，0范數(shù)的特殊性，不易對式（10）直接求解。文獻［22］中提出，問題的求解等價于問題的求解，因此在該式中用代替||W||2，1，同時省略與W最優(yōu)取值無關(guān)的常數(shù)項r，將式（10）變形為：

對于式（11），其拉格朗日函數(shù)表示為：

其中，斜對角矩陣A∈Rm×m由拉格朗日乘子構(gòu)成。通過求解式（12），其關(guān)于W的卡羅需-庫恩-塔克（Karush-Kuhn-Tucker，KKT）條件為：

其中Ω=diag(Λ1，Λ2，…，Λd)，Λi=+ε)-1/2/2，增加擾動項ε以防止行稀疏投影矩陣W出現(xiàn)平凡解，ε通常取極小值。因此，問題（12）的求解等價于問題（14）：進而通過求解矩陣XTLX+βΩ/2α的前m個最小特征值所對應(yīng)特征向量，即可得到最優(yōu)投影矩陣W。

3.2 固定S和W，優(yōu)化F

當S和W固定時，變量F僅存在于目標函數(shù)的最后一項，故式（9）變?yōu)椋?/p>

其中，最優(yōu)解所對應(yīng)的F即為拉普拉斯矩陣L的前c個最小特征值所對應(yīng)的特征向量組成的矩陣。

3.3 固定W和F，優(yōu)化S

W和F固定后，僅保留與變量S和ht有關(guān)的項后，問題（9）變換為：

進行恒等式變換得到：

將式（17）拆成n項，其第k項的拉格朗日方程為：

其中μ為等式約束乘子，θk≥0(k=1，2，…，n)為不等式約束乘子。對于?h，關(guān)于式（18）的KKT條件如式（19）、（20）所示：

由此分別得到了3個變量W、S、F的優(yōu)化更新表達式，其具體的算法流程總結(jié)如下：

輸入 原始數(shù)據(jù)X=[x1，x2，…，xn]，xi∈Rd×1；聚類數(shù)c；目標維數(shù)m；參數(shù)α、β；r個選定的度量函數(shù)ft。

輸出 投影矩陣W∈Rr×d。

初始化 隨機生成ht，計算初始拉普拉斯矩陣L，并通過式（14）和（15）計算初始W和F

重復迭代：

對于k∈1到n

通過式（22）更新skh

通過ht=更新ht

通過式（15）更新F

根據(jù)式（14），通過求解矩陣XTLX+βΩ/2α的前m個最小特征值，獲得所對應(yīng)的特征向量，更新W直至收斂

計算所有的‖wi‖2并排序，選取前m個特征代入K-means 聚類得到聚類結(jié)果并計算準確率。

4 實驗

本文設(shè)計了多項實驗來測試本文所提出的基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量非監(jiān)督特征選擇（SAM-SGO）方法的性能。

4.1 實驗數(shù)據(jù)集與實驗設(shè)置

本文使用了6組公開圖像數(shù)據(jù)集，包括3組人臉圖像數(shù)據(jù)集MSRA25［27］、ORL［28］、Yale［29］，1 組實物數(shù)據(jù)集COIL20［30］，1組生物數(shù)據(jù)集Lung［31］和1組手寫圖像數(shù)據(jù)集USPS［32］。表1匯總了這些數(shù)據(jù)集的具體信息，并在圖1中展示了3個不同領(lǐng)域數(shù)據(jù)COIL20、Yale、USPS的部分圖像。

圖1 部分樣本圖像Fig.1 Some sample images

表1 樣本數(shù)據(jù)集信息Tab.1 Sample dataset information

為驗證SAM-SGO 方法的有效性，將本文方法與下列幾種常見的非監(jiān)督特征選擇算法進行了比較分析，包括：

1）拉普拉斯分數(shù)（LapScore）方法［6］：通過計算特征對于保持局部流形結(jié)構(gòu)能力，并根據(jù)得分大小選擇特征。

2）多集群特征選擇（MCFS）方法［8］：該方法使用了圖拉普拉斯算子的多個特征向量來捕獲數(shù)據(jù)的多簇結(jié)構(gòu)，通過譜分析和l1范數(shù)正則化來保留多簇結(jié)構(gòu)以選擇特征，而非獨立地評估每個特征的分數(shù)，在聚類和分類上都能取得很好的性能。

3）基于局部學習聚類的特征選擇和內(nèi)核學習（LLCFS）方法［33］：該方法旨在通過基于局部學習聚類（Local Learningbased Clustering，LLC）方法的框架中的特征選擇來獲得合適的數(shù)據(jù)表示，在處理位于流形上的高維數(shù)據(jù)時要優(yōu)于基于全局學習的方法。

4）依賴指導的非監(jiān)督特征選擇（DGUFS）方法［12］：提出了基于l2，0范數(shù)相等約束的無投影特征選擇模型，以聯(lián)合方式選擇特征和分區(qū)數(shù)據(jù)。

5）基于圖結(jié)構(gòu)優(yōu)化的非監(jiān)督特征選擇（SOGFS）方法［11］：該方法同時執(zhí)行特征選擇和局部結(jié)構(gòu)學習，并通過圖結(jié)構(gòu)約束相似矩陣，使該方法所選擇的特征能更好地表達數(shù)據(jù)的結(jié)構(gòu)信息。

6）使用全部特征并進行K-means 聚類的基準線作為對照組（Baseline）。

為了算法比較的公平性，本文所采用的度量方法部分源于上述對比方法，包括：LapScore、MCFS 所使用的高斯核函數(shù)度量法［8］，SOGFS 所使用的基于概率鄰域的相似矩陣度量法［24］，LMNN 算法所使用的夾角余弦法［25］，以及在模糊數(shù)學領(lǐng)域中常見的絕對值倒數(shù)法［34］。

在實驗參數(shù)上，MCFS，LapScore 和SOGFS 中的近鄰個數(shù)k均設(shè)置為5，DGUFS 所使用的參數(shù)α和β以及SOGFS 中參數(shù)γ采用層次網(wǎng)格搜索法來確定?？紤]到聚類性能隨初始聚類中心的選擇而變化，為減輕聚類方法帶來的隨機效應(yīng)，對于所選擇的特征，本文從不同的起點重復10 次K-means 聚類實驗并只取最優(yōu)結(jié)果。本文采用聚類準確度（Accuracy，ACC）作為評價指標來評估所選特征，定義為：

其中：pi和qi分別是數(shù)據(jù)提供的標簽和得到的標簽；δ(x=y)為條件判斷函數(shù)，若x=y則函數(shù)值為1，反之則為0；map(qi)是排列映射函數(shù)，可通過Kuhn-Munkres 算法得到，它能將得到的集群標簽qi映射為數(shù)據(jù)集中的等效標簽。

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

本文實驗環(huán)境為Inter Core i7-6500U，CPU@2.50 GHz，12 GB 內(nèi)存，Windows 10 64 位操作系統(tǒng)，編程軟件為Matlab 2016a。對所提出的SAM-SGO算法進行了3組實驗：在固定所選特征數(shù)時各算法之間的性能對比；對于不同數(shù)據(jù)集，不同算法的聚類準確率隨所選特征數(shù)增加的變化曲線；各實驗參數(shù)對于本方法的靈敏度分析。

4.2.1 對于不同所選特征數(shù)，不同算法在各數(shù)據(jù)集下的聚類結(jié)果

對于各非監(jiān)督特征選擇方法，本文使用了上述實驗數(shù)據(jù)及相應(yīng)設(shè)置，采用十折交叉驗證法對特征子集進行評價，在表2 中展示了各特征選擇方法在選擇前90 個特征的聚類結(jié)果（其中對最優(yōu)方法用加粗表示，次優(yōu)方法用下劃線表示）?？梢钥闯觯疚奶岢龅腟AM-SGO 非監(jiān)督特征選擇方法在不同的數(shù)據(jù)集上普遍優(yōu)于其他5 種方法，具體而言：相較于次優(yōu)的方法，本文方法在人臉圖像數(shù)據(jù)集ORL、Yale、MSRA25 上，聚類準確度（ACC）分別提高了6.8 個百分點，4.0 個百分點和4.3個百分點；在實物圖像數(shù)據(jù)集COIL20 和手寫圖像數(shù)據(jù)集USPS 中分別提高了2.5 個百分點和3.4 個百分點；在生物數(shù)據(jù)集Lung中提高了0.7個百分點。

表2 各算法在選取前90個特征的聚類準確度（ACC）平均值和標準偏差 單位：%Tab.2 Average clustering accuracy（ACC）and standard deviation of each algorithm with selecting top 90 features unit：%

通過對比可以發(fā)現(xiàn)，本文所提出的方法在不同的數(shù)據(jù)集上的性能都較高，特別是對于人臉圖像數(shù)據(jù)集，其聚類正確率不僅優(yōu)于使用全部特征的聚類方案，更是顯著高于其他方法所得到的結(jié)果。由此可見，相較于其他特征選擇方法，本文所提出的基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量非監(jiān)督特征選擇（SAM-SGO）方法能有效地篩選出較為精煉的數(shù)據(jù)特征，從而提高聚類的正確率。

4.2.2 各算法聚類性能對比

為直觀地觀察不同方法之間的性能差異，本文分別在6組數(shù)據(jù)中進行實驗，并繪制出在特征數(shù)為10、20、30、…、110，不同算法所選特征的K-means 聚類準確度（ACC），如圖2所示。

通過分析，可以得出以下結(jié)論：

1）隨著特征數(shù)的增加，本文所述的方法的聚類準確度通常呈現(xiàn)先上升后穩(wěn)定的趨勢。這是由于現(xiàn)實數(shù)據(jù)中包含許多冗余特征，值得挖掘的信息通常包含在少數(shù)特征中，若所選特征過多，導致噪聲特征的增加，勢必影響聚類結(jié)果。這種趨勢間接驗證了特征選擇方法的有效性。

2）在大多數(shù)情況下，由于數(shù)據(jù)中經(jīng)常包含許多噪聲數(shù)據(jù)或冗余數(shù)據(jù)，相較于直接使用所有特征進行K-means 聚類，僅使用特征選擇方法選定的少數(shù)特征進行聚類，其結(jié)果會更好。特別是本文所提出的SAM-SGO 方法，在大多數(shù)數(shù)據(jù)中都有較好的改善。說明了特征選擇方法能有效地提高數(shù)據(jù)的質(zhì)量，獲得精煉后的數(shù)據(jù)，從而提高聚類的準確率。

3）由圖2（e）可以看出，并非在所有的數(shù)據(jù)集中，使用特征選擇方法的聚類正確率都能比基線方法高，這是由于原始數(shù)據(jù)本身的特性不同，這也說明了特征選擇方法仍有進步的空間。

圖2 六組數(shù)據(jù)在不同所選特征數(shù)下各算法的聚類準確度Fig.2 Clustering accuracy of each algorithm for 6 groups of data under different feature numbers

4.2.3 自適應(yīng)權(quán)重ht的收斂性

本文所采用的四種度量方法，包括：高斯核函數(shù)度量法、基于概率鄰域的相似矩陣度量法、夾角余弦法，以及絕對值倒數(shù)法。本文給出了對于COIL20數(shù)據(jù)集和Yale數(shù)據(jù)集，自適應(yīng)權(quán)重ht隨迭代次數(shù)增加的曲線，如圖3所示。

圖3 自適應(yīng)權(quán)重ht的收斂曲線Fig.3 Convergence curve of adaptive weight ht

可以看到，本方法中的自適應(yīng)度量權(quán)重ht收斂速度是非?？斓摹Ｔ谝陨蟽蓚€示例中，經(jīng)過若干次迭代之后均趨近收斂于一個定值。從圖3（a）可以看出在數(shù)據(jù)集COIL20中，絕對值倒數(shù)函數(shù)對于該數(shù)據(jù)的適應(yīng)程度遠高于其他方法，而夾角余弦法的適應(yīng)程度最低。而對于圖3（b）中數(shù)據(jù)集Yale，高斯核函數(shù)度量法的適應(yīng)度最高，其次是基于概率鄰域的相似矩陣度量法，反而數(shù)據(jù)集COIL20中表現(xiàn)良好的絕對值倒數(shù)法權(quán)重較低。由此可以看出在不同數(shù)據(jù)集下，SAM-SGO 方法對于度量方法的選擇是有所偏好的。

4.2.4 統(tǒng)一相似矩陣的稀疏性

為了對比本文SAM-SGO 方法處理相似矩陣能力，本文給出了本文方法在處理COIL20 數(shù)據(jù)集前后，相似矩陣S的稀疏程度對比，如圖4所示，其中，橫坐標表示相似矩陣S的第i列，縱坐標表示相似矩陣S的第j行，右側(cè)顏色欄（colorbar）表示顏色范圍所對應(yīng)的數(shù)值范圍。

圖4 相似矩陣S稀疏程度Fig.4 Sparsity of similarity matrix S

可以看出迭代收斂后的相似矩陣，除主對角線以外的元素，絕大多數(shù)元素均為0或趨近于0。相較于迭代開始前的相似矩陣，SAM-SGO 方法迭代收斂后的矩陣更為稀疏，其結(jié)構(gòu)也更加清晰，驗證了采用本方法構(gòu)造的統(tǒng)一相似矩陣是足夠稀疏的。

4.2.5 靈敏度分析

本文研究了SAM-SGO 方法中，參數(shù)對實驗結(jié)果影響。在本方法中，不確定參數(shù)包括m、α、β三項。

對于參數(shù)m（數(shù)據(jù)投影后的維數(shù)），其值會稍微影響結(jié)果，根據(jù)實驗經(jīng)驗，通常將其設(shè)置在d/3～d/2。

而對于參數(shù)α、β，其值對聚類結(jié)果的影響不大。對于數(shù)據(jù)集COIL20，本文給出了參數(shù)α、β的值對聚類準確率ACC結(jié)果的靈敏度分析，包括固定β=0.7，變化α和特征數(shù)，以及固定α=3，變化β和特征數(shù)兩組對比實驗，如圖5所示。

圖5 SAM-SGO方法在COIL20數(shù)據(jù)集上的靈敏度分析Fig.5 Sensitivity analysis for SAM-SGO method on dataset COIL20

可以發(fā)現(xiàn)，隨著所選特征數(shù)的增加，聚類準確度有著上升的趨勢；而固定特征數(shù)個數(shù)時，聚類準確度不會隨著參數(shù)β的改變而出現(xiàn)太大的變化。整體而言，參數(shù)的小幅度調(diào)整對于結(jié)果的影響不會很大，這說明了SAM-SGO 方法在某種程度上對參數(shù)α、β具有魯棒性。盡管如此，本文仍建議在實際應(yīng)用中使用分層網(wǎng)格搜索來尋找最優(yōu)的參數(shù)。

5 結(jié)語

為統(tǒng)一不同度量的相似矩陣，使得到的相似矩陣具有理想的連通分量數(shù)，本文提出了一種基于圖結(jié)構(gòu)優(yōu)化的自適應(yīng)多度量非監(jiān)督特征選擇方法（SAM-SGO），將自適應(yīng)度量嵌入基于圖的降維問題，并對圖結(jié)構(gòu)進行優(yōu)化?？紤]到噪聲數(shù)據(jù)帶來的影響而引入了l2，0范數(shù)正則化。為解決所提出的問題，給出了一種有效的迭代優(yōu)化算法，在不同領(lǐng)域的多個基準數(shù)據(jù)集上進行的綜合實驗，驗證了本文方法的有效性。

盡管SAM-SGO 方法通過尋求線性變換來進行特征選擇，能夠表現(xiàn)出非常好的性能，但相較于圖像數(shù)據(jù)集，本算法在非圖像數(shù)據(jù)集上的表現(xiàn)不夠優(yōu)秀，可以考慮使用核映射的非線性模型來擴展所提出的方法，可能會提高本算法的普適性；另外，可以嘗試將自適應(yīng)多度量思想方法應(yīng)用到有監(jiān)督和半監(jiān)督的分類領(lǐng)域之中。