决策树 & 随机森林中的公式推导

决策树学习的生成算法主要有三种： * ID3 * Iterative Dichotomiser * C4.5 * CART * Classification And Regression Tree

决策树建立就是从特征中选择一个作为分类条件把样本划分为两个子集，然后对每个子集做同样的事情直到每个子集都属于相同的标签。所以建立决策树的关键在于每次划分子集的时候选择哪个特征，这也是上面三种算法的最主要区别，下面将一一探讨。

ID3

要了解ID3算法首先要了解一下信息增益等知识。该算法也可以参考我前面的文章：决策树之ID3算法详解。

信息熵

在信息论中，熵是接收的每条消息中包含的信息的平均量，又被稱為信息熵、信源熵、平均自信息量。这里，消息代表来自分布或数据流中的事件、样本或特征。（熵最好理解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大。）来自信源的另一个特征是样本的概率分布。这里的想法是，比较不可能发生的事情，当它发生了，会提供更多的信息。由于一些其他的原因（下面会有解释），把信息（熵）定义为概率分布的对数的相反数是有道理的。事件的概率分布和每个事件的信息量构成了一个随机变量，这个随机变量的均值（即期望）就是这个分布产生的信息量的平均值（即熵）。                      -- from WikiPedia

熵的公式定义为： \[H(X) = E[-\ln P(x)] = -\sum_i P(x_i)ln(P(x_i)) \]

熵的直观解释是对不确定性的度量，熵越大不确定性越大，熵越小不确定性越小。

\(H(X)\) 随 \(P(x_i)\) 变化的曲线为

设随机变量 \(X\) 只能取两个值 \(0\) 和 \(1\)，显然当取两个数的概率都为50%的时候不确定性最大，即熵最大为1；若取 \(0\) 或取 \(1\) 的概率为 100%，则事件完全确定，此时熵为0 。

条件熵

下面来讨论一下条件熵，它的定义式为：\(H(X, Y) - H(X)\)。

\((X,Y)\) 发生所包含的熵,减去 \(X\) 单独发生包含的熵： * 在 \(X\) 发生的前提下, \(Y\) 发生“新”带来的熵 * 该式子定义为 \(X\) 发生前提下, \(Y\) 的熵: * 条件熵 \(H(Y|X)\)

我们来推导一下这个式子等于什么。

\[\begin{array}{lcl} H(Y|X) = H(X, Y) - H(X) \\ = -\sum_{x, y}p(x, y) \ln p(x, y) + \sum_x p(x)\ln p(x) \\ = -\sum_{x, y}p(x, y) \ln p(x, y) + \sum_x\sum_y p(x, y) \ln p(x) \\ = - \sum_{x, y} p(x, y) (\ln p(x, y) - \ln p(x)) \\ = - \sum_{x, y} p(x, y) \ln\frac{p(x, y)}{p(x)} \\ = - \sum_{x, y} p(x, y) \ln p(y\ |\ x) \end{array}\]

继续推导我们可以得到：

\[\begin{array}{lcl} H(X, Y) - H(X) \\ = - \sum_{x, y} p(x, y) \ln p(y\ |\ x) \\ = -\sum_{x, y} p(x) p(y\ |\ x) \ln p(y\ |\ x) \\ = \sum_x p(x) (- \sum_y p(y\ |\ x) \ln p(y\ |\ x)) \\ = \sum_x p(x) H(Y\ |\ X = x) \\ = E[H(Y\ |\ X = x)] \end{array}\]

是熵的数学期望！

信息增益

• 信息增益表示得知特征 \(A\) 的信息而使得类 \(X\) 的信息的不确定性减少的程度。
• 经验熵：当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。
• 定义：特征 \(A\) 对训练数据集 \(D\) 的信息增益 \(g(D,A)\), 定义为集合 \(D\) 的经验熵 \(H(D)\) 与特征 \(A\) 给定条件下 \(D\) 的经验条件熵 \(H(D|A)\) 之差, 即:
  • \(g(D,A)=H(D)\ – H(D\ |\ A)\)

