李校林，陸佳麗，王韓林

(1. 重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2. 重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065；3. 重慶信科設(shè)計(jì)有限公司，重慶 400021)

1 引言

在現(xiàn)實(shí)應(yīng)用中，一個(gè)對象往往與多個(gè)標(biāo)簽同時(shí)相關(guān)。傳統(tǒng)的單標(biāo)簽分類(Single-Label Classification)即一個(gè)實(shí)例分配一個(gè)標(biāo)簽，已經(jīng)無法處理如今多樣化的海量數(shù)據(jù)。因此，多標(biāo)簽分類(Multi-Label Classification， MLC)即一個(gè)實(shí)例分配多個(gè)標(biāo)簽，成為了一種處理多樣化海量數(shù)據(jù)的重要方法，例如在文本分類中，一篇描述上海世博會的文檔有可能同時(shí)與經(jīng)濟(jì)、創(chuàng)新、城市等多個(gè)主題相關(guān)。目前現(xiàn)有的多標(biāo)簽分類方法可以大致分為兩類，一種是直接修改現(xiàn)有的單標(biāo)簽分類方法以實(shí)現(xiàn)多標(biāo)簽分類，例如多標(biāo)簽決策樹(Multi-Label Decision Tree， ML-DT)、多標(biāo)簽k近鄰等方法。另一種多標(biāo)簽分類方法是通過問題轉(zhuǎn)換，將一個(gè)多標(biāo)簽分類問題轉(zhuǎn)化為一個(gè)或多個(gè)單標(biāo)簽分類問題。這種方法是先使用單標(biāo)簽分類器進(jìn)行單標(biāo)簽分類，然后將這些分類結(jié)果轉(zhuǎn)換為多標(biāo)簽表示形式。例如二元關(guān)聯(lián)(Binary Relevance， BR)、隨機(jī)K標(biāo)簽集(Random k-Labelsets)等方法。這些多標(biāo)簽分類方法從不同角度解決了多標(biāo)簽分類問題，方便人們從大量數(shù)據(jù)中快速的提取有用信息。

分類器鏈(Classifier Chains， CC)是問題轉(zhuǎn)換策略中典型的多標(biāo)簽分類方法之一。雖然BR方法分類模型簡單且直接，但由于其沒有考慮標(biāo)簽間的相關(guān)性導(dǎo)致分類準(zhǔn)確率低。因此，研究人員在基于BR方法的基礎(chǔ)上，提出了CC方法。CC將當(dāng)前分類器的預(yù)測結(jié)果加入到下一個(gè)分類器的屬性空間中，以此來構(gòu)造分類器的鏈狀結(jié)構(gòu)。CC在保證與BR相似的計(jì)算復(fù)雜度的基礎(chǔ)上提高了分類準(zhǔn)確率，其鏈?zhǔn)浇Y(jié)構(gòu)模型簡單，分類效率高，但是CC也存在一些問題：一方面是當(dāng)一個(gè)(或多個(gè))分類器中的一個(gè)(或多個(gè))標(biāo)簽預(yù)測不佳時(shí)，會沿分類器鏈傳播錯(cuò)誤；另一方面是分類器鏈考慮的是所有標(biāo)簽間的相關(guān)性，一些相關(guān)性較小的標(biāo)簽對于分類并沒有太大的作用，因此考慮所有標(biāo)簽間的相關(guān)性就增加了訓(xùn)練時(shí)標(biāo)簽集的冗余度。針對CC出現(xiàn)的問題，許多基于鏈?zhǔn)浇Y(jié)構(gòu)的改進(jìn)方法被提出，例如有序分類器鏈(Ordered Classifier Chains， OCC)、貝葉斯鏈分類器(Bayesian Chain Classifiers， BCC)以及利用信息熵進(jìn)行標(biāo)簽排序的分類器鏈(Entropy based Classifier Chains， EbCC)等方法。其中，OCC是對標(biāo)簽進(jìn)行排序進(jìn)而形成有序的分類器鏈；BCC是基于概率來形成樹狀鏈?zhǔn)浇Y(jié)構(gòu)；EbCC是基于信息熵來形成鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行分類。這些方法在一定程度上改善了CC出現(xiàn)的問題，但也存在著模型復(fù)雜、效率低的缺點(diǎn)。

