基于類屬特征和依賴標記的多標記分類算法

秦夢瑩，秦鋒

（安徽工業大學計算機科學與技術學院，馬鞍山243000）

0 引言

隨著信息技術的迅速發展，互聯網中存在著大量的多標記數據，如何高效地處理這些多標記數據是當前研究的熱點問題。傳統的單標記監督學習框架在處理這些多標記數據時難以取得很好的效果，基于此多標記學習框架應運而生。現如今多標記分類問題作為多標記學習研究的主要問題被廣泛運用于各個領域，如信息檢索、文本分類、圖像識別、生物信息學、音樂情感分類等。

在多標記分類問題中，數據的特征維度通常會影響到算法的最終分類性能，冗余和不相關的特征不僅會降低分類器的精度，而且會導致算法運行的速度變慢。多標記特征選擇技術是解決數據特征維度過高的一種有效方法，特征選擇是指從原始特征空間選擇出最小的特征子集并且不改變原始特征空間信息，當前一些多標記特征選擇方法通常使用標記與特征之間的互信息[1-5]作為評判相關特征的標準，根據閾值設定以刪除不相關的特征。但上述多標記特征選擇方法并沒有利用類屬特征[6]的概念以進行特征選擇，類屬特征是指與每個標記最相關、對該標記最具有判別能力的特征，例如可以認為特征“氣溫”、“海拔”是類別標記“高原”的類屬特征，特征“音色”、“頻率”可作為類別標記“鳥聲”的類屬特征，構造類屬特征以進行特征選擇可以有效緩解決數據特征維度過高的問題，與傳統多標記特征選擇方法相比基于類屬特征的多標記學習方法則更充分考慮了標記與特征之間的聯系。

類別標記之間往往不是相互獨立的，而是存在一種相互依賴的關系，依賴關系反映了標記之間的相關性，如在圖像標注中，標記“大海”和“沙灘”則可稱之為依賴標記，一篇體育類文檔，標記“運動員”、“比賽”和“排名”也可構成依賴標記。現有多標記分類學習算法根據標記相關性程度可以被分為三大類[7]：“一階”策略，“二階”策略，“高階”策略。“一階”策略是指將多標記分類問題分解為與類別標記個數相同的多個二元分類問題，對每一個類別標記都訓練各自的分類器，典型的“一階”策略算法如二元關聯算法（Binary Relevance，BR）[8]，基于K近鄰的多標記算法[9]，“一階”策略算法的時間復雜度與數據集的標記數量呈正比，“一階”策略雖然概念簡單但忽視了標記之間的相關性。“二階”策略考慮了標記之間的成對關聯性，典型的“二階”策略算法如校準標記排序算法（Calibrated Label Ranking，CLR）[10]利用每個示例的相關標記與無關標記的排序關系求解多標記分類問題，但在實際應用中，標記相關性往往超出了二階假設。“高階”策略則充分考慮了所有類別標記之間的全局相關性來解決多標記學習任務，如文獻[11]提出了集成鏈式分類器方法通過構造多條鏈式分類器以考慮標記全局相關性，但高階模型通常復雜度較高且存在誤差傳播問題。

針對上述問題，本文提出了一種基于類屬特征和依賴標記的多標記分類算法（Multi-label Classification Algorithm Based on Class-specific Features and Depen?dent Labels，CFDL），CFDL算法的主要貢獻如下：

（1）通過構造標記的類屬特征集以去取冗余或不相關的特征。

（2）根據依賴標記之間的相關性，構造基于標記高階相關性的分類模型。

（3）在測試階段通過類屬特征與依賴標記之間的聯系以生成預測標記，從而無需借助外部分類器進行分類預測。

（4）對比實驗結果表明CFDL算法在處理多標記分類問題的優越性。

1 相關工作

類屬特征反映的是每個標記最相關最具判別性的特征，因此構造類屬特征有助于確定每個示例的相關標記集合。文獻[12]通過聚類集成技術考慮標記關聯性以生成類屬特征，文獻[13]使用線性回歸模型從非稀疏場景中提取數值型標記的類屬特征以構建更具競爭性的多標記分類器，文獻[14]則提出將l1范數與l2,1范數結合同時對特征空間到標記空間的投影矩陣作正則約束，用以提取共享特征和類屬特征，文獻[15-16]則結合類屬特征和局部標記相關性用于處理類不平衡問題。在構建類屬特征的過程中可能會致使特征空間產生冗余信息，文獻[17]提出利用模糊粗糙集對類屬特征約簡以降低類屬特征的維數，文獻[18]通過綜合利用隨機子空間模型及成對約束降維思想提取更有效的特征信息。

