一種改進(jìn)的RAKEL多標(biāo)簽分類算法*

金永賢， 張微微， 周恩波

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

?

一種改進(jìn)的RAKEL多標(biāo)簽分類算法*

金永賢， 張微微， 周恩波

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

RAKEL(randomk-labelsets)算法是一種集成技術(shù)，能有效解決多標(biāo)簽分類問(wèn)題.它將原始標(biāo)簽集隨機(jī)選用一小部分標(biāo)簽子集構(gòu)成的數(shù)據(jù)集來(lái)訓(xùn)練每個(gè)分類器，但由于RAKEL算法構(gòu)造標(biāo)簽空間的隨機(jī)性，并未充分考察到樣本多個(gè)標(biāo)簽之間的相關(guān)性，從而造成分類精度不高，泛化性能受到一定影響.為此，提出了改進(jìn)的LC-RAKEL算法.首先，通過(guò)標(biāo)簽聚類將原始標(biāo)簽集劃分成標(biāo)簽簇，再?gòu)拿總€(gè)標(biāo)簽簇中各選擇一個(gè)標(biāo)簽構(gòu)成標(biāo)簽集，以此發(fā)現(xiàn)標(biāo)簽空間中重要且不頻繁的映射關(guān)系；然后,利用出現(xiàn)次數(shù)較少的標(biāo)簽集合組成新的訓(xùn)練數(shù)據(jù)，訓(xùn)練相應(yīng)的分類器.實(shí)驗(yàn)證明,改進(jìn)的算法性能優(yōu)于其他常用多標(biāo)簽分類算法.

多標(biāo)簽分類；RAKEL；標(biāo)簽空間；隨機(jī)；不頻繁的映射

多標(biāo)簽學(xué)習(xí)問(wèn)題在現(xiàn)實(shí)世界中廣泛存在.例如，在圖像分類[1]中，一張圖片往往可以對(duì)應(yīng)多個(gè)主題，如“海灘”和“落日”.在文檔分類[2]中，一篇文檔可以屬于多個(gè)主題，如“世界杯”和“足球”.可以看出，每個(gè)樣例都與一個(gè)標(biāo)簽集合相對(duì)應(yīng).多標(biāo)簽學(xué)習(xí)主要研究當(dāng)樣本同時(shí)具有多個(gè)類別標(biāo)記時(shí)，如何構(gòu)建分類器準(zhǔn)確預(yù)測(cè)未知樣本的標(biāo)簽集合.

