数据挖掘: 技术及其应用 沙朝锋 复旦大学计算机科学与工程系.

Presentation on theme: "数据挖掘: 技术及其应用 沙朝锋 复旦大学计算机科学与工程系."— Presentation transcript:

1 数据挖掘: 技术及其应用 沙朝锋 复旦大学计算机科学与工程系

2 大纲 数据挖掘定义 分类问题 聚类问题 关联分析 文本挖掘 Web挖掘 社会网络分析 …

3 什么是数据挖掘? 从数据中识别有效的、新奇的、有用的以及可理解的模式的过程. 也称为KDD
数据库中的知识发现 (Knowledge Discovery in Databases) “We’re drowning in information, but starving for knowledge.” - John Naisbett

4 相关领域 机器学习 (Machine learning) 数据库 (Databases) 统计学 (Statistics)
信息检索 (Information retrieval) 可视化 (Visualization) 高性能计算 (High-performance computing) ...

5 相关领域 数据库 系统 统计学 数据挖掘 机器 学习 可视化 算法 其他领域

6 数据挖掘应用 电子商务 (E-commerce) 市场和零售 (Marketing and retail) 金融 (Finance)
电信 (Telecoms) 药物设计 (Drug design) 过程控制 (Process control) ...

7 数据挖掘过程 了解领域,先验知识,和目标 数据集成和选取 数据清洗和预处理 建模和模式搜索 解释结果 整理并使用发现的知识 循环

8 数据挖掘:一个KDD过程 Knowledge 数据挖掘—KDD过程的核心 模式评估 数据挖掘 任务相关的数据 数据仓库 选取 数据清洗
数据集成 数据库

9 数据挖掘和商务智能 做出 决策 数据表示 可视化技术 数据挖掘 信息发现 数据检查 统计分析, 查询和报告 数据仓库 / 数据超市
提升对 商务决策的 支持 最总用户 做出 决策 数据表示 商务 分析员 可视化技术 数据挖掘 数据 分析员 信息发现 数据检查 统计分析, 查询和报告 数据仓库 / 数据超市 OLAP, MDA DBA 数据源 论文, 文件, 信息提供商, 数据库系统, OLTP

10 框架:典型的数据挖掘系统 图形用户接口 模式评估 数据挖掘引擎 知识库 数据库或数据仓库服务器 过滤 数据清洗&集成 数据 仓库 数据库

11 数据挖掘:数据源 关系数据库 数据仓库 事务数据库 高级数据库和信息库 面向对象数据库 空间和时态数据库 时序数据 流数据 多媒体数据库
异种数据库 文本数据库 & WWW

12 数据挖掘任务 I 分类 (Classification) 回归分析 (Regression)
构造模型(函数)来描述和区分各种类别或概念用于未来的预测 表示: 决策树, 分类规则, 神经网络 预测未知或丢失的数值 信息提取 (Information extraction) 协同过滤 (Collaborative Filtering) 回归分析 (Regression) 概率估计 (Probability estimation)

13 数据挖掘任务 II 聚类 (Clustering) 关联发现 (Association detection)
类的标签未知: 对数据分组来形成新的类, 如: 对房子聚类来发现分布模式 把类内的相似性最大化 & 类间的相似性最小化 奇异点检测 关联发现 (Association detection) 尿布 à 啤酒 [0.5%, 75%] 总结 (Summarization) 趋势和偏差检测 (Trend and deviation detection) ...

14 分类: 定义 给定一个记录(样本)集合 (训练集 ) 找到一个将类别属性表示为其他属性的函数的模型. (如c = f(x))
每条记录有一些属性组成, 其中一个属性为类别. (x1, x2, …, xn, c) 找到一个将类别属性表示为其他属性的函数的模型. (如c = f(x)) 目标: 未见过的记录尽可能准确地被分类. 一个测试集用来确定模型的精度. 通常, 给定的数据集被分成训练集和测试集, 训练集用于建立模型, 而测试集用于检验该模型.

15 分类任务演示

16 分类任务例子 预测肿瘤细胞是良性还是恶性 将信用卡交易分为正常或是欺诈 对蛋白质的二级结构进行分类 手写体的识别: 0, 1, …, 9
过滤: 识别垃圾邮件

17 常用的方法 决策树 (Decision trees) 规则归纳 (Rule induction)
贝叶斯学习 (Bayesian learning) 神经网络 (Neural networks) 支持向量机 (Support Vector Machine) Ensemble方法 (AdaBoost, Bagging...) …

18 决策树例子 模型: 决策树 训练数据 划分属性 categorical continuous class Refund Yes No NO
MarSt Single, Divorced Married TaxInc NO < 80K > 80K NO YES 模型: 决策树 训练数据

