基于標(biāo)記依賴(lài)關(guān)系集成分類(lèi)器鏈的多示例多標(biāo)簽支持向量機(jī)算法①

李村合, 王文杰(中國(guó)石油大學(xué) 計(jì)算機(jī)與通信工程學(xué)院, 青島 266580)

基于標(biāo)記依賴(lài)關(guān)系集成分類(lèi)器鏈的多示例多標(biāo)簽支持向量機(jī)算法①

李村合, 王文杰
(中國(guó)石油大學(xué) 計(jì)算機(jī)與通信工程學(xué)院, 青島 266580)

ECC-MIMLSVM+是多示例多標(biāo)簽學(xué)習(xí)框架下一種算法, 該算法提出了一種基于分類(lèi)器鏈的方法, 但其沒(méi)有充分考慮到標(biāo)簽之間的依賴(lài)關(guān)系, 而且當(dāng)標(biāo)簽數(shù)目的增多, 子分類(lèi)器鏈長(zhǎng)度增加, 使得誤差傳播問(wèn)題凸顯.因此針對(duì)此問(wèn)題, 提出了一種改進(jìn)算法, 將ECC-MIMLSVM+算法和標(biāo)簽依賴(lài)關(guān)系相結(jié)合, 設(shè)計(jì)成基于標(biāo)記依賴(lài)關(guān)系集成分類(lèi)器鏈(ELDCT-MIMLSVM+)來(lái)加強(qiáng)標(biāo)簽間信息聯(lián)系, 避免信息丟失, 提高分類(lèi)的準(zhǔn)確率. 通過(guò)實(shí)驗(yàn)將本文算法與其他算法進(jìn)行了對(duì)比, 實(shí)驗(yàn)結(jié)果顯示, 本文算法取得了良好的效果.

多示例多標(biāo)簽; 支持向量機(jī); 標(biāo)簽依賴(lài)關(guān)系; 分類(lèi)器鏈

1 引言

在傳統(tǒng)監(jiān)督學(xué)習(xí)[1]中, 每個(gè)對(duì)象用一個(gè)示例進(jìn)行描述, 該示例隸屬于一個(gè)概念標(biāo)簽, 在該框架下對(duì)象不具有歧義性. 在多示例學(xué)習(xí)[2]中, 每個(gè)對(duì)象由多個(gè)示例進(jìn)行描述, 并且同時(shí)隸屬于一個(gè)概念標(biāo)簽, 其描述對(duì)象的內(nèi)容存在歧義性. 在多標(biāo)簽[3,4]學(xué)習(xí)中, 每個(gè)對(duì)象由單個(gè)示例描述, 并且隸屬于多個(gè)概念標(biāo)簽, 其描述對(duì)象的概念存在歧義性. 然而在現(xiàn)實(shí)生活中的對(duì)象通常同時(shí)具有內(nèi)容、概念兩方面的歧義性, 因此出現(xiàn)了多示例多標(biāo)簽學(xué)習(xí)框架(MIML)[5,6].

2007年, 南京大學(xué)的周志華等人提出兩個(gè)多示例多標(biāo)簽支持向量機(jī)算法, 分別是MIMLBOOST 算法[6]和MIMLSVM算法[7].

2010年, 河海大學(xué)的張敏靈提出MIML-KNN[8]算法, 該算法在K-NN算法基礎(chǔ)上的改進(jìn)算法并應(yīng)用于MIML學(xué)習(xí). 該算法不僅考慮一個(gè)樣本的近鄰(稱(chēng)為neighbors), 還考慮了以該樣本為近鄰的樣本.

2011年, 美國(guó)的Nguyen提出的一種新的解決MIML學(xué)習(xí)問(wèn)題的SVM算法, SISL-MIML算法[9]. 該算法假設(shè)MIML樣本中的每一個(gè)示例只有一個(gè)最準(zhǔn)確的與之對(duì)應(yīng)的標(biāo)簽, 因?yàn)樵趥鹘y(tǒng)的MIML樣本退化為SISL樣本時(shí)會(huì)丟失信息, 即會(huì)標(biāo)錯(cuò)很多示例的標(biāo)簽.

2013年, 哈爾濱工業(yè)大學(xué)的Wu等人提出一種基于馬爾科夫鏈的MIML學(xué)習(xí)算法[10].

鑒于支持向量機(jī)(SVM)[11]在解決小樣本、非線(xiàn)性及高維模式識(shí)別問(wèn)題中的優(yōu)勢(shì), 因此在多示例多標(biāo)簽學(xué)習(xí)框架下的許多算法都采用了支持向量機(jī)技術(shù), 如E-MIMLSVM+算法[12]等.

