Decision Tree

决策树概述

结构

  • 决策树分析结论、展示方式类似一棵倒置的树
  • 决策树由 nodedirected edge 组成

    • internal node:内部节点,表示特征、属性
    • leaf node:叶子节点,表示一个类
  • 对训练数据进行分类

    • 从根节点开始,对实例某特征进行测试,根据测试结果将实例分配到其子节点,对应该特征一个取值
    • 递归地对实例进行分配,直至到达叶子节点,将实例分到叶节点地类中
  • 对新数据的预测

    • 从决策树的树根到树叶搜索,确定数所的叶子节点
    • 利用叶子节点中训练数据集预测
      • 分类型:众数
      • 数值型:均值

本质

决策树:本质上是从训练数据中归纳出一组分类规则

  • 与训练数据不矛盾的分类规则(即能对训练数据正确分类)可能有多个、没有,需要找到矛盾较小、泛化能力较好的
  • 决策树学习也是由训练数据集估计条件概率模型,需要寻找对训练数据有很好拟合、对未知数据有很好预测的模型

分类规则集合

  • 决策树可以看作是 if-then 规则的集合:体现输入、输出变量逻辑关系
  • 决策树根节点到叶节点每条路径构成一条规则
  • 路径上内部节点的特征对应规则的条件,叶节点对应规则结论
  • 决策树的路径或其对应的 if-then 规则集合 互斥且完备,即每个实例有且仅有一条路径覆盖

条件概率分布

  • 决策树可以表示定义在特征空间、类空间上的条件概率分布
  • 此条件概率分布定义在特征空间的一个划分(有限)上

    • 决策树中一条路径(叶节点)对应划分中一个单元
    • 每个单元定义的概率分布就构成一个条件概率分布
  • 条件概率分布由 各单元的给定条件下,各类的条件概率分布组成

    • $P(Y|X)$:$X$ 为表示特征的随机变量(取值各个单元),$Y$ 表示类的随机变量
    • 各叶节点上的条件概率往往偏向于某类,决策树分类时将属于该节点实例分为该类

特点

  • 优势

    • 能有效处理分类型输入变量
    • 能够实现非线性分割
    • 模型具有可读性,分类速度块
  • 问题

    • 充分生长的决策有高方差,预测不稳定
    • 剪枝可以提高预测稳健性,但是预测精度可能会下降

决策树构建

  • 从所有可能决策树中选取最优决策树是NP完全问题

    • 所以实际决策树算法通常采用 启发式 算法、贪心算法,近似求解最优化问题,得到 sub-optimal 决策树
    • 从包含所有数据的根节点开始,递归的选择 当前 最优特征、分割点对训练数据进行分割,使得各子数据集有当前最好分类
    • 此样本不断分组过程对应特征空间的划分、决策树的构建
  • 原则:使节点/组内观测取值异质性下降最大,从而确定

    • 最佳划分特征
    • 特征的最佳分割点
算法 ID3 C4.5 CART CHAID
特征 分类 分类、连续 同左 同左
输出 分类 分类 分类、回归 分类
连续值处理 - 二分法 同左 等距分组
分叉 多叉 多叉 二叉 多叉
分裂指标 信息增益 信息增益比 GINI 不纯度 相关性
前剪枝 - 叶节点数量 树深度、节点样本数量 -
后剪枝 - 置信度、减少-误差法 MCCP -

异质性衡量:划分准则

  • 信息增益
  • 信息增益比:避免信息增益倾向于取值较多特征
    • 若样本类别严格服从分布,则信息增益和信息增益比选择应完全相同
    • 但由于偶然性、样本数量等原因,各特征取值的样本数量往往不完全符合分布
    • 由信息增益定义可看出,各特征取值样本数量较小时,数量变动影响更大,而特征取值较多更可能出现各取值对应样本数量较小
  • GINI 指数
  • 研究表明,不同决策树的划分准则对泛化性能影响有限,信息增益和 GINI 指数理念分析表明,其仅在 2% 情况下有所不同

