数据挖掘：概念与技术（翻译 张磊） 22
2014-8-21
决定最终树大小的方法

将数据集的2/3作为训练集, 1/3作为测试集
使用交叉验证, 例如, 10-fold交叉验证 使用全部数据来训练

但运用统计检验(例如, chi-square)来估计对某 个节点的分裂或修剪是否能改善整体分布 当编码量达到最小时停止树的生长
数据挖掘：概念与技术（翻译 张磊） 2
2014-8-21
分类与预测



分类: 预测分类标签 基于训练集和分类属性值(分类标签)构造分类模型，然 后用该模型分类新数据 预测: 对连续函数建模, 即预测未知的或缺失的数据 典型应用 信用审核 目标营销 医疗诊断 治疗效果分析
通过决策树归纳进行分类



决策树 类似于流程图的树型结构 内部节点代表对某个属性的一次测试 分支代表测试的输出结果 叶节点代表分类标签或分布 决策树的生成包括两个阶段 树的创建 首先, 所有训练样本都位于根节点 递归地基于选择属性来划分样本集 树的修剪 识别并删除那些反映噪声或孤立点的分支 应用决策树: 对未知样本进行分类 在决策树上测试样本的各个属性值
2014-8-21
数据挖掘：概念与技术（翻译 张磊）
15
属性选取的度量


信息增益 (ID3/C4.5) 所有属性应为类别型变量 可以通过改进来处理连续值属性 Gini索引 (IBM IntelligentMiner) 所有属性应为连续值变量 对于每个属性, 假定已存在若干可能的切分点 可能需要其它工具(如聚类)的辅助来获取切分点 可以通过改进来处理类别型属性
5
数据挖掘：概念与技术（翻译 张磊）
分类过程 (2): 使用模型来预测
分类器 测试 数据
新数据 (Jeff, Professor, 4)
NAME Tom M erlisa G eorge Joseph
2014-8-21
RANK Y E A R S TE N U R E D A ssistant P rof 2 no A ssociate P rof 7 no P rofessor 5 yes A ssistant P rof 7 yes
20
N1 gini( ) N 2 gini( ) ( T ) gini split T1 T2 N N
2014-8-21
数据挖掘：概念与技术（翻译 张磊）
从树中抽取分类规则





用IF-THEN规则来作为知识表示 从根节点到叶节点的每条路径, 对于于一条规则 路径上的每个(属性-值)对被联合起来 叶节点给出了类别预测 规则非常易懂 示例
Gain(income) 0.029 Gain( student ) 0.151 Gain(credit _ rating ) 0.048
19
数据挖掘：概念与技术（翻译 张磊）
Gini 索引 (IBM IntelligentMiner)

如果数据集T 包含n种类别的样本, gini index, gini(T) 定义如 下
数据挖掘：概念与技术（翻译 张磊）
Tenured?
6
有指导的 vs. 无指导的学习

有指导的学习 (分类)

指导: 模型的学习在被告知每个训练样本属于 哪个类的“指导”下进行 基于训练集对新数据进行分类


无指导的学习 (聚类)


训练数据的类标签是未知的
给定一组样本, 试图建立分类或数据的聚类
2014-8-21
2014-8-21
数据挖掘：概念与技术（翻译 张磊）
16
信息增益 (ID3/C4.5)

选取具有最高信息增益的属性 假定存在两个分类, P 和N

样本集S中包含p个样本属于类别P, n个样本属于类别N
用于判别S中任意样本属于类别P 或N 的信息量, 定义为
p p n n I ( p, n) log2 log2 pn pn pn pn
2014-8-21
分类与预测相关问题 (1): 数据准备

数据清洗

数据准备是为了减少噪声数据, 并处理缺失值

相关分析 (特征选取)

删除无关属性和冗余属性
数据的泛化和归一化

数据转换

2014-8-21
数据挖掘：概念与技术（翻译 张磊）
9
分类与预测的相关问题 (2): 分类方法的评估





