Introduction to Decision tree

class: center, middle, inverse

# 决策树简介
章恒
.footnote[Power by Remark.js & MathJax.js]

???
上一次分享时，我们以线性回归这一个监督式学习算法为例子，给大家科普了模型、算法、损失函数以及机器学习里面的一些重要的概念，相信大家对模型这个黑盒子应该有了一个初步的认识，今天则是介绍另外一个传统、经典的模型，决策树。
开始之前，先简单回顾下线性回归，顺便加强下对机器学习的三要素的认识
---

.left-column[
  ## review
  ### - linear regression
]
.right-column[

模型：\$\hat{y} = h_{\theta} (\textbf{x}) = \theta^{T} \cdot \textbf{x}\$

策略：\$J(\theta) = \textbf{MSE} = \frac{1}{m} \sum_{i=1}^{m} (\theta^{T}\cdot\textbf{x}^i - y^i)^2\$

算法：normal equation、 Gradiend desent

<img src="/public/fig/mr_17.png" width="500" height="450">
]

???
首先，机器学习首先就是要考虑的问题就是学习一个什么样的模型，可能是一个函数也可能是一个概率分布。

线性回归的模型时假设我们的样本的各个特征和要预测的值之间存在这样的一个简单的线性关系。theta是模型的参数权重向量, x是样本的特征向量

有了模型之后，接着要考虑的是按照什么样的准则学习最优的模型，也就是学习的策略。
通常而言，需要选择一个损失函数来表达训练样本数据集拟合模型的程度，训练过程就是去最小化这个损失函数以求解模型参数

对于线性回归的来说，我们使用的是均方误差来度量样本数据拟合模型的程度

最后，怎么去最小化这个损失函数，也就是训练所采用的算法，上次分享以最小化均方误差函数为例，介绍了两种训练线性回归模型的算法
一个是normal equation，直接得到模型参数向量的解析解，另外一个是gradiend desent，他是按照梯度方向迭代更新模型参数已最优化目标函数的一种数值算法

