基于類別一致性的層次特征選擇算法

張智慧 ,林耀進 ,張小清 ,呂 彥

（1.閩南師范大學計算機學院,福建漳州 363000；2.數據科學與智能應用福建省高等學校重點實驗室,福建漳州 363000）

在信息時代，隨著數據量的增加，分類問題的規模變得越來越大，給分類算法的效率和準確率帶來了嚴峻挑戰[1].例如，在文獻[2]中，數百萬的圖像樣本包含數千個類別，每個樣本由數百萬個特征描述，導致特征空間具有高維性.特征選擇是處理分類學習特征維度災難的重要技術.目前已有大量工作致力于研究利用特征選擇解決特征空間高維性問題.Lin 等[3]引入模糊互信息評價多標簽學習中的特征重要度，設計相關算法進行特征選擇.Peng 等[4]研究如何根據基于相互信息的最大統計依賴性準則來選擇好的特征.然而隨著分類學習中類別數量的迅速增加，在大規模類別條件下的層次分類學習比傳統的平面分類學習面臨更加嚴重的維度災難問題.因此，對于層次分類的特征選擇問題的研究具有重要意義.

近年來，針對層次數據的特征選擇方法也越來越受到關注.Freeman 等[5]使用遺傳算法優化分類問題，使層次分類器中的基分類器都能獲取各自最優特征子集.Grimaudo 等[6]為層次數據集的每一層節點選擇的不同特征子集，降低特征維數，提高分類任務的準確性.Zhao 等[7]利用類別相關性關系，將父類和兄弟類之間的關系作為正則化項去評估特征的重要性，為層次樹結構的每個節點選擇不同的特征子集.但在實際應用中，類別的層次結構不僅表示成一個簡單的樹結構，通常是一個更廣義的有向無環圖結構，而上述算法對于有向無環圖結構的數據進行特征選擇存在一定挑戰.

在層次圖結構中，一個類別可能同時屬于一個或多個父類，因此層次分類學習也可以轉化成特殊的多標簽或多輸出學習[2].在多標簽分類特征選擇的算法中，標簽相似度和特征的權重矩陣有著緊密的聯系，并基于此有大量的研究成果.在算法LLSF[8]中，假設任何兩個強相關性的類標簽比兩個不相關或弱相關的類標簽共享更多的特征，同時特征的權重系數向量之間有極大相似性.Ren 等[9]提出LDLSF 算法，指出如果兩個標簽即使是強相關的，它們應該在標簽上有相似的輸出，而不僅體現在它們的特征權重參數向量上.上述算法雖然能有效解決傳統多標記問題中的類別差異問題，但在層次類結構中，兩個類別較為相似時，所選特征也會存在較大差異，出現不一致問題，而且子節點比父節點的類別更加具體化.因此，只考慮特征權重相似性選擇特征子集是不夠的，可以進一步考慮樣本的類別一致性來減小所選特征的誤差問題.

基于上述思想，本文將分類直接限制在類別的標簽輸出上，而不是只考慮類別的特征權重系數的相似性，減少不一致性產生的分類誤差.利用類別之間的層次結構，充分考慮節點類別與其祖先節點類別、兄弟節點類別之間的關系，獲得更準確的特征子集，提高分類精度.因此，本文提出一種基于類別一致性的層次特征選擇算法HierASFC(A Hierarchical Feature Selection Algorithm Βased on the Consistency of Categories).首先，基于類別的層次結構，利用遞歸正則化計算內部每個子類別的相似度，得到一個相似度矩陣，構建特征權重損失函數，學習層次結構中每個子類別的共同特征；其次，考慮到類別與各自的父類、兄弟類以及區別特征之間的依賴關系，根據輸出一致性直接在樣本的類別上約束標簽的相關性；最后，對樣本特征進行稀疏性學習去除無關特征并在樹結構和有向無環圖結構的層次數據中進行大量實驗，驗證該算法的有效性.

綜上，本文主要內容安排如下：1）介紹相關基礎知識；2）設計基于類別一致性的層次特征選擇算法模型；3）描述所提出算法的實驗結果并進行分析；4）對本文工作進行總結.

1 特征選擇

給定X∈Rn×m為一個數據矩陣，Y∈Rm×d是一個類別矩陣，其中n和m分別為樣本數和特征的數量，d是類別數量.

特征選擇，即選擇一個足以充分預測目標類別標簽的特征子集.許多特征選擇算法將數據矩陣X和類別標簽Y的關系表述為一個線性優化問題：

其中：W是特征權重矩陣，L(·)是經驗損失函數；R([W])是對W施加的正則約束項；λ是一個正常數.

