基于分類器鏈的多標簽分類算法

李校林，陸佳麗，王韓林

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

1 引言

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

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

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

2 基于分類器鏈改進的多標簽分類算法

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

D

={(

x

，

Y

)，

i

=1，2，…，

n

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

x

=[

x

1，…，

x

]代表

d

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

L

={

l

，

l

，…，

l

}代表標簽集合，

Y

=[

y

1，…，

y

]?

L

，如果第

i

個標簽與樣本

x

相關(guān)，則

y

=1，否則

y

=0，則一個樣本的標簽集合就可以表示為

y

∈{0，1}。

2.1 分類器鏈多標簽分類算法

分類器鏈是考慮所有標簽之間的相關(guān)性，將上一個分類器的輸出結(jié)果加入到下一個分類器的屬性空間中，每個分類器處理與標簽相關(guān)的二分類問題，鏈中每個分類器的屬性空間被擴展為與所有先前分類器的標簽關(guān)聯(lián)，

CC

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

α

：{1，…，

q

}→{1，…，

q

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

l

(1)?

l

(2)?…?

l

()，對標簽

y

()(1<

j

<

q

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

(1)

即將第

j

個分類器以前的(

j

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

j

個分類器的屬性空間中，實現(xiàn)標簽信息在分類器鏈中的傳遞。

(2)

其中，

sign

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

x

′對應的預測標簽集合可以表示為：

(3)

圖1 CC算法的分類過程

2.2 標簽選擇有序分類器鏈算法

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

D

={(

x

，

Y

)，

i

=1，2，…，

n

}，測試樣本集為

T

={(

x

，

Y

)，

i

=1，2，…，

m

}，標簽集合

L

={

l

，

l

，…，

l

}。每個標簽訓練一個分類器，每個分類器對所有樣本進行遍歷預測，并統(tǒng)計每個標簽的分類錯誤率

V

(4)

其中，

y

表示第

j

個標簽向量，

γ

表示第

j

個標簽的預測結(jié)果，

n

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

D

；標簽集

L

；預測樣本集

T

輸出： 標簽的順序集

V

1) 初始化訓練集

D

；

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

D

←

D

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

h

：

D

→{0，1}；

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

h

預測樣本

x

的第

j

個標簽

y

，其預測結(jié)果為

γ

；8)

if

y

≠

γ

9)

V

←1；

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

標簽

Υ

=(

y

，

y

，…，

y

)表示訓練樣本

x

是否屬于

y

標簽類

(5)

用余弦相似度衡量標簽

y

與標簽

y

間的相關(guān)性

(6)

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

(7)

訓練每個分類器時，通過計算標簽間的相關(guān)性，將當前分類器的輸出結(jié)果加入到與它相關(guān)程度(相關(guān)程度大于0

.

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

LS

-

OCC

算法的分類過程，樣本

x

屬于

y

y

y

y

四個類別，由表1算法得到標簽的順序

y

y

y

y

后，利用余弦相似度計算

y

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

y

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

y

，將

y

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

y

分類器的屬性空間中，為

y

分類器的訓練提供有用信息。然后按照標簽順序?qū)撕?p>y

進行訓練并將訓練結(jié)果加入到與

y

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

y

y

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

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

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

x

進行預測，得到樣本

x

預測標簽集

l

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

D

；標簽集

L

；測試集

T

；標簽順序集

V

輸出：

Y

，樣本

x

的預測標簽集1) 初始化訓練集

D

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

V

的順序?qū)撕炛鹨挥柧毞诸惼鳎?p>

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

D

←

D

{}；5)

h

：

D

→{0，1}；

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

sim

(

y

，

y

)，將大于0

.

5的結(jié)果存入

arr

[]數(shù)組中；

9)：

i

=argmax(

arr

[])，對應的標簽為

y

；10)

x

←[

x

，…，

x

，

y

]；11)

D

←

D

∪(

x

，

y

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

h

：

D

→{0，1}；

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

h

預測樣本

x

的第

j

個標簽

y

，并將結(jié)果存入

l

中；16)

Y

←

l

3 實驗與結(jié)果分析

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

3.1 評估指標和實驗數(shù)據(jù)

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

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

(8)

其中，

R

表示第

i

個樣本的真實標簽集合，

Y

表示預測得到的標簽集合，|

R

∩

Y

|表示預測正確的標簽個數(shù)，|

R

∪

Y

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

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

(9)

其中，|

R

Δ

Y

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

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

(10)

其中，

p

是查準率，

r

是查全率

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

表1描述了所用的8個數(shù)據(jù)集的訓練集與測試集的樣本數(shù)、特征維數(shù)、標簽數(shù)量、基數(shù)(每個樣本的平均標簽數(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兩個數(shù)據(jù)集的樣本數(shù)量最多，但是其特征數(shù)量與標簽數(shù)量相對較少，而樣本數(shù)量較少的Medica和Enron數(shù)據(jù)集的特征數(shù)量與標簽數(shù)量相對較多， Emotions和Scene兩個數(shù)據(jù)集的標簽數(shù)量相同。

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

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

圖3 訓練集與測試集的占比

3.2 實驗結(jié)果和分析

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

表2 不同方法在準確率↑指標上的實驗結(jié)果

表3 不同方法在漢明損失↓指標上的實驗結(jié)果

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

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

表4 不同方法在Macro-F1↑指標上的實驗結(jié)果

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

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

4 結(jié)束語

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