自適應嵌入的半監(jiān)督多視角特征降維方法

孫圣姿，萬 源，曾 成

(武漢理工大學 理學院，武漢 430070)(*通信作者電子郵箱wanyuan@whut.edu.cn)

0 引言

當數(shù)據(jù)從不同數(shù)據(jù)源獲得或者由不同的特征集來共同表示，這類數(shù)據(jù)稱為多視角數(shù)據(jù)。比如圖像可以由灰度值、尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)特征[1]、方向梯度直方圖(Histogram of Oriented Gradients, HOG)特征[2]等多種特征來表示；網(wǎng)頁可以由網(wǎng)站地址、網(wǎng)站名稱等多種特征表示。多視角數(shù)據(jù)的各個視角之間通常能夠提供互補和相關的信息，而傳統(tǒng)方法并不考慮這一點，因此如何有效提取不同視角的特征且保留各個視角之間的相關性來實現(xiàn)特征降維成為機器學習和數(shù)據(jù)挖掘近年來的研究熱點?；诮Y構信息保持的特征提取方法通過最大程度上保持原始數(shù)據(jù)的結構，包括全局結構[3-4]和局部流形結構[5-6]來實現(xiàn)特征降維。這些結構可以通過圖約束模型來表示，如樣本成對相似圖[4]、K最近鄰(K-Nearest Neighbors,K-NN)圖[7]、局部判別模型[8]、局部線性嵌入(Locally Linear Embedding, LLE)[3]等。在近年來的研究進展中，嵌入矩陣被廣泛引入到各類特征提取方法中[9-10]，這些方法通過重構各數(shù)據(jù)點與全局信息之間的關系，來保留原始的結構。但是將這些方法應用于多視角特征提取時，它們大多只是單獨對單視角的特征進行選擇，然后將各視角直接相連，導致了各個視角間特征的相關性和部分原始信息的缺失。

在實際應用中，收集到的數(shù)據(jù)存在少量標簽數(shù)據(jù)和大量無標簽數(shù)據(jù)是非常常見的。對數(shù)據(jù)加注標簽信息會耗費大量時間精力，因此半監(jiān)督特征降維方法通過同時使用有標簽和無標簽兩類數(shù)據(jù)，來保留原始的結構信息。近年來半監(jiān)督特征降維已取得一些研究成果。半監(jiān)督判別分析(Semi-supervised Discriminant Analysis, SDA)方法[11]，使用帶標簽的數(shù)據(jù)點來最大化不同類別之間的可分離性，通過標記數(shù)據(jù)點來估計數(shù)據(jù)的固有幾何結構。Xu等[12]通過最大化不同類別之間的分類邊界來選擇特征，利用幾何概率分布來生成標記的和未標記的數(shù)據(jù)，并將其轉化成凸凹優(yōu)化問題。Coelho等[13]提出了一種基于單變量相關性度量的半監(jiān)督特征選擇方法，在Pareto最優(yōu)集合中決策最優(yōu)解的過程中，嘗試最大化每個特征的相關性指標，確定最小的相關特征集，同時確定最優(yōu)模型。

然而這些方法直接應用于多視角數(shù)據(jù)進行特征降維效果并不理想。多視角問題中，針對全局結構的保持項，非監(jiān)督自適應性特征選擇(unsupervised Feature Selection with Adaptive Structure Learning, FSASL)方法[14]提出了一種多視角下自適應性的全局結構保持方法，通過稀疏重構來保留數(shù)據(jù)的原始結構。將各個視角的數(shù)據(jù)信息映射到一個最優(yōu)稀疏組合權重矩陣。同時，一些改進的半監(jiān)督模式下的多視角學習方法被相繼提出。半監(jiān)督多視角特征選擇(Semi-supervised Multi-view Feature Selection, Semi-MFS)方法[15]通過將多個數(shù)據(jù)點分解成多個有意義且不相關的組別來生成不同的視圖，每個組別代表一個視角，每個視角描述一個數(shù)據(jù)特征。Sun等[16]提出一種通過遺傳算法構建多視圖的特征選擇方法，用于尋找可能的特征子集。多視角黑賽半監(jiān)督低維特征選擇(Multi-view Hessian Semi-supervised sparse Feature Selection for multimedia analysis, MHSFS)方法[17]，利用多視圖學習來揭示和利用不同視圖間的相關和互補信息，從而直接實現(xiàn)多視圖稀疏特征選擇。Zhu等[18]提出了一個新的多視角半監(jiān)督學習框架，利用圖像中偽標簽包含的信息提高圖像分類的預測性能。

