在上一篇，主要是学习周志华教授的西瓜书之后做的一些笔记，本篇开始转战算法及实际应用上面，希望能通过更深层次的探索，加深对决策树集成学习模型的理解。
基础概念
a、信息熵（Information Entropy）
假设X是一个有限值的离散随机变量，其概率分布满足：$p_i=P(X=x_i)，i=1,2,3…,n$
则随机变量X的熵等于：
$Ent(X) = -\sum_{i=1}^{n}p_i\log_{2}{p_i}$
信息熵Ent(X)就是随机变量x的熵，表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的度量。
从公式可知，随机变量的个数越多，状态数就越多，信息熵就越大，信息就越混乱。且当随机变量均匀分布时，熵最大。
注意点： 熵只依赖于随机变量概率分布，与随机变量的取值无任何关系。
示例讲解：考虑一个随机变量，可以有4种状态取值，并且每个状态值取得概率均等。那么:
如果仍然具有4种可能状态的{A,B,C,D}4个随机变量，每个状态的各自概率为{0.5,0.25,0.125,0.125}，此时熵为：
可以看到：非均匀分布比均匀分布的熵值要小。
证明0 ≤ Ent(X) ≤ logn
利用拉格朗日乘子法证明：
因为 $p_1+p_2+…+p_n=1$
所以有
objective： $f(p_1,p_2,…,p_n)=-(p_1\log p_1+p_2\log p_2+⋯+p_n\log p_n)$
subject to： $g(p_1,p_2,…,p_n,λ)=p_1+p_2+…+p_n-1=0$
证明如下：
1、定义拉格朗日函数：
$L(p_1,p_2,…p_n,λ)=-(p_1\log p_1+p_2\log p_2+⋯+p_n\log p_n)+λ(p_1+p_2+⋯+p_n-1)$
2、$L(p_1,p_2,…p_n,λ)$ 分别对 $p_1,p_2,⋯,p_n,λ$求偏导数，并令偏导数等于0（求出极值）：
$-(\log p_1+\log e) + λ = 0$
$-(\log p_2+\log e) + λ = 0$
……
$-(\log p_n+\log e) + λ = 0$
3、求出 $p_1,p_2,⋯,p_n$的值
因为 $p_1+p_2+…+p_n-1=0$
而上面n个式子均相等于0，只有：$p_1=p_2=…=p_n=\frac{1}{n}$
代入目标函数得到：
$f(\frac{1}{n},\frac{1}{n},…,\frac{1}{n})=-(\frac{1}{n}\log \frac{1}{n}+\frac{1}{n}\log \frac{1}{n}+⋯+\frac{1}{n}\log \frac{1}{n})=-\log(\frac{1}{n})=\log n$
由此可证明
b、条件熵（Conditional Entropy）
假设Ent(Y|X)表示在随机变量X条件下的随机变量Y的不确定性，则
$Ent(Y|X) = \sum_{i=1}^{n}p_iEnt(Y|X=x_i)，其中 p_i=P(X=x_i)$
公式变形
$Ent(Y|X) = -\sum_{i=1}^{n}p_i \sum_{j=1}^{m}P(Y=y_j|X=x_i)\log P(Y=y_j|X=x_i)$
$=-\sum_{i=1}^{n} \sum_{j=1}^{m}P(X,Y)\log P(Y=y_j|X=x_i)$
$=-\sum_{i,j=1}^{nm} P(X,Y)\log P(Y=y_j|X=x_i)，其中P(X,Y)是联合概率分布$
条件熵Ent(Y|X) = 联合熵Ent(X,Y) - 对应熵Ent(X) 证明如下：
$Ent(X,Y) = -\sum_{i,j=1}^{nm} P(X,Y)\log P(X,Y)$
$=-\sum_{i,j=1}^{nm} P(X,Y)\log P(Y=y_j|X=x_i)P(X=x_i)$
$=-\sum_{i,j=1}^{nm} P(X,Y)\log P(Y=y_j|X=x_i)-\sum_{i,j=1}^{nm} P(X,Y)P(X=x_i)$
$=Ent(Y|X)-\sum_{i,j=1}^{nm} P(X,Y)\log P(X=x_i)$
$=Ent(Y|X)-\sum_{i=1}^{n}\sum_{j=1}^{m} P(X,Y)\log P(X=x_i)$
$=Ent(Y|X)-\sum_{i=1}^{n}\log P(X=x_i)\sum_{j=1}^{m} P(X,Y)$
$=Ent(Y|X)-\sum_{i=1}^{n}(\log P(X=x_i))P(X=x_i)$
$=Ent(Y|X)-\sum_{i=1}^{n}P(X=x_i)\log P(X=x_i)$
$=Ent(Y|X)+Ent(X)$
得到证明
c、信息增益（Information Gain）
又称相对熵（Relative Entropy）
百度百科中介绍，在概率论和信息论中，信息增益是非对称的，它是度量两个概率分布P和Q两者之间的差异性的。
假设$p_i = P(X=x_i), q_i = Q(X=x_i)$ 是离散随机变量X中两个概率分布，则p对q的信息增益为：
$D_{KL}(p||q) = \sum_{i=1}^{n}p_i\log\frac{p_i}{q_i}$
$=Ent_{p_i}\log\frac{p_i}{q_i}$
性质：
如果P、Q分布概率相等，则相对熵为0
相对熵具有不对称性
相对熵恒不小于0
特征选择
在信息增益中，衡量标准是看特征能够为分类系统带来多少分辨信息，带来的信息越多，该特征就越重要。但信息增益最大的问题在于它只能考察特征对整个系统的贡献，而不能具体到某个类别上，这就使得它只适合用来做少量特征选择或者做所谓的“全局”的特征选择，而无法做“本枝叶”上的特征选择。
决策树算法
ID3算法
以信息增益为准则来选择最优划分属性
ID3算法是一种贪心算法，用来构造决策树。之所以使用贪心，只因决策树是一个NP问题，如果全部划分归纳出再评价模型是否最符合的话，将造成难以估计的计算灾难。所以最常用的处理方法就是找到“局部最优解”，或者叫“当前最优解”。同样它也是建立在奥卡姆剃刀理论基础上的（越是小型的决策树越优越于大的决策树）
核心思想：
利用信息熵原理选择信息增益最大的属性作为分类属性，递归地拓展决策树的分枝，完成决策树的构造。
决策树的生成
1、选择决策树的根结点（以属性的信息增益作为筛选标准）
2、结点属性划分
3、对划分的子结点按照步骤一反复迭代获得树的所有内部结点
4、根据根结点、内部结点以及叶结点关系构造决策树
特征属性划分
如果一个特征属性A，它包含的信息越混乱，那么这个作为特征划分就越不稳定，也就是信息增益越大，那么特征A的信息就越稳定，其代表的“纯度提升”也就越大，越能作为划分标准。
简单写下
数据集 $D$ 的信息熵表示如下（其中 $C_k$ 表示集合 $D$ 中属于第 k 类分类样本的子集）
$E(D) = -\sum_{k=1}^{K}\frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$
对于某特征A，数据集 $D$ 的条件熵 $E(D|A)$为：
$E(D|A) = \sum_{i=1}^{N}\frac{|D_i|}{|D|} E(D_i)$
$=\sum_{i=1}^{N}\frac{|D_i|}{|D|} (\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|})$
其中：$D_i$ 表示数据集 $D$ 中特征 $A$ 取第 i 值的样本子集
$D_{ik}$ 表示样本子集 $D_i$ 中属于第 k 类分类的样本子集
那么：信息增益 = 信息熵 - 条件熵
$Gain(D, A) = E(D) - E(D|A)$
不足之处
- 没有剪枝算法，因此特别容易overfit（主要由噪声和缺乏代表性样本导致）
- 以信息增益准则来制定划分标准，对特征属性可取值多的特征有偏好，类似于“编号”这类的特征，信息增益为1，但对分类决策无丝毫帮助
- 局限于处理离散分布的特征，对于连续型值特征束手无策
- 如果遇到缺失值无法有效处理
C4.5算法
以信息增益率为准则来选择最优划分属性
算法改进
引入剪枝策略（C4.5选择了后者中的悲观剪枝技术）
预剪枝（pre-pruning）：通过建立规则限制决策树的生长
后剪枝（post-pruning）：待决策树完全生长完进行剪枝处理
相比于预剪枝，后剪枝方法更常用，这是因为在预剪枝方法中精确地估计何时停止树增长会很困难。而后剪枝方法中，主要利用的技术有 Reduced-Error Pruning（REP，错误率降低剪枝）、Pesimistic-Error Pruning（PEP，悲观错误剪枝）、Cost-Complexity Pruning（CCP，代价复杂度剪枝）、Error-Based Pruning（EBP，基于错误的剪枝）
这里介绍一下悲观剪枝技术（Pessimistic Error Pruning，PEP）
假设如下：
$T_1$ 为决策树 $T$ 的所有内部结点（非叶子结点）
$T_2$ 为决策树 $T$ 的所有叶子结点
$T_3$ 为决策树 $T$ 的所有结点
$n(t)$ 为某结点 $t$ 的所有样本数
$n_i(t)$ 为某结点 $t$ 中类别 $i$ 的所有样本数
$e(t)$ 为某结点 $t$ 中不属于该结点 $t$ 所标识类别的样本数（用来计算错误率）
开始剪枝
当前结点被剪枝后在训练集上的错误率 $r(t) = \frac{e(t)}{n(t)}$
更进一步，把错误分布当成二项分布，可得
$\color{Red}{r(T_t) = \frac{\sum_{c \in \zeta _{T_t} }^{}e(c)}{\sum_{c \in \zeta _{T_t} }^{}n(c)}}$ 其中 $c$ 为 $t$ 结点的叶子结点 $\zeta _{T_t}$ 为 $t$ 的所有叶子结点数目
但是上面这个二项分布式子是有偏差的。这里面需要知道二项分布的正态逼近概念，为了修正这个概率偏差，我们用连续概率分布近似离散概率分布，在计算概率之前我们把每一个错误的结点样本数据都增加0.5，值0.5就是称为二项概率分布近似的连续性修正因子。
于是有
$r’(t) \approx \frac{e(t) + \frac{1}{2}}{n(t)}$
$\color{Red}{r’(T_t) \approx \frac{\sum_{c \in \zeta_{T_t}}[e(c) + \frac{1}{2}]}{\sum_{c \in \zeta _{T_t} }n(c)} = \frac{\sum_{c \in \zeta_{T_t}}e(c) + \frac{|\zeta_{T_t}|}{2}}{\sum_{c \in \zeta _{T_t} }^{}n(c)}}$
考虑 $r’(T_t)$ 的标准差，由于偏差近似看成二项式分布，根据 $\mu = np，\sigma ^2= np(1-p)$ 其中 $p$ = 每次试验成功的概率
这里基于分母一定，可以简化只求分子错误数的偏导，可得
$SE(e’(T_t)) = [\frac{e’(T_t) \cdot (n(t) - e’(T_t))}{n(t)}] ^{\frac{1}{2}}$
因此，只要结点满足：
$e’(t) \leq e’(T_t) + SE(e’(T_t))$
$T_t$ 结点就可以被剪枝
在网上找到一个关于悲观剪枝的例子，上面过于抽象的话可以看下面这个
悲观剪枝不足之处
这种算法使用的是从上而下的剪枝策略，这种剪枝会导致和预剪枝同样的问题，造成剪枝过渡
这种剪枝有可能会出现剪枝失败的情况
案例说明
接下来展示一组数据集及其标签，该数据集包含四个属性，$A = \{天气，温度，湿度，风速\}$，类别标签包含两个，$L = \{进行，取消\}$
| 天气 | 温度 | 湿度 | 风速 | 活动 |
|---|---|---|---|---|
| 晴 | 炎热 | 高 | 弱 | 取消 |
| 晴 | 炎热 | 高 | 强 | 取消 |
| 阴 | 炎热 | 高 | 弱 | 进行 |
| 雨 | 适中 | 高 | 弱 | 进行 |
| 雨 | 寒冷 | 正常 | 弱 | 进行 |
| 雨 | 寒冷 | 正常 | 强 | 取消 |
| 阴 | 寒冷 | 正常 | 强 | 进行 |
| 晴 | 适中 | 高 | 弱 | 取消 |
| 晴 | 寒冷 | 正常 | 弱 | 进行 |
| 雨 | 适中 | 正常 | 弱 | 进行 |
| 晴 | 适中 | 正常 | 强 | 进行 |
| 阴 | 适中 | 高 | 强 | 进行 |
| 阴 | 炎热 | 正常 | 弱 | 进行 |
| 雨 | 适中 | 高 | 强 | 取消 |
根据天气的三种状态 $\{晴，阴，雨\}$，汇总后划分成如下三个子表格，同样根据温度、湿度、风速的属性状态，也可以划分（考虑页面空间不再划分）。
表格1 —— 晴
温度 湿度 风速 活动 炎热 高 弱 取消 炎热 高 强 取消 适中 高 弱 取消 寒冷 正常 弱 进行 适中 正常 强 进行 表格2 —— 阴
温度 湿度 风速 活动 炎热 高 弱 进行 寒冷 正常 强 进行 适中 高 强 进行 炎热 正常 弱 进行 表格3 —— 雨
温度 湿度 风速 活动 适中 高 弱 进行 寒冷 正常 弱 进行 适中 正常 弱 进行 寒冷 正常 强 取消 适中 高 强 取消
步骤一 计算类别信息熵
类别（进行 & 取消）信息熵：表示所有样本中各种类别出现的不确定性之和。
$Info(D) = -(\frac{9}{14}\log_2 \frac{9}{14} + \frac{5}{14}\log_2 \frac{5}{14}) = 0.940$
步骤二 计算每个属性的信息熵
每种属性的信息熵相当于一个条件熵，表示的是在某种属性条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不纯（该属性类别可取值越多）。
$Info(天气) = \frac{5}{14}(-\frac{2}{5}\log_2 \frac{2}{5} - \frac{3}{5}\log_2 \frac{3}{5}) + \frac{4}{14}(-\frac{4}{4}\log_2 \frac{4}{4} - \frac{0}{4}\log_2 \frac{0}{4}) + \frac{5}{14}(-\frac{3}{5}\log_2 \frac{3}{5} - \frac{2}{5}\log_2 \frac{2}{5}) = 0.694$
$Info(温度) = \frac{4}{14}(-\frac{2}{4}\log_2 \frac{2}{4} - \frac{2}{4}\log_2 \frac{2}{4}) + \frac{6}{14}(-\frac{4}{6}\log_2 \frac{4}{6} - \frac{2}{6}\log_2 \frac{2}{6}) + \frac{4}{14}(-\frac{3}{4}\log_2 \frac{3}{4} - \frac{1}{4}\log_2 \frac{1}{4}) = 0.911$
$Info(湿度) = \frac{7}{14}(-\frac{3}{7}\log_2 \frac{3}{7} - \frac{4}{7}\log_2 \frac{4}{7}) + \frac{7}{14}(-\frac{6}{7}\log_2 \frac{6}{7} - \frac{1}{7}\log_2 \frac{1}{7}) = 0.789$
$Info(风速) = \frac{8}{14}(-\frac{6}{8}\log_2 \frac{6}{8} - \frac{2}{8}\log_2 \frac{2}{8}) + \frac{6}{14}(-\frac{3}{6}\log_2 \frac{3}{6} - \frac{3}{6}\log_2 \frac{3}{6}) = 0.892$
步骤三 计算信息增益
信息增益（Infomation Gain）= 信息熵 - 条件熵，表示信息不确定性减少程度，如果一个属性的信息增益越大，那么信息不确定性减少程度就越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性。简单讲，选择该属性可以更快更好的完成目标分类任务。（这一步其实ID3算法的特征选择）
$Gain(天气) = Info(D) - Info(天气) = 0.940 - 0.694 = 0.246$
$Gain(温度) = Info(D) - Info(温度) = 0.940 - 0.911 = 0.029$
$Gain(湿度) = Info(D) - Info(湿度) = 0.940 - 0.789 = 0.151$
$Gain(风速) = Info(D) - Info(风速) = 0.940 - 0.892 = 0.048$
步骤四 计算属性分裂信息度量
用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，这也称为属性的内在信息（Intrinsic information ），而信息增益率（Information Gain Ratio） = 信息增益 / 内在信息。因此，属性的重要性反而随着内在信息量的增大而变得不那么重要。（这一步是C4.5在ID3算法的基础上进行了改造，其实就是信息增益权重熵）
$Intri(天气) = -\frac{5}{14}\log_2 \frac{5}{14} -\frac{5}{14}\log_2 \frac{5}{14} -\frac{4}{14}\log_2 \frac{4}{14} = 1.577$ //天气3种状态取值
$Intri(温度) = -\frac{4}{14}\log_2 \frac{4}{14} -\frac{6}{14}\log_2 \frac{6}{14} -\frac{4}{14}\log_2 \frac{4}{14} = 1.556$ //温度3种状态取值
$Intri(湿度) = -\frac{7}{14}\log_2 \frac{7}{14} -\frac{7}{14}\log_2 \frac{7}{14} = 1.000$ //湿度2种状态取值
$Intri(风速) = -\frac{8}{14}\log_2 \frac{8}{14} -\frac{6}{14}\log_2 \frac{6}{14} = 0.985$ //风速2种状态取值
步骤五 计算信息增益率（Information Gain Ratio， IGR） $IGR = Gain / Intri$
$IGR(天气) = Gain(天气) / Intri(天气) = \frac{0.246}{1.577} = 0.155$
$IGR(温度) = Gain(温度) / Intri(温度) = \frac{0.029}{1.556} = 0.0186$
$IGR(湿度) = Gain(湿度) / Intri(湿度) = \frac{0.151}{1.000} = 0.151$
$IGR(风速) = Gain(风速) / Intri(风速) = \frac{0.048}{0.985} = 0.048$
结论
因为天气的信息增益率最大，因此选天气作为划分属性。划分之后，当 天气 = “阴”，类别标签只有一种情况（最纯），所以把 天气 =“阴” 这一分枝结点定义为叶子结点，继续重复上述1~5步骤，选择不“纯”的结点划分。至此，C4.5算法的计算过程就完成了，一棵树也就构建出来了。
写一下伪代码大致流程while (当前结点可划分)
(1) 计算当前结点的类别信息熵 Info(D) （以类别取值计算）
(2) 计算当前结点的各个属性信息熵 Info(X) （以属性取值下各类别取值计算）
(3) 计算各个属性的信息增益 Gain(X) = Info(D) - Info(X)
(4) 计算各个属性的分类信息度量 Intri(X) （以属性取值计算）
(5) 计算各个属性的信息增益率 IGR(X) = Gain(X) / Intri(X)
end while
设置当前结点为叶子结点
代码实现
【备注】后面抽空补上
优缺点
优点
分类规则易于理解，划分准确度高。
缺点
主要还是在于算法的低效上，因为在构造树时，需要对数据集进行多次顺序遍历和排序；
再比如使用较为复杂的多叉树，并且模型是用较为复杂的熵来度量，这个情形下，是只能处理分类而无法处理回归问题的。对这些问题的处理，就引入了下面要介绍的CART算法，既可以处理分类也可以处理回归。
CART算法
以基尼系数为准则来选择最优划分属性 可用于回归和分类
核心思想
CART（Classification And Regression Tree，CART）是基于假设决策树是二叉树这种情形下的，内部结点特征的取值为 “是” 跟 “否”，左分支取 “是”， 右分支取 “否”。这种决策树等价于递归二分每种特征，它将特征空间划分成 N 份，然后再在这些划分单元上确定预测的概率分布，即在给定的特征条件下计算出条件概率分布。
CART分类树算法使用了基尼系数来代替增益率，而基尼系数则代表了模型的不纯度，基尼系数越大，纯度就越低，特征越不能代表划分标准。这和ID3里的信息增益以及C4.5里的增益率是相反的。
CART算法主要有以下两步
- 1、决策树生成： 基于训练数据集生成决策树，生成的决策树尽可能覆盖各种情形。
- 2、决策树剪枝： 用验证集对已生成的决策树进行剪枝，选择最优子树，而剪枝的标准就是损失函数达到最小。
算法释义
最优特征选择
假设一数据集有 $k$ 个类别，第 $k$ 个类别的概率为 $p_k$ ，那么概率分布的基尼系数为：
$Gini(p) = \sum_{k=1}^{K} p_k(1-p_k) = 1-\sum_{k=1}^{K} p_k ^2$
如果是二分类问题，假设第一个样本的输出概率为 $p$，那么概率分布的基尼系数为：
$Gini(p) = 2p(1-p)$
现在有一样本 $D$，样本数为 $|D|$，假设有 $K$ 个类别，第 $k$ 个类别样本数为 $C_k$，则样本 $D$ 的基尼系数为：
$Gini(D) = 1-\sum_{k=1}^{K} (\frac{|C_k|}{|D|})^2$
对于样本 $D$，根据特征A的某个值a，把样本 $D$ 分成 $D_1$ 和 $D_2$，则在特征A的条件下，样本 $D$ 的基尼系数为：
$Gini(D, A) = \frac{D_1}{D} Gini(D_1) + \frac{D_2}{D} Gini(D_2)$
这里面需要借助matplotlib绘制一下基尼指数、熵之半以及分类误差率之间的关系，见下
import numpy as np |
个人习惯用Anaconda，运行得到如下绘图
可以看到
Gini-Index和半熵的曲线非常接近，在某种程度上可以近似的认为二者相等，仅在45°角附近偏差较大。因此，Gini-Index实际上是可以作为熵模型的一个近似替代
连续特征 vs 离散特征
CART分类树宣发对连续值的处理
处理方法类似于C4.5，都是采用连续特征离散化方式，区别在于前者使用信息增益率划分特征，而后者则是通过基尼系数。
思路： $n$个样本的连续特征$A$有$n$个，由小及大顺序排列 $\{a_1, a_2, … , a_n\}$，则CART取相邻两样本值的平均数作为划分点，一共取 $n$-1 个，其中第 $i$ 个划分点 $T_i$ 表示为： $T_i = \frac{a_i + a_{i+1}}{2}$。分别计算这 $n$-1 个点作为二元分类时的基尼系数。，选择基尼系数最小的点作为该连续特征的二元离散分类点。比如：基尼系数最小的点为 $a_x$，则小于 $a_x$ 的值为类别1，大于 $a_x$ 的值为类别2，这样就做到了连续特征的离散化。
CART分类树宣发对离散值的处理
处理方法是不断遍历二分离散特征。
思路： 如果特征 $L$ 有3个类别 $\{L_1, L_2, L_3\}$，那么在决策树上先建立一个三叉点，接下来考虑把特征 $L$ 分成 $\{L_1\}$ 和 $\{L_2, L_3\}$、$\{L_2\}$ 和 $\{L_1, L_3\}$、$\{L_3\}$ 和 $\{L_1, L_2\}$ 这三种情况，找到基尼系数最小的组合，比如 $\{L_2\}$ 和 $\{L_1, L_3\}$，然后建立二叉树结点，一个结点是 $L_2$ 对应的样本集，另一边是 $\{L_1, L_3\}$ 对应的样本。对于子结点存在多特征未完全划分开，则继续针对 $\{L_1, L_3\}$ 二分，这和ID3、C4.5算法不同，在这两个算法中，子树中的离散特征只会参与一次结点建立。
算法流程
分类树算法（有剪枝）
Input： 训练集 $D$ 基尼系数阈值 $T_g$ 样本个数阈值 $N_s$
Output： CART决策树 $T$
算法从根结点开始，用训练集递归构建二叉决策树
(1) 对于当前结点数据集 $D$，如果样本数小于阈值 $N_s$ 或没有特征时，则返回决策子树，当前结点停止递归
(2) 计算样本集 $D$ 的基尼系数，如果基尼系数小于阈值 $T_g$，则返回决策子树，当前结点停止递归
(3) 计算当前结点拥有的各特征的特征值对数据集 $D$ 的基尼系数，处理缺失值，有关离散、连续值的基尼系数计算 见上面
(4) 计算出各个特征的特征值对于数据集 $D$ 的基尼系数，选择基尼系数最小的 $A$ 和对应的特征值 $a$；再然后根据最优特征和最优特征值，划分数据集 $D_1$ 和 $D_2$，同时构建当前结点的左右子结点，此时左结点的数据集为 $D_1$ ，右结点的数据集为 $D_2$
(5) 对左右子结点递归调用（1）-（4）步，生成CART决策树
【注】测试集预测决策树时，加入测试集中的某样本被划分到了某个叶子结点里，然而此时这个结点里有多个训练集样本，那么对于该样本而言，该样本的类别预测采用这个叶子结点里概率最大的类别
回归树算法
CART回归树同分类树的构建类似，然而不同点在于
>(1) 样本的输出不同（分类树输出的是样本的类别，回归树输出的是一个实数）
(2) 连续值处理方式不同
(3) 决策树构建之后对于预测的方式不同
关于剪枝
CART分类树的剪枝策略在度量损失的时候使用 基尼系数
CART回归树的剪枝策略在度量损失的时候使用 均方差
这里只讲一下剪枝的思路，具体可以自行上网查找资料。
思路：由于决策树很容易overfit，所以需要对CART树进行剪枝，即类似线性回归的正则化。CART所采用的是后剪枝技术，先生成决策树，然后再生成所有可能的剪枝后的CART树，再使用交叉验证检验剪枝的效果，从而选择泛化能力最好的剪枝策略。
算法不足
- 无论是ID3、C4.5、亦或是CART，它们都只是选择一个最优的特征来进行分类决策的，但大多数情况下，分类决策并不是由某个特征来决定，而是一组特征。（这里进一步引出多变量决策树，代表算法比如斜决策树OC1）
- 牵一发而动全身，有时样本数据集的一点点变动，或者某个噪声值影响，都可能导致树结构的剧烈波动。（解决方法：随机森林算法解决）
总结
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类 回归 |
二叉树 | 基尼系数 均方差 |
支持 | 支持 | 支持 |
以下引用sklearn官网关于三种算法的一些总结，想看原文请戳这里
优势
1、生成的决策树简单直观
2、不需要预处理数据，以及归一化、缺失值处理
3、决策树预测算法的复杂度为 $O(\log_2 m)$ ，其中 m 为样本数
4、区别于一些单一的处理算法，决策树算法既可以处理离散值也可以处理连续值
5、可以处理多维度输出的分类问题
6、使用白盒模型，不同于神经网络的黑盒模型，决策树在模型上的解释很符合逻辑思维
7、可以使用统计测试来交叉验证模型，这使得模型的可靠性更高，泛化能力更强
8、对于异常值的容错能力及robust（健壮性）有很好的的表现
不足
1、决策树算法非常容易过拟合，导致泛化能力不强。为了避免这个问题，需要设置叶结点所需的最小样本数或设置树的最大深度。
2、决策树可能不稳定，因为数据集中的微小变化可能导致生成完全不同的树。在集成学习中使用决策树可以缓解这个问题
3、寻找最优决策树是一个NPC问题，一般通过启发式方法，比如贪心算法求得局部最优解，这种算法不能保证返回全局最优的决策树。这可以通过在集成学习器中训练多个树来缓解，当然其中的特征和样本是随机抽样的（也就是我们经常说的随机森林法）。
4、有些概念很难学习，因为决策树不容易表达它们，比如 异或（XOR）、奇偶性或多路复用器等问题
5、如果某些特征的样本比例过大，那么生成的决策树就会比较容易偏向这些特征。一般可以通过调节样本权重来改善