鏈式分類器（Classifier Chain，CC）[11]是一種常見的鏈式多標記分類方法，與BR方法不同的是鏈式分類器考慮了標記之間的相關性，CC方法將多標記分類問題被轉化為多個二元分類器鏈，且前一個分類器的標記輸出結果將作為后一個分類器的附加輸入信息，因此鏈式分類器也常被用于構建標記高階相關性模型。如文獻[19]提出構造多條環形分類器鏈用于解決CC方法中標記順序影響分類性能的問題。文獻[20]提出構造樹形結構的分類器鏈用于搜索標記的相關特征子集。文獻[21]則將鏈式分類模型用于處理元標記（meta-la?bel）的分類預測。鏈式方法通常只捕獲標記之間的部分依賴關系，堆疊方法（stacking）則可以在將冗余度引入特征空間的同時，捕獲標記的完全依賴性。如文獻[22]提出的修剪可信堆疊方法可以使多個分類器鏈在測試階段并行運行，同時通過計算所有所有成對標記的信息增益值來刪除低于給定閾值的不必要標記依賴關系。文獻[23]提出的基于帕累托最優（Pareto Opti?mum）的堆疊模型選擇出最相關的標記子集再進行標記預測，最終在測試階段使用選定的標記子集和擴展特征得到預測結果。文獻[24]提出以堆疊稀疏方式學習類屬特征和依賴標記學習了依賴標記之間的高階相關性。鏈式方法和堆疊方法雖然能有效反映類別標記的全局相關性，但由于結構的特殊性也會導致誤差傳播問題，例如前一個分類器的預測錯誤將會沿鏈傳播到下一個分類器或者上一層的分類預測錯誤會影響到下一層的分類預測。

本文提出的CFDL算法將通過l1范數正則約束構造稀疏的類屬特征集，同時為避免高階多標記分類算法因使用外部分類器而導致誤差傳播問題，CFDL算法將根據類屬特征和依賴標記之間的聯系以生成預測標記。

2 CFDL算法

2.1 多標記分類問題的相關定義

令X=Rd表示d維特征空間，表示q維標記空間，給定一個包含n個樣本的多標記數據集，其中表示特征向量，表示標記向量，如果第i個示 例xi含有 標記yj，則yij=1，否則yij=0，令X=[x1,x2,…,xn]T∈Rn×d表示輸入數據，Y=[y1,y2,…,yn]T∈Rn×q表示真實標記集合。

2.2 類屬特征和依賴標記

類屬特征應當是每個標記最相關、最具判別性的特征，因此標記的類屬特征集中所包含的特征個數應遠小于原始特征空間的特征數目，使用表示特征空間到標記空間對應的類屬特征矩陣為第j個標記所含有的類屬特征中的非零元素則說明該特征可作為標記j的類屬特征，否則不是標記j的類屬特征，通過構造類屬特征集可以有效解決數據特征維度過高的問題。

通常認為關聯性很強的標記之間比關聯性較弱的標記之間存在更多相同的類屬特征，因此挖掘標記之間的關聯性將會有助于類屬特征的提取，把關聯性很強的標記稱之為依賴標記，令表示依賴標記矩陣，表示與第j個標記相關的所有依賴標記中的非零元素表示兩個標記之間構成依賴標記中的零元素則說明兩個標記之間關聯性較弱或者不相關，Wy的提出可以反映標記集中所有標記之間的相互依賴關系。

采用最小二乘作為損失函數用來判斷預測值與真實標記之間的誤差，得到的優化問題如下：

在測試階段輸出標記Y需使用現有的分類器得出，如果使用額外的分類器進行標記預測可能會出現誤差傳播的問題，從而降低算法的分類性能，為避免上述問題，可將目標函數中的輸出標記矩陣Y視為一個變量并改寫為其他形式，令l表示式（1）所示的損失函數，由，可得，其中I∈Rq×q為對角線元素全為1的單位矩陣,使得測試階段的輸出標記可由類屬特征矩陣和依賴標記矩陣確定，由此得到的優化問題如下：

考慮到并不是所有類屬特征和標記依賴關系都有助于提升算法性能，因此需要對類屬特征矩陣和依賴標記矩陣使用l1范數正則化以去除冗余的類屬特征和依賴標記，最終獲得較為稀疏的類屬特征矩陣Wx和依賴標記矩陣Wy，即讓Wx和Wy獲得盡可能多的零元素，得到的基于標記高階相關性的線性分類模型如下：

