type
status
date
slug
summary
tags
category
icon
password
决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回:
- 当前结点包含的样本全属于同一类别，无需划分;
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
- 当前结点包含的样本集合为空，不能划分.
在第 (2)种情形下，我们把当前结点标记为叶结点，井将其类别设定为该结点所含样本最多的类别；在第 (3)种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同：情形 (2)是在利用当前结点的后验分布，而情形(3)则是把父结点的样本分布作为当前结点的先验分布.
情形（2）是后验分布，是指在已知样本 的情况，推测出的当前结点所属的类别，即 ；而情形（3）是先验分布，是因为当前结点没有样本集合给我去做推断，而是去利用已知的父结点分布做先验，即我们预先假设，是一种脱离样本的假设条件。
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 的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。
基尼值的定义
基尼值（）用于度量数据集的纯度， 反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此， 越小，则数据集的纯度越高。
假定当前样本集合 中第 类样本所占的比例为 ，则 的基尼值为：
基尼指数的定义
基尼指数表示在样本集合中一个随机选中的样本被分错的概率。基尼指数越大，样本的不确定性也就越大。
其中 表示第 个类别的样本集。