特征变量处理

  • 离散值处理

    • 全分类:各类别分别独立作为分支,构建节点
    • 切分二分:将类别分为的两组
    • 是否二分:某取值作为一个分支,其余作为另一分支
  • 连续值处理

    • 二分法:选择阈值,按照阈值将连续值分为两部分
      • 精确阈值选取:检查所有可能阈值点,即所有不同取值点的中间点
      • 近似阈值选取
    • 近似分裂算法:选取一组阈值,将特征划分至不同桶内,类似分类值处理
      • 等频阈值:分位数
      • 等距阈值:linespace

缺失值处理

  • 缺失值处理需要解决:异质性衡量指标计算、特征缺失样本划分问题
  • 异质性衡量指标计算:使用特征未缺失样本权重对指标加权(以信息增益为例)

    • $Y, X, w_x$:样本类别,特征,样本权重
    • $D, \tilde D, \tilde {D_k}, \tilde {D^v}$:样本全集,在特征 $X$ 上无缺失样本子集,属于 $k$ 类样本子集,在特征 $X$ 上取 $v$ 样本子集
  • 特征缺失样本划分

    • 划分至所有节点,其权重设置为 $\tilde {r_v} * w_x$
      • $\tilde {r_v}$ 为节点 $v$ 的权重
      • 即将特征缺失样本节点权重比例划分至各节点

剪枝

树剪枝:在决策树的学习过程中,将已生成的树进行简化的过程

  • 最小化 RSS、最大化置信目标下,会导致庞大的树

    • 对训练数据拟合好
    • 模型复杂度越高
    • 推广能力差
    • 比较难理解、解释
  • 通过剪枝得到恰当的树,具备一定的预测精度、复杂程度恰当,代价(误差)和复杂度之间的权衡是必要的

  • Pre-pruning 预剪枝:在决策树分裂过程中,不分裂不满足分裂条件的节点,限制决策树充分生长

    • 分裂条件
      • 最大深度
      • 叶节点数量
      • 样本量最小值
      • 异质性下降阈值
    • 预剪枝基于“贪心”的禁止划分,可能降低过拟合、减少时间开销,但也可能导致欠拟合
  • Post-pruning 后剪枝:决策分裂完成后,根据一定规则剪去不具备普遍性的子树

    • 比预剪枝决策保留更多分支,欠拟合风险小、泛化性能好
    • 决策树生成局部模型,决策树剪枝学习整体模型
  • 剪枝方法、程度对泛化性能影响显著,尤其是数据带有噪声

自底向上剪枝

  • 自底向上剪去所有无法改善评价准则的非叶节点分支(转为叶节点)

    • 最简单后剪枝策略
    • 若已使用一定预剪策略,则该策略价值不大
  • 特点

    • 须在生成完全决策树之后自底向上逐个考察非叶节点,时间开销大

Minimal Cost Complexity Pruning

  • $N_t$:树 $T$ 的第 $t$ 个叶子节点中样本点数量
  • $N_{t,k}$:树 $T$ 的第 $t$ 个叶子节点第 $k$ 类样本点数量
  • $H_t(T)$:树 $T$ 的第 $t$ 个叶子节点熵
  • $C(T)$:模型对训练数据的预测误差
  • $|T|$:用叶节点数量衡量的模型复杂度
  • $\alpha \geq 0$:控制模型复杂度对模型总损失影响,每个叶节点带来的复杂度
  • 极小化损失复杂度剪枝
    • 损失函数:正则化的极大似然函数
    • 此策略即在给定 $\alpha$ 的情况下,选择损失函数最小树

剪枝步骤

  • 输入:生成算法产生的整个树 $T$,参数 $\alpha$
  • 输出:修剪后的子数 $T_\alpha$
  • 计算每个节点的经验熵
  • 递归的从树的叶节点向上回缩
    • 若 $C\alpha(T{before}) \geq C\alpha(T{after})$,则剪枝
    • 不断回缩直到根节点,选取损失函数最小的子树 $T_\alpha$
  • 算法只需要比较节点、节点子树之间损失函数之差即可,计算可以在局部进行
  • 算法可以由动态规划算法实现

