第八章分类算法

这是一篇第八章分类算法的思维导图，从决策树的定义、优点、构建、剪枝，线性分类等方面进行了分析和概述，需要可收藏。

第八章 分类算法

• 决策树
  • 基本概念
    • 基本思想
      • 基于树结构进行决策
        • 每个内部节点对应于某个属性上的测试
        • 每个分支对应于该测试的一种可能结果，即该属性的某个取值
        • 每个叶节点对应于一个测试结果
    • 优点
      • 易于理解
        • 划分过程容易理解，决策过程可以表示为if then形式
      • 可解释性强
        • 划分过程完全依赖于属性变量的取值特点
      • 易于剪枝
        • 可自动忽略对目标变量分类没有贡献的属性变量，也为判断属性变量的重要性、减少变量数目提供参考
  • 决策树的构建
    • 构建过程
      • 构建方式
        • 通过对训练样本的分析来确定划分属性，即内部节点所对应的属性
    • 算法框架
      • 停止条件
        • 当前节点包含的样本全属于同一类别，无需划分
        • 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
        • 当前节点包含的样本集为空，不能划分
    • 划分
      • 关键
        • 如何选择最优划分属性
      • 划分方法
        • 信息增益
          • 信息熵
            • 度量样本集合纯度的指标
          • 定义
          • 特点
            • 对可取值数目较多的属性有所偏好，有明显弱点
        • 增益率
          • 定义
          • 特点
            • 属性a的可能取值数目越多，即V越大，则IV(a)的值通常就越大
            • 启发式：先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的
          • 缺点
            • 对取值数目较少的属性有偏好
        • 基尼指数
          • 定义
          • 特点
            • 反映了从D中随机抽取两个样例，其类别标记不一致的概率
            • Gini(D)越小，数据集D的纯度越高
            • 在候选属性集合中，选取那个使划分后基尼指数最小的属性
  • 决策树的剪枝
    • 原因
      • 是决策树学习对付过拟合的主要手段
      • 可通过剪枝来一定程度避免因决策分支过多，以至于把训练集自身的一些特点当作所有数据都具有的一般性质导致的过拟合
    • 基本策略
      • 预剪枝
        • 优点
          • 降低过拟合风险
          • 显著减少训练时间和测试时间
        • 缺点
          • 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于贪心本质禁止这些分支展开，带来了欠拟合风险。
      • 后剪枝
        • 首先生成一颗完整的决策树，依次逐个考虑决策节点，替换叶节点后，验证集精度是否有提高
        • 优点
          • 降低过拟合风险，欠拟合风险基本不变
          • 测试时间开销降低
        • 缺点
          • 训练时间开销增加
    • 判断决策树泛化性能是否提升
      • 预留一部分数据用作验证集以进行性能评估，后剪枝通常优于预剪枝
• 线性分类
  • 线性分类器
    • 优点
      • 简单、基本、可理解性好
      • 非线性模型的基础，引入层级结构或高维映射
    • 线性回归
    • 多元线性回归
    • 二分类问题
  • 多分类方法
    • 多分类学习方法
      • 利用二分类学习器解决多分类问题
        • 对问题进行拆分，为拆出的每个二分类任务训练一个分类器
        • 对于每个分类器的预测结果进行集成以获得最终的多分类结果
    • 拆分策略
      • 一对一
      • 一对其余
      • 多对多