考慮標(biāo)記間依賴關(guān)系的多標(biāo)記分類算法

孫艷歌 , 邵 罕 , 李艷靈

(1. 信陽師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 信陽 464000；2. 北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044)

0 引言

傳統(tǒng)的分類學(xué)習(xí)都假設(shè)數(shù)據(jù)只有一個(gè)類標(biāo)，然而在實(shí)際應(yīng)用中，一個(gè)實(shí)例卻往往可能同時(shí)屬于多個(gè)類別．例如，一部電影可能同時(shí)屬于動(dòng)作片、犯罪片和驚悚片；一篇新聞報(bào)道可能同時(shí)屬于國內(nèi)新聞、政治新聞和經(jīng)濟(jì)新聞；一個(gè)場景可能同時(shí)屬于日出場景和海濱場景等．在這些情況下，每個(gè)實(shí)例都對應(yīng)由多個(gè)標(biāo)記組成的標(biāo)記集，針對這種實(shí)例的分類稱為多標(biāo)記學(xué)習(xí)．多標(biāo)記學(xué)習(xí)目前是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域研究的熱點(diǎn)之一，其研究成果廣泛地應(yīng)用于如文本分類[1]、圖像視頻的語義標(biāo)注[2]、功能基因組[3]、音樂情感分類[4]等領(lǐng)域．

目前，研究者提出了眾多多標(biāo)記分類算法，文獻(xiàn)[5]將標(biāo)記分類算法分為兩類：問題轉(zhuǎn)化方法和算法適應(yīng)方法．前者是將多標(biāo)記分類問題轉(zhuǎn)化為單個(gè)或者多個(gè)單標(biāo)記分類問題．而后者則是對現(xiàn)有的單標(biāo)記學(xué)習(xí)算法進(jìn)行擴(kuò)展，使其能直接處理多標(biāo)記數(shù)據(jù)．

近年來，如何有效地利用標(biāo)記間的依賴關(guān)系中所蘊(yùn)含的信息以提高分類性能，已成為多標(biāo)記學(xué)習(xí)中的一個(gè)研究熱點(diǎn)．標(biāo)記之間依賴關(guān)系中往往包含潛在有用的信息，如在場景分類中，海濱場景一般也屬于室外場景，而政治新聞卻不太可能屬于娛樂新聞等，利用這些潛在信息將有助于提高分類器的性能．因此，本文在分析總結(jié)已有研究的基礎(chǔ)上，重點(diǎn)研究如何描述與利用標(biāo)記間的依賴關(guān)系以取得更好的分類效果，提出了一種考慮標(biāo)記間依賴關(guān)系的多標(biāo)記分類算法.

1 相關(guān)工作

1.1 多標(biāo)記學(xué)習(xí)模型描述

從概率的角度來看，多標(biāo)記學(xué)習(xí)可看作是一個(gè)求多個(gè)標(biāo)記的聯(lián)合條件概率p(y|x)的問題，其中，y為0/1組成的標(biāo)記向量．對于實(shí)例x預(yù)測的最優(yōu)標(biāo)記向量y*為使聯(lián)合概率獲得最大的向量，即：

(1)

用Parent(yk)表示標(biāo)記yk所依賴的標(biāo)記集合，則求p(y|x)可以轉(zhuǎn)化為如式(2)所示的形式來求解．

(2)

由式(2)可看出，求x的標(biāo)記向量的關(guān)鍵是如何找出標(biāo)記所依賴的標(biāo)記集，以盡可能準(zhǔn)確地計(jì)算標(biāo)記向量概率．

1.2 多標(biāo)記分類算法

傳統(tǒng)單標(biāo)記分類算法無法直接應(yīng)用到多標(biāo)記分類的問題中．近年來已經(jīng)提出許多解決多標(biāo)記分類問題的方法，主要分為兩大類：算法適應(yīng)和問題轉(zhuǎn)化．