基本记号

• 设训练数据集为 \(D\) , \(|D|\) 表示样本个数。
• 设有 \(K\) 个类 \(C_k\) , \(k = 1, 2, ... K\) , \(C_k\) 为属于类 \(C_k\) 的样本个数, 有: $_k | C_k | = | D | $
• 设特征 \(A\) 有 \(n\) 个不同的取值 \(\{a_1, a_2, ... a_n\}\) ,根据特征 \(A\) 的取值将 \(D\) 划分为 \(n\) 个子集 \(D_1, D_2, ... D_n\) , 为 \(| D_i |\) 为 \(D_i\) 的样本个数，有：\(\sum_i |D_i| = |D|\)
• 记子集 \(D\) 中属于类 \(C\) 的样本的集合为 \(D_{ik}\) ，\(|D_{ik}|\) 为 \(D_{ik}\) 的样本个数。

ID3算法

1. 计算数据集 \(D\) 的经验熵 \(H(D) = -\sum_{k=1}^K \frac{|C_k|}{|D|} log\frac{|C_k|}{|D|}\)
2. 遍历所有特征, 对于特征 \(A\) :
   • 计算特征 \(A\) 对数据集 \(D\) 的经验条件熵 \(H(D\ |\ A)\)
   • 计算特征 \(A\) 的信息增益 : \(g(D,A)=H(D) – H(D\ |\ A)\)
   • 选择信息增益最大的特征作为当前的分裂特征

条件经验熵 \(H(D\ |\ A)\) 计算方法

\[\begin{array}{lcl} H(D\ |\ A) = H(D, A) - H(A) \\ = -\sum_{i,k} p(D_k, A_i) \log p(D_k, A_i) \\ = - \sum_{i=1}^n p(A_i) \sum_{k=1}^K p(D_k\ |\ A_i) \log p(D_k\ |\ A_i) \\ = - \sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|} \log \frac{|D_{ik}|}{|D_i|} \end{array}\]

以上就是 ID3 算法的核心内容。

但是ID3算法有一个问题，算法每次选择一个信息增益最大的特征进行子集划分，这样就会倾向于选择一些取值很多而且每个值对应的样本很少的特征，比如样本序号（如果你把它加入特征的话），若选择样本序号作为划分子集的特征，则可一次划分结束，所有子集都变为叶子节点，熵为零，但是这样分类并没有意义，因为它完全过拟合了而且没有任何预测能力。为了避免这种情况的发生，我们需要改进这种选择特征标准，于是就有了C4.5和CART。

C4.5

C4.5 对 ID3 的主要改进在于每次分割选择特征的标准，由信息增益换成了信息增益率。

信息增益率

定义式： \[g_r(D, A) = \frac{g(D, A)}{H(A)}\]

其中 \(H(A)\) 为选择特征 \(A\) 的熵，\(H(A) = -\sum_i p(A_i) \log p(A_i) = -\sum \frac{|D_i|}{|D|} \log \frac{|D_i|}{|D|}\)

CART

Classification And Regression Tree

CART 再次更换了选择特征标准，它采用Gini系数作为评判标准。

Gini 系数

定义式：

\[Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1 - \sum_{k=1}^Kp_k^2 ＝1 - \sum_{k=1}^K(\frac{|C_k|}{|D|})^2 \]

Gini系数看起来比较突兀，根据著名机器学习讲师邹博的观点，Gini系数实则是对信息增益的近似： * 将 \(f(x) = -\ln x\) 在 \(x = 1\) 处一阶展开，忽略高阶无穷小，得到 \(f(x) \approx 1 - x\) * $H(x) = -{k=1}^Kp_k p_k {k=1}^Kp_k(1 - p_k) = Gini(p) $ * Gini系数与熵的对比图如下：

三种决策树的学习算法

