王國慶

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

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

0 引言

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

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

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

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

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

1.1 CLS算法

CLS（Concept Learning System）學(xué)習(xí)算法是Hunt.E.B等人在1966年提出的，后來的許多決策樹學(xué)習(xí)算法都可以看作是CLS算法的改進與更新。CLS的主要思想是從一個空的決策樹出發(fā) 通過添加新的判定結(jié)點來改善原來的決策樹，直到該決策樹能夠正確地將訓(xùn)練實例分類為止。它對決策樹的構(gòu)造過程也就是假設(shè)特化的過程，所以CLS可以看作是只帶一個操作符的學(xué)習(xí)算法，此操作符可以表示為：通過添加一個新的判定結(jié)點特化當(dāng)前假設(shè)，CLS算法遞歸調(diào)用這個操作符作用在每個葉結(jié)點來構(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)前樣本集分為兩個子樣本集，使得生成的決策樹的每一個非葉節(jié)點都有兩個分枝，最后生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。由于CART算法得到的決策樹每個節(jié)點有兩個分支，這種樹也稱為二叉樹。

1.3 CHAID

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

1.4 ID3算法

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

2 ID3算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)傳球者為A，接球者為B，離B最近的兩名對方球員為C，D，球為E，下面將屬性因素總結(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í)目標是：A能傳給B為T，否則F;屬性集合大小13;

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

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

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

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

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

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

4 不足與總結(jié)

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

【參考文獻】

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

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

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

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

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

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

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

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