决策树

约定：

  • 红色：对名词进行解释的重点
  • 黄色：各部分总结中的重点
  • 绿色：算法基本假设与解释

摘要：

  1. 熵的概念详解（熵）
  2. 三种核心的决策树算法（信息增益与ID3、信息增益率与C4.5、GINI系数与CART）
  3. 工程优化总结和剪枝（工程优化总结，剪枝）

名词解释：树、ID3/C4.5/CART、熵、条件熵、信息增益、信息增益率、GINI系数、剪枝

  1. 树：一种数据结构，在决策树中利用这种数据结构可视化构建整个决策过程
  2. ID3/C4.5/CART：三种知名的决策树算法，分别基于信息增益、信息增益率和GINI系数作为特征排序的标准对于先验的修正，即$P(Y|X=xx)$
  3. 熵：信息论中的消息的平均量，决策树中借用以表达数据集中标签的分布的混乱程度
  4. 条件熵：给定一定的信息后熵的大小，和“后验概率”的思想有点像
  5. 信息增益：给定条件后（某一个特征的具体取值），熵的减小程度，ID3就通过这个指标进行特征选择，即找到信息增益最大的特征作为第一个特征，以此类推
  6. 信息增益率：解决信息增益倾向于找特征项最多的那个特征，所以给信息增益除以了特征项的个数，类似于调整R方和R方的关系。C4.5中基于这个指标进行特征排序
  7. GINI系数：解决信息增益率直接除以特征项个数可能不准，以及「熵」引入的对数计算的复杂度高的问题。GINI系数的本质是，从训练集中任选两个样本，其标签不同的概率，这个概率越大说明数据越混乱（和「熵」的判断过程类似，但出发点完全不一样）
  8. 剪枝：决策树考虑了所有特征，极其容易过拟合，所以需要一些工程化的操作防止过拟合。决策树中防止过拟合的常用手段就是「剪枝」

原理实现： 决策树的实现ID3、C4.5

零、熵

在开始决策树的部分之前，我决定先花一定篇幅将明白「熵」的概念，这是一个很熟悉但又有些陌生的概念（至少对于我来说），所以把第零章的内容祭奠给这个一直说不清道不明的概念。

0.0 “entropy”与“熵”

  1. entropy: 是一个自造词，最开始取自希腊语 “trope”意味转换（英文trans前缀的来源）克劳修斯（热力学熵的发明者）又添加了en（能量的前缀）和后缀（y）得到了“entropy”
  2. 熵：中文也是一个自造字，普朗克在中国讲学时（1923年），当时的翻译（胡刚复）用「火」表示能量，用「商」表示比值，创造了这个字

    0.1 熵概念的发展

  3. 热力学：1865年（克劳修斯）：克劳修斯用entropy的概念描述：在一个可逆过程里，被用在恒温的热的总数，$\Delta S=\frac{\Delta Q}{T}$\ 热量与温度的比值
  4. 统计力学：1877年（玻尔兹曼）：将熵和微观状态联系起来: $S=k(ln \Omega)$\ k: 玻尔兹曼常数，$\Omega$: 微观状态数量
  5. 信息论：1948年（香农）：每条消息中包含的信息量的平均: 对于离散事件：$信息熵 = \sum_{i}^{n}p_i * 信息量_i$\ 不确定性的度量

0.2 信息熵的公式

  1. 根据定义，信息熵是信息量的平均，在搞明白信息熵之前，先看一下信息量
  2. 信息量表示一件事情发生后带来的信息量，显然需要满足以下几个特性\ a. 信息量为正：即：$信息量_a > 0$\ b. 信息量的独立可加性（发生两件事带来的信息量等于发生这两件事带来的信息量的和）即：$信息量_{ab} = 信息量_a+信息量_b$\ c. 一件事情的信息量和这件事情的概率有关（狗咬人不是新闻，人咬狗才是）：$p_a 越大，信息熵_i越小$
  3. 负对数是一个比较简单可以满足的公式：$-log(pi)$\ a. 取「对数」：比较重要的一条就是 $信息量{ab} = 信息量_a+信息量_b$ 对数可以满足 $log(ab) = log(a)+log(b)$\ b. 取「负」对数：可以让信息量为正的同时（底数大于1），满足概率越大，信息量越小
  4. 此时得到「熵」的定义：$$\mathrm{H}(X)=\sum{i} \mathrm{P}\left(x{i}\right) \mathrm{I}\left(x{i}\right)=-\sum{i} \mathrm{P}\left(x{i}\right) \log {b} \mathrm{P}\left(x_{i}\right)$$
  5. 至于最后取2为底，是因为 （常用的）信息熵的单位是bit（binary digit）。还有其他底数，如以e为底，单位nart，以10为底，单位Hart

信息熵的总结

  1. 热力学（克劳修斯1865） 「entropy」和「熵」名称的来源
  2. 统计力学（玻尔兹曼1877） 将熵和混乱从微观熵联系起来
  3. 信息论（香农1948） 将熵带入信息的考量【概率的负对数】（取对数为了满足独立可加性，取负数为了满足整体非负性和随概率递减的性质）

一、一句话概括

通过将标签纯度最大化的方式，进行特征的划分，从而构建一颗树。核心是特征的重要性排序和最佳切分点的划分（只有CART需要考虑切分点）

二、特征选择标准与决策树发展

2.1 信息增益与ID3

