Decision Tree决策树

先来看个例子
一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。本质上来讲，决策树就是基于已知数据中总结出来的一组分类规则。

可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法，下面介绍决策树的构造算法。

问题描述

从给定的训练数据集中，依据特征选择的准则，递归的选择最优划分特征，并根据此特征将训练数据进行分割，使得各子数据集有一个最好的分类的过程。

• 输入：训练数据集 D = {(x₁,y₁),(x₂,y₂),..,(x_N,y_N)}

  x_i = (x_i⁽¹⁾,x_i⁽²⁾,...,x_i⁽ⁿ⁾)为输入实例（特征向量）
  n为特征个数
  y_i ∈ {1,2,...,K}为类标记
  N为样本容量

• 算法三要素：

  1. 特征选择 （准则：信息增益，信息增益率，基尼指数）
  2. 决策树生成 （ 使用满足划分准则的特征不断的将数据集划分为纯度更高，不确定性更小的子集的过程。）
  3. 决策树剪枝

• 输出：一组分类规则

• 损失函数：正则化的极大似然函数

• 学习策略：以损失函数为目标函数的最小化

特征选择准则：
目的：使用某特征对数据集划分之后，各数据子集的纯度要比划分前的数据集D的纯度高（不确定性要比划分前数据集D的不确定性低。）
注意：
1. 划分后的纯度为各数据子集的纯度的加和（子集占比×子集的经验熵）。
2. 度量划分前后的纯度变化用子集的纯度之和与划分前的数据集D的纯度进行对比。

特征选择的准则就是度量样本集合不确定性以及纯度的方法。本质相同，定义不同而已。

熵

熵就是用来度量随机变量的不确定性（纯度）。
定义：假设随机变量X的可能取值有x₁，x₂， ... , x_n
对于每一个可能的取值x_i，其概率 P(X=x_i) = pi , i = 1,2, ... , n。则，随机变量X的熵：

决策树构造

1.信息增益（ ID3算法 ）

定义： 以某特征划分数据集前后的熵的差值

在熵那部分提到了，熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

划分前样本集合D的熵是一定的 ，entroy(前)，
使用某个特征A划分数据集D，计算划分后的数据子集的熵entroy(后)
信息增益 = entroy(前) - entroy(后)
书中公式:

做法：计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

信息增益的理解：对于待划分的数据集D，其 entroy(前)是一定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因此 entroy(前) - entroy(后)差异越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

• 缺点：信息增益偏向取值较多的特征
• 原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。

2.信息增益比（ C4.5算法 ）

信息增益比 = 惩罚参数 * 信息增益
书中公式：

注意：其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。
（之前是把集合类别作为随机变量，现在把某个特征作为随机变量，按照此特征的特征取值对集合D进行划分，计算熵H_A(D)）

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）

• 缺点：信息增益比偏向取值较少的特征
• 原因： 当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
• 使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

3.基尼指数（ CART算法 ---分类树）

基尼指数（Gini不纯度）表示在样本集合中一个随机选中的样本被分错的概率。

注意：Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

书中公式：

样本集合D的Gini指数 ： 假设集合中有K个类别，则：

基于特征A划分样本集合D之后的基尼指数：

需要注意：CART是个二叉树，也就是当使用某个特征划分样本集合只有两个集合：1. 等于给定的特征值 的样本集合D1 ， 2 不等于给定的特征值 的样本集合D2

实际上是对拥有多个取值的特征的二值处理。

举个例子，假设现在有特征 “学历”，此特征有三个特征取值： “本科”，“硕士”， “博士”，当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：

• 划分点： “本科”，划分后的子集合 ： {本科}，{硕士，博士}
• 划分点： “硕士”，划分后的子集合 ： {硕士}，{本科，博士}
• 划分点： “博士”，划分后的子集合 ： {博士}，{本科，硕士}

对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：

因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)

然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。

剪枝

在实际构造决策树时，通常要进行剪枝，这时为了处理由于数据中的噪声和离群点导致的过分拟合问题，即减少决策树模型的复杂度。

剪枝有两种：

• 先剪枝——在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。
• 后剪枝——先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。