决策树 (Decision Tree) 详解——机器学习经典分类算法

/ Machine Learning / 没有评论 / 576浏览

决策树模型

决策树是一个类似于流程图的树结构,由结点(node)和有向边(directed edge)组成

树的最顶层是根结点。

决策树既可以用于分类,也可以用于回归

分类决策树

分类决策树模型是一种描述实例进行分类的树形结构。决策树表示基于特征对实例进行分类的过程。

if-then 规则

可以将决策树看做一个if-then规则
决策树的路径或者其对应的 if-then 规则必须满足:互斥+完备

条件概率分布

将特征空间划分为互不相交的单元(cell)或区域(regison),并在每个单元定义一个类的概率分布,这样就构成了一个条件概率分布

决策树的一条路径对应于划分中的一个单元

决策树的生成

特征选择

特征选择在于选取对训练数据具有分类能力的特征,当特征是连续值时,将连续值按一定规则切分成多个段,按照切分规则形成分类条件

随着树深度的增加,节点的熵迅速地降低。熵降低的速度越快越好,这样就能得到一颗最矮的决策树

如果想了解,请查看熵(Entropy)与信息量详细介绍——统计机器学习核心概念

熵下降的速度可以用信息增益信息增益比来衡量

决策树过高会导致过拟合的问题

过拟合

在学习的过程中,过多地考虑如何提高对训练数据的正确分类,从而构建出一棵过于负载的决策树,

ID3 生成算法

1970-1980, J.Ross. Quinlan 提出 ID3 算法

ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归的构建决策树。

ID3相当于用极大似然法进行概率模型的选择

ID3 算法只有树的生成,所以该算法生成的树容易产生过拟合

C4.5生成算法

考虑一种极端情况,将每组数据的 ID 作为根节点,可以一次将类别全部分出来,因为一个ID只对应一个类别,导致决策树仅只有一层,但是分支却很多。将 ID 作为根节点,能使信息增益最大化,但是这种做法荒唐至极

对于一个特征,如果其包含的属性有很多,而每个属性对应的样本又很少,对于这种特征,信息增益很大,但选择这样的特征作为结点是不合理的。

使用信息增益率来选择特征是更好的做法

C4.5 算法在树的生成过程中,用信息增益比来选择特征,递归的构建决策树。

决策树剪枝

损失函数

要评价一棵决策树的好坏,可以使用如下的评价函数计算

$$C(T) = \sum_{t \in leaf}N_{t} \cdot H(t) \tag{1}$$

$N_t$ 指当前叶子结点 t 具有的样本数,相当于权重
$H(t)$ 指当前叶子结点 t 的熵值或者是 Gini 系数

损失函数越小,表示决策树越好

预剪枝

在构建决策树的时候,希望能够提前停止,避免其一直构造下去,导致最终每个节点只一个样本

可以定义最大深度,比如微软小冰读心术规定,最大深度为15

可以定义最小的样本结点个数,如规定结点的最小样本数为30,则小于30样本点的结点就是叶结点。

后剪枝

构建好决策树后,进行剪枝操作

评价函数

$$C_\alpha(T) = C(T) + \alpha \cdot |T_{leaf}|$$

$C(T)$ 是 (1) 式的损失函数,$T_{leaf}$ 表示叶子节点的个数

随机森林

所谓森林,是指构造一片决策树,用这一片决策树来共同做决策

所谓随机,指下面讲到的双重随机性

使用有放回的采样(Bootstraping),在原始训练集中,不选择全部数据,而是随机选择部分数据(如样本容量的60%)这样总可以使得选择的一部分数据集中异常样本很少,从而使得部分决策树比较好

在所有特征中,随机选择部分特征(如特征总数的60%),这样总可以使得选择的一部分特征是对结果影响较大的特征,使得部分决策树比较好