第四章决策树

作者: 康君爱上了蕊酱 | 来源:发表于2018-08-29 10:24 被阅读0次

机器学习（4）
第四章决策树
《机器学习》西瓜书学习笔记（三）
机器学习西瓜书 Day04 决策树
机器学习6-决策树
决策树
决策树
决策树算法总结
机器学习 - 决策树算法[一]
机器学习系列（三十六）——回归决策树与决策树总结

基本流程

决策树是一种常用的机器学习方法，过程类似于树状结构每一层通过对属性进行决策来进行分类。

结构主要有：根节点（初始的所有数据集），内部节点（初步决策结果），叶节点（最终决策结果），路径（判定决策过程）。

决策树学习基本算法：

输入：训练集D,属性集A={a1,a2,...,ad}
过程：函数TreeGenerate(D,A)
  生成节点node:
  if D中样本全属于统一类别C then
    将node标记为C类叶节点;return
  end if 
  if A=空集 or D中样本在A上取值相同 then
    将node标记为叶节点，类别标记为D中最多的类;return
  end if
  从A中选择最优划分属性a*;
  for a* 的每一个取值a*v do
    为node生成一个分支;另Dv表示D在a*上取值为a*v的样本子集;
    if Dv为空 then
      将分支节点标记为叶节点，类别标记为D中最多的类;return
    else
      以TreeGenerate(Dv,A\{a*})为分支节点
    end if
  end for
输出：以node为根节点的一颗决策树

这个是一个递归过程，其中有三种情况导致递归返回：

当前节点所有样本属于同一类，不用再划分
当前节点属性集空，不能再划分（当前节点的后验分布）
当前节点样本集为空，不能再划分（将父节点的分布当成当前节点的先验分布）

划分选择

什么样的划分属性是最优的？划分后的结点中样本的纯度因该是比划分前高的。因此，引入了信息熵即度量样本集合纯度的指标，样本集合 $D$ 的信息熵定义为：
$Ent(D)=-\sum^{|y|}_{k=1}p_k\log_2p_k$
其中 $p_k$ 为第 $k$ 类样本所占的比例。信息熵的值越小， $D$ 的纯度越高。

当根据某一属性 $a=\lbrace a^1,a^2,\ldots,a^V\rbrace$ ，对 $D$ 进行划分后，形成的多个子结点的信息熵就是 $Ent(D^v)$ 。为了比较前后的信息熵变化，定义信息增益：
$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$
其中 $\frac{|D^v|}{|D|}$ 为每个分支点的权重。信息增益越大，就表明通过属性 $a$ 划分得到的子结点的纯度提升越大。

同时注意到一个问题，信息增益作为度量的时候，对于取值数目多的属性具有偏爱性，比如样本序号（1，2，3，4，5），如果作为一种划分属性，得到的结果纯度达到 $100\%$ ，但是却不具有对新样本的预测能力。因此引入增益率:
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
其中：
$IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$
但是，增益率对于取值数目少的属性具有偏爱性，因此长使用一种启发式：先挑选信息增益高于平均水平的属性，然后在选取增益率最高的属性。

