蔡 劍 牟甲鵬 余孟池 徐 建

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

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

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

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

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

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

2 相關(guān)工作

2.1 多標(biāo)簽問題的定義

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

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

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

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

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

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

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

3 本文算法

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

3.1 特征選擇步驟

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

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

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

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

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

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

為了考察每個(gè)標(biāo)簽被預(yù)測(cè)成功地難易程度，需要為每個(gè)標(biāo)簽分別訓(xùn)練分類器t(i)。首先從訓(xùn)練集選擇一個(gè)子集Ds?D作為t(i)的訓(xùn)練集，然后使用測(cè)試集DDs對(duì)分類器進(jìn)行驗(yàn)證。這里使用預(yù)測(cè)精確率作為評(píng)價(jià)指標(biāo)，統(tǒng)計(jì)每個(gè)標(biāo)簽的預(yù)測(cè)精確率pi。預(yù)測(cè)概率小于閾值t的標(biāo)簽即為易錯(cuò)標(biāo)簽，易錯(cuò)標(biāo)簽集合記為L(zhǎng)e。

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

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

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

算法1 FLBR算法的訓(xùn)練過程

判定易錯(cuò)標(biāo)簽的閾值t

二分類學(xué)習(xí)算法B

輸出：為每個(gè)標(biāo)簽yi訓(xùn)練的兩個(gè)分類器hi，h'i

算法步驟：

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

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

3）為標(biāo)簽i訓(xùn)練基分類器h(i)←B({Fi，yi})；

4）end for

5）對(duì)訓(xùn)練集D隨機(jī)采樣得到子集Ds?D；

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

7）為每個(gè)標(biāo)簽i訓(xùn)練驗(yàn)證分類器t(i)←B(Ds)；

8）end for

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

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

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

12）為標(biāo)簽i訓(xùn)練元分類器

13）end for

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

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

4 實(shí)驗(yàn)分析

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

4.2 評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

上述五種評(píng)價(jià)指標(biāo)中，除平均準(zhǔn)確率是取值越大了算法性能越好外，其他四個(gè)指標(biāo)都是取值越小越好。

4.3 實(shí)驗(yàn)結(jié)果及分析

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

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

圖3 特征選擇閾值t1的實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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