蔡 劍 牟甲鵬 余孟池 徐 建

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

傳統(tǒng)的分類學習處理一個實例與單個類別標簽相關(guān)的問題。但是在現(xiàn)實世界中，一個實例可能會具有多個類別標簽。例如，一張圖片可能會被標注上多個關(guān)鍵詞；一篇文章可能屬于多個主題；一個基因也可能與多個功能相關(guān)。為了表達這些對象擁有的多重語義，經(jīng)常使用一個標簽子集代替單個標簽來標識該對象，這類使用標簽子集來表達對象語義的學習模式稱為多標簽學習。多標簽分類的目標就是為具有多重語義的對象建立分類模型，讓該模型可以有效預(yù)測未知實例的相關(guān)標簽子集。

解決多標簽分類問題最經(jīng)典的方法是BR（Bi?nary Relevance）算法［1］，BR將多標簽分類問題轉(zhuǎn)換成多個二分類問題，為每個標簽分別訓練一個二分類器，最后綜合多個分類器結(jié)果作為最終的預(yù)測結(jié)果。BR算法具有簡單直接的優(yōu)點，但是也存在一些問題。Zhang等［2］提出標簽相關(guān)性（label correla?tion）的概念，即標簽間通常存在依賴關(guān)系，指出BR算法未考慮標簽性的問題；Wu等［3］提出類屬屬性（label-specific feature）的概念，即每個標簽具有其特有的屬性特征，指出BR算法存在冗余屬性的問題。

為了解決BR算法存在的冗余屬性問題，現(xiàn)有的改進工作主要有兩種：特征選擇和特征轉(zhuǎn)化。特征選擇的目的是從原始特征空間中篩選出與標簽相關(guān)性強的屬性特征。相關(guān)算法有Qu等提出的MLSF算法［4］，該算法分別為正、負例集計算特征密度，以此作為特征選擇的指標。特征轉(zhuǎn)化的目的是將原始特征空間映射到類屬屬性空間中，相關(guān)算法有LIFT［5］和其改進算法ELIFT［6］。這些算法雖然都解決了BR算法的冗余屬性問題，但最大的問題是沒有考慮標簽相關(guān)性。

為了解決BR未考慮標簽相關(guān)性的問題，現(xiàn)有的改進工作主要分兩種［7］：鏈結(jié)構(gòu)（chaining struc?ture）和堆疊結(jié)構(gòu)（stacking structure）。鏈結(jié)構(gòu)是假定隨機的標簽相關(guān)性，每個標簽的預(yù)測僅考慮鏈之前標簽的影響。堆疊結(jié)構(gòu)是假定所有標簽的相關(guān)性，每個標簽的預(yù)測需要考慮其他所有標簽的影響。這兩種策略雖然都考慮了標簽相關(guān)性，但是未考察加入的特征與標簽間的實際關(guān)系，因此都存在冗余依賴的問題。此外，由于預(yù)測過程需要加入其它標簽的預(yù)測值，如果預(yù)測值有誤，則還會引發(fā)錯誤傳播的問題。

以上算法都只是單獨解決了BR算法的一個問題，鑒于這種情況，本文提出基于特征選擇和標簽相關(guān)性的二元關(guān)聯(lián)算法（Binary Relevance with Fea?ture selection and Label correlation，F(xiàn)LBR）。該算法先使用信息增益為每個標簽選擇與其相關(guān)的特征屬性，然后引入新的“控制結(jié)構(gòu)”（controlled struc?ture）的方式考察標簽相關(guān)性，最后為每個標簽訓練二分類器。這里的控制結(jié)構(gòu)指的是對加入特征空間的標簽進行“控制”，僅添加與預(yù)測標簽相關(guān)性強并且不容易被預(yù)測錯誤的標簽，從而解決鏈結(jié)構(gòu)和堆疊結(jié)構(gòu)中存在的無關(guān)依賴和錯誤傳播問題。實驗結(jié)果表明，該算法的預(yù)測性能明顯優(yōu)于其它的BR改進算法。

2 相關(guān)工作

2.1 多標簽問題的定義

在本文中，多標簽學習描述如下：已知X=Rd表示實體的d維特征空間，標簽空間L={y1，y2，…，yq}表示實體可能屬于的q個標簽。多標簽學習的目標是從訓練集L}中學習得到一個映射模型h:X→2L。對于每個待預(yù)測的未知實例x∈X，多標簽分類器做出預(yù)測，所得結(jié)果即為與實體x相關(guān)的標簽。

2.2 標簽相關(guān)性的利用

在改進BR算法的研究工作中，針對標簽相關(guān)性的改進是最多的，因此接下來對改進BR標簽相關(guān)性問題常用的兩種策略進行具體的介紹。