超参选择

  • 对给定超参 $\alpha$,存在使损失函数 $C\alpha(T)$ 最小子树 $T\alpha$,且此最优子树唯一

    • $\alpha$ 偏大时,最优子树 $T_\alpha$ 偏小
    • $\alpha=0$ 时完整树最优,$\alpha \rightarrow \infty$ 时单节点树最优
  • 对决策树种每个节点 $t$,通过以下策略生成 $g(t)$

    • $C_{\alpha}(T^t) = C(T^t) + \alpha|T^t|$:以 $t$ 为根节点的子树 $T^t$ 损失
    • $C_{\alpha}(t) = C(t) + \alpha$:对 $t$ 剪枝之后,仅包含单个节点 $t$ 的正则损失
    • 则 $\alpha=g(t) = \frac {C(t)-C(T^t)} {|T^t|-1}$ 时,单节点 $t$ 和子树 $T^t$ 损失相同
  • 考虑以上 $g(t)$ 序列

    • $\alpha^t=g(t)$ 表示对 $T^{(0)}$ 中每个内部节点 $t$ 剪枝后,整体损失函数值减少程度
    • 可以证明,对以上 $\alpha > 0$ 序列排序,按 $0, \alpha^{(1)}, \cdots, \alpha^{(N)}$ 依次进行剪枝,对应最优子树序列 $T^{(0)}, T^{(1)},\cdots, T^{(N)}$ 嵌套
    • 通过交叉验证法在独立的验证数据集上对子树进行测试,选择最优决策树

完整剪枝+超参选择

  • 输入:CART 算法生成决策树 $T^{(0)}$
  • 输出:最优决策树 $T_\alpha$
  • 自下而上地计算各内部节点 $t$ 对应 $C(T^t), |T^t|, g(t)$,对 $g(t)$ 升序排列得到 $\alpha^{(1)},\cdots,\alpha^{(N)}$

  • 置:$k=1, \alpha=\alpha^{(k)}, T=T^{(0)}$

  • 自上而下访问内部节点,若有 $g(t)=\alpha$,剪枝并计算新叶节点 $t$ 取值,得到对应最优树 $T^{(k)}$

    • 对于节点 $t$,其子树 $T^t$ 最大有效 $\alpha$ 也只是根节点对应 $g(t)$,更大没有价值
    • 自上而下剪枝避免无效剪枝
  • 置:$k+=1, \alpha=\alpha^{(k)}, T=T^{(k)}$

  • 若 $T$ 不是单节点树,则重复以上

  • 采用交叉验证法在子树序列中选取最优子树 $T_\alpha$

  • 也可从 $\alpha \leftarrow \infty$ 开始,逐渐减少,添枝 得到子树序列

决策树构建算法

  • 以下是一些经典的决策树(算法),但实际实现中往往不会严格按其构建决策树

  • 决策树算法常用递归描述、构建,完全决策树中止条件如下 (往往不会应用,而是以预剪枝条件作为中止条件)

    • 节点中样本属于同一类
    • 所有特征利用完毕
    • 无法找到满足划分阈值的特征、划分点

Iterative Dichotomiser 3

步骤

  • 输入:训练数据集 $D$,特征集 $A$,阈值 $\epsilon$
  • 输出:决策树 $T$
  • 以下情况下 $T$ 为单节点树,以 $D$ 中实例数最大的类(众数) $C_k$ 作为该节点的类标记,返回 $T$

    • $D$ 中所有实例属于同一类 $C_k$
    • $A = \varnothing$
  • 计算 $A$ 中各特征对 $D$ 的信息增益,选择信息增益最大的特征 $A_g$

    • 若 $A_g$ 的信息增益小于阈值 $\epsilon$,则置 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为节点类标记,返回 $T$
    • 否则,对 $A_g$ 每个可能值 $a_m$,将 $D$ 分割为若干非空子集 $D_i$
      • 将 $D_i$ 中实例数最多的类作为标记,构建子节点
      • 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-{A_g}$ 为特征集,递归的构造子树 $T_i$ 并返回

特点

  • 只允许分类型特征,且每个特征只会被用于划分一次

    • 每次所有取值都会被用于建立子节点
    • ID3 树是多叉树,各个节点的分叉个数取决于使用特征
  • 只有树的生成,容易产生过拟合

  • 以信息增益作为划分训练数据集的特征,倾向于选择取值较多的特征进行划分

    • 理论上若特征取值严格符合分布,取值数量多寡,对信息增益没有影响
    • 由于各种误差的存在,样本不可能严格符合总体分布,取值数量较多特征,各取值对应样本数量较少,误差会使得条件经验熵倾向于偏小 (假设误差随机,可以大概证明)
  • 相当于用 极大似然法 进行概率模型的选择

