机器学习-决策树

2018-06-06 | 阅读：次

决策树基本算法

我们要判断一个复杂的问题往往通过多次简单判断来得出结论. 比如我们看到一个小姐姐我们会判断这个小姐姐是不是一个美女, 这是一个很简单的例子, 假设我们只有两个答案, 一个是,一个否, 我们首先看五官是否端正, 如果是, 我们再看有没有麻子痘痘, 如果没有我们再看看身材.. 通过上诉一系列询问最后得出结论这个小姐姐是\不是美女. 对于其中的每次判断, 都是一个决策过程, 因为我们的判断比较简单, 只会分出两种情况, 最后得到一颗二叉树, 二叉树的每个非叶子节点都代表一次决策, 每个叶子节点即我们的决策结果(论), 当然你的每次决策可能会有多种结果, 这样就会生成一个普通的树, 这棵树就是决策树.

算法:

输入: 训练集 D={(x1, y1), (x2, y2), ..., (xm, ym)}
      属性集 A={a1, a2, ..., ad}
过程: 函数TreeGenerate(D, A)

1:  生成节点node;
2:  if D中样本全属于同一个类别C then
        将node标记为C类叶节点; return
    end if
3:  if A 为空 OR D中样本在A上取值相同 then
        将node标记为叶节点, 其类别为D中样本数最多的类; return
    end if
