【机器学习】决策树算法原理详解

决策树

1 概述

1.1 定义

决策树是一种解决分类问题的算法，决策树算法采用树形结构，使用层层推理来实现最终的分类。

决策树即可以做分类，也可以做回归。它主要分为两种：分类树 和 回归树。

1.2 决策树算法

第一个决策树算法: CLS （Concept Learning System）
使决策树受到关注、成为机器学习主流技术的算法: ID3
最常用的决策树算法: C4.5
可以用于回归任务的决策树算法: CART （Classification and Regression Tree）
基于决策树的最强大算法: RF （Random Forest）

1.3 结构

决策树由下面几种元素构成：

根节点：包含样本的全集（全部训练数据）
内部节点：对应特征属性测试
叶节点：代表决策的结果

在这里插入图片描述

决策树学习的目的是为了产生一棵泛化能力强的决策树

2 决策树构建

2.1 构建过程

整体策略：自上而下分而治之

决策树的构建过程就是一个自根至叶的递归过程，在每个中间结点寻找一个划分属性。

大致过程：

开始：构建根节点，所有训练数据都放在根节点，选择x个最优特征，按着这一特征将训练数据集分割成子集，进入子节点。
所有子集按内部节点的属性递归地进行分割。
如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

递归的三种停止条件：

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

2.2 特征选择

信息熵：随机变量的不确定性。
$\sum p_i log_2 p_i \hspace{2em} \text{i = 1, 2, ..., n}$

例：

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

B集合 $[1, 2, 3, 4, 5, 6, 7, 8, 9, 1]$

A集合熵值低于B集合熵值，因为A集合中只有两种类别，B集合中类别比较多（结构比较乱），熵值就会比较大

信息增益： 表示特征X使得类Y的不确定性减少的程度（熵值减少），即当前划分对信息熵所造成的变化。

信息增益越大，表示特征a来划分所减少的熵最大，即提升最大，应当作为根节点。

3 决策树算法

3.1 ID3（信息增益）

下面是基于信息增益的ID3算法的实例：

我们有14天的数据，4个特征条件：天气，温度，湿度，是否有风。最终结果是去玩不玩。

在这里插入图片描述

上面有四种划分方式，我们需要判断谁来当根节点，根据的主要就是信息增益这个指标。下面计算信息增益来判断根节点。

本例暂且以ent(a, b)代表以下含义：（只有两种结果的时候的熵值计算）

from math import log2
def ent(a, b):tot = a + bx, y = a / tot, b / totreturn -(x * log2(x) + y * log2(y))

总的数据中，9天玩，5天不玩，熵值为：
$-\frac{9}{14}log_2 \frac{9}{14} - \frac{5}{14}log_2 \frac{5}{14} = 0.940$
然后对4个特征逐个分析：

outlook
- outlook = sunny时，熵值为0.971，取值为sunny的概率为 $\frac{5}{14}$
- outlook = overcast时，熵值为0，取值为overcast的概率为 $\frac{4}{14}$
- outlook = rainy时，熵值为0.971，取值为rainy的概率为 $\frac{5}{14}$
熵值为：
$\frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971 = 0.693$
信息增益：系统熵值从0.940下降到0.693，增益为0.247。
temperture
- temperture = hot时，熵值为1.0（ent(2, 2)），取值为hot的概率为 $\frac{4}{14}$
- temperture = mild时，熵值为0.918（ent(4, 2)），取值为mild的概率为 $\frac{6}{14}$
- temperture = cool时，熵值为0.81（ent(3,1)），取值为cool的概率为 $\frac{4}{14}$
熵值为：
$\frac{4}{14} \times 1.0 + \frac{6}{14} \times 0.918 + \frac{4}{14} \times 0.81 = 0.911$
信息增益： $G ain (S, t e m p er t u re) = 0.940 - 0.911 = 0.029$
其他特征按照相同方法来做得到：

$\\ Gain(S, Humidity)=0.151 \\ Gain(S, Wind)=0 .048 \\ Gain(S,Temperature)=0 .029$

计算出所有的信息增益之后，选择有最大的信息增益的特征作为根节点。

下面找Sunny分支的决策树划分：

总的熵值
$-\frac{2}{5} \times log_2(\frac{2}{5}) - \frac{3}{5}log_2(\frac{3}{5}) = 0.97$
以剩下的三个特征进行分析：

temperture
- temperture=hot，熵值为0，概率为 $\frac{2}{5}$
- temperture=mild，熵值为1.0，概率为 $\frac{2}{5}$
- temperture=cool，熵值为0，概率为 $\frac{1}{5}$
熵值为 $\frac{2}{5}$

信息增益： $0.97 - 0.4 = 0.57$
humidy
- high，熵值为0，概率为 $\frac{3}{5}$
- normal，熵值为1，概率为 $\frac{2}{5}$
熵值为 $\frac{2}{5}$

信息增益： $0.97 - 0.4 = 0.57$
windy
- false，熵值为0.918，概率为 $\frac{3}{5}$
- true，熵值为1，概率为 $\frac{2}{5}$
熵值为 $0.951$

信息增益： $0.97 - 0.95 = 0.02$

故选择humidy或wind划分

剩下的划分同理，最终决策树为

在这里插入图片描述

3.2 C4.5（信息增益率）

基于信息增益的决策树算法会有哪些问题：

如果有一个特征：id，代表样本的编号，以上述数据为例，id为从1到14，如果计算id特征的根节点，发现信息增益是最大的，因为每一个子节点的信息熵值都为0。

信息增益率：（解决了ID3的问题，考虑自身熵，信息增益除以自身熵）
$\frac{G}{H(x)} \hspace{2em} \text{G:信息增益, H(x):熵值}$

3.3 CART（GINI系数）

使用基尼系数作为衡量标准。
$\sum \limits _{k = 1}^K p_k (1 - p_k) = 1 - \sum \limits _{k = 1}^K p_k^2$

3 决策树剪枝

3.1 预剪枝

在建立决策树边的时候进行剪枝的操作，比较使用实用。

剪枝策略：

限制深度
限制叶子结点个数
限制叶子结点样本数
限制信息增益量等。

3.2 后剪枝

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

4 连续值和缺失值处理

连续值属性可取数值不是有限的，不能根据连续树形的可取值对节点进行划分。常见做法是：二分法对其进行离散化。
现实应用中，经常会遇到属性值缺失现象仅使用无缺失的样例，这是对数据的极大浪费使用带缺失值的样例，需解决：
- 如何进行划分属性选择?
- 给定划分属性，若样本在该属性上的值缺失，如何进行划分?
基本思路：样本赋权，权重划分

集成算法

1 概述

集成算法：Ensemble Learning

Bagging：训练多个分类器取平均
$\frac{1}{M} \sum \limits_{m = 1}^M f_m(x)$
Boosting：从弱学习器开始加强，通过加权来训练。
$F_m(x) = F_{m - 1}(x) + argmin_h \sum \limits_{i = 1}^n L(y_i, F_{m - 1}(x_i) + h(x_i))$
Stacking：聚合多个分类或回归模型。