這些方法仍然存在兩個主要問題：1)嵌入思想類似于單視角問題的研究。大多數(shù)已有方法在各個單視角下引入的嵌入矩陣都是相同的，并未考慮到不同視角間特征的差異性。2)一些半監(jiān)督特征降維方法，僅僅局限于局部結構的保持項，并未考慮到全局范圍的特征降維，且部分方法由于缺乏對降維后的低維矩陣的稀疏約束，無法避免噪聲和其他不相關特征的影響。

針對以上兩個問題，本文提出了一種自適應嵌入的半監(jiān)督多視角特征降維方法(Semi-Supervised Adaptive Multi-View Embedding method for feature dimension reduction, SS-AMVE),將嵌入思想直接引入到多視角問題中，考慮各視角下特征的差異性，將投影從單視角下相同的自適應矩陣擴展到多視角間不同的矩陣。在半監(jiān)督模式下引入全局結構的保持項,將不含標簽信息的數(shù)據(jù)利用無監(jiān)督模式方法進行嵌入投影；對于含有標簽的數(shù)據(jù)，結合分類的判別信息進行線性投影。然后，將多投影映射到一個統(tǒng)一的低維空間，使用組合權重矩陣保留全局結構，并引入正則化參數(shù)。實驗結果表明，所提方法較好地保留了多視角間特征的相關性，捕獲了更多的具有判別信息的特征。

1 相關工作

相關學者相繼提出各種多視角特征降維方法[19-20]。對于多維特征，通過引入嵌入思想，構建各視角間的相似性矩陣來保留原始的結構信息，已經(jīng)取得了一定的研究成果。FSASL方法[14]提出了一種多視角下自適應性的全局結構保持方法，通過稀疏重構來保留數(shù)據(jù)的原始結構。將各個視角的數(shù)據(jù)信息映射到一個最優(yōu)稀疏組合權重矩陣，并在重構過程中引入行變換矩陣W，具體表達式如下：

(1)

s. t.Qii=0,WTXXTW=I

式中：X={x1,x2,…,xn}∈Rd×n為原始的數(shù)據(jù)矩陣；α為約束低維矩陣的正則化參數(shù)；Q為全局特征投影到低維空間下的組合權重矩陣。約束WTXXTW=I可以避免受到小樣本量數(shù)據(jù)的影響。l1范數(shù)正則化可以產(chǎn)生稀疏權值矩陣，即產(chǎn)生一個稀疏模型，用于特征提取使得特征系數(shù)變?yōu)?。

在半監(jiān)督模式下，多視角間局部特征結構的保持顯得尤為重要。對于有標簽和無標簽的數(shù)據(jù)，一個統(tǒng)一的半監(jiān)督特征降維框架(a unified framework for Semi-Supervised Dimensionality Reduction, SSDR)方法[21]提出利用兩者在投影空間中的正則化項，可以以一種共同的方法來提取視角的局部結構信息，在一定程度上保留原始結構信息和成對約束信息。最終得到以下正則化目標函數(shù)：

(2)

式中：Mij為相似性矩陣；L為拉普拉斯矩陣。

進一步，半監(jiān)督模式下，對于正則化線性判別(Regularization Linear Discriminant Analysis, RLDA)方法及正則化最大距離準則(Regularization Maximum Margin Criterion, RMMC)方法，投影矩陣W的求解可以分別通過以下形式得到：

(3)

(4)

其中，類內(nèi)散布矩陣Sw和類間散布矩陣Sb定義為:

(5)

2 半監(jiān)督模式下多視角特征降維框架

在半監(jiān)督模式下，以上提到的FSASL方法沒有考慮各單視角投影矩陣的差異。SSDR方法在特征降維時僅僅引入局部結構的保持項，且由于缺乏對低維矩陣的稀疏約束，有時無法避免噪聲和其他不相關特征的影響。因此，針對以上問題，本文提出了SS-AMVE。目標函數(shù)可以分成兩個部分，分別為全局結構保持項和局部結構保持項。同時，對每個視角上的投影矩陣添加行稀疏約束，具體的流程如圖1所示。