鏈結(jié)構(gòu)的算法在BR算法中考慮了標簽間鏈式的相關(guān)性，其代表算法是CC（Classifier Chains）算法［8～9］。圖1表示標簽鏈為y1，y2，y3時算法的分類預(yù)測過程，與BR算法類似，CC也會依次為每個標簽訓練分類器，但區(qū)別是CC訓練每個分類器時需要添加標簽鏈中在預(yù)測標簽前的標簽作為額外屬性。由于使用的標簽鏈順序是隨機的，算法性能會受到鏈順序的影響。因此，算法作者在CC基礎(chǔ)上使用集成學習的思想提出了ECC算法［8～9］，從而弱化標簽鏈選取對性能的影響。此外，Cheng等［10］通過計算概率分布來選擇最優(yōu)的鏈順序，提出PCC和EPCC算法。Huang等［11］通過構(gòu)建有向無環(huán)圖來尋找合適的鏈順序，提出GCC算法。

圖1 鏈結(jié)構(gòu)代表算法CC分類示例

堆疊結(jié)構(gòu)的算法在BR算法中考慮了其它所有標簽的相關(guān)性，其代表算法是DBR（Dependent Bi?nary Relevance）算法［12］。DBR算法的分類預(yù)測過程如圖2所示，需要首先用BR算法為每個標簽訓練一個二分類器作為基分類器，然后再依次為每個標簽訓練一個元分類器，元分類器的構(gòu)建需要添加其它所有標簽作為額外屬性。由于某些標簽之間并不存在依賴關(guān)系，DBR算法考慮所有標簽相關(guān)性會來帶冗余依賴的問題。針對這樣的問題，Zhang等［13］提出一種基于DBR的剪枝算法（Correla?tion-Based Pruning of DBR，CPDBR），通過計算標簽間相關(guān)性系數(shù)phi來量化標簽相關(guān)性，最后通過閾值來排除冗余依賴的影響。此外，為了解決DBR算法仍會存在的錯誤傳播問題，Alali等［14］提出Pru?Dent算法。

圖2 堆疊結(jié)構(gòu)代表算法DBR分類示例

3 本文算法

針對BR未考慮標簽相關(guān)性以及存在冗余屬性的問題，本文提出基于標簽相關(guān)性和特征選擇的FLBR算法。同時針對現(xiàn)有考察標簽相關(guān)性方法存在的冗余依賴和錯誤傳播問題，F(xiàn)LBR采用控制結(jié)構(gòu)的方式考察標簽相關(guān)性。以下是算法的具體介紹。

3.1 特征選擇步驟

FLBR算法首先需要進行特征選擇，考察標簽和特征之間的關(guān)系，從而去除冗余屬性。這里的特征選擇使用信息增益法，用信息增益來量化兩集合的相關(guān)程度，集合A、B之間的信息增益可以由式（1）計算。對于數(shù)值型的數(shù)據(jù)集需要先對數(shù)據(jù)進行離散化，這里使用基于信息熵的方法［15］進行數(shù)據(jù)的離散化。

其中，H(B)表示集合的熵，其值可以由式（2）計算。H(B|A)表示A集合發(fā)生的條件下，B集合的條件熵，其值可以由式（3）計算。

特征選擇過程中需要先用公式（1）分別計算每個特征跟標簽的信息增益值，然后根據(jù)值的大小產(chǎn)生特征排名，最后通過閾值法刪除信息增益值小于給定閾值t1的特征，留下的特征集合即為標簽的相關(guān)特征子集。這里標簽yi的相關(guān)特征集合Fi可由式（4）得到。

3.2 基分類器構(gòu)建步驟

經(jīng)過上一步驟后可以得到每個標簽的相關(guān)特征集合Fi，接下來使用該特征集合為每個標簽分別構(gòu)建基分類器h(i)←B({Fi，yi})，其中B表示二分類學習算法。

在訓練元分類器之前，需要考察每個標簽基分類器的預(yù)測性能，找出預(yù)測準確率低的標簽集合。本文將這些標簽稱為“易錯標簽”，通過去除相關(guān)標簽中的易錯標簽來避免錯誤傳播問題。

為了考察每個標簽被預(yù)測成功地難易程度，需要為每個標簽分別訓練分類器t(i)。首先從訓練集選擇一個子集Ds?D作為t(i)的訓練集，然后使用測試集DDs對分類器進行驗證。這里使用預(yù)測精確率作為評價指標，統(tǒng)計每個標簽的預(yù)測精確率pi。預(yù)測概率小于閾值t的標簽即為易錯標簽，易錯標簽集合記為Le。

