劉 競， 郭忠文， 孫中衛(wèi)， 劉石勇， 王續(xù)澎

(中國海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

與傳統(tǒng)分類問題相比，在多標(biāo)簽分類中，每個(gè)樣本也用單個(gè)實(shí)例表示，它的不同之處在于，每個(gè)實(shí)例可以同時(shí)擁有多個(gè)標(biāo)簽，這樣標(biāo)簽之間就不再相互獨(dú)立[1]。為了解決多標(biāo)簽分類問題，研究者們已經(jīng)提出了許多多標(biāo)簽分類方法，主要包括采用支持向量機(jī)的方法，采用神經(jīng)網(wǎng)絡(luò)的方法，采用樸素貝葉斯的方法，采用決策樹的方法和采用k最近鄰的方法[2]等。這些方法已經(jīng)在文本分類[3]、圖像視頻的語義標(biāo)注[4-5]、生物信息學(xué)預(yù)測[6]、音樂情感分類[7]等許多領(lǐng)域獲得成功運(yùn)用。但是，在現(xiàn)實(shí)世界中存在許多應(yīng)用，它們需要在大規(guī)模數(shù)據(jù)集上進(jìn)行多標(biāo)簽分類，這將導(dǎo)致許多原有的多標(biāo)簽分類方法不能被很好地使用。這主要是受到繁重計(jì)算復(fù)雜度的限制，主要表現(xiàn)為所需訓(xùn)練和測試時(shí)間過長，這在支持向量機(jī)上尤為明顯。本文將聚焦于支持向量機(jī)類型的多標(biāo)簽分類技術(shù)。

傳統(tǒng)的支持向量機(jī)(Support Vector Machine，SVM)[8-9]算法只能解決單標(biāo)簽分類問題，經(jīng)過改進(jìn)的多標(biāo)簽支持向量機(jī)算法[10]可以進(jìn)行多標(biāo)簽分類。但是，現(xiàn)實(shí)世界中的很多應(yīng)用數(shù)據(jù)集需要SVM采用非線性核函數(shù)，這進(jìn)一步限制了SVM多標(biāo)簽分類算法在大規(guī)模多標(biāo)簽數(shù)據(jù)集上的使用。

此外，多標(biāo)簽分類算法無法回避的問題是絕大多數(shù)的多標(biāo)簽數(shù)據(jù)集都在遭受一個(gè)嚴(yán)重的標(biāo)簽數(shù)據(jù)不平衡問題[11]，這將影響各類算法的分類效果。

本文針對多標(biāo)簽SVM分類算法在大規(guī)模數(shù)據(jù)集上使用所遇到的問題，將結(jié)合著名的二元關(guān)聯(lián)問題轉(zhuǎn)換策略和二元DC-SVM[12]分類算法來構(gòu)建一個(gè)新的多標(biāo)簽SVM分類算法(MLDC-SVM)。該算法采用DEC方法來解決標(biāo)簽數(shù)據(jù)不平衡問題。在二個(gè)公共數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：相比于已經(jīng)存在的基于二元關(guān)聯(lián)問題轉(zhuǎn)換策略的多標(biāo)簽分類算法如ML-LIBSVM[13]、ML-CVM[14]和ML-BVM[15]等，本文的算法在訓(xùn)練和測試時(shí)間上是最短的，并且5個(gè)評價(jià)指標(biāo)數(shù)據(jù)顯示，本文的算法性能與ML-LIBSVM更接近，且優(yōu)于ML-CVM和ML-BVM。

1 相關(guān)工作

在過去幾十年里，由于多標(biāo)簽分類在機(jī)器學(xué)習(xí)、模式識別和統(tǒng)計(jì)學(xué)等領(lǐng)域受到廣泛關(guān)注，許多多標(biāo)簽分類算法已經(jīng)被提出和應(yīng)用。這些多標(biāo)簽分類方法可以被歸納為下面兩個(gè)主要策略：問題轉(zhuǎn)換策略和算法改進(jìn)策略[2]。同時(shí)為了解決多標(biāo)簽分類中標(biāo)簽數(shù)據(jù)不平衡問題，許多標(biāo)簽數(shù)據(jù)不平衡處理方法被提出和應(yīng)用并取得良好的效果。本節(jié)將按照上面的兩個(gè)策略介紹一下已有多標(biāo)簽分類方法，介紹一下已經(jīng)存在的標(biāo)簽數(shù)據(jù)不平衡處理方法。

問題轉(zhuǎn)換策略主要是把一個(gè)多標(biāo)簽分類問題轉(zhuǎn)換為幾個(gè)單標(biāo)簽分類問題來解決。因此，基于問題轉(zhuǎn)換策略的多標(biāo)簽分類方法主要是通過聯(lián)合問題轉(zhuǎn)換技巧和已經(jīng)存在的二元分類方法來實(shí)現(xiàn)多標(biāo)簽分類。問題轉(zhuǎn)換技巧主要包括二元關(guān)聯(lián)(Binary relevance)轉(zhuǎn)換技巧、OVO(One-versus-one)轉(zhuǎn)換技巧、OBO(One-by-one)轉(zhuǎn)換技巧和LP(Label powerset)轉(zhuǎn)換技巧[2]等。常用的二元分類方法主要包括SVM、CVM、神經(jīng)網(wǎng)絡(luò)、決策樹和最近鄰等[2]。

在文獻(xiàn)[16]中，作者描述了二元關(guān)聯(lián)問題轉(zhuǎn)換策略主要存在的三個(gè)問題。首先，由于它假定標(biāo)簽之間是獨(dú)立的，這將忽略標(biāo)簽之間的關(guān)聯(lián)性和內(nèi)在依賴性。其次，它將導(dǎo)致標(biāo)簽數(shù)據(jù)不平衡問題，主要表現(xiàn)為轉(zhuǎn)換后的二元數(shù)據(jù)集中，負(fù)實(shí)例數(shù)量將遠(yuǎn)超正實(shí)例數(shù)量。最后，如果標(biāo)簽的數(shù)量過于龐大，標(biāo)簽數(shù)據(jù)不平衡問題將近一步惡化，同時(shí)分類器的數(shù)量也將增加。盡管存在這些問題，但二元關(guān)聯(lián)問題轉(zhuǎn)換策略任然是簡單實(shí)用的并且數(shù)據(jù)是可逆轉(zhuǎn)的。在文獻(xiàn)[17]中，作者著重強(qiáng)調(diào)了它的主要優(yōu)勢。首先，它可以使用任何二元分類器作為基礎(chǔ)分類器來實(shí)現(xiàn)多標(biāo)簽分類。其次，相比于其它的方法，二元關(guān)聯(lián)轉(zhuǎn)換策略有很低的計(jì)算復(fù)雜度，且計(jì)算復(fù)雜度與標(biāo)簽的數(shù)量呈線性關(guān)系。再次，由于標(biāo)簽是獨(dú)立的，標(biāo)簽的增加或減少將不會影響其它標(biāo)簽分類模型，因此，它可以很容易的并行化。最后，它的最重要的優(yōu)勢是能夠優(yōu)化幾個(gè)損失函數(shù)?；诖?，本文將采用著名的二元關(guān)聯(lián)問題轉(zhuǎn)換策略來實(shí)現(xiàn)多標(biāo)簽分類。

算法改進(jìn)策略則通過修改已經(jīng)存在的分類算法來解決多標(biāo)簽分類問題。Clare和King[18]基于C4.5經(jīng)典決策樹算法提出一個(gè)C4.5類型的多標(biāo)簽分類算法，該算法是通過修改信息熵計(jì)算公式和允許決策樹的葉子節(jié)點(diǎn)為一個(gè)標(biāo)簽集合來實(shí)現(xiàn)多標(biāo)簽分類。該多標(biāo)簽分類算法更適用于小規(guī)模數(shù)據(jù)集。多標(biāo)簽支持向量機(jī)(Rank-SVM)被提出在文獻(xiàn)[10]中，它是通過擴(kuò)展多類別支持向量機(jī)并且采用最小化排序損失(Ranking Loss)來實(shí)現(xiàn)多標(biāo)簽分類，這樣做將導(dǎo)致一個(gè)極其復(fù)雜的二次規(guī)劃問題。為了克服Rank-SVM算法的訓(xùn)練耗時(shí)問題，Xu Jianhua[19-20]采用核向量機(jī)(CVM[14])和零標(biāo)簽方法，提出多標(biāo)簽分類算法Rank-CVM和Rank-CVMz，它可以在一定程度上提高訓(xùn)練速度，但將降低分類效果。反向傳播多標(biāo)簽分類算法(BP-MLL)[21]引入一個(gè)新的誤差函數(shù)，該函數(shù)考慮了多標(biāo)簽分類的特征，使得該算法可以應(yīng)用于多標(biāo)簽分類，這將導(dǎo)致一個(gè)大規(guī)模的非約束優(yōu)化問題?；趉最近鄰(kNN)的多標(biāo)簽分類算法ML-kNN[22]，它基于待預(yù)測樣本的k個(gè)最近鄰樣本的類別標(biāo)簽出現(xiàn)的先驗(yàn)和后驗(yàn)概率，使用最大化后驗(yàn)原則確定待預(yù)測樣本的標(biāo)簽集。該算法只能在小規(guī)模數(shù)據(jù)集上使用。

在文獻(xiàn)[23]中詳細(xì)介紹了標(biāo)簽數(shù)據(jù)不平衡問題對各種分類算法的影響。為了克服這個(gè)問題，已經(jīng)有許多的對策被提出和使用，并取得良好的效果。這些對策主要可以概括為以下三個(gè)主流方法，分別為重采樣方法[23]、基于實(shí)例的方法[24]和代價(jià)敏感方法[25]。本文提出的MLDC-SVM分類算法采用DEC方法來克服標(biāo)簽數(shù)據(jù)不平衡問題，DEC方法是代價(jià)敏感方法的一種具體實(shí)現(xiàn)。

盡管許多多標(biāo)簽分類算法已經(jīng)被提出和應(yīng)用，但是它們在大規(guī)模多標(biāo)簽數(shù)據(jù)集上的使用將受到一定限制，尤其是基于SVM方法的更為嚴(yán)重。

2 采用分而治之策略的快速多標(biāo)簽支持向量機(jī)分類算法(MLDC-SVM)

2.1 二元關(guān)聯(lián)問題轉(zhuǎn)換策略

本文將采用著名的二元關(guān)聯(lián)問題轉(zhuǎn)換策略來實(shí)現(xiàn)多標(biāo)簽分類。假定多標(biāo)簽訓(xùn)練數(shù)據(jù)集S={(x1,Y1),(x2,Y2),…,(xN,YN)}，其標(biāo)簽集合為L={1,2,…,k}。二元關(guān)聯(lián)問題轉(zhuǎn)換策略首先把多標(biāo)簽訓(xùn)練數(shù)據(jù)集S轉(zhuǎn)換為k個(gè)獨(dú)立的二元訓(xùn)練數(shù)據(jù)子集Sj={(x1,y1),(x2,y2),…,(xN,yN)},j={1,2,…,k}。其中，二元訓(xùn)練數(shù)據(jù)子集Sj包含多標(biāo)簽訓(xùn)練數(shù)據(jù)集S的所有實(shí)例，但是它的每個(gè)實(shí)例僅帶有一個(gè)積極或消極標(biāo)簽，即相應(yīng)多標(biāo)簽訓(xùn)練實(shí)例的標(biāo)簽集合包含標(biāo)簽j，則該實(shí)例為積極實(shí)例,否者，為消極實(shí)例。之后，針對每個(gè)標(biāo)簽j使用二元訓(xùn)練數(shù)據(jù)子集Sj構(gòu)造相應(yīng)的二元分類器fj(x)。最后，二元關(guān)聯(lián)問題轉(zhuǎn)換策略構(gòu)造了一個(gè)包含k個(gè)二元分類器的集合即HBR，公式如下：

HBR={fj(x)→j′∈{-1,+1}|j∈L}。

(1)

式中，x表示未知的測試實(shí)例；j′表示x在fj(x)的預(yù)測結(jié)果即x是否含有j標(biāo)簽。

為更好的使用二元關(guān)聯(lián)問題轉(zhuǎn)換策略來實(shí)現(xiàn)多標(biāo)簽分類，本文將采用下面的決策函數(shù)來對每個(gè)二元分類數(shù)據(jù)結(jié)果進(jìn)行集成，從而獲取多標(biāo)簽分類結(jié)果。該決策函數(shù)的公式如下：

Y={j,s.t.fj(x)≥0,j=1,…,k}。

(2)

同時(shí)，本文使用以下規(guī)則來避免獲取一個(gè)空的相關(guān)標(biāo)簽集合[26]，公式如下：

Y={j,s.t.maxfj(x),fj(x)<0,j=1,…,k}。

(3)

從章節(jié)1了解到，二元關(guān)聯(lián)問題轉(zhuǎn)換策略是非常實(shí)用和高效的。

2.2 采用分而治之策略的二元支持向量機(jī)及其改進(jìn)

假定有一個(gè)含有N個(gè)數(shù)據(jù)實(shí)例的二元訓(xùn)練數(shù)據(jù)集，即X={xi:xi∈RD,i=1,2,…,N},它對應(yīng)的標(biāo)簽集為Y={yi:yi∈[-1,1],i=1,2,…,N}。那么二元支持向量機(jī)的原始優(yōu)化問題可以轉(zhuǎn)化為下面的一個(gè)對偶形式的二次規(guī)劃問題，公式如下：

(4)

公式(4)就是標(biāo)準(zhǔn)的C-SVM模型。在這里參數(shù)C是用來平衡模型復(fù)雜度和訓(xùn)練樣本誤差的，α∈RN是對偶變量組成的向量，e∈1N是1組成的向量，αi是α中第i個(gè)對偶變量值，Q是一個(gè)N×N的矩陣且Qij=yiyj.K(xi,xj)，其中K(xi,xj)是核函數(shù)。盡管二元支持向量機(jī)能夠提供一個(gè)非常好的分類效果，但是它在大規(guī)模數(shù)據(jù)集上的使用將受到繁重計(jì)算復(fù)雜度的嚴(yán)重限制。因此，在文獻(xiàn)[12]中，作者提出了采用分而治之策略的二元支持向量機(jī)分類算法(DC-SVM算法)。為了實(shí)現(xiàn)DC-SVM算法，作者首先把全局對偶變量集合分解為w個(gè)子集{V1,…,Vw}，之后，獨(dú)立解決各個(gè)子分類問題，公式如下：

(5)

在這里，j={1,…,w},α(j)代表Vj組成的子向量即{α(j)i|α(j)i∈Vj,i=1,…,|Vj|}，Q(j,j)是一個(gè)子矩陣且其行數(shù)和列數(shù)為|Vj|。|Vj|代表了Vj中對偶變量數(shù)量，α(j)i是α(j)中第i個(gè)對偶變量值，e(j)∈1|Vj|是1組成的向量。

DC-SVM分類算法在標(biāo)簽數(shù)據(jù)不平衡時(shí)，傾向于將實(shí)例預(yù)測為負(fù)實(shí)例，其預(yù)測結(jié)果具有偏斜性。解決該問題的一個(gè)有效途徑就是在DC-SVM模型中對兩類實(shí)例選取不同的懲罰參數(shù)，對數(shù)量較少的正實(shí)例選取較大的C值，代表對少類實(shí)例的正確識別更為重視，對其錯(cuò)誤分類的懲罰也更加嚴(yán)格，這就是DEC方法的基本思想。依據(jù)DEC方法，我們將對DC-SVM進(jìn)行部分改進(jìn)，以便于它們可以更好的解決標(biāo)簽數(shù)據(jù)不平衡問題。針對DC-SVM的原始優(yōu)化問題,我們將其改進(jìn)為下面的一個(gè)對偶形式的二次規(guī)劃問題，公式如下：

(6)

s.t.0≤α(j)i≤C+,yi=+1,

0≤α(j)i≤C-,yi=-1。

式中C+和C-代表不同懲罰因子。

從公式(6)中可以看出，通過對兩類實(shí)例選取不同的懲罰參數(shù)C+和C-，可以很好地處理不平衡問題。不同的懲罰參數(shù)C+和C-的取值將用下面的公式來計(jì)算：

C-/C+=n/(pβ)。

(7)

式中:C-/C+代表該訓(xùn)練集的標(biāo)簽不平衡級別；n是訓(xùn)練集的負(fù)實(shí)例個(gè)數(shù)；p是訓(xùn)練集的正實(shí)例個(gè)數(shù)；β是一個(gè)正整數(shù)常量且0<β

2.3 采用分而治之策略的快速多標(biāo)簽支持向量機(jī)分類算法

本文提出的采用分而治之策略的快速多標(biāo)簽支持向量機(jī)分類算法(MLDC-SVM)將采用著名的二元關(guān)聯(lián)問題轉(zhuǎn)換策略來實(shí)現(xiàn)多標(biāo)簽分類。首先，把多標(biāo)簽數(shù)據(jù)集按標(biāo)簽的個(gè)數(shù)(k)轉(zhuǎn)化為k個(gè)二元數(shù)據(jù)集，其中每個(gè)二元數(shù)據(jù)集是有包含該指定標(biāo)簽的正實(shí)例和不包含該指定標(biāo)簽的負(fù)實(shí)例組成，并且每個(gè)二元數(shù)據(jù)集的實(shí)例數(shù)目與多標(biāo)簽數(shù)據(jù)集中的實(shí)例數(shù)目相同。然后，依據(jù)DC-SVM分類算法原理，對DC-SVM分類算法進(jìn)行改進(jìn)，使其采用DEC方法來處理標(biāo)簽數(shù)據(jù)不平衡問題，進(jìn)而提出IMDC-SVM分類算法來處理每個(gè)二元數(shù)據(jù)集，獲取k個(gè)二元分類器。最后，通過公式(2)和(3)來集成k個(gè)二元分類器的結(jié)果，實(shí)現(xiàn)快速多標(biāo)簽分類。

IMDC-SVM分類算法首先隨機(jī)選出m個(gè)訓(xùn)練實(shí)例；其次采用Kernel Kmeans算法對選出的實(shí)例進(jìn)行聚類；獲取w個(gè)聚類中心；然后依據(jù)聚類中心把訓(xùn)練數(shù)據(jù)集分解為w個(gè)訓(xùn)練數(shù)據(jù)子集；然后，針對每個(gè)訓(xùn)練數(shù)據(jù)子集獲取標(biāo)簽數(shù)據(jù)不平衡程度，并采用LIBSVM算法來進(jìn)行訓(xùn)練，使用LIBSVM算法主要是因?yàn)樗芎玫貙?shí)現(xiàn)了DEC方法和SMO算法；最后通過集成每個(gè)訓(xùn)練數(shù)據(jù)子集的解決方案來獲取全局訓(xùn)練數(shù)據(jù)集解決方案。算法1和2分別給出了IMDC-SVM算法和MLDC-SVM算法的偽代碼。