針對以上鏈?zhǔn)浇Y(jié)構(gòu)方法出現(xiàn)的問題，本文提出了一種標(biāo)簽選擇有序分類器鏈算法(Label selection ordered Classifier Chain， LS-OCC)。其主要思想是首先統(tǒng)計(jì)標(biāo)簽被錯(cuò)誤分類的分類錯(cuò)誤率以升序的方式對標(biāo)簽進(jìn)行排序，以此得到分類器的順序，在一定程度上減小了錯(cuò)誤傳播，然后在訓(xùn)練階段，建立每個(gè)基分類器的時(shí)候通過判斷標(biāo)簽之間相關(guān)程度的大小進(jìn)行選擇，選擇相關(guān)性最大的標(biāo)簽，降低分類器屬性空間的信息冗余。

2 基于分類器鏈改進(jìn)的多標(biāo)簽分類算法

為了更好的描述MLC，在MLC場景中，用

D

={(

x

，

Y

)，

i

=1，2，…，

n

}表示多標(biāo)簽數(shù)據(jù)集，其中

x

=[

x

1，…，

x

]代表

d

維樣本數(shù)據(jù)，

L

={

l

，

l

，…，

l

}代表標(biāo)簽集合，

Y

=[

y

1，…，

y

]?

L

，如果第

i

個(gè)標(biāo)簽與樣本

x

相關(guān)，則

y

=1，否則

y

=0，則一個(gè)樣本的標(biāo)簽集合就可以表示為

y

∈{0，1}。

2.1 分類器鏈多標(biāo)簽分類算法

分類器鏈?zhǔn)强紤]所有標(biāo)簽之間的相關(guān)性，將上一個(gè)分類器的輸出結(jié)果加入到下一個(gè)分類器的屬性空間中，每個(gè)分類器處理與標(biāo)簽相關(guān)的二分類問題，鏈中每個(gè)分類器的屬性空間被擴(kuò)展為與所有先前分類器的標(biāo)簽關(guān)聯(lián)，

CC

算法的分類過程如圖1。假設(shè)

α

：{1，…，

q

}→{1，…，

q

}是一個(gè)指定分類器鏈順序的函數(shù)，用于指定標(biāo)簽的順序。任給定一個(gè)標(biāo)簽順序

l

(1)?

l

(2)?…?

l

()，對標(biāo)簽

y

()(1<

j

<

q

)構(gòu)建一個(gè)二分類訓(xùn)練數(shù)據(jù)集

(1)

即將第

j

個(gè)分類器以前的(

j

-1)個(gè)分類器的輸出結(jié)果加入到第

j

個(gè)分類器的屬性空間中，實(shí)現(xiàn)標(biāo)簽信息在分類器鏈中的傳遞。

(2)

其中，

sign

[·]是符號函數(shù)，預(yù)測樣本

x

′對應(yīng)的預(yù)測標(biāo)簽集合可以表示為：

(3)

圖1 CC算法的分類過程

2.2 標(biāo)簽選擇有序分類器鏈算法

假設(shè)訓(xùn)練樣本集為

D

={(

x

，

Y

)，

i

=1，2，…，

n

}，測試樣本集為

T

={(

x

，

Y

)，

i

=1，2，…，

m

}，標(biāo)簽集合

L

={

l

，

l

，…，

l

}。每個(gè)標(biāo)簽訓(xùn)練一個(gè)分類器，每個(gè)分類器對所有樣本進(jìn)行遍歷預(yù)測，并統(tǒng)計(jì)每個(gè)標(biāo)簽的分類錯(cuò)誤率

V

(4)

其中，

y

表示第

j

個(gè)標(biāo)簽向量，

γ

表示第

j

個(gè)標(biāo)簽的預(yù)測結(jié)果，

n

為訓(xùn)練集樣本的個(gè)數(shù)。以分類錯(cuò)誤率升序的方式對標(biāo)簽進(jìn)行排序，從而得到標(biāo)簽的順序，即分類器的順序。標(biāo)簽順序的獲取過程描述如下。輸入： 訓(xùn)練集

D

；標(biāo)簽集

L

；預(yù)測樣本集

T

輸出： 標(biāo)簽的順序集

V

1) 初始化訓(xùn)練集

D

；

3) 根據(jù)式(1)訓(xùn)練分類器：

D

←

D

{}；4) 得到預(yù)測函數(shù)

h

：

D

→{0，1}；

7) 根據(jù)預(yù)測函數(shù)

h

預(yù)測樣本

x

的第

j

個(gè)標(biāo)簽

y

，其預(yù)測結(jié)果為

γ

；8)

if

y

≠

γ

9)

V

←1；