19 另一个决策树例子 可能有多棵决策树拟合 同一个数据集! MarSt Single, Divorced categorical
continuous Married class NO Refund No Yes NO TaxInc < 80K > 80K NO YES 可能有多棵决策树拟合 同一个数据集!

20 决策树分类任务 决策树

21 对测试数据应用模型 从树的根节点开始. 测试数据 Refund MarSt TaxInc YES NO Yes No Married
Single, Divorced < 80K > 80K

22 对测试数据应用模型 测试数据 Refund MarSt TaxInc YES NO Yes No Married
Single, Divorced < 80K > 80K

23 对测试数据应用模型 测试数据 Refund Yes No NO MarSt Single, Divorced Married TaxInc
< 80K > 80K NO YES

24 对测试数据应用模型 测试数据 Refund Yes No NO MarSt Single, Divorced Married TaxInc
< 80K > 80K NO YES

25 对测试数据应用模型 测试数据 Refund Yes No NO MarSt Single, Divorced Married TaxInc
< 80K > 80K NO YES

26 对测试数据应用模型 Assign Cheat to “No” 测试数据 Refund Yes No NO MarSt Married
Single, Divorced TaxInc NO < 80K > 80K NO YES

27 决策树分类任务 决策树

28 决策树归纳 主要的几个算法: Hunt的算法 CART ID3, C4.5 SLIQ, SPRINT

29 Hunt算法的基本结构 记Dt为到达结点t的训练记录集 基本过程: ? 如果Dt包含的记录属于同一个类yt, 那么t为叶子结点, 标记为yt
如果Dt为空集, 那么t为标记为缺省类别yd的叶子结点 如果Dt包含属于多个类的记录, 使用属性测试将数据划分为更小的子集. 递归地对每个子集应用该过程. Dt ?

30 Hunt算法 Refund Refund Refund Marital Marital Status Status Taxable
Don’t Cheat Yes No Don’t Cheat Refund Don’t Cheat Yes No Marital Status Single, Divorced Married Refund Don’t Cheat Yes No Marital Status Single, Divorced Married Taxable Income < 80K >= 80K

31 树归纳 贪心策略. 问题 根据优化某个标准的属性测试来划分记录集. 确定如何划分记录 确定何时停止划分 使用哪个属性测试条件?
如何确定最优划分? 确定何时停止划分

32 基于规则的分类器 使用“if…then…”规则集对记录进行分类 规则: (条件)  类别 分类规则例子:
规则: (条件)  类别 分类规则例子: (Blood Type=Warm)  (Lay Eggs=Yes)  Birds (Taxable Income < 50K)  (Refund=Yes)  Evade=No

33 基于规则的分类器(例子) R1: (Give Birth = no)  (Can Fly = yes)  Birds
R2: (Give Birth = no)  (Live in Water = yes)  Fishes R3: (Give Birth = yes)  (Blood Type = warm)  Mammals R4: (Give Birth = no)  (Can Fly = no)  Reptiles R5: (Live in Water = sometimes)  Amphibians

34 Application of Rule-Based Classifier
一条规则r 覆盖 一个实例x : 如果该实例的属性满足规则的条件 R1: (Give Birth = no)  (Can Fly = yes)  Birds R2: (Give Birth = no)  (Live in Water = yes)  Fishes R3: (Give Birth = yes)  (Blood Type = warm)  Mammals R4: (Give Birth = no)  (Can Fly = no)  Reptiles R5: (Live in Water = sometimes)  Amphibians 规则 R1覆盖 hawk => Bird 规则 R3覆盖 grizzly bear => Mammal

35 规则的覆盖率和精度 规则的覆盖率: 规则的精度: 满足规则的前件的记录比率 同时满足规则前件和结果的记录比率
(Status=Single)  No Coverage = 40%, Accuracy = 50%

36 基于规则的分类器如何工作? R1: (Give Birth = no)  (Can Fly = yes)  Birds
R2: (Give Birth = no)  (Live in Water = yes)  Fishes R3: (Give Birth = yes)  (Blood Type = warm)  Mammals R4: (Give Birth = no)  (Can Fly = no)  Reptiles R5: (Live in Water = sometimes)  Amphibians lemur触发规则R3, 因此被分类为mammal turtle触发R4和R5 dogfish shark不触发任何规则

37 从决策树构造规则集

38 直接方法: 顺序覆盖 从空规则集开始 使用Learn-One-Rule函数增加一条规则 从训练记录集中删除被该规则覆盖的记录
重复步骤(2)和(3)直到满足停止标准

39 顺序覆盖例子

40 顺序覆盖例子…

41 最近邻分类器 基本思想: 如果一只动物走起来像鸭子, 叫起来像鸭子, 那么它可能是只鸭子 训练记录集 测试 记录 计算 距离
选k条“最近的” 记录