公式(1)的目標是學習得到一個合適的W，使實際的類別矩陣Y與預測的XW之間的差值最小，重構后的矩陣XW能夠近似表示原始的數據矩陣X.

2 基于類別一致性的層次特征選擇算法

2.1 層次分類學習

在層次分類學習任務中，通常分為樹結構和有向無環圖結構[10]，樹狀結構可以看作是一種特殊的有向無環圖結構.首先將數據中樣本集X劃分為X0,X1,…,XN，同時令Y0,Y1,…,YN表示為對應的標簽類別集合，其中，且，dmax是內部節點中類別數目的最大值,類別層次結構的內部節點數為N+1.令表示為內部節點i的權重矩陣，則可構建經驗損失項L(Xi,Wi,Yi)學習內部節點i的所有特征，同時考慮到節點間存在共同特征，將其作為正則項包含于Γ(Wi)中，最后為保證特征的稀疏性，加入稀疏性正則項，因此目標函數表述如公式(2)所示：

其中：W0,W1,…,WN分別為根節點和每個中間節點的特征權重矩陣.

2.2 HierASFC算法設計

在層次類別結構中，每個祖先類別和其后代擁有共同特征，同一層次的兄弟類別也會包含各自祖先類別的共同特征.因此，類別的繼承性體現了類別之間的一致性，而類別一致的標記之間其特征應擁有更多共同特征.本文對類別的層次結構進行分析得到類別間的相似度矩陣，通過矩陣構造特征權重損失函數去學習每個類別的共同特征.如果類別yi和類別yj越相似，那么二者的特征權重Wi和Wj就越相似，即擁有的共同特征越多.因此，相似度矩陣和分類的一致性需要一起考慮.利用相似度矩陣構造特征損失函數，學習層次結構中各子樹類別的輸出相似度.輸出一致性關系的正則項可以構造如下公式(3)：

其中：Cij=1-Sij，Sij表示為各類別yi與其他類別yj相似度，且S∈RN×N.

利用二元關聯將層次分類問題轉化為基于類別層次結構的多標簽學習問題，用余弦相似度計算節點類別的相似度.目標函數(3)可通過控制參數α的大小達到最小化.對于所有節點特征的學習，基于公式(2)，本實驗采用最小二乘損失作為損失函數并學習l2,1范數加入稀疏學習的正則化項得到最終目標函數，如公式(4)所示：

其中：λ和α為兩個非負參數，分別控制著特征的稀疏性和輸出一致性的學習.

2.3 模型優化

因為l2,1范數的非光滑性，按照文獻[11]中提供的解決方法，對公式(4)中||W||2,1對W的求導計算如公式(5)所示：

對于各個內部節點，根據公式(6)求出關于Wi的導數并設置為0，由此可以求得Wi如公式(7)所示：

計算特征的權值矩陣W=[W0,W1,…,WN]，并進行升序排序，選擇較大權重值的特征，完成每個節點的特征選擇任務.

3 實驗結果與分析

在本節中，首先介紹在實驗中使用的數據集，然后分析參數的敏感性和正則化項的有效性，最后將所提出的算法與一些先進的算法進行比較分析.

3.1 實驗數據集

為測試所提出的算法，本文選擇10 個數據集，其中6 個是樹狀結構數據集.具體是蛋白質數據集DD[11]、F194[12]，圖像數據集VOC[13]、ILSVRC65[14]、SUN[15]和Cifar[7]，4 個有向無環圖結構的基因數據集，分別是Eisen，Derisi，Cellcycle，Gasch[16].具體信息如表1所示.

表1 數據集描述Tab.1 Data Description

3.2 評價指標和對比算法

在實驗中，采用Tree Induced Error(TIE)[17]和Hierarchical-F1 measure(H-F1)[18]兩個層次分類評價指標.其中TIE的取值越小說明實驗準確率越高，誤差越小，而Hierarchical-F1 measure的取值越大則說明算法表現越好.并且引入Friedman檢驗方法[19]和Βonferroni-Dunn檢驗方法[20]更加直觀地比較各算法的分類性能.

為有效驗證HierASFC 算法的性能，本文將該算法與五種層次特征選擇算法進行比較.具體信息如下：

1）HierMRMR[6]是一種基于mRMR的層次特征選擇方法，為每個子分類器選擇不同的特征集；

2）HierFisher是一種由Fisher score[18]改進而來的層次特征選擇方法；

3）HierFSNM是一種由FSNM[18]改進而來的層次特征選擇方法；

4）Hier-FS[7]是分層特征選擇方法，考慮層次中的兄弟節點關系，加入正則化項，提高分類精度；

