秦夢瑩，秦鋒

（安徽工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，馬鞍山243000）

0 引言

隨著信息技術(shù)的迅速發(fā)展，互聯(lián)網(wǎng)中存在著大量的多標記數(shù)據(jù)，如何高效地處理這些多標記數(shù)據(jù)是當(dāng)前研究的熱點問題。傳統(tǒng)的單標記監(jiān)督學(xué)習(xí)框架在處理這些多標記數(shù)據(jù)時難以取得很好的效果，基于此多標記學(xué)習(xí)框架應(yīng)運而生。現(xiàn)如今多標記分類問題作為多標記學(xué)習(xí)研究的主要問題被廣泛運用于各個領(lǐng)域，如信息檢索、文本分類、圖像識別、生物信息學(xué)、音樂情感分類等。

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

類別標記之間往往不是相互獨立的，而是存在一種相互依賴的關(guān)系，依賴關(guān)系反映了標記之間的相關(guān)性，如在圖像標注中，標記“大?！焙汀吧碁眲t可稱之為依賴標記，一篇體育類文檔，標記“運動員”、“比賽”和“排名”也可構(gòu)成依賴標記?，F(xiàn)有多標記分類學(xué)習(xí)算法根據(jù)標記相關(guān)性程度可以被分為三大類[7]：“一階”策略，“二階”策略，“高階”策略?！耙浑A”策略是指將多標記分類問題分解為與類別標記個數(shù)相同的多個二元分類問題，對每一個類別標記都訓(xùn)練各自的分類器，典型的“一階”策略算法如二元關(guān)聯(lián)算法（Binary Relevance，BR）[8]，基于K近鄰的多標記算法[9]，“一階”策略算法的時間復(fù)雜度與數(shù)據(jù)集的標記數(shù)量呈正比，“一階”策略雖然概念簡單但忽視了標記之間的相關(guān)性?！岸A”策略考慮了標記之間的成對關(guān)聯(lián)性，典型的“二階”策略算法如校準標記排序算法（Calibrated Label Ranking，CLR）[10]利用每個示例的相關(guān)標記與無關(guān)標記的排序關(guān)系求解多標記分類問題，但在實際應(yīng)用中，標記相關(guān)性往往超出了二階假設(shè)?！案唠A”策略則充分考慮了所有類別標記之間的全局相關(guān)性來解決多標記學(xué)習(xí)任務(wù)，如文獻[11]提出了集成鏈式分類器方法通過構(gòu)造多條鏈式分類器以考慮標記全局相關(guān)性，但高階模型通常復(fù)雜度較高且存在誤差傳播問題。

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

（1）通過構(gòu)造標記的類屬特征集以去取冗余或不相關(guān)的特征。

（2）根據(jù)依賴標記之間的相關(guān)性，構(gòu)造基于標記高階相關(guān)性的分類模型。

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

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

1 相關(guān)工作

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

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

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

2 CFDL算法

2.1 多標記分類問題的相關(guān)定義

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

2.2 類屬特征和依賴標記

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

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

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

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

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

其中λ3、λ4為非負權(quán)衡參數(shù)。

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

其中λ1，λ2為非負權(quán)衡參數(shù)，令:

因此可將（4）式寫為如下優(yōu)化問題：

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

3 優(yōu)化求解

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

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

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

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

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

3.1 更新Wx

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

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

Wx以如下方式優(yōu)化：

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

3.2 更新Wy

令A(yù)2=XWx，則（8）式可寫為：

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

根據(jù)文獻[25]中加速近端梯度的求解方法，以如下形式更新表示W(wǎng)y的第t次迭代。

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

Wy以如下方式優(yōu)化：

算法1 CFDL算法優(yōu)化求解

4 實驗分析

4.1 數(shù)據(jù)集與對比算法

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

表1 多標記數(shù)據(jù)集

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

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

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

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

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

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

4.2 評估指標

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

（2）F1 measure：F1評估指標考察的是每個樣本精確率和召回率的加權(quán)平均，該評估指標的值越大表示系統(tǒng)性能越優(yōu)。

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

（3）Micro F1：F1微平均考察的是總體樣本的F1分數(shù)，該評估指標的值越大表示系統(tǒng)性能越優(yōu)。

（4）Macro F1：F1宏平均考察的是每個標記精確率和召回率的加權(quán)平均，該評估指標的值越大表示系統(tǒng)性能越優(yōu)。

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

4.3 實驗結(jié)果分析

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

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

表2 對比算法在Subset Accuracy上的實驗結(jié)果

表3 對比算法在F1 measure上的實驗結(jié)果

表4 對比算法在Micro F1上的實驗結(jié)果

表5 對比算法在Macro F1上的實驗結(jié)果

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

4.4 參數(shù)分析

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

5 結(jié)語

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

圖2 參數(shù)敏感性分析