第１１卷第３期 ２０１３年９月 南京工程学院学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｎａｍｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏ１．１１，Ｎｏ．３ Ｓｅｐ．，２０１３
文章编号：１６７２—２５５８（２０１３）０３—００５８—０４
决策树算法的研究及实例分析
周桂如
（福建船政交通职业学院公共教学部，福建福州３５０００７）
摘要：分类与预测是数据挖掘技术中的一个重要研究领域．而决策树算法又是分类与预测的核心技术算法之一．描 述ＩＤ３的主要算法，介绍信息增益、系统总熵和信息熵的概念及其计算公式；然后对ＩＤ３算法进行了深入地研究与分 析；最后把决策树中的ＩＤ３算法运用在学生综合测评中．ＩＤ３算法最大的缺点是运算复杂，而且要花费较多的时间． 关键词：决策树算法；ＩＤ３算法；综合评价；分类与预测 中图分类号：ＴＰＩ８１
Ｒｅｓｅａｒｃｈ ｉｎｔｏ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｃａｓｅ Ｓｔｕｄｉｅｓ
ＺＨ０Ｕ Ｇｕｉ—ｒｕ
（Ｄｅｐｔ．ｏｆ Ｐｕｂｌｉｃ Ｃｏｕｒｓｅｓ Ｔｅａｃｈｉｎｇ，Ｆｕｊｉａｎ Ｃｈｕａｎｚｈｅｎｇ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｃｏｌｌｅｇｅ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｖｉｅｗｅｄ ａｓ ｏｎｅ ｏｆ ｔｈｅ ｃｏｒｅ ｔｅｃｈｎｉｃａｌ ａｌｇｏｒｉｔｈｍｓ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ ｗｈｉｃｈ ｉｓ ｃｏｎｓｉｄｅｒｅｄ ａ ｋｅｙ ａｒｅａ ｉｎ ｄａｔａ ｍｉｎｉｎｇ ｔｅｃｈｎｏｌｏｇｙ．Ｔｈｉｓ ｐａｐｅｒ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｍａｊｏｒ ａｌｇｏｒｉｔｈｍ ｏｆ ＩＤ３ ａｎｄ ｉｎｔｒｏｄｕｃｅｓ ｓｕｃｈ ｃｏｎｃｅｐｔｓ ａｓ ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ，ｔｏｔａｌ ｓｙｓｔｅｍ ｅｎｔｒｏｐｙ，ａｎｄ ｉｎｆｏｒｍａｔｉｏｎａｌ ｅｎｔｒｏｐｙ，ａｓ ｗｅｌｌ ａｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｆｏｒｍｕｌａ．Ａｎｄ ｉｎ—ｄｅｐｔｈ ｒｅｓｅａｒｃｈ ｉｓ ｃｏｎｄｕｃｔｅｄ ｉｎｔｏ ＩＤ３ ａｌｇｏｒｉｔｈｍ．Ｆｉｎａｌｌｙ，ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｏｆ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｉｓ ｕｓｅｄ ｔｏ ｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙ ｅｖａｌｕａｔｅ ｓｔｕｄｅｎｔｓ’ｐｅｒｆｏｒｍａｎｃｅ．ＩＤ３ ａｌｇｏｒｉｔｈｍ，ｈｏｗｅｖｅｒ，ｈａｓ ｉｔｓ ｄｉｓａｄｖａｎｔａｇｅｓ，ｆｏｒ ｅｘｍｐｌｅ，ｃｏｍｐｌｅｘ ｃａｌｃｕｌａｔｉｏｎ ａｎｄ ｔｉｍｅ— ｃｏｎｓｕｍｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ；ＩＤ３ ａｌｇｏｒｉｔｈｍ；ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｅｖａｌｕａｔｉｏｎ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ
分类对象 ：在程序中输入的数据或称训练集（ｔｒａｉｎｉｎｇ ｓｅｔ）样本，是由每个包含若干个属性
（ａｔｔｒｉｂｕｔｅ）的数据库所记录（ｒｅｃｏｒｄ）组成的一个特征向趋 训练集中的每条记录还必须由系统的输入一个
特定的类标签（ｃｌａｓｓ ｌａｂｅ１）与之相对应的．如一个样本向量（ ，， ，…， ；Ｃ）的形式中， 表示其中属性值，
Ｃ表示它的类别．
分类的评价方法：
１）对准确度进行预测，常用于预测型分类任务的一种比较尺度．
２）对复杂度的计算，主要是一些实现细节和所依赖的硬件环境．
３）对模型简洁度的描述，特别是对于描述型的分类任务，它的模型描述越简洁就越容易理解．
对于一些分类的操作通常主要有两个步骤 Ｊ：第一步，可以根据给定的训练集数据，找到较合适于这
种训练集的函数映射的模型形式．这个步骤一般被称作为模型训练阶段．第二步，使用函数映射模型是为
了能够预测数据到底是属于那一种类型；或利用该函数模型描述数据所集中的那类别数据，从而形成这种
分类规则．
收稿日期：２０１３—０８—０８；修回日期：２０１３—０８—３０ 作者简介：周桂如，硕十，讲师，研究方向为数学与应用数学 Ｅ－ｍａｉｌ：８４１５９９０３９＠ｑｑ．ｃｏｎｌ
第１１卷第３期 周桂如：决策树算法的研究及实例分析 ５９
１ ＩＤ３算法描述
ＩＤ３Ｔｒｅｅ ３ （Ｔ，ｔａｔｔｒｉｂｕｔｅｌｉｓｔ）（其中 为样本空间，ｔａｔｔｒｉｂｕｔｅｌｉｓｔ为属性集）是一个递归过程，所以仅仅需
要讨论对某个特定结点Ｎ的分裂方法．
分割前设指向特定结点Ⅳ的训练集为Ｓ，其中训练集的样本个数为ｓ，包含所有不同的类别，他们区分
了不同的类Ｃ （ｆｏｒ ｉ＝１，…，ｍ），设ｓ 是Ｓ中属于类Ｃ 的记录的个数．那么分裂之前，系统的总熵为
ｌ（ｓ１，ｓ２，…，ｓ ）＝一∑（ｉ＝１ ｔｏ ｍ）ｐｉｌｏｇ２ｐ （１）
其中Ｐ 是任意样本属于类ｃ 的概率，从公式容易看出，总熵是属于各个类的记录信息量的加权平均．
从属性集中选取某一属性Ａ，它是带有 个不同值的属性｛０ ，口：，…，ｏ ｝，Ａ可以把ｓ划分成 个子集
｛ｓ ，Ｌｓ ，…，Ｊｓ ｝，其中ｓ ＝｛ ＩＸ∈Ｓ＆Ｘ・Ａ：ａｊ｝．如果Ａ被选为测试属性，那么那些子集表示从集合Ｊｓ出 发的所有树枝．设ｓ，为子集．ｓｆ中的记录个数，ｓ 就表示为在子集Ｊｓｆ中属于类为Ｃ 的记录个数．这时按Ａ
的每个属性值（更一般的是取 的一个子集）进行分割后的信息量，也就是系统总熵 为
Ｅ（Ａ）＝∑（ ：１ ｔｏ ）［ｓ１ ＋ｓ ＋…＋ｓ ）／ｓ］ （ ｕ，ｓ ，…，ｓ哪） （２）
式中：总熵Ｅ（Ａ）是各个子集信息量的加权平均；（ｓ ｓ ，＋…＋ｓ耐）／ｓ表示第 个子集的权重；，（ｓ ｓ 一，ｓ面）
为子集Ｊｓ 的信息量（子集的总熵），
１（ｓ ，ｓ ，…，ｓ阿）＝一∑（ｉ＝１ ｔｏ ｍ）ｐ ｌｏｇ２Ｐ （３）
其中Ｐ ＝ｓ ／４是ｓｆ中的样本属于类Ｃ 的概率．
信息增益（Ｉｎｆｏｒｍａｔｉｏｎ Ｇａｉｎ） 是表示系统由于分类所获得的信息量，由系统熵的减少值定量描述．对
结点Ｊ７ｖ用属性Ａ分类后的信息增益 为
Ｇａｉｎ（Ａ）＝，（ｓ。，５：，…，ｓ ）一Ｅ（Ａ） （４） 算法依次计算出属性集中其他属性的信息增益，具有最高信息增益值的属性将选作特定结点Ⅳ的分
裂属性即根节点．
２ １１）３算法的复杂度
１）由于在ＩＤ３算法中决策树的生成过程都是采用层层递归的方法，因此每次以最大信息增益属性分
区时都将产生与此属性取值个数相同数目的子表．而每个子表都会占用一定的存储空间，这种存储空间占
用以指数速度上升，会消耗大量的内存，并且还有大量的数据传送过程中的时间消耗．另外，当数据传送过
程中数据量极大时，决策树算法会由于无法一次性将所有的数据调入内存而不能进行工作，所有的这些因
素都增加了决策树生成中的空间复杂度．
２）当在计算每个属性的信息增益时，需要统计这个属性中每种取值的个数和该种取值相对于分类属
性的个数．一般采用的方法是循环计数的过滤来实现．在上述方法中，一次只能进行一个属性取值的统计，
但往往需要若干次循环嵌套才能完成所需属性信息增益的计算，而且在属性信息增益计算中对对数计算
所花的时间也相对较多，使得决策树分类算法的执行效率难以得到提高，从而增加了时间复杂度．
３ 实例分析
根据福建交通学院学生的德育素质、智育素质、健康与卫生、技能素质和社会实践来进行评定学生综
合成绩的分类．
南京工程学院学报（自然科学版） ２０１３年９月
把政治思想品德、专业成绩、健康与卫生、技能素质和社会实践的所有
分值按８０—１００的设为１级（即优），７Ｏ—＿７９．５设为２级（即良），６０—６９．５
设为３级（即中），把原有的数据进行离散化．它的非类别属性见表１．
根据表２的学生的成绩的综合的评价做出如下计算：
１）对于类别属性的信息熵，即对学生综合成绩的分类，令类别属性的
信息熵为 ，那么属于１级有２５个，２级有１４个，３级有１１个，所以类别属
性的信息熵为 表１非类别属性及取值
属性 可能取值 政治思想品德 专业成绩 健康与卫生 技能素质 社会实践 １，２，３ １，２，３ １，２，３ １，２ １，２
，（ ）＝一 ３＠ｌｏｇ２了￣Ｓｉ＝一 ２５ｌ。ｇ ２ ５一亏１ ４ｌ。ｇ １４一 １１ｌ。ｇ １１＝１．５０１ ２
表２样本训练集
序号 政治思想品德 专业成绩 健康与卫生 技能素质 社会实践 综合成绩
２）对于非类别属性的信息熵计算，选择非类别属性为政治思想，在政治思想中１级有ｌ９个，其中综
合成绩为１的有１９个，２的为０个，３的为０个；２级有ｌ８个，其中综合成绩为１的有６个，综合成绩为２
的有９个，综合成绩为３的有３个；３级的有１３个，其中综合成绩为１的有１个，综合成绩为２的有７个，
综合成绩为３的有５个．由公式
Ｅ（Ａ）＝∑ ，（Ｓｌｊ￣Ｓ２ｊ，Ｓ３ｊ）
可得：
Ｅ ｃ思想 ＝ １９（一嚣 。ｇ ）＋ （一 。ｇ： 一 －％ 一素 ｏｇ２ ）＋
（一古－。ｇ： 一 。ｇ： 一 。ｇ 吾）＝０．８６７ ８
同理可得，以专业成绩和健康与卫生为非类别属性计算
Ｅ（专业）＝０．５４１ ７，Ｅ（健康）＝１．０８３ ８
以技能和社会实践作为非类别属性计算
（技能）＝１．３９８ ９，Ｅ（实践）＝１．０９１ ５
３）根据属性Ａ对数据划分的信息增益，Ｇ（Ａ）＝，（Ｔ）一Ｅ（Ａ）可以得出以下信息增益量：
Ｇ（思想）＝，（ ）一 （思想）＝１．５０１ ２—０．８６７ ８＝０．６３３ ４
Ｇ（专业）＝，（ ）一Ｅ（专业）＝１．５０１ ２—０．５４１ ７＝０．９５９ ５
Ｇ（健康）＝，（Ｔ）一Ｅ（健康）＝１．５０１ ２—１．０８３ ８＝０．４１７ ４
Ｇ（技能）＝，（ ）一Ｅ（技能）＝１．５０１ ２—１．３９８ ９＝０．１０２ ３ ｌ｛．．＿１ ｌ，‘ ｌ １ １ ； ２ ２ ２ ２ １ ２ １ ２ ２ １ ３ １｛．．３ １， ２ ； 卯 铝
如 第１１卷第３期 周桂如：决策树算法的研究及实例分析 ６１
Ｇ（实践）＝，（ ）一Ｅ（实践）＝１．５０１ ２—１．０９１ ５＝０．４０９ ７
从以上公式推理得到的结果可以比较出Ｇ（专业）的值最大，即可以认为专业成绩对分类的帮助最
大，因此可以选择专业作为它的测试属性．
根据以上方法，通过ＩＤ３算法构造出的一棵决策树，如图１所示．
４ 结语 图１ ＩＤ３算法生成的决策树
主要介绍决策树的分类及其过程．介绍信息增益、条件熵和信息熵的概念及其计算公式；描述ＩＤ３的
主要算法，利用其算法过程进行实例分析；ＩＤ３算法是逐个考虑训练例，是一种单变量的算法，偏向于属性
取值较多值的那个属性，而实际上，选择取值多的属性作为首先分裂的属性不一定是最优的；同时由以上
所计算的工作量也就可以看出，ＩＤ３算法中对数的运算还是比较复杂的，这要花一定的时间的换算．所以
针对ＩＤ３算法中的信息熵，互信息的计算可以进行化简，以提高其的建树速度和效率．
参考文献： ［１］营志刚，金旭．数据挖掘中数据预处理的研究与实现［Ｊ］．计算机应用研究，２００４，２１（７）：１１７—１ｊ ８． ［２］戴稳胜，匡宏波，谢邦昌．数据挖掘中的关联规则［Ｊ］．统计研究，２００２（８）：４Ｏ一４２． ［３］罗海蛟，刘显．数据挖掘中分类算法的研究及其应用［Ｊ］．微机发展，２００３，１３（ｓ２）：４８—５０． ［４］牛祥春．数据挖掘技术研究与应用初探［Ｊ］．活力，２００６，５：２８—３Ｏ． ［５］ ＮＩＷＡ Ｋ．Ａ ｋｎｏｗｌｅｄｇｅ ｂａｓｅｄ ｈｕｍａｎ—ｃｏｍｐｕｔｅｒ ｃｏｏｐｅｒａｔｉｏｎ ｓｙｓｔｅｍ ｆｏｒ ｉｌｌ—ｓｔｒｕｃｔｕｒｅ ｍａｎａｇｅｍｅｎｔ ｄｏｍａｉｎｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎ Ｓｙｓｔ，Ｍａｎ ａｎｄ Ｃｙｂｅｍ，１９８６，１６（３）：３３５—３４３． ［６］栾丽华，吉根林．决策树分类技术研究［Ｊ］．计算机工程，２００４．３０（９）：９４—９６．