当一个数学家走进一片树林中......

话说有个数学家走进一片森林中，先看到一棵树，然后看到一片树，再看到一排树，最后看到草丛中的蜘蛛网。而在他的思维中却涌现了四个词：决策树、随机森林、梯度下降树、神经网络。本文将简单介绍这四个算法的原理和其优缺点等。

决策树：

决策树的生成算法有ID3, C4.5和CART等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。决策树是一种贪心算法策略，只考虑当前数据特征的最好分割方式，不能回溯操作。

纯度的定义：

度量随机变量的不确定性，因此我们引入熵、基尼系数这两个概念。以下为熵的公式：

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

（1）ID3算法：划分前样本集合D的熵是一定的 ，entroy(前)，使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy(后)，公式如下：

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

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

信息增益的理解：

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

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

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

（2）C4.5算法：为了解决ID3算法的缺陷我们在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。公式如下：

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

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

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

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

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

（3）CART算法：

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

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

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

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

决策树构建有以下三步骤：

1.将所有的特征看成一个一个的节点

2.遍历所有特征,遍历到其中某一个特征时：遍历当前特征的所有分割方式，找到最好的分割点,将数据划分为不同的子节点，计算划分后子节点的纯度信息

3.在遍历的所有特征中，比较寻找最优的特征以及最优特征的最优划分方式，纯度越高,则对当前数据集进行分割操作

4.对新的子节点继续执行2-3步，直到每个最终的子节点都足够纯

决策树算法构建的停止条件：
1.当子节点中只有一种类型的时候停止构建（条件苛刻可能产生过拟合）
2.当前节点种样本数小于某个值，同时迭代次数达到指定值，停止构建，此时使用该节点中出现最多的类别样本数据作为对应值（常用）

随机森林：

以上所说的决策树是一颗树的构建算法，而随机森林是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

随机森林采样方式：分为行采样和列采样

（1）行采样使用使用bagging中的Bootstrap aggregating方法。采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。

（2）列采样从M个feature中，选择m个(m

特点如下：