以下博客是我在学习过程中发现的比较好的博客，可以参考：机器学习算法实践-决策树(Decision Tree)、July_sun的博客、HerosOfEarth的博客、天泽28的专栏

decision tree 基本结构

借用西瓜书中西瓜问题的一棵决策树，观察可知，决策树主要由若干节点（包括根节点、叶节点、内部节点等）组成。每个内部节点都表示某个属性，叶子节点表示判别结果。

决策树的构建

节点划分

一棵决策树包含许多节点，可以通过递归方式产生新节点。递归终止条件为：

当前节点包含样本全部为同一类别，无需划分新节点
当前属性集为空或所有样本在所有属性上取值相同，无法划分
当前节点包含样本集为空。

节点划分伪代码棵表示为：

Generate_decision_tree(samples, attribute_list){
创建结点 N；
if samples 都在同一个类C then   //类标号属性的值均为C，其候选属性值不考虑
    return N 作为叶结点，以类C 标记；
if attribut_list 为空 then      
    return N 作为叶结点，标记为 samples 中最普通的类； //类标号属性值数量最大的那个
选择attribute_list 中具有最高信息增益的属性best_attribute；//找出最好的划分属性
标记结点 N 为best_attribute；
for each best_attribute 中的未知值a i //将样本samples按照best_attribute进行划分
    由结点 N 长出一个条件为 best_attribute = a i 的分枝；
    设si 是samples 中best_attribute = a i 的样本的集合；//a partition
    if si 为空 then
        加上一个树叶，标记为 samples 中最普通的类；//从样本中找出类标号数量最多的，作为此节点的标记
    else 
        加上一个由 Generate_decision_tree(si,attribute_list–best_attribute)返回的结点；//对数据子集si,递归调用，此时候选属性已删除best_attribute
}

ID	色泽	根蒂	敲声	target
01	青绿	蜷缩	浑浊	好瓜
…	…	…	…	…	…

随着划分过程的进行，我们希望决策树的分支节点包含的纯度越高（即属于同一类别），下面将简单介绍如何构建决策树（以上表为例）：

分别计算每个特征的分支纯度（不同决策树有不同评价指标），选取最佳的分支节点此处选择色泽。
按照色泽将数据集划分为青绿-乌黑-浅白的几个子集（对应3个子节点），重复1步骤不断计算并选择最佳划分节点，直到无法划分为止。

常见决策树模型的节点划分方式

ID3：信息增益

信息熵是度量样本集合纯度最常用的一种指标
$$entropy(D) = -\sum\limits_{i=1}^n P_ilog_2 P_i$$
其中D为数据集，$i$为数据集$D$的可能分类标签,$P_i$为该标签的概率。信息熵就是平均而言一个事件发生得到的信息量大小，也就是信息量的期望值。(明天会下雨的信息熵远大于明天太阳会升起（后面那是废话吧）)

条件熵：
$$entropy(D,A) = \sum_{i=1}^k \frac {D_{A_i}}{D} log_2D_{A_i}$$
其中A表示约束特征，k表示A特征的种类。条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。

信息增益:
$$gain(D,A) = entropy(D) - entropy(D,A)$$

ID3：信息增益的缺点

信息增益准则对可取值数目较多的属性有所偏好，比如将样本编号作为特征，则该特征的信息增益远大于其他特征。为此提出了改进的c4.5模型。

ID3的主要缺点：

用信息增益选择属性时偏向选择取值多的属性
输入变量必须是分类变量（连续变量必须离散化）
无法处理空值

c4.5：信息增益率

c4.5以信息增益率为节点划分指标：
$$gainrate(D,A) = \frac{gain(D,A)}{entropy(D,A)}$$

c4.5对ID3主要改进在于：

克服了用信息增益选择属性时偏向选择取值多的属性的不足；
在树构造过程中进行剪枝；
能够完成对连续属性的离散化处理；
能够对不完整数据进行处理。
c4.5：信息增益率的缺点
信息增益率对数目较少的属性有偏好。

