决策树算法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.

[责任编辑：张涛]