3.3 元分類器構(gòu)建步驟

在元分類器的構(gòu)建階段，F(xiàn)LBR使用控制結(jié)構(gòu)的方式考察標簽相關(guān)性，避免冗余依賴的影響。這里的標簽相關(guān)性還是通過信息增益方法進行衡量，利用式（1）計算每個標簽跟其它標簽的信息增益值，標簽間的相關(guān)性小于給定閾值將會判定為無關(guān)標簽，無關(guān)標簽集合記為Lu。這里相關(guān)標簽的判定閾值仍選用式（4）中使用的t1。

經(jīng)過上面的處理后，可以得到每個標簽中的相關(guān)標簽集合Li=L-Le-Lu，結(jié)合特征選擇的結(jié)果可以得到新的特征集合為每個標簽訓練元分類器h′(i)←B(Fi')。FLBR算法的訓練過程描述如下。

算法1 FLBR算法的訓練過程

判定易錯標簽的閾值t

二分類學習算法B

輸出：為每個標簽yi訓練的兩個分類器hi，h'i

算法步驟：

1）fοr i=1tοq dο

2）根據(jù)公式（4）得到每個標簽i的相關(guān)特征集合Fi；

3）為標簽i訓練基分類器h(i)←B({Fi，yi})；

4）end for

5）對訓練集D隨機采樣得到子集Ds?D；

6）fοr i=1tοq dο

7）為每個標簽i訓練驗證分類器t(i)←B(Ds)；

8）end for

9）根據(jù)公式（5）得到易錯標簽集合ye；

10）fοr i=1tοq dο

11）根據(jù)公式（6）得到標簽新的特征集合

12）為標簽i訓練元分類器

13）end for

14）返回每個標簽的分類器(h'1，h'2，…，h'q)。

在對實例x分類時，需要先去除其特征集合中的冗余特征，得到其基分類器的預(yù)測結(jié)果。然后將每個標簽相關(guān)的正確標簽加入到特征集合中，最后獲取元分類器的最終分類結(jié)果。

4 實驗分析

4.1 數(shù)據(jù)集介紹

本文在六個多標簽基準數(shù)據(jù)集上進行實驗對比。所選數(shù)據(jù)集涉及多標簽學習的音樂標注、基因功能預(yù)測、文本分類和聲學分類四個不同應(yīng)用領(lǐng)域。表1給出了數(shù)據(jù)集的統(tǒng)計信息，這些數(shù)據(jù)集可以從http：//mulan.sourceforge.net/上獲取。

表1 實驗數(shù)據(jù)集信息

4.2 評價指標

在給出各個評價指標的數(shù)學定義之前，先介紹使用到的數(shù)學符號。給定一個測試實例xi，h表示分類器，f表示排序函數(shù)，rank f則表示指定標簽的排名，p表示實例個數(shù)，Δ表示兩個集合中不同元素的數(shù)量。本實驗所使用的評價指標主要包括以下五種：

1）漢明損失（Hamming Loss）：實例被誤判的次數(shù)，包括屬于所給實例的標簽未被預(yù)測，以及預(yù)測出的標簽不屬于所給實例，其定義如下：

2）單一錯誤（One-Error）：排名第一的標簽不屬于所給實例的次數(shù)，其定義如下：

3）覆蓋距離（Coverage）：預(yù)測標簽序列中，平均走多少步才能覆蓋所給實例的所有相關(guān)標簽，其定義如下：

4）平均精確度（Average Precision）：統(tǒng)計標簽在預(yù)測的標簽序列中排名在其前面的相關(guān)標簽的個數(shù)，其定義如下：

5）排序損失（Ranking Loss）：考察標簽排名中出現(xiàn)排序錯誤的情況，其定義如下：

上述五種評價指標中，除平均準確率是取值越大了算法性能越好外，其他四個指標都是取值越小越好。

4.3 實驗結(jié)果及分析

實驗主要包括兩部分：第一部分是特征選擇過程的實驗，用以確定最佳的特征選擇百分比；第二部分是FLBR算法和其他BR改進算法的對比實驗，用以驗證FLBR算法的有效性。

首先進行第一部分實驗，研究特征選擇百分比t對算法結(jié)果的影響。這里選擇C4.5分類器作為基礎(chǔ)分類器，在6個數(shù)據(jù)集上進行實驗。實驗采用10重交叉驗證方法，統(tǒng)計10次交叉驗證結(jié)果的均值作為最終結(jié)果，實驗結(jié)果如圖3所示。

圖3 特征選擇閾值t1的實驗結(jié)果

從以上結(jié)果可以看出，隨著t1的增大，CAL500和Yeast數(shù)據(jù)集的各項評價指標都明顯變差，Emo?tion、Enron和Medical數(shù)據(jù)集的各項評價指標有變差的趨勢，變化幅度相對較小，這五個數(shù)據(jù)集最佳的特征選擇百分比在0.1～0.2之間。Birds數(shù)據(jù)集的各項指標一直在小范圍內(nèi)波動，沒有明顯的變化趨勢，但是其在0.2處的評價指標優(yōu)于多數(shù)其他取值。因此，當t1取0.2時，各個數(shù)據(jù)集都具有較好的表現(xiàn)。

接下來進行第二部分的實驗，將FLBR算法和典型的BR改進算法進行對比。實驗中采用的對比算法有BR，MLSF，F(xiàn)BR，DBR和CPDBR算法。其中FBR是第一部分實驗所用算法，僅進行了特征選擇。FBR和MLSF是針對冗余特征問題的改進方法，DBR、CPDBR和GCC是針對標簽相關(guān)性問題的改進方法。本文算法在Weka-3.7.10系統(tǒng)平臺上設(shè)計和實現(xiàn)，各算法統(tǒng)一使用C4.5分類器作為基礎(chǔ)分類器。FLBR算法中涉及到兩個參數(shù)，易錯標簽的判定閾值t取0.6，特征選擇百分比使用上文得到的結(jié)果0.2。其他算法涉及到的閾值均使用原文中選取的閾值。各算法統(tǒng)一使用10重交叉驗證后的結(jié)果，各算法在6個基準數(shù)據(jù)集上的實驗結(jié)果如表2～表6所示。

表2 各算法在數(shù)據(jù)集上的漢明損失

表6 各算法在數(shù)據(jù)集上的排序損失

表3 各算法在數(shù)據(jù)集上的平均準確率

表4 各算法在數(shù)據(jù)集上的覆蓋距離

表5 各算法在數(shù)據(jù)集上的單一錯誤

在特征選擇方面，MLSF算法在4個數(shù)據(jù)集上的表現(xiàn)比BR算法好，而FBR算法在6個數(shù)據(jù)集上的表現(xiàn)都優(yōu)于BR算法，并且FBR在每個指標上的提升效果更明顯。這一方面表明通過解決冗余屬性問題可以有效提升算法性能，另一方面也說明FBR是一種有效的特征選擇方法。

在考慮標簽相關(guān)性方面，DBR算法僅在Yeast數(shù)據(jù)集上優(yōu)于BR算法，說明無關(guān)依賴的引入會誤導分類結(jié)果。CPDBR算法除了Yeast外，各項指標都優(yōu)于DBR，但是相較于BR算法并未有明顯提升，說明其并未徹底解決冗余屬性的問題。而FL?BR算法在4個數(shù)據(jù)集上的表現(xiàn)優(yōu)于FBR算法，說明FLBR算法通過控制結(jié)構(gòu)考察標簽相關(guān)性的方式有效解決了冗余屬性和錯誤傳播問題，從而驗證了控制結(jié)構(gòu)的有效性。在Emotion和Enron數(shù)據(jù)集中，F(xiàn)LBR算法的表現(xiàn)比FBR略差。究其原因，第一部分實驗結(jié)果表明Enron和Emotions數(shù)據(jù)集最佳的特征選擇百分比在0～0.1之間，因此使用0.2作為閾值仍會引入無關(guān)依賴，從而導致FLBR算法的預(yù)測性能變差。

總體來看，算法在6個基準數(shù)據(jù)集上的總體表現(xiàn)都優(yōu)于其他典型的BR改進算法。這說明FLBR算法通過同時解決BR存在的冗余屬性和未考慮標簽相關(guān)性兩個問題，更有效地提升了BR算法的性能。

5 結(jié)語

改進BR算法的方法主要有兩種：考慮標簽和特征間關(guān)系以及考慮標簽間相關(guān)性，現(xiàn)有的改進工作大多只考慮其中一個方面。針對這樣的問題，本文提出基于特征選擇和標簽相關(guān)性的FLBR算法。算法首先進行特征選擇，而后將相關(guān)標簽加入特征集合中，通過這兩步操作較好地解決了BR算法存在的問題。此外，針對現(xiàn)有標簽相關(guān)性改進工作中存在的無關(guān)依賴和錯誤傳播問題，F(xiàn)LBR算法使用控制結(jié)構(gòu)的考察方式予以解決。實驗表明，F(xiàn)LBR算法取得了比BR的相關(guān)改進算法更好的性能。算法在考察標簽依賴關(guān)系時未考慮其他標簽影響，未來將研究更有效的考察方式，以期獲得更好的分類效果。