4.1 基本流程
1.决策树的基本结构
1）根结点：相当于树的根
2）内部结点(决策结点)：相当于树的枝干
3）叶结点 (结果结点)：相当于树的叶子
2.决策树的基本流程
决策树的基本流程基于决策树的结构来进行的，遵循”分而冶之“的策略，其流程如下所示。设我们训练集为D，有m个样本，每个样本的属性有d个，构成属性集A。
实际上，决策树的流程是一个递归的过程，而递归需要递归出口(让递归结束)。决策树的流程有三个递归出口
-
当前结点包含的样本全属于同一类别，无需划分
(样本为同一类别，没有需要划分的属性了)递归出口1 -
当前结点包含的样本集合为空，不能划分
(没有该属性取值下的样本)递归出口2 -
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
(属性集为空或者有属性但是全部样本属性值一样无需划分)
(属性用完了)递归出口3
举例：
我们要用决策树判断好人还是坏人。样本集D为100个人，100人里面有30个好人、70个坏人。属性集A为{性别，年龄段，地方}，取值分别为(男，女)、（青年、中年、老年）、(北京、上海)。
递归出口1：当前结点包含的样本全属于同一类别，无需划分
假设第一次划分是根据性别划分，然后有50个男人50个女人。我们发现，男人这个子节点50个全是坏人，毕竟男人都是大猪蹄子。这50个坏男人里面，有青年有中年也有老年，有北京的也有深圳的，但无所谓了，没必要再继续划分。这就是第一个终止条件
递归出口2：当前结点包含的样本集合为空，不能划分
对女人，我们还要继续考察，假设接下来我们是按照年龄段划分的子节点，然后我们发现，老年这个子节点里一个样本都没有。这肯定是没办法继续划分了。问题是，那么我们如何归类这个子节点呢？如果来了一个“老女人”让我们判断，该判断为好人还是坏人呢？答案是利用父节点来判断，老女人这个子节点为空，但是它的父节点是30个好人20个坏人。我们无法判断一个老女人的好坏，但是既然一个女人有60%的可能性是好人，那么我们就也把老女人判断为好人吧！这就叫先验概率。
递归出口3：属性用完了
例子来源：https://www.jianshu.com/p/d153130b813f
4.2 划分选择
1.决策树关键
从决策树的流程可以看出，关键在于第8行，如何选择最有划分属性，即根结点。
2.选择根结点的依据
-
信息增益
设y是类别，如好、坏。
设k是样本属于第k类，k取1、2、3……y，如第1类是好、第2类是坏
设pk是样本集合D中第k类样本数目的占比。即第k类样本数目/m个样本
1） 信息熵(Ent)：度量样本集合纯度的指标。数据集D的Ent为
Ent的值越小，则D的纯度越高。
设属性集A，包括多个属性，对离散属性a的取值可能有V个，(av1,av2,av3,……,av)，用a来对D进行划分，则会产生V个分支结点。其中Dv表示，属性a下取值为av的样本。如，有15个西瓜，有三种属性，其中属性a是"色泽"，取值{1青绿,2浅白,3乌黑}，其中取值青绿的有D1=6，取值浅白的有D2=6，取值乌黑的有D3=3。
每个分支结点的权重为：|Dv| / |D|，样本数越多的分支结点影响越大。
Dv的信息熵为：Ent(Dv)，即关键求在在Dv里，有多少样本是属于第k类的占比。如，上面D1=6，其中2例是好瓜，4例是坏瓜。那么
Ent(D1) = -((2/6) * log2(2/6) + (4/6) * log2(4/6))
2） 信息增益
通过上面的铺垫后，我们可以给出用属性a对D进行划分所获得的"信息增益"公式：
信息增益越大，则意味着使用属性a来进行划分所获得的"纯
度提升"越大，故我们可以使用信息增益来进行决策树的划分选择。
举例：
3）求信息增益及画出决策树的步骤
① 求数据集D的信息熵Ent(D)
② 选择一个属性a，找出每个取值所在的样本数目，然后求占D的比例，即权重Dv/D。
③ 求每个取值的信息熵Ent(Dv)。
④ 重复上面步骤，求出其他属性的信息增益。
⑤ 选择最大信息增益，然后画出根结点的结果，然后重复上述步骤，直到得到决策树。
下面这个链接有相关的代码和解释
https://www.jianshu.com/p/14a9e8d1f2a3
-
增益率
1）属性a的"固有值"属性a的可能取值数目越多，固有值通常越大。 固有值看起来很像信息熵，以下是它们的区别固有值固有值与信息熵的区别
2）增益率
3）增益率准则与信息增益准则的区别
信息增益准则：选择信息增益大的。但是信息增益准则对可取值数目较多的属性有所偏好。易导致泛化能力差。
增益率准则：选择增益率大的。但是增益率准则对可取值数目较少的属性有所偏好。
因此，C4.5决策树算法，结合了两个指标，使用了启发式：
先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
-
基尼系数(CART决策树算法使用的度量)
1）基尼值含义：从数据集中随机抽取两个样本，其类别不同的概率。基尼值越小，数据集D纯度越高。基尼值，k指类别2）基尼系数
基尼系数3）准则
在属性集A中，选择那个基尼系数最小的属性作为最有划分属性。
4.3 剪枝处理
1. 剪枝作用
防止决策树学习算法出现"过拟合"的问题。
2. 剪枝处理的基本策略
设有数据集D，划分为训练集和测试集。
1）预剪枝：要对划分前后泛化性能进行评估。对比决策树某节点生成前与生成后的泛化性能。有所提升就停止剪去该分支。
下面由例子来说明预剪枝。
基于信息增益原则，属性"脐部"的最大，选择"脐部"作为最优划分属性，问题来了，是否应该进行划分呢？预剪枝要通过比较划分前后，泛化性能的大小来估计。
① 未划分前，根据训练集，类别标记为训练样例数最多的类别。这里选择"好瓜"。
当所有节点集中在根节点，所有训练集属于标记类别的仅有{4,5,8}，因此分类正确的是3/7 * 100%=42.9%。
| 编号 | 好瓜 |
|---|---|
| 4 | 是 |
| 5 | 是 |
| 8 | 是 |
| 9 | 否 |
| 11 | 否 |
| 12 | 否 |
| 13 | 否 |
| 3/7 = 42.9% |
且可以看出，测试集中分类正确的结果为5/7 = 71.4%
| 编号 | 按脐部划分分类正确的 |
|---|---|
| 4(凹陷) | 分类正确 |
| 5(凹陷) | 分类正确 |
| 8(稍凹) | 分类正确 |
| 9(稍凹) | 分类错误 |
| 11(平坦) | 分类正确 |
| 12(平坦) | 分类正确 |
| 13(凹陷) | 分类错误 |
| 5/7 = 71.4% |
划分前和划分后，测试集分类正确的精度从42.9%上升到71.4%，因此预剪枝策略让"脐部"属性进行划分，即不剪掉这个分支。
接着继续进一步计算凹陷、根蒂特征下，其他属性的信息增益，按照最大信息增益准则选择最优属性划分"色泽"。
对于凹陷结点，进一步按照色泽进行划分后，对比划分前后的准确性：
| 编号 | 按照脐部划分 | 对凹陷，按照色泽划分 |
|---|---|---|
| 4(凹陷、青绿) | 分类正确 | 分类正确 |
| 5(凹陷、浅白) | 分类正确 | 分类错误 |
| 8(稍凹) | 分类正确 | 分类正确 |
| 9(稍凹) | 分类错误 | 分类错误 |
| 11(平坦) | 分类正确 | 分类正确 |
| 12(平坦) | 分类正确 | 分类正确 |
| 13(凹陷、青绿) | 分类错误 | 分类错误 |
| 正确率 | 5/7(划分前) | 4/7(划分后，精度降低) |
划分后，精度下降，因此不让"色泽"进行划分。
接着就是对于稍凹进行上述的操作，最优划分属性为"根蒂"，但是划分后的精度没有变化，因此预剪枝测率也不让"根蒂"进行划分，即剪掉"根蒂"结点产生的枝干。
预剪枝决策树中很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显著提高，因此预剪枝给决策树带来了欠拟合的风险。
2）后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点(结果结点)能带来决策树泛化性能提升，则将该子树换成叶结点。
完整的决策树
剪枝后：后剪枝从最底部开始剪枝，先看最底部的属性"纹理"，将其剪掉，即结点6替换成结果结点(叶结点)，剪掉的结点中包括{7,15}两个训练样本，则剪枝后的决策树为
接着往上剪结点5，即结点5替换为叶结点，包含的样本号为{6,7,15}，好瓜（2个）多于坏瓜（1个），因此选择好瓜进行标记，剪枝后的决策树为：
然后对结点②、结点③和结点①逐个进行考察(结点④不用是因为达到了递归出口1的条件)，最后结点②剪掉，结点③和①保留，产生最终的后剪枝决策树。
对比预剪枝与后剪枝生成的决策树，可以看出
后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往优于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。
4.4 连续值与缺失值
1.连续值处理
现实学习任务中，我们会遇到连续属性，它们的取值无限，因此需要进行离散化。
策略：二分法
给定数据集D，有连续属性a，假定a在D上出现了n个不同的取值，将这些连续值从小到大排序，记{a1，a2，a3，……，an}。
再设置一个划分点t，划分点将数据集D分为Dt+和Dt-，划分点t由连续属性的信息增益决定。
Dt-：包含了连续属性a取值小于t的样本。
Dt+：包含了连续属性a取值大于等于t的样本。
对相邻的连续属性取值ai 和 ai+1来说，t在它们的区间之内中取任意值产生的划分结果相同，所以我们可以产生n-1个候选划分点。可以考虑取中点，则有候选划分点集合，
对于含糖率也是一样的操作，得到
2.缺失值处理
在现实中，会经常遇见不完整的样本，即样本的某些属性值缺失。
我们需要解决两个问题：
- 如何在属性值缺失的情况下进行划分属性选择?
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?
设数据集D和属性a，a有V个取值{a1，a2，……，aV}
设D~表示D中在属性a上无缺失值的样本子集。如属性a为"色泽"，则无缺失样本为 {2，3，4，6，7，8，9，10，11，12，14，15，16，17}，14个
设D~v表示D~中在属性a上取值为av的样本子集。如色泽取值{青绿1，乌黑2，浅白3}，D~1 = {4，6，10，17}；D~2 = {2，3，7，8，9，15}；D~3 = {11，12，14，16}
设D~k表示D~中属于第k类(k∈1，2，……)的样本子集。如，西瓜有好瓜和坏瓜，k = 1(好瓜)，2(坏瓜)，
则D~1={2，3，4，6，7，8}；D~2={9，10，11，12，14，15，16，17}
假定我们为每个样本x赋一个权重wx(一开始都为1)，且定义
含义：对属性a，
ρ表示无缺失样本占全部样本的比值；
p~k表示无缺失样本中第k类样本的占比；
r~v表示无缺失样本中，取值为v的样本的占比。
∑p~k=1；∑r~v=1。
对问题一，我们可以用D~来判断属性a的优劣
我们可以将信息增益改写为
接着对问题二：
若x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且权重依旧为wx。
若x在划分属性a上的取值未知，则将x同时划入所有子结点，且权重变为原来的权重乘上与对应结点的属性值的样本在D~中的占比，即r~v * wx，就是让同一个样本以不同的概率划入到不同的子结点中去。 从问题一到问题二的举例
4.5 多变量决策树
在第一章中，我们知道了属性空间，就是每个属性都可以看成一个坐标轴，这样d个属性就形成了d维空间，而样本就是d维空间里面的一个点。样本分类就是在这个d维空间中，寻找它们的分类边界。
由于开销过大，因此我们考虑使用斜的划分边界，如图
多变量决策树不再是为每个非叶结点寻找最有划分属性，而是建立一个合适的线性分类器。如对上图的数据集D建立线性分类器。
