决策树学习-周志华

title: 决策树 tags:

• 机器学习

• 决策树

  categories:

• 机器学习

基本流程

• 决策树是基于树结构来进行决策的

• 决策树学习的目的是：

  • 产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循 分而治之 策略

• 结构：

  • 一个根节点：

  • 若干内部节点：

    • 对应一个测试属性

  • 若干叶子结点：

    • 对应于决策结果

• 每个节点包含的样本集合根据属性测试的结果被划分到子结点中

• 根节点包含样本全集

• 从根节点到每个叶节点的路径对应一个 判定测试序列

输入：

• 训练集 $D = {(x_1, y_1), (x_2, y_2), …, (x_m, y_m)}$;

• 属性集 $A = {a_1, a_2, …, a_d}$

过程： 函数 TreeGenerate(D, A)

• 生成节点node;

• if D 中样本全属于同一类别 C then

  • 将node标记为C类叶节点；return

• end if

• if A = $\varnothing$ OR D 中样本在A上取值相同 then

  • 将 node 标记为叶节点，其类别标记为 D 中样本数最多的类；return

• end if

• 从A中选择最优划分属性 $a_*$；

• for $a_*$ 的每一个值 $a_*^v$ do

  • 为 node 生成一个分支；令 $D_v$ 表示 $D$ 中在 $a_*$ 上取值为 $a_*^v$ 的样本子集；

  • if $D_v$ 为空 then

    • 将分支节点标记为叶节点，其类别标记为D中样本最多的类；return

  • else

    • 以 $TreeGenerate(D_v, A \setminus {a_*})$ 为分支节点

  • end if

• end for

输出：以node为根节点的一棵决策树

• 决策树的生成是一个递归过程

• 递归返回情形

  • 当前节点包含的样本全属于同一类别，无需划分

  • 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分

    • 把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别

    • 利用当前节点的后验分布

  • 当前节点包含的样本集合为空，不能划分

    • 把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别

    • 把父节点的样本分布作为当前节点的先验分布

划分选择

• 决策树关键是如何选择最优划分属性。

• 随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

信息增益

• 信息熵(information entropy) 是度量样本集合纯度最常用的一种指标

  • 假定当前样本集合 D 中第 k 类样本所占的比例为 $p_k \ (k = 1, 2, …, |\gamma|)$，则D的信息熵定义为：

    $$Ent(D) = - \sum_{k=1}^{|\gamma|}p_k log_2 p_k$$
  • $Ent(D)$ 值越小，则 $D$ 的纯度越高

• 计算属性 a 对样本集 D 进行划分所获得的“信息增益”

$$Gain(D,a) = Ent(D) - \sum_{V}^{v=1}\frac{|D^v|}{|D|} Ent(D^v)$$

• 一般而言，信息增益越大，意味着使用属性 a 进行划分所获得的 “纯度提升” 越大

• 可用信息增益来进行决策树的划分属性选择，即选择属性：$a_* = \arg \limits _{a \in A} max \ Gain(D, a)$

• 信息增益准则对可取值数目较多的属性有所偏好

增益率

$$Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$

其中：

$$IV(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$

称为属性 a 的固有值。属性 a 的可能取值数目越多(即 V 越大)，则 $IV(a)$ 的值通常会越大。

• 增益率准则对可取数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

基尼指数

• CART决策树使用 基尼指数 来选择划分属性

• 数据集 D 的纯度可用基尼值来度量

• 选择那个使得划分后基尼指数最小的属性作为最优划分属性

剪枝处理

• 剪枝是决策树学习算法对付 过拟合 的主要手段

• 决策树剪枝的基本策略有：

  • 预剪枝

    • 在决策树生成过程中

    • 对每个节点在划分前先进行估计

    • 若当前节点的划分不能带来决策树泛化性能提升，则停止划分

    • 并将当前节点标记为叶节点

  • 后剪枝

    • 先是从训练集生成一棵完整的决策树

    • 然后自底向上地对非叶节点进行考察

    • 若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点

• 使用验证集判断泛化性能

连续与缺失值

其他

• ID3 决策树学习算法以信息增益为准则来选择划分属性

• C4.5 决策树算法使用增益率来选择最优划分属性

计算

• 信息增益

• 预剪枝

• 后剪枝

参考

• 周志华《机器学习》