然而這些算法通常基于退化策略, 該策略會(huì)導(dǎo)致退化過(guò)程中有效信息的丟失, 降低了分類(lèi)準(zhǔn)確率. ECC算法[13,14]是對(duì)所有的CC模型進(jìn)行集成學(xué)習(xí). 雖然在一定程度上改善退化過(guò)程中信息丟失, 但當(dāng)標(biāo)簽數(shù)目的增多, 子分類(lèi)器鏈長(zhǎng)度增加, 使得誤差傳播問(wèn)題凸顯.

因此本文提出新算法, 改進(jìn)了ECC算法誤差傳播凸顯問(wèn)題,提高分類(lèi)準(zhǔn)確率. ELDCT-MIMLSVM+算法是在訓(xùn)練過(guò)程中依次加入依賴(lài)程度最大的標(biāo)簽信息.主要目的在于減少其他無(wú)關(guān)標(biāo)簽的干擾, 避免了信息丟失, 同時(shí)也降低因增加子分類(lèi)鏈而使誤差傳播凸顯的問(wèn)題, 從而達(dá)到較好的分類(lèi)效果.

本文的組織結(jié)構(gòu)如下: 第二部分介紹相關(guān)工作,第三部分提出改進(jìn)算法, 第四部分給出了實(shí)驗(yàn)結(jié)果,第五部分進(jìn)行了總結(jié).

2 相關(guān)工作

在傳統(tǒng)監(jiān)督學(xué)習(xí)中, 每個(gè)對(duì)象由一個(gè)示例描述并且隸屬于一個(gè)概念標(biāo)簽, 在該學(xué)習(xí)框架下, 對(duì)象與示例和標(biāo)簽都是一一對(duì)應(yīng)的關(guān)系[15], 學(xué)習(xí)對(duì)象不具有歧義性. 其通過(guò)已有的部分輸入數(shù)據(jù)與輸出標(biāo)簽生成一個(gè)函數(shù), 建立輸入輸出數(shù)據(jù)間的關(guān)系, 將輸入數(shù)據(jù)映射到合適的輸出.

在多示例學(xué)習(xí)中, 每個(gè)對(duì)象由多個(gè)示例描述并且隸屬于一個(gè)概念標(biāo)簽, 其主要考查了對(duì)象在概念空間的歧義性. 多示例學(xué)習(xí)在給定的多示例數(shù)據(jù)集合上學(xué)習(xí)一個(gè)映射函數(shù):2x→其中x∈x(j =1,2,...,ni)是第i個(gè)包Xi中的一個(gè)示例, 每個(gè)包?X是個(gè)示例的集合, y∈{-1,+1}是包X的所屬類(lèi)別. ii

在多標(biāo)簽學(xué)習(xí)中, 每個(gè)對(duì)象由單個(gè)示例描述并且同時(shí)隸屬于多個(gè)概念標(biāo)簽, 其主要考察對(duì)象在語(yǔ)義空間的歧義性. 多標(biāo)簽學(xué)習(xí)在給定的多標(biāo)簽數(shù)據(jù)集合上學(xué)習(xí)一個(gè)映射函數(shù)x→, 其中x是單個(gè)示例描述的對(duì)象, Y?Yii是對(duì)象i所屬的類(lèi)別標(biāo)簽的集合{...},∈Y(k =1,2,...,l). i在現(xiàn)實(shí)生活中, 對(duì)象往往同時(shí)具有概念歧義性和語(yǔ)義歧義性, 為同時(shí)考察這兩方面的歧義性, 多示例多標(biāo)簽學(xué)習(xí)框架應(yīng)運(yùn)而生. MIML既不像多標(biāo)簽學(xué)習(xí)中那樣將對(duì)象僅用單一示例描述引起對(duì)象概念信息的丟失[16], 也不像多示例學(xué)習(xí)中那樣僅將對(duì)象劃分到單個(gè)預(yù)定義的語(yǔ)義類(lèi)別引起對(duì)象語(yǔ)義信息的丟失. 在該框架下, 每個(gè)對(duì)象由多個(gè)示例表示同時(shí)隸屬于多個(gè)概念標(biāo)簽[17], 因此它能夠充分考慮到輸入輸出空間中的歧義性, 對(duì)歧義性對(duì)象進(jìn)行有效地學(xué)習(xí). 多示例多標(biāo)簽學(xué)習(xí)在給定的多示例多標(biāo)簽數(shù)據(jù)集合上學(xué)習(xí)一個(gè)從示例集合X到標(biāo)簽集合上的映射函數(shù)f→, 其中i?X是個(gè)示例∈x(j =1,2,...,n)的集合i,,...,,?Y是與包相關(guān)的類(lèi)別標(biāo)簽∈Y(k =1,2,...,l)的集合{,,...,}. 傳i統(tǒng)監(jiān)督問(wèn)題、多示例問(wèn)題、多標(biāo)簽問(wèn)題都是多示例多標(biāo)簽問(wèn)題的特殊表示形式, 上述三種問(wèn)題都可在多示例多標(biāo)簽框架下進(jìn)行求解.

