顿搜
飞过闲红千叶，夕岸在哪
类目归类
决策树 (Decision Tree) 详解——机器学习经典分类算法
12/30
决策树模型
决策树是一个类似于流程图的树结构，由结点（node）和有向边（directed edge）组成
- 每个内部结点 (internal node) 表示在一个属性上的测试
- 每个分支代表一个属性输出
- 每个树叶结点 (leaf node) 代表类或类分布。
树的最顶层是根结点。
决策树既可以用于分类，也可以用于回归
分类决策树
分类决策树模型是一种描述实例进行分类的树形结构。决策树表示基于特征对实例进行分类的过程。
- 它既可以认为是
if-then规则的集合， - 也可以认为是定义在特征空间与类空间上的
条件概率分布。
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%），这样总可以使得选择的一部分特征是对结果影响较大的特征，使得部分决策树比较好
