决策树学习的关键就是特征选择的问题，即如何确定每个内部结点对应哪个特征（每次划分到底应该按照哪个特征来进行）。我们希望的是每次划分得到的分支结点尽可能的“纯”（最好是属于同一类的）。

在信息论中，熵是对随机变量不确定性的度量。在这里熵可以用来度量集合的纯度。
设随机变量 X 是一个取有限个值得离散的随机变量，其概率分布为：
p(X=xi)=pi,i=1,2,⋯,n
随机变量的熵定义为：
H(X)=−n∑i=1pilogpi
若 pi=0 则定义：
0log(0)=0
当 log 函数以 2 为底时，这时的熵被称为比特熵，当 log 函数以 e 为底时，这时的熵被称为纳熵。有了熵的概念，我们就可以用熵来度量一个数据集的混乱程度（或者反过来说，也就是可以度量纯度）了。

先给出概念上的解释，假设特征（属性）a 有 V 个可能的取值 a1,a2,…,aV，若用特征 a 对样本集 D 进行划分。会产生 V 个分支结点。第 v 个分支结点包含了样本集中 D 中的所有在属性 a 上取值为 av 的样本，记作 Dv。
首先我们可以计算出所有 Dv 的熵。然后我们假设 |Dv| 表示的是 Dv 中的样本数量，|D| 表示的是 D 中的样本数量，这样我们可以通过计算给每个分支结点赋予一个权重：
|Dv||D|
接着我们就可以计算出样本集 D 按照特征 a 划分的信息增益了：
G(D,a)=H(D)−V∑v=1|Dv||D|H(Dv)
一般来说信息增益越大，说明划分以后各个分支结点的“纯度提升“越大。

ID3 算法

ID3 算法就是根据信息增益来选择特征进行划分的。按照一个特征进行划分后，产生的信息增益最大，ID3 算法就选择该特征进行划分。

设上一篇文章文末给出的数据集为 D,观察数据集只有两类，正例个数为 8， 负例个数为 9。我们设 p1 为样本集中正例的概率，p2 为样本集中负例的概率，熵采用比特熵的计算方式，则:
p1=817 p2=917 H(D)=−2∑i=1pilog2pi=−(817log2817+917log2917)=0.998
接下来考虑按照色泽进行划分，色泽这个特征对应三个取值：{青绿，乌黑，浅白}，如果使用这个特征进行划分，那么会得到三个分支结点。也就是会得到三个子样本集合，分别记为 D1,D2,D3，D1 对应色泽为青绿的子集，D2 对应色泽为乌黑的子集，D3 对应色泽为浅白的子集。
D1 包含 6 个样本，3 个正例，3 个反例。
D2 包含 6 个样本，4 个正例，2 个反例。
D3 包含 5 个样本，1 个正例，4 个反例。
计算 D1,D2,D3 三个划分后的样本集的权重和熵，设 D1,D2,D3 对应的权重分别为 p1,p2,p3。
p1=617 p2=617 p3=517 H(D1)=−(36log236+36log236)=1.000 H(D2)=−(46log246+26log226)=0.918 H(D3)=−(56log256+16log216)=0.722
按照色泽划分，对应的信息增益为：
G(D,色泽)=H(D)−3∑v=1|Dv||D|H(Dv) =0.998−(617×1.000+617×0.918+517×0.722) =0.109
然后我们用同样的方法，依次计算按照其他特征（根蒂、敲声、纹理、脐部、触感）进行划分对应的信息增益：
G(D,根蒂)=0.143 G(D,敲声)=0.141 G(D,纹理)=0.381 G(D,脐部)=0.289 G(D,触感)=0.006
通过比较我们可以确定通过纹理这个特征进行划分，得到的信息增益最大，所以应该选择纹理这个特征进行划分。划分结果如下：

接着对得到的三个子数据集 D1,D2,D3 进行划分。子数据集 D1 中有 9 个样例，有色泽、根蒂、敲声、脐部、触感五个特征可供选择（D1,D2,D3 这三个子数据集中每个数据集的纹理特征是唯一的，严么全是清晰，要么全是稍糊，要么就全是模糊）。
划分 D1 数据集，计算按各个特征进行划分对应的信息增益：
G(D1,色泽)=0.043 G(D1,根蒂)=0.458 G(D1,敲声)=0.331 G(D1,脐部)=0.458 G(D1,触感)=0.458
经过比较我们发现按根蒂、脐部、触感三个特征中的任意一个划分，信息增益都能取到最大值 0.458，我们可以从这三个特征里任选一个进行划分。这里选择根蒂这个特征进行划分。如此按照递归的方式依次对各个子数据集进行划分最后不难得到一棵如下的决策树：

ID3 算法的问题

• ID3 算法没有考虑取值为连续值的特征，比如密度，质量等连续值特征是无法被 ID3 算法运用的，这大大限制了ID3的用途。
• ID3 算法对可取值数据较多的属性有偏好
• ID3 算法对于缺失值的情况没有做考虑
• ID3 算法没有考虑过拟合的问题，即没有剪枝处理

1. 《机器学习》 —— 周志华
2. 《统计学习方法》 —— 李航

文章标题:决策树算法（二）：ID3

文章字数:1,543

本文作者:ylhao

发布时间:2018-05-04, 20:56:03

最后更新:2019-06-07, 11:50:53

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。