决策树系列2：决策树是何许人也

引言

今天的《大数据茶馆》我们来聊聊决策树是何许人也。它能解决什么问题，是怎么解决这些问题的？

---

从一个例子说起

放暑假了，小明和小亮约了每天下午一起打网球，但是由于一些原因，有些天他们并没有成行。今天他们把这几天的情况和是否适合打球列了一张表格。

希望从这张表格中可以找到一个综合各个因素得出是否适合打球的规律，这样今后约球时只需把各个因素输入进去，就知道是否适合打球而不需要纠结思考了。

从这个表格中我们分情况判断，很容易得出这样一棵树

决策树

我们来观察这棵树，这是一个类似 if-else 的判断树，帮助我们做出最后的决策，所以又叫决策树。

决策树运用多个属性综合判断给出决策，主要解决分类问题，有时也用来解决回归问题。

这棵树的节点分为两类，叶子节点和非叶子节点。

• 每个非叶子节点都是以某个属性为标准向下分支。
• 每个叶子节点都是一种决策结果。

在这棵决策树中，我们第一个选择的属性是场地，直接帮我们决策了三条数据 (1,2,3), 第二个选择的是天气，又帮我们决策了三条数据(4,5,6)。

假设我们没有这样选择，而是第一个选择的风力或者温度，可能这棵树就会复杂很多，我们需要更多条件更多层次才能做出决策。

可见在每一个非叶子节点处，选择以哪个属性来划分子树显得格外重要。

划分的选择

我们希望每次选择的属性可以让划分后的分支数据更有区分性，使各个分支的数据分类纯度更高，最好是每个分支的数据尽可能属于同一类别。

根据这个标准，如果找到《计算属性划分前后纯度变化的方法》，那么比较各个属性划分纯度变化的大小，选取纯度变化最大的属性来划分分支就行了。

属性划分纯度变化的计算方法较为典型的有三种：

• 信息增益：在 ID3 决策树中使用
• 信息增益率：在 C4.5 决策树中使用
• 基尼系数：在 CART 决策树中使用

属性划分的方法是决策树的核心，我们将在下篇文章中跟大家详聊。现在假设我们有了这样一种属性划分的方法用来在节点处选择最优属性，接下来看看怎样建立一棵决策树。

构建决策树

容易看出决策树的构建过程是一个属性划分递归的过程，下面一起来看看。

输入:
    样本集：TrainSet 用 T 表示
    属性集：AttributeSet 用 A 表示

决策树构建过程：函数 TreeGenerate(T, A)
1. 生成数据原始节点 node # 该节点包含整个输入数据集
2. if 样本集数据同属于一个类别，then
        将 node 节点标记为叶子节点，构建完成
        return
   endif
3. if A 中属性集为空，或 样本集每个样本的每个属性都一样，then
        将 node 节点标记为叶子节点, 决策类别为样本个数最多的类别，构建完成
        return
   endif
4. 从 A 中选取最优划分属性 aBest:
    for aBest 属性上的每个值 aValue：
        根据 aValue 生成一个分支节点 branch
            - 这个 branch 上的样本集为原样本集的分支子集 TBranch
            - 这个 branch 上的属性集为属性集去掉刚刚用过的aBest属性后的属性集 ABranch
        if branch 上样本集为空，then
            将 branch 标记为叶节点，决策类别为上层样本集中个数最多的类别
        else
            递归调用 TreeGenerate(TBranch, ABranch)
        endif
    endfor

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

生成决策树的递归过程有三种情形导致递归返回：

1. 样本集数据同属于一个类别, 无需划分
2. 属性集是空的，或者所有样本所有属性都一样，无法划分
3. 样本集是空的，不能划分

连续值的处理

上面讨论的属性的值是离散的，如果属性值连续的，比如温度不再是"炎热"和"凉爽"的离散值，而是一个数(比如 23.6)，此时应该如何进行属性划分呢？

最简单的方法是"二分法"，这也是 C4.5 决策树中采用的机制。

1. 首先找到这个属性在样本集中出现的所有数字并排序，比如有 n 个值，此时连续值变成了每个样本的离散值。
2. 排完序的 n 个值在任意两个值中间进行划分，有 n-1 中划分的方法, 比如从第i个与第i+1个之间划分，划分点 $t = \frac{a_i\,+\,a_{i+1}}{2}$t=2ai​+ai+1​​
3. 依次计算每个划分点的划分前后区分度(纯度)的变化，选择纯度变化最大的划分点作为该连续属性的划分点，将数据划分为两部分。

决策树的优化：剪枝

决策树的剪枝是为了防止"过拟合"，也就是训练的太全太细，把训练集一些个性特点也当成数据的一般性质了。

剪枝分为"预剪枝"和"后剪枝"

• 预剪枝： 每个节点划分时先进行估计，该节点的划分是否带来了泛化能力的提升，如果该节点划分不能带来泛化能力的提升则不划分，直接标记为叶子节点。
• 后剪枝： 先生成完整的决策树，再自下而上评估每个非叶子节点的划分是否带来了泛化能力的提升，如果没有带来泛化能力的提升，则将该节点的子树替换为叶子节点。

如何定义划分前后泛化能力有没有提升？

这里就要使用验证集的数据了，数据集在训练前应该留出一部分作为验证集，用来验证训练的效果。

根据决策树构建过程可知，

1. 如果不划分：则类别为该节点样本个数最多的类别
2. 如果划分：样本的类别在每个自分支上进行判定

如果验证集有100条数据，不划分时分类准确的有50条，划分后分类准确的只剩下30条，说明训练的结果对于验证集而言准确度下降了，也就是并没有带来泛化能力的提升，此时就应该剪枝。

---

后记

决策树今天先聊到这里，下期将带来决策树最核心的部分：如何选择最优划分属性。

欢迎关注本人公众号《大数据茶馆》，用大白话畅聊大数据。

来的都是客，欢迎您常来坐坐~