决策树

决策树

决策树模型是对描述样本进行分类的树形结构。 树由节点和有向边组成, 其中内部节点标书一个特征或者属性, 叶子节点表示一个分类, 有向边代表了一个划分规则。决策树进行分类时, 对样本的某个特征进行计算, 根据计算结果将样本分配到树的子节点上,此时每个子节点对应特征的一个取值。递归地对样本计算, 直到该样本被分到某个叶节点,确定样本所属类别或者输出值。决策树可以用于分类和回归。 当用于分类时, 输出是最后叶节点所属的类别, 用于回归问题时, 最后输出是叶节点的平均值。

决策树的学习通常包含三个步骤: 特征选择, 决策树生成, 决策树剪枝。

特征选择

特征选择的关键是选取对训练数据有较强分类能力的特征。常用的特征选择指标是信息增益或者信息增益比, 分别对应于 ID3 和 C4.5算法的特征选择标准。

信息增益

我们知道信息熵的定义为

定义在数据集 D 上的信息熵为

其中 K 表示数据集 D 中类别的数目, $ N_{k} $表示类别 k 的数量. H(D) 刻画了数据集 D 中样本在各个类别的分布情况.

现在定义

  • 条件熵 , 它表示 在给定特征 A的条件下熵的期望.
  • 假设特征 A 的取值范围为 .
  • 属性 $A=a_{i}$ 的样本数量为 $N_{a_{i}}$.
  • 当属性 $A = a_{i}$ 且类别为 $c_{k}$ 的样本数量为 $N_{a_{i}, k}$

则在数据集 D 上的条件熵为

则信息增益定义为

信息增益刻画了由于特征 A 的确定, 使得数据集 D 的分类的不确定性减少的程度, 信息增益大的特征具有更强的分类能力.

信息增益比

观察 $H(D|A)$ 的定义我们发现, 当 $N_{a_{i}, k} = N_{a_{i}}$ 或者 $N_{a_{i}, k}=0$ 时, 该项为 0, 此时信息增益最大, 对应于该项特征在该类别没有值或者只有一个值,即倾向于选取值较多的特征. 显然该情况这个特征不具备什么分类能力. 因此 信息增益存在偏向于选取值较多的特征的问题 .

为了解决该问题, 人们提出了信息增益比的概念, 它在信息增益的基础上, 除以 $H_{A}(D) = -\sum_{i=1}^{n_{A}}\frac{N_{a_{i}}}{N}\log \frac{N_{a_{i}}}{N} $, 即数据集 D 在特征 A 上的取值分布情况. A 的特征值越多, 则该项越大. 从而抑制信息增益的倾向性问题. 信息增益比完整公式为

生成算法

ID3 算法生成算法采用信息增益作为特征选取标准, ID 4.5 采用信息增益比作为特征选取标准. 生成算法的流程为

  • 输入训练集 D, 特征集合 $A = {A_{1}, A_{2}, \dots, A_{n}}$, 特征信息增益(信息增益比)阈值 $\epsilon \gt 0 $, 输出决策树 T.
  • 从根节点开始, 选择信息增益(信息增益比)最大的特征 $A_{i}$ 作为分类特征
  • 对 $A_{i}$ 特征的每个可能取值 $a_{i},~~i=1,2,\dots, n_{g}$ .根据取值对数据集划分为若干子集. 将子节点中样本数最大的类别作为该子集的标记, 构建子节点.
  • 递归地对样本计算地执行以上步骤, 直到子节点中所有样本均属于一类或者信息增益(信息增益比)值小于预设值, 此时子节点为叶子节点.

剪枝算法

决策树生成的树对训练数据很容易过拟合, 过拟合产生的原因是决策树太复杂. 解决的办法是对决策树剪枝, 对决策树进行简化. 决策树的剪枝是从已生成的树上裁减掉一些子树或者叶节点, 并将根节点或者其父节点作为新的叶节点. 剪枝的依据是极小化决策树的整体损失函数. 这样通过损失函数, 使得决策树从全局上进行了优化.

决策树的损失函数定义为

其中 $T_{f}$ 为树 T 的叶节点的个数, 设叶节点 t 的样本点个数为 $N_{t}$, 其中属于类别 $c_{k}$ 的样本点有 $N_{t,k}$. $H(t) = -\sum_{k=1}^{K}\frac{N_{t,k}}{N_{t}}\log \frac{N_{t,k}}{N_{t}}$.

  • 第一项意味着叶节点的熵越大, 即分布越分散, 损失函数越大.
  • 第一项熵前面还有权重, 值为叶节点大小. 即: 越大的叶节点, 其分类错误的影响越大.
  • 第二项是一个惩罚项, $\alpha$ 是惩罚系数, 它用来限制叶节点个数, 即决策树越复杂, 则损失函数越大.

决策树剪枝的准则是考虑当 $\alpha$ 确定时, $C_{\alpha}(T)$ 最小化. 这等价于正则化的最大似然估计. 决策树剪枝的流程为:

  • 输入为决策树 T 和惩罚系数 $\alpha$, 输出为裁剪后的决策树 $T_{\alpha}$
  • 计算一组叶节点回退到父节点之前与之后的整棵树的损失函数 $C_{\alpha}(T)$ 和 $C_{\alpha}(T^{‘})$. 若剪枝后的损失函数更小, 则进行剪枝, 将父节点变成新的叶节点.
  • 递归地从树的叶节点向上回退, 执行以上步骤进行剪枝, 直到不能继续为止.

CART 树

CART 树 (Classfication and regression tree) 学习在给定输入 x 的情况下, 随机变量y 的条件概率分布的模型. 它假设决策树是二叉树, 内部节点特征取值为左侧 “yes” 和 右侧 “not”. 由于是二叉树吗, 因此 CART 树的拆分不依赖于特征的数量, 而是根据特征的取值进行划分. 因此 CART 树的取值可以使离散的, 也可以是连续的. CART 算法 也分为 决策树生成和决策树剪枝两步.

CART 生成算法

CART 生成算法有两个生成准侧:

  • CART 回归树: 平方误差最小化准则
  • CART 分类树: Gini(基尼)指数最小化准则.

CART 回归树

设 训练数据及 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})}$. 设模型将空间划分为 M 个单元$R_{1}, R_{2}, \dots, R_{M}$, 且在 $R_{m}$ 上的输出值为类别 $c_{m}$, 则 CART 树回归模型可以表示为

则采用平方误差损失函数的话, 损失函数可以表达为

为了使得损失函数最小化, 我们对 $c_{m}$ 求导为零得到最优输出解:

含义为 $R_{m}$ 上所有输出入样本 $x_{i}$ 对应的输出的平均值作为该节点的输出. 对上式进行变形:

其含义为: 经过输入空间的单元划分后, CART 树的方差. 通过这个方差来刻画 CART 回归树的纯度. 因此我们可以利用其对输入空间进行划分:

  • 选择第 j 维输入特征和它的取值 s 作为切分变量和切分点.得到两个区域:
  • 遍历所有特征和可能取值作为切分点, 找到使得损失函数最小的 j 和 s:
    • \min_{js}\left[ \right]
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章