一. 决策树概述

1.1 树模型

1. 决策树：从根节点开始一步步走到叶子节点（决策）决策树
2. 所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

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

image.png

1.2 树的组成

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

image.png

1.3 决策树的训练与测试

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

2. 测试阶段
   根据构造出来的树模型从上到下去走一遍就好了

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

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

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

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

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

1.5 衡量标准-熵

1.5.1 熵的概述

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

1.5.2 公式

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

H(X)=-Σ pi * logpi, i=1,2, ... , n

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

image.png

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(p)=0,随机变量完全没有不确定性
当p=0.5时，H(p)=1,此时随机变量的不确定性最大

image.png

如何决策一个节点的选择呢？
信息增益：表示特征X使得类Y的不确定性减少的程度。
（分类后的专一性，希望分类后的结果是同类在一起）

1.6 决策树构造实例

1.6.1 数据及目标

数据：14天打球情况
特征：4种环境变化
目标：构造决策树

image.png

1.6.2 谁当根节点呢

划分方式：4种
依据：信息增益

image.png

1.6.3 计算信息增益

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

image.png

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;

image.png

根据数据统计，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 决策树算法

image.png

决策树的几种常见实例

1. ID3决策树
2. C4.5决策树
3. CART分类（回归）树

image.png image.png

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

年龄	分离点	信息增益是否最大
12
18	15
19	18.5
22	20.5	是
29	25.5
40	34.5

如果20.5处，信息增益最大，则此处是最好的分离点

1.8 连续值怎么办？

image.png

1.9 决策树剪枝策略

为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据
（想象一下，如果树足够庞大，每个叶子节点不就一个数据了嘛）

image.png

剪枝策略：预剪枝，后剪枝

image.png

1.9.1 预剪枝

边建立决策树边进行剪枝的操作（更实用）

预剪枝：限制深度，叶子节点个数
叶子节点样本数，信息增益量等

1.9.2 后剪枝

当建立完决策树后来进行剪枝操作

通过一定的衡量标准

image.png

（叶子节点越多，损失越大）

参考：

1. https://study.163.com/course/introduction.htm?courseId=1003590004#/courseDetail?tab=1