随机森林
决策树
随机森林算法是机器学习、计算机视觉等领域内应用极为广泛的一个算法，它不仅可以用来做分类，也可用来做回归即预测，随机森林机由多个决策树构成，相比于单个决策树算法，它分类、预测效果更好，不容易出现过度拟合的情况。
图1 具体例子
决策树的含义：
决策树是数据挖掘与机器学习领域中一种非常重要的分类器，算法通过训练数据来构建一棵用于分类的树，从而对未知数剧进行高校分类。
决策树的构建步骤：
- 将所有记录看作是一个节点
- 遍历每个记录的分割方式，找到最好的分割点
- 利用分割点将记录分割成两个子节点C1和C2
- 对子结点C1和C2重复执行步骤2. 3. 直到满足特定条件为止。
分割点：
寻找好的分割点是通过量化分割后类的纯度来确定的，目前有三种纯度计算方式，分别是Gini不纯度、熵（Entropy)及错误率，它们的公式定义为：(1)、
(2)、
(3)。公式中的P(i)表示记录中第i类记录数占总记录数的比例。上面的三个公式均是值越大表示越"不纯"，值越小表示越"纯"。最常用的是Gini不纯度公式。
互信息（信息增益）：
指的是两个随机变量之间的关联程度，即给定一个随机变量后，另一个随机变量不确定性的削弱程度，因而互信息取值最小为0，意味着给定一个随机变量对确定另一个随机变量没有关系。取值最大，意味着给定一个随机变量，能完全消除另一个随机变量的不确定性。
对于步骤1中特征的选择（ID3）：
- 假设约会去或不去的事件为Y，其信息熵为H(Y);
- 假设给定特征的条件下，其条件信息熵为H(Y|长相)，H(Y|收入)，H(Y|身高)
- 分别计算信息增益：G(Y,长相)=I(Y|长相)=H(Y)-H(Y|长相)、G(Y,收入)=I(Y|收入)=H(Y)-H(Y|收入)
- 选择信息增益最大的特征作为分类特征，因为增益信息大的特征意味着给定这个特征，能很大的消除去约会还是不约会的不确定性。
- 迭代选择特征即可。
决策树的优点：
- 决策树模型可读性好，具有描述性，有助于人工分析
- 效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
决策树的缺点：
- 决策树很容易导致过度拟合（overfitting），因此在实际应用中需要设定停止条件，当达到停止条件时，直接停止决策树的构建。但这仍然不能完全解决过度拟合问题，过度拟合的经典表现是决策树对训练数据错误率很低，而对测试数据其错误率却非常高。
- 过度拟合原因：（1）训练数据中存在噪声；（2）数据不具有代表性。过度拟合的经典表现是决策树的节点过多，因此实际中常常需要对构建好的决策树进行枝叶剪裁（Prune Tree）,但它不能解决根本问题，随机森林算法的出现能够较好地解决过度拟合问题。
随机森林
通过构建大量的决策树组成森林来防止过拟合；虽然单个树可能存在过拟合，但通过广度的增加就会消除过拟合现象。由多个决策树构成的森林，算法分类结果由这些决策树投票得到，决策树在生成的过程中分别在行方向和列方向上添加随机过程，行方向上构建决策树时采用放回抽样（bootstraping）得到训练数据，列方向上采用无放回随机抽样得到特征子集，并据此得到其最优切分点，这便是随机森林算法的基本原理。
随机森林在bagging的基础上更进一步：
- 样本的随机：从样本集中用Bootstrap随机选择n个样本
- 特征的随机：从所有属性中随机选择K个属性，选择最佳分割属性作为节点建立CART决策树（泛化的理解，这里面也可以是其他类型的分类器，比如SVM、Logistics）
- 重复以上两步m次，即建立了m颗CART决策树
- 这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类
图2： 随机森林算法示意图
关于调参：
- 如何选取K, 可以考虑有N个属性，取
- 最大深度，不超过8层
- 颗数
- 最小分裂样本数
- 类别比例
随机森林的优点：
- 在数据集上表现良好
- 在当前的很多数据集上，相对其他算法有很强的优势
- 它能够处理很高维度（feature）很多的数据，并且不用做特征选择
- 在训练完成后，它能够给出哪些feature比较重要
- 训练速度快
- 在训练过程中，能够检测到feature间的互相影响
- 实现比较简单
- 随机森林在对数据进行分类的同时，还可以给出各个变量（基因）的重要性评分，评估各个变量在分类中所起的作用。