通過將已有的機(jī)器學(xué)習(xí)算法經(jīng)過調(diào)整、擴(kuò)展或定制以適應(yīng)多標(biāo)記分類的任務(wù)而形成多標(biāo)記方法，統(tǒng)稱為算法適應(yīng)型方法．CLARE等[2]修改了C4.5算法的信息熵的計(jì)算公式，提出了適應(yīng)于多標(biāo)記數(shù)據(jù)的ML-C4.5算法．ZHANG等[6]提出的使用于多標(biāo)記的懶惰式算法ML-kNN算法．SCHAPIRE等[1]提出AdaBoost.MH和AdaBoost.MR兩種擴(kuò)展于Boosting的多標(biāo)記方法．BP-MLL則是通過修改流行的反向傳播算法來適應(yīng)多標(biāo)記數(shù)據(jù)的一種算法[7]．

目前常用的問題轉(zhuǎn)化算法主要兩種：二值相關(guān)算法(Binary Relevance, BR)和標(biāo)記冪集合算法(Label PowerSet, LP)．BR方法將多標(biāo)記問題轉(zhuǎn)換成多個(gè)二值分類問題．并假設(shè)標(biāo)記間彼此獨(dú)立，并未考慮標(biāo)記間的依賴關(guān)系．為此，READ等[8]提出了分類器鏈算法(Classifier Chain，CC)，將標(biāo)記隨機(jī)排序形成一個(gè)鏈，在對每個(gè)標(biāo)記分類時(shí)都考慮在鏈中其之前所有標(biāo)記的信息．SUCAR等[9]提出了基于貝葉斯網(wǎng)絡(luò)的改進(jìn)型分類器鏈算法，通過建立貝葉斯網(wǎng)絡(luò)來尋找到分類器鏈的適當(dāng)順序，從而達(dá)到優(yōu)化的目的．LP方法將實(shí)例的標(biāo)記集看作一個(gè)新標(biāo)記，從而潛在地利用了標(biāo)記間的依賴關(guān)系，但標(biāo)記個(gè)數(shù)呈指數(shù)級增長．TSOUMAKAS等[10]提出了隨機(jī)標(biāo)記子集算法(Randomk-Labelsets，RAkEL)，在考慮了標(biāo)記間依賴關(guān)系的同時(shí)，又避免了基本LP方法的標(biāo)記數(shù)過多的問題．

2 考慮標(biāo)記間依賴關(guān)系的多標(biāo)記分類算法

2.1 問題的提出

DEMBCYNSKI等[11]提出了概率分類器鏈(Probabilistic Classifier Chains, PCC)算法，從最小化損失和貝葉斯最優(yōu)估計(jì)角度來解釋多標(biāo)記問題．概率分類器鏈與分類器鏈算法類似，也對標(biāo)記排序，并把每個(gè)標(biāo)記前的所有標(biāo)記當(dāng)作其依賴標(biāo)記．對于給定實(shí)例x，它的每一種標(biāo)記組合y=(y1,…,ym)的概率可以由概率的乘法定則得出．

(3)

由于PCC算法需要求2m個(gè)不同標(biāo)記取值的聯(lián)合概率，并將概率值最大的標(biāo)記集合賦予實(shí)例．由于遍歷了所有可能的標(biāo)記集，概率分類器鏈從理論上能夠找到全局最優(yōu)解，然而訓(xùn)練速度會(huì)隨著標(biāo)記個(gè)數(shù)呈指數(shù)級增長，時(shí)間復(fù)雜度過高．因此，PCC算法只能應(yīng)用于標(biāo)記數(shù)較小的數(shù)據(jù)上．

