Decision Trees

决策树的应用场合非常广泛：
- 分类
- 回归
- multioutput tasks

【特点】对数据预处理的要求较低，例如，不需要对特征进行scaling或者centering

结构说明

• 内部节点：每个节点代表一个属性
• 叶节点：每个叶节点代表一个类别
• 分支：每个分支代表一个属性的取值
• sample: 通过该节点的训练样本数量
• value: 通过该节点的 不同类别 的样本数量
• gini: 测量节点的不纯度 (impurity)，pure: gini=0

纯度/不纯度

• Entropy Impurity 熵不纯度
  
  i(N)=−∑jP(wj)log2(wj)$$i(N)=-\sum _{j}P(w_j){\log }_2(w_j)$$
• Gini Impurity Gini不纯度
  
  Gi=∑i≠jP(wi)P(wj)=1−∑jP(wj)2$$G_i=\sum _{i\ne j}P(w_i)P(w_j)=1-\sum _{j}P(w_j{)}^2$$
• Misclassification Impurity 错分不纯度
  
  i(N)=1−maxjP(wj)$$i(N)=1-\underset{j}{max}P(w_j)$$
  
  其中，P(wj)$P(w_j)$: 第 j$j$ 类样本在第 i$i$ 个节点处所占的 比例。
  
• 比较：
  
  • 一般情况下Gini不纯度与Entropy不纯度的区别不太大，而Gini不纯度的计算量较小，因此默认使用Gini不纯度
  • 当Gin不纯度与Entropy不纯度有所区别是，Gini不纯度倾向于将最长出现的类单独划分为树的一枝，而Entropy不纯度则相对来说更加平衡。

剪枝

• 目的：防止过拟合
• 预剪枝
  
  • validation
  • 阈值法
• 后剪枝
  
  • 类别1：把训练数据分成树的生长集和剪枝集
  • 类别2：使用同一数据集进行决策树生长和剪枝
  • CCP (Cost Complexity Pruning)
  • REP (Reduced Error Pruning)
  • PEP (Pessimistic Error Pruning)
  • MEP(Minimum Error Pruning)

缺失属性值的处理（C4.5中应用）

• Q1：在构建决策树时，每一个分裂属性的选取是由训练样本集中所有属性的信息増益率来决定的。而在此阶段，如果训练样本集中有些样本缺少一部分属性，此时该如何计算该属性的信息増益率？
  
  • A1：计算某属性的信息増益率时忽略掉缺失了此属性的样本；或者通过此属性的样本中出现频率最高的属性值，賦值给缺失了此属性的样本。
• Q2：当已经选择某属性作为分裂属性时，样本集应该根据该属性的值来进行分支，但对于那些该属性的值为未知的样本，应该将它分支到哪一棵子树上？
  
  • A2：不处理那些属性Ａ未知的样本，即简单的忽略它们；或者根据属性Ａ的其他样本的取值，来对未知样本进行赋值；或者为缺失属性Ａ的样本单独创建一个分支，不过这种方式得到的决策树模型结点数显然要増加，使模型更加复杂了。
• Q3：在决策树已经构建完成后，如果待分类样本中有些属性值缺失，则该样本的分类过程如何进行？
  
  • A3：待分类样本在到达属性Ａ的分支结点时即可结束分类过程，此样本所属类别为属性Ａ的子树中概率最大的类别；或者把待分类样本的属性Ａ赋予一个最常见的值，然后继续分类过程。

连续型属性的离散化处理（C4.5中应用）

• 将连续属性A的N个属性值按照升序排列（当前节点有N个样本）；
• 通过二分法将属性A的所有属性值分成两部分（共N-1种划分方法，二分阈值为中间值）
• 计算每种划分方法对应的信息增益率
• 选取信息增益率最大的划分方法的阈值作为属性A的二分阈值

Q & A

• binary value V.S. multi-value？
  
  • 与属性的性质有关，所有属性均可以用 二叉树 的形式来分类
• 某个节点处应该以哪个attri.为准则进行分类？
  
  • 简单性原则(simplicity)：以得到一个简单的&紧凑的&节点数少的树为目标
    
    • 得到的后继节点越 纯 越好
      
      maxΔi(N)Δi(N)=i(N)−PLi(NL)−PRi(NR)$$\begin{gathered} max\mathrm{\Delta }i(N) \\ \mathrm{\Delta }i(N)=i(N)-P_{L}i(N_L)-P_{R}i(N_R) \end{gathered}$$
  • 如果每个节点处只选择一个attri.为分类准则
    
    • 得到的决策树与特征坐标轴平行
    • 不稳定：different tree because of only one point
  • Multivariate decision tree: 每个节点处以一个线性分类器作为分类准则
• 如何确定取值连续的atrri的划分节点？
  
  • 例如
    
    xx=(1−P)xlower+Pxupper$$x_x=(1-P)x_{lower}+P{x}_{upper}$$
