数据挖掘 —— 期末复习
第一章、数据挖掘概论
数据挖掘, 数据库中的知识挖掘 (KDD)
? 数据挖掘 —— 知识挖掘
的核心
数据清理
数据集成
数据库
数据仓库
任务相关数据
选择
数据挖掘
模式评估
知识挖掘的步骤
? 了解应用领域
? 了解相关的知识和应用的目标
? 创建目标数据集, 选择数据
? 数据清理和预处理, (这个可能要占全过程 60％的工作量 )
? 数据缩减和变换
? 找到有用的特征，维数缩减 /变量缩减，不变量的表示。
? 选择数据挖掘的功能
? 数据总结,分类模型数据挖掘,回归分析,关联规则挖掘,聚类分析
等,
? 选择挖掘算法
? 数据挖掘, 寻找感兴趣的模式
? 模式评估和知识表示
? 可视化，转换，消除冗余模式等等
? 运用发现的知识
体系结构,典型数据挖掘系统
数据仓库
数据清洗 过滤
数据库
数据库或数据仓库服务器
数据挖掘引擎
模式评估
图形用户界面
知识库
数据集成
数据挖掘的主要功能
? 概念 /类描述, 特性化和区分
? 归纳，总结和对比数据的特性。
? 关联分析
? 发现数据之间的关联规则，这些规则展示属性－值频繁的在给定的数据中所一
起出现的条件。
? 分类和预测
? 通过构造模型 (或函数 )用来描述和区别类或概念，用来预测类型标志未知的对
象类。
? 聚类分析
? 将类似的数据归类到一起，形成一个新的类别进行分析。
? 孤立点分析
? 通常孤立点被作为“噪音”或异常被丢弃，但在欺骗检测中却可以通过对罕见 事件进行孤立点分析而得到结论。
? 趋势和演变分析
? 描述行为随时间变化的对象的发展规律或趋势
数据挖掘,多个学科的融合
数据挖掘
数据库系统 统计学
其他学科 算法
机器学习 可视化
数据挖掘的主要问题
? 挖掘方法
? 在不同的数据类型中挖掘不同类型的知识,e.g.,生物数据,流式数据,Web数据
? 性能, 算法的有效性、可伸缩性和并行处理
? 模式评估, 兴趣度问题
? 背景知识的合并
? 处理噪声何不完全数据
? 并行,分布式和增量挖掘算法
? 新发现知识与已有知识的集成, 知识融合
? 用户交互
? 数据挖掘查询语言和特定的数据挖掘
? 数据挖掘结果的表示和显示
? 多个抽象层的交互知识挖掘
? 应用和社会因素
? 特定域的数据挖掘 & 不可视的数据挖掘
? 数据安全,完整和保密的保护
第二章、数据仓库和 OLAP技术
什么是数据仓库?
? 数据仓库的定义很多，但却很难有一种严格的定义
? 它是一个提供决策支持功能的数据库，它与公司的操作数据
库分开维护。
? 为统一的历史数据分析提供坚实的平台，对信息处理提供支
持
?,数据仓库是一个面向主题的、集成的、随时间而变
化的、不容易丢失的数据集合，支持管理部门的决策
过程,”— W,H,Inmon（数据仓库构造方面的领头设计
师）
? 建立数据仓库 (data warehousing),
? 构造和使用数据仓库的过程。
数据仓库与异种数据库集成
? 传统的异种数据库集成,
? 在多个异种数据库上建立包装程序（ wrappers）和中介程序
（ mediators ）
? 查询驱动方法 —— 当从客户端传过来一个查询时，首先使用
元数据字典将查询转换成相应异种数据库上的查询；然后，
将这些查询映射和发送到局部查询处理器
? 缺点：复杂的信息过虑和集成处理，竞争资源
? 数据仓库, 更新驱动
? 将来自多个异种源的信息预先集成，并存储在数据仓库中，
供直接查询和分析
? 高性能
OLTP系统和 OLAP系统的比较
特征 OLTP OLAP
任务特点 操作处理 信息处理
面向 事务 分析
用户 办事员,DBA、数据库专业人员 经理、主管、数据分析员
功能 日常操作 长期信息分析、决策支持
DB设计 基于 E-R，面向应用 星型 /雪花，面向主体
数据 最新的、详细的 历史的、汇总的
视图 详细的、二维关系型 汇总的、多维的
任务单位 简短的事务 复杂的查询
访问数据量 数十个 数百万个
用户数 数千个 数百个
DB规模 100M-数 GB 100GB-数 TB
优先性 高性能、高可用性 高灵活性、端点用户自治
度量 事务吞吐量 查询吞吐量、响应时间
从关系表和电子表格到数据立方体
? 数据仓库和数据仓库技术基于 多维数据模型 。这个模型把数据看
作是 数据立方体 形式。多维数据模型围绕中心主题组织，该主题
用 事实表 表示。 事实 是数值度量的。
? 数据立方体 允许以多维数据建模和观察。它由 维 和 事实 定义。
? 维 是关于一个组织想要记录的视角或观点。每个维都有一个表与
之相关联，称为 维表 。
? 事实表 包括事实的名称或度量以及每个相关维表的关键字
? 在数据仓库的研究文献中，一个 n维的数据的立方体叫做 基本方体 。
给定一个维的集合，我们可以构造一个 方体的格,每个都在不同
的汇总级或不同的数据子集显示数据，方体的格称为 数据立方体 。
0维方体存放最高层的汇总，称作 顶点方体 ；而存放最底层汇总的
方体则称为 基本方体 。
度量的分类
? 一个数据立方体的度量是一个数值函数，该函数可以
对数据立方体的每一个点求值。度量可以根据其所用
的聚集函数分为三类,
? 分布的 (distributive)：将函数用于 n个聚集值得到的结果和将
函数用于所有数据得到的结果一样。
? 比如,count(),sum(),min(),max()等
? 代数的 (algebraic)：函数可以由一个带 M个参数的代数函数
计算（ M为有界整数），而每个参数值都可以有一个分布的
聚集函数求得。
? 比如,avg(),min_N(),standard_deviation()
? 整体的 (holistic)：描述函数的子聚集所需的存储没有一个常
数界。
? 比如,median(),mode(),rank()
概念分层,location维的一个概念分层
all
Europe North_America
Mexico Canada Spain Germany
Vancouver
M,Wind L,Chan
..,
...,.,
...,.,
..,
all
region
office
country
Toronto Frankfurt city
多维数据模型上的 OLAP操作
? 上卷 (roll-up):汇总数据
? 通过一个维的概念分层向上攀升或者通过维规约
? 下钻 (drill-down)：上卷的逆操作
? 由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下 或引入新的维来实现
? 切片和切块 (slice and dice)
? 投影和选择操作
? 转轴 (pivot)
? 立方体的重定位，可视化，或将一个 3维立方体转化维一个 2维平
面序列
? 其他 OLAP操作
? 钻过 (drill_across)：执行涉及多个事实表的查询
? 钻透 (drill_through)：使用关系 SQL机制，钻到数据立方体的底层，
到后端关系表
数据仓库设计的四种视图
? 数据仓库设计的四种视图
? 自顶向下视图
? 允许我们选择数据仓库所需的相关信息
? 数据源视图
? 揭示被操作数据库系统所捕获、存储和管理的信息
? 数据仓库视图
? 有事实表和维表所组成
? 商务查询视图
? 从最终用户的角度透视数据仓库中的数据
三种数据仓库模型
? 企业仓库
? 搜集关于跨越整个组织的主题的所有信息
? 数据集市
? 企业范围数据的一个子集，对于特定的客户是有用的。其范
围限于选定的主题，比如一个商场的数据集市
? 独立的数据集市 VS,非独立的数据集市（数据来自于企业数据
仓库）
? 虚拟仓库
? 操作数据库上的一系列视图
? 只有一些可能的汇总视图被物化
OLAP服务器类型
? 逻辑上,OLAP服务器从数据仓库或数据集市中给商业用户提供多
维数据
? 物理上,OLAP的底层数据存储实现可以有多种不同的方式
? 关系 OLAP服务器 (ROLAP)
? 使用关系数据库或扩展的关系数据库存放并管理数据仓库的数据，而
用 OLAP中间件支持其余部分
? 包括每个 DBMS后端优化，聚集导航逻辑的实现，附加的工具和服务
? 较大的可扩展性
? 多维 OLAP服务器 (MOLAP)
? 基于数组的多维存储引擎（稀疏矩阵技术）
? 能对预计算的汇总数据快速索引
? 混合 OLAP服务器 (HOLAP)
? 结合上述两种技术，更大的使用灵活性
? 特殊的 SQL服务器
? 在星型和雪花模型上支持 SQL查询
方体计算的多路数组聚集方法 (1)
? 将数组分成块（ chunk,一个可以装入内存的小子方）
? 压缩的稀疏数组寻址,(chunk_id,offset)
? 通过访问立方体单元，计算聚集。可以优化访问单元组的次序，
使得每个单元被访问的次数最小化，从而减少内存访问和磁盘 I/O
的开销。
A(month)
B
29 30 31 32
1 2 3 4
5
9
13 14 15 16
64 63 62 61 48 47 46 45
a1 a0
c3 c2
c1 c 0
b3
b2
b1
b0
a2 a3
C(item)
B(city)
44 28
56 40
24 52
36 20
60 哪个是多路数组
聚集的最佳遍历
次序？
第三章、数据预处理
为什么要预处理数据？
? 现实世界的数据是“肮脏的”
? 不完整的：有些感兴趣的属性缺少属性值，或仅包
含聚集数据
? 含噪声的：包含错误或者“孤立点”
? 不一致的：在编码或者命名上存在差异
? 没有高质量的数据，就没有高质量的挖掘结果
? 高质量的决策必须依赖高质量的数据
? 数据仓库需要对高质量的数据进行一致地集成
数据预处理的主要任务
? 数据清理
? 填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性
? 数据集成
? 集成多个数据库、数据立方体或文件
? 数据变换
? 规范化和聚集
? 数据归约
? 得到数据集的压缩表示，它小得多，但可以得到相同或相近
的结果
? 数据离散化
? 数据归约的一部分，通过概念分层和数据的离散化来规约数据,对数字型数据特别重要
如何处理空缺值
? 忽略元组：当类标号缺少时通常这么做（假定挖掘任
务设计分类或描述），当每个属性缺少值的百分比变
化很大时，它的效果非常差。
? 人工填写空缺值：工作量大，可行性低
? 使用一个全局变量填充空缺值：比如使用 unknown或
-∞
? 使用属性的平均值填充空缺值
? 使用与给定元组属同一类的所有样本的平均值
? 使用最可能的值填充空缺值：使用像 Bayesian公式或
判定树这样的基于推断的方法
噪声数据
? 噪声：一个测量变量中的随机错误或偏差
? 引起不正确属性值的原因
? 数据收集工具的问题
? 数据输入错误
? 数据传输错误
? 技术限制
? 命名规则的不一致
? 其它需要数据清理的数据问题
? 重复记录
? 不完整的数据
? 不一致的数据
如何处理噪声数据
? 分箱 (binning),
? 首先排序数据，并将他们分到等深的箱中
? 然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平
滑等等
? 聚类,
? 监测并且去除孤立点
? 计算机和人工检查结合
? 计算机检测可疑数据，然后对它们进行人工判断
? 回归
? 通过让数据适应回归函数来平滑数据
数据变换
? 平滑：去除数据中的噪声 （分箱、聚类、回归）
? 聚集：汇总，数据立方体的构建
? 数据概化：沿概念分层向上汇总
? 规范化：将数据按比例缩放，使之落入一个小的特定
区间
? 最小－最大规范化
? z-score规范化
? 小数定标规范化
? 属性构造
? 通过现有属性构造新的属性，并添加到属性集中；以增加对
高维数据的结构的理解和精确度
数据归约策略
? 数据仓库中往往存有海量数据，在其上进行复杂的数
据分析与挖掘需要很长的时间
? 数据归约
? 数据归约可以用来得到数据集的归约表示，它小得多，但可
以产生相同的（或几乎相同的）分析结果
? 数据归约策略
? 数据立方体聚集
? 维归约
? 数据压缩
? 数值归约
? 离散化和概念分层产生
? 用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。
分类数据的概念分层生成
? 分类数据是指无序的离散数据，它有有限个值（可能
很多个）。
? 分类数据的概念分层生成方法,
? 由用户或专家在模式级显式的说明属性的部分序。
? 通过显示数据分组说明分层结构的一部分。
? 说明属性集，但不说明它们的偏序，然后系统根据算法自动
产生属性的序，构造有意义的概念分层。
? 对只说明部分属性集的情况，则可根据数据库模式中的数据
语义定义对属性的捆绑信息，来恢复相关的属性。
第四章、数据挖掘原语和 DMQL
数据挖掘原语的组成部分
? 数据挖掘原语应该包括以下部分,
? 说明数据库的部分或用户感兴趣的数据集
? 要挖掘的知识类型
? 用于指导挖掘的背景知识
? 模式评估、兴趣度量
? 如何显示发现的知识
? 数据挖掘原语用于用户和数据挖掘系统通信，让用户
能从不同的角度和深度审查和发现结果，并指导挖掘
过程。
说明数据挖掘任务的原语
? 任务相关的数据
? 数据库（仓库）名、数据立方体、选择条件、相关属性、分组条件
? 挖掘的知识类型
? 特征化、区分、关联、分类 /预测、聚类
? 背景知识
? 概念分层，关联的确信度
? 模式兴趣度度量
? 简单性、确定性、实用性、新颖性
? 发现模式的可视化
? 规则、表、图表、图、判定树 …
兴趣度度量
? 没有兴趣度度量，挖掘出来的有用模式，很可
能会给淹没在用户不感兴趣的模式中。
? 简单性
? 确定性
? 实用性
? 新颖性
? 兴趣度的客观度量方法：根据模式的结构和统
计，用一个临界值来判断某个模式是不是用户
感兴趣的。
第五章、特征化和比较
两种不同类别的数据挖掘
? 从数据分析的角度看，数据挖掘可以分为描述
性挖掘和预测性挖掘
? 描述性挖掘：以简洁概要的方式描述数据，并提供
数据的有趣的一般性质。
? 预测性数据挖掘：通过分析数据建立一个或一组模
型，并试图预测新数据集的行为。
什么是概念描述？
? 描述性挖掘 VS,预测性挖掘
? 描述性挖掘：以简洁概要的方式描述数据，并提供
数据的有趣的一般性质。
? 预测性数据挖掘：通过分析数据建立一个或一组模
型，并试图预测新数据集的行为。
? 概念描述：为数据的特征化和比较产生描述
（当所描述的概念所指的是一类对象时，也称
为 类描述 ）
? 特征化：提供给定数据集的简洁汇总。
? 区分：提供两个或多个数据集的比较描述。
数据概化
? 数据概化
? 数据库中的数据和对象通常包含原始概念层的细节信息，数
据概化就是将数据库中的跟任务相关的数据集从较低的概念
层抽象到较高的概念层的过程。
? 主要方法,
? 数据立方体（ OLAP使用的方法）
? 面向属性的归纳方法
1
2
3
4
5 概念层
面向属性的归纳
? Attribute-oriented induction,AOI (KDD `89
Workshop)
? 受数据类型和度量类型的约束比较少
? 面向属性归纳的基本思想,
? 使用关系数据库查询收集任务相关的数据
? 通过考察任务相关数据中每个属性的不同值的个数进行概化，
方法是属性删除或者是属性概化
? 通过合并相等的，概化的广义元组，并累计他们对应的计数
值进行聚集操作
? 通过与用户交互，将广义关系以图表或规则等形式，提交给
用户
面向属性的归纳的基本步骤
? 数据聚焦，获得初始工作关系
? 进行面向属性的归纳
? 基本操作是数据概化，对有 大量不同值的属性,进
行进一步概化
? 属性删除
? 属性概化
? 属性概化控制：控制概化过程，确定有多少不同的
值才算是有 大量不同值的属性
? 属性概化临界值控制
? 概化关系临界值控制
概念描述的属性相关分析步骤 (1)
? 数据收集
? 通过查询处理，收集目标类和对比类数据
? 使用保守的 AOI进行预相关分析
? 识别属性和维的集合，它们是所选择的相关性分析度量的应
用对象
? 因为不同的概念层对某个类描述的相关性可能很不同，因此
在这个过程中同时要包含概念分层
? 对有大量不同值的属性进行删除或概化
? 在这一级进行概化时，临界值要相应比较高，以便在后续步
骤的分析中包含更多属性（保守的）
? 产生候选关系
概念描述的属性相关分析步骤 (2)
? 使用选定的相关分析度量删除不相关和弱相关
的属性
? 使用选定的相关分析度量（ e.g.信息增益），评估
候选关系中的每个属性
? 根据所计算的相关性对属性进行排序
? 低于临界值的不相关和弱相关的属性被删除
? 产生初始目标类工作关系（或初始对比类工作关系）
? 使用 AOI产生概念描述
? 使用一组不太保守的属性概化临界值进行 AOI
挖掘类比较：区分不同的类
? 类比较挖掘的目标是得到将目标类与对比类相区分的
描述。
? 目标类和对比类间必须具有可比性，即两者间要有相似的属
性或维。
? 本科生 VS,研究生 ； student VS,address
? 很多应用于概念描述的技巧可以应用于类比较，比如
属性概化。
? 属性概化必须在所有比较类上同步进行，将属性概化到同一
抽象层后进行比较。
? City VS country
类比较的过程
? 数据收集
? 通过查询处理收集数据库中相关的数据，并将其划分为一个目标类
和一个或多个对比类
? 维相关分析
? 使用属性相关分析方法，使我们的任务中仅包含强相关的维
? 同步概化
? 同步的在目标类和对比类上进行概化，得到 主目标类关系 /方体 和
主对比类关系 /方体
? 导出比较的表示
? 用可视化技术表达类比较描述，通常会包含“对比”度量，反映目
标类与对比类间的比较 (e.g count%)
在大型数据库中挖掘描述统计计量
? 对于数据挖掘任务，用户经常关心的数据特征包括数
据的中心趋势和离散特征
? 中心趋势的度量包括,mean,median,mode 和 midrange
? 数据离散度量包括,quartiles,五数概括和标准差等
? 关系数据库中，系统提供了以下聚集函数,count(),sum(),
avg(),max(),min()
? 在大型数据库中挖掘用户感兴趣的描述统计计量涉及到如何
利用关系数据库现有的函数来计算上述两类用户感兴趣的度
量值
第六章、关联规则挖掘
什么是关联规则挖掘？
? 关联规则挖掘,
? 从事务数据库，关系数据库和其他信息存储中的大
量数据的项集之间发现有趣的、频繁出现的模式、
关联和相关性。
? 应用,
? 购物篮分析、分类设计、捆绑销售和亏本销售分析
关联规则：基本概念
? 给定,
? 项的集合,I={i1,i2,...,in}
? 任务相关数据 D是数据库事务的集合，每个事务 T则
是项的集合，使得
? 每个事务由事务标识符 TID标识；
? A,B为两个项集，事务 T包含 A当且仅当
? 则关联规则是如下蕴涵式,
? 其中 并且,规则 在事
务集 D中成立，并且具有支持度 s和置信度 c
IT ?
TA?
],[ csBA ?
IBIA ??,??? BA BA ?
Apriori算法
? Apriori算法利用频繁项集性质的先验知识（ prior
knowledge），通过逐层搜索的迭代方法，即将 k-项
集用于探察 (k+1)-项集，来穷尽数据集中的所有频繁
项集。
? 先找到频繁 1-项集集合 L1,然后用 L1找到频繁 2-项集集合 L2，
接着用 L2找 L3，直到找不到频繁 k-项集，找每个 Lk需要一次
数据库扫描。
? Apriori性质：频繁项集的所有非空子集也必须是频繁
的。（ 模式不可能比 A更频繁的出现）
? Apriori算法是反单调的，即一个集合如果不能通过测试，则
该集合的所有超集也不能通过相同的测试。
BA ?
Apriori算法步骤
? Apriori算法由 连接 和 剪枝 两个步骤组成。
? 连接,为了找 Lk，通过 Lk-1与自己连接产生候选 k-项集
的集合，该 候选 k项集 记为 Ck。
? Lk-1中的两个元素 L1和 L2可以执行连接操作 的条件是
? 剪枝,Ck是 Lk的超集，即它的成员可能不是频繁的，
但是所有频繁的 k-项集都在 Ck中（为什么？）。因此
可以通过扫描数据库，通过计算每个 k-项集的支持度
来得到 Lk 。
? 为了减少计算量，可以使用 Apriori性质，即如果一个 k-项集
的 (k-1)-子集不在 Lk-1中，则该候选不可能是频繁的，可以直
接从 Ck删除。
])1[]1[(])2[]2[(...])2[]2[(])1[]1[( 21212121 ???????????? klklklklllll
21 ll ??
Apriori算法 —— 示例
Database TDB
1st scan
C1 L1
L2
C2 C2
2nd scan
C3 L3 3rd scan
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} 3
{D} 1
{E} 3
Itemset sup
{A} 2
{B} 3
{C} 3
{E} 3
Itemset
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
Itemset sup
{A,B} 1
{A,C} 2
{A,E} 1
{B,C} 2
{B,E} 3
{C,E} 2
Itemset sup
{A,C} 2
{B,C} 2
{B,E} 3
{C,E} 2
Itemset
{B,C,E}
Itemset sup
{B,C,E} 2
使用 Apiori性质由 L2产生 C3
? 1,连接,
? C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}}
{{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}
? 2．使用 Apriori性质剪枝：频繁项集的所有子集必须是频繁的，
对候选项 C3，我们可以删除其子集为非频繁的选项,
? {A,B,C}的 2项子集是 {A,B},{A,C},{B,C}，其中 {A,B}不是 L2的元素，
所以删除这个选项；
? {A,C,E}的 2项子集是 {A,C},{A,E},{C,E}，其中 {A,E} 不是 L2的元素，
所以删除这个选项；
? {B,C,E}的 2项子集是 {B,C},{B,E},{C,E}，它的所有 2－项子集都是
L2的元素，因此保留这个选项。
? 3．这样，剪枝后得到 C3={{B,C,E}}
????
多层关联 —— 一致支持度 VS,递减支持度
? 一致支持度：对所有层都使
用一致的最小支持度
? 优点：搜索时容易采用优化
策略，即一个项如果不满足
最小支持度，它的所有子项都可以不用搜索
? 缺点：最小支持度值设置困难
? 太高：将丢掉出现在较低抽
象层中有意义的关联规则
? 太低：会在较高层产生太多
的无兴趣的规则
? 递减支持度：在较低层使用递减的最小支持度
? 抽象层越低，对应的最小支
持度越小
Computer
[support=10%]
Laptop
[support=6%]
Desktop
[support=4%]
min_sup = 5%
min_sup = 5% 3%
多层关联 —— 搜索策略
? 具有递减支持度的多层关联规则的搜索策略
? 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝
? 层交叉单项过滤：一个第 i层的项被考察，当且仅当它在第
（ i-1）层的父节点是频繁的（图 6-14）
? 层交叉 k项集过滤：一个第 i层的 k项集被考察，当且仅当它在
第 (i-1)层的对应父节点 k-项集是频繁的（图 6-15）
? 搜索策略比较
? 逐层独立策略条件松，可能导致底层考察大量非频繁项
? 层交叉 k项集过滤策略限制太强，仅允许考察频繁 k-项集的子
女
? 层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层
频繁项（图 6-14)
关联规则的兴趣度度量
? 客观度量
? 两个流行的度量指标
? 支持度
? 置信度
? 主观度量
? 最终，只有用户才能确定一个规则是否有趣的，而且这种判
断是主观的，因不同的用户而异；通常认为一个规则（模式）
是有趣的，如果,
? 它是出人意料的
? 可行动的（用户可以使用该规则做某些事情）
? 挖掘了关联规则后，哪些规则是用户感兴趣的？强关
联规则是否就是有趣的？
第七章、分类和预测
分类 VS,预测
? 分类,
? 预测分类标号（或离散值）
? 根据训练数据集和类标号属性，构建模型来分类现有数据，
并用来分类新数据
? 预测,
? 建立连续函数值模型，比如预测空缺值
? 典型应用
? 信誉证实
? 目标市场
? 医疗诊断
? 性能预测
数据分类 —— 一个两步过程
? 第一步，建立一个模型，描述预定数据类集和概念集
? 假定每个元组属于一个预定义的类，由一个类标号属性确定
? 基本概念
? 训练数据集,由为建立模型而被分析的数据元组形成
? 训练样本,训练数据集中的单个样本（元组）
? 学习模型可以用分类规则、判定树或数学公式的形式提供
? 第二步，使用模型，对将来的或未知的对象进行分类
? 首先评估模型的预测准确率
? 对每个测试样本，将已知的类标号和该样本的学习模型类预测比较
? 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比
? 测试集要独立于训练样本集，否则会出现“过分适应数据”的情况
有指导的学习 VS,无指导的学习
? 有指导的学习（用于分类）
? 模型的学习在被告知每个训练样本属于哪个类的
“指导”下进行
? 新数据使用训练数据集中得到的规则进行分类
? 无指导的学习（用于聚类）
? 每个训练样本的类编号是未知的，要学习的类集合
或数量也可能是事先未知的
? 通过一系列的度量、观察来建立数据中的类编号或
进行聚类
比较分类方法
? 使用下列标准比较分类和预测方法
? 预测的准确率：模型正确预测新数据的类编号的能
力
? 速度：产生和使用模型的计算花销
? 健壮性：给定噪声数据或有空缺值的数据，模型正
确预测的能力
? 可伸缩性：对大量数据，有效的构建模型的能力
? 可解释性：学习模型提供的理解和洞察的层次
用判定树归纳分类
? 什么是判定树？
? 类似于流程图的树结构
? 每个内部节点表示在一个属性上的测试
? 每个分枝代表一个测试输出
? 每个树叶节点代表类或类分布
? 判定树的生成由两个阶段组成
? 判定树构建
? 开始时，所有的训练样本都在根节点
? 递归的通过选定的属性，来划分样本 （必须是离散值）
? 树剪枝
? 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检 测和剪去这种分枝
? 判定树的使用：对未知样本进行分类
? 通过将样本的属性值与判定树相比较
贝叶斯分类
? 贝叶斯分类利用统计学中的
贝叶斯定理，来预测类成员
的概率，即给定一个样本，
计算该样本属于一个特定的
类的概率。
? 朴素贝叶斯分类：假设每个
属性之间都是相互独立的，
并且每个属性对非类问题产
生的影响都是一样的。
)(
)()|()|(
DP
hPhDPDhP ?
后向传播分类
? 后向传播是一种神经网络学习算法；神经网络是一组
连接的输入 /输出单元，每个连接都与一个权相连。在
学习阶段，通过调整神经网络的权，使得能够预测输
入样本的正确标号来学习。
? 优点
? 预测精度总的来说较高
? 健壮性好，训练样本中包含错误时也可正常工作
? 输出可能是离散值、连续值或者是离散或量化属性的向量值
? 对目标进行分类较快
? 缺点
? 训练（学习）时间长
? 蕴涵在学习的权中的符号含义很难理解
? 很难根专业领域知识相整合
什么是预测？
? 预测是构造和使用模型评估无样本类，或评估给定样
本可能具有的属性或值空间。
? 预测和分类的异同
? 相同点
? 两者都需要构建模型
? 都用模型来估计未知值
? 预测当中主要的估计方法是回归分析
? 线性回归和多元回归
? 非线性回归
? 不同点
? 分类法主要是用来预测类标号（分类属性值）
? 预测法主要是用来估计连续值（量化属性值）
第八章、聚类分析
什么是聚类分析？
? 聚类（簇）：数据对象的集合
? 在同一个聚类（簇）中的对象彼此相似
? 不同簇中的对象则相异
? 聚类分析
? 将物理或抽象对象的集合分组成为由类似的对象组成的多个
类的过程
? 聚类是一种无指导的学习：没有预定义的类编号
? 聚类分析的数据挖掘功能
? 作为一个独立的工具来获得数据分布的情况
? 作为其他算法（如：特征和分类）的预处理步骤
聚类分析的典型应用
? 模式识别
? 空间数据分析
? 在 GIS系统中，对相似区域进行聚类，产生主题地图
? 检测空间聚类，并给出它们在空间数据挖掘中的解释
? 图像处理
? 经济学（尤其是市场研究）
? 万维网
? 对 WEB上的文档进行分类
? 对 WEB日志的数据进行聚类，以发现相同的用户访问模式
主要的聚类方法
? 聚类分析算法种类繁多，具体的算法选择取决于数据
类型，聚类的应用和目的，常用的聚类算法包括,
? 划分方法
? 层次的方法
? 基于密度的方法
? 基于网格的方法
? 基于模型的方法
? 实际应用中的聚类算法，往往是上述聚类方法中多种
方法的整合
孤立点挖掘
? 什么是孤立点？
? 一个数据集与其他数据有着显著区别的数据对象的集合
? 例如：运动员,Michael Jordon,舒马赫，布勃卡
? 孤立点产生原因
? 度量或执行错误（年龄,-999）
? 数据变异的结果
? 孤立点挖掘
? 给定一个 n个数据对象的集合，以及预期的孤立点数目 k，发现与
剩余的数据有着显著差异的头 k个数据对象
? 应用
? 信用卡欺诈检测
? 移动电话欺诈检测
? 客户划分
? 医疗分析（异常）
电子商务与数据挖掘
电子商务与数据挖掘 —— 完美结合
? 在电子商务中进行成功的数据挖掘得益于,
? 电子商务提供海量的数据
? 如果一个电子商务网站平均每个小时卖出五件物品，那么它一 个月的平均点击量是 160万次。
? 丰富的记录信息
? 良好的 WEB站点设计将有助于获得丰富的信息
? 干净的数据
? 从电子商务站点收集的都是电子数据，无需人工输入或者是从 历史系统进行整合
? 研究成果容易转化
? 在电子商务中，很多知识发现都可以进行直接应用
? 投资收益容易衡量
对电子商务网站的 Web数据挖掘
? 通常在一个电子商务网站上应用的数据挖掘技
术是 Web数据挖掘。
? 我们可以在一个电子商务网站挖掘些什么东西？
? 内容挖掘 (Web Content Mining)
? 结构挖掘 (Web Structure Mining)
? 使用挖掘 (Web Usage Mining)
Web Usage Mining
? 与 Web Content Mining和 Web Structure Mining不同
的是,Web Usage Mining的挖掘对象是用户和网络
交互过程中抽取出来的二手数据，这些数据主要是用
户在访问 Web时在 Web日志里留下的信息，以及其它
一些交互信息,
? 日志信息包括访问日期、时间、用户 IP地址、服务器 IP地址、
方法、所请求 URL资源、服务器响应状态、用户代理、发送
字节等。
? Web Usage Mining就是对系统日志信息，以及用户的注册
数据等进行挖掘，以发现有用的模式和知识。
Web Usage Mining的作用
? 通过对电子商务网站应用 Web Usage Mining
数据挖掘技术，可以
? 提高站点的质量
? 改善 WEB缓存，缓解网络交通，提高性能
? 在电子商务中还可捕捉到大量的采购过程的细节，
为更加深入的分析提供了可能
第一章、数据挖掘概论
数据挖掘, 数据库中的知识挖掘 (KDD)
? 数据挖掘 —— 知识挖掘
的核心
数据清理
数据集成
数据库
数据仓库
任务相关数据
选择
数据挖掘
模式评估
知识挖掘的步骤
? 了解应用领域
? 了解相关的知识和应用的目标
? 创建目标数据集, 选择数据
? 数据清理和预处理, (这个可能要占全过程 60％的工作量 )
? 数据缩减和变换
? 找到有用的特征，维数缩减 /变量缩减，不变量的表示。
? 选择数据挖掘的功能
? 数据总结,分类模型数据挖掘,回归分析,关联规则挖掘,聚类分析
等,
? 选择挖掘算法
? 数据挖掘, 寻找感兴趣的模式
? 模式评估和知识表示
? 可视化，转换，消除冗余模式等等
? 运用发现的知识
体系结构,典型数据挖掘系统
数据仓库
数据清洗 过滤
数据库
数据库或数据仓库服务器
数据挖掘引擎
模式评估
图形用户界面
知识库
数据集成
数据挖掘的主要功能
? 概念 /类描述, 特性化和区分
? 归纳，总结和对比数据的特性。
? 关联分析
? 发现数据之间的关联规则，这些规则展示属性－值频繁的在给定的数据中所一
起出现的条件。
? 分类和预测
? 通过构造模型 (或函数 )用来描述和区别类或概念，用来预测类型标志未知的对
象类。
? 聚类分析
? 将类似的数据归类到一起，形成一个新的类别进行分析。
? 孤立点分析
? 通常孤立点被作为“噪音”或异常被丢弃，但在欺骗检测中却可以通过对罕见 事件进行孤立点分析而得到结论。
? 趋势和演变分析
? 描述行为随时间变化的对象的发展规律或趋势
数据挖掘,多个学科的融合
数据挖掘
数据库系统 统计学
其他学科 算法
机器学习 可视化
数据挖掘的主要问题
? 挖掘方法
? 在不同的数据类型中挖掘不同类型的知识,e.g.,生物数据,流式数据,Web数据
? 性能, 算法的有效性、可伸缩性和并行处理
? 模式评估, 兴趣度问题
? 背景知识的合并
? 处理噪声何不完全数据
? 并行,分布式和增量挖掘算法
? 新发现知识与已有知识的集成, 知识融合
? 用户交互
? 数据挖掘查询语言和特定的数据挖掘
? 数据挖掘结果的表示和显示
? 多个抽象层的交互知识挖掘
? 应用和社会因素
? 特定域的数据挖掘 & 不可视的数据挖掘
? 数据安全,完整和保密的保护
第二章、数据仓库和 OLAP技术
什么是数据仓库?
? 数据仓库的定义很多，但却很难有一种严格的定义
? 它是一个提供决策支持功能的数据库，它与公司的操作数据
库分开维护。
? 为统一的历史数据分析提供坚实的平台，对信息处理提供支
持
?,数据仓库是一个面向主题的、集成的、随时间而变
化的、不容易丢失的数据集合，支持管理部门的决策
过程,”— W,H,Inmon（数据仓库构造方面的领头设计
师）
? 建立数据仓库 (data warehousing),
? 构造和使用数据仓库的过程。
数据仓库与异种数据库集成
? 传统的异种数据库集成,
? 在多个异种数据库上建立包装程序（ wrappers）和中介程序
（ mediators ）
? 查询驱动方法 —— 当从客户端传过来一个查询时，首先使用
元数据字典将查询转换成相应异种数据库上的查询；然后，
将这些查询映射和发送到局部查询处理器
? 缺点：复杂的信息过虑和集成处理，竞争资源
? 数据仓库, 更新驱动
? 将来自多个异种源的信息预先集成，并存储在数据仓库中，
供直接查询和分析
? 高性能
OLTP系统和 OLAP系统的比较
特征 OLTP OLAP
任务特点 操作处理 信息处理
面向 事务 分析
用户 办事员,DBA、数据库专业人员 经理、主管、数据分析员
功能 日常操作 长期信息分析、决策支持
DB设计 基于 E-R，面向应用 星型 /雪花，面向主体
数据 最新的、详细的 历史的、汇总的
视图 详细的、二维关系型 汇总的、多维的
任务单位 简短的事务 复杂的查询
访问数据量 数十个 数百万个
用户数 数千个 数百个
DB规模 100M-数 GB 100GB-数 TB
优先性 高性能、高可用性 高灵活性、端点用户自治
度量 事务吞吐量 查询吞吐量、响应时间
从关系表和电子表格到数据立方体
? 数据仓库和数据仓库技术基于 多维数据模型 。这个模型把数据看
作是 数据立方体 形式。多维数据模型围绕中心主题组织，该主题
用 事实表 表示。 事实 是数值度量的。
? 数据立方体 允许以多维数据建模和观察。它由 维 和 事实 定义。
? 维 是关于一个组织想要记录的视角或观点。每个维都有一个表与
之相关联，称为 维表 。
? 事实表 包括事实的名称或度量以及每个相关维表的关键字
? 在数据仓库的研究文献中，一个 n维的数据的立方体叫做 基本方体 。
给定一个维的集合，我们可以构造一个 方体的格,每个都在不同
的汇总级或不同的数据子集显示数据，方体的格称为 数据立方体 。
0维方体存放最高层的汇总，称作 顶点方体 ；而存放最底层汇总的
方体则称为 基本方体 。
度量的分类
? 一个数据立方体的度量是一个数值函数，该函数可以
对数据立方体的每一个点求值。度量可以根据其所用
的聚集函数分为三类,
? 分布的 (distributive)：将函数用于 n个聚集值得到的结果和将
函数用于所有数据得到的结果一样。
? 比如,count(),sum(),min(),max()等
? 代数的 (algebraic)：函数可以由一个带 M个参数的代数函数
计算（ M为有界整数），而每个参数值都可以有一个分布的
聚集函数求得。
? 比如,avg(),min_N(),standard_deviation()
? 整体的 (holistic)：描述函数的子聚集所需的存储没有一个常
数界。
? 比如,median(),mode(),rank()
概念分层,location维的一个概念分层
all
Europe North_America
Mexico Canada Spain Germany
Vancouver
M,Wind L,Chan
..,
...,.,
...,.,
..,
all
region
office
country
Toronto Frankfurt city
多维数据模型上的 OLAP操作
? 上卷 (roll-up):汇总数据
? 通过一个维的概念分层向上攀升或者通过维规约
? 下钻 (drill-down)：上卷的逆操作
? 由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下 或引入新的维来实现
? 切片和切块 (slice and dice)
? 投影和选择操作
? 转轴 (pivot)
? 立方体的重定位，可视化，或将一个 3维立方体转化维一个 2维平
面序列
? 其他 OLAP操作
? 钻过 (drill_across)：执行涉及多个事实表的查询
? 钻透 (drill_through)：使用关系 SQL机制，钻到数据立方体的底层，
到后端关系表
数据仓库设计的四种视图
? 数据仓库设计的四种视图
? 自顶向下视图
? 允许我们选择数据仓库所需的相关信息
? 数据源视图
? 揭示被操作数据库系统所捕获、存储和管理的信息
? 数据仓库视图
? 有事实表和维表所组成
? 商务查询视图
? 从最终用户的角度透视数据仓库中的数据
三种数据仓库模型
? 企业仓库
? 搜集关于跨越整个组织的主题的所有信息
? 数据集市
? 企业范围数据的一个子集，对于特定的客户是有用的。其范
围限于选定的主题，比如一个商场的数据集市
? 独立的数据集市 VS,非独立的数据集市（数据来自于企业数据
仓库）
? 虚拟仓库
? 操作数据库上的一系列视图
? 只有一些可能的汇总视图被物化
OLAP服务器类型
? 逻辑上,OLAP服务器从数据仓库或数据集市中给商业用户提供多
维数据
? 物理上,OLAP的底层数据存储实现可以有多种不同的方式
? 关系 OLAP服务器 (ROLAP)
? 使用关系数据库或扩展的关系数据库存放并管理数据仓库的数据，而
用 OLAP中间件支持其余部分
? 包括每个 DBMS后端优化，聚集导航逻辑的实现，附加的工具和服务
? 较大的可扩展性
? 多维 OLAP服务器 (MOLAP)
? 基于数组的多维存储引擎（稀疏矩阵技术）
? 能对预计算的汇总数据快速索引
? 混合 OLAP服务器 (HOLAP)
? 结合上述两种技术，更大的使用灵活性
? 特殊的 SQL服务器
? 在星型和雪花模型上支持 SQL查询
方体计算的多路数组聚集方法 (1)
? 将数组分成块（ chunk,一个可以装入内存的小子方）
? 压缩的稀疏数组寻址,(chunk_id,offset)
? 通过访问立方体单元，计算聚集。可以优化访问单元组的次序，
使得每个单元被访问的次数最小化，从而减少内存访问和磁盘 I/O
的开销。
A(month)
B
29 30 31 32
1 2 3 4
5
9
13 14 15 16
64 63 62 61 48 47 46 45
a1 a0
c3 c2
c1 c 0
b3
b2
b1
b0
a2 a3
C(item)
B(city)
44 28
56 40
24 52
36 20
60 哪个是多路数组
聚集的最佳遍历
次序？
第三章、数据预处理
为什么要预处理数据？
? 现实世界的数据是“肮脏的”
? 不完整的：有些感兴趣的属性缺少属性值，或仅包
含聚集数据
? 含噪声的：包含错误或者“孤立点”
? 不一致的：在编码或者命名上存在差异
? 没有高质量的数据，就没有高质量的挖掘结果
? 高质量的决策必须依赖高质量的数据
? 数据仓库需要对高质量的数据进行一致地集成
数据预处理的主要任务
? 数据清理
? 填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性
? 数据集成
? 集成多个数据库、数据立方体或文件
? 数据变换
? 规范化和聚集
? 数据归约
? 得到数据集的压缩表示，它小得多，但可以得到相同或相近
的结果
? 数据离散化
? 数据归约的一部分，通过概念分层和数据的离散化来规约数据,对数字型数据特别重要
如何处理空缺值
? 忽略元组：当类标号缺少时通常这么做（假定挖掘任
务设计分类或描述），当每个属性缺少值的百分比变
化很大时，它的效果非常差。
? 人工填写空缺值：工作量大，可行性低
? 使用一个全局变量填充空缺值：比如使用 unknown或
-∞
? 使用属性的平均值填充空缺值
? 使用与给定元组属同一类的所有样本的平均值
? 使用最可能的值填充空缺值：使用像 Bayesian公式或
判定树这样的基于推断的方法
噪声数据
? 噪声：一个测量变量中的随机错误或偏差
? 引起不正确属性值的原因
? 数据收集工具的问题
? 数据输入错误
? 数据传输错误
? 技术限制
? 命名规则的不一致
? 其它需要数据清理的数据问题
? 重复记录
? 不完整的数据
? 不一致的数据
如何处理噪声数据
? 分箱 (binning),
? 首先排序数据，并将他们分到等深的箱中
? 然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平
滑等等
? 聚类,
? 监测并且去除孤立点
? 计算机和人工检查结合
? 计算机检测可疑数据，然后对它们进行人工判断
? 回归
? 通过让数据适应回归函数来平滑数据
数据变换
? 平滑：去除数据中的噪声 （分箱、聚类、回归）
? 聚集：汇总，数据立方体的构建
? 数据概化：沿概念分层向上汇总
? 规范化：将数据按比例缩放，使之落入一个小的特定
区间
? 最小－最大规范化
? z-score规范化
? 小数定标规范化
? 属性构造
? 通过现有属性构造新的属性，并添加到属性集中；以增加对
高维数据的结构的理解和精确度
数据归约策略
? 数据仓库中往往存有海量数据，在其上进行复杂的数
据分析与挖掘需要很长的时间
? 数据归约
? 数据归约可以用来得到数据集的归约表示，它小得多，但可
以产生相同的（或几乎相同的）分析结果
? 数据归约策略
? 数据立方体聚集
? 维归约
? 数据压缩
? 数值归约
? 离散化和概念分层产生
? 用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。
分类数据的概念分层生成
? 分类数据是指无序的离散数据，它有有限个值（可能
很多个）。
? 分类数据的概念分层生成方法,
? 由用户或专家在模式级显式的说明属性的部分序。
? 通过显示数据分组说明分层结构的一部分。
? 说明属性集，但不说明它们的偏序，然后系统根据算法自动
产生属性的序，构造有意义的概念分层。
? 对只说明部分属性集的情况，则可根据数据库模式中的数据
语义定义对属性的捆绑信息，来恢复相关的属性。
第四章、数据挖掘原语和 DMQL
数据挖掘原语的组成部分
? 数据挖掘原语应该包括以下部分,
? 说明数据库的部分或用户感兴趣的数据集
? 要挖掘的知识类型
? 用于指导挖掘的背景知识
? 模式评估、兴趣度量
? 如何显示发现的知识
? 数据挖掘原语用于用户和数据挖掘系统通信，让用户
能从不同的角度和深度审查和发现结果，并指导挖掘
过程。
说明数据挖掘任务的原语
? 任务相关的数据
? 数据库（仓库）名、数据立方体、选择条件、相关属性、分组条件
? 挖掘的知识类型
? 特征化、区分、关联、分类 /预测、聚类
? 背景知识
? 概念分层，关联的确信度
? 模式兴趣度度量
? 简单性、确定性、实用性、新颖性
? 发现模式的可视化
? 规则、表、图表、图、判定树 …
兴趣度度量
? 没有兴趣度度量，挖掘出来的有用模式，很可
能会给淹没在用户不感兴趣的模式中。
? 简单性
? 确定性
? 实用性
? 新颖性
? 兴趣度的客观度量方法：根据模式的结构和统
计，用一个临界值来判断某个模式是不是用户
感兴趣的。
第五章、特征化和比较
两种不同类别的数据挖掘
? 从数据分析的角度看，数据挖掘可以分为描述
性挖掘和预测性挖掘
? 描述性挖掘：以简洁概要的方式描述数据，并提供
数据的有趣的一般性质。
? 预测性数据挖掘：通过分析数据建立一个或一组模
型，并试图预测新数据集的行为。
什么是概念描述？
? 描述性挖掘 VS,预测性挖掘
? 描述性挖掘：以简洁概要的方式描述数据，并提供
数据的有趣的一般性质。
? 预测性数据挖掘：通过分析数据建立一个或一组模
型，并试图预测新数据集的行为。
? 概念描述：为数据的特征化和比较产生描述
（当所描述的概念所指的是一类对象时，也称
为 类描述 ）
? 特征化：提供给定数据集的简洁汇总。
? 区分：提供两个或多个数据集的比较描述。
数据概化
? 数据概化
? 数据库中的数据和对象通常包含原始概念层的细节信息，数
据概化就是将数据库中的跟任务相关的数据集从较低的概念
层抽象到较高的概念层的过程。
? 主要方法,
? 数据立方体（ OLAP使用的方法）
? 面向属性的归纳方法
1
2
3
4
5 概念层
面向属性的归纳
? Attribute-oriented induction,AOI (KDD `89
Workshop)
? 受数据类型和度量类型的约束比较少
? 面向属性归纳的基本思想,
? 使用关系数据库查询收集任务相关的数据
? 通过考察任务相关数据中每个属性的不同值的个数进行概化，
方法是属性删除或者是属性概化
? 通过合并相等的，概化的广义元组，并累计他们对应的计数
值进行聚集操作
? 通过与用户交互，将广义关系以图表或规则等形式，提交给
用户
面向属性的归纳的基本步骤
? 数据聚焦，获得初始工作关系
? 进行面向属性的归纳
? 基本操作是数据概化，对有 大量不同值的属性,进
行进一步概化
? 属性删除
? 属性概化
? 属性概化控制：控制概化过程，确定有多少不同的
值才算是有 大量不同值的属性
? 属性概化临界值控制
? 概化关系临界值控制
概念描述的属性相关分析步骤 (1)
? 数据收集
? 通过查询处理，收集目标类和对比类数据
? 使用保守的 AOI进行预相关分析
? 识别属性和维的集合，它们是所选择的相关性分析度量的应
用对象
? 因为不同的概念层对某个类描述的相关性可能很不同，因此
在这个过程中同时要包含概念分层
? 对有大量不同值的属性进行删除或概化
? 在这一级进行概化时，临界值要相应比较高，以便在后续步
骤的分析中包含更多属性（保守的）
? 产生候选关系
概念描述的属性相关分析步骤 (2)
? 使用选定的相关分析度量删除不相关和弱相关
的属性
? 使用选定的相关分析度量（ e.g.信息增益），评估
候选关系中的每个属性
? 根据所计算的相关性对属性进行排序
? 低于临界值的不相关和弱相关的属性被删除
? 产生初始目标类工作关系（或初始对比类工作关系）
? 使用 AOI产生概念描述
? 使用一组不太保守的属性概化临界值进行 AOI
挖掘类比较：区分不同的类
? 类比较挖掘的目标是得到将目标类与对比类相区分的
描述。
? 目标类和对比类间必须具有可比性，即两者间要有相似的属
性或维。
? 本科生 VS,研究生 ； student VS,address
? 很多应用于概念描述的技巧可以应用于类比较，比如
属性概化。
? 属性概化必须在所有比较类上同步进行，将属性概化到同一
抽象层后进行比较。
? City VS country
类比较的过程
? 数据收集
? 通过查询处理收集数据库中相关的数据，并将其划分为一个目标类
和一个或多个对比类
? 维相关分析
? 使用属性相关分析方法，使我们的任务中仅包含强相关的维
? 同步概化
? 同步的在目标类和对比类上进行概化，得到 主目标类关系 /方体 和
主对比类关系 /方体
? 导出比较的表示
? 用可视化技术表达类比较描述，通常会包含“对比”度量，反映目
标类与对比类间的比较 (e.g count%)
在大型数据库中挖掘描述统计计量
? 对于数据挖掘任务，用户经常关心的数据特征包括数
据的中心趋势和离散特征
? 中心趋势的度量包括,mean,median,mode 和 midrange
? 数据离散度量包括,quartiles,五数概括和标准差等
? 关系数据库中，系统提供了以下聚集函数,count(),sum(),
avg(),max(),min()
? 在大型数据库中挖掘用户感兴趣的描述统计计量涉及到如何
利用关系数据库现有的函数来计算上述两类用户感兴趣的度
量值
第六章、关联规则挖掘
什么是关联规则挖掘？
? 关联规则挖掘,
? 从事务数据库，关系数据库和其他信息存储中的大
量数据的项集之间发现有趣的、频繁出现的模式、
关联和相关性。
? 应用,
? 购物篮分析、分类设计、捆绑销售和亏本销售分析
关联规则：基本概念
? 给定,
? 项的集合,I={i1,i2,...,in}
? 任务相关数据 D是数据库事务的集合，每个事务 T则
是项的集合，使得
? 每个事务由事务标识符 TID标识；
? A,B为两个项集，事务 T包含 A当且仅当
? 则关联规则是如下蕴涵式,
? 其中 并且,规则 在事
务集 D中成立，并且具有支持度 s和置信度 c
IT ?
TA?
],[ csBA ?
IBIA ??,??? BA BA ?
Apriori算法
? Apriori算法利用频繁项集性质的先验知识（ prior
knowledge），通过逐层搜索的迭代方法，即将 k-项
集用于探察 (k+1)-项集，来穷尽数据集中的所有频繁
项集。
? 先找到频繁 1-项集集合 L1,然后用 L1找到频繁 2-项集集合 L2，
接着用 L2找 L3，直到找不到频繁 k-项集，找每个 Lk需要一次
数据库扫描。
? Apriori性质：频繁项集的所有非空子集也必须是频繁
的。（ 模式不可能比 A更频繁的出现）
? Apriori算法是反单调的，即一个集合如果不能通过测试，则
该集合的所有超集也不能通过相同的测试。
BA ?
Apriori算法步骤
? Apriori算法由 连接 和 剪枝 两个步骤组成。
? 连接,为了找 Lk，通过 Lk-1与自己连接产生候选 k-项集
的集合，该 候选 k项集 记为 Ck。
? Lk-1中的两个元素 L1和 L2可以执行连接操作 的条件是
? 剪枝,Ck是 Lk的超集，即它的成员可能不是频繁的，
但是所有频繁的 k-项集都在 Ck中（为什么？）。因此
可以通过扫描数据库，通过计算每个 k-项集的支持度
来得到 Lk 。
? 为了减少计算量，可以使用 Apriori性质，即如果一个 k-项集
的 (k-1)-子集不在 Lk-1中，则该候选不可能是频繁的，可以直
接从 Ck删除。
])1[]1[(])2[]2[(...])2[]2[(])1[]1[( 21212121 ???????????? klklklklllll
21 ll ??
Apriori算法 —— 示例
Database TDB
1st scan
C1 L1
L2
C2 C2
2nd scan
C3 L3 3rd scan
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} 3
{D} 1
{E} 3
Itemset sup
{A} 2
{B} 3
{C} 3
{E} 3
Itemset
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
Itemset sup
{A,B} 1
{A,C} 2
{A,E} 1
{B,C} 2
{B,E} 3
{C,E} 2
Itemset sup
{A,C} 2
{B,C} 2
{B,E} 3
{C,E} 2
Itemset
{B,C,E}
Itemset sup
{B,C,E} 2
使用 Apiori性质由 L2产生 C3
? 1,连接,
? C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}}
{{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}
? 2．使用 Apriori性质剪枝：频繁项集的所有子集必须是频繁的，
对候选项 C3，我们可以删除其子集为非频繁的选项,
? {A,B,C}的 2项子集是 {A,B},{A,C},{B,C}，其中 {A,B}不是 L2的元素，
所以删除这个选项；
? {A,C,E}的 2项子集是 {A,C},{A,E},{C,E}，其中 {A,E} 不是 L2的元素，
所以删除这个选项；
? {B,C,E}的 2项子集是 {B,C},{B,E},{C,E}，它的所有 2－项子集都是
L2的元素，因此保留这个选项。
? 3．这样，剪枝后得到 C3={{B,C,E}}
????
多层关联 —— 一致支持度 VS,递减支持度
? 一致支持度：对所有层都使
用一致的最小支持度
? 优点：搜索时容易采用优化
策略，即一个项如果不满足
最小支持度，它的所有子项都可以不用搜索
? 缺点：最小支持度值设置困难
? 太高：将丢掉出现在较低抽
象层中有意义的关联规则
? 太低：会在较高层产生太多
的无兴趣的规则
? 递减支持度：在较低层使用递减的最小支持度
? 抽象层越低，对应的最小支
持度越小
Computer
[support=10%]
Laptop
[support=6%]
Desktop
[support=4%]
min_sup = 5%
min_sup = 5% 3%
多层关联 —— 搜索策略
? 具有递减支持度的多层关联规则的搜索策略
? 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝
? 层交叉单项过滤：一个第 i层的项被考察，当且仅当它在第
（ i-1）层的父节点是频繁的（图 6-14）
? 层交叉 k项集过滤：一个第 i层的 k项集被考察，当且仅当它在
第 (i-1)层的对应父节点 k-项集是频繁的（图 6-15）
? 搜索策略比较
? 逐层独立策略条件松，可能导致底层考察大量非频繁项
? 层交叉 k项集过滤策略限制太强，仅允许考察频繁 k-项集的子
女
? 层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层
频繁项（图 6-14)
关联规则的兴趣度度量
? 客观度量
? 两个流行的度量指标
? 支持度
? 置信度
? 主观度量
? 最终，只有用户才能确定一个规则是否有趣的，而且这种判
断是主观的，因不同的用户而异；通常认为一个规则（模式）
是有趣的，如果,
? 它是出人意料的
? 可行动的（用户可以使用该规则做某些事情）
? 挖掘了关联规则后，哪些规则是用户感兴趣的？强关
联规则是否就是有趣的？
第七章、分类和预测
分类 VS,预测
? 分类,
? 预测分类标号（或离散值）
? 根据训练数据集和类标号属性，构建模型来分类现有数据，
并用来分类新数据
? 预测,
? 建立连续函数值模型，比如预测空缺值
? 典型应用
? 信誉证实
? 目标市场
? 医疗诊断
? 性能预测
数据分类 —— 一个两步过程
? 第一步，建立一个模型，描述预定数据类集和概念集
? 假定每个元组属于一个预定义的类，由一个类标号属性确定
? 基本概念
? 训练数据集,由为建立模型而被分析的数据元组形成
? 训练样本,训练数据集中的单个样本（元组）
? 学习模型可以用分类规则、判定树或数学公式的形式提供
? 第二步，使用模型，对将来的或未知的对象进行分类
? 首先评估模型的预测准确率
? 对每个测试样本，将已知的类标号和该样本的学习模型类预测比较
? 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比
? 测试集要独立于训练样本集，否则会出现“过分适应数据”的情况
有指导的学习 VS,无指导的学习
? 有指导的学习（用于分类）
? 模型的学习在被告知每个训练样本属于哪个类的
“指导”下进行
? 新数据使用训练数据集中得到的规则进行分类
? 无指导的学习（用于聚类）
? 每个训练样本的类编号是未知的，要学习的类集合
或数量也可能是事先未知的
? 通过一系列的度量、观察来建立数据中的类编号或
进行聚类
比较分类方法
? 使用下列标准比较分类和预测方法
? 预测的准确率：模型正确预测新数据的类编号的能
力
? 速度：产生和使用模型的计算花销
? 健壮性：给定噪声数据或有空缺值的数据，模型正
确预测的能力
? 可伸缩性：对大量数据，有效的构建模型的能力
? 可解释性：学习模型提供的理解和洞察的层次
用判定树归纳分类
? 什么是判定树？
? 类似于流程图的树结构
? 每个内部节点表示在一个属性上的测试
? 每个分枝代表一个测试输出
? 每个树叶节点代表类或类分布
? 判定树的生成由两个阶段组成
? 判定树构建
? 开始时，所有的训练样本都在根节点
? 递归的通过选定的属性，来划分样本 （必须是离散值）
? 树剪枝
? 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检 测和剪去这种分枝
? 判定树的使用：对未知样本进行分类
? 通过将样本的属性值与判定树相比较
贝叶斯分类
? 贝叶斯分类利用统计学中的
贝叶斯定理，来预测类成员
的概率，即给定一个样本，
计算该样本属于一个特定的
类的概率。
? 朴素贝叶斯分类：假设每个
属性之间都是相互独立的，
并且每个属性对非类问题产
生的影响都是一样的。
)(
)()|()|(
DP
hPhDPDhP ?
后向传播分类
? 后向传播是一种神经网络学习算法；神经网络是一组
连接的输入 /输出单元，每个连接都与一个权相连。在
学习阶段，通过调整神经网络的权，使得能够预测输
入样本的正确标号来学习。
? 优点
? 预测精度总的来说较高
? 健壮性好，训练样本中包含错误时也可正常工作
? 输出可能是离散值、连续值或者是离散或量化属性的向量值
? 对目标进行分类较快
? 缺点
? 训练（学习）时间长
? 蕴涵在学习的权中的符号含义很难理解
? 很难根专业领域知识相整合
什么是预测？
? 预测是构造和使用模型评估无样本类，或评估给定样
本可能具有的属性或值空间。
? 预测和分类的异同
? 相同点
? 两者都需要构建模型
? 都用模型来估计未知值
? 预测当中主要的估计方法是回归分析
? 线性回归和多元回归
? 非线性回归
? 不同点
? 分类法主要是用来预测类标号（分类属性值）
? 预测法主要是用来估计连续值（量化属性值）
第八章、聚类分析
什么是聚类分析？
? 聚类（簇）：数据对象的集合
? 在同一个聚类（簇）中的对象彼此相似
? 不同簇中的对象则相异
? 聚类分析
? 将物理或抽象对象的集合分组成为由类似的对象组成的多个
类的过程
? 聚类是一种无指导的学习：没有预定义的类编号
? 聚类分析的数据挖掘功能
? 作为一个独立的工具来获得数据分布的情况
? 作为其他算法（如：特征和分类）的预处理步骤
聚类分析的典型应用
? 模式识别
? 空间数据分析
? 在 GIS系统中，对相似区域进行聚类，产生主题地图
? 检测空间聚类，并给出它们在空间数据挖掘中的解释
? 图像处理
? 经济学（尤其是市场研究）
? 万维网
? 对 WEB上的文档进行分类
? 对 WEB日志的数据进行聚类，以发现相同的用户访问模式
主要的聚类方法
? 聚类分析算法种类繁多，具体的算法选择取决于数据
类型，聚类的应用和目的，常用的聚类算法包括,
? 划分方法
? 层次的方法
? 基于密度的方法
? 基于网格的方法
? 基于模型的方法
? 实际应用中的聚类算法，往往是上述聚类方法中多种
方法的整合
孤立点挖掘
? 什么是孤立点？
? 一个数据集与其他数据有着显著区别的数据对象的集合
? 例如：运动员,Michael Jordon,舒马赫，布勃卡
? 孤立点产生原因
? 度量或执行错误（年龄,-999）
? 数据变异的结果
? 孤立点挖掘
? 给定一个 n个数据对象的集合，以及预期的孤立点数目 k，发现与
剩余的数据有着显著差异的头 k个数据对象
? 应用
? 信用卡欺诈检测
? 移动电话欺诈检测
? 客户划分
? 医疗分析（异常）
电子商务与数据挖掘
电子商务与数据挖掘 —— 完美结合
? 在电子商务中进行成功的数据挖掘得益于,
? 电子商务提供海量的数据
? 如果一个电子商务网站平均每个小时卖出五件物品，那么它一 个月的平均点击量是 160万次。
? 丰富的记录信息
? 良好的 WEB站点设计将有助于获得丰富的信息
? 干净的数据
? 从电子商务站点收集的都是电子数据，无需人工输入或者是从 历史系统进行整合
? 研究成果容易转化
? 在电子商务中，很多知识发现都可以进行直接应用
? 投资收益容易衡量
对电子商务网站的 Web数据挖掘
? 通常在一个电子商务网站上应用的数据挖掘技
术是 Web数据挖掘。
? 我们可以在一个电子商务网站挖掘些什么东西？
? 内容挖掘 (Web Content Mining)
? 结构挖掘 (Web Structure Mining)
? 使用挖掘 (Web Usage Mining)
Web Usage Mining
? 与 Web Content Mining和 Web Structure Mining不同
的是,Web Usage Mining的挖掘对象是用户和网络
交互过程中抽取出来的二手数据，这些数据主要是用
户在访问 Web时在 Web日志里留下的信息，以及其它
一些交互信息,
? 日志信息包括访问日期、时间、用户 IP地址、服务器 IP地址、
方法、所请求 URL资源、服务器响应状态、用户代理、发送
字节等。
? Web Usage Mining就是对系统日志信息，以及用户的注册
数据等进行挖掘，以发现有用的模式和知识。
Web Usage Mining的作用
? 通过对电子商务网站应用 Web Usage Mining
数据挖掘技术，可以
? 提高站点的质量
? 改善 WEB缓存，缓解网络交通，提高性能
? 在电子商务中还可捕捉到大量的采购过程的细节，
为更加深入的分析提供了可能