RAkEL算法利用集成學(xué)習(xí)技術(shù)訓(xùn)練多個(gè)分類器．每次訓(xùn)練都從原標(biāo)記集合中隨機(jī)抽取大小為k的標(biāo)記子集并生成新的訓(xùn)練集合，集合中每個(gè)實(shí)例的新標(biāo)記集為其原始標(biāo)記集與這k個(gè)標(biāo)記形成集合的交集．然后利用基本的LP方法對該子集訓(xùn)練分類器．由于每次學(xué)習(xí)時(shí)的標(biāo)記數(shù)僅為k個(gè)，所以RAkEL方法在考慮了標(biāo)記間依賴關(guān)系的同時(shí)，又避免了基本LP方法的標(biāo)記數(shù)過多的問題．然而，采用了隨機(jī)抽取的方法即假定了標(biāo)記間存在隨機(jī)的依賴關(guān)系，并未根據(jù)標(biāo)記之間的依賴關(guān)系程度來確定各標(biāo)記的依賴標(biāo)記集．

2.2 考慮標(biāo)記間依賴關(guān)系的多標(biāo)記分類算法

盡管在過去的研究中，對多標(biāo)記學(xué)習(xí)研究已經(jīng)取得了一系列的進(jìn)展，但針對多標(biāo)記學(xué)習(xí)中依賴關(guān)系的描述與利用等問題的研究工作開展并不久，仍面臨諸多挑戰(zhàn)．根據(jù)上述分析，可將這兩種算法融合起來，這樣不僅充分利用PCC算法考慮標(biāo)記間依賴關(guān)系的優(yōu)點(diǎn)，又采用RAkEL算法對標(biāo)記進(jìn)行分組從而提高算法的性能.

算法首先利用RAkEL算法來劃分若干個(gè)標(biāo)記子集，然后在各個(gè)子集上通過PCC算法發(fā)現(xiàn)標(biāo)記間的依賴關(guān)系．具體算法過程為：對于一個(gè)多標(biāo)記數(shù)據(jù)，首先選取一個(gè)k值，將標(biāo)記集合分為大小為k的若干個(gè)標(biāo)記子集，然后在每個(gè)標(biāo)記子集內(nèi)部運(yùn)用概率分類器鏈算法構(gòu)建分類器，最后得出最終分類結(jié)果．算法中分類器訓(xùn)練偽代碼如下：

輸入：訓(xùn)練集D，大小為M的標(biāo)記集L，標(biāo)記子集大小k；

輸出：新標(biāo)記集個(gè)數(shù)m，大小為k的新標(biāo)記集Ri，相應(yīng)的LP分類器hi；

1:m=[M/k],i=1,j=1；

2: 設(shè)Ri為空集；

3: 若j小于等于k，則從L中隨機(jī)選取標(biāo)記λj，設(shè)Ri=Ri∪{λj}，L=L{λj},i++，若L為空,則到步驟4;若j大于k,則返回步驟2；

4: 基于數(shù)據(jù)集D和標(biāo)記集Ri利用PCC算法訓(xùn)練分類器hi，i++.若i≤m,則返回步驟2;若i>m,則結(jié)束．

算法的分類如下：

輸入：新標(biāo)記集個(gè)數(shù)m，新實(shí)例x，大小為k的標(biāo)記集Ri，相應(yīng)的LP分類器hi；

輸出：多標(biāo)記分類結(jié)果的向量表示Result；

i從1到m循環(huán)，對于每一個(gè)λj∈Ri，Result=hi(x,λj)．

3 實(shí)驗(yàn)評價(jià)

實(shí)驗(yàn)是在CPU為2.8 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 7的PC機(jī)上進(jìn)行的，所有算法均在mulan平臺(tái)下實(shí)現(xiàn)．Mulan[12]是一個(gè)用于多標(biāo)記數(shù)據(jù)學(xué)習(xí)的JAVA開源庫．

3.1 數(shù)據(jù)集描述

