特征標記依賴自編碼器的多標記特征提取方法*

程玉勝，李志偉，龐淑芳

1.安慶師范大學 計算機與信息學院，安徽 安慶246011

2.安徽省高校智能感知與計算重點實驗室，安徽 安慶246011

1 引言

隨著大數據時代的到來，人們能從各種渠道獲取大量的數據，但同時也帶來了如何處理這些數據的問題，其中最常見的方法是對數據進行降維，主要包括特征選擇和特征提取。目前特征選擇研究較多，但相對于特征選擇而言，特征提取可以通過原始數據集進行適當變換，得到更有效更有用的低維特征[1-5]。目前已經有很多經典的特征提取方法，如主成分分析（principal component analysis，PCA）[6]、方向梯度直方圖（histogram of oriented gradient，HOG）[7]、線性判別分析（linear discriminant analysis，LDA）[8]、潛在語義索引（latent semantic indexing，LSI）[9]等。

相比于傳統的單標記問題，經典的分類建模方法取得了不錯的成果，而關于多標記分類問題，往往可以利用標記之間相關信息有效提高分類器的性能。但目前多標記學習仍存在三大挑戰。其一，在單標記學習中，各示例標記分類相互排斥不存在共生關系，而對于多標記學習則各標記之間存在相關性，如何利用標記之間的相關性對多標記分類精度的提高尤為重要[10]。其二，在多標記學習中，數據特征往往具有較高的維度，而高維特征可能導致“維度災難”，嚴重影響分類器的分類性能。其三，在多標記學習中各標記與其特征具有關聯性[11-12]，如何挖掘此類信息也是多標記學習中難點之一。為此大量學者提出了各種多標記分類學習方法，如類KNN（K-nearest neighbor）方法[13]、集合分類器和集成學習技術[14-16]，大多數已被廣泛地應用。

但是上述方法主要采用特征選擇的方法進行分類建模，由于該方法通常具有指數級時間復雜度，一般不太適合高維數據分類建模。目前，多標記學習中數據一般具有高維性特點，因此如何處理這些高維數據，相關研究成果相繼被提出。例如：MLSI（multi-label informed latent semantic indexing）[17]擴展了單標記無監督潛在語義索引（LSI）來處理多標記特征提取問題，通過引入權重來構建一個新的特征-標記信息的函數；文獻[18]利用LDA 方法進行多標記特征降維處理，但是并沒有有效利用標記與標記之間的相關性；文獻[19]提出了多標記線性判別分析（multi-label linear discriminant analysis，MLDA）方法，在LDA 的基礎上進行了優化，利用了標記與標記之間的關系，但是在實際中的性能受到了標記數量的影響；文獻[20]基于希爾伯特-施密特獨立標準（Hilbert-Schmidt independence criterion，HSIC）提出了基于最大化依賴的多標記維度約簡方法（multi-label dimensionality reduction via maximum dependence，MDDM）。MDDM

的主要目的是通過使特征-標記之間的依賴度達到最大而得到最適合實驗數據的投影矩陣，但是該方法并沒有充分獲取特征的信息，也沒有考慮特征-特征、標記-標記的內在聯系。

基于此，本文提出了一種基于特征標記依賴自編碼器的多標記特征提取方法（multi-label feature extraction method relied on feature-label dependence autoencoder，MIMLFE）。主要包括：（1）使用核極限學習機自編碼器將標記空間與原特征空間融合并產生重構后特征空間；（2）結合主成分分析與希爾伯特-施密特獨立準則分別提取“特征-特征”和“特征-標記”信息；（3）使用多標記K近鄰算法（multi-labelKnearest neighbor，ML-KNN）分類器進行分類。通過Yahoo 數據集中的11個子數據集上的結果與相關對比算法比較表明，本文提出的算法在多個評價指標上大部分優于這些方法。在算法介紹結束后給出了本文的偽代碼。

2 基本理論研究

2.1 核極限學習機

極限學習機（extreme learning machine，ELM）[21-24]是一種單隱層前饋神經網絡。相比于傳統神經網絡算法需要較多的網絡參數設置可能出現局部最優解而無法得到全局最優的問題，極限學習機的主要特點在于學習速度快并且效果相較之前的神經網絡也有著很大的提高。該網絡在求解時只需設置隱藏層節點數并隨機初始化權值和偏置就可以以較快的速度得到全局最優解。ELM 求解單隱層前饋神經網絡可分為兩個階段：隨機特征映射和線性參數求解。

