决策树

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构

决策树由以下内容组成：

  • 结点 (node)
    • 内部结点 (internal node)
      • 表示一个特征或属性
    • 叶结点 (leaf node)
      • 表示一个类
  • 有向边 (directed edge)

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中

![[images/截屏2026-03-30 13.16.50.png]]

if-then 规则

决策树的路径（或其对应的 if-then 规则集合）具有：互斥并完备的特性。即每一个实例都被且仅被一条路径或者一条规则覆盖

条件概率分布

决策树表示给定特征条件下类的条件概率分布

  • 这一条件概率分布定义在特征空间的一个划分 (partition)上
  • 将特征空间划分为互不相交的单元 (cell) 或区域 (region) ，并在每个单元定义一个类的概率分布就构成了一个条件概率分布
  • 决策树的一条路径对应于划分中的一个单元
  • 决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成

假设 $X$ 为表示特征（长度、身高、体重）的随机变量，$Y$ 为表示类（长短、黑白、优劣）的随机变量，那么这个条件概率分布可以表示为 $P(Y|X)$

  • $X$ 取值于给定划分下单元的集合
  • $Y$ 取值于类的集合

各叶结点上的条件概率往往偏向某一个类，即属于该类的概率会更大。因此决策树分类时，会将该结点的实例强行分到该条件概率大的一类中

![[images/截屏2026-03-30 14.00.08.png]]

  • $P(Y=+1|(x^{(1)}\leq a_1, x^{(2)}\leq a_2))=1$
  • $P(Y=+1|(x^{(1)}\geq a_1, x^{(2)}\leq a_3))=0$
  • $P(Y=+1|(x^{(1)}\leq a_1, x^{(2)}\geq a_2))=0$
  • $P(Y=+1|(x^{(1)}\geq a_1, x^{(2)}\geq a_3))=1$

决策树学习

决策树学习的本质是从训练数据集中归纳出一组分类规则

  • 目标：与训练数据矛盾较小，同时具有很好的泛化能力
  • 指标：损失函数
  • 策略：以损失函数为目标函数的最小化

确定损失函数后，问题变为：在损失函数意义下选择最优决策树的问题（NP 完全问题）。采用启发式方法，得到次最优决策树

递归选择最优特征

  • 构建根结点：所有训练数据都在根结点，选择最优特征
  • 根据最优特征分割子集，使得各个子集都有一个在当前条件下最好的分类
    • 子集能被正确分类：构建叶结点
    • 子集不能被正确分类：选择新的最优特征，继续分割

特征选择

特征选择问题

信息增益

信息增益比

决策树生成

ID3 算法

C4.5 算法

决策树剪枝

CART 算法

CART 生成

CART 剪枝