概述
- 是一种基本的分类与回归方法, 模型呈树形结构.
- 学习步骤:
- 特征选择
- 决策树的生成
- 决策树的修剪
决策树模型与学习
特征选择
信息增益
相关概念
- 熵(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): 熵中的概率由数据估计(特别是极大似然估计)得到的计算值.
- 条件熵(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): 条件熵中的概率由数据估计(特别是极大似然估计)得到的计算值.
- 信息增益(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)
- 信息增益比(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)}$$
决策树的生成
ID3算法
- 概述:
- 核心是在决策树各个节点上应用信息增益准则选择特征, 递归地构建决策树.
- 相当于用极大似然法进行概率模型的选择.
相关概念:
不纯度: 决策树的每个叶子节点中都会包含一组数据，在这组数据中，如果有某一类标签占有较大的比例，我们就说叶子节点“纯”，分枝分得好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。 如果没有哪一类标签的比例很大，各类标签都相对平均，则说叶子节点”不纯“，分枝不好，不纯度高。- 分类型决策树在叶子节点上的决策规则是少数服从多数.
- 不纯度基于节点来计算，树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度一定是最低的。
优缺点:
- 缺点:
- 在选择根节点和各内部节点中的分支属性时, 采用信息增益作为评价标准. 信息增益的缺点是倾向于选择取值较多的属性, 在有些情况下这类属性可能不会提供太多有价值的信息.
- 不能处理具有连续值的属性, 也不能处理具有缺数据的属性
- 没有对决策树进行修剪的过程, 噪声比较大.
C4.5的生成算法
- 概述:
- 与ID3算法相似, C4.5算法对ID3算法进行了改进, 在生成过程中, 用信息增益比来选择特征.
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}$$
- 优缺点:
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$$
回归树的生成
分类树的生成
决策树的剪枝(pruning)
- 如果一个分支, 叶节点的错误率之和大于将该分支砍去所产生的错误率, 则对此分支进行修剪.
决策树算法异同
- C5.0通过计算预测错误率来剪枝, 而CART算法通过验证数据来剪枝.
相关库
Python
from sklearn.tree import DecisionTreeClassifier