目前, 在MIML框架下問(wèn)題的解決方式主要有兩種:

一種是基于退化的策略, 將多示例多標(biāo)簽問(wèn)題退化為多示例或多標(biāo)簽, 再轉(zhuǎn)化為傳統(tǒng)監(jiān)督學(xué)習(xí)框架下的等價(jià)形式進(jìn)行求解, 如MIMLSVM[7]、MIMLBOOST[6]等算法, 兩者分別以多標(biāo)簽學(xué)習(xí)和多示例學(xué)習(xí)為橋梁, 將多示例多標(biāo)簽問(wèn)題退化為傳統(tǒng)監(jiān)督問(wèn)題進(jìn)行求解. 但這兩種方式在退化過(guò)程中都會(huì)引起有效信息的丟失, 導(dǎo)致分類(lèi)效果不理想, 而且針對(duì)大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題時(shí)有明顯不足;

另一種是考察示例與標(biāo)簽之間的關(guān)系, 直接設(shè)計(jì)針對(duì)多示例多標(biāo)簽樣本的學(xué)習(xí)算法, 如M3MIML算法[18]. 但這種算法設(shè)計(jì)難度大, 樣本訓(xùn)練時(shí)間長(zhǎng), 而且實(shí)驗(yàn)證明分類(lèi)效果不好.

Ying-xin Li和Shui-wang Ji等在果蠅基因表達(dá)模式注釋的問(wèn)題中提出基于支持向量機(jī)的多示例多標(biāo)簽算法的MIMLSVM+算法[12], 這是一種針對(duì)大規(guī)模學(xué)習(xí)問(wèn)題提出的算法. 該算法具有較低的訓(xùn)練時(shí)間和較好的分類(lèi)效果, 但其沒(méi)有考慮標(biāo)簽之間的依賴(lài)性, 忽略了標(biāo)簽內(nèi)在聯(lián)系, 影響力分類(lèi)準(zhǔn)確率.

3 改進(jìn)的算法

3.1 MIMLSVM+算法(Multi-instance Multi-label SVM for Large-scale Learning)

MIMLSVM+算法同MIMLSVM和MIMLBOOST算法相似是一種基于退化的算法, MIMLSVM+將多示例多標(biāo)簽問(wèn)題退化為多示例單標(biāo)簽問(wèn)題進(jìn)行求解, 該算法主要針對(duì)大規(guī)模的數(shù)據(jù)問(wèn)題. MIMLSVM+算法每次為單個(gè)標(biāo)簽訓(xùn)練分類(lèi)器, 收集所有具有該標(biāo)簽的包為正包, 不具有該標(biāo)簽的包為負(fù)包, 得到一系列二類(lèi)分類(lèi)任務(wù), 每個(gè)任務(wù)利用支持向量機(jī)處理. 為處理類(lèi)不平衡問(wèn)題, MIMLSVM+采用不同的懲罰參數(shù)分別應(yīng)用于正類(lèi)和負(fù)類(lèi)的松弛條件.

3.1.1 MIMLSVM+算法主要包括以下步驟:

①將多示例多標(biāo)簽退化為二分問(wèn)題, 對(duì)每個(gè)二分類(lèi)問(wèn)題設(shè)計(jì)SVM算法進(jìn)行處理

②處理數(shù)據(jù)不平衡問(wèn)題, 在訓(xùn)練過(guò)程中優(yōu)化SVM, 采用“rescaling”(尺度改變)方法來(lái)調(diào)節(jié)懲罰參數(shù)大小.

③不同的核函數(shù)的計(jì)算結(jié)果不同, 選取恰當(dāng)?shù)暮撕瘮?shù).

④設(shè)計(jì)總的分類(lèi)模型.

3.1.2 MIMLSVM+的懲罰參數(shù)

