Wynette F
1.75m Medium Medium
11
分类表现：混淆矩阵
真正例
假反例
假正例
真反例
12
ROC 曲线
13
回归
根据输入值估计一个输出值
确定最佳的 回归系数 c0,c1,…,cn.
假设出一个误差: y = c0+c1x1+…+cnxn+e 可以利用均方差函数估计线性回归模型拟合实
28
决策树往往基于信息论构建 So
29
信息
30
信息/熵
给定概率 p1, p2, .., ps ，之和为 1, 熵的定义为:
熵是数据不确定性、突发性或随机性程度的度 量.
分类的目标
- 没有不确定性 - 熵为 0
31
熵
log (1/p)
H(p,1-p)
32
ID3
基于信息论构建决策树的ID3技术试图使比较 的期望数最小化。
ID3 利用最高信息增益属性作为分裂属性:
33
ID3 例子
初始集合的熵: 4/15 log(15/4) + 8/15 log(15/8) + 3/15 log(15/3) = 0.4384 性别作为分裂属性的信息增益:
- 女: 3/9 log(9/3)+6/9 log(9/6)=0.2764 - 男: 1/6 (log 6/1) + 2/6 log(6/2) + 3/6 log(6/3) =
- 基于统计的算法 - 基于距离的算法 - 基于决策树的算法 - 基于规则的算法 - 基于神经网络的算法 - 支持向量机
3
分类问题
给定一个由元组组成的数据库（数据集）
D={t1,t2,…,tn} 和一个类别集合 C={C1,…,Cm}, 分 类问题 是指定义一个映射 f:DgC ，其中每个元
组中心点: 代表点.
- 各个元组
算法: KNN
19
K最近邻 (KNN):
训练集包括了类别标签. 进一步考虑训练集中K个与新元组相距最近的元
组. 新元组将被分配到一个包含了K个最近元组中最
多元组的那一类. O(q) 是该问题的时间复杂度. (q 训练集中元组
的个数.)
20
2. 将产生的模型应用于目标数据库中对 元组进行分类.
类别必须预先定义 最常用的算法包括决策树，神经网络，及基
于距离，统计等算法.
8
定义类别
分割
基于距离
9
分类中的问题
缺失数据
- 忽略 - 利用假定值来替换
性能度量
- 分类精度 - 混淆矩阵 - ROC 曲线
10
身高数据例子
Name
Gender Height Output1 Output2
KNN
21
KNN 算法
22
基于决策树的算法
基于区域划分: 将搜索空间划分为一些矩形区域.
根据元组落入的区域对元组进行分类.
大部分研究集中在如果有效的构建树: 决策树归纳
内部结点标记为一个属性，属性值为弧 算法: ID3, C4.5, CART
23
决策树
给定:
- D = {t1, …, tn} ，其中 ti=<ti1, …, tih> - 数据库模式包含下列属性 {A1, A2, …, Ah} - 类别集合 C={C1, …., Cm}
Kristina F
1.6m Short Medium
Jim
M
2m
Tall
Medium
Maggie F
1.9m Medium Tall
Martha F
1.88m Medium Tall
Stephanie F
1.7m Short Medium
Bob
M
1.85m Medium Medium
Kathy
F
1.6m Short Medium
际数据的精度:
14
线性拟合误差
15
回归用于分类
分割: 利用回归函数，将空间划分成一些区域，
每一个类对应一个区域.
预测: 通过回归，产生一个可以用于预测类别值
的线性公示
16
分割
17
预测
18
基于距离法的分类
将更接近或更相似的成员映射到同一个类别当 中去
必须确定项之间或者类之间的距离 . 类别描述
0.4392 - 加权和: (9/15)(0.2764) + (6/15)(0.4392) = 0.34152 - 增益: 0.4384 – 0.34152 = 0.09688 身高作为分裂属性的信息增益:
决策树或分类数 是具有下列属性的树
- 每个内部结点都标记一个属性, Ai - 每个弧都被标记一个谓词，这个谓词可应用于相应的父
结点的属性 - 每个叶结点都被标记一个类, Cj
24
DT 算法
25
决策树划分区域
M Gender
F
Height
26
决策树对比
平衡树
深的树
27
决策树的问题
选择分裂属性 分裂属性次序 分裂 树的结构 停止准则 训练数据 剪枝
数据挖掘技术
第二部分 分类预测、聚类、关联规则
1
数据挖掘提纲
第一部分 - 概述 - 相关概念 - 数据挖掘技术
第二部分
- 分类 - 聚类 - 关联规则
第三部分 - Web 挖掘 - 空间数据挖掘 - 时序数据挖掘
2
分类
目标: 提供一个分类问题的概述并介绍几种常见分
类问题的算法
分类问题概述 分类技术
预测 是一种特殊的分类, 连续时可看成无限多类，
离散时就是分类了.
4
分类举例
老师根据分数将学生分类为 A, B, C, D, 和 F. 识别蘑菇是否有毒. 预测何时何地会发洪水. 识别个人的信用风险. 语音识别 模式识别
5
等级分类
x >= 90 等级 =A. 80<=x<90 等级 =B. 70<=x<80 等级 =C. 60<=x<70 等级 =D. x<50 等级 =F.
Dave
M
1.7m Short Medium
Worth
M
2.2m Tall
Tall
Steven M
2.1m Tall
Tall
Debbie F
1.8m Medium Medium
Todd
M
1.95m Medium Medium
Kim
F
1.9m Medium Tall
Amy
F
1.8m Medium Medium
x <90 >=90
xA
<80 >=80 xB
<70 >=70 xC
<50 >=60 FD
6
字母识别
一个字母由五个组成部分组成:
Letter A
Letter B
Letter C
Letter D
Letter E
Letter F
7
分类方法
步骤:
1. 通过对训练集进行计算产生一个特定 的模型。训练数据作为输入，以计算 得到的模型作为输出