文档介绍：第 13 页
2021 届学士学位毕业论文
决策树算法研究
学号：
姓名：
指导教师：
专业：
系别：
完成时间：。
眼睛颜色
[1,6]
[2,4,8]
[3,5,7]
黑色
蓝色
灰色
初步构建决策树
根据“眼睛颜色〞所划分的子集中的样本不属于同一类，所以选择新的测试属性“头发颜色〞对各个子集进展划分，，所得的样本属于同一类，决策树构建完成。
第 3 页
眼睛颜色
头发颜色
头发颜色
头发颜色
黑色
蓝色
灰色
白种人[4]
白种人[2]
混血
[7]
白种人[6]
黄种人[1]
混血
[8]
白种人[5]
白种人[3]
黑色
金色
金色
红色
黑色
金色
红色
黑色
决策树
ID3算法
ID3算法是决策树学****算法中最具有影响和最为典型的算法，它的根本思想是，利用信息熵原理，选择信息增益最大的属性作为分类属性。
信息量大小的度量
Shannon1948年提出的信息论理论。事件ai的信息量I(ai)可如下度量：
其中p(ai)表示事件ai发生的概率。
假设有n个互不相容的事件a1,a2,a3,……，an，它们中有且仅有一个发生，那么其平均的信息量可如下度量：
在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本划分为n个不同的类C1，C2，……Cn，这些类的大小分别标记为|C1|，|C2|，……，|Cn|。那么任意样本S属于类Ci的概率为：
第 4 页
假设属性A的所有不同值的集合为XA，Sv是S中属性A的值为v的样本子集，在选择属性A后的每一个分支节点上，对该节点的样本集Sv分类的熵为E(Sv)。选择A导致的期望熵定义为每个子集Sv的熵的加权和，权值为属于Sv的样本占原始样本S的比例,即期望熵为：
属性A相对样本集合S的信息增益Gain(S，A)定义为：
其中Gain(S，A)是指因知道属性A的值后导致的熵的期望压缩。Gain(S，A)越大，说明选择测试属性A对分类提供的信息越多。ID3算法就是将每个节点选择信息增益Gain(S，A)最大的属性作为测试属性。
ID3决策树应用举例
例2：，对于任意给定的客人，能否帮助公司将这位客人归类。
谁在买计算机
计数
年龄
收入
学生
信誉
归类：买计算机？
64
青
高
否
良
不买
64
青
高
否
优
不买
128
中
高
否
良
买
60
老
中
否
良
买
64
老
低
是
良
买
64
老
低
是
优
不买
第 5 页
64
中
低
是
优
买
128
青
中
否
良
不买
64
青
低
是
良
买
132
老
中
是
良
买
64
青
中
是
优
买
32
中
中
否
优
买
32
中
高
是
良
买
63
老
中
否
优
不买
1
老
中
否
优
买
(1) 计算决策属性的熵
决策属性“买计算机？〞，该属性分为两类：买、不买。
S1(买)=641 S2(不买)=383 S=S1+S2=1024
I(S1，S2)=I(641,383)=-P1log2P1-P2log2
(2) 计算条件属性的熵
条件属性共有4个，分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。
计算年龄的熵：
年龄共分三个组：青年、中年、老年
青年买与不买比例为128/256
P1=128/384 P2=256/384
I(S1，S2)=I(128,256)=-P1log2P1-P2log2
中年买与不买的比例为256/0
第 6 页
P1=256/256 P2=0/256
I(S1,S2)=I(256,0)=-P1log2P1-P2log2P2=0
老年买与不买的比例为257/127
P1=257/384 P2=127/384
I(S1，S2)=I(257,127)= -P1log2P1-P2log2
所占比例：
青年组：384/1024；中年组：5；老年组：
计算年龄的平均信息期望：
E(年龄
G(年龄
计算收入的熵：
收入共分三个组：高、中、低
E(收入)=
G(收入)
计算学生的熵：
学生共分为两个组：学生、非学生
E