---
.left-column[
  ## review
  ### - elements
]
.right-column[

### 模型
 - \$Y = f(X)\$ （基于决策函数）
 - \$Y = arg max_{c_k}P(c_k|X)\$ （基于概率分布）

### 策略

- 0-1损失函数  \$L(Y,f(X)) = (Y != f(X))\ ?\ 1 : 0\$
 - 平方损失函数  \$L(Y, f(X)) = (Y - f(x))^2 \$
 - 绝对损失函数  \$L(Y, f(X)) = abs((Y - f(x)) \$
 - 对数损失函数  \$L(Y, f(X)) = -log(P(Y|X)) \$

### 算法
 - 最优化问题
 - 随着模型假设空间、策略的不同而不同

]

???
模型、策略、算法这三者就是所谓的机器学习三要素，可以说任一种统计学习方法本质上都是由这三个要素构成
模型，前面说到，可以是基于决策函数的，模型又一个函数表达，输入是样本的各个特征值，输出是模型的预测结果

对于分类问题，模型往往也会基于概率分布去表达，即我们学习出在给定样本数据下的各个类别的条件概率，选择最大的作为预测的分类结果

关于策略，也就是损失函数，这里列举了几种常见的，其中Y是真实值，F(X)是预测值，第一种叫0-1损失函数

对数损失函数，对分类问题来说很常见，可能看起来没那么直观，这里简单解释下，对分类问题来说，模型通常是基于这种概率分布来表达的，
损失函数要度量的是模型误分类的惩罚代价，正确分类时代价小，错误分类时代价大，正好和P(Y|X)相反，所以有这么个负号

最后，算法就是基于训练数据样本集、根据定义好的学习策略，从模型的假设空间中选择出最优模型的方法。
通常而言，他是一个最优化问题，会随着模型的假设空间、以及学习策略不同而不同

这三者就是机器学习这个黑盒子内部的大概结构，不同的机器学习方法主要就来自于模型、策略、和算法的不同。

有时，模型简单，比如线性回归，直接能找到最优化问题的解析解，有时候模型复杂，需要通过一些数值计算算法求近似求最优解，
有时全局最优解不容易求，退而求其次得到一个次优解。

今天要介绍的决策树，就是这么一个例子

---
class: center, middle, inverse

# 什么是决策树

???
好，那什么事决策树，首先回答决策树方法的模型是什么，

---
.left-column[
  ## desicion tree
  ### - model
]
.right-column[
 ### 决策树模型

]

???
这里，以根据西瓜的各个特征预测西瓜的好坏例子，决策树模型得到的是这样的一颗树，从根节点开始，每个非叶子
都是对样本的某个特征进行测试，按照特征的不同有多个分支，每个分支都对应着改特征的一个取值，这样递归的进行直到达到叶子节点，
叶子节点就回答了类别或者要预测的值

可以将决策树看做是一堆判别规则的集合，这堆判别规则是互斥而且完备的，也即是说每个样本都有且唯一一条从根节点到叶子节点的路径

---
.left-column[
  ## desicion tree
  ### - entropy

<img src="/public/fig/dt2.png" width="300" height="260">
]
.right-column[
 ### 熵

- 香农信息论里最基本的概念
 - 度量的是随机变量的不确定性

- 假设X是一个离散型随机变量，有n个不同的取值，概率分布情况是：
 
 $$P(X = x_i) = p_i, i =1,2,...,n$$

那么，X的熵为

$$H(X) = -\sum_{i=1}^{n}p_ilogp_i$$

- 当随机变量只有两个离散值时（比如0和1）\$P(X=1) = p, P(X=0) = 1-p\$

$$H(p) = -p log_2p - (1-p)log_2(1-p)$$

举例： 地球明天会不会毁灭、抛一枚硬币出现的正面还是反面

]
???
决策树模型有了，接下来就要回答训练决策树模型的策略，也就是决策树的损失函数怎么定义。

这回答这个问题之前，需要先介绍一个概念，熵，因为决策树利用熵来表达损失函数。

熵本来是物理学的中概念，在香农的信息论中含义被引申，用来度量随机变量的不确定性

。。。

---
.left-column[
  ## desicion tree
  ### - loss
]
.right-column[
### 怎么利用熵来度量决策树的拟合训练数据集的好坏？

\$Ht(T) = -\sum_{k=1}^{K}\frac{\|C_k\|}{\|D\|}log\frac{\|C_k\|}{\|D\|}\$

\$Cost(T) = \sum_{t=1}^{\|T\|}N_tHt(T)\$

]
???
那么怎么用熵来度量决策树拟合训练集数据的好坏呢？

这里还是已对西瓜分类为例，假设我们有这样一颗决策树，现在把我们的训练样本西瓜数据集按照这个决策树来分类，最终所有样本中会被划分到不同的这些叶子节点上
也就是每个叶子节点上都挂着很多样本实例

每个叶子节点都可能存在一些误分类，也就是说对于训练集样本，每个叶子节点都可能有些正例也有些负例，因此我们可以为叶子节点定义它的经验熵，根据前面熵的定义有这个式子。

这时这个叶子节点的经验熵表达的是这个叶子节点拟合对应部分样本集的好坏，因为这个熵值越小，意味着不确定性越小，分类的越准确。

那么，总体上一颗决策树的代价函数就可以用这个式子来度量，T是叶子个数，即每个叶子节点上的样本集大小*叶子节点的经验熵值，对所有叶子节点求和就是这颗决策树的代价

下面问题就是怎么最小化这个代价函数。

---
.left-column[
  ## desicion tree
  ### - algorithm
]
.right-column[
### 怎么最小化决策树的代价函数

- 从所有决策树空间中搜索最优决策树是个NP-complete问题

- 存在很多启发式算法: ID3、C4.5、CART

- 基本思想：选择一个最优的特征，根据这个特征来对训练数据集进行分割，对分割产生的各个子数据集递归地重复这个过程，直至将各个子数据集基本分类。
这个选择特征，再分割训练数据集的过程就是决策树的生成过程。

- 剪枝：
  - 为了防止过拟合
  - 预剪枝和后剪枝

]
???
不幸的是，从所有的决策树构成的决策空间中搜索最优决策树是个NP-complete问题，没法在多项式时间求得最优解

只能退而求其次，找次优解

那么存在很多种启发法算法，最经典常用的有...

他们的基本思想都类似...

还是以识别西瓜好坏为例，介绍下这个构建过程，刚开始先构建根节点，我们经过对数据集的统计发现纹理这个特征对瓜好坏的区分度是最高的，（最优特征）
，所以先采用纹理的不同来分割数据集，得到三个子数据集。对于这个子数据集，我们发现里面的样本基本都是坏瓜了，意味着我们不需要再
去对他找别的特征来进行分割，就形成了一个叶子节点。
对于其他数据集，比如第一个，其中有好瓜也有坏的，对这个数据集我们再统计发现根蒂的形状对区分好坏有很大帮助，因此再根据根底形状进行分割，
递归地重复这个过程，直至所有的子数据都已基本分类。那么一颗决策树就构建好了。

为什么要选择这样的启发式策略，从直观上来看，选择最优特征这中做法倾向于生成一个深度浅的树，从而叶子节点数少，从而近似最优化这个代价函数

在生成好一颗决策树后，为了防止过拟合，我们通常还需要进行剪枝操作。剪枝操作分为两类，预剪枝和后剪枝(一个事先，一个事后)后面再介绍

---
class: center, middle, inverse

# 怎么选择最优特征

???
那么怎么来选择这个最优特征呢，也就是怎么度量特征区分度，这是启发式策略的关键，不同的度量方法也决定了算法的不同

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - feature selection
]
.right-column[
### 信息增益

假设训练数据集D，\$\|D\|\$表示其样本容量，有K个分类: \$C_1,C_2,C_3,...,C_k\$, \$\|C_k\|\$是第k类的样本个数

那么：\$\sum_{k=1}^{K}\|C_k\|\$ = \|D\|

假设特征A有n个不同的取值{\$a_1, a_2, ..., a_n\$}，特征A的不同取值将D划分为n个不同子数据集\$D_1,D_2,...,D_n\$，
\$\|D_i\|\$是第i个子集中的样本个数。

记子集\$D_i\$中属于类 \$C_k\$ 的样本集合为:

\$D_{ik} = D_i \cap C_k\$

- 定义：数据D的熵为H(D): \$H(D) = -\sum_{k=1}^{K}\frac{\|C_k\|}{\|D\|}log\frac{\|C_k\|}{\|D\|}\$

- 定义: 特征A对数据集D的条件熵H(D|A): \$H(D|A) = -\sum_{k=1}^{K}\frac{\|D_i\|}{\|D\|}H(D_i) \$

- 定义: 特征A的在数据D的信息增益g(D,A): \$g(D,A) = H(D) - H(D|A)\$

]
???
为了度量特征的区分度，引入一个概念：信息增益