5）HiRRfam-FS[7]是分層特征選擇方法，考慮父子節點關系和兄弟節點關系，為內部每個節點選擇不同的特征子集進行分類.

3.3 參數分析

對于Hier-FS 算法的參數依據文獻[7]將λ設為10，HiRRfam-FS 算法依據文獻[8]將參數α和β設為1.在本實驗中，同樣采用線性支持向量機(LSVM)作為基分類器，對于HierASFC 算法兩個參數λ和α，在樹結構和有向無環圖結構中通過網格{0.001，0.01，0.1，1，10，100，1 000}搜索最優值.分別列出樹結構的VOC數據集與圖結構的Eisen數據集，取20%的特征，計算不同參數所得的H-F1值.從圖1的結果可以看出當λ=10 時，H-F1 值比較穩定且數值較大，僅次于λ=1；從圖2 的結果可以看出，當λ=1 時在DD 數據集上的H-F1 值較差于λ=10，因此針對樹結構的數據集，參數λ設為10 可以得到較好的平均實驗效果，參數α設為0.01時的H-F1值也較大；從圖3的結果可以看出，針對有向無環圖結構的數據集，λ取100時，H-F1值比較穩定且數值較大，因此參數λ設為100，參數α設為0.01.

圖1 VOC數據集的不同參數對應的Hierarchical-F1 measure值Fig.1 Hierarchical-F1 measure values for different parameters on the VOC dataset

圖2 DD數據集的參數α對應的Hierarchical-F1 measure值比較Fig.2 Comparison of Hierarchical-F1 measure values for the parameters α on the DD dataset

圖3 Eisen數據集的不同參數對應的Hierarchical-F1 measure值Fig.3 Hierarchical-F1 measure values for different parameters on the Eisen dataset

3.4 實驗結果與分析

3.4.1 在樹結構數據上的性能分析

基于LSVM 分類器，本文在選擇相同比例特征所需的時間，TIE 和H-F1(Hierarchical-F1)兩個層次分類評價指標將本文算法與對比算法進行比較，實驗結果如表2所示，表3和表4中加粗部分表示實驗最優結果；“↑”表示取值越大越好，“↓”表示取值越小越好，每個算法的平均性能用斜體表示.

表2 運行時間(s)Tab.2 Running time(s)

表3 6種算法在不同數據集上的TIE歸一化結(↓)Tab.3 TIE normalization results of 6 algorithms on different datasets(↓)

表4 6種算法在不同數據集上的H-F1結果(↑)Tab.4 H-F1 results of 6 algorithms on different datasets(↑)

采用Βonferroni-Dunn 檢驗比較不同算法之間的分類性能差異，計算出平均值序值差別的臨界值域，在顯著性水平α=0.1 下，有qα=2.326，因此可計算出CD=2.512(k=6,N=6).圖4 結果表明，HierASFC算法的H-F1值在統計上明顯優于其他算法，具有較好的實驗性能.

圖4 HierASFC算法與其他算法的性能比較Fig.4 Performance comparison of HierASFC algorithm against the others

3.4.2 在圖結構數據上的性能分析

基于LSVM 分類器，對不同層次特征選擇算法的分類性能進行評估.結果如圖5所示.

圖5 圖結構的Hierarchical-1值Fig.5 Hierarchical-F1 measure evaluation of graph structure

同樣采用Βonferroni-Dunn 檢驗來準確比較不同算法性能差異，圖6 結果表示，在包含有向無環圖結構的數據集上，HierASFC算法有更好的穩定性.

圖6 HierASFC算法和其他算法在選擇不同的特征數量上的性能比較Fig.6 The performance of HierASFC and other algorithms in selecting different number of features

3.4.3 HierASFC的收斂性分析

在實驗中，本文設定所有數據集的最大迭代數T=10.從圖7中可以看出，10個數據集的目標函數值都是處于單調下降狀態，在迭代2次范圍內快速下降并趨于收斂；在不超過10次的迭代次數中達到收斂，這證明HierASFC算法的收斂性較好，極大縮短分類時間，分類效率極大提高.

圖7 目標函數的收斂圖Fig.7 Convergence diagrams of the objective function

4 結語

本文提出一種基于層次類別一致性的層次特征選擇算法HierASFC.該算法充分利用類別的層次結構所提供的信息，為每個節點選擇不同的特征子集，并且能夠同時處理具有樹結構和有向無環圖結構數據集.在實驗部分，與5種層次特征選擇算法作對比，結果表明本文算法在各個評價指標中均取得較優的結果.