算法1. IMDC-SVM算法

輸入：S-二元訓(xùn)練數(shù)據(jù)集

{(x1,y1),(x2,y2),…,(xN,yN)}。

w-數(shù)據(jù)聚類中心個(gè)數(shù)，

β-正實(shí)數(shù)常量。

BEGIN

(1) 從二元訓(xùn)練數(shù)據(jù)集S中隨機(jī)取樣m個(gè)實(shí)例即

{(x1,y1),(x2,y2),…,(xm,ym)}。

(2) 在{(x1,y1),(x2,y2),…,(xm,ym)}上運(yùn)行Kernel Kmeans算法獲取w個(gè)聚類中心即c1,…,cw。

(3) 對于二元訓(xùn)練數(shù)據(jù)集S,依據(jù)聚類中心c1,…,cw，劃分為w個(gè)二元訓(xùn)練數(shù)據(jù)子集即V1,…,Vw。

(4) FOR每個(gè)二元訓(xùn)練數(shù)據(jù)子集Vc,(c=1,…,w) DO

(a)計(jì)算消極實(shí)例數(shù)量nc；

(b)計(jì)算積極實(shí)例數(shù)量pc；

END

END

算法2. MLDC-SVM算法

輸入：S-多標(biāo)簽訓(xùn)練集