其中λ3、λ4為非負權衡參數。

令C∈Rq×q表示標記相似度矩陣，標記之間的相關性程度可由余弦相似度計算（cosine similarity），余弦值越大，說明兩個標記越相似，即標記的關聯性越強，使用ci,j表示矩陣C中任意兩個標記yi和yj之間的余弦相似度則標記空間中任意兩個標記之間的相關性可通過獲得，任意兩個標記之間的類屬特征共享性可通過獲得，由此得到的優化問題如下：

其中λ1，λ2為非負權衡參數，令:

因此可將（4）式寫為如下優化問題：

由此可得CFDL算法的優化問題如（5）式所示，其中λ1≥0，λ2≥0，λ3≥0，λ4≥0為權衡參數，λ1控制標記與特征之間的關聯性，λ2控制標記之間的關聯性，λ3控制類屬特征的稀疏性，λ4控制依賴標記的稀疏性，待求解的Wx∈Rd×q為類屬特征矩陣，Wy∈Rq×q為依賴標記矩陣。

3 優化求解

（5）式中由于l1范數正則項的引入，導致目標函數的非平滑性，提出了算法1采用加速近端梯度方法（Accelerated Proximal Gradient）求解該非平滑凸優化問題，令F(·,·)表示（6）式如下所示：

代替直接最小化F(·,·)，可將F(·,·)分成兩部分f(·,·)和g(·,·)求解：

H為希爾伯特空間（Hilbert space），其中f(·,·)和g(·,·)分別表示如下：

利用可分二次逼近法（Separable Quadratic Approxi?mations）求解（10）式可得到（6）式的解：

其中Lf為利普希茨常數（Lipschitz constant），根據文獻[25]Lf可由線性搜索策略獲得。和分別為Wx和Wy的第t次迭代。

3.1 更新Wx

由（11）式對Wx求梯度可得：

根據文獻[25]中加速近端梯度的求解方法，以如下形式更新表示Wx的第t次迭代，其中αt滿足由線性搜索策略獲得。

Wx以如下方式優化：

考慮到（15）式中l1范數正則項的存在，可對Wx中的每一個元素分別執行軟閾值函數作進一步處理，令proxε()?表 示 軟 閾 值 函 數，wij∈R，且ε>0，()?+=max(?,0)，則proxε()?定義如下：

3.2 更新Wy

令A2=XWx，則（8）式可寫為：

由（18）式對Wy求梯度可得：

根據文獻[25]中加速近端梯度的求解方法，以如下形式更新表示Wy的第t次迭代。

其中αt滿足由線性搜索策略獲得。

Wy以如下方式優化：

算法1 CFDL算法優化求解

4 實驗分析

4.1 數據集與對比算法

為驗證CFDL算法分類預測的有效性，本文將在六個不同規模的多標記數據集（http://mulan.sourceforge.net/datasets.html）上與ML-KNN、MLSF、LIFT、LLSF-DL四種多標記分類算法進行對比實驗，數據集的具體信息如表1。

表1 多標記數據集

對比算法的具體實驗信息如下：

（1）ML-KNN[9]：ML-KNN算法將傳統的K近鄰算法引入多標記學習，根據未知示例的相鄰示例標記集來獲得該示例可能的所屬類別信息，最后利用最大后驗概率確定未知示例的標記集。近鄰個數k∈{8,9,10,11,12}，平滑參數s=1。

（2）LIFT[6]：LIFT算法首先對每個標記的正類樣本和負類樣本分別進行聚類分析，由此來構造每個標記的類屬特征，然后為每個標記來訓練二元分類模型。比率參數r∈{0.1,0.2,0.3,0.4,0.5}。

（3）MLSF[21]：MLSF算法首先通過標記間的依賴關系構造元標記（meta-label），其次為每個元標記選擇所屬的類屬特征，最后構造鏈式結構的分類器以進行標記預測。參數設置K∈{2,4,6,8,10,12,14,16}，γ∈{0.001,0.01,0.1,1}。

（4）LLSF-DL[24]：LLSF-DL算法以堆疊稀疏的方式學習依賴標記的高階相關性用于處理多標記分類問題。權衡參數α,β,γ∈{4-5,4-4,…,45}，ρ∈{0.1,1,10}。

