决策树 - ID3-ID4.5-C4.5

发表于 更新于 分类于 ， 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 4 分钟

也是非常直观的分类方法，关键过程是：特征的选择，衡量标准的熵、信息增益率和基尼指数

什么是决策树 (Decision tree,DT)?

  • 决策树是一个树形结构的预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个叶节点表示某个类别，而每个分叉路径则代表属性值，决策树可以包括分类决策树和回归决策树
  • 随机森林 (Random Forest) 分类器将许多决策树结合起来以提升分类的正确率

什么是分类决策树？

  • 预计结果可能为离散类型的决策树 (Decision tree,DT) ，由结点和有向边组成，结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类
  • 从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点，确定类别
  • sklearn 的 DecisionTreeClassifier 是一个能够对数据集进行多类分类的分类器
    1
    2
    3
    4
    5
    6
    7
    >>> from sklearn import tree
    >>> X = [[0, 0], [1, 1]]
    >>> Y = [0, 1]
    >>> clf = tree.DecisionTreeClassifier()
    >>> clf = clf.fit(X, Y)
    >>> clf.predict([[2., 2.]])
    	array([1])

什么是回归决策树？

  • 预计结果可能为实数的决策树 (Decision tree,DT)
  • sklearn 的 DecisionTreeRegressor 一个数据集进行回归器
    1
    2
    3
    4
    5
    6
    7
    >>> from sklearn import tree
    >>> X = [[0, 0], [2, 2]]
    >>> y = [0.5, 2.5]
    >>> clf = tree.DecisionTreeRegressor()
    >>> clf = clf.fit(X, y)
    >>> clf.predict([[1, 1]])
    	array([0.5])

回归决策树和分类决策树的区别与联系？

  • 联系
    • 在决策树的构建上是一样的（最优划分）
    • 回归决策树是计算预测点所在的叶子节点的均值或者加权平均值得到回归结果
    • 分类是通过多数投票或者加权的多数投票得到分类结果
  • 度量指标不同
    • 回归决策树是 MAE,MSE
    • 分类决策树是：信息熵、基尼系数、错误率

决策树的组成？

  • 根节点： 对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案
  • 内部节点： 代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率
  • 结果节点： 将每个方案在各种自然状态下取得的分类结果

决策树的构建方法？

  • 特征选择特征选择：选择分类能力强的特征优先进行分类。判断分类能力强的度量包括：信息增益 、信息增益率 、基尼系数 (Gini)
  • 决策树生成：根据特征选择选择分裂的特征及分裂阈值，构造树结构
  • 决策树剪枝： 对决策树进行剪枝，提高决策树的泛化能力

决策树的 if-then 规则？

  • ** 关系：** 由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论
  • 重要的性质：互斥并且完备。即每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖

什么是 ID3 决策树？

算法 ID3 构造决策树过程？

  • 从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点
  • 再对子结点递归地调用以上方法，构建决策树
  • 直到所有特征的信息增益均很小或没有特征可以选择为止

ID3 决策树缺点

  • 不适合处理连续数据
  • 难以处理海量数据集
  • 建树时偏选属性值较大的进行分离，而有时属性值较大的不一定能反应更多的数据信息

ID3 决策树优点

  • ID3 算法建立的决策树规模比较小； 查询速度快

对表的训练数据集，利用 ID3 算法建立决策树

对表所给的训练数据集 D，根据信息增益准则选择最优特征

什么是 CART 决策树？

算法 CART 生成决策树的过程？

  • 对回归树用平方误差（最小二乘法）最小化准则，生成二叉树
  • 对分类树用基尼系数 (Gini) 最小化准则，进行特征选择，生成二叉树

算法 CART 的剪枝过程？

  • CART 剪枝算法由两步组成：首先从生成算法产生的决策树 T0 底端开始不断剪枝，直到 T0 的根结点，形成一个子树序列 {T0 ， T1,…,Tn} ；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树

根据表所给训练数据集，应用 CART 算法生成决策树

什么是 C4.5 决策树？

算法 C4.5 构造决策树过程？

  • 同 ID3 算法过程一样，但使用信息增益率比来选择特征

C4.5 决策树缺点

  • 构造树时，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效
  • 只适合于能驻留于内存的数据集，当训练集达到内存无法容纳时程序无法运行

C4.5 决策树描述

  • C4.5 算法是 ID3 算法的修订版，采用信息增益率来加以改进，选取有最大增益率的分割变量作为准则，避免 ID3 算法过度的适配问题

C4.5 决策树优点

  • C4.5 继承了 ID3 优点
  • 在树构造过程中进行剪枝
  • 能对不完整数据进行处理
  • 能够完成对连续属性的离散化处理
  • 产生的分类规则易于理解，准确率较高
  • 用增益率来选择属性，克服了用增益选择属性时偏向选择取值多的属性