• ID3 : 使用信息增益/互信息 \(g(D,A)\) 进行特征选择
  • 取值多的属性,更容易使数据更纯 ,其信息增益更大。
  • 训练得到的是一棵庞大且深度浅的树 : 不合理。
• C4.5 : 信息增益率 \(g_r(D,A) = g(D,A) / H(A)\)
• CART : 基尼指数
• 一个属性的信息增益(率)/Gini指数越大, 表明属性对样本的熵减少的能力更强, 这个属性使得数据由不确定性变成确定性的能力越强。

决策树的评价

• 假定样本的总类别为 \(K\) 个
• 对于决策树的某叶结点,假定该叶结点含有样本数目为 \(n\) , 其中 第 \(k\) 类的样本点数目为 \(n_k\), \(k=1,2,...,K\)。
  • 若某类样本 \(n_j=n\) 而 \(n_1,...,n_{j-1},n_{j+1},...,n_K=0\), 称该结点为纯结点;
  • 若各类样本数目 \(n_1=n_2=...=n_k=n/K\), 称该样本为均结点。
• 纯结点的熵 \(H_p=0\), 最小
• 均结点的熵 \(H_u=\ln K\), 最大
• 对所有叶结点的熵求和, 该值越小说明对样本的分类越精确
  • 各叶结点包含的样本数目不同,可使用样本数加权求熵和
• 评价函数 :
  • \(C(T) = \sum_{t \in leaf} N_t \cdot H(t)\)
  • 由于该评价函数越小越好, 所以可以称之为“损失函数”。

剪枝

决策树对训练属于有很好的分类能力, 但对未知的测试数据未必有好的分类能力, 泛化能力弱, 即可能发生过拟合现象。

适当的剪枝可以防止过拟合现象，三种决策树的剪枝过程算法相同, 区别仅是对于当前树的评价标准不同。

剪枝总体思路

• 由完全树 \(T_0\) 开始,剪枝部分结点得到 \(T_1\), 再次剪枝部分结点得到\(T_2\)...直到仅剩树根的树 \(T_k\);
• 在验证数据集上对这 \(k\) 个树分别评价, 选择损失函数最小的树 \(T_α\)。

随机森林

Bagging

在谈随机森林之前先来看看 Bagging 的策略 * bootstrap aggregation * 从样本集中重采样(有重复的)选出 \(n\) 个样本 * 在所有属性上, 对这 \(n\) 个样本建立分类器 (ID3、C4.5、CART、SVM、Logistic回归等) * 重复以上两步 \(m\) 次, 即获得了 \(m\) 个分类器 * 将数据放在这 \(m\) 个分类器上,最后根据这 \(m\) 个分类器的投票结果, 决定数据属于哪一类

Bootstraping的名称来自成语“pull up by your own bootstraps”, 意思是依靠你自己的资源, 称为自助法, 它是一种有放回的抽样方法。

随机森林

随机森林就是在Bagging的基础上做了些修改： * 从样本中用 Bootstrap 采养出 \(n\) 个样本 * 从所有属性中随机选择 \(k\) 个属性，建立 CART 树 * 重复以上步骤 \(m\) 次，即建立了 \(m\) 棵 CART 树 * 这 \(m\) 个 CART 形成随机森林,通过投票表决结果，决定数据属于哪一类

当然可以使用决策树作为基本分类器，也可以使用SVM、Logistic回归等其他分类器, 习惯上, 这些分类器组成的“总分类器”, 仍然叫做随机森林。不过随机森林的思想是使用很多个弱分类器（受异常点影响较小）投票得出一个强分类器，所以把小树们换成SVM、LR等强分类器效果不一定会更好，反而可能会更容易受异常点影响（理论上）。

投票机制

投票机制一般有以下几种，少数服从多数用的比较多了： * 简单投票机制 * 一票否决 * 少数服从多数 * 有效多数（加权） * 阈值表决 * 贝叶斯投票机制 * Laplace平滑