傳統(tǒng)的二分類和多類分類問(wèn)題，都可以看作多標(biāo)簽學(xué)習(xí)問(wèn)題的特例.目前，研究者已提出多種解決多標(biāo)簽學(xué)習(xí)問(wèn)題的方法，這些方法主要分為算法適應(yīng)法和問(wèn)題轉(zhuǎn)換法兩類[3].由于問(wèn)題轉(zhuǎn)換法具有簡(jiǎn)化性及在大多數(shù)數(shù)據(jù)集上應(yīng)用良好性的特點(diǎn)，因此，本文主要討論問(wèn)題轉(zhuǎn)換法.問(wèn)題轉(zhuǎn)化法中最基本、最常用的2個(gè)方法：Binary Relevance(BR，即二值相關(guān))方法和Label Powset(LP，即標(biāo)記集合)方法.其中，BR 法學(xué)習(xí)多個(gè)二類分類器，每個(gè)分類器只針對(duì)某一個(gè)標(biāo)簽進(jìn)行分類.這種方法簡(jiǎn)便易行，但忽略了標(biāo)簽之間的相互關(guān)系，預(yù)測(cè)結(jié)果往往難以令人滿意.在BR的基礎(chǔ)上，文獻(xiàn)[4]提出Classifier Chain(CC)算法，構(gòu)造多個(gè)鏈?zhǔn)浇Y(jié)構(gòu)的分類器.所謂鏈?zhǔn)浇Y(jié)構(gòu)，即將之前分類器的類屬性加入到訓(xùn)練集的特征屬性中，建立新的訓(xùn)練集，后面的分類器則是在新的訓(xùn)練集上構(gòu)建，這樣就能有效地利用標(biāo)記之間的依賴關(guān)系，但構(gòu)建分類器鏈的順序會(huì)影響分類器的性能.文獻(xiàn)[5]提出的Tree-Based Classifier Chain(TCC)算法是在分類器鏈算法的基礎(chǔ)上改進(jìn)的，它按照一定的順序建立分類器鏈.LP 方法是通過(guò)將多標(biāo)簽數(shù)據(jù)集中每一個(gè)唯一的標(biāo)簽集合看成一個(gè)類別，將多標(biāo)簽分類問(wèn)題分解為多類單標(biāo)簽問(wèn)題.對(duì)于給出的一個(gè)測(cè)試實(shí)例，多類LP 分類器可以預(yù)測(cè)出最可能的類別，然后被轉(zhuǎn)換成一個(gè)標(biāo)簽集合.與簡(jiǎn)單的BR方法相比，LP 方法一定程度上考慮標(biāo)簽的相關(guān)性.然而，隨著標(biāo)簽數(shù)目和訓(xùn)練樣本實(shí)例的增加，可能的類別也相應(yīng)地成比例增加，使得計(jì)算開(kāi)銷變大;另一方面，個(gè)別類別訓(xùn)練樣本過(guò)少，使得學(xué)習(xí)變難.而且LP 僅能預(yù)測(cè)訓(xùn)練集中出現(xiàn)的標(biāo)簽組合.為此，文獻(xiàn)[6]提出了Pruned Problem Transformation(PPT)算法，它保留出現(xiàn)次數(shù)大于閾值的標(biāo)記集合，并對(duì)出現(xiàn)次數(shù)較少的標(biāo)記集合進(jìn)行劃分，對(duì)劃分后的子集建立LP分類器，然而在實(shí)例預(yù)測(cè)時(shí)只能得到在訓(xùn)練集中出現(xiàn)過(guò)的標(biāo)記集合.文獻(xiàn)[7]提出了Randomk-labelsets(RAKEL)算法，從標(biāo)簽的原始集中每次隨機(jī)選擇一部分標(biāo)簽子集，使用LP方法訓(xùn)練相應(yīng)的分類器，最后由多個(gè)LP分類器通過(guò)投票的方式集成預(yù)測(cè).這種方法通過(guò)集成方式解決LP產(chǎn)生數(shù)據(jù)傾斜的不足，同時(shí)通過(guò)隨機(jī)構(gòu)造標(biāo)簽子集考慮標(biāo)簽之間的相關(guān)性.值得注意的是，也正是由于隨機(jī)選擇的特點(diǎn)，標(biāo)簽之間的相關(guān)關(guān)系并沒(méi)有被充分利用，從而造成分類精度不高，泛化性能會(huì)受到一定影響.

在實(shí)際應(yīng)用中，標(biāo)簽與標(biāo)簽之間是有一定聯(lián)系的.例如,圖片分類中，一張圖片包含“黑色”和“月亮”2個(gè)標(biāo)簽，那么其屬于“夜晚”的可能性就很大.又如，包含“裙子”、“長(zhǎng)發(fā)”標(biāo)簽的圖片，屬于“男性”標(biāo)簽的可能性會(huì)很小.因此，是否能充分利用標(biāo)簽之間的相關(guān)性，將直接影響算法的預(yù)測(cè)性能.為此，本文結(jié)合Hierarchy of Multilabel Classifiers(HOMER)算法[8]中balancedk-means(平衡k-means)聚類標(biāo)簽的方法對(duì)RAKEL算法進(jìn)行了改進(jìn).首先，利用balancedk-means將標(biāo)簽聚類為k簇；然后，從每簇中各選擇一個(gè)構(gòu)成新的標(biāo)簽子集.以此發(fā)現(xiàn)訓(xùn)練集中出現(xiàn)次數(shù)較少的標(biāo)簽集合，提高出現(xiàn)次數(shù)較少標(biāo)簽組合的利用率，充分利用標(biāo)簽之間的聯(lián)系，以提高算法的預(yù)測(cè)性能.