圖1 SS-AMVE流程Fig. 1 Flow chart of SS-AMVE

2.1 保持局部結構的半監(jiān)督多視角學習

設第v個視角上的投影矩陣為Wv=[Wv1,Wv2,…，Wv,dn]∈RDn×dn，則第v個視角上的低維嵌入為WvTXv，由此得到表達式:

(6)

對各投影矩陣添加稀疏性約束，局部保持項的目標函數(shù)變?yōu)?

(7)

同樣，在有標簽和無標簽的數(shù)據(jù)信息同時存在的條件下，本文針對多視角半監(jiān)督模式下的RLDA方法及RMMC方法中的投影矩陣進行具體的求解，以保留局部的流形結構信息。

2.1.1 半監(jiān)督多視角RLDA局部結構保持

將RLDA方法由單視角推廣到多視角問題，各視角下投影矩陣的表達式為:

(8)

式(8)通過最大限度地減少類內(nèi)特征的分散性，來保留局部的流形結構。參數(shù)α、β則用來平衡正則化的形式。

2.1.2 半監(jiān)督多視角RMMC局部結構保持

類似的，將正則化最大距離準則(RMMC)方法推廣到多視角半監(jiān)督特征降維，各視角下投影矩陣的表達式轉化為:

(9)

2.2 保持全局結構的半監(jiān)督多視角自適應嵌入

2.2.1 無標簽數(shù)據(jù)信息的全局結構保持

對于不含標簽的數(shù)據(jù)，可以直接將其看作非監(jiān)督模式下的特征降維。非監(jiān)督自適應性特征選擇(FSASL)方法，并未考慮不同視角特征的差異性，認為得到的投影矩陣都是相同的。對此，進行一定程度上的推廣與改進。

對每個視角分別定義一個行稀疏特征選擇和變換矩陣Wv∈Rd×c。為了保留更多的特征，將各單視角下得到的投影求和作為最終選定的特征空間。對于每個特定的單視角，得到以下的結構保持項:

s. t.WTW=I,Tii=0

進一步，將其推廣到多視角問題，對各個視角下提取出的特征進行求和，得到多視角下全局結構的表達式:

(10)

s. t.WvTWv=I,Tii=0

與成對相似性相比，稀疏表示具有一定的識別性：在所有的候選樣本中，它選擇距離目標最近的樣本，舍掉所有其他不夠緊湊的候選樣本。由此，可以進一步優(yōu)化對嵌入矩陣的求解。

2.2.2 含標簽數(shù)據(jù)信息的全局結構保持

在半監(jiān)督學習模式中，對于包含標簽的一些數(shù)據(jù)，需要結合標簽信息，對不同視角下的特征投影進行說明。在此，同樣對正則化線性判別(RLDA)方法及正則化最大距離準則(RMMC)方法在半監(jiān)督模式下的特征投影矩陣進行具體的求解。類似的，不同視角下的特征存在差異性，需要對單視角的投影矩陣分別進行定義。

考慮數(shù)據(jù)的標簽信息時，對于正則化線性判別(RLDA)方法，在特定的第v個視角下，投影矩陣的定義如式(8)。對于正則化最大距離準則(RMMC)方法，在第v個視角下，投影矩陣定義如式(9)。

2.3 多視角半監(jiān)督模式下的自適應嵌入特征降維

由此，將嵌入思想直接引入到半監(jiān)督多視角問題中，同時對各個視角下的數(shù)據(jù)進行特征降維，完成了整體特征的重構以及局部特征的保持，最終得到目標函數(shù):

(11)

3 算法求解

LT=(I-T)(I-T)T

L=LT+Lv

目標函數(shù)變?yōu)?

又由于μ‖T‖為獨立項，與Wv無關，可轉化為：

(12)

其中Dv是一個對角矩陣，對角線上的元素為：

(13)

s. t.WvTWv=I

交替迭代更新式(12)即可得到Wv對應的特征向量。

變量T只存在于第一項中，當固定其他變量時，已知約束條件Tii=0，故可由求解以下問題來對T進行優(yōu)化：

s. t.Tii=0

對T求偏導，有:

μ=0

通過求解得到：

(14)

