发表于 | 分类于 | 0 | 阅读次数 962

1. 概述

  • 是一种基本的分类与回归方法, 模型呈树形结构.
  • 学习步骤:
    1. 特征选择
    2. 决策树的生成
    3. 决策树的修剪

2. 决策树模型与学习

3. 特征选择

3.1 信息增益

3.1.1 相关概念

  1. 熵(entropy)
    • 定义: 表示随机变量不确定性的度量.
    • 公式:
      • 设X是一个取有限个值得离散随机变量, 其概率分布为:$$P(X = x_i) = p_i, \quad i=1,2,...,n$$则随机变量X的熵定义为$$H(x) = -\sum_{i=1}^np_i logp_i \tag{3.1.1.1}$$式(3.1.1.1)中的对数以2或以e为底, 熵单位分别称作比特(bit)或纳特(nat).
      • 由定义可知, 熵只依赖于X的分布, 而与X的取值无关, 所以也可以将X的熵记作H(p), 即$$H(p) = -\sum_{i=1}^np_i logp_i \tag{3.1.1.2}$$
    • 性质:
      • 熵越大, 随机变量的不确定性就越大, 从定义可证$$0 \le H(p) \le logn$$
    • 经验熵(empirical entropy): 熵中的概率由数据估计(特别是极大似然估计)得到的计算值.
  2. 条件熵(conditional entropy)
    • 定义:
      • 设有随机变量(X , Y), 其联合概率分布为$$P(X = x_i, Y = y_j) = p_{ij}, \quad i=1,2,\cdots,n; j=1,2,\cdots, m$$条件熵H(Y|X) 表示在已知随机变量X的条件下随机变量Y的不确定性. 定义为X给定条件下Y的条件概率分布的熵对X的数学期望$$H(Y|X) = \sum_{i=1}^np_iH(Y|X=x_i), \quad p_i = P(X = x_i), i=1,2,\cdots,n$$
    • 经验条件熵(empirical entropy): 条件熵中的概率由数据估计(特别是极大似然估计)得到的计算值.
  3. 信息增益(information gain): 表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.
    • 定义:
      • 特征A对训练数据集D的信息增益g(D,A), 定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差, 即$$g(D,A) = H(D) - H(D|A)$$
      • 一般地, 熵H(Y)与条件熵H(Y|X)之差称为互信息(mutual information)
  4. 信息增益比(information gain ratio):
    • 定义:
      • 特征A对训练数据集D的信息增益比$g_R(D, A)$, 定义为其信息增益g(D, A)与训练数据集D的经验熵H(D)之比:$$g_R(D, A) = \frac{g(D, A)}{H(D)}$$

4. 决策树的生成

4.1 ID3算法

  • 概述:
    • 核心是在决策树各个节点上应用信息增益准则选择特征, 递归地构建决策树.
    • 相当于用极大似然法进行概率模型的选择.

相关概念:

  • 不纯度: 决策树的每个叶子节点中都会包含一组数据，在这组数据中，如果有某一类标签占有较大的比例，我们就说叶子节点“纯”，分枝分得好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。 如果没有哪一类标签的比例很大，各类标签都相对平均，则说叶子节点”不纯“，分枝不好，不纯度高。
    • 分类型决策树在叶子节点上的决策规则是少数服从多数.
    • 不纯度基于节点来计算，树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度一定是最低的。

优缺点:

  • 缺点:
    1. 在选择根节点和各内部节点中的分支属性时, 采用信息增益作为评价标准. 信息增益的缺点是倾向于选择取值较多的属性, 在有些情况下这类属性可能不会提供太多有价值的信息.
    2. 不能处理具有连续值的属性, 也不能处理具有缺数据的属性
    3. 没有对决策树进行修剪的过程, 噪声比较大.

4.2 C4.5的生成算法

  • 概述:
    • 与ID3算法相似, C4.5算法对ID3算法进行了改进, 在生成过程中, 用信息增益比来选择特征.

4.3 C5.0算法

  • 概述:
    • C5.0算法是C4.5算法的修订版, 适用于处理大数据集, 引入了分支度(Information Value)$$IV = -\sum_{i=1}^n(c_i/t)log_2(c_i/t)$$信息增益率为:$$g_R(D,A) = \frac{g(D,A)}{IV}$$
  • 优缺点:
    • 优点:
      1. 可以处理数值型数据

4.4 CART 算法

  • 概述:
    • 分类与回归树(classification and regression tree, CART), 同样由特征选择, 树的生成及剪枝组成, 既可用于分类也可以用于回归. 分类树与回归树的区别在于叶节点. 如果目标字段是类别型的, 则建立的模型为分类树; 如果目标字段是数值型的, 则建立的模型就是回归树.
    • 决策树的生成就是递归地构建二叉决策树的过程.
      • 回归树用平方误差最小化准则
      • 分类树用基尼指数(Gini index)最小化准则$$Gini(p) = \sum_{k=1}^Kp_k(1 - p_k) = 1- \sum_{k=1}^Kp_k^2$$

4.4.1 回归树的生成

4.4.2 分类树的生成

5. 决策树的剪枝(pruning)

  • 如果一个分支, 叶节点的错误率之和大于将该分支砍去所产生的错误率, 则对此分支进行修剪.

6. 决策树算法异同

  • C5.0通过计算预测错误率来剪枝, 而CART算法通过验证数据来剪枝.

7. 相关库

7.1 Python

from sklearn.tree import DecisionTreeClassifier