在求解之前需要先做出以下定義：設有N個隨機樣本{(Xi,Yi)|i=1,2,…,N}，其中特征空間與標記空間可分別表示為Xi=[xi1,xi2,…,xin]Τ，Yi=[yi1,yi2,…,yim]Τ，對于具有L個隱藏節點的單隱藏層神經網絡形式化定義為：

式（1）中，βi=[βi1,βi2,…,βim]Τ表示輸出權值，gi表示第i個隱藏節點的輸出，而gi實質為激活函數，并可表示為：

式（2）中，Wi=[wi1,wi2,…,wim]Τ為輸入權值，bi表示為第i個隱藏神經元的偏置，?表示為點積。通常式（1）用來建?；貧w，而對于分類問題可使用sigmoid 函數來限制輸出值的范圍，從而達到分類效果。

以上為ELM 的第一階段即隨機特征映射，對于第二階段的線性參數求解，通過最小化平方誤差的近似誤差來求解出連接隱藏層和輸出層的權值β可表示為：

其中，H為隱藏層輸出矩陣：

Y為訓練標記矩陣：

通過式（1）和式（3），最小二乘解為：

其中，H?表示H的Moore-Penrose 廣義逆矩陣，表示為：

2.2 主成分分析

主成分分析是一種統計方法，是一種簡化數據集的技術，是一個線性變換。這個變換把數據變換到一個新的坐標系統中，使得任何數據投影的第一大方差在第一個坐標（稱為第一主成分）上，第二大方差在第二個坐標（第二主成分）上，依次類推。主成分分析經常用減少數據集的維數，同時保持數據集的對方差貢獻最大的特征。同時無監督范式下最流行的線性特征提取方法之一，無監督的方法是在不使用標簽標記信息的情況下提取少量特征來保留盡可能多的判別信息，基于最小化平方重構誤差來尋找最優投影矩陣。主成分分析可表示為以下最小二乘問題：

其中，F 表示矩陣的Frobenius 范數，P∈RD×D是投影方向矩陣，A∈Rl×D表示投影系數矩陣。通過約束PΤP=I，限制投影方向（即P的列向量）是正交的。

其中，tr()是矩陣的軌跡，通過使用?tr(XA)/?A=XΤ和?tr(AΤA)/?A=2A，然后設定J(A,P)對A的導數為零，得到并插入J(A,P)，目標函數（10）就可以簡化為:

因為tr(XΤX)是常數項，最小化J(P)的問題就可以等價于最大化tr(PΤXΤXP)，所以式（9）可以轉化為：

通過拉格朗日乘數技術，將該問題轉化為如下特征值問題XΤXP=ΛP，其中Λ是一個對角矩陣的特征值(λ1,λ2,…,λD≥0)。

