決策樹算法ID3的應用研究

王國慶

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

【關鍵詞】決策樹算法;ID3算法;傳球決策

0 引言

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

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

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

1 決策樹學習

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

1.1 CLS算法

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

1.2 CART算法

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

1.3 CHAID

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

1.4 ID3算法

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

2 ID3算法

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

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

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 } ，假設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作為根節點，對A3的不同取值對應的E的V個子集E 遞歸上述過程生成A3的子結點B1，B2，…Bn，ID3是一個典型的決策樹學習系統，其核心是在決策樹的各級節點上，用信息增益作為屬性選擇標準，使得在每個非葉節點上進行測試時，能獲得關于被測試例子最大的類別信息，使用該屬性將例子集分成子集后，系統的熵值最小，期望該非葉節點到達各后代葉節點的平均深度較小，準確率較高， ID3采用這種自頂向下的策略，搜索全部空間的一部分，它確保所做的測試次數較少，因而分類速度也較快。

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

3 ID3在RoboCup中的應用

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

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

假設傳球者為A，接球者為B，離B最近的兩名對方球員為C，D，球為E，下面將屬性因素總結如下：

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。

學習目標是：A能傳給B為T，否則F;屬性集合大小13;

根據屬性集，采集一定的訓練樣本，進行基于ID3的決策樹構造;具體的構造方法如下：

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

2）如果所有的屬性均在T中或者F中則決策樹構造結束;否則轉3;

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

4）循環3，迭代計算子結點等。

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

4 不足與總結

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

【參考文獻】

[1]Tom M. Mitchell.機器學習[M].機械工業出版社，2003，1.

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

[3]麻春，韓有韜.決策樹學習研究[J].科技咨詢導報，2007.

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

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

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

[7]李龍. 基于價值的機器學習方法及其在RoboCup仿真2D中的應用[D].合肥工業大學，2009，3.

[責任編輯：張濤]