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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3 改進的算法

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

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

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

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

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

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

④設(shè)計總的分類模型.

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

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

φ

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

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

3.1.3 MIMLSVM+的改進

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

經(jīng)過上述改進, SVM的優(yōu)化變?yōu)橐陨蠁栴}(MIMLSVM+步驟2).

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

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

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

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

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

3.2 ELDCC(Ensembles of Label Dependencies Classifier Chain)

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

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

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

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

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

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

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

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

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

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

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

其中Xi表示第i個包, xij為包Xi中的第j個示例, yk是第k個基分類器的輸出標(biāo)簽. 鑒于ECC算法是解決單示例多標(biāo)簽問題的算法, 本篇論文采用與ECC-MIMLSVM+算法相同的策略, 對ECC算法加以改造使其適用于解決多示例多標(biāo)簽問題. 即在第k個基分類器訓(xùn)練之前, 首先將標(biāo)簽yk-1擴展為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個基分類器.第四步: 置信度的計算.

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

第五步: 確定閾值t.

第六步: 計算樣本的最終輸出.

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

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

?

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

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

?

4 實驗

4.1 實驗設(shè)置

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

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

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

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

這四種多示例多標(biāo)簽算法的評價指標(biāo)采用五個標(biāo)準(zhǔn)的多示例評價指標(biāo): one-error、average precision、hamming loss、ranking loss和coverage. 對于這五個評價指標(biāo), 簡單來說one-error、hamming loss、ranking loss和coverage這四個值越小說明算法效果越好; 而average precision則值越大說明算法效果越好.

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

4.2 實驗結(jié)果

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

表3 場圖形圖像樣本集實驗結(jié)果

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

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

表4 文本樣本集實驗結(jié)果

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

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

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

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

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

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

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

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

5 總結(jié)

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

10.15888/j.cnki.csa.005686