對(duì)于每個(gè)標(biāo)簽Yy∈, 若1),(=yXiφ, 則說(shuō)明包iX具有標(biāo)簽y, 若1-),(=yXi

φ

, 表明包iX不具有標(biāo)簽y. MIMLSVM+的相關(guān)優(yōu)化問(wèn)題為:

其中, φ（Xi）是將示例包Xi映射到核空間的映射函數(shù), φ（Xi,y）表示包Xi是否具有標(biāo)簽y. εi是hinge loss, n是示例包的數(shù)目, w和b是用于表示核空間線(xiàn)性描述函數(shù)的參數(shù). C+和C-分別為正類(lèi)和負(fù)類(lèi)的懲罰因子.

3.1.3 MIMLSVM+的改進(jìn)

為了增強(qiáng)分類(lèi)模型的容錯(cuò)率和減少訓(xùn)練樣本被錯(cuò)誤分類(lèi), 我們對(duì)算法引入非負(fù)松弛變量ξiy. 引入之后將公式轉(zhuǎn)化為:

經(jīng)過(guò)上述改進(jìn), SVM的優(yōu)化變?yōu)橐陨蠁?wèn)題(MIMLSVM+步驟2).

3.1.4 核函數(shù)MIMLSVM+算法采用多示例核函數(shù)[19]KMI( X,X′):

該核函數(shù)是通過(guò)對(duì)標(biāo)準(zhǔn)設(shè)置內(nèi)核函數(shù)

取合適的p值得到的, 其中p≥1, K(.，.)為示例級(jí)別的內(nèi)核.

為進(jìn)一步利用本地視覺(jué)特征和空間特征的信息, MIMLSVM+算法重新定義了核函數(shù)

其中||xt0-xk0||衡量了兩個(gè)圖像補(bǔ)丁間本地視覺(jué)特征的相似性, ||xti-衡量了兩個(gè)圖像補(bǔ)丁間的的空間距離. 通過(guò)調(diào)節(jié)參數(shù)γ1和γ2可對(duì)本地視覺(jué)特征和空間信息進(jìn)行顯式利用. MIMLSVM+的核函數(shù)十分恰當(dāng), 所以我們采用其核函數(shù). 最終的判別函數(shù)為:

3.2 ELDCC(Ensembles of Label Dependencies Classifier Chain)

MIMLSVM+算法為每個(gè)標(biāo)簽建立一個(gè)二類(lèi)分類(lèi)器, 忽略了標(biāo)簽之間的聯(lián)系信息, 退化過(guò)程中信息丟失, 因此本篇論文提出了基于標(biāo)記依賴(lài)關(guān)系的多示例多標(biāo)簽分類(lèi)器鏈算法. 本篇文章采用ECC技術(shù)對(duì)標(biāo)簽間的聯(lián)系信息加以利用, 并依據(jù)某種策略計(jì)算標(biāo)簽間的依賴(lài)程度值, 根據(jù)獲得的標(biāo)簽依賴(lài)程度組織基分類(lèi)器鏈.

ELDCC主要目標(biāo)是依據(jù)標(biāo)簽間的依賴(lài)程度的大小依次訓(xùn)練基分類(lèi)器, 在訓(xùn)練時(shí)依次加入依賴(lài)程度最大的標(biāo)簽信息, 以達(dá)到較好的分類(lèi)效果. 這樣在保持了ECC算法低時(shí)間復(fù)雜度、低空間復(fù)雜度優(yōu)勢(shì)的同時(shí),又能夠?qū)?biāo)簽間的依賴(lài)關(guān)系加以利用, 進(jìn)一步提高分類(lèi)的準(zhǔn)確率. 該算法不僅能降低時(shí)間、空間復(fù)雜度, 還能消除標(biāo)簽順序?qū)Ψ诸?lèi)的影響.

以下是ELDCC算法的主要步驟:

第一步: 計(jì)算標(biāo)簽間的依賴(lài)程度值.

首先依據(jù)表1統(tǒng)計(jì)數(shù)據(jù)集中相應(yīng)樣本的數(shù)目. 其中N表示數(shù)據(jù)集中的樣本總數(shù), 各個(gè)變量(a/b/c/d)對(duì)應(yīng)在數(shù)據(jù)集中與兩個(gè)標(biāo)記相關(guān)的樣本的統(tǒng)計(jì)量, 例如a表示數(shù)據(jù)集中同時(shí)與標(biāo)簽i和標(biāo)簽j相關(guān)的樣本個(gè)數(shù)．

表1 標(biāo)記和的關(guān)聯(lián)表

