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