决策树：ID3,C4.5,CART树总结

树模型总结
决策树部分重点关注分叉的指标，多叉还是单叉，处理离散还是连续值，剪枝方法，以及回归还是分类

一、决策树
ID3(Iterative Dichotomiser 3) 、C4.5、CART决策树
ID3:确定分类规则判别指标、寻找能够最快速降低信息熵的方式进行数据集划分（分类规则提取）
C4.5:一方面使得现在的树模型能够处理连续变量（此前的ID3只能处理分类变量），同时也能够一定程度提高树模型的生长速度，而C4.5也是目前最为通用的决策树模型的一般框架
CART决策树:分类与回归决策树,拓展了回归类问题的计算流程（此前C4.5只能解决分类问题）,并且允许采用更丰富的评估指标来指导建模流程,CART树还能够用一套流程同时处理离散变量和连续变量、能够同时处理分类问题和回归问题

二、CART树：
先考虑自变量都是离散变量的分类预测问题，再逐步拓展连续变量的处理方法和回归类问题的预测方法。
划分标准：不纯度，一般有三种，分别是分类误差、信息熵和基尼系数，
（1）分类误差：𝐶𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝑒𝑟𝑟𝑜𝑟(𝑡)=1−max1≤𝑖≤𝑐[𝑝(𝑖|𝑡)]
例如某个包含10条数据的数据集，有6条0类数据、4条1类数据，此时该数据集分类误差就是1-6/10 = 0.4。分类误差在[0, 0.5]范围内取值，分类误差越小，说明数据集标签纯度越高。
(2)信息熵（Entropy）：𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑡)=−∑ 𝑖=1 𝑐  𝑝(𝑖|𝑡)𝑙𝑜𝑔2𝑝(𝑖|𝑡)
(3)基尼系数（Gini）：𝐺𝑖𝑛𝑖(𝑡)=1−∑ 𝑖=1 𝑐   𝑝(𝑖|𝑡)2
规则创建：每两个点取中间值，因此离散和连续变量一样处理
CART树用这种方法同时处理离散和连续变量，而C4.5只用这种方式处理连续变量。因此CART树是将离散变量视为连续变量来处理
剪枝：前主流的C4.5和CART树都采用的是后剪枝的方法，其中C4.5是通过计算叶节点的期望错误率（一种区间估计的方法）来进行剪枝，而CART树则是通过类似正则化的方法在损失函数（基尼系数计算函数）中加入结构复杂度的惩罚因子，来进行剪枝。
实操中用决定树模型复杂度的参数(树深度等来剪枝）

分类树：
DecisionTreeClassifier的参数：

重点参数：
criterion：不纯度衡量指标
ccp_alpha：结构风险权重

控制树结构的参数类：
 这类参数可以进一步细分成两类，其一是限制模型整体结构，主要包括限制树深度的max_depth参数和限制叶节点数量的max_leaf_nodes参数。
 第二类就是限制树生长的参数，包括从节点样本数量限制树生长的参数，包括min_samples_split、min_samples_leaf两个参数，当然也有从损失值降低角度出发限制树生长的参数，包括min_impurity_split和min_impurity_decrease参数。
 树的最大深度：指的是树的最多生长几层，或者除了根节点外总共有几层，并不是树的总共的层数。

控制迭代随机过程的参数类：
主要包含两个，其一是splitter参数，当该参数取值为random时其实是随机挑选分类规则对当前数据集进行划分，其二是max_features，该参数可以任意设置最多带入几个特征进行备选规律挖掘，只要该参数的设置不是带入全部特征进行建模，就相当于是给备选特征随机划个范围，也相当于是给树模型的训练增加了一定的随机性。

CART回归树：
区别：划分标准是MSE/MAE(MAE实际上计算的是预测值和真实值的差值的绝对值再除以样本总数)
𝑀𝐴𝐸=1𝑚∑𝑖=1𝑚|(𝑦𝑖−𝑦̂ 𝑖)|
也就是说，MSE是基于预测值和真实值之间的欧式距离进行的计算，而MAE则是基于二者的街道距离进行的计算
注意，criterion不仅是划分方式挑选时的评估标准，同时也是划分子数据集后选取预测值的决定因素。MSE下取均值，MAE下取中位数。
如果希望模型对极端值（非常大或者非常小的值，也被称为离群值）的忍耐程度比较高，整体建模过程不受极端值影响，可以考虑使用mae参数（就类似于中位数会更少的受到极端值的影响），此时模型一般不会为极端值单独设置规则。

三.ID3、C4.5决策树的建模流程
ID3无法处理连续型特征、也无法处理回归问题.如果带入训练数据有连续型变量，则首先需要对其进行离散化处理，也就是连续变量分箱。
ID3和CART树区别：
CART树是在所有特征里找一个切点做二分，而ID3是在一列里根据所有切分点做多叉树
CART树的备选规则就要多的多，这也使得CART树能够进行更加精细的规则提取；

C4.5:
三个优化：在衡量不纯度降低的数值计算过程中引入信息值概念来修正信息熵的计算结果，以抑制ID3更倾向于寻找分类水平较多的列来展开的情况，从而间接抑制模型过拟合倾向
其二则是新增了连续变量的处理方法，也就是CART树中寻找相邻取值的中间值作为切分点的方法；
其三是加入了决策树的剪枝流程，使得模型泛化能力能够得到进一步提升。
缺点：尽管有如此改进，但C4.5仍然只能解决分类问题，其本质仍然还是一种分类树。

节点划分：
1.I�𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑉𝑎𝑙𝑢𝑒=−∑𝑖=1𝐾𝑃(𝑣𝑖)𝑙𝑜𝑔2𝑃(𝑣𝑖)
注意这里的比例不再是各类样本所占比例，而是各划分后子节点的数据所占比例
𝐺𝑎𝑖𝑛 𝑅𝑎𝑡𝑖𝑜=𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝐺𝑎𝑖𝑛/𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑉𝑎𝑙𝑢𝑒来指导具体的划分规则的挑选

2.离散变量是一次消耗一列来进行展开（有可能多分叉），而连续变量则一次消耗一个切分点，因此和CART树一样、同一个连续变量可以多次指导数据集进行划分。

对比总结图