王　杰,　 蔡良健,　 高　瑜

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

?

一種基于決策樹的多示例學習算法

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

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

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

關鍵詞：多示例學習; 決策樹; 梯度提升; C4.5算法

0引言

1決策樹及 C4.5算法

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

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

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

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

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

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

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

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

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

2梯度提升決策樹算法

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

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

或

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

(1)

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

具體算法流程如下:

Step 2Form=1 toM:

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

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

Step 3 輸出Fm(x) .

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

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

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

(2)

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

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

(3)

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

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

多示例的熵定義為

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

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

為了避免這個缺點,將推演過程修改如下：一旦一個正包中的示例被正確地劃分為正的示例, 移除包中余下的示例.只要一個子樹成功地為一個示例貼上正的包標簽, 另外的一個示例就直接被移除. 基于多示例熵以及對以上樹生成的修剪, 經典的決策樹 C4.5就被拓展成多示例版本C4.5-MI.

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

4仿真實驗

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

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

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

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

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

在通過梯度提升算法之后, GDBT-MI算法的分類精度處于最好的位置,在除 MUSK2 以外的數(shù)據(jù)集上測試誤差都達到了最小.圖 1 記錄了GDBT-MI算法在MUSK1 和 MUSK2 數(shù)據(jù)集隨著提升迭代次數(shù)的增加輸出分類訓練和測試精度的結果. 可以看出, 隨著迭代次數(shù)增加, GDBT-MI 的訓練和測試誤差越來越低. 當?shù)螖?shù)達到200 以上, 輸出精度幾乎不再變化. 對于 MUSK1數(shù)據(jù)集,在迭代次數(shù)達 150 次之后, 訓練誤差基本上接近零. 然而, 對于MUSK2數(shù)據(jù)集, 200 次迭代之后的訓練誤差為 0.06, 測試誤差則降為0.121, 訓練和測試誤差均不如在 MUSK1數(shù)據(jù)集上的效果. 這可能是由于MUSK2數(shù)據(jù)集比MUSK1數(shù)據(jù)集的構造更為復雜. 因為梯度提升算法不易過擬合, 所以迭代次數(shù)越多, 效果會越好.

5小結

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

參考文獻：

[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)計學習方法[M]． 北京: 清華大學出版社, 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.

(責任編輯：孔薇)

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

基金項目:教育部高等學校博士學科點科研項目(20124101120001)； 河南省教育廳科學技術研究重點項目(14A41300)； 中國博士后科學基金面上項目(2014T70685，2013M541992).

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

中圖分類號：TP181

文獻標志碼：A

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

DOI:10.3969/j.issn.1671-6841.201507006

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