决策树定义
它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。
在这个决策过程中，我们一直在对记录的特征进行提问。最初的问题所在的地方叫做根节点，在得到结论前的
每一个问题都是中间节点，而得到的每一个结论都叫做叶子节点。
决策树的核心
决策树算法的核心是要解决两个问题：
1）如何从数据表中找出最佳节点和最佳分枝？
2）如何让决策树停止生长，防止过拟合？
关键概念
原则上讲，任意一个数据集上的所有特征都可以被拿来分枝，特征上的任意节点又可以自由组合，所以一个数据集上可以发展出非常非常多棵决策树，其数量可达指数级。
全局最优：经过组合形成的，整体来说分类效果最好的模型
局部最优：每一次分枝的时候都向着更好的分类效果分枝，但无法确认如此生成的树在全局上是否是最优的
贪心算法：通过实现局部最优来达到接近全局最优结果的算法，所有的树模型都是这样的算法。
ID3、C4.5和CART
1.不纯度
决策树需要找出最佳节点和最佳的分枝方法，而衡量这个“最佳”的指标叫做“不纯度”。不纯度基于叶子节点来计算的，所以树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度一定是最低的。
决策树的每个叶子节点中都会包含一组数据，在这组数据中，如果有某一类标签占有较大的比例，我们就说叶子
节点“纯”，分枝分得好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。
如果没有哪一类标签的比例很大，各类标签都相对平均，则说叶子节点”不纯“，分枝不好，不纯度高
2.不纯度划分标准：信息熵(越小越纯)，阻尼系数(越小越好)
3.信息增益(ID3：越大越好)，信息增益比(C4.5)，阻尼系数(CART)
ID3最优条件是叶节点的总信息熵最小，因此ID3决策树在决定是否对某节点进行切分的时候，会尽可能选取使得该节点对应的子节点信息熵最小的特征进行切分。换而言之，就是要求父节点信息熵和子节点总信息熵之差要最大。对于ID3而言，二者之差就是信息增益
ID3局限主要源于局部最优化条件，即信息增益的计算方法，其局限性主要有以下几点：
(1) 分支度越高（分类水平越多）的离散变量往往子节点的总信息熵会更小，ID3是按照某一列进行切分，有一些列的分类可能不会对我需要的结果有足够好的指示。极限情况下取ID作为切分字段，每个分类的纯度都是100%，因此这样的分类方式是没有效益的
(2) 不能直接处理连续型变量，若要使用ID3处理连续型变量，则首先需要对连续变量进行离散化
(3) 对缺失值较为敏感，使用ID3之前需要提前对缺失值进行处理
(4) 没有剪枝的设置，容易导致过拟合，即在训练集上表现很好，测试集上表现很差
剪枝：防止过拟合
常用的的是预剪枝：预剪枝的核心思想是在树的结点进行扩展之前，先计算当前的划分能否带来模型泛化能力的提升，如果不能，则停止划分子节点。这时可能存在不同类别的样本同时存在该结点中，此时按照多数投票的原则来判断该结点所属类别。
预剪枝中满足以下几种条件时可以停止划分子节点：
1.当树到达一定深度时则停止
2.当结点包含的样本数量小于某个阈值时则停止
3.计算每次划分时对测试集中性能的提升，如果性能小于某个阈值或降低，则停止
预剪枝的算法简单，效率较高，适合解决大规模问题，但是如何准确地估计停止划分子节点条件时，不同的问题会有较大的差别。此外，预剪枝存在一定欠拟合的风险。
后剪枝：
后剪枝的核心思想是让算法生成一颗完全生长的决策树，然后减去置信度不高的子树，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。常见的一种后剪枝方法是从最底层向上计算是否剪枝，可以通过对测试集进行评估，如果剪枝后的结构对性能有提升则进行剪枝。相比于预剪枝，后剪枝通常可以获得泛化能力更强的决策时，但是时间开销会更大。
分类实现
class sklearn.tree.DecisionTreeClassifier (
criterion=’gini’, '只算不纯度的指标'
splitter=’best’,
max_depth=None,'决策树多生长一层，对样本量的需求会增加一倍，所
以限制树深度能够有效地限制过拟合。在集成算法中也非常实用。实际使用时，建议从3开始尝试，看看拟合的效
果再决定是否增加设定深度。'
min_samples_split=2, 'min_samples_split限定，一个节点必须要包含至少min_samples_split个训练样本，这个节点才允许被分枝，否则
分枝就不会发生。'
min_samples_leaf=1, '一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生，或者，分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生,建议从=5开始使用'
min_weight_fraction_leaf=0.0, '有了class_weight权重之后，样本量就不再是单纯地记录数目，而是受输入的权重影响了，因此这时候剪枝，就需要搭配min_
weight_fraction_leaf这个基于权重的剪枝参数来使用。'
max_features=None,
random_state=None,'是否每次都随机选取特征进行不纯度计算'
max_leaf_nodes=None,
min_impurity_decrease=0.0, '限制信息增益的大小，信息增益小于设定数值的分枝不会发生'
min_impurity_split=None,'老版本'
class_weight=None,'完成样本标签平衡的参数'
presort=False
)
min_samples_leaf 一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样
本，否则分枝就不会发生
min_samples_split 一个节点必须要包含至少min_samples_split个训练样本，这个节点才允许被分
枝，否则分枝就不会发生
重要属性和接口
八个参数：Criterion，两个随机性相关的参数（random_state，splitter），五个剪枝参数（max_depth,min_samples_split，min_samples_leaf，max_feature，min_impurity_decrease）
一个属性：feature_importances_
四个接口：fit，score，apply，predict
#apply返回每个测试样本所在的叶子节点的索引
clf.apply(Xtest)
#predict返回每个测试样本的分类/回归结果
clf.predict(Xtest)
分类中中对连续性特征的处理：(ID3 只能处理离散特征（前面示例中都是离散特征），C4.5 和 CART 都可以离散特征以及连续特征。)
回归实现：ID3 算法不支持对连续特征进行处理，C4.5 和 CART 对此作了优化。
class sklearn.tree.DecisionTreeRegressor (
criterion=’mse’, '这种方法通过使用叶子节点的均值来最小化L2损失,MAE这种指标使用叶节点的中值来最小化L1损失'
splitter=’best’,
max_depth=None,
min_samples_split=2,
min_samples_leaf=1,
min_weight_fraction_leaf=0.0,
max_features=None,
random_state=None,
max_leaf_nodes=None,
min_impurity_decrease=0.0,
min_impurity_split=None,
presort=False)
1.在回归树种，没有标签分布是否均衡的问题，因此没有class_weight这样的参数
2.回归树的接口score返回的是R平方，并不是MSE
3.其它的参数和分类树一致
决策树回归的过程：
https://blog.csdn.net/pearl8899/article/details/88671885
https://zhuanlan.zhihu.com/p/82054400
https://www.cnblogs.com/qiu-hua/p/14851292.html