核心思想：基于信息熵的概念，按照能够快速降低数据集熵的特征方向进行选择

$$g(D, A)=H(D)-H(D \mid A)$$

  1. 信息增益就是知道特征的值后，系统的熵减小程度（衡量了特征的重要性）
  2. 条件熵的定义为：特征的每一个取值下系统熵的均值\ a. 特征=a时会取出一部分样本计算其熵\ b. 特征=b时会取出一部分样本计算其熵\ c. 以上两个结果取加权平均（如果该特征只有两个取值的话）

    2.2 信息增益率与C4.5

    核心思想：改善信息增益倾向于选择不同特征项最多的特征
  3. 计算信息增益
  4. 除以该特征的「熵」

信息增益率的讨论

  1. 从定义上来看，不同特征项越多的特征确实会被照顾（切分的细小，类别的纯度越纯的概率越高）
  2. 但是直接除以「特征的熵」是否”公平“值得商榷，是不是这样一来又会选择特征较为规整（不同特征项较少的特征），也许是一个经验上的方法
  3. 题外话：作者本人描述到这里的时候也只是简单说，“我们需要一个类似正则化项的手段对不同特征项个数很多的特征进行惩罚” 选择熵作为衡量不同特征项的混乱程度的度量，似乎「师出同门」，简单作为分母也许也只是随意为之。

2.3 GINI系数与CART

核心思想：改善对数不易计算的问题

  1. 从信息论的熵引入系统用来判断「纯度」开始，对数的计算就被引入了整个过程
  2. 和之前算法需要梯度下降求偏导不一样，这里并不需要log来优化求导过程，反而加大了计算难度
  3. 于是这个思路就变成了：从数据集中连续取出两个样本，标签不一样的概率，显然这个计算大大降低$$\operatorname{Gini}(p)=\sum{k=1}^{K} p{k}\left(1-p{k}\right)=1-\sum{k=1}^{K} p_{k}^{2}$$
  4. 公式也很好理解：用1减去，两次拿到同样标签的样本的概率
  5. 二分类问题也可以进行简化：正着思考问题，第一次A第二次B或者第一次B第二次A $$\operatorname{Gini}(p)=p(1-p)+(1-p)p=2p(1-p)$$

    三、特征最佳切分点

  6. 只有基尼系数的CART有最佳切分点的问题（可能是因为log的计算太复杂，寻找最佳切分点的计算过程时间复杂度太高，所以ID3和C4.5并没有引入）
  7. 因为只有CART树有最佳切分点，所以只有CART树是二叉树，ID3和C4.5根据信息增益或者信息增益率排好序之后直接就构建好了（多叉树）
  8. 利用OVR（one vs rest）的思想在一个特征下进行多次GINI系数的计算，取最小的作为该特征的GINI系数，参与和其他特征的GINI系数的比较。同时取得这个最小的GINI系数的特征项，就是该特征的最佳切分点

    四、工程优化总结

  9. ID3：没有什么优化（有一个很简单的前剪枝过程 增益效果），容易过拟合

  10. C4.5\ a. 处理连续性数据（使用阈值把样本分为两部分）\ b. 处理缺失性数据（属性值缺失的样本在计算熵减时被忽略）\ c. 剪枝（合并无法产生大量信息增益的节点）【前剪枝】

  11. CART\ a. 可用于回归（此时损失函数是平方误差）\ b. 剪枝的优化（从需要多次扫描的悲观剪枝变为了从下往上的剪枝策略）

    五、剪枝

    5.1 前剪枝

    核心：生成树的时候差不多行了（不要竭泽而渔）

  12. 限制高度
  13. 限制叶子节点个数
  14. 系统性能：比如标准是信息增益，那么信息增不了多少益的时候

    5.2 后剪枝

    核心：给定一个损失函数 $C(T) + alpha * T$ 对生成后的树按着这个公式比较「效益」进行剪枝

    5.2.1 C4.5：剪坏了就撤销

    核心：给树定义一个损失函数，试着剪（有提升就Ctrl+s，没提升就Ctrl+z）

  15. 叶子节点的熵 + alpha * 叶子节点个数 相当于 熵+惩罚项
  16. 剪一下带入损失函数算一下

    5.2.2 CART：边剪边保存

    核心：剪出一堆树，带入数据进行测试（树是越来越小的：后面的树是前面的子树，边剪树，边Ctrl+s）

  17. 分类：$GINI + \alpha * 叶子节点个数$
  18. 回归：$MSE + \alpha * 叶子节点个数$
  19. 结果就是：从一个树，派生出很多模型，挑最好的那个
  20. 具体过程：考虑所有的倒数第二层节点（所有叶子节点的父亲）\ a. 膨胀 alpha，会有某一个 Node 中招（此时损失函数为0）\ b. 记录此时的alpha，并把它的子节点剪掉\ c. 最终就得到一系列的alpha和一系列的子树\

    六、总结

    1. 决策树的核心目标是想让标签的「纯度」最大化从而构建一个决策过程，「树」只是其可视化的手段
    2. 不同的决策树算法的核心不同就在于对「纯度」的不同依据：从信息论的「熵」触发逐步优化思想和减少计算的过程。
    3. 决策树真正的用武之地在于之后的集成学习（随机森林和各种提升算法中）
    4. 一个简单的计算示例在番外-一次决策过程（ID3和CART） 中