决策树1-基本概念
决策树1- 基本概念
决策树
上图来自西瓜书，是决策树的一种树形。生成决策树的过程，不断的根据样本的属性( 样本的某个特征 )划分样本子集。每个结点选择当前最优的属性作为划分依据，将样本集合不断的划分成更小的子集合，直到子集合中样本类别一致时或者没有可以划分的属性值时，则停止划分，标记为叶结点(叶节点代表一个类别)。
简单的介绍一下决策树的组成元素:
- 根节点: 所有的训练样本
- 内部节点: 对应某一个划分属性
- 叶节点： 对应某一种决策结果
- 判定测试序列： 某个样本在节点中传递的路径
所有节点都包含着不同数量的样本。
以上是分类树的例子，决策树也可以用作回归任务，如CART算法。决策树是GBDT,Xgboost等更高级结构的基础，所以尽量要掌握决策树的原理。
决策树算法的基本流程
假设有一个数据集，其中的每个样本有多种特征，每个特征有不同的取值。通过这个数据集来生成一个决策树的一般流程可以归纳为:
- 特征选择
特征选择就是决策树分叉时，依据新节点的”纯度”，选择最优的划分属性;
- 决策树生成
树不断的分叉，直到样本的属性用光，或者树的深度达到了预定值，则结束分叉;
- 剪枝
如果一直树杈分下去，一定能够使得所有的样本都正确的归类，但这样会产生对训练集的过拟合，泛化能力变差，可以通过剪枝操作来改善泛化能力。
通过这三步，就可以生成一颗决策树了。下面来学习一下具体怎么进行特征的选择和剪枝。
如何选择最优的划分属性(分类树)?
决策树不断分叉的原因，是尽可能的让不同类别的样本划分到不同的节点，同类别的样本划分到同一个节点。而选择最优的划分属性（特征）的过程，相当于是遍历计算出所有特征的结果，找到能使分叉后子集合最 “纯” 的特征，就是最优的划分属性了。
所以，该如何定义 “纯” ，需要借助信息论中 “信息熵” 的概念了。
熵 : 表示随机变量不确定性的度量,也就是混乱程度的一种度量。
假定数据集 D 中第 K 类样本所占的比例为
数据集包含的类别越少时越纯，Ent(D)也越小。
法1: 信息增益
==ID3算法用到信息增益==
直白的讲就是决策树分叉前的信息熵减去分叉后的信息熵。
信息增益最大的特征就是最佳划分属性。
假定分叉前样本集 D 中的特征 a 有 V个可能的取值 a 做划分属性时，会分V个节点，每个节点上的子样本集合为
减数部分也叫 条件熵
缺点: 分叉时偏好取值较多的属性。 原因分析:- 取值多的特征，样本更分散，所有得到的新节点”纯度” 趋于更高，熵更低，而划分前的增益不变的情况下，该特征增益更大。
- 比如，当特征的可能取值数量正好等于样本数量，那条件熵几乎为0，该特征一定会被选择。
法2: 信息增益率
==C4.5算法用到信息增率==
相当于在法1基础上，增加了惩罚系数，可取值越多，系数越大。
IV(a) 是属性 a 的 “固有值”，内部属性。
缺点: 分叉时偏好取值较少的属性。
法3：基尼指数
==CART决策树算法用到基尼指数==
反应从节点样本集合中随机抽取两个样本，类别不一致的概率。CART决策树默认为二叉树。
基尼值的定义:
选择特征 A 的情况下，针对 A 所有可能取值 a, 分别计算基尼指数：
选择基尼指数最小的特征和切分点，作为最优划分属性。
三种决策树模型：
| 算法 | 特征选择标准 |
|---|---|
| ID3 | 信息增益 |
| C4.5 | 信息增益率 |
| CART | 基尼指数 |
对抗过拟合 — 剪枝处理
分支太多，容易过拟合，泛化能力变差。所以要适当剪枝，常用方法是预剪枝和后剪枝
剪枝操作包括的点也很多，这里只是简单描述一下，详细的参考未来的博客。www.elgong.top
预剪枝
- 预剪枝是在决策树生成的过程中，对每个结点在划分前先估计，根据划分前后验证集的精度，来决定是否划分；
- 只能估计当前结点可划分性，不能预测到未来节点划分的必要性，是贪心算法；
- 容易造成欠拟合。
后剪枝
- 先生成完整的树，再从叶结点往回计算，根据验证集精度是否提升决定是否剪枝；
- 泛化能力往往优于预剪枝，欠拟合风险小；
- 时间开销大。
属性为连续值时？
C4.5 算法采用二分法将连续值离散化
与离散属性不同，连续的属性可以在后代节点中再次使用
当数据中含有缺失值时？
处理方法：
通过无缺失数据计算出三个参数：
- 无缺失样本占总样本比例
- 无缺失样中
K类别占比pk - 无缺失样本中
v 属性样本占比rv
对单样本增加一个权值 Wx, 无缺失样本的Wx = 1， 有缺失样本的Wx = rv*Wx。
在计算分支时，同一样本以不同的概率划分到不同的子节点中
- 当样本的属性已知：则把该样本划分进对应的子节点，权值=1；
- 当样本的该属性缺失：则把该样本同时划入所有的子节点，样本权值需要更新为`Wx = rv*Wx。
决策树的优缺点
==优点==：
- 便于理解和可视化；
- 训练需要的数据少，不需要对数据进行规范化；
- 可同时处理数值型，类别型数据；
- 是白盒模型，可解释；
==缺点==：
- 容易产生过于复杂的模型 -> 泛化能力差 （剪枝，限制叶节点所需要的最小样本数，最大深度）
- 决策树不稳定，微小变化会产生不同的树（集成多棵树可以缓解）
- 难学NP问题（启发式学习）
- 异或，奇偶，很难被学习到