在得到標(biāo)簽順序后，接下來實(shí)現(xiàn)對標(biāo)簽選擇有序分類器鏈算法的訓(xùn)練與測試過程。

標(biāo)簽

Υ

=(

y

，

y

，…，

y

)表示訓(xùn)練樣本

x

是否屬于

y

標(biāo)簽類

(5)

用余弦相似度衡量標(biāo)簽

y

與標(biāo)簽

y

間的相關(guān)性

(6)

在標(biāo)簽選擇有序分類器鏈算法中，若出現(xiàn)某個(gè)標(biāo)簽與其它標(biāo)簽間的相關(guān)性都很小，則此標(biāo)簽對其它標(biāo)簽的分類不能提供有用的信息。因此，設(shè)置閾值：

(7)

訓(xùn)練每個(gè)分類器時(shí)，通過計(jì)算標(biāo)簽間的相關(guān)性，將當(dāng)前分類器的輸出結(jié)果加入到與它相關(guān)程度(相關(guān)程度大于0

.

5)最大的分類器的屬性空間中，若出現(xiàn)相關(guān)程度相同的情況，就將當(dāng)前分類器的輸出結(jié)果加入到相關(guān)程度最大的多個(gè)分類器的屬性空間中，以此來訓(xùn)練新的分類器。例如，圖2是

LS

-

OCC

算法的分類過程，樣本

x

屬于

y

y

y

y

四個(gè)類別，由表1算法得到標(biāo)簽的順序

y

y

y

y

后，利用余弦相似度計(jì)算

y

與其它標(biāo)簽間的相關(guān)性，取與

y

相關(guān)程度最大的標(biāo)簽

y

，將

y

分類器的訓(xùn)練結(jié)果加入到

y

分類器的屬性空間中，為

y

分類器的訓(xùn)練提供有用信息。然后按照標(biāo)簽順序?qū)?biāo)簽

y

進(jìn)行訓(xùn)練并將訓(xùn)練結(jié)果加入到與

y

相關(guān)程度最大的標(biāo)簽

y

y

的屬性空間中，具體描述見表2中的步驟1至步驟13。

圖2 LS-OCC算法的分類過程

在訓(xùn)練結(jié)束后，對測試樣本

x

進(jìn)行預(yù)測，得到樣本

x

預(yù)測標(biāo)簽集

l

，具體描述如表2中的步驟14至步驟17，重復(fù)步驟14至步驟17，得到所有測試樣本的預(yù)測結(jié)果集Y。LS-OCC算法的分類過程描述如下。輸入：訓(xùn)練集

D

；標(biāo)簽集

L

；測試集

T

；標(biāo)簽順序集

V

輸出：

Y

，樣本

x

的預(yù)測標(biāo)簽集1) 初始化訓(xùn)練集

D

；2) 根據(jù)標(biāo)簽順序集

V

的順序?qū)?biāo)簽逐一訓(xùn)練分類器；

4) 根據(jù)式(1)訓(xùn)練分類器：

D

←

D

{}；5)

h

：

D

→{0，1}；

7) 根據(jù)式(6)計(jì)算標(biāo)簽相似度

sim

(

y

，

y

)，將大于0

.

5的結(jié)果存入

arr

[]數(shù)組中；

9)：

i

=argmax(

arr

[])，對應(yīng)的標(biāo)簽為

y

；10)

x

←[

x

，…，

x

，

y

]；11)

D

←

D

∪(

x

，

y

)；12) 得到預(yù)測函數(shù)

h

：

D

→{0，1}；

15) 根據(jù)預(yù)測函數(shù)

h

預(yù)測樣本

x

的第

j

個(gè)標(biāo)簽

y

，并將結(jié)果存入

l

中；16)

Y

←

l

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文中所提出方法的性能，將其與CC、OCC、BCC、EbCC四種傳統(tǒng)的多標(biāo)簽分類方法在三種不同的評估指標(biāo)上進(jìn)行對比實(shí)驗(yàn)，并對實(shí)驗(yàn)結(jié)果進(jìn)行對比分析與總結(jié)。

3.1 評估指標(biāo)和實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)中采用了三種評估指標(biāo)來判斷多標(biāo)簽分類方法的性能：準(zhǔn)確率(Accuracy)、漢明損失(Hamming loss)和Macro-F1。

1)準(zhǔn)確率表示分類正確的樣本數(shù)占樣本總數(shù)的比例

(8)

其中，

R

表示第

i

個(gè)樣本的真實(shí)標(biāo)簽集合，

