机器学习-决策树算法梳理
学习任务：
- 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）
- 决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
- 回归树原理
- 决策树防止过拟合手段
- 模型评估
- sklearn参数详解，Python绘制决策树
决策树的3个步骤：特征选择、决策树的生成、决策树的修剪
1、信息论基础
熵（entropy）：表示随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。
联合熵：度量随机变量集合的不确定性。
条件熵 H(Y|X)：在已知随机变量X的条件下，对随机变量Y的不确定性的度量。定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
信息增益：表示得知特征A的信息而使得对数据集D的分类的不确定性减少的程度。
定义：特征A对训练数据集D的信息增益g(D,A)定义为，集合D的经验熵（熵的估计）H(D)与特征A给定条件下D的经验条件熵（条件熵的估计）H(D|A)之差，即：
在属性选择时，要选择信息增益大的属性。
基尼不纯度（基尼指数）：反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini(D)越小，则数据集D的纯度越高。
在属性选择时，要选择那个使得划分后基尼指数最小的属性最为最优划分属性。
2、决策树的不同分类算法（原理及应用场景）
ID3算法：以信息增益为准选择决策树的属性，注意信息增益偏好可取值数目较多的属性。该算法生成的树容易产生过拟合。
C4.5算法：使用信息增益比选择最优划分属性，矫正了ID3可能存在的问题。注意增益率偏好可取值数目较少的属性。
CART算法：分类与回归树模型，假设决策树是二叉树，递归地二分每个特征。既可用于分类（基尼指数最小化准则）也可用于回归（平方误差最小化准则-最小二乘回归树）。
3、回归树原理
决策树是基于树结构来进行决策的，由结点和有向边组成，结点包括内部节点（表示一个特征或属性）、叶节点（表示一个类）。
使用决策树进行决策（即分类）的过程，从根节点开始，对某一特征或属性进行“测试”，每个测试结果将分配到相应的子节点（即内部节点），对应着该特征的一个取值，如此递归直到到达叶节点，将叶节点的结果作为分类决策结果。
决策树模型可以认为是If-then规则的集合，也可以认为是在给定特征条件下类的条件概率分布。我们希望决策树模型与训练数据矛盾较小，同时具有很好的泛化能力。
决策树的损失函数通常是正则化的极大似然函数，学习策略是以损失函数为目标函数的最小化。
算法步骤：递归选择最优特征，并根据这一特征对训练数据集进行分割，直到各个子数据集有一个最好的分类。（李航. ch5. p57-58）
4、决策树防止过拟合手段
一棵树如果结点过多，可能对训练数据有很好地分类能力，但未必能很好地对未知数据进行分类，表明该模型可能发生了 “过拟合”。
解决方法：
1. 剪枝（pruning）：去掉过于细分的叶结点，使其退回父结点甚至更高的节点，简化树模型。
2. 特征选择：在决策树学习开始前，对过多的特征进行选择，留下对训练数据有足够分类能力的特征。即决定用哪个特征（作为根结点）来划分特征空间。
准则：信息增益或信息增益比
（西瓜书. ch4. p79）：
4.1.1、预剪枝(prepruning)
在决策树生成过程中对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
判断准则：熵的减小量
优点：降低过拟合；时间开销小
缺点：有欠拟合风险
4.1.2、后剪枝(postpruning)
先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换成叶结点能带来决策树繁华性能的提升，则将该子树替换成叶结点。后剪枝是目前最普遍的做法。
判断准则：熵的增加量
优点：欠拟合风险小，泛化性能优于预剪枝
缺点：时间开销大
5、模型评估
5.1 常用的对泛化性能的评估方法
（西瓜书ch2、参考网址（3））
通过测试集上的测试误差作为泛化误差的近似。以下是从数据集D中产生出训练集S和测试集T的常见做法。
留出法（hold-out）：直接将数据集D划分为两个互斥的集合。
交叉验证法（cross-validation）：先将数据集D划分为k个大小相似的互斥子集；然后每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集；最后返回k次训练和测试结果的平均值。
自助法（bootstrapping）：以自助采样法为基础，在数据集较小、难以有效划分训练/测试集时很有用。
5.2 性能度量
分类任务常用性能度量，如错误率、精度、准确率、召回率等，见逻辑回归算法梳理。
6、sklearn参数详解，Python绘制决策树
- from sklearn.tree import DecisionTreeClassifier
- DecisionTreeClassifier(criterion=“gini”,
splitter=“best”,
max_depth=None,
min_samples_split=2,
min_samples_leaf=1,
min_weight_fraction_leaf=0.,
max_features=None,
random_state=None,
max_leaf_nodes=None,
min_impurity_decrease=0.,
min_impurity_split=None,
class_weight=None,
presort=False)
参数含义：详见参考（4）
Python决策树算法：详见参考（5）
参考：
1.《统计机器学习》
2.西瓜书
3.https://www.cnblogs.com/fushengweixie/p/8039991.html
4.手推XGBT&sklearn参数：https://github.com/Bruce-zhangyuyang/Algorithm-exercises/blob/master/3.决策树算法梳理.md
5.https://github.com/apachecn/AiLearning/blob/dev/blog/ml/9.树回归.md