為方便表示，定義：

優(yōu)化函數(shù)可以表示為：

利用拉格朗日方程，得到以下等式:

其中，σ為拉格朗日系數(shù)，化簡得:

根據(jù)約束條件:

則:

(15)

由此，本文分別得到了三個變量的優(yōu)化表達式，具體的更新過程如算法1所示。

算法1 自適應嵌入的半監(jiān)督多視角特征間降維方法(SS-AMVE)。

初始化：

迭代更新：

Forv=1 ToV(循環(huán)v個視角)

計算各視角下的Sw,Sb；

s. t.WvTWv=I

通過交替迭代得到Wv對應的特征向量；

對于多視角正則化線性判別(MV-SSLDA)方法，根據(jù)式(8)，計算特征值及特征向量；

對于多視角正則化最大距離準則(MV-SSMMC)方法，根據(jù)式(9)，計算特征值及特征向量；

直到收斂。

分別對v個視角下Xv的特征進行排序，選取前kv個特征作為結果。

4 實驗結果及分析

本文設計了4組實驗來驗證自適應嵌入的半監(jiān)督多視角特征間降維方法(SS-AMVE)的性能和效果。

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

在實驗中，本文使用4個圖像數(shù)據(jù)集，來測試自適應嵌入的半監(jiān)督多視角特征間降維方法( SS-AMVE)的性能。具體包括：Yale face(http://www.oalib.com/references/9283312)，Handwritten digits(http://yann.lecun.com/exdb/mnist)，WebKB(http://www.cs.umd.edu/～sen/lbc-proj/LBC.html)，Labelme(http://labelme2.csail.mit.edu/Release3.0/index.php)，以上分別為不同領域下不同類別的圖片資源。

圖2給出了部分樣本圖像。具體的圖像提取信息如表1所示。其中，維度是標簽的一種屬性。每個樣本的標簽信息，可以表示一個特定維度的數(shù)據(jù)標識；而對于多視角特征提取，標簽通常代表多種含義。因此對于同一個樣本，本文選取多個維度進行數(shù)據(jù)集的測試實驗。對于4個數(shù)據(jù)集，隨機將每個數(shù)據(jù)集中的數(shù)據(jù)分為含標簽信息的數(shù)據(jù)和不含標簽信的數(shù)據(jù)。將本文方法與拉普拉斯得分(Laplacian Score, LS)、半監(jiān)督判別分析(SDA)、半監(jiān)督特征降維框架(SSDR)、多視角半監(jiān)督特征降維(Multiple View Semi-Supervised Dimensionality Reduction, MVSSDR)四種方法進行對比，各方法內(nèi)容介紹如下：

1)LS方法[7]：該方法通過計算特征對于原始結構的局部保持能力，根據(jù)得分大小選擇與最高分相對應的特征。

2)SDA方法[11]：該方法使用帶標簽的數(shù)據(jù)點來最大化不同類別之間的可分離性，通過標記數(shù)據(jù)點來估計數(shù)據(jù)的固有幾何結構。

3)SSDR方法[21]：半監(jiān)督降維方法中，通過成對約束矩陣平衡每個視角的嵌入投影。同時，引入線性變換使得不同視角下的不同嵌入特征矩陣具有可比性。

4)MVSSDR方法[22]：該方法將SSDR方法引入到多視角數(shù)據(jù)中，且利用稀疏正則方式進行半監(jiān)督多視角特征降維。

圖2 部分樣本圖像Fig. 2 Some sample images表1 樣本數(shù)據(jù)集信息Tab. 1 Information of sample datasets

數(shù)據(jù)集樣本數(shù)特征數(shù)維度數(shù)數(shù)據(jù)集樣本數(shù)特征數(shù)維度數(shù)Yale face1653066WebKB8775648Digits179710010Labelme1206474

在4種方法LS、SDA、SSDR、MVSSDR中設置最近鄰個數(shù)為5，參數(shù)β、γ通過格點搜索來確定。同時，將本文方法中的參數(shù)μ設為1，設定各個視角上所選特征數(shù)總數(shù)為100。對于單視角特征選擇算法LS，仍按各個視角上特征數(shù)的比例來決定各個視角上要選擇的特征的數(shù)量，采用逐個視角上特征降維的策略。對于MVSSDR方法，在數(shù)據(jù)上運行算法，得到各個視角上的投影矩陣來選擇特征。進一步，改變含標簽信息的數(shù)據(jù)量，本文對所有算法進行了15次實驗，并記錄了聚類準確率(ACC)的平均值和標準差。考慮到聚類性能隨初始聚類中心的選擇而變化，本文在4種算法中調節(jié)譜聚類形式20次。