（5）CFDL：本文提出的基于類屬特征和依賴標記的多標記分類算法，利用類屬特征和依賴標記之間的聯 系 以 獲 得 預 測 標 記。權 衡 參 數λ1,λ2∈{100,101,…,105}，λ3,λ4∈{10-1,100,…,104}。

4.2 評估指標

（1）Subset Accuracy：考察標記子集的準確率，對于給定的多標記樣本如果預測標記集與真實標記集相同返回1，否則返回0，該評估指標的值越大表示系統性能越優。

（2）F1 measure：F1評估指標考察的是每個樣本精確率和召回率的加權平均，該評估指標的值越大表示系統性能越優。

其中pi和ri分別表示第i個樣本的精確率和召回率。

（3）Micro F1：F1微平均考察的是總體樣本的F1分數，該評估指標的值越大表示系統性能越優。

（4）Macro F1：F1宏平均考察的是每個標記精確率和召回率的加權平均，該評估指標的值越大表示系統性能越優。

其中pi和ri分別表示第i個樣本的精確率和召回率。

4.3 實驗結果分析

對于每個數據集，每次實驗隨機抽取80%的樣本作為訓練集，剩余的20%作為測試集，觀察每種多標記算法在不同數據集上的性能表現，重復實驗10次取平均值作為實驗結果，最終的實驗結果如表2-表5所示，粗體表示最優的算法結果，↑表示該評價指標的值越大算法性能越優。

本文通過Nemenyi檢驗對比各算法在不同評價指標上的相對性能排名，結果如圖1所示。Nemenyi檢驗反映的是不同算法之間的性能差異大小，如果任意兩個算法的在評估指標上平均排名大于臨界差異值（Critical Difference，CD），則認為兩個算法之間的性能差異較明顯，k為算法個數，N為數據集個數，在顯著水平α=0.05的情況下查表得qα=2.728，由此計算出CD值為2.4903（k=5,N=6），圖1中紅線連接的算法表示在該評價指標下性能差異不明顯，未連接紅線表示算法性能差異明顯。觀察表2-表5及圖1可以看出，CFDL算法在六種不同數據集上都取得了不錯的分類效果，其中在Subset Accuracy評估指標上CFDL算法與LLSF-DL算法、MLSF算法性能差異并不明顯，但優于ML-KNN算法，在F1 measure、Micro F1和Macro F1評估指標上CFDL算法均處于性能平均排名第一位。與一階算法ML-KNN、LIFT相比CFDL算法充分考慮了標記之間的關聯性，與高階算法MLSF和LLSF-DL相比CFDL算法在測試階段可以通過類屬特征矩陣和依賴標記矩陣直接獲得輸出標記，避免了高階算法在使用外部分類器導致的誤差傳播問題，這也在一定程度上提升了CFDL算法的分類性能。

表2 對比算法在Subset Accuracy上的實驗結果

表3 對比算法在F1 measure上的實驗結果

表4 對比算法在Micro F1上的實驗結果

表5 對比算法在Macro F1上的實驗結果

圖1 使用Nemenyi檢驗分析（α=0.05）CFDL算法與其他算法的性能差異

4.4 參數分析

由目標函數（5）式可知，權衡參數λ1控制標記與特征之間的關聯性，λ2控制標記之間的關聯性，λ3控制類屬特征的稀疏性，λ4控制依賴標記的稀疏性。以數據集enron為例，參數設置的最優值為λ1=103，λ2=103，λ3=102，λ4=103，在參數敏感性實驗中每次實驗只變化其中一個參數，以最優值固定另外三個參數，觀察CFDL算法在不同評價指標上的分類性能隨參數變化情況，其中λ1和λ2的搜索范圍為{100,101,…,105}，λ3和λ4的 搜 索 范 圍 為{10-1,100,…,104}。由圖2（a）可知，當λ1過小時，四種評價指標的值會減小為0，由圖2（b）和圖2（d）可知，變化λ2和變化λ4對分類性能影響不大，由圖2（c）可知，當λ3過大時，四種評價指標的值會迅速減小為0。

5 結語

CFDL算法通過構造類屬特征集和依賴標記集以進行多標記分類任務，同時針對“高階”策略可能存在的誤差傳播問題，CFDL算法在測試階段無需借助外部分類器即可生成預測標記，多個數據集上的實驗結果也反映了CFDL算法分類的準確性與有效性。今后將對類屬特征集與依賴標記集的構造作進一步研究。

圖2 參數敏感性分析