{(x1,Y1),(x2,Y2),…,(xN,YN)}。

x-測試實(shí)例(x∈X)，

k-標(biāo)簽數(shù)量，

β-正實(shí)數(shù)常量，

w-數(shù)據(jù)聚類中心個(gè)數(shù)。

輸出：Y-測試實(shí)例的預(yù)測標(biāo)簽集合 (Y∈Y)。

BEGIN

(1) 對于多標(biāo)簽訓(xùn)練集

S={(x1,Y1),(x2,Y2),…,(xN,YN)},

使用二元關(guān)聯(lián)問題轉(zhuǎn)換策略分解多標(biāo)簽訓(xùn)練集S為k組獨(dú)立的二元訓(xùn)練數(shù)據(jù)集即S1,S2,…,Sk。

(2) FOR每個(gè)二元訓(xùn)練數(shù)據(jù)集

Sj,(j=1,2,…,k) DO

使用公式(6)，訓(xùn)練采用非線性核的IMDC-SVM分類器

fj=IMDC-SVM(Sj,w,β)。

END FOR

(3) 獲取測試實(shí)例x的預(yù)測標(biāo)簽集合

IF (所有fj(x)<0)

Y={j,maxfj(x)},(j=1,2,…,k), 使用公式(3)

ELSE

Y={j|fj(x)≥0},(j=1,2,…,k), 使用公式(2)。