4.2 實驗結果與分析

4.2.1 半監(jiān)督模式下不同方法的聚類結果

對于LS方法，采用逐個視角上特征降維的策略，通過調整各個視角上特征數(shù)的比例來確定各個視角上要提取的特征的數(shù)量。對于SSDR和MVSSDR方法，通過各個視角上的投影矩陣得到提取結果。改變含標簽信息的數(shù)據(jù)量，比較含標簽信息的數(shù)量不同的情況下特征降維的結果。

對于半監(jiān)督的方法，利用所有可見數(shù)據(jù)集合，包括有標簽數(shù)據(jù)和無標簽數(shù)據(jù)，對其進行訓練。5種算法和基線的聚類準確率(ACC)結果如表2所示。

從表2可以看出，除了數(shù)據(jù)集Digits外，本文提出的SS-AMVE在其他數(shù)據(jù)集中都優(yōu)于其他4種方法。在WebKB數(shù)據(jù)集上，SS-AMVE比其他方法的最佳結果增加了10%以上。在Labelme數(shù)據(jù)集上，SS-AMVE平均的提升比例也接近9%。與SDA和SSDR方法相比，SS-AMVE整體上能夠得到更好的結果。應用本文方法SS-AMVE，人臉圖像可以被映射到由“半監(jiān)督特征面”構成的半監(jiān)督判別子空間中。可以看出，SS-AMVE考慮了不同視角下的投影矩陣的差異，并將其統(tǒng)一映射到一個組合空間中，通過引入低維矩陣可以消除不相關特征的影響。而對于Digits數(shù)據(jù)集的ACC結果，SS-AMVE雖未達到基準線,但仍然優(yōu)于其他方法。

表2 不同算法聚類準確率(ACC)的平均值和標準偏差 %Tab. 2 Average and standard deviation of different algorithm clustering accuracy (ACC) %

4.2.2 不同特征數(shù)下各方法的性能比較

為了更直觀地觀察不同方法之間的性能差異，對于4個數(shù)據(jù)集，5種算法在不同數(shù)量特征下的聚類準確率(ACC)如圖3所示。

圖3 不同特征數(shù)下不同方法的ACCFig. 3 ACC of different methods under different feature numbers

從圖3(a)可以看出，隨著所選特征數(shù)量的增加，本文方法的聚類準確率呈現(xiàn)平穩(wěn)上升趨勢，除了所選特征數(shù)為50時，本文方法都有最高的聚類準確率，且當特征數(shù)大于80時，本文方法的準確率基本趨于穩(wěn)定。

從圖3(b)中可以看出，對比的4個方法整體上均呈現(xiàn)平穩(wěn)上升的趨勢，并當特征數(shù)大于70時保持穩(wěn)定，當所選特征數(shù)量為60～100時，本文方法雖然略低于基準線，但都有最高的聚類準確率。

從圖3(c)可以看出，本文方法在處理WebKB數(shù)據(jù)集時有很好的聚類準確率，在所選特征數(shù)量是40～100時均優(yōu)于基準線，并且準確率較穩(wěn)定。

從圖3(d)可以看出，本文方法的聚類準確率整體上變化幅度很小，當所選特征數(shù)量為20～60和80～100時能得到最優(yōu)的聚類準確率。

由上述分析可知，在大多數(shù)情況下，SS-AMVE的聚類準確率優(yōu)于其他方法。一方面，在選擇的特征數(shù)量相同的情況下，本文的方法可以更加緊湊地保留數(shù)據(jù)的結構信息；另一方面，SS-AMVE可以實現(xiàn)更高效的降維，特別是在數(shù)據(jù)集WebKB中。

在Digits和Labelme中，自適應嵌入的半監(jiān)督多視角特征間降維方法( SS-AMVE)的ACC值很接近或者有時略大于半監(jiān)督特征降維框架(SSDR)方法，而在其他數(shù)據(jù)集中則不是很接近這種情況,表明SS-AMVE在處理部分數(shù)據(jù)方面有其自身的優(yōu)勢。

