笔者介绍

曾担任零售企业项目负责人，负责企业数据化转型，数据化管理；曾服务中国移动，负责客服部门产品推荐模型组组长；现于某金融投资公司大数据中心，负责风控数据建设，风控建模工作。在除工作外，也喜欢在DC、DF、天池、Kaggle参加一些比赛。机器学习方面，有一定经验，愿与各位分享我的所见所闻所想，与各位共同进步。

什么是决策树？

决策树，是一种基于特征的模型，常用的决策树有ID3、C4.5、CART，可以用来做分类也可以用来做回归，和之前将的岭回归，Lasso回归，逻辑回归不同的是，决策树是基于特征的。怎么理解呢？

回归是通过一定的方法（最小二乘法，梯度下降法等），变量需要是连续型，通过拟合变量权重求解。

决策树是基于离散分类节点，进行决策判断构建的，所以做决策树之前就需要把连续变量离散化。也是基于此决策树不用拟合变量权重，也不用考虑多重共线性。

决策树

决策树怎么构建？

当我们构建决策树模型时，只需要考虑三个步骤：

1.特征处理；因为决策树是基于离散变量的，所以通常情况下需要将连续变量进行离散化，离散化的操作可以考虑分箱的方法，如等频分箱，等宽分箱，卡方分箱等；（分箱既分类，比如年龄，0-18：少年，18-30：青年，30-50：中年，>50：老年，关于分箱后续也会有专题分享）

2.特征选择；将特征分好类之后，需要选择特征，到底哪些特征应该优先决策，比如医生想确定这个人的症状，需要先问哪里痛？绞痛还是阵痛？特征选择一般有信息熵、信息增益、Gini系数。这些都是贪婪算法，贪婪是指他们会找当前选择下的最佳决策点，无法考虑这个决策点对于整体来说是不是最佳的决策点。

所以决策树的结果，可能是相对好的结果，但是可能不是最佳结果。

3.决策生成；基于之前的决策点生成决策树；

4.决策剪枝；如果特征足够多，决策树可能会无限衍生下去，但是当决策枝叶太长，可能会导致过拟合的情况，所以需要进行剪枝来修正结果。包括：

①.预剪枝，通过提前停止树的构建而对树剪枝，一旦停止，节点就是树叶，该树叶持有子集元祖最频繁的类。

停止决策树生长最简单的方法有：

a.定义一个高度，当决策树达到该高度时就停止决策树的生长

b.达到某个节点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这个方法对于处理数据冲突问题比较有效。

c.定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长

d.定义一个阈值，当达到某个节点的实例占比小于阈值时，就可以停止决策树的生长

e.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。

②.后剪枝方法，它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。

决策树的优缺点？

优点：

决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。

对于决策树，数据的准备往往是简单或者是不必要的。其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。

能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一

决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。

易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。

在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

可以对有许多属性的数据集构造决策树。

决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。

缺点：

对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。

决策树处理缺失数据时的困难。

过度拟合问题的出现。

忽略数据集中属性之间的相关性。

特征选择？

决策树的特征选择主要有信息增益、信息增益比、基尼指数。

信息增益（ ID3算法 ）

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

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

划分前样本集合D的熵是一定的 ，entroy(前)，使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy(后)

信息增益 = entroy(前) – entroy(后)

公式:

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

信息增益的理解：

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

缺点：信息增益偏向取值较多的特征

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

解决方法 : 信息增益比（ C4.5算法 ）

信息增益比 = 惩罚参数 * 信息增益

公式：

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

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）

缺点：信息增益比偏向取值较少的特征

原因： 当特征取值较少时H_A(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

基尼指数（ CART算法 —分类树）

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

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

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

公式：

说明:

1. p_k表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-p_k)

2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和

3. 当为二分类是，Gini(P) = 2p(1-p)

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

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

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

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

举个例子：

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

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

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

因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,A_i)，(其中A_i 表示特征A的可能取值)然后从所有的可能划分的Gini(D,A_i)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。

信息增益部分借鉴了：https://www.cnblogs.com/muzixi/p/6566803.html