CtrlK

决策树学习-周志华

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 决策树算法使用增益率来选择最优划分属性

计算

信息增益
预剪枝
后剪枝

参考

周志华《机器学习》

上一页Notes 下一页神经网络-周志华

最后更新于5年前

这有帮助吗？