Y

表示預(yù)測得到的標(biāo)簽集合，|

R

∩

Y

|表示預(yù)測正確的標(biāo)簽個(gè)數(shù)，|

R

∪

Y

|表示真實(shí)標(biāo)簽集合與預(yù)測集合中標(biāo)簽出現(xiàn)的總個(gè)數(shù)。該評估指標(biāo)的值越大表示多標(biāo)簽分類方法的性能越好。

2)漢明損失是用于統(tǒng)計(jì)分類器在所有樣本上被錯(cuò)誤分類的標(biāo)簽個(gè)數(shù)的均值

(9)

其中，|

R

Δ

Y

|表示對稱差。該評估指標(biāo)的值越小表示多標(biāo)簽分類方法的性能越好。

3)Macro-F1對稀有類別(少數(shù)標(biāo)簽)的性能很敏感，用于測量不均衡數(shù)據(jù)的精度。該評估指標(biāo)的值越大表示多標(biāo)簽分類方法的性能越好

(10)

其中，

p

是查準(zhǔn)率，

r

是查全率

本文采用Mulan中的8個(gè)數(shù)據(jù)集(Benchmark Datasets)進(jìn)行實(shí)驗(yàn)來評估本文所提出的分類方法的性能。Mulan是一個(gè)開放的Java庫，用于從多標(biāo)簽數(shù)據(jù)集中學(xué)習(xí)。多標(biāo)簽數(shù)據(jù)集由有多個(gè)二進(jìn)制目標(biāo)變量的目標(biāo)函數(shù)的訓(xùn)練示例組成，這意味著多標(biāo)簽數(shù)據(jù)集的每個(gè)項(xiàng)目都可以是多個(gè)類別的成員，或者可以由許多標(biāo)簽(類)標(biāo)注。

表1描述了所用的8個(gè)數(shù)據(jù)集的訓(xùn)練集與測試集的樣本數(shù)、特征維數(shù)、標(biāo)簽數(shù)量、基數(shù)(每個(gè)樣本的平均標(biāo)簽數(shù))以及數(shù)據(jù)集類型。Emotions是音樂領(lǐng)域的數(shù)據(jù)集，Scene和Flags是圖像領(lǐng)域的數(shù)據(jù)集，Yeast和Genbase是生物領(lǐng)域的數(shù)據(jù)集，Birds是音頻領(lǐng)域的數(shù)據(jù)集，Medical和Enron是文本領(lǐng)域的數(shù)據(jù)集。從表中可以獲知Sence和Yeast兩個(gè)數(shù)據(jù)集的樣本數(shù)量最多，但是其特征數(shù)量與標(biāo)簽數(shù)量相對較少，而樣本數(shù)量較少的Medica和Enron數(shù)據(jù)集的特征數(shù)量與標(biāo)簽數(shù)量相對較多， Emotions和Scene兩個(gè)數(shù)據(jù)集的標(biāo)簽數(shù)量相同。

表1 數(shù)據(jù)集的基本信息

在本次實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)集按照2：1的比例劃分為訓(xùn)練集和測試集，如圖3。

圖3 訓(xùn)練集與測試集的占比

3.2 實(shí)驗(yàn)結(jié)果和分析

CC、OCC、BCC、EbCC和LS-OCC這五種多標(biāo)簽分類方法在準(zhǔn)確率、漢明損失和Macro-F1上進(jìn)行相同環(huán)境下的5次實(shí)驗(yàn)，去除偏差較大的實(shí)驗(yàn)結(jié)果，并將保留的實(shí)驗(yàn)結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。每個(gè)數(shù)據(jù)集上最優(yōu)方法的實(shí)驗(yàn)結(jié)果用黑體標(biāo)出，“↑”表示評估指標(biāo)越大越好，“↓”表示評估指標(biāo)越小越好。實(shí)驗(yàn)結(jié)果見表2至表4。

表2 不同方法在準(zhǔn)確率↑指標(biāo)上的實(shí)驗(yàn)結(jié)果

表3 不同方法在漢明損失↓指標(biāo)上的實(shí)驗(yàn)結(jié)果