1 RAKEL算法

Tsoumakas 等[7]提出的RAKEL算法是通過(guò)將原始的大標(biāo)簽集分成一定數(shù)目的小標(biāo)簽集，然后使用LP訓(xùn)練相應(yīng)的分類器，最后集成預(yù)測(cè)結(jié)果.

在訓(xùn)練過(guò)程中，RAKEL迭代構(gòu)建m(大小為2倍的標(biāo)簽個(gè)數(shù))個(gè)LP分類器，每次迭代中，從所有不同的標(biāo)簽組合(大小為k)中隨機(jī)選擇一個(gè)標(biāo)簽組合Yi，然后學(xué)習(xí)一個(gè)LP分類模型hi.

在預(yù)測(cè)分類時(shí)，對(duì)于一個(gè)未知實(shí)例x，每個(gè)模型hi對(duì)在自己相應(yīng)的Yi中的每一個(gè)標(biāo)簽λj給出一個(gè)二值的預(yù)測(cè)結(jié)果(0或1)，通過(guò)RAKE算法計(jì)算L(標(biāo)簽集合)中每一個(gè)標(biāo)簽λj的一個(gè)平均得票率，如果平均得票率大于給定的閾值t，那么λj就屬于x.一般閾值為0.5.

2 LC-RAKEL算法

RAKEL算法是通過(guò)集成學(xué)習(xí)來(lái)獲得最后的結(jié)果，而集成學(xué)習(xí)的有效性在于分類器的差異性和精確度.由于該算法從標(biāo)簽集合L中隨機(jī)選擇標(biāo)簽子集，所以當(dāng)L較小時(shí)，預(yù)先設(shè)置好的子分類器數(shù)量可以較好地體現(xiàn)出標(biāo)簽的相關(guān)關(guān)系，同時(shí)也保證了子分類器的差異性和精確度.但對(duì)于大標(biāo)簽數(shù)據(jù)集，隨機(jī)選取的一定數(shù)量的標(biāo)簽子集構(gòu)成的子模型就不能充分體現(xiàn)出相關(guān)性，從而對(duì)集成預(yù)測(cè)的準(zhǔn)確度造成較大的影響.本文從該角度出發(fā)，在標(biāo)簽子集選取過(guò)程中，重視發(fā)現(xiàn)訓(xùn)練集出現(xiàn)次數(shù)稀少的標(biāo)簽組合，使構(gòu)造的子模型更具有代表性.

首先，通過(guò)基于HOMER算法中balancedk-means(平衡k-means)聚類的方法，從標(biāo)簽集合L中隨機(jī)選擇k個(gè)標(biāo)簽作為標(biāo)簽聚類中心，將與每個(gè)標(biāo)簽中心的歐式距離最近的其他標(biāo)簽加入到相應(yīng)的標(biāo)簽集合中，每次聚類后都要重新計(jì)算標(biāo)簽聚類中心.把類似的標(biāo)簽聚成k個(gè)標(biāo)簽簇，通過(guò)控制每個(gè)標(biāo)簽簇大小的上限，使每個(gè)聚類標(biāo)簽簇的大小平衡.

然后，在模型訓(xùn)練過(guò)程中依次從不同標(biāo)簽簇內(nèi)隨機(jī)取出一個(gè)標(biāo)簽，組成k-labelsets標(biāo)簽子集.根據(jù)訓(xùn)練集的數(shù)據(jù)集迭代構(gòu)建m個(gè)LP分類器模型.由于在訓(xùn)練集中，以這種方式組成的k-labelsets標(biāo)簽子集對(duì)應(yīng)的樣本較少，從而使得訓(xùn)練出的子分類器預(yù)測(cè)輸出的標(biāo)簽組合更傾向于負(fù)例(這種標(biāo)簽組合的可能性很小)，進(jìn)而得到分類精度更高的子分類器.最后，預(yù)測(cè)分類時(shí)，每個(gè)分類器都會(huì)得到未知實(shí)例的標(biāo)簽預(yù)測(cè)結(jié)果，通過(guò)綜合計(jì)算每一個(gè)標(biāo)簽的平均得票率，預(yù)測(cè)未知實(shí)例的所屬標(biāo)簽.

