王國慶

【摘 要】如何利用機器學(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在傳球的準(zhǔn)確性方面有很大提高。

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

0 引言

RoboCup即機器人世界杯足球錦標(biāo)賽，是機器人足球的一個國際盛會，涉及到人工智能，機器視覺，機器控制，智能決策等廣泛領(lǐng)域。含有包括仿真組在內(nèi)的多大40多個比賽項目。RoboCup對于促進(jìn)人工智能領(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)驗進(jìn)行手工編碼來處理Agent 的所有行為是不可能的。因此，很多研究者都嘗試應(yīng)用機器學(xué)習(xí)的方法來解決這個復(fù)雜的問題。

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

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

決策樹算法是目前分類方法中應(yīng)用最廣泛的歸納推理算法之一，它是以實例為基礎(chǔ)，從無次序、無規(guī)則的樣本數(shù)據(jù)集中推理出決策樹表示形式、逼近離散值目標(biāo)函數(shù)的分類規(guī)則方法。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進(jìn)行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點向下的分支，在決策樹的葉結(jié)點得到結(jié)論，因此從根結(jié)點到葉結(jié)點的一條路徑就對應(yīng)著一條規(guī)則，整棵決策樹就對應(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的主要思想是從一個空的決策樹出發(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é)點上選擇屬性，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個非葉節(jié)點上進(jìn)行測試時，能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息。使用該屬性將實例集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點到達(dá)各后代葉節(jié)點的平均路徑最短，使生成的決策樹平均深度較小，提高分類速度和準(zhǔn)確率。ID3算法的基本算法是貪婪算法，采用自頂向下的遞歸方式構(gòu)造決策樹。其原理是對大量的數(shù)據(jù)進(jìn)行歸納、概括、提煉出帶有普遍性、概括性的描述（即事物的屬性規(guī)律），并將這些規(guī)律以決策樹的方式表示出來。

2 ID3算法

由于ID3采用信息的增益作為屬性決策的標(biāo)準(zhǔn)，算法速度快，適應(yīng)于大型的數(shù)據(jù)集應(yīng)用，因此本文選擇ID3算法對球場上與傳球有關(guān)的數(shù)據(jù)屬性進(jìn)行歸類。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é)點上，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個非葉節(jié)點上進(jìn)行測試時，能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息，使用該屬性將例子集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點到達(dá)各后代葉節(jié)點的平均深度較小，準(zhǔn)確率較高， ID3采用這種自頂向下的策略，搜索全部空間的一部分，它確保所做的測試次數(shù)較少，因而分類速度也較快。

ID3 是通過自頂向下構(gòu)造決策樹來進(jìn)行學(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)生大的影響?；谝陨希琁D3算法能有效的消弱不確定的影響，使比賽的決策趨于穩(wěn)定。下面主要針對傳球策略，給出影響的屬性集。

若要考慮場上所有因素，則狀態(tài)空間很大，是目前的機器所不能支持的。下面根據(jù)主要和次要的矛盾，簡化狀態(tài)空間，考慮影響傳球的主要干擾，忽略次要方面。當(dāng)然，這可能會造成判斷不準(zhǔn)確，但是相比較運行時間而言，在誤差允許范圍內(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í)目標(biāo)是：A能傳給B為T，否則F;屬性集合大小13;

根據(jù)屬性集，采集一定的訓(xùn)練樣本，進(jì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算法運用于傳球策略中并達(dá)到百分之百的成功率還有很多需要改進(jìn)的地方。

【參考文獻(xiàn)】

[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ìn)研究[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é)任編輯：張濤]