CART决策树是一种著名的决策树学习算法，分类和回归任务都可用。它使用“基尼指数”来选择划分属性。D的基尼值度量为：
$Gini(D)=\sum^{|y|}{k=1}\sum_{k' \not= k}p_kp'_k$
$=1-\sum^{|y|}_{k=1}p_k^2$
指从D中随机抽取两个样本不同类的概率，越小，D的纯度越高。
属性 $a$ 的基尼指数定义为：
$Gini_index(D,a)=\sum_{v=1}^V \frac{|D^v|}{|D|}Gini(D^v)$
使得划分后基尼指数最小的属性为最优属性。

剪枝处理

剪枝指对决策树进行枝干的修剪，为了应对过拟合现象。分为以下两种：

预剪枝
预剪枝是在决策树形成的过程中，根据结点划分是否提升决策树整体的泛化性能来决定。这种方法计算量比较小，但是因为其贪婪特性，可能导致欠拟合（一些后续划分提升泛化性能的枝，会因为初始划分不能提升泛化性能而扼杀）。
后剪枝
后剪枝是在决策树形成后，自下而上，根据非叶结点替换为叶节点是否提高决策树泛化性能来决定是否替换。这种方法计算量比较大，但是不会欠拟合，而且多数情况比预剪枝的泛化性能要强。

连续与缺失值

连续值处理
对于给定的数据集D，连续属性 $a=\lbrace a^1,a^2, \dots,a^n\rbrace$ ，并不能像离散指那样直接按照取值进行划分。因此，将连续属性的所有取值进行，从小到大的排序，然后 $a^i,a^{i+1}$ 之间任意的取值划分效果相同，所以候选划分点集合为：
$T_a=\lbrace \frac{a^i+a^{i+1}}2|1\leq i \leq n-1\rbrace$
然后就可以按照离散属性值一样来考察这些划分点，选取最优划分点。例如：
$Gain(D,a)=max_{t \in T_a} Gain(D,a,t)$
$=max_{t \in T_a} Ent(D)-\sum_{\lambda \in \lbrace -,+\rbrace}\frac{|D^{\lambda}_t|}{|D|}Ent{D_t^\lambda}$
注意，与离散值不同的是，连续属性在划分后的后代结点还可继续划分。
缺失值处理
给定数据集 $D$ ，缺失属性 $a$ ， $D'$ 表示属性 $a$ 上没有缺失值的样本子集， $D'^v$ 表示 $D'$ 在属性a上不同取值的样本子集， $D'_k$ 表示 $D'$ 中的第几类样本。
问题主要是在存在属性值缺失的情况下，选择划分属性，并且进行划分。先要进行准备工作：
首先，每个样本初始化权重 $w_x$ （取值1），然后定义：
$\rho=\frac{\sum_{x \in D'}w_x}{\sum_{x \in D}w_x}$
$p'^k=\frac{\sum_{x \in D'_k}w_x}{\sum_{x \in D'}w_x}$
$r'_v=\frac{\sum_{x \in D'^v}w_x}{\sum_{x \in D'}w_x}$
根据这些式子就可以将信息增益推广：
$Gain(D,a)=\rho \times Gain(D',a)$
$=\rho \times(Ent(D')-\sum^V_{v=1}r'_vEnt(D'^v))$
其中：
$Ent(D')=-\sum_{k=1}^{|y|}p'_k \log_2 p'_k$
划分的过程中，样本在属性 $a$ 上的取值已知，直接划分对应的子结点，权重保持 $w_x$ ，如果未知，同时划入所有子结点，权重调整为 $r'_v \cdot x_x$ 。

多变量决策树

多变量决策树在划分的时候不再是针对一个属性，而是针对多个属性的组合。

我们把每个属性看做一个坐标轴， $d$ 个属性的样本就对应了 $d$ 维空间中的一个点，分类就相当与寻找一个边界将点划分开。决策树的划分有个特点就是，形成的划分界面是多段与坐标轴平行的线段组成（单每层单属性划分）。每一段对应了某个属性的取值，解释性强，但是运算量比较大。因此想要通过平滑的斜线来代替这些线段，这样可以简化模型，同时达到分类效果，即每次划分采用多属性的组合：
$\sum^d_{i-1}w_ia_i=t$
其中 $w_i$ 为属性 $a_i$ 的权重， $t$ 代表线性分类器， $w_i$ 和 $t$ 都可以在该结点对应样本集和属性集上学得。

机器学习（4）
本章节是对我学习完机器学习（周志华）第四章所做出来的总结第四章决策树 4.1 基本流程一般的，一棵决策树包...
第四章决策树
第四章决策树 4.1 基本流程一颗决策树一个根结点，若干内部结点，若干叶结点。数据结构中结点是专用的。叶...
《机器学习》西瓜书学习笔记（三）
上一篇笔记在这里：《机器学习》西瓜书学习笔记（二）第四章决策树 4.1 基本流程决策树的生成是一个递归过程，...
机器学习西瓜书 Day04 决策树
p73 - p97 第四章决策树 4.1 基本流程一棵决策树包含一个根节点，若干个内部节点和若干个叶节点；叶节...
机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
决策树
1、决策树决策树学习通常包括3个步骤：特征选择。决策树生成。决策树剪枝。决策树的学习目标是：根据给定的训...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
机器学习 - 决策树算法[一]
1 决策树模型与学习 1.1 决策树模型决策树定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...
机器学习系列（三十六）——回归决策树与决策树总结
本篇主要内容：回归决策树原理、回归树学习曲线、决策树总结回归决策树原理回归决策树树是用于回归的决策树模型，回归...