決策樹算法ID3的應(yīng)用研究

王國慶

【摘 要】如何利用機(jī)器學(xué)習(xí)方法解決仿真機(jī)器人足球中環(huán)境的復(fù)雜性一直是該領(lǐng)域的一大難題。通過對(duì)機(jī)器學(xué)習(xí)方法中決策樹學(xué)習(xí)算法的研究與探討，本文介紹了基于決策樹算法的幾種分類技術(shù)，重點(diǎn)介紹了具有很大影響的ID3算法，并提出將基于ID3的決策算法應(yīng)用到RoboCup仿真球隊(duì)中?；贗D3算法，以傳球決策為實(shí)例，Agent實(shí)時(shí)的判斷是否執(zhí)行傳球，如果不傳球下一步的行為如何等等。實(shí)驗(yàn)表明，將ID3算法算法應(yīng)用于傳球訓(xùn)練中，能夠使Agent在傳球的準(zhǔn)確性方面有很大提高。

【關(guān)鍵詞】決策樹算法;ID3算法;傳球決策

0 引言

RoboCup即機(jī)器人世界杯足球錦標(biāo)賽，是機(jī)器人足球的一個(gè)國際盛會(huì)，涉及到人工智能，機(jī)器視覺，機(jī)器控制，智能決策等廣泛領(lǐng)域。含有包括仿真組在內(nèi)的多大40多個(gè)比賽項(xiàng)目。RoboCup對(duì)于促進(jìn)人工智能領(lǐng)域的研究，提高民族的創(chuàng)新精神，以及對(duì)于教學(xué)都有很大作用和成效。目前國內(nèi)大多數(shù)高校都積極參與，極大的提高了大學(xué)生的動(dòng)手和獨(dú)創(chuàng)的實(shí)踐能力。

仿真球隊(duì)的設(shè)計(jì)是一個(gè)非常復(fù)雜的問題，每個(gè)球員是一個(gè)Agent，如只考慮22 名Agent 在場上的位置、速度以及身體朝向等三個(gè)因素，場上的狀態(tài)就有10198 種之多，再加上球的位置、速度以及過去的狀態(tài)，場上的狀態(tài)數(shù)就會(huì)更多。對(duì)于如此龐大的一個(gè)狀態(tài)空間，僅僅依靠人的經(jīng)驗(yàn)進(jìn)行手工編碼來處理Agent 的所有行為是不可能的。因此，很多研究者都嘗試應(yīng)用機(jī)器學(xué)習(xí)的方法來解決這個(gè)復(fù)雜的問題。

傳球是一個(gè)非常重要的策略，也是進(jìn)攻對(duì)方的一個(gè)不可缺少的動(dòng)作。因此傳球的成功率的大小很大程度上決定了進(jìn)攻的強(qiáng)弱，也決定我方進(jìn)球數(shù)量。如何提高傳球成功率，以及如何決策傳球都是極端重要的。本文基于決策樹的學(xué)習(xí)算法ID3，給出一種判斷傳球與否的依據(jù)。這使得Agent能夠根據(jù)場上動(dòng)態(tài)的變化決策下個(gè)周期的行為。

1 決策樹學(xué)習(xí)

決策樹算法是目前分類方法中應(yīng)用最廣泛的歸納推理算法之一，它是以實(shí)例為基礎(chǔ)，從無次序、無規(guī)則的樣本數(shù)據(jù)集中推理出決策樹表示形式、逼近離散值目標(biāo)函數(shù)的分類規(guī)則方法。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分支，在決策樹的葉結(jié)點(diǎn)得到結(jié)論，因此從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條規(guī)則，整棵決策樹就對(duì)應(yīng)著一組表達(dá)式規(guī)則。常用的決策樹學(xué)習(xí)算法有以下幾類：

1.1 CLS算法

CLS（Concept Learning System）學(xué)習(xí)算法是Hunt.E.B等人在1966年提出的，后來的許多決策樹學(xué)習(xí)算法都可以看作是CLS算法的改進(jìn)與更新。CLS的主要思想是從一個(gè)空的決策樹出發(fā) 通過添加新的判定結(jié)點(diǎn)來改善原來的決策樹，直到該決策樹能夠正確地將訓(xùn)練實(shí)例分類為止。它對(duì)決策樹的構(gòu)造過程也就是假設(shè)特化的過程，所以CLS可以看作是只帶一個(gè)操作符的學(xué)習(xí)算法，此操作符可以表示為：通過添加一個(gè)新的判定結(jié)點(diǎn)特化當(dāng)前假設(shè)，CLS算法遞歸調(diào)用這個(gè)操作符作用在每個(gè)葉結(jié)點(diǎn)來構(gòu)造決策樹。

1.2 CART算法

