决策树（Decision Tree）

基本概念

• 由很多“树”组成，是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

• 包含了一个根结点，若干个内部结点和若干个叶结点；

  • 叶结点对应于决策结果，其他每个结点则对应于一个属性测试
  • 每个结点包含的样本集合根据属性测试的结果被划分到子结点中
  • 根结点包含样本全集
  • 从根结点到每个叶结点的路径对应了一个判定测试序列

学习目的

• 产生一棵泛化能力比较强，处理未遇见的示例能力强的决策树。也就是说，根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

伪代码

划分选择

• 问题提出

  • 如何获得最优划分属性

• 信息熵（information entropy）

  • 度量样本集合纯度的常用指标
  • 公式：

• 信息增益（information gain）

  • 基本定义和解释

  • 意义

    • 信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大。

  • 结论

    • 可以使用信息增益来进行决策树的划分属性选择，即

  • 计算步骤（示例）

    • １、先计算所有样例的正反例的比例，得出根结点的信息熵
    • ２、计算其他每个属性集合的信息增益（需要先计算出每个属性的信息熵）
    • ３、信息增益最大的就被选为划分属性，成为了根结点的划分
    • ４、再对分支节点进一步进行划分（划分属性集合的信息），划分后对每个结点再次计算信息增益
    • ５、再根据信息增益最大的被选为划分属性，如此重复上述步骤。对每个分支节点进行操作

• 增益率（gain ratio）

  • 提出问题

    • 信息增益准则对可取值数目较多的属性有所偏好，会带来不利的影响

  • 基本概念

    • 对可取值数目较少的属性有所偏好
    • 属性ａ为“固有值”（intrinsic value）。属性ａ的可取值数目越多（Ｖ越大），则IV(a)的值通常也会越大。

  • 特点

    • 并不直接选择增益率最大的候选划分属性，而是使用了一个启发式

      • 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

• 基尼指数（Gini index）

  • 基本概念

    • 用基尼值带度量数据集Ｄ的纯度

  • 公式

  • 说明

    • 反映了从Ｄ中随机抽取两个样本，其类别标记不一致的概率。所以，Gini(D)越小，数据集Ｄ的纯度越高。

  • 属性的基尼指数计算

    • 在属性集合Ａ中，选择使的划分后基尼指数最小的属性作为最优划分属性

PS

后续会把这章没看完的补全

Reference

【1】周志华. Machine Learning 机器学习