什么是 C5.0 决策树？

C5.0 决策树缺点

  • 目标字段必须为分类字段

C5.0 决策树描述

  • C5.0 算法是在 C4.5 算法的基础上改进而来的产生决策树算法，它除了包括 C4.5 的全部功能外，还引入许多新的技术，其中最重要的技术是提升（Boosting）技术，目的是为了进一步提高决策树对样本的识别率。
  • 同时 C5.0 的算法复杂度要更低，使用更简单，适应性更强，因此具有更高的使用价值

C5.0 决策树优点

  • C5.0 模型能同时处理连续和离散的数据
  • C5.0 模型估计模型通常不需要很长的训练时间
  • C5.0 引入 Boosting 技术以提高分类的效率和精度
  • C5.0 模型易于理解，模型推出的规则有非常直观的解释
  • C5.0 模型在面对数据遗漏和特征很多的问题时非常稳健

ID3、C4.5、C5.0 和 CART 有什么差异？

  • ID3（Iterative Dichotomiser 3）: 是由 Ross Quinlan 在 1986 年开发的。该算法创建了一棵多向树，为每个节点（即以一种贪婪的方式）寻找分类目标的最大信息增益的分类特征。树长到最大尺寸，然后通常应用一个修剪步骤，以提高树对未见数据的概括能力
  • C4.5 是 ID3 的后继者，通过动态地定义一个离散的属性（基于数字变量），将连续的属性值划分为一组离散的区间，从而消除了特征必须是分类的限制。C4.5 将训练好的树（即 ID3 算法的输出）转换为 if-then 规则集。然后对每个规则的准确性进行评估，以确定它们的应用顺序。如果规则的准确性在没有前提条件的情况下得到提高，则通过删除规则的前提条件来进行修剪
  • C5.0 是 Quinlan 的最新版本，采用专有许可证发布。与 C4.5 相比，它使用的内存更少，构建的规则集更小，同时更准确
  • CART（分类和回归树）与 C4.5 非常相似，但它的不同之处在于，它支持数字目标变量（回归），不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构建二进制树

如何解决决策树中单样本输出多标签的问题？

  • 多输出问题是一个有多个输出需要预测的监督学习问题，即当 Y 是一个 2d 形状的数组（n_samples，n_outputs）
  • 当输出之间没有相关性时，解决这种问题的一个非常简单的方法是建立 n 个独立的模型，即每个输出一个模型，然后用这些模型来独立预测 n 个输出中的每一个。然而，由于与同一输入相关的输出值本身很可能是相关的，所以通常更好的方法是建立一个能够同时预测所有 n 个输出的单一模型。首先，它需要较少的训练时间，因为只需要建立一个估计器。其次，由此产生的估计器的泛化精度通常可以提高
  • 修改决策树：（1） 在叶子中存储 n 个输出值，而不是 1 个 ；（2） 使用分割标准，计算所有 n 个产出的平均减少量

简单描述分类与回归树？

  • 分类与回归树的英文缩写是 CART，也属于一种决策树，树的构建基于基尼指数。CART 假设决策树是二叉树，内部结点特征的取值为 “是” 和 “否”，左分支是取值为 “是” 的分支，右分支是取值为 “否” 的分支。这样的决策树等价于递归二分每个特征，将输入空间（特征空间）划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布

决策树的常用算法有那些，这些算法有什么区别？

  • 常用的有：ID3,C4.5,CART 三种算法
  • 纯度量化指标不同.ID3–> 信息增益，C4.5–> 信息增益率，CART–> 基尼系数
  • 数据处理能力不同. ID3–> 离散数据，C4.5,CART—> 连续数据离散化，剪枝操作
  • 要求的树的类型不同.ID3 和 C4.5 可以是多叉树，CART 只能是二叉树

决策树的剪枝过程？

决策树剪枝的基本策略有哪些？

  • 决策树剪枝的基本策略有 "预剪枝" (prepruning) 和 " 后剪枝 “(post” pruning) [Quinlan , 1993]. 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
  • 决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型

表是一个由 15 个样本组成的贷款申请训练数据。数据包括贷款申请人的 4 个特征（属性）：第 1 个特征是年龄，有 3 个可能值：青年，中年，老年；第 2 个特征是有工作，有 2 个可能值：是，否；第 3 个特征是有自己的房子，有 2 个可能值：是，否；第 4 个特征是信贷情况，有 3 个可能值：非常好，好，一般。表的最后一列是类别，是否同意贷款，取 2 个值：是，否

三个特征选择值及三个决策树关系

  • 信息增益：在 ID3 决策树中使用
  • 信息增益率：在 C4.5 决策树中使用
  • 基尼系数：在 CART 决策树中使用