映射矩陣P是由相應的特征向量組成，主成分分析投影系數矩陣A的協方差矩陣是ATA=PΤXΤXP=Λ。說明主成分分析投影系數是不相關的。然后可以將式（11）轉化為J(P)=tr(XΤX)-tr(Λ)。為了使J(P)最小化，選擇d(

其中，t∈(0,1)是一個合適的閾值，用于衡量保存原始數據的信息。

2.3 基于依賴最大化的多標記維數約簡

Hilbert-Schmidt 獨立性標準（HSIC）是一種非參數依賴性度量，它考慮所有變量之間的所有依賴關系模式。對于特征空間和標記的線性核，HSIC 的經驗估計被描述為：

其中，tr()表示的是矩陣的軌跡，K和L分別是示例和標記對應的核矩陣。H用于除去均值IN表示大小為N×N的單位矩陣，eN表示所有的元素都是1，長度為N的列向量。如今通過MDDM 方法HSIC 已經成功應用在多標記特征提取上，忽略常數項(N-1)-2得到目標函數：

其中，P是線性變換矩陣P∈Rd×t，MDDM 的主要目的是通過使特征-標記之間的依賴度達到最大而得到最優的映射矩陣P，此方法已經在文獻[25-26]中得到驗證。具有正交投影方向的MDDM 的原始優化問題也被稱為MDDMp[25]：

3 特征重構的多標記特征提取

3.1 基于KELM（kernel ELM）自編碼器的多標記特征重構

在現實世界中，真實的對象并不能如理論中那樣簡單，傳統的單標記學習算法由于算法簡單、對象單一而不能對現實中多語義復雜的對象進行有效準確的處理，也無法解決機器學習中的高難度問題，因此需要通過建立一個新的多標記學習框架來解決這一問題。對于任意的一個對象，通過向量來對其一個特征進行描述，再用這個特征向量對對象進行分類和類別標記。假定一個有N個樣本的多標記數據集，X為n維的示例空間Rn，Y為m類標記空間，則在多標記學習中，給定數據集D={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈X是一個示例，yi∈Y是一組標記集合且，可得到映射關系f:X→2Y。

自動編碼器（auto encoder）最早是由Rumelhart在1986年提出的，并成功用于處理高維度復雜數據，它的出現大大促進了神經網絡的發展。自動編碼器是一個由大于或等于3 層的神經網絡組成，主要是輸入層、隱藏層和輸出層。自動編碼器主要分為編碼和解碼兩個過程。先將無標記的特征a輸入到encoder 編碼器得到輸出b。這時候需要判別之前輸入的a和b是否表示一致。這時就在輸出后再加一個decoder 解碼器，此時b就成為了解碼器decoder 的輸入，現在只要判斷這個輸出信號與之前的輸入a的近似度就可以得到結論。如果這兩個近似度很高，那么就有理由可以相信這個b是可靠的。因此在自編碼器中需要不斷調整encoder 與decoder 的參數使得重構的誤差最小，此時的b就是原輸入a的表示。

根據多標記學習的目標，同時結合ELM 學習模型和自編碼器，多標記ELM 的輸出函數H為：

為了使ELM 的輸出h(x)β取得更好的分類結果，RELM 算法（regularized ELM）就是添加L2 正則來提高原始ELM 算法的穩定性和泛化性能，同時有效避免過擬合，目標函數表示為：

其中，ξi=[ξi1,ξi2,…,ξim]Τ，是訓練樣本Xi在m個輸出節點的訓練誤差向量，C為正則化參數，根據KKT（Karush-Kuhn-Tucker）理論，可得:

其中，βj是連接隱藏層節點到第j個輸出節點的權值向量，β=[β1,β2,…,βm]，每個拉格朗日乘子αij對應于第i個樣本的第j個輸出節點，同時αi=[αi1,αi2,…,αim]Τ，α=[α1,α2,…,αm]Τ，可得到如下的KKT優化條件：

訓練樣本數N和隱藏層節點數L決定著隱藏層節點輸出H的大小，將等式（21）和等式（22）代入等式（23），可以得到：

U=(xN,yN)表示原特征空間xN與標記空間yN融合成的新的特征空間。此時，從等式（23）和等式（24）可得出ELM 的表達式為：

當N>L時，即當樣本數量N大于隱藏節點數L時，可以從式（21）、式（22）和式（23）中得出ELM 另一種表達式為：

在ELM中，用戶通常知道特征映射，如果用戶不知道特征映射，則可以按如下方式定義ELM的內核矩陣：

此時，可得KELM 的輸出表達式為：

3.2 結合PCA 與HSIC 的多標記特征提取

目前，PCA 已經得到了廣泛的應用。盡管現存的特征提取算法有很多，但是大部分不能有效利用“特征-特征”的信息，為此提出的方法希望既可以有效利用標記信息，又可以充分利用特征信息。第一，結合2.3 節的相關知識，采用了基于HSIC 與MDDM相同的目標函數，通過最大化XP與標記U之間的依賴度以獲取“標記-標記”的信息；第二，利用PCA 的優點，降低維度約簡中信息的損失。然后將PCA 中的目標函數與MDDMp 中的目標函數線性組合，最大化特征方差并同時最大化“特征-標記”依賴性。

其中,λ∈[0,1]是控制PCA 和MDDMp 兩個平方誤差項之間權衡的平衡因子，A和B表示兩個投影系數矩陣，P表示投影方向矩陣。當λ=0 時，該模型退化為原始PCA，而當λ=1 時，模型就相當于MDDMp。然后對公式進行擴展：

在J(A,B,P)相對于A和B的導數為0之后，得到：

根據A和B上式可以化簡為：

然后定義了一個新的向量：

帶入得到J(P)=tr(G)-tr(PTGP)，因為tr(G)是不變的，所以將問題轉化為：

再利用拉格朗日定理轉化為GP=ΛP，現在的目標函數為G(P)=tr(G)-tr(Λ)。意味著應該選擇d維最大特征值及其特征向量來構造映射矩陣P。

算法偽代碼如下：

算法1MIMLFE 算法

輸入：X，N×n維樣本特征空間；Y，N×m維樣本標記空間；λ，平衡因子；t，特征值閾值；d，映射特征的維度。

（1）根據式（28）通過核極限學習機自編碼器重構特征空間；

（2）根據式（33）構造出矩陣G；

（3）構造具有最大d特征值的n×d映射矩陣P；

（4）ML-KNN 分類器分類。

4 實驗方案及結果分析

4.1 實驗數據及評價指標描述

為驗證本文算法的有效性，從雅虎網站選取了不同的應用領域中的11個數據集（“Arts”“Business”“Computers”等）進行測試，各數據集的特征數目在400～1 100 之間，各數據集中包含2 000個訓練樣本以及3 000個測試樣本，詳細信息如表1 所示。

對于多標記學習，為有效驗證本文算法性能，本文采用海明損失（Hamming Loss，HL）、1-錯誤率（One-Error，OE）、覆蓋率（Coverage，CV）、排序損失（Ranking Loss，RL）[27]和平均精度（Average Precision，AP）作為評價算法性能的指標。

設多標記分類器為h(?)，預測函數f(?,?)，排序函數rankf，多標記數據集D={(xi,Yi)|1 ≤i≤n}。上述5種評價指標HL、OE、CV、RL和AP具體定義如下：

海明損失用于估計樣本在單個標記上被誤分類的情況。公式中Δ 用于計算h(xi)和Yi的對稱差。當HLD(h)=0 時為最好的情況，HLD(h)越小，分類器h(?)的性能越高。

1-錯誤率度量標準用于評估排名靠前的標簽在對象的正確標簽集中的次數。即OED(f)越小，f(?)的性能越高，當OED(f)=0 時為最好的情況。

覆蓋率公式表示的意思就是所有文檔中排序最靠后的真實標記的排序平均值，CVD(f)越小，f(?)的性能越高。

排序損失表示的是相關標記與非相關標記進行兩兩對比，然后統計相關標記比非相關標記預測可能性小的次數。RLD(f)越小，f(?)的性能越高，當RLD(f)=0 時為最好情況。

Table 1 Details of Yahoo data sets表1 雅虎數據集描述

平均精度用于考察在樣本的類別標記排序序列中，排在給定樣本標記之前的標記仍屬于該樣本標記概率的均值，APD(f)越大，f(?)的性能越高，最優值為1。

4.2 實驗方案及參數選取

對比實驗代碼均在Matlab2016a 中運行，硬件環境Intel?CoreTMi7-8700K 3.7 GHz CPU，16 GB 內存；操作系統是Windows 10。在實驗中，每個算法的性能將由5個評估指標綜合測量，各評價指標中↑表示指標數值越高越好，↓表示指標數值越低越好。實驗采用OS（original set，表示原始ML-KNN 沒有使用任何的特征提取算法的結果）、MDDMp、MVMD（multi-label feature extraction algorithm via maximizing feature variance and feature-label dependence）[26]、PCA、MLSI 和wMLDA（weighted MLDA）等多標記特征提取算法與本文算法MIMLFE 進行各指標對比。

在各對比算法的參數設置上，在MDDMp 中，設置為0.5。本文的實驗使用ML-KNN 作為分類器，ML-KNN 值設置為默認值，即平滑系數設置為1，最近鄰居數k設置為10。

4.3 實驗結果及分析

為了更直觀展示本文算法的有效性，本文在選取的11個數據集中每個數據集選取的特征子集數目占總數的10%，與所有對比實驗的實驗結果如表2～表6 所示。同時，隨著特征子集數目的改變，針對評價指標AP，11個數據集在各個算法上的趨勢情況如圖1 所示，其他4個評價指標也可同樣繪制此圖，由于篇幅有限，省去未提。表7 給出各算法在11個數據集中實驗的時間消耗。

Table 2 Results of Hamming loss↓表2 海明損失測試結果

Table 3 Results of one-error↓表3 1-錯誤率測試結果

Table 4 Results of coverage↓表4 覆蓋率測試結果

Table 5 Results of ranking loss↓表5 排序損失測試結果

Table 6 Results of average precision↑表6 平均精度測試結果

Table 7 Comparison of computation time for algorithms表7 各算法的時耗對比 s

實驗結果分析：

（1）對 于Hamming Loss、One-Error 和Ranking Loss，可以發現在11個數據集上，其中有10個數據集取得最優值，即分類性能最佳。在數據集Computers上，MIMLFE 取得的Hamming Loss 值與最優Hamming Loss 值僅相差0.000 2。在數據集Business 上，MDDMp 算法在所有對比算法中取得的One-Error 最優值，MIMLFE 取得的One-Error 值比最優值僅高0.002。在數據集Social 上，ML-KNN 取得了最優Ranking Loss值。

（2）對于Coverage，MIMLFE 在9個數據集上取得最小Coverage 值。另外兩個數據集在MIMLFE 上取得Coverage 值與最優Coverage 值最大僅相差0.083 0，最小僅相差0.020 7。實驗結果進一步表明本文算法在絕大部分數據集上占優。

（3）對于Average Precision，MIMLFE 在11個數據集上取得Average Precision 值都是最大，這充分表明本文所提出算法的有效性。

（4）圖1 為MIMLFE 算法在11個多標記數據集上以Average Precision 為指標的特征趨勢圖，可發現MIMLFE 選取的特征子集在特征總數的10%本文算法MIMLFE 比所有對比算法都占優。隨著特征子集數量的增加，MIMLFE 在大部分數據集上效果都占優。進一步說明該算法性能占優。

各算法在多個數據集實驗的時間消耗如表7 所示，本文提出的算法MIMLFE 運行的時間消耗明顯比OS 和wMLDA 少，MIMLFE 和其他4個對比算法的運行時間基本相差不大，但是性能明顯占優。進一步表明本文算法MIMLFE 的有效性。

為了進一步驗證本文算法的有效性，運用統計學知識，在11個數據集上采用顯著性水平為5%的Friedman test[28]檢驗。對于每個評價指標，都拒絕零假設，若兩個算法在所有數據集上的平均排序的差高于臨界差（critical difference，CD），則認為它們有顯著性差異；反之則兩個算法沒有顯著性差異。圖2 給出了所有算法在不同評價指標上的比較，坐標軸畫出了各種算法的平均排序，并且坐標軸上的數字越小則表示平均排序越低，相同顏色線段連接則表示兩種算法性能沒有顯著差異。根據式（35）可計算出CD值為2.205 2。

對某個任意算法，都有30個結果作為對比（在5個評價指標上具有6個對比算法），通過圖2 可以得出：（1）MIMLFE 在5個評價指標上與其他6個對比算法相比時排序均為第一。（2）在Hamming Loss、Coverage 和Ranking Loss 三個評價指標上，MIMLFE與MDDMp 和MVMD 均無顯著性差異，但均優于OS、MLSI、PCA、wMLDA。（3）在One-Error 評價指標上，MIMLFE 優 于OS、MLSI、PCA。（4）在Average Precision 指標上，MIMLFE 與MDDMp 取得了相當的性能，但均優于其他所有對比算法。

Fig.1 AP trend chart圖1 AP 趨勢圖

5 總結

Fig.2 Performance comparison of algorithms圖2 算法性能比較

特征提取是針對處理高維數據進行降維的一種有效方法。主成分分析（PCA）和特征標記依賴度（MDDM）是減少多標記維度的兩種有效的多標記特征提取技術，前者已經與最小二乘法相關聯。在本文中，利用核極限學習機自編碼器，將原始的特征空間與標記空間融合重構，得到新的特征空間。然后推導出具有正交投影方向的MDDM 的最小二乘公式，利用線性組合方式組合這兩個最小二乘公式，從而構建一種新穎的多標記特征提取方法，分別提取“特征-特征”“標記-特征”的信息以最大化特征方差和特征標記依賴性。實驗結果表明了本文提出的MIMLFE 算法具有不錯的效果和較好的穩定性。