獲得表1求得的變量值, 依據(jù)公式(1)量化標(biāo)簽i與標(biāo)簽j的依賴(lài)程度.

第二步: 隨機(jī)選擇m個(gè)標(biāo)簽作為初始根節(jié)點(diǎn), 利用prim算法生成m個(gè)有序分類(lèi)器鏈.

取依賴(lài)程度值的倒數(shù), 利用prim算法獲得最小生成樹(shù). 集合U是已加入鏈中的標(biāo)簽, 集合V是待加入標(biāo)簽, 每次從集合V中選取到集合U中依賴(lài)程度最大的標(biāo)簽, 并將其加入到集合U中, 更新集合V到集合U中的依賴(lài)程度值, 循環(huán)直到集合V中所有的標(biāo)簽都加入到集合U中. 將依次加入集合U中標(biāo)簽結(jié)點(diǎn)的順序作為一個(gè)分類(lèi)器鏈的訓(xùn)練標(biāo)簽的順序.

第三步: 利用訓(xùn)練樣本訓(xùn)練基分類(lèi)器.

假設(shè)共有L個(gè)標(biāo)簽, 依據(jù)第二步獲得的標(biāo)簽順序C（c1,c2,.....cL）為每個(gè)標(biāo)簽構(gòu)建一個(gè)二類(lèi)分類(lèi)器, L個(gè)二類(lèi)分類(lèi)器組成一個(gè)有序分類(lèi)器鏈. 分類(lèi)器鏈中第一個(gè)基分類(lèi)器的輸入為初始樣本, 其余基分類(lèi)器的輸入為上一個(gè)基分類(lèi)器的輸入樣本以及該樣本相應(yīng)輸出標(biāo)簽的組合, 即:

其中Xi表示第i個(gè)包, xij為包Xi中的第j個(gè)示例, yk是第k個(gè)基分類(lèi)器的輸出標(biāo)簽. 鑒于ECC算法是解決單示例多標(biāo)簽問(wèn)題的算法, 本篇論文采用與ECC-MIMLSVM+算法相同的策略, 對(duì)ECC算法加以改造使其適用于解決多示例多標(biāo)簽問(wèn)題. 即在第k個(gè)基分類(lèi)器訓(xùn)練之前, 首先將標(biāo)簽yk-1擴(kuò)展為d維向量y=（y,y,......,y）T（k=1,...,L）, 其中d為示例的維k-1k-1k-1k-1d數(shù), L為標(biāo)簽的數(shù)目.

最終基于新的數(shù)據(jù)集合訓(xùn)練第k個(gè)基分類(lèi)器.第四步: 置信度的計(jì)算.

為取得更準(zhǔn)確的分類(lèi)結(jié)果, ELDCC對(duì)多個(gè)鏈的輸出結(jié)果進(jìn)行匯總. 假設(shè)有m個(gè)有序分類(lèi)器鏈:為m個(gè)有序分類(lèi)器鏈上的輸出. h1,h2......,hm.....y根據(jù)公式計(jì)算該樣本在所有分類(lèi)器鏈的平均值.

第五步: 確定閾值t.

第六步: 計(jì)算樣本的最終輸出.

利用第四步的置信度, 結(jié)合第五步的閾值函數(shù)計(jì)算該樣本的最終輸出標(biāo)簽. 當(dāng)?shù)?(,.....,....,) j個(gè)標(biāo)簽的置信度大于或等于閾值t時(shí), 第j個(gè)標(biāo)簽的最終輸出為1, 表明該樣本具有第j個(gè)標(biāo)簽, 否則該樣本在標(biāo)簽j上的輸出為0, 表明該樣本不具有標(biāo)簽j.

對(duì)于一個(gè)未知標(biāo)簽的測(cè)試樣本X, 將樣本輸入到m個(gè)分類(lèi)器鏈中. 對(duì)應(yīng)其中的一個(gè)分類(lèi)器鏈, 在進(jìn)行第j個(gè)標(biāo)簽預(yù)測(cè)時(shí), 獲得對(duì)應(yīng)鏈第j-1個(gè)基分類(lèi)器的輸出值并進(jìn)行d維擴(kuò)展獲得新的樣本將該樣本代入第j個(gè)標(biāo)簽的分類(lèi)函數(shù)中fj(X′), 獲得樣本X關(guān)于第j個(gè)標(biāo)簽的估計(jì)值yj. 對(duì)于所有的有序分類(lèi)器鏈都重復(fù)上述過(guò)程,將m個(gè)分類(lèi)器鏈的結(jié)果進(jìn)行計(jì)算獲得置信向量, 利用置信向量和閾值確定樣本的最終輸出標(biāo)簽.改進(jìn)算法的偽代碼:

