一種基于決策樹(shù)的多示例學(xué)習(xí)算法

王　杰,　 蔡良健,　 高　瑜

(1. 鄭州大學(xué) 電氣工程學(xué)院　河南 鄭州450001； 2. 鄭州大學(xué) 信息工程學(xué)院　河南 鄭州 450001)

?

一種基于決策樹(shù)的多示例學(xué)習(xí)算法

王杰1, 蔡良健1, 高瑜2

(1. 鄭州大學(xué) 電氣工程學(xué)院河南 鄭州450001； 2. 鄭州大學(xué) 信息工程學(xué)院河南 鄭州 450001)

摘要：提出了一種基于決策樹(shù) C4.5 的多示例學(xué)習(xí)算法 C4.5-MI，通過(guò)拓展 C4.5的熵函數(shù)和信息增益比來(lái)適應(yīng)多示例學(xué)習(xí)框架.應(yīng)用梯度提升方法對(duì) C4.5-MI算法進(jìn)行優(yōu)化，得到效果更優(yōu)的GDBT-MI算法.與同類決策樹(shù)算法在benchmark數(shù)據(jù)集上進(jìn)行比較，結(jié)果表明，C4.5-MI 和 GDBT-MI 算法具有更好的多示例分類效果.

關(guān)鍵詞：多示例學(xué)習(xí); 決策樹(shù); 梯度提升; C4.5算法

0引言

1決策樹(shù)及 C4.5算法

決策樹(shù)的主要優(yōu)點(diǎn)是模型具有可讀性, 分類速度快, 應(yīng)用廣泛. 學(xué)習(xí)時(shí), 利用訓(xùn)練數(shù)據(jù), 根據(jù)損失函數(shù)最小化的原則建立決策樹(shù)模型;預(yù)測(cè)時(shí), 對(duì)新的數(shù)據(jù)利用決策樹(shù)模型進(jìn)行分類.C4.5 是 ID3 擴(kuò)展版， 它既可以處理連續(xù)和離散的量，也可以處理帶有缺失數(shù)據(jù)的數(shù)據(jù)集，分類效果比 ID3 更優(yōu).

C4.5 的生成算法[7]如下:

輸入：訓(xùn)練數(shù)據(jù)集D, 特征集A, 閾值ε; 輸出：決策樹(shù)T.

Step 1如果D中所有示例屬于同一類Ck, 則置T為單節(jié)點(diǎn)樹(shù), 并將Ck作為該節(jié)點(diǎn)的類, 返回T.

Step 2如果A=? , 則置T為單節(jié)點(diǎn)樹(shù), 并將D中示例數(shù)最大的類Ck作為該節(jié)點(diǎn)的類, 返回T.

Step 3否則, 計(jì)算A中各特征對(duì)D的信息增益比, 選擇信息增益比最大的特征Ag.

Step 4如果Ag的信息增益比小于閾值ε, 則置T為單節(jié)點(diǎn)樹(shù), 并將D中示例數(shù)最大的類Ck作為該節(jié)點(diǎn)的類, 返回T.

Step 5否則, 對(duì)Ag的每一可能值ai, 依Ag=ai將D分割為若干非空子集Di, 將Di中示例數(shù)最大的類作為標(biāo)記, 構(gòu)建子節(jié)點(diǎn), 由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)成樹(shù)T, 返回T.

Step 6對(duì)節(jié)點(diǎn)i, 以Di為訓(xùn)練集, 以A-{Ag} 為特征集, 遞歸地調(diào)用Step 1～5, 得到子樹(shù)Ti, 返回Ti.

2梯度提升決策樹(shù)算法

在梯度提升的每個(gè)階段， 1≤m≤M, 假設(shè)存在一個(gè)不完美的模型Fm, 給它增加一個(gè)估計(jì)值h(x)得到一個(gè)更好的模型Fm+1(x)=Fm(x)+h(x) . 梯度提升算法認(rèn)為一個(gè)好的h(x) 需要滿足如下等式：