CART （ Classification and Regression Trees 分類回歸樹）是由Leo Breiman 、Jerome Friedman 、Richard Olshen 和 Charles Stone 于1984 年提出的一種數(shù)據(jù)勘測和預(yù)測算法。這種算法選擇具有最小基尼指數(shù)值的屬性作為測試屬性，并采用一種二分遞歸分割的技術(shù)，將當(dāng)前樣本集分為兩個(gè)子樣本集，使得生成的決策樹的每一個(gè)非葉節(jié)點(diǎn)都有兩個(gè)分枝，最后生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。由于CART算法得到的決策樹每個(gè)節(jié)點(diǎn)有兩個(gè)分支，這種樹也稱為二叉樹。

1.3 CHAID

CHA ID （ Chi - Square Automatic Interaction Detector，卡方自動(dòng)交互檢測） 是一種快速多維樹型統(tǒng)計(jì)算法。CHA ID 的目的主要是在每次分割時(shí)利用卡方檢驗(yàn) （ Chi - Square Test ） 來計(jì)算節(jié)點(diǎn)中類別的屬性值，以屬性值大小來決定決策樹是否繼續(xù)生長，不必作修剪樹的動(dòng)作。CHA ID 自動(dòng)地把數(shù)據(jù)分成互斥的、無遺漏的組群，但只適用于類別型資料 。

1.4 ID3算法

相比于前幾種算法，ID3算法是一種更有影響力的決策樹生成算法。ID3（Iterative Dichotomizer 3）算法是Quinlan在1986年提出的，它基于信息熵的理論，采用從上到下分而治之的貪心算法策略。ID3是一個(gè)典型的決策樹學(xué)習(xí)系統(tǒng)，其核心是在決策樹的各級(jí)節(jié)點(diǎn)上選擇屬性，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個(gè)非葉節(jié)點(diǎn)上進(jìn)行測試時(shí)，能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息。使用該屬性將實(shí)例集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均路徑最短，使生成的決策樹平均深度較小，提高分類速度和準(zhǔn)確率。ID3算法的基本算法是貪婪算法，采用自頂向下的遞歸方式構(gòu)造決策樹。其原理是對(duì)大量的數(shù)據(jù)進(jìn)行歸納、概括、提煉出帶有普遍性、概括性的描述（即事物的屬性規(guī)律），并將這些規(guī)律以決策樹的方式表示出來。

2 ID3算法

由于ID3采用信息的增益作為屬性決策的標(biāo)準(zhǔn)，算法速度快，適應(yīng)于大型的數(shù)據(jù)集應(yīng)用，因此本文選擇ID3算法對(duì)球場上與傳球有關(guān)的數(shù)據(jù)屬性進(jìn)行歸類。ID3算法簡介如下：

設(shè)E =D1 ×D2 ×…×Dn 是n維有窮向量空間，其中Dj是有窮離散符號(hào)集， E中的元素e = < v1 ， v2 ， …， vn > ，叫做例子，其中vj∈Dj， j = 1， 2， …， n. 設(shè)PE和N E是E的兩個(gè)子集，分別叫作正例集和反例集.假設(shè)向量空間E中的正例集PE和反例集N E的大小分別為p和n， ID3基于下列兩個(gè)假設(shè)：

1）在向量空間E上的一棵正確決策樹對(duì)任意例子的分類概率同E中正反例的概率一致;

2）一棵決策樹能對(duì)一個(gè)例子作出正確類別判斷所需的信息量為：

I（p，n）=p/（p+n）ln（p/（p+n））+n/（p+n）ln（n/（p+n））

如果以屬性A作為樹的根， A具有v個(gè)值{ v1 ， v2 ， …， vv } ，它將E分為V個(gè)子集{ E1 ， E2 ， …， Ev } ，假設(shè)Ei 中含有pi 個(gè)正例和ni 個(gè)反例，那么子集Ei 所需的信息期望是I （ pi ， ni ） ，以屬性A為根所需的期望信息是：

E（A）=■■I（pi，ni）;

因此，以A為根的信息增益是：

gain（A）=I（p，n）-E（A）;

ID3選擇使gain（A）最大的屬性A3作為根節(jié)點(diǎn)，對(duì)A3的不同取值對(duì)應(yīng)的E的V個(gè)子集E 遞歸上述過程生成A3的子結(jié)點(diǎn)B1，B2，…Bn，ID3是一個(gè)典型的決策樹學(xué)習(xí)系統(tǒng)，其核心是在決策樹的各級(jí)節(jié)點(diǎn)上，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個(gè)非葉節(jié)點(diǎn)上進(jìn)行測試時(shí)，能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息，使用該屬性將例子集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均深度較小，準(zhǔn)確率較高， ID3采用這種自頂向下的策略，搜索全部空間的一部分，它確保所做的測試次數(shù)較少，因而分類速度也較快。

ID3 是通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)的，在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣本。由于使用所有樣本的統(tǒng)計(jì)屬性，大大降低了對(duì)個(gè)別訓(xùn)練樣本錯(cuò)誤的敏感性，因此該算法適合于訓(xùn)練樣本中含有錯(cuò)誤的學(xué)習(xí)。