42 最近邻分类器 三个问题 存储的记录 计算记录间距离的距离度量 k值, 即要查找的最近邻个数 分类未知的记录: 计算到其他训练记录的距离
使用这些最近邻居的类标签来 确定未知记录的类别 (如: 根据 多数原则)

43 最近邻的定义 记录x的K-最近邻为到x的距离最小的k个数据点

44 1最近邻 Voronoi图

45 最近邻分类 计算两点之间的距离: 根据找到的最近邻确定类 欧几里德距离: 在k-最近邻中进行多数原则投票 根据距离对投票的分值计算权重
权重因子, w = 1/d2

46 最近邻分类… 选取k: 如果k太小, 对噪声点比较敏感 如果k太大, 邻居点会包含其他类的点

47 支持向量机 一个可能解

48 支持向量机 另一个可能解

49 支持向量机 其他可能解

50 支持向量机 哪一个更好? B1 还是 B2? 如何定义“更好”?

51 支持向量机 找到最大化“边际”的超平面 => B1比B2好

52 支持向量机

53 支持向量机 我们希望最大化: 等价于最小化: 但是有以下约束: 约束优化问题 各种数值方法来解该问题 (如: 二次规划)

54 Ensemble方法 从训练数据构造一些分类器 根据多个分类器所作的预测来预测未知记录的类

55 一般思想

56 Ensemble方法例子 如何产生一族分类器? Bagging Boosting AdaBoost

57 什么是聚类? 把数据聚类成多个簇 同一个簇中的数据相似 不同簇中数据不相似 非监督学习: 没有预先定义的类 簇1 聚类 2 奇异点

58 应用例子 独立的工具: 发现数据分布 作为其他算法的预处理步骤 模式识别, 空间数据分析, 图像处理, 市场研究, WWW, … 文档聚类
对web日志数据聚类来发现不同组的相同访问模式

59 聚类的概念是模糊的 多少个簇? 6个簇 2个簇 4个簇

60 聚类类型 聚类为簇的集合 划分型聚类 数据点划分为非交的子集 (簇), 使得每个数据点恰好在一个子集中 层次型聚类 嵌套的簇组织成一棵层次树

61 划分型聚类 划分聚类 原始数据点

62 层次型聚类 传统层次型聚类 传统树状图解 非传统层次性聚类 非传统树状图解

63 划分方法:K-Means 把每个对象分配给最相近的中心 更新簇的均值 重新分配 重新分配 K=2 任意地选取k个对象作为簇的初始中心点
1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 把每个对象分配给最相近的中心 5 更新簇的均值 4 3 2 1 1 2 3 4 5 6 7 8 9 10 重新分配 重新分配 K=2 任意地选取k个对象作为簇的初始中心点 更新簇的均值

64 两个不同的K-means聚类 原始数据点 最优聚类 次最优聚类

65 选取初始中心点的重要性

66 选取初始中心点的重要性

67 层次型聚类 产生嵌套的簇组织成的一棵层次树 可以可视化为树状图解

68 层次型聚类的优点 无需设定簇的个数 可能对应于多个有意义的分类 在合适的层次上分割树状图解可以产生任意个数的簇
如生物学中的例子 (如: 动物王国, 进化演变系统重构…)

69 层次型聚类 两类主要层次型聚类 传统的层次型算法使用一个相似度或距离矩阵 聚集型: 分裂型: 每次合并或分裂一个簇
开始时每个点都为单独一个簇 每步合并最近的两个簇直到只剩一个簇 (或k个簇) 分裂型: 开始时, 所有点都在同一个簇中 每步分裂一个簇, 直到每个簇包含一个点 (或者有k个簇) 传统的层次型算法使用一个相似度或距离矩阵 每次合并或分裂一个簇

70 聚集型层次聚类 更常见的层次型聚类技术 基本算法 关键操作是计算两个簇之间的相似度 Compute the proximity matrix
Let each data point be a cluster Repeat Merge the two closest clusters Update the proximity matrix Until only a single cluster remains 关键操作是计算两个簇之间的相似度 不同的算法定义了不同的簇之间的距离

71 开始状态 开始时每个点为一个簇, 并给定一个相近矩阵 p1 p3 p5 p4 p2 . . . . Proximity Matrix

72 中间状态 经过一些合并步骤后, 有了一些稍大的簇 Proximity Matrix C2 C1 C3 C5 C4 C3 C4 C1 C5

73 中间状态 合并最近的两个簇(C2和C5), 并更新相近矩阵 Proximity Matrix C2 C1 C3 C5 C4 C3 C4 C1

74 合并后 问题: 如何更新相近矩阵? Proximity Matrix C2 U C5 C1 C3 C4 C1 ? ? ? ? ?
问题: 如何更新相近矩阵? C2 U C5 C1 C3 C4 C1 ? ? ? ? ? C2 U C5 C3 C3 ? C4 ? C4 Proximity Matrix C1 C2 U C5