標(biāo)簽聚類過(guò)程描述如下：

輸入：聚類的數(shù)目k，全部標(biāo)簽集合L，循環(huán)次數(shù)p

輸出：k個(gè)平衡標(biāo)簽聚類簇

fori←1tokdo

Ci←?;//初始化標(biāo)簽聚類集合Ci,賦為空集

ci←randommemberofL;//初始化聚類中心ci，從L中隨機(jī)取一個(gè)標(biāo)簽賦給ci

whilep>0do

foreachλ∈Ldo

fori←1tokdo

dλi←distance(λ,ci)//利用歐式距離公式計(jì)算2個(gè)標(biāo)簽間的距離dλi

finished←false;

insert sort(v,dvj) to sorted listCj;//將標(biāo)簽λ及最短距離添加到標(biāo)簽聚類集合Cj中

if |Cj|>「|L/k|? then

v←remove last element ofCj;//控制Cj的大小大致相等，若大小超過(guò)上限，則將 //Cj的最后一個(gè)元素移除并插入到下一個(gè)最接近的集合中

dvj←∞;

else

finished←true;

recalculate centers；//重新計(jì)算聚類標(biāo)簽中心

p←p-1

returnC1,C2,…,Ck.

模型訓(xùn)練過(guò)程如下：

輸入：模型個(gè)數(shù)m，labelsets(標(biāo)簽子集)大小k,全部標(biāo)簽集合L,訓(xùn)練樣本集D

輸出：LP分類器的組合及相應(yīng)的k-labelsetsYi

R←Lk;//將所有的標(biāo)簽子集賦給R

fori=1tomin(m,|Lk|)do

Yi←?;//清空標(biāo)簽集Yi

forj←1tokdo

Yi←Yi+randomlymemberselectfromCj

end

trainanLPclassifierhi:X→P(Yi)onD;

R←R{Yi};//從R中去掉Yi這種標(biāo)簽組合

end

預(yù)測(cè)分類過(guò)程如下：

輸入：未知實(shí)例x，LP分類器hi的組合，相應(yīng)的k-labelsetsYi，全部標(biāo)簽集合L，閾值t

輸出：多標(biāo)簽分類結(jié)果向量T

forj←1to|L|do

Sj←0;//Sj統(tǒng)計(jì)第j個(gè)標(biāo)簽的預(yù)測(cè)結(jié)果

Vj←0;//Vj統(tǒng)計(jì)含有第j個(gè)標(biāo)簽的訓(xùn)練模型數(shù)量

fori←1tomdo

foralllabelsλj∈Yido

Sj←Sj+hi(x,λj);

Vj←Vj+1;

forj←1to|L|do

Aj←Sj/Vj;//Aj計(jì)算對(duì)未知實(shí)例x的標(biāo)簽λi平均得票率

ifAj>tthen

Tj←1;

elseTj←0;//若平均得票率大于閾值，則對(duì)應(yīng)標(biāo)簽的預(yù)測(cè)為1,反之為0

3 實(shí)驗(yàn)與分析

為了驗(yàn)證算法的有效性，在一些多標(biāo)記數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)采用emotions[9]，scene[10]，birds[11]，medical[12]，genbase[13]5個(gè)數(shù)據(jù)集.表1給出了詳細(xì)的統(tǒng)計(jì)信息.

表1 多標(biāo)簽數(shù)據(jù)集及統(tǒng)計(jì)信息

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