4:  从A中选择最优化分属性a';
5:  for a' 中的每一个值aa do
        为node生成一个分支; 另Dv 表示D中在a'上取值为aa的样本子集;
        if Dv为空 then
            将分支节点标记为叶节点, 其类别标记为D中样本最多的类; return
        else
            以TreeGenerate(Dv, A\{a'})为分支节点
        end if
    end for
输出: 以node为根的决策树

上面的算法即递归建树的过程, 非常清晰, 其中只有第4步从A中选择最优化分属性a’我们不清楚什么是最优, 不同的最优化分方法效率和结果都有差别, 下面介绍几种划分方法.

ID3( Iterative Dichotomiser )决策树

在介绍ID3算法之前先来介绍一下信息熵和信息增益的概念:

信息熵: 度量样本集合纯度的常用指标, 当前样本集合D中第k类样本所占比例为 $p_k$ , D的信息熵定义为 $Ent(D) = -\sum_{k=1}^{\|y\|}p_k\log _2p_k$ .

如果我们用属性a来对D进行划分, a的取值为 $\{a^1, a^2,...,a^V\}$ , D划分之后在属性a上取值为 $a^v$ 的集合为 $D^v$ , 我们计算划分之后各个集合的信息熵, 对于每个子集合我们加一个权重 $\|D^v\|/\|D\|$

信息增益:

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

一般来说, 信息增益越大获得的纯度提升也越大, ID3算法选取使得信息增益最大的属性a来划分数据集D, 即选取 $a' = \arg \max_{a\in A} Gain(D, a)$ .

C4.5决策树算法

ID3算法倾向于选取取值数目多的属性做为划分属性, 比如我们对所有样本都进行编号, 而编号也做为一个划分属性, 这个属性的取值数目显然等于样本总数N, 这样我们划分出N个子集合, 每个子集合中只有一个元素,每个子集合的信息熵显然为0, 所有子集合的信息熵之和也为0, 信息增益获得最大值即原数据集合的信息熵. 但是这样的做法对于算法泛化很不利, 因此提出的C4.5是以增益率做为属性选取标准的算法.

增益率:

$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\|}$

IV(a)的计算方法是不是很熟悉, 感觉不到回头看看信息熵的定义. 所以上面式子的直观理解就是, 我们希望信息增益越大越好, 但是用于划分的属性a的作用于数据集D的划分结果的信息熵越小越好(这个不好解释, 大约等价于划分出的分支集合越少越好, 当然不完全等价, 需要自己体会).

如果单纯的用增益率来决定划分属性, 会致使算法倾向于选择可取值数目少的属性做为划分属性(与ID3相反), 在C4.5中先选择使得信息增益高于平均水平的属性, 再在其中选择增益率最高的属性做为划分属性.

CART决策树(Classification and Regression Tree)

CART使用基尼指数来选择划分属性.

$Gini(D) = \sum _{k=1}^{\|y\|}\sum_{k\neq k} p_kp_{k'} = 1- \sum _{k=1}^{\|y\|}p_k^2$

Gini表示直观理解就是D中热议两个任意属于一个类别的概率越高, Gini值越小, 因此Gini值可以做为集合纯度的度量, 我们希望划分之后的集合的纯度越高越好, 对于属性a其Gini值为

$Gini\_index(D,a)=\sum _{v=1}^V \frac{\|D^v\|}{\|D\|} Gini(D^v)$

欲获得最高的纯度, 我们需要Gini值越小越好, 即:

$a' = \arg \min_{a\in A} Gini\_index(D, a)$

剪枝

上面提到的是决策树的基本理论, 有些时候我们划分的过于精细会使你的决策树对你的数据过拟合而泛化性能不足, 且如果递归的对每种情况都加以考虑效率也非常低下, 下面介绍防止决策树过拟合且提高决策树构造速度的方法–剪枝. 剪枝分为预剪枝和后剪枝, 其中预剪枝可以提高效率但可能会造成欠拟合, 后剪枝不能提高效率但泛化性能更好, 下面分别介绍.

预剪枝, 顾名思义在未构造完成决策树之前进行剪枝, 具体做法是当我们递归的构造决策树到了节点S, 假设我们不对S划分(即S为叶节点), S的类别即为属于S集合中的样本的类别数最多的类(如果有3个样本,其中2个x类, 1个y类, 则S为x类), 此时准确率为p(上例中为2/3, 总过3个, 两个划对了). 对于其中可选择用于划分的属性a, 如果我们将S按照样例在属性a上的值划分为k个字迹S1, S2…Sk, 所有的子集的加权准确率为q(权值就是该子集中样本数除以S集合中的样本数, 每个子集的准确率按照之前提到的选取样本类别最多的类做为子集的类别, 求出准确率), 如果q<p, 则不进行a属性的划分, 这个很好理解, 如果我们划分之后准确率还不如没划分之前, 但是这个属性从直觉上就不适合划分(不利于泛化), 应该剪掉. 剪掉以a属性为划分节点的树不仅可以提高泛化性能, 还免去了对于以a为根的整棵子树的计算, 提高了效率. 但是因为对于以a为根的子树我们之考察了他的下一层, 再深的子节点我们都没有考察, 此时做出的决定有点莽撞, 可能会错失一些很好的结果, 造成欠拟合.

后剪枝, 和预剪枝相反, 后剪枝是构造完整颗决策树之后, 考察每个节点在验证集上的泛化性能, 如果将该节点剪掉在验证集上的结果有提升, 那我门就将以该节点为根的整棵子树剪掉. 一般来说后剪枝的泛化效果要由于预剪枝, 但是对于效率并没有提升.

连续与缺失值

对于连续值我们可以用最简单的二分法来做, 对于集合D中的连续属性a, D中的样本在a上的取值从小到大排序 $\{a^1, a^2,...,a^n\}$ , 我们取任意连个相邻值的中点做为划分节点, 划分节点集合为 $T_a = \left\{ \frac{a^i+a^{i+1}}{2} \vert 1 \leq i \leq n-1\right\}$ . 选取最优的划分节点进行样本的集合划分, 当我们求用a做为划分属性时的信息增益表示为:

$Gain(D,a) = \max_{t\in T_a} Gain(D, a, t) = \max_{t\in T_a} Ent(D) - \sum_{\lambda \in \{-,+\}} \frac{D_t^{\lambda}}{D} \lambda Ent(D_t^{\lambda})$

对于假设我们考察以a做为划分节点时, 有些样本在a属性上的信息缺失, 我们就将该节点以概率 $p_i$ 划分到第i个分支, 其中 $p_i= \frac{第i个属性的样本数}{样本总数}$

多变量决策树

如果我们每次考察一个属性作为划分属性, 可能需要非常多次的决策才行, 比如我们判断一个人身材是否匀称, 我们将身高和体重分开看来进行决策树的构造那会产生非常多的分支节点, 而如果我们将身高和体重综合起来, 比如身高体重比做为一个划分属性, 这样效率会高很多. 每次考察单个属性的影响是对整个空间进行垂直分割, 而有时我们也可以对空间进行斜的或者其他形式的分割会有更好的结果, 当然这个实现会更复杂, 本文只探讨决策树的基本理论, 所以这里不深究.

cstsunfu

孙付