【数据挖掘】第四章 分类任务（决策树）

数据挖掘

第四章 分类任务

1.分类基本概念

1.1 分类是什么

• 分类任务就是通过学习得到一个目标函数f把每个属性集x映射到一个预先定义的类标号y
• 目标函数f也称之为分类模型（classification model）
• 给定一组记录（训练集）每条记录由一个元组(x,y)表示，其中x是属性集，y是类标签
  

1.2 分类的目的

• 预测性建模：分类模型可以用于预测未知记录的类标号
• 描述性建模：分类模型可以作为解释性的工具，用于区分不同类中的对象（例如，了解人们为何逃税

1.3 分类的一般流程

• 训练集由具有已知类别标签的记录组成-
• 训练集用于建立分类模型
• 以前未见过的数据记录的标记测试集用于评估模型的质量
• 分类模型应用于类别标签未知的新记录
  

1.4 分类模型的评估

1.5 分类技术

• 基于决策树的方法
• 基于规则的方法
• 神经网络
• 贝叶斯和贝叶斯网络
• 支持向量机

2. 决策树

divide and conquer(分而治之）

2.1 决策树结构

• 类似流程图的树结构
• 根节点：没有传入边和零个或多个传出边的根节点
• 内部节点：每个节点都有一个传入边和两个或多个传出边
• 叶节点或终端节点：每个节点都只有一个入边，没有出边

2.2 决策树的归纳过程

• 找到最佳决策树是NP-hard
  • 根据优化特定标准的属性对记录进行拆分
• 贪心算法
  • Hunt算法(早期的算法)
  • CART
  • ID3, C4.5

2.3 Hunt 算法

• 如何指定测试条件
  • 取决于属性类型
    • 标称属性
    • 序数属性
    • 连续属性
  • 取决于拆分方式的数量
    • 二路拆分
    • 多路拆分

2.3.1 基于标称属性的拆分

2.3.1 基于连续属性的拆分

2.3.2 如何确定最佳拆分

• 贪心算法（总是做出对当前看来最优的选择,而不是从全局出发考虑）、
• 需要测量节点不纯度
  
• 增益
  
• 连续属性的拆分
  
  
• 增益率
  

2.4 决策树归纳的停止标准

• 当所有记录属于同一类时停止扩展节点
• 当所有记录具有相似的属性值时停止扩展节点
• 提前终止

2.5 决策树的优缺点

• 优点：
  • 构造成本相对低廉
  • 分类未知记录的速度极快
  • 易于解释小型树
  • 对噪声具有鲁棒性
  • 可以轻松处理冗余或不相关的属性（除非属性是交互的）
• 缺点：
  • 由于拆分标准的贪心性质，相互关联的属性（可以区分类别但不能单独区分）可能会被忽略，而有利于其他区分度较低的属性。
  • 每个决策边界只涉及一个属性