針對(duì)LC-RAKEL算法，本文采用5-fold交叉驗(yàn)證方法來(lái)評(píng)價(jià)其性能.為了驗(yàn)證該算法的有效性，選擇了BR算法、RAKEL算法、CC算法及基于kNN的ML-KNN[14]算法作為對(duì)比，并采用分類準(zhǔn)確率(Subset Accuracy)、準(zhǔn)確率(Accuracy)、召回率(Recall)、F值(F-measure)、微平均(microF1)、宏平均(macroF1)[15-16]6個(gè)評(píng)價(jià)指標(biāo)進(jìn)行比較.其中:對(duì)于BR算法、CC算法及RAKEL算法采用的基礎(chǔ)分類器算法為支持向量機(jī)分類算法，RAKEL算法中標(biāo)簽子集大小設(shè)為3，模型個(gè)數(shù)設(shè)為標(biāo)簽數(shù)量的2倍，閾值設(shè)為0.5.ML-KNN算法中的k設(shè)為10，smoothing取值為1.所有實(shí)驗(yàn)均在Mulan[17]開(kāi)源庫(kù)中用Java實(shí)現(xiàn).

表2 各算法在5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率(該指標(biāo)值越大，算法的性能越好)

表3 各算法在5個(gè)數(shù)據(jù)集上的準(zhǔn)確率(該指標(biāo)值越大，算法的性能越好)

表4 各算法在5個(gè)數(shù)據(jù)集上的F值(該指標(biāo)值越大，算法的性能越好)

表5 各算法在5個(gè)數(shù)據(jù)集上的召回率(該指標(biāo)值越大，算法的性能越好)

表6 各算法在5個(gè)數(shù)據(jù)集上的微平均(該指標(biāo)值越大，算法的性能越好)

表7 各算法在5個(gè)數(shù)據(jù)集上的宏平均(該指標(biāo)值越大，算法的性能越好)

表2～表7給出了本文算法與其他算法的對(duì)比實(shí)驗(yàn)結(jié)果，表中標(biāo)注星號(hào)的數(shù)據(jù)表示最優(yōu)結(jié)果.從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)：LC-RAKEL算法的性能有明顯提升，5個(gè)數(shù)據(jù)集中的絕大部分指標(biāo)都達(dá)到了1%的提升，有些甚至有2%的性能提升；在emotions，birds和genbase 3個(gè)數(shù)據(jù)集上的全部指標(biāo)都達(dá)到最優(yōu)；在scene數(shù)據(jù)集上除了分類準(zhǔn)確率這個(gè)指標(biāo)之外都達(dá)到最優(yōu).因?yàn)閿?shù)據(jù)集本身具有數(shù)據(jù)分布的復(fù)雜性及標(biāo)簽之間相關(guān)關(guān)系強(qiáng)弱程度，所以在medical數(shù)據(jù)集上的表現(xiàn)略遜于CC算法，但較改進(jìn)前的算法仍有很大的提升.整體上，LC-RAKEL算法優(yōu)于其他算法.

4 結(jié) 語(yǔ)

基于RAKEL算法在處理存在大量標(biāo)簽的數(shù)據(jù)集時(shí)，由于隨機(jī)選擇標(biāo)簽的特點(diǎn)，使得構(gòu)建的子分類器分類精度降低.為此，首先通過(guò)平衡k-means算法找到相關(guān)度高的標(biāo)簽集合，然后從每一類中隨機(jī)選擇標(biāo)簽構(gòu)成子標(biāo)簽集合進(jìn)行模型訓(xùn)練，以此找到分類精度高的模型.實(shí)驗(yàn)證明,LC-RAKEL算法處理多標(biāo)記學(xué)習(xí)問(wèn)題優(yōu)于其他4種算法.

[1]劉鵬,葉志鵬,趙巍,等.一種多層次抽象語(yǔ)義決策圖像分類方法[J].自動(dòng)化學(xué)報(bào),2015,41(5):960-969.