?

1) 將標(biāo)簽數(shù)據(jù)集O隨機(jī)分N次, 得到不同的n個(gè)數(shù)據(jù)集L（ii=1,2,…,N）.

2) 循環(huán)訓(xùn)練集S=｛（Xi, Yi）｝（i=1,2,…,n）, 計(jì)算多示

?

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

本文使用周志華等人提供的兩個(gè)數(shù)據(jù)集(即表2圖像樣本集和文本樣本集特征)進(jìn)行實(shí)驗(yàn).

表2的scene數(shù)據(jù)集是圖形圖像數(shù)據(jù)集. 該數(shù)據(jù)集包含2000個(gè)場(chǎng)景圖像, 其中每個(gè)圖像都被分配一組標(biāo)簽. 總共5個(gè)類(lèi)別, 分別是海、沙漠、山、樹(shù)和日落. 其中單標(biāo)簽樣本數(shù)目1544個(gè), 約占整個(gè)樣本集數(shù)量77%左右; 雙標(biāo)簽441, 約占整個(gè)樣本集數(shù)量的22%左右,同時(shí)屬于三個(gè)類(lèi)的樣本數(shù)目極少. 平均每個(gè)樣本與1.24±0.44個(gè)類(lèi)標(biāo)簽有關(guān)聯(lián). 每幅圖片所對(duì)應(yīng)的多示例多標(biāo)簽樣本的示例數(shù)為9, 本文用一個(gè)15維的特征向量表示每一個(gè)示例[20].

表二的Reuters是文本數(shù)據(jù)集, 從Reuters-21578樣本集[21]中獲得. 我們基于最常用的7個(gè)類(lèi), 刪除部分只屬于一個(gè)類(lèi)別的文本, 再刪除其中沒(méi)有類(lèi)別和沒(méi)有正文的文本, 總共得到8848個(gè)文本. 抽出一部分單標(biāo)簽樣本和所有雙標(biāo)簽和三標(biāo)簽樣本, 得到該樣本集所包含2000個(gè)文本. 屬于多個(gè)類(lèi)的文本數(shù)占該數(shù)據(jù)集的15%左右, 平均每個(gè)文本所屬的類(lèi)別數(shù)是1.15±0.37.每個(gè)文本通過(guò)滑動(dòng)窗口術(shù)用一組實(shí)例向量表示, 滑動(dòng)窗口的大小設(shè)置為50. 包中的示例采取基于詞頻的詞袋模型進(jìn)行表示, 將詞頻為前3%的詞匯予以保留[22],最終包中的每個(gè)示例都由243維的特征向量進(jìn)行表示.

把本文提出的ELDCT-MIMLSVM+算法跟、MIMLSVM+、MIMLBOOST與MIMLSVM算法進(jìn)行對(duì)比. MIMLBOOST和MIMLSVM算法的參數(shù)分別根據(jù)文獻(xiàn)[6]和[12]設(shè)置為它們的最佳值, MIMLSVM的高斯核為γ=0.22, MIMLBOOST的boosting rounds的值設(shè)為25. 為了保證實(shí)驗(yàn)客觀(guān)正確, ELDCT-MIMLSVM+算法和MIMLSVM+算法的gamma=le-5. 比較四種算法的平均分類(lèi)表現(xiàn).

這四種多示例多標(biāo)簽算法的評(píng)價(jià)指標(biāo)采用五個(gè)標(biāo)準(zhǔn)的多示例評(píng)價(jià)指標(biāo): one-error、average precision、hamming loss、ranking loss和coverage. 對(duì)于這五個(gè)評(píng)價(jià)指標(biāo), 簡(jiǎn)單來(lái)說(shuō)one-error、hamming loss、ranking loss和coverage這四個(gè)值越小說(shuō)明算法效果越好; 而average precision則值越大說(shuō)明算法效果越好.

表2 圖像樣本集和文本樣本集特征

4.2 實(shí)驗(yàn)結(jié)果

表3和表4分別顯示了四種不同的多示例多標(biāo)簽算法在圖像數(shù)據(jù)集和文本數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

表3 場(chǎng)圖形圖像樣本集實(shí)驗(yàn)結(jié)果

從表3可以看出, 在圖像數(shù)據(jù)集上, ELDCT-MIMLSVM+算法略好于MIMLSVM+, 對(duì)于MIMLBOOST和MIMLSVM有明顯的優(yōu)勢(shì).