Fm+1=Fm(x)+h(x)=y，

或

h(x)=y-Fm(x).

(1)

因此, 梯度提升不斷擬合余數(shù)式 (1), 每個(gè)Fm+1都試著去校正它的前一個(gè)Fm.

具體算法流程如下:

Step 2Form=1 toM:

② 訓(xùn)練時(shí)使用全部訓(xùn)練集,使一個(gè)基本的決策樹(shù)學(xué)習(xí)算法擬合偽余數(shù)rim.

④ 更新模型Fm(x)=Fm-1(x)+γmhm(x).

Step 3 輸出Fm(x) .

把決策樹(shù)(例如C4.5) 作為梯度提升的基本學(xué)習(xí)算法就得到梯度提升決策樹(shù)算法.

3C4.5-MI 和 GDBT-MI 算法

對(duì)于C4.5算法, 一顆決策樹(shù)的長(zhǎng)成是基于熵和相關(guān)準(zhǔn)則啟發(fā)式得到的. 假設(shè)有一個(gè)樣本集D包含p個(gè)正樣本和n個(gè)負(fù)樣本, 對(duì)于這個(gè)二分類的D的熵定義為

(2)

在 C4.5算法中用到了信息增益比, 即

gR(D(p,n),A)=g(D(p,n),A)/H(D(p,n)).

(3)

需要拓展式 (2)和式 (3)使其適應(yīng)多示例框架. 首先引入兩個(gè)函數(shù)α(D) 和β(D)，給定一個(gè)多示例訓(xùn)練集合D,α(D) 和β(D) 返回的是集合D中的正負(fù)包( 樣本) 個(gè)數(shù). 考慮到一個(gè)樣本是由多個(gè)示例構(gòu)成的,必須重新定義刻畫任意樣本集合的純度.

在多示例問(wèn)題中,本文的目標(biāo)是學(xué)習(xí)一個(gè)區(qū)分樣本正負(fù)的模型, 而不是區(qū)分某一個(gè)樣本中示例的正負(fù). 因此, 這里的純度不應(yīng)該定義在示例個(gè)數(shù)p和n上, 而應(yīng)該是定義在樣本集合D中包含正負(fù)包的個(gè)數(shù)α(D)和β(D)上.

多示例的熵定義為

多示例的信息增益比定義為

在一個(gè)決策樹(shù)中直接顯示多示例熵會(huì)得到異常復(fù)雜的樹(shù). 假如一個(gè)正包包含兩個(gè)示例, 根節(jié)點(diǎn)的左子樹(shù)代表第一個(gè)示例, 右子樹(shù)代表第二個(gè)示例. 如果左子樹(shù)成功地將第一個(gè)示例劃分為正的示例, 那么這個(gè)包( 樣本) 就可以判定為正包，因此推演右子樹(shù)劃分其他示例類型將毫無(wú)意義. 但是, 一個(gè)決策樹(shù)模型 (如C4.5) 利用多示例熵將會(huì)傾向把所有的示例都劃完為止, 這將會(huì)導(dǎo)致樹(shù)變得復(fù)雜.

為了避免這個(gè)缺點(diǎn),將推演過(guò)程修改如下：一旦一個(gè)正包中的示例被正確地劃分為正的示例, 移除包中余下的示例.只要一個(gè)子樹(shù)成功地為一個(gè)示例貼上正的包標(biāo)簽, 另外的一個(gè)示例就直接被移除. 基于多示例熵以及對(duì)以上樹(shù)生成的修剪, 經(jīng)典的決策樹(shù) C4.5就被拓展成多示例版本C4.5-MI.

為了得到更好的分類效果, 把 C4.5-MI 作為梯度提升方法的基本分類器就得到了GDBT-MI 算法.

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

表1　MUSK 數(shù)據(jù)集的一些特性