CART：基尼指数或

对于分类树的损失函数为基尼指数:
$$gini(D) = \sum_{i=1}^n p_k (1-p_k)$$

$gini(D)$反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，$gini(D)$越小，则数据集$D$的纯度越高。

对于回归树的损失函数为平方差损失:
$$\sum_{x_i \in R_m}(y_i-f(x_i))^2$$

对于一个数据集我们可以将其分为m个子区间$(R_1,R_2……R_m)$对于每一区间我们可以产生一个对应的输出cm.我们的最终输出$f(x)=\sum_{i=1}^mc_mI(x \in R_m)$。每个单元的最优输出就是使该单元的损失函数最小。每个单元的最终输出可以表示为$C = avg(y_i|x_i)(x_i \in R_m)$(区间$R_m$ 上所有$x_i$ 的输出$y_i$的均值)

有关回归树的更多介绍可参考：没有名字、HerosOfEarth的博客、fionacai

决策树对连续值的处理

以上分析中，只有离散的属性值，如果加入西瓜重量这一离散的属性值，该如何处理呢？特征变为下表：

ID	色泽	根蒂	敲声	质量	target
01	青绿	蜷缩	浑浊	1.0	好瓜
02	乌黑	硬挺	清晰	1.4	坏瓜
03	浅白	蜷缩	清晰	1.7	好瓜
04	青绿	硬挺	浑浊	0.8	好瓜
…	…	…	…	…	…

c4.5对ID3d额改进之一便是加入离散特征的处理方式（二分法），主要步骤为：

对连续特征进行排序$[A_1,A_2,…,A_n]$
依次选取2个质量值$A_i,A_{i-1}$取中间的一个点$a(A_{i}<a<A_{i-1})$，则数据集可以分为小于$a$与大于$a$两个部分（即将连续的特征离散化，可以理解为将质量特征转化为大小特征，只有大西瓜与小西瓜2中状态），计算$a$的信息增益率。
不断循环执行(2)步骤，计算得到的最大信息增益率作为该特征的信息增益率，最大的信息增益率对应的a即为该节点分裂依据。

决策树对缺失值的处理

以c4.5为例，决策树对缺失值的处理分为2个方面：

有缺失值的情况下如何计算信息增益率？（即如何选择分裂属性）
分裂完成后，含缺失值样本f分类（进入子节点）？

下面将依次进行解答：

有缺失值的情况下如何计算信息增益率？（即如何选择分裂属性）：计算无缺失值样本集的信息增益率，然后根据样本无缺失比重（感觉很别扭啊）进行折减，$gainrate(D,A) = gainrate(\hat{D},A)\times \rho$，其中$\rho$为非缺失比重。
分裂完成后，含缺失值样本分类（进入子节点）？：缺失值样本将会同时进入所有子节点，但缺失值样本所占比重将根据子节点样本权重来下调。

剪枝(pruning)方式解决过拟合

如果任由决策树野蛮生长，不停迭代，最后得到的肯定不是一棵健康的、优美的树（树枝杂乱无章，相互争夺阳光、空间等，打住，这不是园艺233），防止过拟合的基本策略是预剪枝(prepruning)与后剪枝(postpruning)。

预剪枝 prepruning

预剪枝即提前终止树的生长。预剪枝方式为：

指定结点所包含的最小样本数目，当该结点总样本数小于此数目时，则不再分；
指定树的高度或者深度；
当划分节点不能带来泛化能力提升，则停止划分。如何判断泛化能力提升提升与否？可以将一部分数据当作测试集。

预剪枝特点

预剪枝使得决策树的很多分支都没有展开,这不仅降低了过拟合风险，还显著减少时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险。

后剪枝

后剪枝将在决策树构造完成后进行剪枝。剪枝的过程将依次对内部节点进行检查，判断如果将该节点下子树删除，验证集精度是否会提高。如果验证集精度提高，则进行剪枝策略。否则不变。

后剪枝特点

后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

后剪枝算法

可参考决策树的剪枝问题