决策树和Random Forests：优秀的群体智慧

What is Decision Tree:

说起决策树，就好像是一个ML算法的标配一样，在每本ML的教程里，每个ML的代码库里，每个ML的软件包里，都有决策树的存在。个人认为决策树是一种人类本能的规则判别的算法表达，当我们遇到一个分类问题时，本能的会以一些IF-THEN规则去划分，这是本质的关联和分类的思维在起作用。比如我们在做决策时总会找一些阈值x，大于x该怎么做，小于x又该怎么做。或者我们换句话说，决策树是一种归纳推理的典型，而我们数学推理的模式无非是归纳和演绎。

决策树分类是希望通过数据集中各个属性的特点，归纳得到一组规则作为分类条件，而这些规则是通过一棵树来展现的，每个节点都是一个规则，得到规则后在遇到新的数据实例时，只要从树根按照顺序遍历树，评估每个节点的规则条件，最后到达叶子时就得到了决策。我们就拿Quinlan论文中的例子来讲什么是决策树。下面的表是一个训练数据集，其中表示了每天的一个天气状况（有4个特征维度：forecast, temperature, humidity, windy），而需要给出的决策结论(class)是当天是否要play tennis。而下面的图就是决策树。

其实稍加推断，不难发现，根据训练集去构建决策树，树的数目是不唯一的，甚至是无限多的（当然前提是数据集足够充分），比如上面就有两棵决策树，它们都是正确的，但是从复杂程度上来看有了区分。但是我们构建分类器的目的是要尽可能的具备优秀的泛化能力，即除了对训练数据集有好的效果，对于未知数据的分类要准确这才是我们想要的结果。基于此，我们构建决策树不是随便的，我们倾向于更简单的树，更简单的规则来分类数据，因为这样明显具有更好的泛化能力（显而易见）。具体如何构建呢？决策树算法有成千上万种，paper也遍地都是，但是ID3算法是构建决策树的最经典的算法之一，也是Quinlan的经典作。

ID3是一个迭代的算法，自顶向下构建决策树，步骤可以分作3步：

1. 在所有没有选定的属性中，计算每个属性的信息增益

1. 选择信息增益最大的特征作为节点

1. 对于选定的节点特征，选择其所有的可能取值作为子节点，重复步骤a，直到叶子节点的熵为0或者属性节点全部被计算过

直白的解释是，构建树嘛，就要不断的选好节点和子节点咯，选的规则嘛，很简单——信息增益，为啥是信息增益？信息增益怎么算？这要引出一段故事了：

熵是信息论中广泛使用的度量标准，表述的是数据集的纯度，在信息论中的解释是对信息编码的最少二进制位数。

以上面的数据集为例，14个数据实例的样本集S，有9个P，5个N，所以它p(class:P)=9/14，p(class:N)=5/14，在class上的熵为-(9/14)log2(9/14)-(5/14)log2(5/14)=0.94。熵值在0~1之间分布，熵越小说明数据集越纯。因为分类树的目的是找到规则属性来尽量的划分不同类别，那么也就是说如果能找到一个属性来划分数据集从而使期望的熵最小，则这个节点的属性就是好的，表示这个属性的这种程度被定义为信息增益（information gain）

Values(Windy)=True, False

S = [9 P, 5 N]

=[3 P, 3 N] 

=[6 P, 2 N] 

同样的道理我们计算所有的属性的信息增益得到

Gain(S,Outlook)=0.246, Gain(S,Humidity)=0.151, Gain(S,Temprature)=0.029

属性Outlook具有最大信息增益，所以第一个节点就选Outlook，而剩下的过程照此迭代，于是得到了最后的决策树就如上面图片中较简单的树形。当然作为衡量属性优劣的度量标准除了信息增益外还有增益比率（gain ratio）和基尼指数（gini index）等。