75 如何定义簇之间的相似度 MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差
p1 p3 p5 p4 p2 . . . . 相似度? MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差 Proximity Matrix

76 如何定义簇之间的相似度 MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差
p1 p3 p5 p4 p2 . . . . MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差 Proximity Matrix

77 如何定义簇之间的相似度 MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差
p1 p3 p5 p4 p2 . . . . MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差 Proximity Matrix

78 如何定义簇之间的相似度 MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差
p1 p3 p5 p4 p2 . . . . MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差 Proximity Matrix

79 如何定义簇之间的相似度 MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差
p1 p3 p5 p4 p2 . . . .   MIN MAX 组平均 中心点距离 由目标函数驱动的其他方法 Ward方法使用了平方误差 Proximity Matrix

80 簇相似性: MIN 或 Single Link 两个簇之间的相似度基于不同簇中最相似的两个点 由一对点确定, 即相近图中个一条link. 1
2 3 4 5

81 层次型聚类: MIN 5 1 2 3 4 5 6 4 3 2 1 Nested Clusters Dendrogram

82 簇相似性: MAX 或 Complete Linkage
两个簇之间的相似度基于不同簇中最不相似的两个点 由两个簇中所有点确定 1 2 3 4 5

83 层次型聚类: MAX 5 4 1 2 3 4 5 6 2 3 1 Nested Clusters Dendrogram

84 DIANA (DIvisive ANAlysis)
初始时,所有对象在一个簇中 一步步分裂形成小的簇

85 MST: 分裂型层次聚类 构造MST (最小生成树) 由任意某个点组成的树开始
以下的每一步, 找到p在树中而q不在树中的最近的点对(p, q) 将q加入到树中, 并添加p和q之间的边

86 MST: 分裂型层次聚类 使用MST构造簇的层次结构

87 基于密度的聚类: DBSCAN 簇: 密度连同的点的最大集合 在带噪声的空间数据库中发现任意形状的簇 异常点 边缘 Eps = 1cm
核心 边缘 异常点 Eps = 1cm MinPts = 5

88 关联规则挖掘 频繁模式: 数据库中频繁出现的模式 (项的集合,序列等) [AIS93] 频繁模式挖掘: 从数据中找出规律
哪些产品通常是一起购买的? 啤酒和尿布?! 买了一辆汽车后还会购买哪些产品? 是否可以对顾客自动分类?

89 为何重要？ 许多数据挖掘任务的基础 广泛的应用 关联规则, 相关性, 顺序模式, 空间和多媒体模式, 关联分类, 聚类分析, …
篮子数据分析, 交叉-市场供应, 目录设计, 销售活动分析, web日志(点击流)分析, …

90 基础 项集: 项的集合 项集支持度 给定 min_sup=3, 那么acm是一个频繁模式 频繁模式挖掘: 从数据库中找出所有的频繁模式
如: acm={a, c, m} 项集支持度 Sup(acm)=3 给定 min_sup=3, 那么acm是一个频繁模式 频繁模式挖掘: 从数据库中找出所有的频繁模式 交易数据库 TDB TID 购买的项 100 f, a, c, d, g, I, m, p 200 a, b, c, f, l,m, o 300 b, f, h, j, o 400 b, c, k, s, p 500 a, f, c, e, l, p, m, n

91 频繁模式挖掘方法 Apriori和各种变体/改进 不产生候选项的频繁模式挖掘 最大模式和封闭项集挖掘 带各种可调约束的多维,多层频繁模式挖掘
各种兴趣度: 相关性

92 Apriori: 候选项产生和测试 频繁项集的任何子集都是频繁的 — 反单调性 非频繁项集的超集不需要被产生或测试
一个包含{beer, diaper, nuts}的交易同样包含 {beer, diaper} {beer, diaper, nuts}是频繁的  {beer, diaper}肯定也是频繁的 非频繁项集的超集不需要被产生或测试 大量项的组合可以被排除

93 Apriori Algorithm 基于层的候选项产生和测试方法(Agrawal & Srikant 1994) 数据库 D 1-候选项
频繁 1-项集 2-候选项 TID Items 10 a, c, d 20 b, c, e 30 a, b, c, e 40 b, e Itemset Sup a 2 b 3 c d 1 e Itemset Sup a 2 b 3 c e Itemset ab ac ae bc be ce 扫描 D Min_sup=2 3-候选项 频繁 2-项集 计数 扫描 D Itemset bce Itemset Sup ac 2 bc be 3 ce Itemset Sup ab 1 ac 2 ae bc be 3 ce 扫描 D 频繁 3-项集 Itemset Sup bce 2

94 Apriori 算法 Ck: Candidate itemset of size k
Lk : frequent itemset of size k L1 = {frequent items}; for (k = 1; Lk !=; k++) do Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support return k Lk;