机器学习算法决策树（一）+https://developer.aliyun.com/article/1544086?spm=a2c6h.13148508.setting.17.1fa24f0ewU5jCe
ID3 决策树
ID3 树是基于信息增益构建的决策树
- 熵在信息论中代表随机变量不确定度的度量。
- 熵越大，数据的不确定性度越高
import numpy as np import matplotlib.pyplot as plt def entropy(p): return -p*np.log(p)-(1-p)*np.log(1-p) x = np.linspace(0.01,0.99,200) plt.plot(x,entropy(x)) plt.show()
信息增益
信息熵是一种衡量数据混乱程度的指标，信息熵越小，则数据的“纯度”越高
ID3算法步骤
- 计算每个特征的信息增益
- 使用信息增益最大的特征将数据集 S 拆分为子集
- 使用该特征（信息增益最大的特征）作为决策树的一个节点
- 使用剩余特征对子集重复上述（1，2，3）过程
C4.5 决策树
信息增益率计算公式
如果某个特征的特征值种类较多，则其内在信息值就越大。特征值种类越多，除以的系数就越大。
如果某个特征的特征值种类较小，则其内在信息值就越小
C4.5算法优缺点
- 优点：分类规则利于理解，准确率高
- 缺点
- 在构造过程中，需要对数据集进行多次的顺序扫描和排序，导致算法的低效
- C4.5只适合于能够驻留内存的数据集，当数据集非常大时，程序无法运行
- 无论是ID3还是C4.5最好在小数据集上使用，当特征取值很多时最好使用C4.5算法。
CART 分类决策树
Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归
（1）决策树生成：用训练数据生成决策树，生成树尽可能大
（2）决策树剪枝：基于损失函数最小化的剪枝，用验证数据对生成的数据进行剪枝。
分类和回归树模型采用不同的最优化策略。Cart回归树使用平方误差最小化策略，Cart分类生成树采用的基尼指数最小化策略。
Criterion这个参数正是用来决定模型特征选择的计算方法的。sklearn提供了两种选择：
- 输入”entropy“，使用信息熵（Entropy）
- 输入”gini“，使用基尼系数（Gini Impurity）
基尼指数：
- 信息增益（ID3）、信息增益率值越大（C4.5），则说明优先选择该特征。
- 基尼指数值越小（cart），则说明优先选择该特征。
剪枝
剪枝是决策树学习算法对付过拟合的主要手段。
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合
决策树的构建过程是一个递归的过层，所以必须确定停止条件，否则过程将不会停止，树会不停生长。
先剪枝和后剪枝
- 先剪枝就是提前结束决策树的增长。
- 后剪枝是在决策树生长完成之后再进行剪枝的过程。
- 预剪枝使决策树的很多分支没有展开，不单降低了过拟合风险，还显著减少了决策树的训练、测试时间开销。
- 后剪枝比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。