先给出一些符号定义。。。

那么定义数据集D的经验熵，根据熵的定义有这个式子，可以将Ck/D看作数据集D中类别k的概率，数据集D的经验熵度量了D的不确定性

在定义特征A对数据集D的条件熵，意思是特征A取值给定下的数据集D的经验熵，特征A的各个取值下的子数据集的熵的数学期望

最后，特征A的信息增益定义就是.., 表达的是A这个特性确定之后，对原来数据集D不确定性的减少程度，值越大表示这个特征的区分度越大
对分类的贡献越大

现在对于给的一个数据集，我们可以通过这个式子来计算来计算各个特征的信息增益，选择信息增益最大的特征作为最优特征。然后划分数据集进行分割，同时构建决策树节点
ID3算法就是这样干的

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - ID3/C4.5
]
.right-column[
### ID3
- 使用信息增益作为最优特征的选择依据

### C4.5
- 使用信息增益比作为最优特征的选择依据
  $$g_r(D,A) = \frac{g(D,A)}{H(D)}$$

]
???

ID3算法就是直接拿信息增益作为每次选择特征的依据，

C4.5算法很类似，作为对ID3的改进，他认为信息增益本身是绝对值，他是以特征A的信息增益值和当前数据集D的比值作为最优特征的选择依据

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - pruning

<img src="/public/fig/dt3.png" width="300" height="300">
]
.right-column[
### 剪枝
- 预剪枝：在生成决策树过程中就采取策略防止模型过复杂，比如限制树的最大深度、设置子数据集的熵阈值

- 后剪枝：在生成完决策树后对树进行修剪。

$$C_α(T) = Cost(T)+α\|T\|$$

算法思想

- 计算树每个叶子结点的经验熵。
   - 递归地从叶节点向上回缩：设一叶结点回缩到父结点之前和之后，树分别是TB和TA，其对应的损失函数值分别是Cα(TB)与Cα(TA)，如果Cα(TA)≤Cα(TB)，则剪枝，即将父节点变成新的叶结点。

]
???
前面提到，决策树算法通常需要剪枝，目的是为了防止过拟合，因为递归生成的决策树比较深的话很容易就过拟合