當特征數(shù)量較大時，SSDR有著更好的聚類性能，表明SSDR方法能有效地獲得原始數(shù)據(jù)的全局和內(nèi)在幾何結構，從而獲得更多的判別信息。

4.2.3 不同平衡程度下的樣本集結果比較

在數(shù)據(jù)集WebKB和Labelme中，不同平衡程度下SS-AMVE樣本集結果如表3可知。由表3可以看出，兩個數(shù)據(jù)集中，在有無標簽比例為1∶1時，本文方法的聚類準確率(ACC)最高，且均大于50%。由此可見本文提出的半監(jiān)督方法，更適用于一些特定的數(shù)據(jù)集;當有無標簽比例改變時，SS-AMVE聚類準確率稍有變化，但仍大于50%，具有一定的普適性。

表3 不同平衡程度下SS-AMVE樣本集結果Tab. 3 Sample set results of SS-AMVE at different equilibrium levels

4.2.4 算法靈敏度分析

本文進行了大量的實驗來測試參數(shù)的靈敏度，并選定WebKB和Labelme作為實驗數(shù)據(jù)集。當β固定為1，改變γ取值時，本文方法SS-AMVE在數(shù)據(jù)集上的ACC結果如圖4所示。當γ固定為1，改變β取值時，本文方法SS-AMVE在數(shù)據(jù)集上的ACC結果如圖5所示。由圖4～5可以發(fā)現(xiàn)，相較于參數(shù)β，SS-AMVE對參數(shù)γ更為敏感。在圖4中, 在數(shù)據(jù)集WebKB中，當γ=1時，SS-AMVE有較高的ACC值。在圖5中, 對參數(shù)β而言，SS-AMVE的ACC值相對穩(wěn)定，尤其在數(shù)據(jù)集WebKB中；值得注意的是，在Labelme數(shù)據(jù)集中，當β=1時，SS-AMVE的ACC值幾乎是不變的。

4.2.5 算法收斂性

自適應嵌入的半監(jiān)督多視角特征間降維方法(SS-AMVE)在數(shù)據(jù)集WebKB和Labelme下的收斂性曲線如圖6所示。由圖6可以看出，目標函數(shù)值在迭代期間不增加，并最終收斂到固定值，SS-AMVE在10次迭代內(nèi)收斂，表明了該方法具有較為快速的收斂速度。

圖5 SS-AMVE在不同特征數(shù)和β下的ACC(γ=1)Fig. 5 ACC of SS-AMVE under different feature numbers and β (γ=1)

4.2.6 算法復雜度

圖6 不同迭代次數(shù)下SS-AMVE的目標函數(shù)值Fig. 6 Objective function values of SS-AMVE under different iterations

5 結語

本文提出了一種半監(jiān)督特征降維方法，即自適應嵌入的半監(jiān)督多視角特征間降維方法(SS-AMVE)，直接將嵌入思想引入到多視角中，并將從各個視角提取的特征映射到一個統(tǒng)一的空間，以保持整體的全局結構?？紤]到不同視角下的特征可能不同，本文將各單視角下相同的嵌入投影矩陣推廣到多視角間的不同矩陣。對于有標簽與無標簽的信息同時存在的高維數(shù)據(jù)，在局部特征得到保留的基礎上，增加了全局結構的保持項。將不含標簽信息的數(shù)據(jù)利用無監(jiān)督模式方法進行嵌入投影；對于含有標簽的數(shù)據(jù)，結合分類的判別信息進行線性投影。使用組合權重矩陣來保留全局結構，很大程度上消除了噪聲及不相關因素的影響。實驗結果表明，自適應嵌入的半監(jiān)督多視角特征間降維方法(SS-AMVE)是保持全局和局部結構的有效方法，在半監(jiān)督多視角問題中可以更好地提取出具有判別信息的特征。

本文所提方法涉及到了特征值分解，而這一過程的時間復雜度對于計算機的內(nèi)存要求大，且時間效率不夠高，因此需要尋求更好更快的解決方法。同時，方法中參數(shù)的設定值影響提取效果，而如何確定參數(shù)的最優(yōu)值，是進一步需要研究的方向。