1 前言

在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？

树形模型是一个一个特征进行处理，之前线性模型是所有特征给予权重相加得到一个新的值。

决策树与逻辑回归的分类区别也在于此。

逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割（输入特征x与logit之间是线性的，除非对x进行多维映射），而决策树可以找到非线性分割。

树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性。树模型拟合出来的函数其实是分区间的阶梯函数。

2 决策树

决策树（decision tree）是一种基本的分类与回归方法，此处主要讨论分类的决策树。决策树是一种十分常用的分类方法，属于有监督学习（Supervised Learning）。所谓有监督学习，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

相亲决策树：树中每一个非叶节点表示一个决策，叶节点是该元组的分类结果。

决策树是一种树形结构，它主要有三种不同的节点：

决策节点：它表示的是一个中间过程，主要是用来与一个数据集中各个属性的取值作对比，以此来判断下一步的决策走向趋势。

状态节点：代表备选方案的期望值，通过各个状态节点的对比，可以选出最佳的结果。

结果节点：它代表的是该类最终属于哪一个类别，同时也可以很清晰的看出该模型总共有多少个类别。

最终，一个数据实例根据各个属性的取值来得到它的决策节点。

2.1 决策树算法

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。

比较常用的决策树算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。

特征选择。特征选择的目的是选取能够对训练集分类的特征。 决策树一种理解，实际上是寻找最纯净的划分方法，这个最纯净在数学上叫纯度（纯度通俗点理解就是目标变量要分得足够开）。另一种理解是分类误差率的一种衡量。实际决策树算法往往用到的是，纯度的另一面也即不纯度，下面是不纯度的公式。不纯度的选取有多种方法，每种方法也就形成了不同的决策树方法，比如ID3算法使用信息增益作为不纯度；C4.5算法使用信息增益率作为不纯度；CART算法使用基尼系数作为不纯度。 特征选择的关键是准则：信息增益、信息增益率/比、Gini 指数（基尼系数）；

决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；

决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。

样本数量，特征数量上面，一开始需要注意的：

当样本数量少但是样本特征非常多的时候，决策树很容易过拟合，一般来说，样本数比特征数多一些会比较容易建立健壮的模型。

如果样本数量少但是样本特征非常多，在拟合决策树模型前，推荐先做维度规约，比如主成分分析（PCA），特征选择（Losso）或者独立成分分析（ICA）。这样特征的维度会大大减小，再来拟合决策树模型效果会好。

推荐多用决策树的可视化，同时先限制决策树的深度，这样可以先观察下生成的决策树里数据的初步拟合情况，然后再决定是否要增加深度。

在训练模型时，注意观察样本的类别情况（主要指分类树），如果类别分布非常不均匀，就要考虑用class_weight来限制模型过于偏向样本多的类别。

2.2 信息论相关内容

克劳德·艾尔伍德·香农（Claude Elwood Shannon 1916年4月30日-2001年2月24日）美国数学家 信息论创始人  

香农提出的三个概念

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。

什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。

训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：

经验熵(empirical entropy)

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

条件熵(conditional entropy) 其中，pi=P(X=xi)

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0。

信息增益

信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

信息增益（互信息）

一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比

特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比，即

信息增益比

Gini 指数

Gini不纯度是对分类结果好坏的度量标准，表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。公式在下面红框中。

三种算法选择特征的数学公式

举例计算Gini指数（不纯度）

数据集

先通过城市是否拥有房产这条特征，把这10个人划分为2类

这个分类结果明显并不是很好，因为它没有将见面与不见面完全的分开，在算法中，当然不能凭我们的“感觉”去评价分类结果的好坏。我们需要用一个数去表示。（具体数值代入上面的基尼指数计算公式）

对于上述的结果来讲，总的集合D被分为两个集合D1，D2，假设见面为1，不见面为0。

那么D1的不纯度为1-f1^2-f0^2，总数为5，见面的占了全部，则f1=1，f0=0，结果为0。

D2的不纯度为1-f1^2-f0^2，f1=0.8，f0=0.2，结果为0.32。

那么整个分类结果的Gini不纯度就是D1/D与0的乘积 加上 D2/D与0.32的乘积，为0.16。

Gini值代表了某一个分类结果的“纯度”，我们希望结果的纯度很高，这样就不需要对这一结果进行处理了。

从以上分析可以看出，Gini值越小，纯度越高，结果越好。

信息增益 vs 信息增益比

之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

Gini 指数 vs 熵

既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？

Gini 指数的计算不需要对数运算，更加高效；

Gini 指数更偏向于连续属性，熵更偏向于离散属性。

2.3 ID3算法

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。

具体方法是：

1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。

2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；

3）最后得到一个决策树。

ID3相当于用极大似然法进行概率模型的选择。

2.4 C4.5算法

与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。

2.5 CART算法

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

2.6 ID3、C4.5、CART的区别

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

2.7 决策树的剪枝

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。

剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。

实现方式：极小化决策树整体的损失函数或代价函数来实现

决策树学习的损失函数定义为：

https://www.cnblogs.com/ooon/p/5647309.html

3 随机森林

鉴于决策树容易过拟合的缺点，随机森林采用多个决策树的投票机制来改善决策树，我们假设随机森林使用了m棵决策树，那么就需要产生m个一定数量的样本集来训练每一棵树，如果用全样本去训练m棵决策树显然是不可取的，全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的。

产生n个样本的方法采用Bootstraping法，这是一种有放回的抽样方法，产生n个样本。

而最终结果采用Bagging的策略来获得，即多数投票机制。

随机森林的生成方法：

1.从样本集中通过重采样的方式产生n个样本

2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点

3.重复m次，产生m棵决策树

4.多数投票机制来进行预测

（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）

随机森林是一个比较优秀的模型，在我的项目的使用效果上来看，它对于多维特征的数据集分类有很高的效率，还可以做特征重要性的选择。运行效率和准确率较高，实现起来也比较简单。但是在数据噪音比较大的情况下会过拟合，过拟合的缺点对于随机森林来说还是较为致命的。

4 参考

机器学习实战（三）——决策树 https://blog.csdn.net/jiaoyangwm/article/details/79525237