END IF

END

在算法2中，Sj表示第j個(gè)二元訓(xùn)練數(shù)據(jù)集，fj表示使用Sj訓(xùn)練獲得的第j個(gè)標(biāo)簽的預(yù)測模型，fj(x)表示測試實(shí)例x在第j個(gè)標(biāo)簽預(yù)測模型中的預(yù)測值。

2.4 時(shí)空復(fù)雜度分析

由于公式(6)中有N/w個(gè)對偶變量，在實(shí)際中IMDC-SVM的時(shí)間復(fù)雜度至少為 O(N2/w)，空間復(fù)雜度為O(N2/w2)。 MLDC-SVM算法的時(shí)間復(fù)雜度至少為O(kN2/w)，空間復(fù)雜度為O(kN2/w2)，其中k表示標(biāo)簽的數(shù)量，w表示數(shù)據(jù)聚類中心個(gè)數(shù),N表示數(shù)據(jù)集實(shí)例數(shù)量。

3 實(shí)驗(yàn)驗(yàn)證

3.1 三種已經(jīng)存在的多標(biāo)簽分類方法

本文將選取三種已經(jīng)存在的多標(biāo)簽分類算法即ML-LIBSVM、ML-CVM和ML-BVM來與我們提出的MLDC-SVM分類算法進(jìn)行比較。它們都將采用二元關(guān)聯(lián)問題轉(zhuǎn)換策略將多標(biāo)簽分類問題轉(zhuǎn)換為多個(gè)二元分類問題來處理。但是它們的不同之處體現(xiàn)在對轉(zhuǎn)換后的二元分類問題的處理方法上。ML-LIBSVM將采用LIBSVM方法[13]來解決二元分類問題，ML-CVM將采用CVM方法[14]來解決二元分類問題，ML-BVM將采用BVM方法[15]來解決二元分類問題。這三種方法都通過整合所有二元分類問題的結(jié)果來獲取多標(biāo)簽分類結(jié)果。

