1.什么是决策树？
决策树很好理解，就是模拟了人们平时的思考方式，根据事务的特征，一层层的对事务的属性进行分析划分，最后实现对事务的归类。
算法用途 ：分类问题，数据挖掘。
优点 ：计算复杂度不高，易于理解数据中蕴含的知识信息。
缺点 ：容易出现过拟合。
2.属性划分
关键：向着数据集纯度变高的方向划分特征。
怎么判断一个数据集的纯度，混乱度？
纯度、混乱度其实就是一个数据集的信息量的表现形式。信息量越大那么就越混乱，越不纯。
而怎么用一个数值去衡量信息量？为此香农提出了信息熵。
● 信息熵 information entropy
$Ent(D)=-\sum \limits_{k=1}^{\vert y\vert}{\rho}_klog_2{\rho}_{k}$
Ent(D)越小，则数据纯度越高，混乱度越小。
● 基尼值 Gini index
$Gini(D)=\sum\limits_{k=1}^{\vert y\vert}\sum\limits_{k’\neq k}\rho_k\rho_k’=1-\sum\limits_{k=1}^{\vert y\vert}\rho_k^2$
Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。
Gini(D)越小，则数据纯度越高，混乱度越小。
每次决策都会将数据集进行分割。怎么表示多个数据集的混乱度？
对于多个数据集，只需要算出各自的信息量，然后分配权重，求和即可。
★ 信息熵指数
$Ent_index=\sum\limits_{v=1}^{V}\frac{\vert D^v\vert}{ {\vert D\vert} }Ent(D^v)$
● 基尼指数(Gini index)
$Gini_index(D,a)=\sum\limits_{v=1}^V\frac{\vert D^v\vert}{ {\vert D\vert} }Gini(D^v)$
表示数据混乱度的方法有了，那算法应该具体怎么应用呢？
虽然我觉得直接用这两个指数就完事了，但事实当然不可能这么简单
★ ID3决策树(Quinlan,1986)以信息增益为准则来选择划分属性。
信息增益： $Gain(D,a)=Ent(D)-\sum\limits_{v=1}^{V}\frac{\vert D^v\vert}{\vert D\vert}Ent(D^v)$
增益越大说明“纯度”提升越快。但是，信息增益有个弊端，那就是对取值数目较多的属性有所偏好（可以想象当属性种类非常多时，比如不小心把编号当成的属性，这时划分出来的子集纯度都饱和，这明显是不利的）。
★ 于是Quinlan大佬在C4.5决策树中提出了用信息增益率来作为准则划分属性。
信息增益率： $Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$ $IV(a)=-\sum\limits_{v=1}^{V}\frac{\vert D^v\vert}{\vert D\vert}\log_{2}\frac{\vert D^v\vert}{\vert D\vert}$
IV(a)被称为属性a的“固有值(intrinsic value)”,实际上就是a属性的信息熵。但问题又来了，这样一处理，变的对取值数目较少的属性有所偏好了。于是C4.5 采用了启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
● CART决策树(Breiman et al.1984)则是直接选择了基尼指数作为准则，每次选指数最低的属性进行划分。
3.减枝 pruning
有了划分的方法，那么就可以生成一颗决策树了。但是这个时候问题又来了！过拟合 ！决策树是十分容易过拟合的！因为每次划分，属性有几类，就会生成几个分支，在实际中这完全没有必要。甚至在不含冲突数据的训练集中，能生成训练误差为0的决策树。于是就有了减枝处理，将那些不必要的分支去除~
那么怎么判断一个分支需不需要？
这个时候就需要用验证集来帮助进行性能评估了。逮到一个非叶节点，用验证集测试一下，看看在这个节点分类和不分类的情况下，正确率有多少。如果发现分类后反而准确率降低了或不变(奥卡姆剃刀准则)，那么就可以将这个节点剪去。（在不分类的情况下，可以用该节点数据集中最多数量的label来替代该节点）
什么时候减枝比较好？
★ 预减枝： 在决策树生成的过程中，每次划分都进行判断。
优点：贪心，早发现早处理。可以显著减少决策树的训练时间开销和测试时间开销。
缺点：欠拟合风险。因为有些分支在当前节点划分可能不利于泛化性能，但在其基础上进行的后续划分却可能导致性能的提升。
★ 后减枝：生成完整个树后，自下而上对非叶节点进行判断。
优点：欠拟合风险很小，泛化性能优于预减枝。
缺点：训练时间大大增加。
4.连续值与缺失值
到目前为止，我们处理的都很开心。但这个时候又有一个问题出现了！之前的属性值都是离散的都是完整的所以很容易的就进行了划分，但实际中往往并不是。
连续值怎么处理？
连续值在属性中十分常见，我们不可能把他和离散值一样处理，想想前面信息增益的遭遇，我们就能明白一个过多分类的属性对于决策树的泛化性能是不利的。这个时候就需要连续属性离散化技术了。
采取了最简单的策略–二分法(bi-partition):这种策略简单的来说就是将连续值分为大于某个值的类和不大于某个值的类。
那么这个“某个值怎么确定”？
当然是一个个试过来啦！你可以直接取每个值试一下，也可以取排序后相邻值的平均值来试一下，然后从中选择那个对信息量最友好的值作为二分法的阈值。
另外注意： 这个属性被二分之后，还能作为后代节点的划分属性！
缺失的值怎么处理
缺失值相比连续值处理起来就麻烦多了。因为有总比没有好。
C4.5算法使用了分配权重的方法进行解决。其核心思想是：缺失样本的分布和未缺失样本的分布一致。
先定义一些接下来要用到的东西：训练集D，属性a，无缺失值的子集D‘，属性a有V个取值，最后给每个样本x赋予一个权重Wx(初始为1)
那么在属性缺失的情况下怎么进行划分属性的选择？
en…………………首先当然只能从存在的V个属性值中选择~然后进行信息增益值的计算。
由于有缺失值所以信息增益的公式需要变化：
$Gain(D,a)=\rho*(Ent(D’)-\sum \limits_{k=1}^{V}r’_vEnt(D’^v))$
$Ent(D’)=-\sum \limits_{k=1}^{\vert y\vert}p’_klog_2p’_{k}$
$\rho=\frac{\sum_{x\in D’} W_X}{\sum_{x\in D} W_X}$ 无缺失样本所占的权重比。
$p_{k}’= \frac{\sum_{x\in D’_{k}} W_X}{\sum_{x\in D’} W_X}$ 无缺失样本中每类所占的权重比。
$r_{v}’=\frac{\sum_{x\in D’_{v}} W_X}{\sum_{x\in D’} W_X}$ 无缺失样本中，属性取值为V时所占的权重比。
实际上就是先将有缺失样本无视，计算无缺失样本的Gain,最后再乘以无缺失样本所占的权重比，作为整体Gain。
那么有了划分属性，怎么对缺失样例进行划分呢？
很明显，既然已经给每个样例赋值了权重，那么现在就是分配权重的时候了。
对于无缺失的样例，当然是直接归类，权重不变。
对于有缺失的样例，则同时划入所有的子节点，权重变为$r_{v}’$*$w_{x}$ 。也就是让同一个样本以不同的概率划入不同的子节点中去。
5.多变量决策树
对于这部分，就了解一下，反正实现是做不到的了。
什么是多变量？
多变量指的就是每次决策同时对多个属性下手！
前面讲到的决策树都是每次只对一个属性进行划分，这会造成这种决策树的分类边界会比较死板，呈现轴平行的特征，就像用一段段与轴平行的线段去拟合边界。当边界比较复杂时，会导致决策树很复杂，很庞大，导致开销很大。
而如果多个变量同时分类，那么就能够画出斜线甚至曲线的分类边界了，这样不但拟合的更好，还能使决策树更精简。
怎么实现多变量？
这就比较麻烦了，需要在每个节点都设置一个线性\非线性分类器。说白了就是每个节点都要进行一次独立的分类。比如在节点上嵌入一个线性分类器，嵌入一个神经网络，或者嵌入一个感知机什么的。
6. CART
classification and regression tree，即分类与回归树。而ID3和C4.5只能做分类。
CART最大的不同点正在于，其是二叉树，左右枝取值为“是”和“否”。另外其划分策略也不同。
分类树生成
划分准则
对于分类问题，采用基尼指数（Gini index）来判断分界点。Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini(D)越小，则数据纯度越高，混乱度越小。
${\rm Gini(D)}= \sum_{k=1}^Kp_k(1-p_k) = 1 -\sum_{k=1}^Kp_k^2$
可以看到基尼指数和信息熵是很相近的，但gini指数的计算简单很多，使得算法更高效。
具体划分
CART的划分不是按照特征进行划分，而是按照特征的取值进行划分。样本被分为“是”和“否”两个子树。通过基尼指数选取最优划分点。
这样做的好处在于每次都是二分类，避免像ID3倾向于取值较多的变量，C4.5倾向于取值较少的变量。
回归树生成
划分准则
回归树采用平方误差最小化为准则。
$\min_{j, s} \left[ \min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i -c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j, s)} (y_i -c_2)^2 \right ] $
c1,c2为对应的R1,R2部分的均值：$\hat c_m = {1\over N_m}\sum_{x_i\in R_m(j,s)}y_i , \quad x\in R_m , m=1,2$
简单来说就是一个节点中的样本要和样本均值尽量接近。
具体划分
同样是按照特征取值进行划分：$R_1(j,s) = {x|x^{(j)} \le s} \ R_2(j,s) = {x|x^{(j)} \gt s}$
实际中一般不直接用特征取值s来作为切分点，而先把特征的取值排序{v1,v2,⋯,vn}，然后可能的阈值有：${\frac{v_1 + v_2}{2},\frac{v_2 + v_3}{2},\cdots,\frac{v_{n-1} + v_n}{2} }$。和C4.5中处理连续变量的方法一样。
最后叶节点的value即为预测值，也称为该叶节点的得分。