剪枝有两种方法。。。spark里的决策树实现采用的就是这中策略，很简单

另外一种，是后剪枝，就是在生成完决策树后，对树的节点进行修剪，去掉一些不必要的子树或者叶子节点，使其归并到上一层父节点作为新的叶子，从而简化树模型。
通常而言，剪枝可以通过最小化决策树的整体代价函数来实现，这个定义了一个新的代价函数，在之前的代价函数基础之上增加了一个表达树模型复杂惩罚项，这也是一般的模型正则化思想

这里给出一个通过最小化代价函数来实现剪枝的算法思想：

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### CART（分类与回归树）

- 更为通用和广泛，可以用于分类也可以用于回归，分类树和回归树

- 二叉树，分支都是是和否（类似于把特征做onehot编码）

- 算法思想：选择特征和划分，递归生成决策树，剪枝

]
???
前面介绍的ID3 C4.5算法属于比较经典的决策树算法，只能用于分类，现在应用的更多更广泛的是CART算法
既可以用于分类也可以用于回归，
CART的模型上也与前面稍有不同，他是一颗二叉树，即每个中间节点都是在测试特征是否满足某个属性，类似于把特征
做onehot编码，在模型的表达上优于前面的多叉树模型

他的算法思想也稍有不同，即不仅要考虑选择最优特征，还有考虑选择最优特征的最优划分，然后递归去生成决策树，再剪枝

比如这里是一颗对水果种类进行划分的CART分类树，首先选择的是颜色这个特征，以及是否为绿色这一划分

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### 分类树

- 定义：Gini指数 \$Gini(D) = \sum_{k=1}^{K}p_k(1-p_k) \$

\$= 1 - \sum_{k=1}^{K}p_k^2\$
  
  \$= 1 - \sum_{k=1}^{K}(\frac{\|C_k\|}{\|D\|})^2\$

Gini指数度量的是数据集D的不确定性（和熵类似）

- 将数据集D按照特征A是否取某一个值a来划分，可分割成两部分，\$D_1\$和\$D_2\$, 
  
  定义条件基尼指数：\$Gini(D,A) = \frac{\|D_1\|}{\|D\|}Gini(D_1) + \frac{\|D_2\|}{\|D\|}Gini(D_2)\$

度量数据集D在经过A=a 分割后的数据集D的不确定性 （和条件熵类似）

]
???
CART分类树和回归树的训练算法的区别主要在于选择特征和选择划分策略不同，首先对于分类树，引入一个概念叫数据集的Gini指数
Gini指数和熵类似，都是用来度量数据集的不确定性，即不确定性越高，gini指数越大

类似地，还有数据集D在经过特征A=a分割后的条件Gini指数，和经验熵类似，将数据D按照特征A是否取某个值a来划分，分割成两个子数据集D1和D2
那么条件基尼指数的定义就是：

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### 分类树生成算法

输入： 训练数据集D，停止计算条件

输出： CART分类树

根据训练数据集，从根节点开始，递归地对每个节点进行以下操作，构建二叉决策树

1. 对现有的每一个特征A，每一个可能的取值a，都将数据集D分割成D1和D2两部分，计算A=a时的基尼指数。

2. 在所有可能的特征以及它们所有可能得切分点中，选择条件基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点。根据这个特征和切分点生成两个子节点，并将训练数据集
分配到这两个子节点中去。

3. 递归调用，直到满足停止条件。

]
???
因此，完成的分类树生成算法就是这样的，

首先输入是：

输出是一颗CART分类树

....

....这里的条件基尼指数最小就等价于之前的信息增益值最大

....

这里的停止条件一般有这么几种：节点中的样本个数小于预定的阈值，样本集的基尼指数小于预定的阈值，或者没有更多可供选择、划分的特征了

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### 回归树

- 回归树适用于那些输入和输出都是连续变量的回归问题