决策树的分支条件除了上述的方法，还有通过做转移函数来进行斜分的和基于最近邻的图的方式，具体几种划分的几何表示见下图。我们一般的划分数据方法也是采用第一种。

决策树学习算法包含了3个部分：特征选择、树构建和剪枝，特征选择可以帮助我们构建更简单有效的树，这个过程其实在很多的机器学习算法中都必不可少，正如Quinlan在论文中提到的噪音问题和丢失值问题，这些都会影响树的构建。而树构建由上面介绍的ID3算法可知是一个启发式搜索过程，如果采用暴力的做法，那么构建决策树是一个需要搜索出所有可能的树然后选择最优的问题，这是NP的，所以全局最优的结论是无法做到的，只能通过像ID3这样找到合适的启发准则（信息增益）来做局部最优搜索（贪心搜索）。顺序搜索带来的问题就是过拟合和局部最优性，我们对于一个训练集进行ID3算法，很难找到一个泛化能力强的树形model，所以这也顺其自然的引出了剪枝的过程。剪枝就是把一些不重要的分支砍掉从而达到简化model的目的，同时这也满足决策树在归纳偏置上的倾向——简单胜于复杂。剪枝可以看做是构建的一个逆过程，自底向上的剔除不“合格”的分支，而“合格”的定义取决于代价函数，代价函数定义为

如果把代价函数的第一项表示为

那么最后的代价函数形式为

这里C(T)表示预测误差，|T|表示模型的复杂度。剪枝的算法描述如下：

1. 计算节点的经验熵
2. 
3. 重复步骤b直到得到最小子树。

经过剪枝的决策树将原有的可能过拟合和有点复杂的树缩减到一棵简单树，完成了模型的泛化。

在应用ID3决策树时需要考虑的问题还有很多，比如缺失值、噪声数据、数据属性要求是nominal或者是enum等等，而Quinlan后面的C4.5算法作为ID3的升级版优化解决了部分问题，比如对于特征属性已经可以兼容连续数值型属性，使用信息增益比率来代替信息增益作为度量标准等等。因为决策树是随机森林的基础，所以特地结合教科书和Quinlan的paper做一个简单介绍，由于发展历史较为悠久，所以变种的决策树多如牛毛，决策树算法的各个阶段都有非常多的paper改进，包括各种剪枝方法理论、树的大数据挑战和可视化等等，感兴趣的话自行查阅搜索，后面可能会单独介绍CART和C4.5这两种树的算法并对比ID3,C4.5和CART。

What is Random Forests:

随机森林是一个组合分类的方法，和bagging和boosting一样都非常常用，组合分类的思想就是将k个学习模型组合在一起，从而创建一个复合分类模型，最后通过投票来决定分类决策。随机森林的一个通俗解释就是：由一组决策树构建的复合分类器，它的特点是每个决策树在样本域里使用随机的特征属性进行分类划分。最后分类时投票每棵分类树的结论取最高票为最终分类结论。

如上所述，如果我们理解随机森林是一组决策树构成的，那么我们需要首先找到构建决策树的方法，同时我们也需要一个判别函数去将各个决策树的分类结果汇总起来并且能保证他们的准确度。首先，如何构建这些决策树呢，显然不能用同样的数据集和同样的特征向量，否则构建n个决策树和构建一个是等价的。那么随机化如何呢？随机化是ML的一个很重要的方法，也是一个很有用的工具，例如交叉验证、随机抽样等等。一种方法来构建决策树就是随机的选择n个特征子集来训练n个决策树，那如上所说，树构建好后需要判别函数来把结果整合，定义判别函数之前我们先看一个后验概率

随机森林是集体智慧的象征，通过随机分配一些特征向量来各自学习最后选举结果，准确率据说可以媲美AdaBoost，且对错误和利群点更鲁棒，通过调整森林中树的个数可以使泛化误差收敛，解决过拟合问题。同时调整个体树的属性选择可以提高准确率，通常的选择方法是log2d+1个属性。