决策树 | Alan Wang

type

status

date

slug

summary

ID3 算法

信息熵的定义

信息熵：熵是度量样本集合纯度最常用的一种指标，代表一个系统中蕴含多少信息量，信息量越大表明一个系统不确定性就越大就存在越多的可能性，即信息熵越大。

假定当前样本集合中第类样本所占的比例为，则的信息熵为：

信息熵满足下列不等式：

对信息熵的最值进行证明（选看）

已知集合的信息熵为

其中表示样本类别总数，表示第类样本所占的比例，且，。

若令，，那么信息熵就可以看作一个元实值函数，即

其中

引入拉格朗日乘子

引入拉格朗日乘子（条件极值, 在的条件下, 求最值) :

对分别关于，求一阶偏导，并令偏导等于：

同理可推得：

对任意的，满足约束条件：

因此：

这里对最大值点还是最小值点需要做个验证：

当时，

当时：

显然，所以为最大值点，最大值为。

下面考虑求 的最小值

仅考虑可以看作是个互不相关一元函数的加和，即

求的最小值，首先对关于求一阶和二阶导数：

在定义域上，始终有，即为开口向下的凹函数，最小值在边界或处取得：

的最小值即为，同理可得的最小值也为，那么的最小值也为。

如果令某个，那么根据约束条件，可知

将其带入，得：

所以，一定是在满足的约束条件下的最小值点，其最小值为。

所以有

信息增益

假定离散属性有个可能的取值，如果使用特征来对数据集进行划分，则会产生个分支结点，其中第个结点包含了数据集中所有在特征上取值为的样本总数，记为。再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予不同的权重，这样对样本数越多的分支节点的影响就会越大，因此，就能够计算出特征对样本集进行划分所获得的“信息增益”：

ID3 算法的计算过程

我们从训练集的分类标签（好瓜）中出发，计算树根节点的信息熵：

第一层分裂

计算各属性的信息增益：

属性：色泽

色泽中，一共有三个种类，分别为青绿（6 个）、乌黑（6 个）、浅白（5 个）。其中青绿中有好瓜 3 个，坏瓜 3 个。

从青绿色属性中，可以得到的信息熵是。

同理，计算乌黑和浅白的信息熵，分别为、。根据对应具体属性值的数量，赋予不同的信息权重，即具体属性值数量所占总体数量的比例。然后得到该属性的信息熵，将根节点的信息熵减去该属性的信息熵，获得信息增益值。

属性：根蒂

属性：敲声

属性：纹理

属性：脐部

属性：触感

选择需要分裂的属性:

属性	信息增益
色泽	0.1091
根蒂	0.1427
敲声	0.1408
纹理	0.3808
脐部	0.2892
触感	0.0060

选择最大信息增益值对应的属性，进行分裂，即对纹理属性进行分裂。

第二层分裂

然后，对每个分支结点做进一步划分。以分支结点“纹理=清晰”为例，该结点包含的样本集合中有编号为 {1,2,3,4,5,6,8,10,15}的 9 个样例，可用属性集合为{色泽，根蒂，敲声，脐部，触感}，基于样本集合（“纹理=清晰”）计算出各属性的信息增益。

样本集合（“纹理=清晰”）的信息熵为：

计算各属性的信息增益值——基于样本集合（“纹理=清晰”）

属性 ：色泽

属性 ：根蒂

属性 ：敲声

属性 ：触感

选择分裂属性

属性	信息增益
色泽	0.431
根蒂	0.4581
敲声	0.3308
脐部	0.4581
触感	0.4581

选择最大信息增益值对应的属性，进行分裂。但是有三类属性的信息增益是相等的，我们可以随机选择一个属性作为分裂属性。我们这里选择根蒂属性来分裂。

同理，对纹理中的其他属性值做上述操作，得到第二层的树。

第三层分裂

接下来对上图中结点（“根蒂=稍蜷”）进行划分，该点的样本集为{6，8，15}，共有 3 个样木。可用特征集为{色泽，敲声，脐部，触感}，同样可以计算信息增益。

样本集合（“根蒂=稍蜷”）的信息熵为：

计算各属性的信息增益值——基于样本集合（“纹理=清晰”）

属性 ：色泽

属性 ：敲声

属性 ：脐部

脐部和敲声一样都只能划分出一个子集，因此脐部的信息增益也为

属性 ：触感

选择分裂属性

属性	信息增益
色泽	0.251
敲声	0
脐部	0
触感	0.251

可知“色泽”，“触感” 2 个属性均取得了最大的信息增益，选个属性作为划分属性，不妨选取“色泽”为划分属性。

最终的树模型

ID3 算法的不足

ID3 没有考虑连续特征。

ID3 采用信息增益大的特征优先建立决策树的节点，取值比较多的特征比取值少的特征信息增益大。

ID3 算法对于缺失值的情况没有做考虑。

没有考虑过拟合的问题

C4.5 算法

增益率的定义

信息增益偏向于选择取值较多的属性，容易过拟合，基于信息增益的缺点，C4.5 算法不直接使用信息增益，而是使用一种叫增益率的方法来选择最优属性进行划分，对样本集中离散属性，增益率为：

是属性的固有值（Intrinsic Value）：

增益率与信息增益的对比：

信用级别	工资级别	是否逾期
1	1	是
2	1	否
3	2	是
4	2	否

信息熵：

当前属性 ：信用级别

当前属性 ：工资级别

我们用信用级别这个属性去划分原数据集，那么，原数据集中有多少个样本，就会被划分为多少个子集，这样的话，会导致信息增益公式的第二项整体为，虽然这种划分毫无意义，但是从信息增益的概念来讲，这就是最好的划分属性。信息增益表示由于特征而使得数据集的分类不确定性减少的程度，信息增益大的属性具有更强的分类能力。根据熵的公式可知，属性越多，熵越大，因此将他将它作为分母，对分支过多的情况进行惩罚，就可以校正信息增益容易偏向于取值较多的属性的问题。

C4.5 算法的不足

C4.5 生成的是多叉树，生成决策树的效率比较慢。

C4.5 只能用于分类。

C4.5 由于使用了熵模型，里面有大量的耗时的对数运算。

CART 算法

CART 是 Classification and Regression Tree 的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。

基尼值的定义

基尼值（）用于度量数据集的纯度，反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，越小，则数据集的纯度越高。

假定当前样本集合中第类样本所占的比例为，则的基尼值为：

基尼指数的定义

基尼指数表示在样本集合中一个随机选中的样本被分错的概率。基尼指数越大，样本的不确定性也就越大。

其中表示第个类别的样本集。

参考资料

《机器学习》——周志华