[2]張晶,李德玉,王素格,等.基于穩(wěn)健模糊粗糙集模型的多標(biāo)記文本分類[J].計(jì)算機(jī)科學(xué),2015,42(7):270-275.

[3]李思男,李寧,李戰(zhàn)懷.多標(biāo)簽數(shù)據(jù)挖掘技術(shù):研究綜述[J].計(jì)算機(jī)科學(xué),2013,40(4):14-21.

[4]Read J,Pfahringer B,Holmes G,et al.Classifier chains for multi-label classification[J].Machine Learning,2011,85(3):254-269.

[5]付彬,王志海.基于樹(shù)型依賴結(jié)構(gòu)的多標(biāo)記分類算法[J].模式識(shí)別與人工智能,2012,25(4):573-580.

[6]Read J.A pruned problem transformation method for multi-label classification[C]//Proceeding of New Zealand Computer Science Research Student Conference.Christchurch:Canterbury University,2008:143-150.

[7]Tsoumakas G,Katakis I,Vlahavas I.Randomk-labelsets for multilabel classification[J].IEEE Transactions on Knowledge and Data Engineering,2011,23(7):1079-1089.

[8]Tsoumakas G,Angelis L,Vlahavas I.Selective fusion of heterogeneous classifiers[J].Intelligent Data Analysis,2005,9(6):511-525.

[9]Trohidis K,Tsoumakas G,Kalliris G,et al.Multi-label classification of music into emotions[J].Eurasip Journal on Audio Speech & Music Processing,2008,11(1):325-330.

[10]Boutell M R,Luo J,Shen X,et al.Learning multi-label scene classification[J].Pattern Recognition,2004,37(4):1757-1771.

[11]Briggs F,Lakshminarayanan B,Neal L,et al.Acoustic classification of multiple simultaneous bird species:A multi-instance multi-label approach[J].Journal of the Acoustical Society of America,2012,131(6):4640-4650.

[12]Kajdanowicz T,Kazienko P.Multi-label classification using error correcting output codes[J].International Journal of Applied Mathematics & Computer Science,2012,22(4):829-840.

[13]Tsoumakas G,Katakis I.Multi-label classification:An overview[J].International Journal of Data Warehousing and Mining,2007,3(3):1-13.

[14]Zhang M L,Zhou Z H.ML-KNN:A lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[15]Schapire R E,Singer Y.Boostexter:A boosting-based system for text categorization[J].Machine Learning,2000,39(2):135-168.

[16]Godbole S,Sarawagi S.Discriminative methods for multi-labeled classification[J].Lecture Notes in Computer Science,2004,30(56):22-30.

[17]Tsoumakas G,Spyromitros-Xioufis E,Vlahavas I P,et al.MULAN:A Java library for multi-label learning[J].Journal of Machine Learning Research,2011,12(7):2411-2414.

(責(zé)任編輯 陶立方)

An improved RAKEL method for multilabel classification

JIN Yongxian, ZHANG Weiwei, ZHOU Enbo

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

The RAKEL(randomk-labelsets) algorithm was an effective ensemble method for solving multi-label classification tasks. Each classifier was trained by a different small random subset of the set of labels. But the random nature of RAKEL algorithm constructing label space did not address the correlations between different labels of each example. Thus, it was proposed a novel algorithm called LC-RAKEL, it divided the initial set of labels into label clusters using label clustering, then it constructed a label set by choosing one label from every label cluster in order to identify important and infrequent projections of the label space. Then it employed these new infrequent label sets to form new data to train a corresponding classifier. The experimental results showed that the modified RAKEL algorithm worked better than other commonly used multi-label algorithm.

multilabel classification; RAKEL; label space; random; infrequent projections

10.16218/j.issn.1001-5051.2016.04.005

2016-01-03；

2016-03-29

金永賢(1964-)，男，浙江東陽(yáng)人，教授.研究方向：嵌入式系統(tǒng);無(wú)線傳感器網(wǎng)絡(luò).

TP181

A

1001-5051(2016)04-0386-06