机器学习-西瓜书第4章-决策树

结合李航老师《统计学习方法》，笔记参见【统计机器学习-李航】第5章 决策树

4.1 导入

从根节点 到 每个叶节点的路径对应了一个 判定测试序列。决策树学习的目的是 产生一颗泛化能力强的决策树，基本流程遵循 简单且直观的“分而治之 (divide-and-conquer)” 策略。

输入：训练集 

        属性集 

过程：

定义 函数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中 选择最优划分属性 ；     # 这一步是十分关键，那么如何选择最优划分属性？参见4.2

        for  的每一个取值  do

                为node生成一个分支；令  表示D中 在上取值为  的样本子集；

                if  为空 then

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

                else

                        以 TreeGenerator (, A \ {}) 为分支结点

                end if

        end for

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

决策树的生成过程是一个递归过程。过程中碰到以下三种情形，则进行递归：

1. 当前结点包含的样本 全部属于同一类别，无需划分；
2. 当前属性集为空，或 所有样本在所有属性上取值相同，无法划分；
3. 当前结点包含的样本集合为空，不能划分

4.2 划分选择

我们希望 决策树的分支结点包含的样本尽可能属于同一个类别，即结点的纯度越高越好。

4.2.1 信息增益

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

假定当前样本集合D中 第k类样本所占的比例为 , 则D的信息熵可定义为：

Ent(D) 值越小，则D的纯度越高。(Ent(D) 值小 -> pk取值愈接近1 -> 某类样本所占比愈大，接近100% -> 训练数据集的纯度愈高)

使用属性a 对样本D进行划分所获得的 “信息增益 (information gain)”如下：

当根据属性a 对 D进行划分，则产生V个分支结点，我们用  表示：第v个分支结点包含了 D中所有的属性值为  的样本子集，上式中  表示：分支结点权重，样本数量越多，该分支结点权重应该越大。

信息增益Gain (a, D)越大，意味着：使用属性a 来进行划分 所获得的 “纯度提升”越大。

因此可以使用 信息增益来进行决策树的划分属性选择，即 

一个例子理解：使用信息增益来选择划分属性

1.  计算信息熵Ent(D): 观察可得:|Y| = 2，正例占比p1= 8/17, 反例占比p0 = 9/17,因此有

      2. 计算所有属性的信息增益，具体计算过程举 色泽为例：

根据色泽属性 = {青绿，乌黑，浅白}，将数据集D分为 D1, D2, D3三个分支结点，分别计算3个分支结点的信息熵为：

计算出“色泽属性”的信息增益为：

依次计算其他5个属性的信息增益：

 由于 属性===纹理的 信息增益最大，因此，它被选为划分属性，得到如下图：

 得到上图后，再对每一个分支结点，即纹理==清晰，纹理==稍糊， 纹理==模糊再次进行划分。具体地，先看纹理==清晰，即样例集合D1的情况：

包含9个样例，属性集合为{色泽，根蒂，敲声，脐部，触感}，5个属性。

首先计算信息熵：

然后，计算该9个样例的 所有属性的信息增益，以色泽为例：

根据色泽属性 = {青绿，乌黑，浅白}，将数据集 分为 三个分支结点，分别计算3个分支结点的信息熵为：

计算出“色泽属性”的信息增益为：

如此，依次计算出 其他属性的信息增益为：

 由于 根蒂，脐部，触感的信息增益并列最大， 可任意选择其中之一作为划分属性，并再次进行分支结点划分(如选择根蒂，则根据根蒂==蜷缩，根蒂==稍蜷，根蒂==硬挺 划分子结点)，得到最终的决策树如下：

4.2.2 增益率 ：C4.5决策树算法

使用信息增益准则来 选择划分属性的缺点：对可取值数目较多的属性有偏好，这会带来不利影响。比如若将上述数据集D中的编号也作为候选划分属性，则可计算出 其信息增益为 0.998，但显然这不是一颗好的决策树，因为它无法对新样本进行预测。

改进对策：使用“增益率 (gain ratio)”来选择最优划分属性。增益率表示为：

IV(a)称为 属性a的“固有值 (intrinstic value)”。属性a的可能取值数目越多，则IV(a)的值通常也越大。相应地，增益率则会变小，表明了 对取值数目很多的属性的 信息增益的惩罚。

增益率的偏好：对可取值数目较少的属性有偏好。

4.2.3 基尼指数 (Gini index)：CART决策树

使用基尼值来衡量 数据集D的纯度：

Gini(D)反映了 从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini(D)越小，表示 数据集D的纯度越高。

属性 a 的基尼指数为：

4.3 剪枝处理 (pruning)

剪枝 (pruning)是 决策树学习算法解决“过拟合”问题的主要手段。其基本策略有：预剪枝 (prepruning) 和 后剪枝 (post-pruning).

数据集如下:

未剪枝决策树：

 

4.3.1 预剪枝

生成决策树过程中，对每个结点在划分前进行估计，若 当前结点的划分不能带来性能提升，则停止划分并将当前结点 作为叶节点。

选择 脐部 对训练集进行划分，产生3个分支，如下图所示：

4.3.2 后剪枝

先从训练集生成一棵完成决策树 

4.4 连续与缺失值

4.4.1 连续值处理

不能直接根据连续属性的可取值来对结点进行划分，可采用二分法 (bi-partition)对连续属性取值进行处理：

对于相邻的属性取值  和  来说，t 在区间[ , )中 取任意值所产生的划分结果相同。则包含n-1个元素的 候选划分点集合为

 如此，便可以像离散属性值一样来考察这些划分点，选择最优的 划分点进行样本集合的划分。

4.4.2 缺失值处理

样本的某些属性值缺失，导致样本不完整，但如果放弃这些信息不完整的样本，将造成数据信息的浪费。

需要解决两个问题：

1）如何在属性值缺失的情况下，选择划分属性？

2）给定划分属性，若样本在该属性上的值已经缺失，该如何对样本进行划分？

4.5 多变量决策树

这篇好文章是转载于：学新通技术网