决策树和随机森林

如果给定输入(x1, x2, x3, ...)来预测输出y属于哪一个分类。最容易想到的方案大概类似于下面的逻辑。

if {$x3 < 0.4} {
  set y "category-1"
} else {
  if {$1 < 0.2} {
     set y "category-2"
  } else {
    if { $2 < 0.7} {
      set y "category-3"
    } else {
      set y "category-4"
    }
  }
}

这样一组条件分支判断实际上就是一颗决策树。因为它从顶端向下看，像是一颗倒着长的树，每个条件判断的地方像是一个树杈。

     [$x3<0.4]
      /     \
(cat-1)    [$1<0.2]
            /    \
      (cat-2)   [$2<0.7]
                 /    \
           (cat-3)    (cat-4)

决策树可以根据人的经验总结得出——这被称为「专家系统」。

如果通过分析（学习）标注过的数据（训练数据)自动构建这样一颗决策树，那就是「机器学习」的方法之一。

随机森林（Random Forest）

通过「机器学习」得出的决策树在对新数据进行预测时不可避免地是有误差的。减小这种预测误差的方法，除了从提高单个决策树的准确性入手之外；还有一个思路是同时训练多个不同的决策树，从这些不同的决策树的预测结果中再综合得出一个最可能的结果来。这个就是随机森林的基本思想。

这有点像是「集体智慧」的意思。

决策树的学习训练

从上面决策树的描述，可以看出其关键点在于确定每个分叉处用哪个特征，和该特征的阈值是什么。

先假设我们每次随机选取某个特征作为该层的分类属性。接下来阈值的确定主要是最小化预测误差。这与线性回归（Regression）里的思想是类似的。

CART算法里面用最小化“不纯度”表示这种最小化预测误差。因为CART算法每次只是把结果划分为两类，其cost function可以表示为

J = m_left/m_total*G_left + m_right/m_total*G_right

其中：

• m_left + m_right = m_total 是左右分类中样本的数量
• G_left 和 G_right 是左右分类的不纯度

这里的不纯度（impurity）是表示预测误差的方法之一种。

假如当前节点中某个分类的样本数据在该节点中存在的比例（概率)是p，对应的它的纯度可以认为是p，不纯度是1-p。对所有k个分类的不纯度(1-p)按照比例p加权求和，获得当前节点的不纯度

G = sum(p_k*(1-p_k)) = 1-sum(p_k^2)

信息熵（entropy）是另一种方法。不纯度为0对应的是熵为0，不纯度增加，对应的是熵增加。因而可以借用熵的概念来表示不纯度。

G = - sum( p_k*log(p_k) )

集成学习（Ensemble Learning）

随机森林（Random Forest）实际上是一种特殊形式的集成学习（Ensemble Learning）——同时用多种模型进行预测然后综合得出最优的预测结果。

""" 如果一个硬币有51%的概率正面朝上，那么跑硬币1000次后，大多数是正面朝上的概率接近75%

类似地，假如用1000个各自独立的预测器进行预测，即使每个预测器的准确率只有51%，如果以这些预测器的结果中的多数作为结果，那么预测准确率也将接近75%

—— 引自《机器学习实战——基于Scikit-Learn和TensorFlow》 """

Ensemble Learning所要求的多个不同预测器可以通过两种基本思路来获得：

• 同样的训练数据，不同的训练方法
• 同样的训练方法，不同的训练数据

Bagging and Pasting

同样的训练方法，不同的训练数据，实践中是通过从训练数据中随机提取子集来实现的。

如果每次随机选取数据后，都把该数据样本放回去，被称为bagging；不放回去则叫做pasting。

换句话说，bagging方法里，同一个样本数据有可能被选中多次。

Bagging是bootstrap aggregating的简写。bootstrap在统计学中是放回重新采样的意思。

TODO