Table of Contents

• 一. 决策树概述
• 1.1 树模型
• 1.2 树的组成
• 1.3 决策树的训练与测试
• 1.4 如何切分特征（选择节点）
• 1.5 衡量标准-熵
• 1.5.1 熵的概述
• 1.5.2 公式
• 1.5.3 一个例子
• 1.6 决策树构造实例
• 1.6.1 数据及目标
• 1.6.2 谁当根节点呢
• 1.6.3 计算信息增益
• 1.7 决策树算法
• 1.8 连续值怎么办？
• 1.9 决策树剪枝策略
• 1.9.1 预剪枝
• 1.9.2 后剪枝
• 参考：

一. 决策树概述

1.1 树模型

决策树：从根节点开始一步步走到叶子节点（决策）决策树

所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

下图是一个简单的树结构，判断家庭成员是否玩游戏，先按照年龄来分，后面按照性别来分。

1.2 树的组成

根节点：第一个选择点
非叶子节点与分支：中间过程
叶子节点：最终的决策结果

1.3 决策树的训练与测试

从给定的训练集构造出来一棵树（从跟节点开始选择特征，如何进行特征切分）决策树

根据构造出来的树模型从上到下去走一遍就好了

一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点就在于如何构造出来一颗树，这就没那么容易了，需要考虑的问题还有很多的！

1.4 如何切分特征（选择节点）

根节点的选择该用哪个特征呢？接下来呢？如何切分呢？决策树

想象一下：
我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家了。

通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

1.5 衡量标准-熵

1.5.1 熵的概述

熵是表示随机变量不确定性的度量
（解释：说白了就是物体内部的混乱程度，比如杂货市场里面什么都有那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦）

1.5.2 公式

pi代表的是某一类出现的概率

H(X)=-Σ pi * logpi, i=1,2, ... , n
公式解释如下:

log函数的分布图，pi取值范围是[0-1],所以取值都是负数，顾前面有一个负号，因为我们的熵要求是正值。从分布图我们可以看到，当概率越大的时候，熵越小。

1.5.3 一个例子

A集合[1,1,1,1,1,1,1,1,2,2]

B集合[1,2,3,4,5,6,7,8,9,1]
显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些

而B中类别太多了，熵值就会大很多。（在分类任务中我们希望通过

节点分支后数据类别的熵值大还是小呢？）
不确定性越大，得到的熵值也就越大

当p=0或p=1时，H§=0,随机变量完全没有不确定性

当p=0.5时，H§=1,此时随机变量的不确定性最大

如何决策一个节点的选择呢？

信息增益：表示特征X使得类Y的不确定性减少的程度。

（分类后的专一性，希望分类后的结果是同类在一起）
1.6 决策树构造实例

1.6.1 数据及目标

数据：14天打球情况

特征：4种环境变化

目标：构造决策树

1.6.2 谁当根节点呢

划分方式：4种

依据：信息增益

1.6.3 计算信息增益

在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：

4个特征逐一分析，先从outlook特征开始：

Outlook = sunny时，熵值为0.971

Outlook = overcast时，熵值为0

Outlook = rainy时，熵值为0.971
select -2/5*log(2,2/5) -3/5*log(2,3/5)  from dual;
select -5/5*log(2,5/5)  from dual;
select -3/5*log(2,3/5) -2/5*log(2,2/5)  from dual;
根据数据统计，outlook取值分别为sunny,overcast,rainy的概率分别为：5/14, 4/14, 5/14
熵值计算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693
同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以啦，相当于是遍历了一遍特征，找出来了大当家，然后再其余的中继续通过信息增益找二当家！

（gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）
1.7 决策树算法

决策树的几种常见实例
ID3决策树
C4.5决策树
CART分类（回归）树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1BKYm0cU-1658386432760)(https://upload-images.jianshu.io/upload_images/2638478-73a47997f1c1d440.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)]
变量信息增益最大，才是最重要的变量，放在最上面

变量的值有很多，但是在训练集里面是有限的，所以可以标记出来
信息增益是否最大