C4.5

C4.5算法:ID3 算法继承者

  • ID3 差别

    • 用信息增益比代替信息增益用于选择特征,并且也被用于 前剪枝
      • 修正 ID3 倾向于使用取值较多的特征值分裂结点
    • 兼容数值型特征,使用二分法处理
  • C4.5 算法还包含 C4.5RulesC4.5 决策树转化为符号规则 - 各分支被重写为规则,并进行前件合并、删减

    • 最终规则集泛化性能可能优于原决策树

Classification and Regression Tree

CART 树:可用于分类和回归的二叉树

  • 特点

    • 二叉树
    • 可以用于分类、回归
      • 分类:众数代表节点,GINI 指数选择特征
      • 回归:均值代表节点,MSE 选择特征
    • 能较好的处理缺失值
  • CART 回归:平方误差最小化准则

    • $R_m$:空间划分出的第 $m$ 单元
    • $\hat c_m=avg(y_i|x_i \in R_m)$:第 $m$ 个单元上所有实例输出变量均值,此时平方误差最小
  • CART 分类:最小化基尼指数准则

    • $D_1 = {(x,y) \in D, X = a}$
    • $D_2 = D - D_1$
    • CART 树是二叉树,对分类变量只选择是否

CART回归步骤

  • 输入:训练数据集 $D$
  • 输出:回归树 $f(x)$
  • 选择最优切变量 $j$、切分点 $s$,即求解

    • $R_1(j,s) = {x|x^{(j)} \leq s}$
    • $R_2(j,s) = {x|x^{(j)} \geq s}$
    • $c_m = avg(y_i|x_i \in R_m)$:使得区域 $R_m$ 中平方误差最小,即其中样本点 $y_i$ 均值
    • 这里通过 遍历 得到
  • 对两个子区域 $R_1(j,s), R_2(j,s)$ 继续重复以上步骤,直至满足停止条件

  • 将输入空间划分为 $M$ 个区域 $R_1, R_2, \cdots, R_M$,生成决策 树

CART 分类步骤

  • 输入:训练数据集 $D$,停止计算条件
  • 输出:CART 决策树
  • 选择最优切变量 $j$、切分点 $s$

    • 对每个特征 $X$,对其所有取值 $a$ 计算条件基尼指数
    • 选择条件基尼指数最小的特征、对应的切分点,将训练数据依特征分配到两个子结点中
  • 对生成两个子节点递归分裂,直至满足停止条件

  • 生成 CART 决策树

Chi-squared Automatic Interaction Detector

CHAID 卡方自动交叉检验法:类似 ID3 算法,但利用卡方统计确定特征变量

特点

  • 通过卡方统计量选择最显著特征变量作为划分特征

    • 分类目标变量:列联分析,卡方检验
    • 数值目标变量:回归分析,F检验
  • 特征预处理

    • 分类型特征变量:根据卡方统计量显著性、组数量等考虑拆分、合并分组
    • 数值型特征变量:均分分组
  • 是从相关性显著角度确定特征变量

    • 对决策树分支优化明显
    • 可用特征变量与目标相关性显著显著性作为停止分裂的标准

QUEST

Quick Unbiased Efficient Statical Tree:类似 CHAID 算法,但对选择特征、划分点依据不同,仅能处理分类目标变量

特点

  • 类似 CHAID,选择最显著(p 值)的特征变量作为划分特征

    • 分类特征变量:连列分析,卡方检验
    • 数值特征变量:方差分析,F检验
  • 划分点选择

    • 分类特征变量:映射为 one-hot 向量后,用判别分析求解划分向量,再映射回划分取值
  • 目标变量多分类

    • 为每个类别计算特征均值,使用均值聚类将其简化为二分类
    • 只需要为节点内样本的、用待划分特征计算均值
  • 运行速度快于 CART

Author

UBeaRLy

Posted on

2019-07-13

Updated on

2021-07-16

Licensed under

Comments