選用5個(gè)數(shù)據(jù)集用于實(shí)驗(yàn)，具體統(tǒng)計(jì)信息描述如表1所示．?dāng)?shù)據(jù)集及其描述可在mulan站點(diǎn)上獲取(http://mulan.sourceforge.net/).

表1 數(shù)據(jù)集合描述Tab. 1 Characteristic of datasets

3.2 評價(jià)標(biāo)準(zhǔn)

為了便于給出各評價(jià)標(biāo)準(zhǔn)的數(shù)學(xué)定義，首先給出將要用到的數(shù)學(xué)符號．設(shè)

D= { (x1,C1), (x2,C2), …, (xn,Cn)}，

為測試實(shí)例集，其中xi表示第i個(gè)實(shí)例，Ci表示xi對應(yīng)的真實(shí)標(biāo)記集合．給定一個(gè)分類器h和測試實(shí)例xi，Yi表示分類器h對其預(yù)測標(biāo)記集合．

采用如下評價(jià)指標(biāo)來度量多標(biāo)記算法的性能：

(1) 漢明損失(Hamming loss)：用于考察樣本在單個(gè)概念類上的誤分類情況，其定義如式(4)所示．

(4)

(2) 準(zhǔn)確率(Accuracy)：用于統(tǒng)計(jì)每個(gè)真實(shí)標(biāo)記集與預(yù)測標(biāo)記集的交集大小與真實(shí)標(biāo)記集與預(yù)測標(biāo)記集的并集大小的比，并求均值．其定義如式(5)所示．

(5)

(3) F1測度(F1 measure)：是查準(zhǔn)率和查全率的綜合指標(biāo)，其定義如式(6)所示．

(6)

3.3 與其他算法進(jìn)行比較

與本文算法比對的算法包括：BR算法、CC算法、PCC算法和RAkEL算法．在上述5個(gè)數(shù)據(jù)集上對比了本文所提出的算法和各相應(yīng)的比對算法，并統(tǒng)計(jì)了各算法在上述3種評價(jià)標(biāo)準(zhǔn)下5次10重交叉驗(yàn)證所得數(shù)據(jù)的均值的實(shí)驗(yàn)結(jié)果，如表2至表4所示．加“*”號表示相應(yīng)的算法在當(dāng)前的平均標(biāo)準(zhǔn)和數(shù)據(jù)集上表現(xiàn)最好．

表2 不同算法的漢明損失

表3 不同算法的準(zhǔn)確率

表4 不同算法的F1測度

表2～表4給出了本文算法與其他算法在5個(gè)數(shù)據(jù)集上的漢明損失、分類準(zhǔn)確率和F1測度上的對比情況．通過比較分析，發(fā)現(xiàn)本文算法在標(biāo)記數(shù)目比較大的數(shù)據(jù)集Enron、Medical和Yeast上具有明顯的優(yōu)勢，而在標(biāo)記數(shù)較小的數(shù)據(jù)集Emotions和Scene上表現(xiàn)并不具有明顯優(yōu)勢，這是由于過分強(qiáng)調(diào)標(biāo)記間的依賴關(guān)系反而可能降低算法的性能．總之，實(shí)驗(yàn)結(jié)果表明，本文所提出的算法較之分類器鏈和其他對比算法，能夠更為有效地利用標(biāo)記間的依賴關(guān)系，從而能夠更為準(zhǔn)確地預(yù)測實(shí)例是否屬于某一標(biāo)記，尤其適用于標(biāo)記數(shù)目較大的數(shù)據(jù)集．

4 結(jié)論

本文重點(diǎn)研究如何有效地利用標(biāo)記間的依賴關(guān)系來提高多標(biāo)記分類算法的性能．在分析了已有算法特點(diǎn)的基礎(chǔ)上，提出了一個(gè)考慮了標(biāo)記間的依賴關(guān)系的多標(biāo)記分類算法．并通過實(shí)驗(yàn)驗(yàn)證了算法的有效性．然而，目前的大多數(shù)研究主要針對有標(biāo)記的數(shù)據(jù)進(jìn)行處理的，然而在實(shí)際應(yīng)用中的許多數(shù)據(jù)具有非完全標(biāo)記識(shí)的．因此，對此類的數(shù)據(jù)進(jìn)行分類是值得研究的問題．