预测准确率 速度和扩展能力 创建模型所需时间 应用模型所需时间 健壮性 可以处理噪声和缺失值 扩展能力 在大型数据库上的处理能力 可解释性 模型能否增强用户对数据的理解和洞察力 是否良好的规则 决策树的大小 分类规则的简洁程度
数据挖掘：概念与技术（翻译 张磊） 10
DM算法-1
分类和预测
出处：《数据挖掘：概念与技术》 © Jiawei Han and Micheline Kamber
2014-8-21
数据挖掘：概念与技术（翻译 张磊）
1
DM算法-1 分类和预测

什么是分类? 什么是预测? 关于分类与预测的问题 通过决策树归纳来分类 贝叶斯分类 通过反向传播来分类 基于关联规则挖掘的概念来分类 其它分类方法 预测 分类准确率 总结
IF IF IF IF
2014-8-21
数据挖掘：避免分类中的过度训练


生成的树可能会过度拟合了训练数据 分支太多, 某些分支其实反映的是特例(由噪声数据或 孤立点引起的) 导致预测未知样本的准确率很差 避免过度训练的两种方法 预修剪: 尽早中止树的创建—当某个分裂会导致优度 度量低于给定阈值时, 就不再分裂节点 难于确定合适的阈值 后修剪: 从“已长成的” 树中删除分支—得到多个修 剪后的树 使用与训练数据不同的验证集来决定哪个是―最佳 剪枝树”
数据挖掘：概念与技术（翻译 张磊） 4
2014-8-21
分类过程 (1): 模型创建
训练 数据 分类 算法
NAME RANK M ike M ary B ill Jim D ave Anne
2014-8-21
YEARS TENURED 3 7 2 7 6 3 no yes yes yes no no
13
2014-8-21
数据挖掘：概念与技术（翻译 张磊）
输出: 预测“是否会购买计算机”的决策树
age? <=30 overcast 30..40 yes yes yes >40
student?
no no
2014-8-21
credit rating?
excellent no fair yes
14
数据挖掘：概念与技术（翻译 张磊）
决策树归纳算法


基本算法(贪婪算法) 树的创建是一种自顶向下递归的分而治之方法 首先, 所有训练样本都位于根节点 属性都是类别型变量 (若为连续值, 则需先离散化) 基于选择的属性, 对样本进行递归划分 通过启发式搜索或统计量来选取测试属性 (例如, 信息增益) 停止划分的条件 对于某个给定节点, 所有样本都属于同一分类 没有剩余属性可供进一步划分 – 按照少数服从多数的原则来确定叶 节点的分类 所有样本都已分类完毕
数据挖掘：概念与技术（翻译 张磊） 12
2014-8-21
训练数据集
接下来是 Quinlan’s ID3算法 示例
age <=30 <=30 31…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40 income high high high medium low low low medium low medium medium medium high medium student no no no no yes yes yes no yes yes yes no yes no credit_rating fair excellent fair fair fair excellent excellent fair fair fair excellent excellent fair excellent
age = ―<=30‖ AND student = ―no‖ THEN buys_computer = ―no‖ age = ―<=30‖ AND student = ―yes‖ THEN buys_computer = ―yes‖ age = ―31…40‖ THEN buys_computer = ―yes‖ age = ―>40‖ AND credit_rating = ―excellent‖ THEN buys_computer = ―yes‖ IF age = ―>40‖ AND credit_rating = ―fair‖ THEN buys_computer = ―no‖
数据挖掘：概念与技术（翻译 张磊）
7
DM算法-1 分类和预测

什么是分类? 什么是预测? 关于分类与预测的问题 通过决策树归纳来分类 贝叶斯分类 通过反向传播来分类 基于关联规则挖掘的概念来分类 其它分类方法 预测 分类准确率 总结
数据挖掘：概念与技术（翻译 张磊） 8
A ssistan t P ro f A ssistan t P ro f P ro fesso r A sso ciate P ro f A ssistan t P ro f A sso ciate P ro f