AmosTian

0%

5. 决策树

发表于 更新于 分类于 >
本文字数 2k字 | 阅读时长 ≈ 2 分钟

决策树算法采用树形结构，使用层层推理来实现最终的分类

[TOC]

决策树是包含根结点，内部结点和叶结点的树结构，通过判定不同属性的特征来解决分类问题

决策树的学习过程包括特征选择，决策树生成，决策树剪枝三个步骤

特征选择的指标包括信息增益，信息增益比和基尼系数

决策树的剪枝策略包括预剪枝和后剪枝

与贝叶斯分类器相比，决策树的优势在于构造过程无需使用任何先验条件，适用于探索式的知识发现

决策树结构

  • 根结点：包含样本全集
  • 内部结点：对应特征属性测试，存储通过特征属性筛选后的样本子集
  • 叶结点：代表决策结果

从根结点到叶结点的每条路径都对应着一个从数据到决策的判定流程：从根结点开始，测试待分类样本的特征属性，并按照其值选择输出的内部节点。当选择过程持续到到达某个叶结点时，就将该叶结点存放的类别作为决策结果

决策树学习的本质是：从训练数据集中归纳出一组用于分类的 $如果…那么…$ 的规则

决策树学习过程

  1. 特征选择
  2. 决策树生成
  3. 决策树剪枝

特征选择

特征选择决定了使用哪些特征来划分特征空间

特征选择的目标：筛选出于分类结果相关性较高（分类能力较强）的特征。理想的特征选择是在每次划分之后，分支节点所包含的样本尽量属于同一个类别

信息增益

信息增益 ：在已知特征后对数据分类不确定性的减少程度。

特征的信息增益越大，得到的分类结果不确定性结果越低，即特征具有更强的分类能力

根据信息增益选择特征：自顶向下进行划分，在每次划分时计算每个特征的信息增益，并选取最大值的过程

eg：

在银行发放贷款时，根据申请人的特征就决定是否发放。训练数据中，每个样本包含年龄、是否有工作、是否有房产、信贷情况等特征

一种极端情况，是否有房产的属性取值与是否同意贷款的分类结果完全吻合

  • 有房——同意贷款
  • 无房——不同意贷款

这种情况下，是否有房 这个特征就具有最大的信息增益，完全消除了分类结果的不确定性

另一种极端情况，申请人的年龄和是否同意贷款的分类结果可能完全无关，即在训练数据中，青年/中年/老年各个年龄段内，同意贷款/不同意贷款的样本数目大致相等，即分类结果在年龄这个特征上是随机分布的。

这种特征的信息增益很小，不具备分类能力

ID3算法

决策树的生成利用信息增益准则选择特征

算法过程

  1. 从根节点出发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，并根据该特征的不同取值建立内部节点；
  2. 对每个内部节点都递归调用以上算法，生成新的子节点，直到信息增益都很小或没有特征可选择为止

分析

ID3算法使用的是信息增益的绝对值，而信息增益的计算方式

  • $Y$ ：p种分类结果
  • $X$ ：特征 $X$ 有 $m$ 种取值

决定了当属性的取值数目较多时，其信息增益的绝对值将大于取值数目较少的属性。导致决策树在初始阶段就进行过于精细的划分，导致其泛化能力受到影响

C4.5算法

信息增益比 ：使用按属性取值计算出的信息熵归一化后的信息增益

算法过程

找出信息增益高于平均水平的特征，再从中选择增益率最高的作为节点特征

  • 保证了对多值属性和少值属性一视同仁

在决策树生成上，C4.5和ID3算法类似

信息增益作为特征选择指标分析

二者都是基于信息论中的熵模型的指标实现特征选择，涉及大量对数运算

基尼系数

CART算法全称 Classfication and Regression Tree，既可用于分类也可以用于回归。使用基尼系数代替了熵模型

假设数据在特征 $X_t$ 上有 $K$ 个类别，第 $k$ 个类别的概率为 $p_k$ ，则基尼系数为 $1-\sum_\limits{i=0}^Kp_k^2$ 。

  • 基尼系数在与熵模型高度近似的前提下，避免了对数运算，使CART算法有较高的执行效率

为了进一步简化分类模型，CART树每次只对某个特征的值进行二分类，最终生成的是二叉树模型

在计算基尼系数时，需要对每个特征找到使基尼系数最小的最优切分点

在树生成时，根据最优特征和最优切分点生成两个子节点，将训练数据集按照特征分配到子节点中

eg：

在某个特征 $A$ 上有 $A_1,A_2,A_3$ 中类别，CART分类树在进行二分类时，会考虑 $\{A_1\}/\{A_2,A_3\}、\{A_2\}/\{A_1,A_3\}、\{A_3\}/\{A_1,A_2\}$ ，并从中找到基尼系数最小的组合

  • $\max\{1-[p_1^2+(p_2+p_3)^2],1-[p_2^2+(p_1+p_3)^2],1-[p_3^2+(p_1+p_2)^2]\} $

过拟合问题——剪枝

决策树剪枝通过主动去掉分支以降低过拟合的风险，提升模型的泛化性能

策略

  • 定义决策树整体的损失函数，并使之极小化$\iff$ 使用正则化的最大似然估计进行模型选择
  • 在训练数据集中取出一部分用于模型验证，根据验证集的分类精度变化决定是否进行剪枝

预剪枝

在决策树的生成过程中，在划分前就对每个节点进行估计，如果当前节点的划分不能带来泛化能力提升，就直接将当前结点标记为叶结点

好处：

禁止欠佳结点的展开，在降低过拟合风险的同时显著减少了决策树的时间开销

缺点

误伤：某些分支虽然当前看看起来没用，在其基础上的后序划分却可能使泛化能力显著提升，带来欠拟合的风险

后剪枝

先从训练集中生成完整的决策树，计算其在验证集上的分类精度，再在完整的决策树的基础上剪枝，通过比较剪枝前后的分类精度决定分支是否保留

好处

欠拟合风险小

缺点

需要逐一考察所有内部节点，通常训练开销比较大

多变量决策树

特征选择只依据一个最优特征进行分类决策。在实际问题中，分类结果通常受到多个因素影响，因而需要依赖多个特征进行分类决策

从特征空间上看

  • 单变量决策树的分类边界是与坐标轴平行的分段
  • 多变量决策树的分类边界是斜线式的
-------------本文结束-------------