3.2 多標(biāo)簽數(shù)據(jù)集和評價(jià)指標(biāo)

實(shí)驗(yàn)選用了兩組公共的大規(guī)模多標(biāo)簽數(shù)據(jù)集，這些數(shù)據(jù)集可以在網(wǎng)站https://www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/和http://computer.njnu.edu.cn/Lab/LABIC/LABIC_Software.html[27]上下載。其數(shù)據(jù)集的規(guī)模及屬性見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集特征Table 1 Characteristics of experimental data sets

與單標(biāo)簽分類系統(tǒng)相比，多標(biāo)簽分類系統(tǒng)的評價(jià)準(zhǔn)則要更加復(fù)雜[1,28-29]。本文將選擇當(dāng)前流行的5個(gè)評價(jià)指標(biāo)作為評判標(biāo)準(zhǔn)，它們分別是：漢明損失(Hamming loss)、1-錯(cuò)誤率(One-error)、覆蓋率(Coverage)、排序損失(Ranking loss)和平均精度(Average-precision)。

在這5個(gè)評價(jià)指標(biāo)中，平均精度的值越大，說明多標(biāo)簽分類算法的分類效果越好，其它4個(gè)的值越小，說明多標(biāo)簽分類算法的分類效果越好。

3.3 實(shí)驗(yàn)設(shè)置與結(jié)果分析

