文档介绍：决策树 ID3 算法

决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数
据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加
入到
训练集数据中，重复该过程一直 161条记录。经统计，
在这 161条记录的训练集中单科成绩及格人数和不及格人数如下表所示：
语文数学英语物理化学
及格 82 57 34 32 39
不及格 79 104 127 129 122
第三步：利用信息增益度选取最能区别训练集中实例的属性。
首先计算课程物理所含有的信息量。由表 4可知物理及格人数 P=32，不及格人
数 N=129，则可得到：
Info(T)=I(32,
129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=
然后计算当课程物理及格和不及格时，课程语文所包含的总信息量。经统计，语
文和物理有如下表所示的统计数据：

成绩搭配人数
语文成绩=1且物理成绩=1 28
语文成绩=1且物理成绩=0 54
语文成绩=0且物理成绩=1 4
语文成绩=0且物理成绩=0 75
可得到：
Info(X,T) = )=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))=(82/161)I(28,54)+(79/161)I(4,75)=
最后可得到语文的信息增益度为：
Gain(X,T)=Info(T)-Info(X,T)=-=
同理可得其他课程的信息增益度，结果如下表所示：

数学英语化学
Gain

由此可以看出所有课程当中数学是最能区别训练集中决定物理成绩与否的课程
第四步：创建一个树结点，并创建该结点的子链，每个子链代表所选属性的一个
唯一值。使用子链的值进一步细化子类。当出现以下两种情形之一时可以停止分
类：；。
根据各个课程的信息增益度，应该选择数学作为所建决策树的根结点。由于数学
的属性值只有两个：1（及格）和 0（不及格），所以在数学下可以建立两个分
支。经统计，数学不及格且物理不及格的人数为 100，其准确率为 100/104=%。
因此对数学不及格这个分之停止分割。又经统计，数学及格的 57人中有 26人物
理及格，31人物理不及格，所以应对数学及格这个分支进行分割。上表可从知，
应该选取化学作为分割结点进行细化。分割后经统计显示，数学和化学都及格的
学生中，有 26人物理及格，6人物理不及格，准确率为 26/32=%；数学及
格但化学不及格的学生中，有 22人物理不及