圖形圖像樣本的分類(lèi)復(fù)雜, 計(jì)算數(shù)據(jù)量大. MIMLSVM+算法主要是為大規(guī)模機(jī)器學(xué)習(xí)設(shè)計(jì)的算法, 采用了SVM來(lái)提高分類(lèi), 所以其效率要好于MIMLBOOST和MIMLSVM. ELDCT-MIMLSVM+采用了分類(lèi)器鏈技術(shù), 也是將問(wèn)題退化為傳統(tǒng)的機(jī)器學(xué)習(xí). ELDCT-MIMLSVM+與其它算法不同在于, 在退化過(guò)程中依次加入標(biāo)簽之間的依賴(lài)關(guān)系, 增強(qiáng)了標(biāo)簽之間聯(lián)系, 所以可以取得比較好的效果.

表4 文本樣本集實(shí)驗(yàn)結(jié)果

從表4可以看出, 在文本數(shù)據(jù)集上, ELDCT-MIMLSVM+算法的前四項(xiàng)指標(biāo)均小于其他各項(xiàng)算法, Average precision大于其他算法, 所有指標(biāo)在四種算法中表現(xiàn)最佳.

文本分類(lèi)相對(duì)簡(jiǎn)單, 各算法之間差距比較小. SVM在二分問(wèn)題上有巨大的優(yōu)勢(shì), ELDCT-MIMLSVM+采用了SVM技術(shù), 將問(wèn)題二分然后再求解, 體現(xiàn)SVM優(yōu)勢(shì), 效果明顯.

表5 算法在圖像數(shù)據(jù)集上的訓(xùn)練時(shí)間對(duì)比

從表5可以看出, 在圖形圖像數(shù)據(jù)集上ELDCT-MIMLSVM+的訓(xùn)練時(shí)間和測(cè)試時(shí)間比MIMLSVM+差,略微優(yōu)于MIMLSVM, 對(duì)MIMLBOOST有比較明顯的優(yōu)勢(shì).

ELDCT-MIMLSVM+采用分類(lèi)器鏈設(shè)計(jì)模式, 當(dāng)子分類(lèi)器鏈增加, 耗時(shí)就會(huì)比較多. 更重要的是ELDCT-MIMLSVM+比MIMLSVM多一步計(jì)算標(biāo)簽之間依賴(lài)關(guān)系, 這增加了計(jì)算量. 所以在訓(xùn)練時(shí)間上會(huì)比MIMLSVM+多.

表6 四種算法在文本數(shù)據(jù)集上的訓(xùn)練時(shí)間對(duì)比

從表6可以看出, 在文本數(shù)據(jù)集上, MIMLSVM+的訓(xùn)練時(shí)間和測(cè)試時(shí)間最少, ELDCT-MIMLSVM+的訓(xùn)練時(shí)間小于MIMLSVM, 但測(cè)試時(shí)間比MIMLSVM多. 效率最低的是MIMLBOOST.

與在圖形圖像數(shù)據(jù)集一樣, ELDCT-MIMLSVM+多一步計(jì)算標(biāo)簽依賴(lài)關(guān)系, 所以耗時(shí)較多, 但這一步驟增強(qiáng)標(biāo)簽之間聯(lián)系, 提高了分類(lèi)準(zhǔn)確率. 如果在強(qiáng)調(diào)準(zhǔn)確率而不是對(duì)時(shí)間有特別嚴(yán)格的要求, ELDCT-MIMLSVM+算法是首選.

5 總結(jié)

從上面數(shù)據(jù)分析可知, 對(duì)于圖像數(shù)據(jù)集和文本數(shù)據(jù)集, 在保證訓(xùn)練時(shí)間和測(cè)試時(shí)間的前提下, ELDCT-MIMLSVM+算法的準(zhǔn)確率略?xún)?yōu)于MIMLSVM+,明顯高于另外兩種算法, 并且ELDCT-MIMLSVM+在各項(xiàng)指標(biāo)中表現(xiàn)優(yōu)異. 因此, 我們可推出結(jié)論: ELDCT-MIMLSVM+算法在訓(xùn)練過(guò)程中可以依據(jù)標(biāo)簽依賴(lài)關(guān)系, 逐步加入依賴(lài)程度較大標(biāo)簽的信息來(lái)輔助分類(lèi)器訓(xùn)練學(xué)習(xí), 從而進(jìn)一步提高分類(lèi)器分類(lèi)的準(zhǔn)確率.