針對數(shù)據(jù)集TMC2007-500，為了獲取最優(yōu)解決方案，相應(yīng)參數(shù)設(shè)置為w=10，4個(gè)多標(biāo)簽分類算法的參數(shù)e和C的設(shè)置分別為e=9.5e-5，C=1.0。表2和3給出了4種不同的多標(biāo)簽分類算法在該數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

表2 在TMC2007-500數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 2 Experimental results on TMC2007-500 data set

表3 在TMC2007-500數(shù)據(jù)集上花費(fèi)的時(shí)間Table 3 Time spent on TMC2007-500 data set /s

表2中的數(shù)據(jù)表明MLDC-SVM分類算法與ML-LIBSVM分類算法相比，在Coverage、Ranking loss、Hamming loss和One-error上的值分別上升0.052 9、0.29%、1.4%和1.22%，在Average-precision上的值下降1.82%。這充分說明了MLDC-SVM分類算法的分類效果與ML-LIBSVM分類算法相近，并且要大大優(yōu)于ML-CVM分類算法和ML-BVM分類算法。同時(shí)，從表3中可以看出，MLDC-SVM分類算法在訓(xùn)練和測試時(shí)間上是最短的，分別是ML-LIBSVM算法的1/5.33和1/10.02，是ML-CVM算法的1/2.03和1/9.26，是ML-BVM算法的1/1.24和1/5.80。