用兩個(gè)標(biāo)準(zhǔn)的多示例測(cè)試集 MUSK1 和 MUSK2 測(cè)試了C4.5-MI 和 GDBT-MI算法. MUSK數(shù)據(jù)集是用來(lái)模擬藥品分子的, MUSK2比 MUSK1含有更多的可能構(gòu)造.因此, MUSK2 比 MUSK1 更難準(zhǔn)確分類. MUSK 數(shù)據(jù)集的一些特性在表 1 中列出. Elephant、Tiger和 Fox 為三個(gè)圖像分類數(shù)據(jù)集.正包是包含某種動(dòng)物的圖片,負(fù)包是不包含該動(dòng)物的圖片. 這里的一個(gè)圖片就代表一個(gè)包( 樣本) , 包中含有圖像的子區(qū)域( 多示例).一個(gè)圖片是一個(gè)正包，則每個(gè)數(shù)據(jù)集包含100個(gè)正包和100個(gè)負(fù)包, 每個(gè)子區(qū)域看成表示為230 維向量的示例. 更多信息可見(jiàn)文獻(xiàn) [8].

為了獲得較好的可比性,通過(guò)十折交叉驗(yàn)證比較了 MITI, ID3-MI, C4.5-MI, GDBT-MI 四種算法. 表2中MSUK 數(shù)據(jù)集的結(jié)果取自于文獻(xiàn)[5—6], 其他的結(jié)果由作者根據(jù)文獻(xiàn)[5—6]實(shí)現(xiàn)了MITI和ID3-MI算法，并測(cè)定了它們?cè)贓lephant、Fox和Tiger三個(gè)數(shù)據(jù)集上的精度. 這幾種算法都是改進(jìn)的決策樹(shù)算法，測(cè)試結(jié)果見(jiàn)表2.可以看出，所提出的 C4.5-MI 算法要優(yōu)于 ID3-MI算法, 比MITI算法稍遜. MITI算法采用較為復(fù)雜的啟發(fā)式擴(kuò)建子樹(shù), 內(nèi)存開(kāi)銷和計(jì)算時(shí)間開(kāi)銷非常大, 而 C4.5-MI 算法構(gòu)建子樹(shù)較為簡(jiǎn)單明了, 計(jì)算量相對(duì)MITI 小很多，需要的內(nèi)存空間也不大， 同時(shí)能夠取得相對(duì)于ID3-MI算法不錯(cuò)的測(cè)試精度.

表2　4種算法在benchmark數(shù)據(jù)集的測(cè)試結(jié)果

圖1　隨著迭代次數(shù)的增加,GDBT-MI 算法的訓(xùn)練和測(cè)試誤差Fig.1　The train and test error of GDBT-MI as the the number of iteration increasing

在通過(guò)梯度提升算法之后, GDBT-MI算法的分類精度處于最好的位置,在除 MUSK2 以外的數(shù)據(jù)集上測(cè)試誤差都達(dá)到了最小.圖 1 記錄了GDBT-MI算法在MUSK1 和 MUSK2 數(shù)據(jù)集隨著提升迭代次數(shù)的增加輸出分類訓(xùn)練和測(cè)試精度的結(jié)果. 可以看出, 隨著迭代次數(shù)增加, GDBT-MI 的訓(xùn)練和測(cè)試誤差越來(lái)越低. 當(dāng)?shù)螖?shù)達(dá)到200 以上, 輸出精度幾乎不再變化. 對(duì)于 MUSK1數(shù)據(jù)集,在迭代次數(shù)達(dá) 150 次之后, 訓(xùn)練誤差基本上接近零. 然而, 對(duì)于MUSK2數(shù)據(jù)集, 200 次迭代之后的訓(xùn)練誤差為 0.06, 測(cè)試誤差則降為0.121, 訓(xùn)練和測(cè)試誤差均不如在 MUSK1數(shù)據(jù)集上的效果. 這可能是由于MUSK2數(shù)據(jù)集比MUSK1數(shù)據(jù)集的構(gòu)造更為復(fù)雜. 因?yàn)樘荻忍嵘惴ú灰走^(guò)擬合, 所以迭代次數(shù)越多, 效果會(huì)越好.