1 Kotsiantis SB, Zaharakis I, Pintelas P. Supervised machine learning: A review of classification techniques. Informatica, 2007, 31(3): 249–268

2 Dietterich TG, Lathrop RH, Lozano-Pérez T. Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence, 1997, 89(1-2): 31–71.

3 Boutell MR, Luo J, Shen X, Brown CM. Learning multi-label scene classification. Pattern Recognition, 2004, 37(9): 1757–1771.

4 Schapire RE, Singer Y. BoosTexter: A boosting-based system for text categorization. Machine Learning, 2000, 39(2-3): 135–168.

5 Zhou ZH. A Framework for machine learning with ambiguous objects. Proc. Brain Informatics, International Conference(BI 2009). Beijing, China. 2009. 5819. 6–6

6 Zhou ZH, Zhang ML, Huang SJ, et al. Multi-instance multi-label learning. Artificial Intelligence, 2012, 176(1): 2291–2320

7 Zhou ZH, Zhang ML. Multi-instance Multi-label learning with application to scene classification. The Neural Information Processing Systems, 2006: 1609–1616.

8 Zhang ML. A k-nearest neighbor based multi-instance multi-label learning algorithm. 22ND International Conference on Tools with Artificial Intelligence. 2010, 2. 207–212.

9 Nguyen N. A new SVM approach to multi-instance multi-label learning. 2010 IEEE International Conference on Data Mining. 2010. 109.

10 Wu QY, Ng MK, Ye YM. Markov-MIML: A Markov chain-based multi-instance multi-label learning algorithm. Knowledge and Information System, 2013, 37(1): 83–104.

11 Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, 1995.

12 Li YX, Ji SW, Kumar S, Ye JP, Zhou ZH. Drosophila gene expression pattern annotation through multi-instance multi-label learning. Trans. on Computational Biology and Bioinformatics, 2012: 98–111.

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

14 Briggs F, Fern XZ, Raich R. Context-aware MIML instance annotation: exploiting label correlations with classifier chains. Knowledge and Information Systems, 2015, 43(1): 53–79

15 Platt JC. Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods-Support Vector Rning. MIT Press, 1999: 185–208

16 Gǎrtner T, Flach PA, Smola AJ. Multi-instance kernels. Proc. of the 19th Intenational Conference on Machine Learning. Sydney, Australia. 2002. 179–186.

17 Yakhnenko O, Honavar V. Multi-instance multi-label learning for image classification with large vocabularies. BMVC. 2011. 1–12

18 Pei Y, Fern XZ. Constrained instance clustering in multi-instance multi-label learning. Pattern Recognition Letters, 2014, 37(1): 107–114.

19 Zhang ML, Zhou ZH. M3MIML: A maximum margin method for multi-instance multi-label learning. Proc. of the 8th IEEE International Conference on Data Mining (ICDM’08). Pisa, Italy. 2008. 688–697.

20 Haussler D. Convolution kernels on discrete structures, [Technical Report]. UCSC-CRL-99-10. Dept. of Computer Science, Univ. of California at Santa Cruz. Santa Cruz, CA. July 1999.

21 Sebastiani F. Machine learning in automated text categorization. ACM Computing Surveys, 2002, 34(1): 1–47.

22 Andrews S, Tsochantaridis I, Hofmann T. Support vector machines for multiple-instance learning. Advances 696 in Neural Information Processing Systems 15, 2003: 561–568.

23 Yang Y, Pedersen JO. A comparative study on feature selection in text categorization. Proc. of the 14th International Conference on Machine Learning. Nashville, TN. 1997. 412–420.

Multi-Instance Multi-Label Support Vector Machine Algorithm Based on Labeled Dependency Relation Ensemble Classifier Chain

LI Cun-He, WANG Wen-Jie
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China)

ECC-MIMLSVM+is an algorithm of multi-instance and multi-label learning framework. This algorithm proposes a method based on classifier chain, but it does not consider the dependencies between labels. When the number of tags increases, the length of the sub classifier chain also increases, making the error propagation problem prominent. Therefore, this paper presents a kind of improved algorithm, combining ECC-MIMLSVM+algorithm and the label dependencies. ELDCT-MIMLSVM+algorithm is designed, which is based on ensembles of label dependencies classifier chain to avoid the information loss and improve the classification accuracy. The experiment results show that the algorithm has good effect.

multi-instance multi-label; SVM; ensembles of label dependencies; classifier chains

2016-07-24;收到修改稿時(shí)間:2016-08-22

10.15888/j.cnki.csa.005686