針對數(shù)據(jù)集mediamill(exp1)，為了獲取最優(yōu)解決方案，相應(yīng)參數(shù)設(shè)置為w=10，4個(gè)多標(biāo)簽分類算法的參數(shù)e和C的設(shè)置分別為e=1.95e-5，C=1.0。表4和5給出了4種不同的多標(biāo)簽分類算法在該數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

表4中的數(shù)據(jù)表明MLDC-SVM分類算法與ML-LIBSVM分類算法相比，在Ranking loss、Hamming loss和One-error上的值分別上升0.63%、2.42%和19.92%，在Coverage和Average-precision上的值分別下降4.352和15.83%。這充分說明MLDC-SVM分類算法的分類效果與ML-LIBSVM分類算法相近，且在Hamming loss、One-error和Average-precision等指標(biāo)上要大大優(yōu)于ML-CVM分類算法和ML-BVM分類算法。同時(shí)，從表5中可以看出，MLDC-SVM分類算法在訓(xùn)練和測試時(shí)間上是最短的，分別是ML-LIBSVM算法的1/4.73和1/8.39，是ML-CVM算法的1/3.64和1/20.39，是ML-BVM算法的1/1.39和1/9.24。

綜上所述，在兩組大規(guī)模多標(biāo)簽數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的MLDC-SVM分類算法在常用的5個(gè)評價(jià)指標(biāo)上的分類效果相近于ML-LIBSVM分類算法，且優(yōu)于ML-CVM和ML-BVM分類算法。它極大的降低了算法的訓(xùn)練和測試時(shí)間，同時(shí)也能適應(yīng)標(biāo)簽數(shù)據(jù)不平衡情況。這些將極大的提高M(jìn)LDC-SVM分類算法在大規(guī)模多標(biāo)簽數(shù)據(jù)集上的適用性。

表4 在mediamll(exp1)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 4 Experimental results on mediamll(exp1) data set

表5 在mediamill(exp1)數(shù)據(jù)集上花費(fèi)的時(shí)間Table 5 Time spent on mediamill(exp1) data set /s

4 結(jié)語

本文針對使用非線性核的SVM多標(biāo)簽分類算法在大規(guī)模多標(biāo)簽數(shù)據(jù)集上的使用將受到繁重計(jì)算復(fù)雜度嚴(yán)重限制的問題，提出了采用分而治之策略的快速多標(biāo)簽支持向量機(jī)分類算法(MLDC-SVM)。它通過采用DEC方法能夠更好地處理標(biāo)簽數(shù)據(jù)不平衡問題。這些都將極大地提高該算法在大規(guī)模多標(biāo)簽數(shù)據(jù)集上的適用性。在兩組公共的大規(guī)模多標(biāo)簽數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，MLDC-SVM分類算法在極大提高訓(xùn)練和測試速度的同時(shí)能夠取得與ML-LIBSVM分類算法相近的分類性能，并且優(yōu)于ML-CVM和ML-BVM分類算法的分類性能。未來的工作是改進(jìn)該算法，使其能夠利用標(biāo)簽的相關(guān)性信息來提高分類性能。