3 ID3在RoboCup中的應(yīng)用

RoboCup仿真比賽是由22名隊(duì)員組成，雙方各11名，是典型的多智能體協(xié)作問題，隊(duì)友及敵人的站位，速度，角度，球的速度，球員的視覺信息等等都會(huì)對(duì)球場上的每個(gè)決策產(chǎn)生影響。另外，由于比賽是實(shí)時(shí)的，而且仿真環(huán)境存在噪聲干擾，所以采集的信息可能是不精確的，甚至機(jī)器的速度都會(huì)對(duì)比賽產(chǎn)生大的影響?；谝陨希琁D3算法能有效的消弱不確定的影響，使比賽的決策趨于穩(wěn)定。下面主要針對(duì)傳球策略，給出影響的屬性集。

若要考慮場上所有因素，則狀態(tài)空間很大，是目前的機(jī)器所不能支持的。下面根據(jù)主要和次要的矛盾，簡化狀態(tài)空間，考慮影響傳球的主要干擾，忽略次要方面。當(dāng)然，這可能會(huì)造成判斷不準(zhǔn)確，但是相比較運(yùn)行時(shí)間而言，在誤差允許范圍內(nèi)，可以提高傳球成功決策率，有實(shí)際的應(yīng)用價(jià)值的。

假設(shè)傳球者為A，接球者為B，離B最近的兩名對(duì)方球員為C，D，球?yàn)镋，下面將屬性因素總結(jié)如下：

1）A與B的距離為distAB，C與E的距離為distCE，D與E的距離為distDE，A與E的距離為distAE;

2）A與C的角度為AngAC，A與B的角度為AngAB，A與D的角度為AngAD，A與E的角度為AngAE;

3）球速度為Espeed，傳球者速度為Aspeed，B速度為Bspeed，D速度為Dspeed，C速度為Cspeed。

學(xué)習(xí)目標(biāo)是：A能傳給B為T，否則F;屬性集合大小13;

根據(jù)屬性集，采集一定的訓(xùn)練樣本，進(jìn)行基于ID3的決策樹構(gòu)造;具體的構(gòu)造方法如下：

1）把所有屬性作為節(jié)點(diǎn)放入樹的集合中;

2）如果所有的屬性均在T中或者F中則決策樹構(gòu)造結(jié)束;否則轉(zhuǎn)3;

3）選擇莫個(gè)屬性A根據(jù)訓(xùn)練樣本值V1，V2，…Vn將訓(xùn)練集分成子集T1，T2，…Tn，計(jì)算屬性A的信息增益，遍歷所有屬性，比較信息增益取最大值即為根節(jié)點(diǎn);

4）循環(huán)3，迭代計(jì)算子結(jié)點(diǎn)等。

為了驗(yàn)證本文帶球算法的可行性和有效性，我們將此方法應(yīng)用于ROBOCUP仿真平臺(tái)中球員的傳球訓(xùn)練中。從統(tǒng)計(jì)數(shù)據(jù)中可以看出，隨著訓(xùn)練次數(shù)的增加，我方球員的傳球成功率逐漸提高，在趨于700次以后，我方的平均傳球決策成功率趨于穩(wěn)定。結(jié)果表明此方法是收斂并且有效的提高了我方的傳球成功率。

4 不足與總結(jié)

本文根據(jù)ID3算法，給出了在RoboCup仿真比賽中訓(xùn)練學(xué)習(xí)傳球策略的思路，但是由于考慮問題的局限性，并且算法本身也存在諸如不連續(xù)性、優(yōu)先選取取值較多的屬性的傾向等缺陷，要想將ID3算法運(yùn)用于傳球策略中并達(dá)到百分之百的成功率還有很多需要改進(jìn)的地方。

【參考文獻(xiàn)】

[1]Tom M. Mitchell.機(jī)器學(xué)習(xí)[M].機(jī)械工業(yè)出版社，2003，1.

[2]云健，張旭，魏曉嗚.RoboCup中截球、控球/帶球、傳球/跑位的策略[J].內(nèi)蒙古科技大學(xué)學(xué)報(bào)，2009，28（2）.

[3]麻春，韓有韜.決策樹學(xué)習(xí)研究[J].科技咨詢導(dǎo)報(bào)，2007.

[4]馬瑜，王有剛.ID3算法應(yīng)用研究[J].信息技術(shù)：2006，12：84-86.

[5]滿桂云，林家駿.ID3決策樹算法的改進(jìn)研究[J].中國科技信息，2007，13：8-9.

[6]陶維馬，吉明.決策樹算法分析及應(yīng)用[J].電腦知識(shí)與技術(shù)，2009，5：3352-3354.

[7]李龍. 基于價(jià)值的機(jī)器學(xué)習(xí)方法及其在RoboCup仿真2D中的應(yīng)用[D].合肥工業(yè)大學(xué)，2009，3.

[責(zé)任編輯：張濤]