從表2可以看出，在評估指標(biāo)準(zhǔn)確率上，同EbCC算法相比，盡管LS-OCC算法在Scene數(shù)據(jù)集上的分類準(zhǔn)確率降低了1.7%，但同其它算法相比均取得了提升。此外，在Genbase數(shù)據(jù)集上，LS-OCC算法和OCC算法均取得了相同的最優(yōu)值，在其它六個(gè)數(shù)據(jù)集上，LS-OCC算法下的分類準(zhǔn)確率均達(dá)到了最優(yōu)，證明了本文所提算法的有效性。另外，觀察發(fā)現(xiàn)，在數(shù)據(jù)集Scene和Flags上，CC與LS-OCC的實(shí)驗(yàn)結(jié)果相差不大，是因?yàn)閷τ跇?biāo)簽數(shù)量少的數(shù)據(jù)集，標(biāo)簽間的相關(guān)性小，為其它標(biāo)簽的預(yù)測提供了很少的有用信息。

從表3可以看出，在評估指標(biāo)漢明損失上，同對比算法相比，LS-OCC在數(shù)據(jù)集Emotions、Scene、Birds、 Enron、Flags和Genbase上均取得了較好的效果，在數(shù)據(jù)集Yeast和Medical上盡管漢明損失值分別增加0.8%和0.2%，但基本達(dá)到最優(yōu)。整體上來說，證明了本文算法的可靠性。在數(shù)據(jù)集Emotions、Scene、Yeast和Flags上的分類效果比在其它數(shù)據(jù)集上的分類效果差，主要是因?yàn)檫@四個(gè)數(shù)據(jù)集的標(biāo)簽數(shù)量少，標(biāo)簽間的相關(guān)性對分類提供的有用信息少。

表4 不同方法在Macro-F1↑指標(biāo)上的實(shí)驗(yàn)結(jié)果

從表4可以看出，在具有整體評價(jià)分類性能的Macro-F1評估指標(biāo)上，盡管在Birds 和Enron 數(shù)據(jù)集上，同OCC和EbCC相比，LS-OCC沒有達(dá)到最優(yōu)，但在多數(shù)數(shù)據(jù)集上的分類效果良好，提高了約1.02%-8.47%。另外，相比于其它數(shù)據(jù)集，該算法在數(shù)據(jù)集Genbase上的Macro-F1值達(dá)到了較高值，更適用于此數(shù)據(jù)集。

CC的分類過程中，標(biāo)簽順序是任意的，錯(cuò)誤信息會沿著鏈傳播，整體上在多個(gè)標(biāo)簽的數(shù)據(jù)集上性能沒有其它方法的性能好。從表2至表4的實(shí)驗(yàn)結(jié)果可以看出，由于CC和OCC過多的考慮標(biāo)簽間的相關(guān)性導(dǎo)致分類性能下降。BCC和 EbCC的模型復(fù)雜，計(jì)算代價(jià)很大，不適合大規(guī)模數(shù)據(jù)。LS-OCC算法從以上兩方面考慮，首先對標(biāo)簽進(jìn)行排序，減小錯(cuò)誤傳播，然后對標(biāo)簽進(jìn)行選擇，保留相關(guān)性大的標(biāo)簽，減少了分類器屬性空間的信息冗余。從整體的實(shí)驗(yàn)結(jié)果來看， LS-OCC算法與幾種對比算法相比，在一定程度上提高了分類性能。

4 結(jié)束語

本文基于分類器鏈算法的思想提出一種標(biāo)簽選擇有序分類器鏈(LS-OCC)多標(biāo)簽分類模型。首先利用標(biāo)簽分類錯(cuò)誤率對標(biāo)簽進(jìn)行排序，然后對排序后的標(biāo)簽進(jìn)行訓(xùn)練，采用余弦相似度來計(jì)算標(biāo)簽之間的相關(guān)性，選擇與當(dāng)前標(biāo)簽相關(guān)性最大的標(biāo)簽作為下一個(gè)被訓(xùn)練的對象，將上一個(gè)訓(xùn)練好的分類器的輸出結(jié)果加入到下一個(gè)分類器的屬性空間中。LS-OCC算法對標(biāo)簽進(jìn)行排序形成有序分類器鏈，在一定程度上減少了錯(cuò)誤傳播。同時(shí)，該算法對標(biāo)簽進(jìn)行選擇，在保證利用標(biāo)簽之間的相關(guān)性的同時(shí)又可以降低分類器屬性空間的信息冗余。通過對比實(shí)驗(yàn)，證明了LS-OCC方法具有良好的分類性能。本文所提算法LS-OCC在分類過程中未考慮其它相似值的標(biāo)簽，接下來的工作將從標(biāo)簽間的相似性在什么范圍內(nèi)對分類起到最好的作用方面進(jìn)行研究。