- 生成一颗树模型，将输入空间划分成M个子单元\$R_1,R_2,..., R_m\$，每个子单元上有个固定的输出值\$c_m\$
  因此，回归树的模型可以用数学语言表示成：

$$ f(x) = \sum_{m=1}^{M}c_mI(x \in R_m) $$

.left[
<img src="/public/fig/dt5.png" width="350" height="300"> 
]

.right[
<img src="/public/fig/dt6.png" width="400" height="300">
]

]
???
CART回归树顾名思义他是用来解决那些输入输出是连续变量的回归问题

回归树在模型上除了是一颗这样的树之外，还可以看成是对原来特征的输入空间的一种划分。比如这颗树有四个叶子节点，
其实就等价于这个对原来的输入空间划分为4个子单元，每个子单元上有一个固定的输出值，因此
回归树可以用数学语言更简洁的刻画成一个决策函数

所以回归树模型的生成面临两个问题：第一（和分类树一样）怎么划分特征空间 
第二，划分好后怎么决定每个子单元上的输出值，也就是每个子单元上这个Cm值

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### 怎么决定每个子单元上的输出值
  - 假设特征空间的划分确定，使用平方误差来表示这颗回归树对训练数据的预测误差：
    $$ Cost(T) = \sum_{x_i \in R_m} (y_i - f(x_i))^2 $$

最小化Cost(T) 得到： \$ c_m = ave(y_i | x_i \in R_m) \$

### 怎么来划分特征空间
  - 启发式方法：每次选择使得平方误差最小的划分方式，递归进行

- 假设选择第j个特征\$x^j\$和它的取值s，作为切分特征和切分点，那么可以将原来的特征空间划分成两个子区域：

$$ R_1(j,s) = \\{x|x^{j} <= s\\},  R_2(j,s) = \\{x|x^{j} > s\\}$$

在\$R_1\$上输出为\$c_1\$，\$R_2\$上输出为\$c_2\$

]
???
先回答第二个问题，就是假设特征划分空间确定后，怎么来最优化每个子空间是输入出值，

套路很常见，先定义回归树对训练数据的预测误差的代价函数，这里采用的是均方误差来定义代价，
然后最小化这个代价函数，由于特征划分已经确定，这个函数中的未知变量就是 各个Cm值，拿他对代价函数求偏导 = 0
很容易推导出这个式子，Cm，即Cm的最优取值是对应子单元上所有样本的输出值得均值

再回到第一个问题，怎么来划分特征空间，同样这里采用的是启发式策略来进行递归生成回归树，
与分类树不同的地方在于，这里不再采用条件Gini指数或者熵来选择特征和划分，还是使用均方误差来定义这次划分的代价

假设我们选择第j个...

c1和c2由上面这个式子求出

---
.left-column[
  ## desicion tree
  ## algorithm
  ### - CART

]
.right-column[
### 怎么来划分特征空间

- 用平方误差来刻画这个划分的代价：

$$ min_{j,s} [min\ Cost(R_1) + min\ Cost(R_2)] $$

- 对于每个特征j，可以通过最小化平方误差可以求出最优的切分点，构成一个(j,s)对，遍历所有的特征
    得到当前特征空间的最优的切分变量和最优切分点，选择这个划分将当前特征空间一分为二

- 对每个子特征空间递归上述过程，直到满足停止条件，得到一颗最小二乘回归树

]
???
现在我们选择最优特征和最优划分点就是最小化这个代价，对个每个特征j，可以通过最小化这个式子求出最优划分点，构成一个特征和
和其最优划分的j,s对，遍历所有特征就得到当前特征空间中的的最优特征和最优切分点，选择这个划分将当前特征空间一分为二

再去递归上述过程，直达满足停止条件，就生成了一颗最小二乘回归树

---
class: center, middle, inverse

# spark中的决策树

https://spark.apache.org/docs/latest/mllib-decision-tree.html

???

---
class: center, middle, inverse

# 总结

???

最后简单总结下今天的内容。
今天的分享都是围绕着机器学习三要素：模型、策略+算法。以决策树作为展开。介绍了多叉树和二叉树两者决策树模型，信息增益、gini指数、均方误差等几种
决策树特征选择策略、以及决策树的启发式生成算法。最后以spark中的决策树为例介绍了决策树模型的使用

希望大家有所收获、谢谢

献给DW.