• 何时可以确定一个节点为叶节点？（stop splitting，预剪枝）
  
  • traditional method: validation
    
    • e.g. 90% 训练集，10%验证集
    • 选择验证错误率最低时对应的停止划分策略
    • 问题：对数据的利用不够
  • 阈值法
    
    • 当 Δi(N)≤β$\mathrm{\Delta }i(N)\le \beta$ 时停止
    • 问题：β$\beta$ 的取值难以确定
    • 优点：1) 各个分支的深度可以不同 2) 充分利用了训练集
• 如何确定 后剪枝 规则？
  
  • 当剪枝后不纯度的上升不显著时则剪枝
  • 与 stop splitting 相比
    
    • 优势：应用了训练集的所有信息
    • 缺陷：计算复杂度更高
• 叶节点如果是 不纯 的，如何确定类别？
  
  • 选择数量多的那一类为当前新叶节点类别

ID3 算法 (Interactive Dichotomizer-3, 交互式二分法)

• 算法步骤：
  
  • 计算当前节点包含的所有样本的不纯度，比较采用不同特征进行分支将会得到的信息增益（即不纯度减小量）ΔI(N)$\mathrm{\Delta }I(N)$
  • 选取具有最大信息增益的特征赋予当前节点。该节点的取值个数决定了该节点下的分支数目
  • 如果后继节点只包含一类样本，则停止该枝的生长，该节点成为叶节点
  • 如果后继节点仍包含不同类样本，则再次进行以上步骤，直至每一枝都到达叶节点位置
• 特点：
  
  • 对于连续的real-valued变量，首先应被切分为不同的intervals
  • 树的深度与输入变量的维度相等
  • no pruning

C4.5 算法

• 改进了ID3
  
  • 用 信息增益率 代替ID3中的 信息增益，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足
  • 能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理
  • 构造决策树之后进行剪枝操作
  • 能够处理具有缺失属性值的训练数据
• 连续型属性的离散化处理：见上文
• 剪枝：PEP(Pessimistic Error Pruning)剪枝法
  
  • 自上而下：根据剪枝前后的错误率来判断是否进行修剪（不需要剪枝集）
• 缺失属性值：见上文
• 缺点：
  
  • 算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
  • 算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。

CART (classification and regression trees)

• 特点：
  
  • 二叉树，既可以用于分类，也可以用于回归。
  • 是贪心算法：每一步都要找到最优的分割，但不保证几步之后的最优性，因此找到的分割不是最优的。
• 算法组成
  
  • 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大
  • 决策树剪枝：用验证数据集对已生成的树尽心剪枝并选择最优子树，剪枝标准为 损失函数最小。
• 算法：根据训练集，从根节点开始，递归地对每个节点进行以下操作，构建二叉决策树
  
  • 计算当前节点现有特征对该数据集的Gini系数。
  • 在所有可能的特征及其所有可能的切分点中，选择Gini系数最小的特征及其对应的且分点，并由此分配训练集数据至两个子节点。
  • 对子节点递归调用以上步骤，直至满足停止条件。
• 停止条件
  
  • 节点中的样本个数小于预定阈值
  • 样本集的GIni系数小于预定阈值
  • 没有更多特征
• 生成最优树的复杂度-NP Complete：O(exp(m))$O(\exp (m))$，
  
  • P: 可以在多项式时间内解决的问题集合
  • NP: 非确定性多项式（non-deterministic polynomial，NP）可以在多项式时间内验证solution的问题集合），NP问题通俗来说是其解的正确性能够被“很容易检查”的问题。
  • NP-hard problem: 所有 NP 问题都可以归约到这种问题，我们称之为 NP-hard 问题。
  • NP-Complete problem 既是 NP 的，又是 NP-Complete的。
• 生成CART树的复杂度：O(n×mlog(m))$O(n\times m\log (m))$
• 预测复杂度：O(log2(m))$O({\log }_2(m))$
  
  • 一般情况下近似平衡，m$m$为样本数
  • 与特征数量独立

Regularization

• reduce: max depth of the tree
• increase: the minimum number of samples a node must have before it can be split
• increase: the minimum number of samples a leaf node must have
• reduce: maximum number of leaf nodes
• reduce: maximum number of features that are evaluated for splitting at each node
• 剪枝：
  
  • wheather the improvement is statistically significant: statistical test: 2${\mathcal{X}}^2$ test
    
    • estimate the probability that the improvement is purely the result of chance (null hypothesis)
    • If this probability, called the p−value$p-value$, is higher than a given threshold (tipically 5%), then do pruning.

缺陷 & 敏感因子

• 对训练数据的微小变化非常敏感
• 分类面倾向于坐标轴平行 => 对数据集的旋转角度非常敏感
  
  • 改善方法：主成分分析 PCA