5小結(jié)

考慮到多示例學(xué)習(xí)的特殊性，提出了包層次上的信息熵和信息增益比,進(jìn)而提出了一種基于 C4.5 的多示例學(xué)習(xí)算法;進(jìn)一步采用梯度提升方法來(lái)優(yōu)化基本的多示例決策樹(shù), 得到了性能更優(yōu)的 GDBT-MI算法, 同時(shí)隨著迭代次數(shù)增加, 能夠進(jìn)一步提升算法效果. 在將來(lái)的研究工作中, 如果在多示例決策樹(shù)中加入一些正則化策略可能會(huì)使結(jié)果更好.

參考文獻(xiàn)：

[1]DIETTERICH T G, LATHROP R H, LOZANO-PEREZ T. Solving the multiple-instance problem with axis-parallel rectangles[J]. Artificial intelligence, 1997,89(1/2)：31—71.

[2]HONG R, WANG M, GAO Y, et al. Image annotation by multiple-instance learning with discriminative feature mapping and selection[J]. IEEE transactions on cybernetics, 2014, 44(5): 669—680.

[3]XIE Y, QU Y, LI C, et al. Online multiple instance gradient features selection for robust visual tracking[J]. Pattern recognition letters, 2012,33(9)：1075—1082.

[4]ZEISL B, LEISTNER C, SAFFARI A, et al.On-line semi-supervised multiple-instance boosting[C]//IEEE Conference on Computer Vision and Pattern Recognition.San Francisco, 2010：1879—1894.

[5]CHEVALEYRE Y, ZUCKER J D. Solving multiple-instance and multiple-part learning problems with decision trees and rules sets:application to the mutagenesis problem[M]// Lecture Notes in Computer Science.Berlin: Springer, 2000：204—214.

[6]BLOCKEEL H, PAGE D, SRINIVASAN A. Multi-instance tree learning[C]// Proceedings of the 22nd International Conference on Machine Learning.Bonn, 2005:57—64.

[7]李航． 統(tǒng)計(jì)學(xué)習(xí)方法[M]． 北京: 清華大學(xué)出版社, 2012．

[8]ANDREWS S, TSOCHANTARIDIS I,HOFMANN T. Support vector machines for multiple-instance learning[M]// Advances in Neural Information Processing Systems .Cambridge: MIT Press,2002：561—568.

(責(zé)任編輯：孔薇)

A Multi-instance Learning Algorithm Based on Decision Tree

WANG Jie1,CAI Liangjian1,GAO Yu2

(1.SchoolofElectricalEngineering，ZhengzhouUniversity，Zhengzhou450001，China；2.SchoolofInformationEngineering,ZhengzhouUniversity，Zhengzhou450001，China)

Abstract:A new multi-instance learning algorithm C4.5-MI based on decision tree C4.5 was proposed, and the entropy function and information gain ratio to multiple instance framework were extended. Excellent algorithm GDBT-MI was obtained by improving C4.5-MI through adopting gradient boosting. The results on several benchmark datasets demonstrated the effectiveness of C4.5-MI and GDBT-MI over other similar algorithms.

Key words:multi-instance learning; decision tree; gradient boosting; C4.5 algorithm

收稿日期:2015-09-10

基金項(xiàng)目:教育部高等學(xué)校博士學(xué)科點(diǎn)科研項(xiàng)目(20124101120001)； 河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(14A41300)； 中國(guó)博士后科學(xué)基金面上項(xiàng)目(2014T70685，2013M541992).

作者簡(jiǎn)介:王杰( 1959—) ，男，河南周口人，教授，博士生導(dǎo)師，主要從事模式識(shí)別與智能控制研究，E-mail: wj@ zzu.edu.cn.

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1671-6841(2016)01-0081-04

DOI:10.3969/j.issn.1671-6841.201507006

引用本文：王杰,蔡良健, 高瑜.一種基于決策樹(shù)的多示例學(xué)習(xí)算法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016,48(1)：81—84.