数据挖掘

liu819yh1

贡献于2010-09-16

字数:0 关键词: 数据挖掘

数据挖掘:概念与技术 韩家炜 Data Mining: Concepts and Techniques J. Han and M. Kamber Morgan Kaufmann 2000 目录 第一章 引言.......................................................................................................................................................... 8 1.1 什么激发数据挖掘?为什么它是重要的?.............................................................................................. 8 1.2 什么是数据挖掘? ................................................................................................................................... 10 1.3 数据挖掘——在何种数据上进行?........................................................................................................ 12 1.3.1 关系数据库........................................................................................................................................ 13 1.3.2 数据仓库............................................................................................................................................ 14 1.3.3 事务数据库........................................................................................................................................ 16 1.3.4 高级数据库系统和高级数据库应用 ................................................................................................ 16 1.4 数据挖掘功能——可以挖掘什么类型的模式?.................................................................................... 18 1.4.1 概念/类描述:特征和区分............................................................................................................... 19 1.4.2 关联分析............................................................................................................................................ 19 1.4.3 分类和预测........................................................................................................................................ 20 1.4.4 聚类分析............................................................................................................................................ 20 1.4.5 局外者分析........................................................................................................................................ 21 1.4.6 演变分析............................................................................................................................................ 21 1.5 所有模式都是有趣的吗?........................................................................................................................ 21 1.6 数据挖掘系统的分类................................................................................................................................ 22 1.7 数据挖掘的主要问题................................................................................................................................ 23 1.8 总结 ........................................................................................................................................................... 25 习题.................................................................................................................................................................. 26 第二章 数据仓库和数据挖掘的 OLAP 技术 ................................................................................................... 29 2.1 什么是数据仓库?...................................................................................................................................... 29 2.2.1 操作数据库系统与数据仓库的区别 ................................................................................................ 30 2.1.2 但是,为什么需要一个分离的数据仓库 ........................................................................................ 31 2.2 多维数据模型 ........................................................................................................................................... 32 2.2.1 由表和电子数据表到数据方............................................................................................................ 32 2.2.2 星形、雪花和事实星座:多维数据库模式 .................................................................................... 34 2.2.3 定义星形、雪花和事实星座的例子 ................................................................................................ 36 2.2.3 度量:它们的分类和计算................................................................................................................ 37 2.2.5 引入概念分层.................................................................................................................................... 38 2.2.6 多维数据模型上的 OLAP 操作........................................................................................................ 40 2.2.7 查询多维数据库的星形网查询模型 ................................................................................................ 42 2.3 数据仓库的系统结构................................................................................................................................ 42 2.3.1 数据仓库的设计步骤和结构............................................................................................................ 42 2.3.2 三层数据仓库结构............................................................................................................................ 44 2.3.3 OLAP 服务器类型:ROLAP、MOLAP、HOLAP 的比较............................................................... 45 2.4 数据仓库实现 ........................................................................................................................................... 46 2.4.1 数据方的有效计算............................................................................................................................ 47 2.4.2 索引 OLAP 数据................................................................................................................................ 50 2.4.3 OLAP 查询的有效处理...................................................................................................................... 52 2.4.4 元数据存储........................................................................................................................................ 53 2.5 数据方技术的进一步发展........................................................................................................................ 54 2.5.1 数据方发现驱动的探查.................................................................................................................... 54 2.5.2 多粒度上的复杂聚集: 多特征方..................................................................................................... 56 2.5.3 其它进展............................................................................................................................................ 57 2.6 由数据仓库到数据挖掘............................................................................................................................ 58 2.6.1 数据仓库的使用................................................................................................................................ 58 2.6.2 由联机分析处理到联机分析挖掘.................................................................................................... 59 2.7 总结 ........................................................................................................................................................... 60 习题.................................................................................................................................................................. 61 第三章 数据预处理 ............................................................................................................................................ 64 3.1 为什么要预处理数据?............................................................................................................................ 64 3.2 数据清理 ................................................................................................................................................... 66 3.2.1 遗漏值................................................................................................................................................ 66 3.2.2 噪音数据............................................................................................................................................ 66 3.3 数据集成和变换...................................................................................................................................... 68 3.3.1 数据集成............................................................................................................................................ 68 3.3.2 数据变换............................................................................................................................................ 69 3.4 数据归约.................................................................................................................................................. 70 3.4.1 数据方聚集...................................................................................................................................... 71 3.4.2 维归约................................................................................................................................................ 72 3.4.3 数据压缩............................................................................................................................................ 73 3.4.4 数值归约.......................................................................................................................................... 75 3.5 离散化和概念分层产生.......................................................................................................................... 79 3.5.1 数值数据的离散化和概念分层产生 ................................................................................................ 80 3.5.2 分类数据的概念分层产生.............................................................................................................. 83 3.6 总结 ........................................................................................................................................................... 84 习题.................................................................................................................................................................. 85 第四章 数据挖掘原语、语言和系统结构 ...................................................................................................... 87 4.1 数据挖掘原语:什么定义数据挖掘任务? .......................................................................................... 87 4.1.1 任务相关的数据.............................................................................................................................. 89 4.1.2 要挖掘的知识的类型...................................................................................................................... 89 4.1.3 背景知识:概念分层...................................................................................................................... 90 4.1.4 兴趣度度量...................................................................................................................................... 92 4.1.5 发现模式的提供和可视化.............................................................................................................. 94 4.2 一种数据挖掘查询语言.......................................................................................................................... 95 4.2.1 任务相关数据说明的语法.............................................................................................................. 96 4.2.2 说明挖掘知识类型的语法.............................................................................................................. 97 4.2.3 概念分层说明的语法...................................................................................................................... 99 4.2.4 兴趣度度量说明的语法.................................................................................................................... 99 4.2.5 模式提供和可视化说明的语法.................................................................................................... 100 4.2.6 汇集 —— 一个 DMQL 查询的例子........................................................................................ 100 4.2.7 其它数据挖掘语言和数据挖掘原语的标准化 ............................................................................ 101 4.3 基于数据挖掘查询语言设计图形用户界面 ........................................................................................ 102 4.4 数据挖掘系统的结构............................................................................................................................ 102 4.5 总结........................................................................................................................................................ 103 第五章 概念描述:特征与比较 ...................................................................................................................... 107 5.1 什么是概念描述?................................................................................................................................107 5.2 数据泛化和基于汇总的特征................................................................................................................ 108 5.2.1 面向属性归纳................................................................................................................................108 5.2.2 面向属性归纳的有效实现...........................................................................................................111 5.2.3 导出泛化的表示............................................................................................................................ 112 5.3 解析特征: 属性相关性分析 ................................................................................................................. 115 5.3.1 为什么进行属性相关性分析? ...................................................................................................... 115 5.3.2 属性相关分析方法........................................................................................................................ 115 5.4 挖掘类比较:区分不同的类................................................................................................................ 118 5.4.1 类比较方法和实现........................................................................................................................ 118 5.4.2 类比较描述的表示.......................................................................................................................... 120 5.4.3 类描述: 提供特征和比较........................................................................................................... 121 5.5 在大型数据库中挖掘描述统计度量.................................................................................................... 123 5.5.1 度量中心趋势................................................................................................................................123 5.5.2 度量数据的发散............................................................................................................................ 124 5.5.3 基本统计类描述的图形显示........................................................................................................ 126 5.6 讨论........................................................................................................................................................ 128 5.6.1 概念描述:与典型的机器学习方法比较 .................................................................................... 128 5.6.2 概念描述的增量和并行挖掘........................................................................................................ 129 5.7 总结........................................................................................................................................................ 129 第六章 挖掘大型数据库中的关联规则 .......................................................................................................... 132 6.1 关联规则挖掘........................................................................................................................................ 132 6.1.1 购物篮分析:一个引发关联规则挖掘的例子 ............................................................................ 132 6.1.2 基本概念........................................................................................................................................ 133 6.1.3 关联规则挖掘:一个路线图........................................................................................................ 133 6.2 由事务数据库挖掘单维布尔关联规则.................................................................................................. 134 6.2.1 Apriori 算法:使用候选项集找频繁项集 ................................................................................... 135 6.2.2 由频繁项集产生关联规则............................................................................................................ 138 6.2.3 提高 Apriori 的有效性 .................................................................................................................. 138 6.2.4 不产生候选挖掘频繁项集............................................................................................................ 140 6.2.5 冰山查询........................................................................................................................................ 142 6.3 由事务数据库挖掘多层关联规则........................................................................................................ 143 6.3.1 多层关联规则................................................................................................................................143 6.3.2 挖掘多层关联规则的方法............................................................................................................ 144 6.3.3 检查冗余的多层关联规则............................................................................................................ 146 6.4 由数据库和数据仓库挖掘多维关联规则 ............................................................................................ 147 6.4.1 多维关联规则................................................................................................................................147 6.4.2 使用量化属性的静态离散化挖掘多维关联规则 ........................................................................ 148 6.4.3 挖掘量化关联规则........................................................................................................................ 148 6.4.4 挖掘基于距离的关联规则............................................................................................................ 150 6.5 由关联挖掘到相关分析 ...................................................................................................................... 151 6.5.1 强关联规则不一定是有趣的:一个例子 .................................................................................... 151 6.5.2 由关联分析到相关分析................................................................................................................ 151 6.6 基于限制的关联挖掘............................................................................................................................ 152 6.6.1 关联规则的元规则制导挖掘........................................................................................................ 153 6.6.2 用附加的规则限制制导的挖掘.................................................................................................... 154 6.7 总结 ......................................................................................................................................................... 156 第七章 分类和预测 .......................................................................................................................................... 162 7.1 什么是分类?什么是预测?................................................................................................................ 162 7.2 关于分类和预测的问题........................................................................................................................ 163 7.2.1 准备分类和预测数据.................................................................................................................... 164 7.2.2 比较分类方法。............................................................................................................................ 164 7.3 用判定树归纳分类................................................................................................................................164 7.3.1 判定树归纳.................................................................................................................................... 165 7.3.2 树剪枝............................................................................................................................................ 168 7.3.3 由判定树提取分类规则.................................................................................................................. 169 7.3.4 基本判定树归纳的加强.................................................................................................................. 169 7.3.5 判定树归纳的可规模性.................................................................................................................. 170 7.3.6 集成数据仓库技术和判定树归纳.................................................................................................. 171 7.4 贝叶斯分类............................................................................................................................................ 172 7.4.1 贝叶斯定理.................................................................................................................................... 172 7.4.2 朴素贝叶斯分类............................................................................................................................ 173 7.4.3 贝叶斯信念网络............................................................................................................................ 174 7.4.4 训练贝叶斯信念网络.................................................................................................................... 175 7.5 后向传播分类........................................................................................................................................ 176 7.5.1 多路前馈神经网络.......................................................................................................................... 176 7.5.2 定义网络拓扑................................................................................................................................177 7.5.3 后向传播........................................................................................................................................ 177 7.5.4 后向传播和可解释性.................................................................................................................... 181 7.6 基于源于关联规则挖掘概念的分类.................................................................................................... 182 7.7 其它分类方法........................................................................................................................................ 183 7.7.1 k-最临近分类................................................................................................................................. 183 7.7.2 基于案例的推理............................................................................................................................ 184 7.7.3 遗传算法.......................................................................................................................................... 184 7.7.4 粗糙集方法.................................................................................................................................... 185 7.7.5 模糊集方法.................................................................................................................................... 185 7.8 预测........................................................................................................................................................ 186 7.8.1 线性和多元回归............................................................................................................................ 186 7.8.2 非线性回归.................................................................................................................................... 188 7.8.3 其它回归模型................................................................................................................................188 7.9 分类的准确性 ......................................................................................................................................... 188 7.9.1 评估分类法的准确率.................................................................................................................... 189 7.9.2 提高分类法的准确率.................................................................................................................... 189 7.9.3 准确率确定分类法够吗?............................................................................................................ 190 7.10 总结...................................................................................................................................................... 191 第八章 聚类分析 ............................................................................................................................................ 196 8.1 什么是聚类分析?...............................................................................................................................196 8.2 聚类分析中的数据类型....................................................................................................................... 197 8.2.2 区间标度(Interval-Scaled)变量 ................................................................................................. 198 8.2.3 二元变量(binary variable) ......................................................................................................... 199 8.2.4 标称型、序数型和比例标度型变量 .............................................................................................. 200 8.2.5 混合类型的变量.............................................................................................................................. 201 8.3 主要聚类方法的分类.............................................................................................................................. 201 8.4 划分方法(PARTITIONING METHODS) ................................................................................................... 202 8.4.1 典型的划分方法:k-Means 和 k-Medoids...................................................................................... 203 8.4.2 大规模数据库中的划分方法:从 k-medoids 到 CLARANS .......................................................... 205 8.5 层次方法 ................................................................................................................................................. 206 8.5.1 凝聚的和分裂的层次聚类.............................................................................................................. 206 8.5.2 BIRCH:利用层次方法的平衡迭代约减和聚类(Balanced Iterative Reducing and Clustering Using Hierarchies)............................................................................................................................................. 207 8.5.3 CURE:利用代表点聚类(clustering using representative) ....................................................... 208 8.5.4 Chameleon(变色龙): 一个利用动态模型的层次聚类算法...................................................... 208 8.6 基于密度的方法 ..................................................................................................................................... 209 8.6.1 DBSCAN:一个基于密度和高密度的连结区域的聚类算法........................................................... 210 8.6.2 OPTICS:通过对象排序识别聚类结构(Ordering Points to Identify the Clustering Structure) 210 8.6.3 DENCLUE:基于密度分布函数的聚类................................................................................... 211 8.7 基于网格的方法 ..................................................................................................................................... 212 8.7.1 STING:统计信息网格(STatistical INformation Grid).................................................................... 212 8.7.2 WaveCluster:采用小波变换聚类................................................................................................... 213 8.7.3 CLIQUE:聚类高维空间................................................................................................................. 214 8.8 基于模型的聚类方法.............................................................................................................................. 215 8.9 孤立点(OUTLIER)分析 ............................................................................................................................. 217 8.9.1 基于统计的孤立点探测.................................................................................................................. 217 8.9.2 基于距离的孤立点探测................................................................................................................... 218 8.9.3 基于偏离的孤立点探测.................................................................................................................. 219 8.10 总结 ....................................................................................................................................................... 220 第九章 复杂类型数据的挖掘 .......................................................................................................................... 223 9.1 复杂数据对象的多维分析和描述性挖掘(DESCRIPTIVE MINING)..................................................... 223 9.1.1 结构数据概化............................................................................................................................ 223 9.1.2 空间和多媒体数据概化中的聚集和近似计算 ........................................................................ 224 9.1.3 对象标识和类/子类层次的概化............................................................................................... 224 9.1.4 类复合层次概化........................................................................................................................ 225 9.1.5 对象立方体的构造与挖掘........................................................................................................ 225 9.1.6 对规划数据库的概化挖掘......................................................................................................... 225 9.2 空间数据库挖掘 .................................................................................................................................. 227 9.2.1 空间数据立方体构造和空间 OLAP ......................................................................................... 227 9.2.2 空间关联分析............................................................................................................................ 229 9.2.3 空间聚类方法............................................................................................................................ 230 9.2.4 空间分类和空间趋势分析........................................................................................................ 230 9.2.5 光栅数据库挖掘........................................................................................................................ 230 9.3 多媒体数据挖掘 .................................................................................................................................. 230 9.3.1 多媒体数据的相似搜索............................................................................................................ 231 9.3.2 多媒体数据的多维分析............................................................................................................ 231 9.3.3 多媒体数据的分类和预测分析 ................................................................................................ 232 9.3.4 多媒体数据中的关联规则挖掘 ................................................................................................ 232 9.4 时序和序列数据的挖掘....................................................................................................................... 233 9.4.1 趋势分析.................................................................................................................................... 233 9.4.2 时序分析中的相似搜索............................................................................................................ 235 9.4.3 序列模式挖掘............................................................................................................................ 236 9.4.4 周期分析.................................................................................................................................... 237 9.5 文本数据库挖掘................................................................................................................................... 238 9.5.1 文本数据分析和信息检索........................................................................................................ 238 9.5.2 文本挖掘:基于关键字的关联和文档分类 ............................................................................ 240 9.6 WEB 挖掘............................................................................................................................................... 241 9.6.1 挖掘 Web 链接结构,识别权威 Web 页面............................................................................... 242 9.6.2 Web 文档的自动分类 ................................................................................................................. 243 9.6.3 多层次 Web 信息库的构造 ....................................................................................................... 243 9.6.4 Web 使用记录的挖掘 ................................................................................................................. 244 9.7 总结 ...................................................................................................................................................... 245 习题............................................................................................................................................................ 245 文献注解.................................................................................................................................................... 246 第十章 数据挖掘的应用和发展趋势 .............................................................................................................. 248 10.1 数据挖掘的应用 ................................................................................................................................248 10.1.1 针对生物医学和 DNA 数据分析的数据挖掘 ........................................................................ 248 10.1.2 针对金融数据分析的数据挖掘 .............................................................................................. 249 10.1.3 零售业中的数据挖掘.............................................................................................................. 249 10.1.4 电信业中的数据挖掘.............................................................................................................. 250 10.2 数据挖掘系统产品和研究原型......................................................................................................... 251 10.2.1 怎样选择一个数据挖掘系统.................................................................................................. 251 10.2.2 商用数据挖掘系统的例子...................................................................................................... 252 10.3 数据挖掘的其他主题.................................................................................................................... 253 10.3.1 视频和音频数据挖掘............................................................................................................... 253 10.3.2 科学和统计数据挖掘.................................................................................................................... 254 10.3.3 数据挖掘的理论基础.............................................................................................................. 255 10.3.4 数据挖掘和智能查询应答....................................................................................................... 255 10.4 数据挖掘的社会影响......................................................................................................................... 256 10.4.1 数据挖掘是宣传出来的还是持久的稳定增长的商业? ....................................................... 256 10.4.2 数据挖掘只是经理的事还是每个人的事? ........................................................................... 257 10.4.3 数据挖掘对隐私或数据安全构成威胁么? ........................................................................... 258 10.5 数据挖掘的发展趋势......................................................................................................................... 259 10.6 总结 .................................................................................................................................................... 260 习题............................................................................................................................................................ 260 文献注解.................................................................................................................................................... 261 附录 A MICROSOFT’S OLE DB FOR DATA MINING 简介 .................................................................... 263 A.1 创建 DMM 对象................................................................................................................................. 263 A.2 向模型中装入训练数据并对模型进行训练...................................................................................... 264 A.3 模型的使用 ......................................................................................................................................... 264 附录 B DBMINER 简介................................................................................................................................266 B.1 系统结构 ............................................................................................................................................. 266 B.2 输入和输出 ........................................................................................................................................ 266 B.3 系统支持的数据挖掘任务................................................................................................................. 267 B.4 对任务和方法选择的支持................................................................................................................. 267 B.5 对 KDD 处理过程的支持.................................................................................................................. 268 B.6 主要应用 ............................................................................................................................................ 268 B.7 现状 .................................................................................................................................................... 268 第一章 引言 本书是一个导论,介绍什么是数据挖掘,什么是数据库中知识发现。书中的材料从数据库角度 提供,特别强调发现隐藏在大型数据集中有趣数据模式的数据挖掘基本概念和技术。所讨论的实现 方法主要面向可规模化的、有效的数据挖掘工具开发。本章,你将学习数据挖掘如何成为数据库技 术自然进化的一部分,为什么数据挖掘是重要的,以及如何定义数据挖掘。你将学习数据挖掘系统 的一般结构,并考察挖掘的数据种类,可以发现的数据类型,以及什么样的模式提供有用的知识。 除学习数据挖掘系统的分类之外,你将看到建立未来的数据挖掘工具所面临的挑战性问题。 1.1 什么激发数据挖掘?为什么它是重要的? 需要是发明之母。 近年来,数据挖掘引起了信息产业界的极大关注,其主要原因是存在大量数据,可以广泛使用, 并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用,包 括商务管理、生产控制、市场分析、工程设计和科学探索等。 数据挖掘是信息技术自然进化的结果。进化过程的见证是数据库工业界开发以下功能(图 1.1): 数据收集和数据库创建,数据管理(包括数据存储和提取,数据库事务处理),以及数据分析与理 解(涉及数据仓库和数据挖掘)。例如,数据收集和数据库创建机制的早期开发已成为稍后数据存 储和提取、查询和事务处理有效机制开发的必备基础。随着提供查询和事务处理的大量数据库系统 广泛付诸实践,数据分析和理解自然成为下一个目标。 自 60 年代以来,数据库和信息技术已经系统地从原始的文件处理进化到复杂的、功能强大的数 据库系统。自 70 年代以来,数据库系统的研究和开发已经从层次和网状数据库发展到开发关系数 据库系统(数据存放在关系表结构中;见 1.3.1 小节)、数据建模工具、索引和数据组织技术。此外, 用户通过查询语言、用户界面、优化的查询处理和事务管理,可以方便、灵活地访问数据。联机事 务处理(OLTP)将查询看作只读事务,对于关系技术的发展和广泛地将关系技术作为大量数据的有效 存储、提取和管理的主要工具作出了重要贡献。 自 80 年代中期以来,数据库技术的特点是广泛接受关系技术,研究和开发新的、功能强大的数 据库系统。这些使用了先进的数据模型,如扩充关系、面向对象、对象-关系和演绎模型。包括空间 的、时间的、多媒体的、主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库系 统百花齐放。涉及分布性、多样性和数据共享问题被广泛研究。异种数据库和基于 Internet 的全球 信息系统,如 WWW 也已出现,并成为信息工业的生力军。 在过去的三十年中,计算机硬件稳定的、令人吃惊的进步导致了功能强大的计算机、数据收集 设备和存储介质的大量供应。这些技术大大推动了数据库和信息产业的发展,使得大量数据库和信 息存储用于事务管理、信息提取和数据分析。 现在,数据可以存放在不同类型的数据库中。最近出现的一种数据库结构是数据仓库(1.3.2 小 节)。这是一种多个异种数据源在单个站点以统一的模式组织的存储,以支持管理决策。数据仓库 技术包括数据清理、数据集成和联机分析处理(OLAP)。OLAP 是一种分析技术,具有汇总、合并 和聚集功能,以及从不同的角度观察信息的能力。尽管 OLAP 工具支持多维分析和决策,对于深层 次的分析,如数据分类、聚类和数据随时间变化的特征,仍然需要其它分析工具。 图 1.1:数据库技术的进化 数据丰富,伴随着对强有力的数据分析工具的需求,被描述为“数据丰富,但信息贫乏”。快速 增长的海量数据收集、存放在大型和大量数据库中,没有强有力的工具,理解它们已经远远超出了 人的能力(图 1.2)。结果,收集在大型数据库中的数据变成了“数据坟墓”——难得再访问的数据 档案。这样,重要的决定常常不是基于数据库中信息丰富的数据,而是基于决策者的直观,因为决 策者缺乏从海量数据中提取有价值知识的工具。此外,考虑当前的专家系统技术。通常,这种系统 依赖用户或领域专家人工地将知识输入知识库。不幸的是,这一过程常常有偏差和错误,并且耗时、 费用高。数据挖掘工具进行数据分析,可以发现重要的数据模式,对商务决策、知识库、科学和医 学研究作出了巨大贡献。数据和信息之间的鸿沟要求系统地开发数据挖掘工具,将数据坟墓转换成 知识“金块”。 图 1.2 我们数据丰富,知识贫乏 1.2 什么是数据挖掘? 简单地说,数据挖掘是从大量数据中提取或“挖掘”知识。该术语实际上有点用词不当。注意, 从矿石或砂子挖掘黄金称作黄金挖掘,而不是砂石挖掘。这样,数据挖掘应当更正确地命名为“从 数据中挖掘知识”,不幸的是它有点长。“知识挖掘”是一个短术语,可能不能强调从大量数据中 挖掘。毕竟,挖掘是一个很生动的术语,它抓住了从大量的、未加工的材料中发现少量金块这一过 程的特点(图 1.3)。这样,这种用词不当携带了“数据”和“挖掘”,成了流行的选择。还有一 些术语,具有和数据挖掘类似,但稍有不同的含义,如数据库中知识挖掘、知识提取、数据/模式分 析、数据考古和数据捕捞。 图 1.3 数据挖掘:在你的数据中搜索知识(有趣的模式) 许多人把数据挖掘视为另一个常用的术语“数据库中知识发现”或 KDD 的同义词。而另一些 人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程如图 1.4 所示,由以 下步骤组成: 1. 数据清理(消除噪音或不一致数据) 2. 数据集成(多种数据源可以组合在一起)1 3. 数据选择(从数据库中提取与分析任务相关的数据) 4. 数据变换(数据变换或统一成适合挖掘的形式;如,通过汇总或聚集操作)2 1 信息产业界的一个流行趋势是将数据清理和数据集成作为预处理步骤执行,结果数据存放在数据仓库中。 2 有时,数据变换和数据统一在数据选择过程之前进行,特别是在数据仓库情况下。 5. 数据挖掘(基本步骤,使用智能方法提取数据模式) 6. 模式评估(根据某种兴趣度度量,识别提供知识的真正有趣的模式;1.5 节) 7. 知识表示(使用可视化和知识表示技术,向用户提供挖掘的知识)。 图 1.4:数据挖掘视为知识发现过程的一个步骤 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户,或作为新的知识存放在知识 库中。注意,根据这种观点,数据挖掘只是整个过程中的一步,尽管是最重要的一步,因为它发现 隐藏的模式。 我们同意数据挖掘是知识发现过程的一个步骤。然而,在工业界、媒体和数据库研究界,“数 据挖掘”比较长的术语“数据库中知识发现”更流行。因此,在本书中,我们选用术语数据挖掘。 我们采用数据挖掘的广义观点:数据挖掘是从存放在数据库、数据仓库或其它信息库中的大量数据 挖掘有趣知识的过程。 基于这种观点,典型的数据挖掘系统具有以下主要成分(图 1.5): „ 数据库、数据仓库、或其它信息库:这是一个或一组数据库、数据仓库、展开的表、或其它类 型的信息库。可以在数据上进行数据清理和集成。 „ 数据库或数据仓库服务器:根据用户的数据挖掘请求,数据库或数据仓库服务器负责提取相关 数据。 „ 知识库:这是领域知识,用于指导搜索,或评估结果模式的兴趣度。这种知识可能包括概念分 层,用于将属性或属性值组织成不同的抽象层。用户确信方面的知识也可以包含在内。可以使 用这种知识,根据非期望性评估模式的兴趣度。领域知识的其它例子有兴趣度限制或阈值和元 数据(例如,描述来自多个异种数据源的数据)。 „ 数据挖掘引擎:这是数据挖掘系统基本的部分,由一组功能模块组成,用于特征、关联、分类、 聚类分析、演变和偏差分析。 „ 模式评估模块:通常,该部分使用兴趣度度量(1.5 节),并与挖掘模块交互,以便将搜索聚 焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模块也可以与挖掘模块 集成在一起,这依赖于所用的数据挖掘方法的实现。对于有效的数据挖掘,建议尽可能地将模 式评估推进到挖掘过程之中,以便将搜索限制在有兴趣的模式上。 „ 图形用户界面:该模块在用户和挖掘系统之间通讯,允许用户与系统交互,指定数据挖掘查询 或任务,提供信息、帮助搜索聚焦,根据数据挖掘的中间结果进行探索式数据挖掘。此外,该 成分还允许用户浏览数据库和数据仓库模式或数据结构,评估挖掘的模式,以不同的形式对模 式可视化。 图 1.5:典型的数据挖掘系统结构 从数据仓库观点,数据挖掘可以看作联机分析处理(OLAP)的高级阶段。然而,通过结合更 高级的数据理解技术,数据挖掘比数据仓库的汇总型分析处理走得更远。 尽管市场上已有许多“数据挖掘系统”,但是并非所有的都能进行真正的数据挖掘。不能处理 大量数据的数据分析系统,最多称作机器学习系统、统计数据分析工具或实验系统原型。一个系统 只能够进行数据或信息提取,包括在大型数据库找出聚集值或回答演绎查询,应当归类为数据库系 统,或信息提取系统,或演绎数据库系统。 数据挖掘涉及多学科技术的集成,包括数据库技术、统计、机器学习、高性能计算、模式识别、 神经网络、数据可视化、信息提取、图象与信号处理和空间数据分析。在本书讨论数据挖掘时,我 们采用数据库观点。即,着重强调大型数据库中有效的和可规模化的数据挖掘技术。一个算法是可 规模化的,如果给定内存和磁盘空间等可利用的系统资源,其运行时间应当随数据库大小线性增加。 通过数据挖掘,可以从数据库提取有趣的知识、规律、或高层信息,并可以从不同角度观察或浏览。 发现的知识可以用于决策、过程控制、信息管理、查询处理、等等。因此,数据挖掘被信息产业界 认为是数据库系统最重要的前沿之一,是信息产业最有前途的交叉学科。 1.3 数据挖掘——在何种数据上进行? 本节,我们考察可以进行挖掘的各种数据存储。原则上讲,数据挖掘可以在任何类型的信息存 储上进行。这包括关系数据库、数据仓库、事务数据库、先进的数据库系统、展平的文件和 WWW。 先进的数据库系统包括面向对象和对象-关系数据库;面向特殊应用的数据库,如空间数据库、时间 序列数据库、文本数据库和多媒体数据库。挖掘的挑战和技术可能因存储系统而异。 尽管本书假定读者具有信息系统的基本知识,我们还是对以上提到的主要数据存储系统做简要 介绍。本节,我们还介绍编造的 AllElectronics 商店,它在本书各处用来解释概念。 1.3.1 关系数据库 数据库系统,也称数据库管理系统(DBMS),由一组内部相关的数据,称作数据库,和一组 管理和存取数据的软件程序组成。软件程序涉及如下机制:数据库结构定义,数据存储,并行、共 享或分布的数据访问,面对系统瘫痪或未授权的访问,确保数据的一致性和安全性。 关系数据库是表的集合,每个表都赋予一个唯一的名字。每个表包含一组属性(列或字段), 并通常存放大量元组(记录或行)。关系中的每个元组代表一个被唯一关键字标识的对象,并被一 组属性值描述。语义数据模型,如实体-联系(ER)数据模型,将数据库作为一组实体和它们之间 的联系进行建模。通常为关系数据库构造 ER 模型。 考虑下面的例子。 例 1.1 AllElectronics 公司由下列关系表描述:customer, item, employee 和 branch。这些表的片 段在图 1.6 中给出。 „ 关系 customer 由一组属性,包括顾客的唯一标识号(cust_ID),顾客的姓名、地址、年龄、职业、 年收入、信誉信息、分类等。 customer cast_ID name address ageincome credit_info ... C1 ... ... Smith,Sandy ... ... 4563 E.Hastings,Burnaby, BC,V5A 4S9, Canada ... 21 ... ... $27000 ... ... 1 ... ... ... ... ... items item_ID name brand category type price place_made supplier cost 13 18 ... high_res TV mutidisc CDplay Toshiba Sanyo ... high resolution mutidisc ... TV CD player ... $988.00 $369.00 ... Japan Japan ... Niko X Music Front ... $600.00 $120.00 ... employee empl_ID name category group salary commission E35 ... Jones,Jane ... home entertainment ... manager ... $18,000 ... 2% .. branch branch_ID name address B1 ... City Square ... 369 Cambie St.,Vancouver,BC V5L 3A2,Canada ... purchases trans_ID cast_ID empl_ID date time method_paid amount T100 ... C1 ... E55 ... 09/21/98 ... 15:45 ... Visa ... $1357.00 items_sold trans_ID item_ID qty T100 T100 ... 13 18 ... 1 2 ... works_at empl_ID brabch_ID E55 ... B1 ... 图 1.6: AllElectronics 关系数据库的关系片段 „ 类似地,关系 employee, branch 和 item 的每一个都包含一组属性,描述它们的性质。 „ 表也用于表示多个关系表之间的联系。对于我们的例子,包括 purchase(顾客购买商品,创建 一个由雇员处理的销售事务)和 work_at(雇员在的一个分店工作)。 关系数据可以通过数据库查询访问。数据库查询使用如 SQL 这样的关系查询语言,或借助于图 形用户界面书写。在后者,用户可以使用菜单指定包含在查询中的属性和属性上的限制。一个给定 的查询被转换成一系列关系操作,如连接、选择和投影,并被优化,以便有效地处理。查询可以提 取数据的一个指定的子集。假定你的工作是分析 AllElectronics 的数据。通过使用关系查询,你可以 提这样的问题:“显式一个上个季度销售的商品的列表”。关系查询语言也可以包含聚集函数,如 sum, avg(平均),count, max(最大)和 min(最小)。这些使得你可以问“给我显式上个月的总销 售,按分店分组”,或“多少销售事务出现在 12 月份?”,或“哪一位销售人员的销售额最高?”。 当数据挖掘用于关系数据库时,你可以进一步搜索趋势或数据模式。例如,数据挖掘系统可以 分析顾客数据,根据顾客的收入、年龄和以前的信誉信息预测新顾客的信誉风险。数据挖掘系统也 可以检测偏差,如,与以前的年份相比,哪种商品的销售出人预料。这种偏差可以进一步考察(例 如,包装是否有变化,或价格是否大幅度提高?)。 关系数据库是数据挖掘的最流行的、最丰富的数据源,因此它是我们数据挖掘研究的主要数据 形式。 1.3.2 数据仓库 假定 AllElectronics 是一个成功的跨国公司,分部遍及世界。每个分部有自己的一组数据库。 AllElectronics 的总裁要你提供公司第三季度每种商品、每个分部的销售分析。这是一个困难的任务, 特别是当相关数据散布在多个数据库,物理地存放在许多站点时。 如果 AllElectronics 有一个数据仓库,该任务将是容易的。数据仓库是一个从多个数据源收集的 信息存储,存放在一个一致的模式下,并通常驻留在单个站点。数据仓库通过数据清理、数据变换、 数据集成、数据装入和定期数据刷新构造。该过程在第 2、3 章详细研究。图 1.7 给出了 AllElectronics 的数据仓库的基本结构。 图 1.7:AllElectronics 典型的数据仓库结构 为便于制定决策,数据仓库中的数据围绕诸如顾客、商品、供应商和活动等主题组织。数据存 储,从历史的角度(如过去的 5-10 年)提供信息,并且是汇总的。例如,数据仓库不是存放每个销 售事务的细节,而是存放每个商店,或(汇总到较高层次)每个销售地区每类商品的销售事务汇总。 通常,数据仓库用多维数据库结构建模。其中,每个维对应于模式中一个或一组属性,每个单 元存放聚集度量,如 count 或 sales_amount。数据仓库的实际物理结构可以是关系数据存储或多维数 据方。它提供数据的多维视图,并允许快速访问预计算的和汇总的数据。 例 1.2 AllElectronics 的汇总销售数据数据方在图 1.8(a)中。该数据方有三个维:address(城市 值),time(季度值 Q1, Q2, Q3, Q4)和 item(商品类型值:家庭娱乐、计算机、电话、安全)。存 放在方体的每个单元中的聚集值是 sales_amount(单位:$1000)。例如,安全系统第一季度在 Vancouver 的总销售为$400,000,存放在单元中。其它方体可以用于存放每个 维上的聚集和,对应于使用不同的 SQL 分组得到的聚集值(例如,每个城市和季度,或每个季度和 商品,或每单个维的总销售量)。 图 1.8 一个通常用于数据仓库多维数据方,(a) 展示 AllElectronics 的 汇总数据 (b) 展示数据方(a)上的下钻与上卷结果。为便于观 察,只给出部分单元值 你可能会问:“我还听说过数据集市。数据仓库和数据集市的区别是什么?”数据仓库收集了 整个组织的主题信息,因此,它是企业范围的。另一方面,数据集市是数据仓库的一个部门子集。 它聚焦在选定的主题上,是部门范围的。 通过提供多维数据视图和汇总数据的预计算,数据仓库非常适合联机分析处理(OLAP)。OLAP 操作使用数据的领域背景知识,允许在不同的抽象层提供数据。这些操作适合不同的用户。OLAP 操作的例子包括下钻和上卷,它们允许用户在不同的汇总级别观察数据,如图 1.8(b)所示。例如, 可以对按季度汇总的销售数据下钻,观察按月汇总的数据。类似地,可以对按城市汇总的销售数据 上卷,观察按国家汇总的数据。 尽管数据仓库工具对于支持数据分析是有帮助的,但是仍需要更多的数据挖掘工具,以便进行 更深入的自动分析。数据仓库技术在第 2 章详细讨论。 1.3.3 事务数据库 一般地,事务数据库由一个文件组成,其中每个记录代表一个事务。通常,一个事务包含一个 唯一的事务标识号(trans_ID),和一个组成事务的项的列表(如,在商店购买的商品)。事务数据库 可能有一些与之相关联的附加表,包含关于销售的其它信息,如事务的日期、顾客的 ID 号、销售 者的 ID 号、销售分店,等等。 例 1.3 事务可以存放在表中,每个事务一个记录。AllElectronics 的事务数据库的片段在图 1.9 中给出。从关系数据库的观点,图 1.9 的销售表是一个嵌套的关系,因为属性”list of item_ID”包含 item 的集合。由于大部分关系数据库系统不支持嵌套关系结构,事务数据库通常存放在一个类似于图 1.9 中的表格式的展平的文件中,或展开到类似于图 1.6 的 items_sold 表的标准关系中。 sales trans_ID list of item_ID T100 ... I1,I3,I8,I16 ... 图 1.9:AllElectronics 销售事务数据库的片段 作为 AllElectronics 数据库的分析者,你想问“显示 Sandy Smith 购买的所有商品”或“有多少 事务包含商品号 I3?”。回答这种查询可能需要扫描整个事务数据库。 假定你想更深地挖掘数据,问“哪些商品适合一块销售?”这种“购物篮分析”使你能够将商 品捆绑成组,作为一种扩大销售的策略。例如,给定打印机与计算机经常一起销售的知识,你可以 向购买选定计算机的顾客提供对一种很贵的打印机打折,希望销售更多较贵的打印机。常规的数据 提取系统不能回答上面这种查询。然而,通过识别频繁一块销售的商品,事务数据的数据挖掘系统 可以做到。 1.3.4 高级数据库系统和高级数据库应用 关系数据库系统广泛地用于商务应用。随着数据库技术的发展,各种先进的数据库系统已经出 现并在开发中,以适应新的数据库应用需要。 新的数据库应用包括处理空间数据(如地图)、工程设计数据(如建筑设计、系统部件、集成 电路)、超文本和多媒体数据(包括文本、图象和声音数据)、时间相关的数据(如历史数据或股 票交换数据)和万维网(Internet 使得巨大的、广泛分布的信息存储可以利用)。这些应用需要有效 的数据结构和可规模化的方法,处理复杂的对象结构、变长记录、半结构化或无结构的数据,文本 和多媒体数据,以及具有复杂结构和动态变化的数据库模式。 为响应这些需求,开发了先进的数据库系统和面向特殊应用的数据库系统。这些包括面向对象 和对象-关系数据库系统、空间数据库系统、时间和时间序列数据库系统、异种和遗产数据库系统、 基于万维网的全球信息系统。 虽然这样的数据库或信息存储需要复杂的机制,以便有效地存储、提取和更新大量复杂的数据, 它们也为数据挖掘提供了肥沃的土壤,提出了挑战性的研究和实现问题。本节,我们将介绍上面列 举的每种高级数据库系统。 面向对象数据库 面向对象数据库基于面向对象程序设计范例。用一般术语,每个实体被看作一个对象。对于 AllElectronics 例子,对象可以是每个雇员、顾客、商品。涉及一个对象的数据和代码封装在一个单 元中。每个对象关联: „ 一个变量集,它描述数据。这对应于实体-联系和关系模型的属性。 „ 一个消息集,对象可以使用它们与其它对象,或与数据库系统的其它部分通讯。 „ 一个方法集,其中每个方法存放实现一个消息的代码。一旦收到消息,方法就返回一个响应值。 例如,消息 get_photo(employee)的方法将提取并返回给定雇员对象的照片。 共享公共特性集的对象可以归入一个对象类。每个对象都是其对象类的实例。对象类可以组成 类/子类层次结构,使得每个类代表该类对象共有的特性。例如,类 employee 可以包含变量 name, address 和 birthdate。假定类 sales_person 是 employee 的子类。一个 sales_person 对象将继承属于其 超类 employee 的所有变量。此外,它还具有作为一个销售员特有的所有变量(如,commission)。 这种类继承特性有利于信息共享。 对象-关系数据库 对象-关系数据库基于对象-关系数据模型构造。该模型通过提供处理复杂对象的丰富数据类型 和对象定位,扩充关系模型。此外,它还包含关系查询语言的特殊构造,以便管理增加的数据类型。 通过增加处理复杂数据类型、类层次结构和如上所述的对象继承,对象-关系模型扩充了基本关系模 型。对象-关系数据库在工业和应用正日趋流行。 在面向对象和对象-关系系统中的数据挖掘具有某些类似性。与关系数据挖掘相比,需要开发新 的技术,处理复杂对象结构、复杂数据类型、类和子类层次结构、特性继承以及方法和过程。 空间数据库 空间数据库包含涉及空间的信息。这种数据库包括地理(地图)数据库、VLSI 芯片设计数据库、 医疗和卫星图象数据库。空间数据可能以光栅格式提供,由 n 维位图或象素图构成。例如,一个 2 维卫星图象可以用光栅数据表示,每个象素存放一个给定区域的降雨量。地图也可以用向量格式提 供,其中,路、桥、建筑物和湖泊可以用诸如点、线、多边形和这些形状形成的分化和网络等基本 地理结构表示。 地理数据库有大量应用,包括从森林和生态规划,到提供关于电话和电缆、管道和下水系统位 置在内的公共信息服务。此外,地理数据库还用于车辆导航和分流系统。例如,一个用于出租车的 系统可以存储一个城市的地图,提供关于单行道、交通拥挤时从区域 A 到区域 B 的建议路径、饭店 和医院的位置、以及每个司机的当前位置等信息。 你可能会问:“空间数据库上可以进行何种数据挖掘?”数据挖掘可以发现描述座落在特定类 型地点(如,公园)的房屋特征。其它模式可能描述不同海拔高度山区的气候,或根据城市离主要 公路的距离描述都市贫困率的变化趋势。此外,可以构造“空间数据方”,将数据组织到多维结构 和层次中,OLAP 操作(如,下钻和上卷)可以在其上进行。 时间数据库和时间序列数据库 时间数据库和时间序列数据库都存放与时间有关的数据。时间数据库通常存放包含时间相关属 性的数据。这些属性可能涉及若干时间标签,每个都具有不同的语义。时间序列数据库存放随时间 变化的值序列,如,收集的股票交易数据。 数据挖掘技术可以用来发现数据库中对象演变特征或对象变化趋势。这些信息对于决策和规划 是有用的。例如,银行数据的挖掘可能有助于根据顾客的流量安排银行出纳员。可以挖掘股票交易 数据,发现可能帮助你制订投资策略的趋势(例如,何时是购买 AllElectronics 的股票的最佳时机?)。 通常,这种分析需要定义时间的多粒度。例如,时间可以按财政年、学年或日历年分解。年可以进 一步分解成季度或月。 文本数据库和多媒体数据库 文本数据库是包含对象文字描述的数据库。通常,这种词描述不是简单的关键词,而是长句子 或短文,如产品介绍、错误或故障报告、警告信息、汇总报告、笔记或其它文档。文本数据库可能 是高度非规格化的(如,万维网上的网页)。有些文本数据库可能是半结构化的(如 email 消息和 一些 HTML/XML 网页),而其它的可能是良结构化的(如图书馆数据库)。通常,具有很好结构 的文本数据库可以使用关系数据库系统实现。 “文本数据库上的数据挖掘可以发现什么?”说到底,可以发现对象类的一般描述,以及关键 词或内容的关联和文本对象的聚类行为。为做到这一点,需要将标准的数据挖掘技术与信息提取技 术和文本数据特有的层次构造(如字典和辞典),以及面向学科的(如化学、医学、法律或经济) 术语分类系统集成在一起。 多媒体数据库存放图象、音频和视频数据。它们用于基于图内容的提取、声音传递、录像点播、 万维网和识别口语命令的基于语音的用户界面等方面。多媒体数据库必须支持大对象,因为象视频 这样的数据对象可能需要数十亿字节的存储。还需要特殊的存储和检索技术,因为视频和音频数据 需要以稳定的、预先确定的速率实时检索,防止图象或声音间断和系统缓冲区溢出。这种数据称为 连续媒体数据。 对于多媒体数据库挖掘,需要将存储和检索技术与标准的数据挖掘方法集成在一起。有前途的 方法包括构造多媒体数据方、多媒体数据的多特征提取和基于相似的模式匹配。 异种数据库和遗产数据库 异种数据库由一组互连的、自治的成员数据库组成。这些成员相互通讯,以便交换信息和回答 查询。一个成员数据库中的对象可能与其它成员数据库中的对象很不相同,使得很难将它们的语义 吸收进一个整体的异种数据库中。 许多企业需要遗产数据库,作为信息技术长时间开发(包括使用不同的硬件和操作系统)的结 果。遗产数据库是一组异种数据库,它将不同的数据系统组合在一起。这些数据系统如关系或对象 -关系数据库、层次数据库、网状数据库、电子表格、多媒体数据库或文件系统。遗产数据库中的异 种数据库可以通过网内或网间计算机网络连接。 这种数据库的信息交换是困难的,因为需要考虑发散的语义,制定从一种表示到另一种表示的 精确转换规则。例如,考虑不同学校之间学生学业情况数据交换问题。每个学校可能有自己的计算 机系统和课程与评分体系。一所大学可能采用学季系统(每学期三个月——译注),开三门数据库 课程,并按由 A+到 F 评定成绩;而另一所可能采用学期系统,开两门数据库课程,并按由 1 到 10 评定成绩。很难制定这两所大学的课程-成绩转换精确的规则,使得信息交换很困难。通过将给定的 数据转换到较高的、更一般的概念层(对于学生成绩,如不及格、良好或优秀),数据挖掘技术可 以对此问题提供有趣的解,使得数据交换可以更容易地进行。 万维网 万维网和与之关联的分布信息服务(如,美国在线,Yahoo!, Alta Vista, Prodigy)提供了丰富的、 世界范围的联机信息服务;这里,数据对象被链接在一起,便于交互访问。用户通过链接,从一个 对象到另一个,寻找有趣的信息。这种系统对数据挖掘提供了大量机会和挑战。例如,理解用户的 访问模式不仅能够帮助改进系统设计(通过提供高度相关的对象间的有效访问),而且还可以引导 更好的市场决策(例如,通过在频繁访问的文档上布置广告,或提供更好的顾客/用户分类和行为分 析)。在这种分布式信息环境下,捕获用户访问模式称作挖掘路径遍历模式。 尽管网页看上去好看并且信息丰富,但它们实际上是非结构化的并且缺乏预定义的模式、类型 和格式。这样,对于系统地进行信息提取和数据挖掘,计算机很难理解各种网页的语义并把它们以 有组织的形式结构化。提供基于关键字的搜索服务,而不理解特定网页的上下文,只能给用户提供 有限的帮助。例如,基于单个关键字的网搜索可能返回数以百计的指针,指向包含该关键字的网页, 而其中大部分与用户期望的查找无关。数据挖掘可以提供比网搜索服务更多的帮助吗?数据挖掘能 够帮助我们学习网上信息的一般分布、网页特征和不同网页之间的关联吗?能够帮助我们找到特定 主题的权威网页吗?这些问题对高级的数据挖掘提出了新的挑战。 1.4 数据挖掘功能——可以挖掘什么类型的模式? 我们已经观察了可以进行数据挖掘的各种数据存储和数据库系统。现在,让我们考察可以挖掘 的数据模式。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。一般地,数据挖掘任务可以分两类: 描述和预测。描述性挖掘任务刻划数据库中数据的一般特性。预测性挖掘任务在当前数据上进行推 断,以进行预测。 在某些情况下,用户不知道他们的数据中什么类型的模式是有趣的,因此可能想并行地搜索多 种不同的模式。这样,重要的是,数据挖掘系统要能够挖掘多种类型的模式,以适应不同的用户需 求或不同的应用。此外,数据挖掘系统应当能够发现各种粒度(即,不同的抽象层)的模式。数据 挖掘系统应当允许用户给出提示,指导或聚焦有趣模式的搜索。由于有些模式并非对数据库中的所 有数据都成立,通常每个被发现的模式带上一个确定性或“可信性”度量。 数据挖掘功能以及它们可以发现的模式类型介绍如下。 1.4.1 概念/类描述:特征和区分 数据可以与类或概念相关联。例如,在 AllElectronics 商店,销售的商品类包括计算机和打印机, 顾客概念包括 bigSpenders 和 budgetSpenders。用汇总的、简洁的、精确的方式描述每个类和概念可 能是有用的。这种类或概念的描述称为类/概念描述。这种描述可以通过下述方法得到(1)数据特 征化,一般地汇总所研究类(通常称为目标类)的数据,或(2)数据区分,将目标类与一个或多 个比较类(通常称为对比类)进行比较,或(3)数据特征化和比较。 数据特征是目标类数据的一般特征或特性的汇总。通常,用户指定类的数据通过数据库查询收 集。例如,为研究上一年销售增加 10%的软件产品的特征,可以通过执行一个 SQL 查询收集关于这 些产品的数据。 有许多有效的方法,将数据特征化和汇总。例如,基于数据方的 OLAP 上卷操作(1.3.2 小节) 可以用来执行用户控制的、沿着指定维的数据汇总。该过程将在第 2 章介绍数据仓库时进一步详细 讨论。面向属性的归纳技术可以用来进行数据的泛化和特征化,而不必一步步地与用户交互。这一 技术将在第 5 章讨论。 数据特征的输出可以用多种形式提供。包括饼图、条图、曲线、多维数据方和包括交叉表在内 的多维表。结果描述也可以用泛化关系或规则(称作特征规则)形式提供。这些不同的输出形式和 它们的转换在第 5 章讨论。 例1.4 数据挖掘系统应当能够产生一年之内在AllElectronics花费$1000以上的顾客汇总特征的 描述。结果可能是顾客的一般轮廓,如年龄在 40-50、有工作、有很好的信誉度。系统将允许用户 在任意维下钻,如在 occupation 下钻,以便根据他们的职业来观察这些顾客。 数据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。目标类和对比 类由用户指定,而对应的数据通过数据库查询提取。例如,你可能希望将上一年销售增加 10%的软 件产品与同一时期销售至少下降 30%的那些进行比较。用于数据区分的方法与用于数据特征的那些 类似。 “区分描述如何输出?”输出的形式类似于特征描述,但区分描述应当包括比较度量,帮助区 分目标类和对比类。用规则表示的区分描述称为区分规则。用户应当能够对特征和区分描述的输出 进行操作。 例 1.5 数据挖掘系统应当能够比较两组 AllElectronics 顾客,如定期(每月多于 2 次)购买计 算机产品的顾客和偶尔(即,每年少于 3 次)购买这种产品的顾客。结果描述可能是一般的比较轮 廓,如经常购买这种产品的顾客 80%在 20-40 岁之间,受过大学教育;而不经常购买这种产品的顾 客 60%或者太老,或者太年青,没有大学学位。沿着维下钻,如沿 occupation 维,或添加新的维, 如 income_level,可以帮助发现两类之间的更多区分特性。 概念描述,包括特征和区分,是第 5 章的主题。 1.4.2 关联分析 “什么是关联分析?”关联分析发现关联规则,这些规则展示属性-值频繁地在给定数据集中一 起出现的条件。关联分析广泛用于购物篮或事务数据分析。 更形式地,关联规则是形如 X ⇒ Y,即 ”A1 ∧...∧ Am ⇒ B1 ∧...∧ Bn”的规则;其中, Ai (i∈{1,...,m}), Bj (j∈{1,...,n})是属性-值对。关联规则解释为“满足 X 中条件的数据库元组多半也满足 Y 中条件”。 例 1.6 给定 AllElectronics 关系数据库,一个数据挖掘系统可能发现如下形式的规则 )"_",()"3020",()"2920",( playerCDXbuysKXincomeXage ⇒−∧− [support = 2%,confidence = 60%] 其中,X 是变量,代表顾客。该规则是说,所研究的 AllElectronics 顾客 2%(支持度)在 20-29 岁, 年收入 20-29K,并且在 AllElectronics 购买 CD 机。这个年龄和收入组的顾客购买 CD 机的可能性有 60%(置信度或可信性)。 注意,这是一个以上属性之间(即 age, income 和 buys)的关联。采用多维数据库使用的术语, 每个属性称为一个维,上面的规则可以称作多维关联规则。 假定作为 AllElectronics 的市场部经理,你想知道在一个事务中,哪些商品经常一块购买。这种 规则的一个例子是 )"",()"",( softwareTcontainscomputerTcontains ⇒ [support = 1%,confidence =50%] 该规则是说,如果事务 T 包含”computer”,则它也包含”software”的可能性有 50%,并且所有事务的 1%包含二者。这个规则涉及单个重复的属性或谓词(即,contains)。包含单个谓词的关联规则称 作单维关联规则。去掉谓词符号,上面的规则可以简单地写成 computer ⇒ software[1%,50%]。 近年来,已经提出了许多有效的关联规则挖掘算法。关联规则挖掘在第 6 章详细讨论。 1.4.3 分类和预测 分类是这样的过程,它找描述或识别数据类或概念的模型(或函数),以便能够使用模型预测类 标号未知的对象。导出模型是基于对训练数据集(即,其类标号已知的数据对象)的分析。 “如何提供导出模型?”导出模式可以用多种形式表示,如分类(IF-THEN)规则、判定树、 数学公式、或神经网络。判定树是一个类似于流程图的结构,每个结点代表一个属性值上的测试, 每个分枝代表测试的一个输出,树叶代表类或类分布。判定树容易转换成分类规则。当用于分类时, 神经网络是一组类似于神经元的处理单元,单元之间加权连接。 分类可以用来预测数据对象的类标号。然而,在某些应用中,人们可能希望预测某些遗漏的或 不知道的数据值,而不是类标号。当被预测的值是数值数据时,通常称之为预测。尽管预测可以涉 及数据值预测和类标号预测,通常预测限于值预测,并因此不同于分类。预测也包含基于可用数据 的分布趋势识别。 相关分析可能需要在分类和预测之前进行,它试图识别对于分类和预测无用的属性。这些属性 应当排除。 例 1.7 假定作为 AllElectronics 的销售经理,你想根据对销售活动的反映,对商店的商品集合 分成三大类:好的反映,中等反映和差的反映。你想根据商品的描述特性,如 price, brand, place_made 和 category,对这三类的每一种导出模型。结果分类将最大限度地区别每一个类,提供有组织的数 据集视图。假定结果分类用判定树的形式表示。例如,判定树可能把 price 看作最能区分三个类的 因素。该树可能揭示,在 price 之后,帮助进一步区分每类对象的其它特性包括 brand 和 place_made。 这样的判定树可以帮助你理解给定销售活动的影响,并帮助你设计未来更有效的销售活动。 第 7 章将详细讨论分类和预测。 1.4.4 聚类分析 “何为聚类分析?”与分类和预测不同,聚类分析数据对象,而不考虑已知的类标号。一般地, 训练数据中不提供类标号,因为不知道从何开始。聚类可以产生这种标号。对象根据最大化类内的 相似性、最小化类间的相似性的原则进行聚类或分组。即,对象的聚类这样形成,使得在一个聚类 中的对象具有很高的相似性,而与其它聚类中的对象很不相似。所形成的每个聚类可以看作一个对 象类,由它可以导出规则。聚类也便于分类编制,将观察组织成类分层结构,类似的事件组织在一 起。 例 1.8 聚类分析可以在 AllElectronics 的顾客数据上进行,识别顾客的同类子群。这些聚类可 以表示每个购物目标群。图 1.10 展示一个城市内顾客的 2-D 图。数据点的三个聚类是显而易见的。 聚类分析形成第 8 章的主题。 1.4.5 局外者分析 数据库中可能包含一些数据对象,它们与数据的一般行为或模型不一致。这些数据对象是局外 者。大部分数据挖掘方法将局外者视为噪音或例外而丢弃。然而,在一些应用中(如,欺骗检测), 罕见的事件可能比正规出现的那些更有趣。局外者数据分析称作局外者挖掘。 局外者可以使用统计试验检测。它假定一个数据分布或概率模型,并使用距离度量,到其它聚 类的距离很大的对象被视为局外者。基于偏差的方法通过考察一群对象主要特征上的差别识别局外 者,而不是使用统计或距离度量。 图 1.10 关于一个城市内顾客的 2-D 图,显示了 3 个聚类,每个 聚类的“中心”用“+”标记 例 1.9 局外者分析可以发现信用卡欺骗。通过检测一个给定帐号与正常的付费相比,付款数额 特别大来发现信用卡欺骗性使用。局外者值还可以通过购物地点和类型,或购物频率来检测。 局外者分析也在第 8 章讨论。 1.4.6 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势,并对其建模。尽管这可能包括时间相 关数据的特征、区分、关联、分类或聚类,这类分析的不同特点包括时间序列数据分析、序列或周 期模式匹配和基于类似性的数据分析。 例 1.10 假定你有纽约股票交易所过去几年的主要股票市场(时间序列)数据,并希望调查高 科技工业公司股份。股票数据挖掘研究可以识别整个股票市场和特定的公司的股票演变规律。这种 规律可以帮助预测股票市场价格的未来走向,帮助你对股票投资作出决策。 数据演变分析将在第 9 章进一步讨论。 1.5 所有模式都是有趣的吗? 数据挖掘系统具有产生数以千计,甚至数以万计模式或规则的潜在能力。 你可能会问:“所有模式都是有趣的吗?”答案是否定的。实际上,对于给定的用户,在可能 产生的模式中,只有一小部分是他感兴趣的。 这对数据挖掘系统提出了一系列的问题。你可能会想:“什么样的模式是有趣的?数据挖掘系 统能够产生所有有趣的模式吗?数据挖掘系统能够仅产生有趣的模式吗?” 对于第一个问题,一个模式是有趣的,如果(1)它易于被人理解,(2)在某种程度上,对于 新的或测试数据是有效的,(3)是潜在有用的,(4)是新颖的。如果一个模式符合用户确信的某 种假设,它也是有趣的。有趣的模式表示知识。 存在一些模式兴趣度的客观度量。这些基于所发现模式的结构和关于它们的统计。对于形如 X⇒Y 的关联规则,一种客观度量是规则的支持度。规则的支持度表示满足规则的样本百分比。支持 度是概率 P (X ∪ Y ),其中,X ∪ Y 表示同时包含 X 和 Y 的事务;即,项集 X 和 Y 的并。关联规则 的另一种客观度量是置信度。置信度是条件概率 P (Y | X);即,包含 X 的事务也包含 Y 的概率。更 形式地,支持度和置信度定义为 support (X ⇒ Y ) = P (X ∪ Y ) confidence (X ⇒ Y ) = P (Y | X) 一般地,每个兴趣度度量都与一个阈值相关联,该阈值可以由用户控制。例如,不满足置信度 阈值 50%的规则可以认为是无趣的。低于阈值的规则可能反映噪音、例外,或少数情况,可能不太 有价值。 尽管客观度量可以帮助识别有趣的模式,但是仅有这些还不够,还要结合反映特定用户需要和 兴趣的主观度量。例如,对于市场经理,描述频繁在 AllElectronics 购物的顾客特性的模式应当是有 趣的;但对于研究同一数据库,分析雇员业绩模式的分析者,它可能不是有趣的。此外,有些根据 客观标准有趣的模式可能反映一般知识,因而实际上并不令人感兴趣。主观兴趣度度量基于用户对 数据的确信。这种度量发现模式是有趣的,如果它们是出乎意料的(根据用户的确信),或者提供 用户可以采取行动的策略信息。在后一种情况下,这样的模式称为可行动的。意料中的模式也可能 是有趣的,如果它们证实了用户希望验证的假设,或与用户的预感相似。 第二个问题——“数据挖掘系统能够产生所有有趣的模式吗?”——涉及数据挖掘算法的完全 性。期望数据挖掘系统产生所有可能的模式是不现实的和低效的。实际上,应当根据用户提供的限 制和兴趣度对搜索聚焦。对于某些数据挖掘任务,这通常能够确保算法的完全性。关联规则挖掘就 是一个例子,那里,使用限制和兴趣度度量可以确保挖掘的完全性。所涉及的方法细节将在第 6 章 详细考察。 最后,第三个问题——“数据挖掘系统能够仅产生有趣的模式吗?”是数据挖掘的优化问题。 对于数据挖掘系统,仅产生有趣的模式是非常期望的。这对于用户和数据挖掘系统是非常有效的, 因为这样就不需要搜索所产生的模式,以便识别真正有趣的模式。在这方面已经有了进展。然而, 在数据挖掘中,这种优化仍然是个挑战。 为了有效地发现对于给定用户有价值的模式,兴趣度度量是必需的。这种度量可以在数据挖掘 步之后使用,根据它们的兴趣度评估所发现的模式,过滤掉不感兴趣的那些。更重要的是这种度量 可以用来指导和限制发现过程,剪去模式空间中不满足预先设定的兴趣度限制的子集,改善搜索性 能。 对于每类可挖掘的模式,评估兴趣度和使用它们改善数据挖掘的有效性的方法将在全书加以讨 论。 1.6 数据挖掘系统的分类 数据挖掘是一个交叉科学领域,受多个学科影响(见图 1.11),包括数据库系统、统计、机器 学习、可视化和信息科学。此外,依赖于所用的数据挖掘方法,可以使用其它学科的技术,如神经 网络、模糊/粗糙集理论、知识表示、归纳逻辑程序设计、或高性能计算。依赖于所挖掘的数据类型 或给定的数据挖掘应用,数据挖掘系统也可能集成空间数据分析、信息提取、模式识别、图象分析、 信号处理、计算机图形学、Web 技术、经济、或心理学领域的技术。 图 1.11:数据挖掘受多学科的影响 由于数据挖掘源于多个学科,因此数据挖掘研究就产生了大量的、各种不同类型数据挖掘系统。 这样,就需要对数据挖掘系统给出一个清楚的分类。这种分类可以帮助用户区分数据挖掘系统,确 定最适合其需要的数据挖掘系统。根据不同的标准,数据挖掘系统可以分类如下: 根据挖掘的数据库类型分类:数据挖掘系统可以根据挖掘的数据库类型分类。数据库系统本身 可以根据不同的标准(如数据模型,或数据或所涉及的应用类型)分类,每一类可能需要自己的数 据挖掘技术。这样,数据挖掘系统就可以相应分类。 例如,如果根据数据模型分类,我们可以有关系的、事务的、面向对象的、对象-关系的、或数 据仓库的数据挖掘系统。如果根据所处理的数据的特定类型分类,我们有空间的、时间序列的、文 本的、或多媒体的数据挖掘系统,或 WWW 数据挖掘系统。 根据挖掘的知识类型分类:数据挖掘系统可以根据所挖掘的知识类型分类。即,根据数据挖掘 的功能,如特征、区分、关联、聚类、局外者、趋势和演化分析、偏差分析、类似性分析等分类。 一个全面的数据挖掘系统应当提供多种和/或集成的数据挖掘功能。 此外,数据挖掘系统可以根据所挖掘的知识的粒度或抽象层进行区分,包括泛化知识(在高抽 象层),原始层知识(在原始数据层),或多层知识(考虑若干抽象层)。一个先进的数据挖掘系 统应当支持多抽象层的知识发现。 数据挖掘系统还可以分类为挖掘数据规律(通常出现的模式)和数据反规律(如例外或局外者)。 一般地,概念描述、关联分析、分类、预测和聚类挖掘数据规律,将局外者作为噪音排除。这些方 法也能帮助检测局外者。 根据所用的技术分类:数据挖掘系统也可以根据所用的数据挖掘技术分类。这些技术可以根据 用户交互程度(例如,自动系统、交互探查系统、查询驱动系统),或所用的数据分析方法(例如, 面向数据库或数据仓库的技术,机器学习、统计、可视化、模式识别、神经网络等等)描述。复杂 的数据挖掘系统通常采用多种数据挖掘技术,或采用有效的、集成的技术,结合一些方法的优点。 根据应用分类:数据挖掘系统可以根据其应用分类。例如,可能有些数据挖掘系统特别适合财 政、电讯、DNA、股票市场、e_mail 等等。不同的应用通常需要集成对于该应用特别有效的方法。 因此,普通的、全能的数据挖掘系统可能并不适合特定领域的挖掘任务。 本书的第 5 章至第 8 章根据所挖掘的知识类型组织。在第 9 章,我们讨论在各种先进的数据库 系统上,复杂的数据类型的挖掘。第 10 章讨论一些数据挖掘应用。 1.7 数据挖掘的主要问题 本书强调数据挖掘的主要问题,考虑挖掘技术、用户界面、性能和各种数据类型。这些问题介 绍如下: 数据挖掘技术和用户界面问题:这反映所挖掘的知识类型、在多粒度上挖掘知识的能力、领域 知识的使用、特定的挖掘和知识显示。 „ 在数据库中挖掘不同类型的知识:由于不同的用户可能对不同类型的知识感兴趣,数据挖掘系 统应当覆盖广谱的数据分析和知识发现任务,包括数据特征、区分、关联、聚类、趋势、偏差 分析和类似性分析。这些任务可能以不同的方式使用相同的数据库,并需要开发大量数据挖掘 技术。 „ 多个抽象层的交互知识挖掘:由于很难准确地知道能够在数据库中发现什么,数据挖掘过程应 当是交互的。对于包含大量数据的数据库,应当使用适当的选样技术,进行交互式数据探查。 交互式挖掘允许用户聚焦搜索模式,根据返回的结果提出和精炼数据挖掘请求。特殊地,类似 于 OLAP 在数据方上做的那样,应当通过交互地在数据空间和知识空间下钻、上卷和转轴,挖 掘知识。用这种方法,用户可以与数据挖掘系统交互,以不同的粒度和从不同的角度观察数据 和发现模式。 „ 结合背景知识:可以使用背景知识或关于所研究领域的信息来指导发现过程,并使得发现的模 式以简洁的形式,在不同的抽象层表示。关于数据库的领域知识,如完整性限制和演绎规则, 可以帮助聚焦和加快数据挖掘过程,或评估发现的模式的兴趣度。 „ 数据挖掘查询语言和特定的数据挖掘:关系查询语言(如 SQL)允许用户提出特定的数据提取 查询。类似地,需要开发高级数据挖掘查询语言,使得用户通过说明分析任务的相关数据集、 领域知识、所挖掘的数据类型、被发现的模式必须满足的条件和兴趣度限制,描述特定的数据 挖掘任务。这种语言应当与数据库或数据仓库查询语言集成,并且对于有效的、灵活的数据挖 掘是优化的。 „ 数据挖掘结果的表示和显示:发现的知识应当用高级语言、可视化表示形式、或其它表示形式 表示,使得知识易于理解,能够直接被人使用。如果数据挖掘系统是交互的,这一点尤为重要。 这要求系统采用有表达能力的知识表示技术,如树、表、图、图表、交叉表、矩阵或曲线。 „ 处理噪音和不完全数据:存放在数据库中数据可能反映噪音、例外情况、或不完全的数据对象。 这些对象可能搞乱分析过程,导致数据与所构造的知识模型过分适应。其结果是,所发现的模 式的精确性可能很差。需要处理数据噪音的数据清理方法和数据分析方法,以及发现和分析例 外情况的局外者挖掘方法。 „ 模式评估——兴趣度问题:数据挖掘系统可能发现数以千计的模式。对于给定的用户,许多模 式不是有趣的,它们表示平凡知识或缺乏新颖性。关于开发模式兴趣度的评估技术,特别是关 于给定用户类,基于用户的信赖或期望,评估模式价值的主观度量,仍然存在一些挑战。使用 兴趣度度量,指导发现过程和压缩搜索空间,是又一个活跃的研究领域。 性能问题:这包括数据挖掘算法的有效性、可规模性和并行处理。 „ 数据挖掘算法的有效性和可规模性:为了有效地从数据库中大量数据提取信息,数据挖掘算法 必须是有效的和可规模化的。换一句话说,对于大型数据库,数据挖掘算法的运行时间必须是 可预计的和可接受的。从数据库角度,有效性和可规模性是数据挖掘系统实现的关键问题。上 面讨论的挖掘技术和用户交互的大多数问题,也必须考虑有效性和可规模性。 „ 并行、分布和增量挖掘算法:许多数据库的大容量、数据的广泛分布和一些数据挖掘算法的计 算复杂性是促使开发并行和分布式数据挖掘算法的因素。这些算法将数据划分成部分,这些部 分可以并行处理,然后合并每部分的结果。此外,有些数据挖掘过程的高花费导致了对增量数 据挖掘算法的需要。增量算法与数据库更新结合在一起,而不必重新挖掘全部数据。这种算法 渐增地进行知识更新,修正和加强先前业已发现的知识。 关于数据库类型的多样性问题: „ 关系的和复杂的数据类型的处理:由于关系数据库和数据仓库已经广泛使用,对它们开发有效 的数据挖掘系统是重要的。然而,其它数据库可能包含复杂的数据对象、超文本和多媒体数据、 空间数据、时间数据、或事务数据。由于数据类型的多样性和数据挖掘的目标不同,指望一个 系统挖掘所有类型的数据是不现实的。为挖掘特定类型的数据,应当构造特定的数据挖掘系统。 这样,对于不同类型的数据,我们可能有不同的数据挖掘系统。 „ 由异种数据库和全球信息系统挖掘信息:局域和广域(如 Internet)计算机网络连接了许多数据 源,形成了大的、分布的和异种的数据库。从具有不同数据语义的结构的、半结构的、和无结 构的不同数据源发现知识,对数据挖掘提出了巨大挑战。数据挖掘可以帮助发现多个异种数据 库中的数据规律,这些规律多半难以被简单的查询系统发现,并可以改进异种数据库信息交换 和协同操作的性能。Web 挖掘发现关于 Web 连接、Web 使用和 Web 动态情况的有趣知识,已 经成为数据挖掘的一个非常具有挑战性的领域。 以上问题是数据挖掘技术未来发展的的主要需求和挑战。在近来的数据挖掘研究和开发中,一 些挑战业已受到关注,并已成为必备的,而另一些仍处于研究阶段。然而,这些问题将继续刺激进 一步的研究和改进。涉及数据挖掘应用、保密性和社会影响的问题将在本书的最后一章,第 10 章 讨论。 1.8 总结 „ 数据库技术已经从原始的数据处理,发展到开发具有查询和事务处理能力的数据库管理系统。 进一步的发展导致越来越需要有效的数据分析和数据理解工具。这种需求是各种应用收集的数 据爆炸性增长的必然结果;这些应用包括商务和管理、行政管理、科学和工程、环境控制。 „ 数据挖掘是从大量数据中发现有趣模式,这些数据可以存放在数据库、数据仓库或其它信息存 储中。这是一个年青的跨学科领域,源于诸如数据库系统、数据仓库、统计、机器学习、数据 可视频化、信息提取和高性能计算。其它有贡献的领域包括神经网络、模式识别、空间数据分 析、图象数据库、信号处理和一些应用领域,包括商务、经济和生物信息学。 „ 知识发现过程包括数据清理、数据集成、数据变换、数据挖掘、模式评估和知识表示。 „ 数据模式可以从不同类型的数据库挖掘;如关系数据库,数据仓库,事务的、对象-关系的和面 向对象的数据库。有趣的数据模式也可以从其它类型的信息存储中提取,包括空间的、时间相 关的、文本的、多媒体的和遗产数据库,以及万维网。 „ 数据仓库是一种数据的长期存储,这些数据来自多数据源,是有组织的,以便支持管理决策。 这些数据在一种一致的模式下存放,并且通常是汇总的。数据仓库提供一些数据分析能力,称 作 OLAP(联机分析处理)。 „ 数据挖掘功能包括发现概念/类描述、关联、分类、预测、聚类、趋势分析、偏差分析和类似性 分析。特征和区分是数据汇总的形式。 „ 模式提供知识,如果它易于被人理解、在某种程度上对于测试数据是有效的、潜在有用的、新 颖的,或者它验证了用户关注的某种预感。模式兴趣度度量,无论是客观的还是主观的,都可 以用来指导发现过程。 „ 数据挖掘系统可以根据所挖掘的数据库类型、所挖掘的知识类型、或所使用的技术加以分类。 „ 大型数据库中有效的数据挖掘对于研究者和开发者提出了大量需求和巨大的挑战。问题涉及数 据挖掘技术、用户交互、性能和可规模性、以及大量不同数据类型的处理。其它问题包括数据 挖掘的应用开发和它们的社会影响。 习题 1.1 什么是数据挖掘?在你的回答中,强调以下问题: (a) 它是又一个骗局吗? (b) 它是一种从数据库、统计和机器学习发展的技术的简单转换吗? (c) 解释数据库技术发展如何导致数据挖掘。 (d) 当把数据挖掘看作知识发现过程时,描述数据挖掘所涉及的步骤。 1.2 给出一个例子,其中数据挖掘对于商务的成功是至关重要的。该商务需要什么数据挖掘功能? 它们能够由数据查询处理或简单的统计分析来实现吗? 1.3 假定你是 Big-University 的软件工程师,任务是设计一个数据挖掘系统,分析学校课程数据库。 该数据库包括如下信息:每个学生的姓名、地址和状态(例如,本科生或研究生)、所修课程, 以及他们的 GPA。描述你要选取的结构。该结构的每个成分的作用是什么? 1.4 数据仓库和数据库有何不同?它们有哪些相似之处? 1.5 简述以下高级数据库系统和应用:面向对象数据库、空间数据库、文本数据库、多媒体数据库、 万维网。 1.6 定义下列数据挖掘功能:特征、区分、关联、分类、预测、聚类、演变分析。使用你熟悉的生 活中的数据库,给出每种数据挖掘功能的例子。 1.7 区分和分类的差别是什么?特征和聚类的差别是什么?分类和预测呢?对于每一对任务,它们 有何相似之处? 1.8 根据你的观察,描述一个可能的知识类型,它需要由数据挖掘方法发现,但本章未列出。它需 要一种不同于本章列举的数据挖掘技术吗? 1.9 描述关于数据挖掘技术和用户交互问题的三个数据挖掘挑战。 1.10 描述关于性能问题的两个数据挖掘挑战。 文献注释 Piatetsky-Shapiro 和 Frawley 编辑的书 Knowledge Discovery in Databases [PSF91]是数据库中知识 发现早期研究论文的汇集。Fayyad, Piatetsky-Shapiro, Smyth 和 Uthurusamy 编辑的书 Advance in Knowledge Discovery and Data Mining[FPS+96]是一本知识发现和数据挖掘研究成果的很好的汇集。 其它数据挖掘书籍包括 Weiss 和 Indurkhya 的 Predictive Data Mining [WI98],Michalski, Brakto 和 Kubat 的 Machine Learning and Data Mining: Methods and Applications [MBK98],Westphal 和 Blaxton 的 Data Mining Solutions: Methoda and Tools for Solving Real-World Problems [WB98],Berry 和 Linoff 的 The Art and Science of Customer Relationship Management [BL99],Berson, Smith 和 Thearling 的 Building Data Mining Applications for CRM [BST99],和 Groth 的 Data Mining: Building Competitive Advantadge [Gro99]。还有一些书包含知识发现特定方面应用的论文,如 Ziarko 编辑的 Rough Sets, Fuzzy Sets and Knowledge Discovery [Zia94],以及一些数据挖掘指南手册,如 ACM 出版社出版的 Tutorial Notes of the 1999 International Conference on Knowledge Discovery and Data Mining (KDD’99)。 KDD Nuggets 是一个包含知识发现和数据挖掘有关信息的定期的、免费的电子通讯。投稿可以 连同描述主题行(和 URL)用电子邮件发往 editor@kdnuggets.com。关于订阅的信息可以在 http://www.kdnuggets.com/news/subscribe.html 找到。自 1991 年以来,KDD Nuggets 已被 Piatetsky_Shapiro 调整。位于 http://www.kdnuggets.com/的 Internet 的站点 Knowledge Discovery Mine 包含大量关于 KDD 的信息。 数据挖掘界于 1995 年开始了它的第一届次知识发现与数据挖掘国际学术会议 [FU96]。该会议 是由 1989 至 1994 年举行的四次数据库中知识发现国际研讨会[PS89,PS91a,FU93,FU94]发展起 来的。数据挖掘研究界于 1998 年建立起一个新的学术组织 ACM-SIGKDD,ACM 下的数据库中知 识发现专业组。1999 年 ACM-SIGKDD 组织了第五届知识发现与数据挖掘国际学术会议(KDD’99)。 专题杂志 Data Mining and Knowledge Discovery 自 1997 年起由 Kluwers 出版社出版。ACM-SIGKDD 还出版一种季刊电子通讯 SIGKDD Explorations,SIGKDD 成员可以使用。还有一些其它国际或地区 性数据挖掘会议,如,知识发现与数据挖掘太平洋亚洲会议(PAKDD),数据库中知识发现原理与 实践欧洲会议(PKDD),和数据仓库与知识发现国际会议(DaWaK)。 数据挖掘研究还在出版的书籍、会议、以及数据库、统计、机器学习和数据可视化杂志上发表。 源于这些的文献列举如下。 数据库系统的流行教科书包括 Ullamn 的 Principles of Database and Knowledege-Base Systems, Vol. 1 [Ull88],Elmasri 和 Navathe 的 Fundamentals of Database Systems,2nd ed.[EN94],Silberschatz, Korth 和 Sudarshan 的 Database System Concepts [SK97],Ullman 和 Widom 的 A First Course in Database Systems [UW97],和 Ramakrishnan 和 Gehrke 的 Database Management Systems, 3rd ed. [RG00]。数据库系统的文章汇集见 Stonebraker 和 Hellerstein 编辑的 Readings in Database Systems [SH98]。关于数据库系统的成就与研究挑战的回顾与讨论在 Stonebraker, Agrawal, Dayal 等[SAD+93] 和 Silberschatz, Stonebraker 和 Ullman [SSU96]中找到。 在过去的几年中,许多关于数据仓库技术、系统和应用的书籍已经出版。如,Kimball 的 The Data Warehouse Toolkit [Kim96],Inmon 的 Building the Data Warehouse [Inm96],Thomsen 的 OLAP Solutions: Building Mulyidimensional Information Systems [Tho97]。Chaudhuri 和 Dayal [CD97]给出了 数据仓库技术的全面回顾。 涉及数据挖掘和数据仓库的研究结果已在许多数据库国际学术会议论文集发表,包括 ACM-SIGMOD 数据管理国际会议(SIGMOD ),超大型数据库国际会议(VLDB ), ACM-SIGMOD-SIGART 数据库原理研讨会(PODS),数据工程国际会议(ICDE),扩展数据库 技术国际会议(EDBT),数据库理论国际会议(ICDT),信息与知识管理国际会议(CIKM), 数据库与专家系统应用国际会议(DEXA),和数据库系统高级应用国际会议(DASFAA)。数据 挖掘研究也发表在主要数据库杂志上,包括 IEEE 知识与数据工程汇刊(TKDE),ACM 数据库系 统汇刊(TODS),ACM 杂志(JACM),信息系统,VLDB 杂志,数据与知识工程,和智能信息 系统国际杂志(JIIS)。 有许多教材涵盖了统计分析的不同主题,如,Devore 的 Probability and Statistics for Engineering and Science, 4th ed. [Dev95],Neter, Kutner, Nachtsheim 和 Wasserman 的 Applied Linear Statistical Models, 4th ed. [NKNW96],Dobson 的 An Introduction to Generalized Linear models [Dob90],Shumway 的 Applied Statistical Time Series Analysis 3rd ed. [Shu88],和 Johnson 和 Wichern 的 Applied Multivariate Statistical Analysis, 3rd ed.[JW92] 统计研究发表在一些主要的统计会议上,包括联合统计会议,皇家统计会国际会议,界面研讨 会:计算科学与统计。其它刊物源包括皇家统计会杂志,统计年鉴,美国统计学会杂志,Technometrics, 和 Biometrika。 机器学习方面的教材和书籍包括 Michalski 等编辑的 Machine Learning, An Artifical Intelligence Approach, Vols. 1-4 [MCM83,MCM86,KM90,MT94],Quinlan 的 C4.5: Programs for Machine Learning [Qui93],Langley 的 Elements of Machine Learning [Lan96],和 Mitchell 的 Machine Learning [M97]。 Weiss 和 Kulikowski 的书 Cmputer Systemthat Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems [WK91]比较了若干不同领域的分类和比 较方法。一本编辑的机器学习论文汇集见 Shavlik 和 Dietterich 的 Readingd in Machine Learning [SD90]。 机器学习研究发表在一些大型机器学习和人工智能会议论文集上,包括机器学习国际会议 (ML),ACM 计算学习理论会议(COLT),人工智能国际联合会议(IJCAI),和美国人工智能 学会会议(AAAI)。其它出版源包括主要的机器学习、人工智能和知识系统杂志,其中,有些上 面已经提到。其余的包括机器学习(ML),人工智能杂志(AI),认知科学。从统计模式识别角 度的分类回顾可以在 Duda 和 Hart [DH73]中找到。 数据可视化技术的先驱者工作在 Tufte 的 The Visual Display of Quantitative Information [T83]和 Envisioning Information [Tuf90],以及 Bertin 的 Graphics and Graphic Information Processing [Ber81] 中介绍。Keim 的 Visual Techniques for Exploring Databases [Kei97]给出了数据挖掘可视化的指南。 可视化主要的会议和研讨会包括 ACM 计算机系统中人的因素(CHI),可视化,以及信息可视化 国际研讨会。可视化研究也发表在可视化和计算机图形学汇刊,计算和图形统计杂志,以及 IEEE 计算机图形学及其应用。 第二章 数据仓库和数据挖掘的 OLAP 技术 构造数据仓库涉及数据清理和数据集成,可以看作数据挖掘的一个重要预处理步骤。此外,数 据仓库提供联机分析处理(OLAP)工具,用于各种粒度的多维数据分析,有利于有效的数据挖掘。进 一步讲,许多其它数据挖掘功能,如分类、预测、关联、聚集,都可以与 OLAP 操作集成,以加强 多个抽象层上的交互知识挖掘。因此,数据仓库已经成为数据分析和联机数据分析处理日趋重要的 平台,并将为数据挖掘提供有效的平台。在系统地介绍数据挖掘技术之前,我们概括地介绍数据仓 库技术。对于理解数据挖掘技术,这种概述是必要的。 本章,你将学习数据仓库和 OLAP 技术使用的基本概念、一般结构和主要实现技术,以及它们 与数据挖掘的联系。 2.1 什么是数据仓库? 数据仓库为商务运作提供结构与工具,以便系统地组织、理解和使用数据进行决策。大量组织 机构已经发现,在当今这个充满竞争、快速发展的世界,数据仓库是一个有价值的工具。在过去的 几年中,许多公司已花费数百万美元,建立企业范围的数据仓库。许多人感到,随着工业竞争的加 剧,数据仓库成了必备的最新营销武器——通过更多地了解客户需求而保住客户的途径。 “那么”,你可能会充满神秘地问,“到底什么是数据仓库?”数据仓库已被多种方式定义, 使得很难严格地定义它。宽松地讲,数据仓库是一个数据库,它与组织机构的操作数据库分别维护。 数据仓库系统允许将各种应用系统集成在一起,为统一的历史数据分析提供坚实的平台,对信息处 理提供支持。 按照 W. H. Inmon,一位数据仓库系统构造方面的领头建筑师的说法,“数据仓库是一个面向 主题的、集成的、时变的、非易失的数据集合,支持管理决策制定”[Inm96]。这个简短、全面的 定义指出了数据仓库的主要特征。四个关键词,面向主题的、集成的、时变的、非易失的,将数据 仓库与其它数据存储系统(如,关系数据库系统、事务处理系统、和文件系统)相区别。让我们进 一步看看这些关键特征。 „ 面向主题的:数据仓库围绕一些主题,如顾客、供应商、产品和销售组织。数据仓库关注决策 者的数据建模与分析,而不是构造组织机构的日常操作和事务处理。因此,数据仓库排除对于 决策无用的数据,提供特定主题的简明视图。 „ 集成的:通常,构造数据仓库是将多个异种数据源,如关系数据库、一般文件和联机事务处理 记录,集成在一起。使用数据清理和数据集成技术,确保命名约定、编码结构、属性度量的一 致性。 „ 时变的:数据存储从历史的角度(例如,过去 5-10 年)提供信息。数据仓库中的关键结构, 隐式或显式地包含时间元素。 „ 非易失的:数据仓库总是物理地分离存放数据;这些数据源于操作环境下的应用数据。由于这 种分离,数据仓库不需要事务处理、恢复和并行控制机制。通常,它只需要两种数据访问:数 据的初始化装入和数据访问。 概言之,数据仓库是一种语义上一致的数据存储,它充当决策支持数据模型的物理实现,并存 放企业决策所需信息。数据仓库也常常被看作一种体系结构,通过将异种数据源中的数据集成在一 起而构造,支持结构化和启发式查询、分析报告和决策制定。 “好”,你现在问,“那么,什么是建立数据仓库(data warehousing)?” 根据上面的讨论,我们把建立数据仓库看作构造和使用数据仓库的过程。数据仓库的构造需要 数据集成、数据清理、和数据统一。利用数据仓库常常需要一些决策支持技术。这使得“知识工人” (例如,经理、分析人员和主管)能够使用数据仓库,快捷、方便地得到数据的总体视图,根据数 据仓库中的信息作出准确的决策。有些作者使用术语“建立数据仓库”表示构造数据仓库的过程, 而用术语“仓库 DBMS”表示管理和使用数据仓库。我们将不区分二者。 “组织机构如何使用数据仓库中的信息?”许多组织机构正在使用这些信息支持商务决策活动, 包括(1)增加顾客关注,包括分析顾客购买模式(如,喜爱买什么、购买时间、预算周期、消费 习惯);(2)根据季度、年、地区的营销情况比较,重新配置产品和管理投资,调整生产策略; (3)分析运作和查找利润源;(4)管理顾客关系、进行环境调整、管理合股人的资产开销。 从异种数据库集成的角度看,数据仓库也是十分有用的。许多组织收集了形形色色数据,并由 多个异种的、自治的、分布的数据源维护大型数据库。集成这些数据,并提供简便、有效的访问是 非常希望的,并且也是一种挑战。数据库工业界和研究界都正朝着实现这一目标竭尽全力。 对于异种数据库的集成,传统的数据库做法是:在多个异种数据库上,建立一个包装程序和一 个集成程序(或仲裁程序)。这方面的例子包括 IBM 的数据连接程序 (Data Joiner) 和 Informix 的数据刀(DataBlade)。当一个查询提交客户站点,首先使用元数据字典对查询进行转换,将它转 换成相应异种站点上的查询。然后,将这些查询映射和发送到局部查询处理器。由不同站点返回的 结果被集成为全局回答。这种查询驱动的方法需要复杂的信息过滤和集成处理,并且与局部数据源 上的处理竞争资源。这种方法是低效的,并且对于频繁的查询,特别是需要聚集操作的查询,开销 很大。 对于异种数据库集成的传统方法,数据仓库提供了一个有趣的替代方案。数据仓库使用更新驱 动的方法,而不是查询驱动的方法。这种方法将来自多个异种源的信息预先集成,并存储在数据仓 库中,供直接查询和分析。与联机事务处理数据库不同,数据仓库不包含最近的信息。然而,数据 仓库为集成的异种数据库系统带来了高性能,因为数据被拷贝、预处理、集成、注释、汇总,并重 新组织到一个语义一致的数据存储中。在数据仓库中进行的查询处理并不影响在局部源上进行的处 理。此外,数据仓库存储并集成历史信息,支持复杂的多维查询。这样,建立数据仓库在工业界已 非常流行。 2.2.1 操作数据库系统与数据仓库的区别 由于大多数人都熟悉商品关系数据库系统,将数据仓库与之比较,就容易理解什么是数据仓库。 联机操作数据库系统的主要任务是执行联机事务和查询处理。这种系统称为联机事务处理 (OLTP)系统。它们涵盖了一个组织的大部分日常操作,如购买、库存、制造、银行、工资、注册、 记帐等。另一方面,数据仓库系统在数据分析和决策方面为用户或“知识工人”提供服务。这种系 统可以用不同的格式组织和提供数据,以便满足不同用户的形形色色需求。这种系统称为联机分析 处理(OLAP)系统。 OLTP 和 OLAP 的主要区别概述如下。 „ 用户和系统的面向性:OLTP 是面向顾客的,用于办事员、客户、和信息技术专业人员的事务和 查询处理。OLAP 是面向市场的,用于知识工人(包括经理、主管、和分析人员)的数据分析。 „ 数据内容:OLTP 系统管理当前数据。通常,这种数据太琐碎,难以方便地用于决策。OLAP 系 统管理大量历史数据,提供汇总和聚集机制,并在不同的粒度级别上存储和管理信息。这些特 点使得数据容易用于见多识广的决策。 „ 数据库设计:通常,OLTP 系统采用实体-联系(ER)模型和面向应用的数据库设计。而 OLAP 系 统通常采用星形或雪花模型(2.2.2 小节讨论)和面向主题的数据库设计。 „ 视图:OLTP 系统主要关注一个企业或部门内部的当前数据,而不涉及历史数据或不同组织的数 据。相比之下,由于组织的变化,OLAP 系统常常跨越数据库模式的多个版本。OLAP 系统也处 理来自不同组织的信息,由多个数据存储集成的信息。由于数据量巨大,OLAP 数据也存放在多 个存储介质上。 „ 访问模式:OLTP 系统的访问主要由短的、原子事务组成。这种系统需要并行控制和恢复机制。 然而,对 OLAP 系统的访问大部分是只读操作(由于大部分数据仓库存放历史数据,而不是当 前数据),尽管许多可能是复杂的查询。 OLTP 和 OLAP 的其它区别包括数据库大小、操作的频繁程度、性能度量等。这些都概括在表 2.1 中。 表 2.1: OLTP 系统和 OLAP 系统的比较 特性 OLTP OLAP 特征 面向 用户 功能 DB 设计 数据 汇总 视图 工作单位 存取 关注 操作 访问记录数量 用户数 DB 规模 优先 度量 操作处理 事务 办事员、DBA、数据库专业人员 日常操作 基于 E-R,面向应用 当前的;确保最新 原始的,高度详细 详细,一般关系 短的、简单事务 读/写 数据进入 主关键字上索引/散列 数十个 数千 100MB 到 GB 高性能,高可用性 事务吞吐量 信息处理 分析 知识工人(如经理、主管、分析员) 长期信息需求,决策支持 星形/雪花,面向主题 历史的;跨时间维护 汇总的,统一的 汇总的,多维的 复杂查询 大多为读 信息输出 大量扫描 数百万 数百 100GB 到 TB 高灵活性,端点用户自治 查询吞吐量,响应时间 2.1.2 但是,为什么需要一个分离的数据仓库 “既然操作数据库存放了大量数据”,你注意到,“为什么不直接在这种数据库上进行联机分 析处理,而是另外花费时间和资源去构造一个分离的数据仓库?”分离的主要原因是提高两个系统 的性能。操作数据库是为已知的任务和负载设计的,如使用主关键字索引和散列,检索特定的记录, 和优化“罐装的”查询。另一方面,数据仓库的查询通常是复杂的,涉及大量数据在汇总级的计算, 可能需要特殊的数据组织、存取方法和基于多维视图的实现方法。在操作数据库上处理 OLAP 查询, 可能会大大降低操作任务的性能。 此外,操作数据库支持多事务的并行处理,需要加锁和日志等并行控制和恢复机制,以确保一 致性和事务的强健性。通常,OLAP 查询只需要对数据记录进行只读访问,以进行汇总和聚集。如果 将并行控制和恢复机制用于这种 OLAP 操作,就会危害并行事务的运行,从而大大降低 OLTP 系统的 吞吐量。 最后,数据仓库与操作数据库分离是由于这两种系统中数据的结构、内容和用法都不相同。决 策支持需要历史数据,而操作数据库一般不维护历史数据。在这种情况下,操作数据库中的数据尽 管很丰富,但对于决策,常常还是远远不够的。决策支持需要将来自异种源的数据统一(如,聚集 和汇总),产生高质量的、纯净的和集成的数据。相比之下,操作数据库只维护详细的原始数据(如 事务),这些数据在进行分析之前需要统一。由于两个系统提供很不相同的功能,需要不同类型的 数据,因此需要维护分离的数据库。然而,许多关系数据库管理系统卖主正开始优化这种系统,使 之支持 OLAP 查询。随着这一趋势的继续,OLTP 和 OLAP 系统之间的分离可望消失。 2.2 多维数据模型 数据仓库和 OLAP 工具基于多维数据模型。该模型将数据看作数据方形式。本节,你将学习数据 方如何对 n-维(n-D)数据建模。你还将学习概念分层,以及如何在基本 OLAP 操作中使用它们,在 多个抽象层上进行交互式挖掘。 2.2.1 由表和电子数据表到数据方 “什么是数据方?”数据方允许以多维对数据建模和观察。它由维和事实定义。 一般地,维是透视或关于一个组织想要记录的实体。例如,AllElectronics 可能创建一个数据 仓库 sales,记录商店的销售,涉及维 time, item, branch, 和 location。这些维使得商店能够记 录商品的月销售,销售商品的分店和地点。每一个维都有一个表与之相关联。该表称为维表,它进 一步描述维。例如,item 的维表可以包含属性 item_name, branch, 和 type。维表可以由用户或专 家设定,或者根据数据分布自动产生和调整。 通常,多维数据模型围绕中心主题(例如,sales)组织。该主题用事实表表示。事实是数值度 量的。把它们看作数量,是因为我们想根据它们分析维之间的关系。例如,数据仓库 sales 的事实 包括 dollars_sold, units_sold 和 amount_budgeted。事实表包括事实的名称或度量,以及每个相 关维表的关键字。当我们稍后考察多维模式时,你很快就会明白这一切如何工作。 尽管我们经常把数据方看作 3-D 几何结构,在数据仓库中,数据方是 n-D 的。为了更好地理解 数据方和多维数据模型,让我们由考察 2-D 数据方开始。事实上,它是 AllElectronics 的销售数 据表或电子数据表。特殊地,我们将观察 AllElectronics 的销售数据中 Vancouver 每季度销售的 商品;这些数据在表 2.2 中。在这个 2-D 表示中,Vancouver 的销售用维 time(按季度组织)和维 item(按所售商品的类型组织)表示。所显示的事实或度量是 dollars_sold (单位:$1000)。 表 2.2: AllElectronics 的销售数据按照维 time, item 的 2-D 视图。 其中销售是取自 location = “Vancouver”的所有分店,所显 示的度量是 dollars_sold location = “Vancouver” item (type) time (quarter) 家庭娱乐 计算机 电话 安全 Q1 Q2 Q3 Q4 605 825 14 400 680 952 31 512 812 1023 30 501 927 1038 38 580 现在,假定我们想以三维角度观察销售数据。例如,我们想根据 time, item, 和 location 观察数据。 location 是城市 Chicago, New York, Toronto 和 Vancouver。3-D 数据如表 2.3 所示。表 2.3 的 3-D 数据 表以 2-D 数据表序列的形式表示。概念上讲,我们也可以以 3-D 数据方的形式表示这些数据,如图 2.1 所示。 表 2.3 Allelectronics 销售数据的 3-D 视图, 根据 time, item, 和 location, 所显示的度 量是 dollars_sold (单位:$1000) location= “Chicago” location=“New York” location=“Toronto” location=“Vancouver” item item item item time 家庭 计算 电话 安 全 娱乐 机 家庭 计算 电话 安全 娱乐 机 家庭 计算 电话 安全 娱乐 机 家庭 计算 电话 安全 娱乐 机 Q1 Q2 Q3 Q4 854 882 89 623 943 890 64 698 1032 924 59 789 1129 992 63 870 1087 968 38 872 1130 1024 41 925 1034 1048 45 1002 1142 1091 54 984 819 746 43 591 894 769 52 682 940 795 58 728 978 864 59 784 605 825 14 400 680 952 31 512 812 1023 30 501 927 1038 38 580 图 2.1:表 2.3 数据的 3-D 数据方表示,维是 time,item 和 location, 所显示的度量为 dollars_sold(单位:$1000) 现在,假定我们想从四维的角度观察销售数据,附加一维,如 supplier。观 察 4-D 事物变得麻烦。 然而,我们可以把 4-D 方看成 3-D 方的序列,如图 2.2 所示。如果我们按这种方法继续下去,我们 可以把任意 n-D 数据方显示成(n-1)-D 数据方的序列。数据方是对多维数据存储的一种比喻,这种数 据的实际物理存储不同于它的逻辑表示。重要的是,数据方是 n 维的,而不限于 3-D。 图 2.2 销售数据的 4-D 数据方表示,维是和 time,item,location 和 supplier,所显示的度量为 dollars_sold(单位:$1000) 上面的表显示不同汇总级的数据。在数据仓库研究界,上面所示的每个数据方称作一个方体。 给定一个维的集合,我们可以构造方体的格,每个在不同的汇总级或 group by3(即,根据维的不同 3 注意,在本书中,查询语言关键字用黑体。 子集)显示数据。方体的格称作数据方。图 2.3 给出形成维 time, item, location 和 supplierr 的数据方 的方体格。 图 2.3 方体格,形成维 time, item, location 和 supplierr 的 4-D 数 据方。每个方体代表一个不同的汇总 存放最低层汇总的方体称为基本方体。例如,图 2.2 中的 4-D 方体是给定维 time, item, location 和 supplier 的基本方体。图 2.1 是 time, item 和 location 的 3-D 方体(非基本的),对所有的供应商汇 总。0-D 方体存放最高层的汇总,称作顶点方体。在我们的例子中,这是总销售 dollars_sold,在所 有的四个维上汇总。顶点方体通常用 all 标记。 2.2.2 星形、雪花和事实星座:多维数据库模式 实体-联系数据模型广泛用于关系数据库设计。在那里,数据库模式由实体的集合和它们之间的 联系组成。这种数据模型适用于联机事务处理。然而,数据仓库需要简明的、面向主题的模式,便 于联机数据分析。 最流行的数据仓库数据模型是多维数据模型。这种模型可以以星形模式、雪花模式、或事实星 座模式形式存在。让我们看看这些模式。 星形模式:最常见的模型范例星形模式;其中数据仓库包括(1)一个大的、包含大批数据、不 含冗余的中心表(事实表);(2)一组小的附属表(维表),每维一个。这种模式图很象星星爆发, 维表围绕中心表显示在射线上。 例 2.1 作为一个例子,Allelectronics 的星形模式如图 2.4 所示。sales 有四个维,分别是 time, item, branch 和 location。该模式包含一个中心事实表 sales,它包含四个维的关键字和两个度量 dollars_sold 和 units_sold。为尽量减小事实表的尺寸,维标识符(如,time_key 和 item_key)是系统产生的标识 符。 注意:在星形模式中,每维只用一个表表示,每个表包含一组属性。例如,location 维表包含属 性集{location_key, street, city, province_or_state, country}。这一限制可能造成某些冗余。例如, “Vancouver”和“Victoria”都是加拿大不列颠哥伦比亚省的城市。location 维表中这些城市实体的属性 province_or_state,country 之间都会有些冗余,即, (..., Vancouver, British Columbia, Canada), (...,Victoria, British Columbia, Canada)。此外,一个维表中的属性可能形成一个层次(全序)或格(偏 序)。 图 2.4: Sales 数据仓库的星形模式 雪花模式:雪花模式是星型模式的变种,其中某些维表是规范化的,因而把数据进一步分解到 附加的表中。结果,模式图形成类似于雪花的形状。 雪花模式和星形模式的主要不同在于,雪花模式的维表可能是规范化形式,以便减少冗余。这 种表易于维护,并节省存储空间,因为当维结构作为列包含在内时,大维表可能非常大。然而,与 巨大的事实表相比,这种空间的节省可以忽略。此外,由于执行查询需要更多的连接操作,雪花结 构可能降低浏览的性能。这样,系统的性能可能相对受到影响。因此,在数据仓库设计中,雪花模 式不如星形模式流行。 例 2.2 作为一个例子,Allelectronics 的 sales 的雪花模式在图 2.5 给出。这里,sales 事实表与图 2.4 的星形模式相同。两个模式的主要不同是维表。星形模式中的 item 的单个维表在雪花模式中被 规范化,导致新的 item 表和 supplier 表。例如,现在 item 维表包含属性 item_key, item_name, brand, type 和 supplier_key,supplier_key 连接到 supplier 维表。而 supplier 维表包含信息 supplier_key 和 supplier_type。类似地,星形模式中 location 的单个维表被规范化成两个表:新的 location 和 city。 新的 location 表中的 location_key 现在连接到 city 维。注意,如果愿意的话,图 2.5 雪花模式中的 province_or_state 和 country 还可以进一步规范化。 图 2.5: sales 数据仓库的雪花模式 事实星座:复杂的应用可能需要多个事实表共享维表。这种模式可以看作星形模式集,因此称 为星系模式,或事实星座。 例 2.3 一个事实星座的例子在图 2.6 中给出。该模式说明了两个事实表,sales 和 shipping。sales 表的定义与星形模式(图 2.4)相同。shipping 表有五个维或关键字:item_key, time_key, shipper_key, from_location 和 to_location;两个度量:dollars_cost 和 units_shipped。事实星座模式允许事实表共 享维表。例如,sales 和 shipping 事实表共享维表 time, item 和 location。 图 2.6:sales 和 shipping 数据仓库的事实星座模式 在数据仓库中,数据仓库和数据集市是有区别的。数据仓库收集了关于整个组织的主题(如顾 客、商品、销售、资产和人员)信息,因此是企业范围的。对于数据仓库,通常使用事实星座模式, 因为它能对多个相关的主题建模。另一方面,数据集市是数据仓库的一个部门子集,它针对选定的 主题,因此是部门范围的。对于数据集市,流行星形或雪花模式,因为它们都适合对单个主题建模, 尽管星形模式更流行、更有效。 2.2.3 定义星形、雪花和事实星座的例子 “我怎样对我的数据定义多维模式?”正象关系数据库查询语言 SQL 可以用于说明关系查询一 样,数据挖掘查询语言可以用于说明数据挖掘任务。特殊地,我们考察一种基于 SQL 的数据挖掘查 询语言 DMQL。DMQL 包括定义数据仓库和数据集市的语言原语。说明其它数据挖掘任务的原语, 如挖掘概念/类描述、关联、分类等,将在第 4 章介绍。 数据仓库和数据集市可以使用两种原语定义:一种是方定义,一种是维定义。方定义语句具有 如下语法形式: define cube [] : 维定义语句具有如下语法形式: define dimension as () 让我们看一些例子,看看如何使用 DMQL 定义例 2.1 到 2.3 的星形、雪花和星座模式。 例 2.4 例 2.1 和图 2.4 定义的星形模式用 DMQL 定义如下: define cube sales_star [time, item, branch, location]: dollars_sold = sum(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city, province_or_state, country) define cube 语句定义一个方,叫做 sales_star,它对应于例 2.1 的中心表 sales 事实表。该命令 说明维表的关键字和两个度量,dollars_sold 和 units_sold。数据方具有四个维,分别为 time, item, branch 和 location。一个 define dimension 语句定义一个维。 例 2.5 例 2.2 和图 2.5 定义的雪花模式用 DMQL 定义如下: define cube sales_snowflake [time, item, branch, location]: dollars_sold = sum(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier(supplier_key, supplier_type)) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city(city_key, city, province_or_state, country)) 该定义类似于 sales_star(例 2.4),不同的是这里 item 和 location 维表是规范化的。例如,在 sales_snowflake 数据方中,sales_star 数据方的 item 维被规范化成两个维表,item 和 supplier。注意: supplier 的维定义在 item 的定义中说明。用这种方式定义 supplier,隐式地在 item 的定义中创建了 一个 supplier_key。类似地,在 sales_snowflake 数据方中,sales_star 数据方的 location 维被规范化成 两个维表,location 和 city。city 的维定义在 location 的定义中说明。用这种方式,city_key 在 location 的定义中隐式地创建。 例 2.6 例 2.3 和图 2.6 定义的星座模式用 DMQL 定义如下: define cube sales [time, item, branch, location]: dollars_sold = sum(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city, province_or_state, country) define cube shipping [time, item, shipper, from_location, to_location]: dollars_sold = sum(cost_in_dollars), units_sipped = count(*) define dimension time as time in cube sales define dimension item as item in cube sales define dimension shipper as (shipper_key, shipper_name, location as location in cube sales, shipper_type) define dimension from_location as location in cube sales define dimension to_location as location in cube sales define cube 语句用于定义数据方 sales 和 shipping,分别对应于例 2.3 模式的两个事实表。注意, 数据方 sales 的 time, item 和 location 维可以与数据方 shpping 共享。例如,time 维,在定义数据方 shipping 语句之下,用“define dimension time as time in cube sales”说明。 2.2.3 度量:它们的分类和计算 “如何计算度量?”为回答这个问题,我们首先看看如何对度量分类。注意,数据方空间的多 维点由维-值对定义。例如,

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 31 人已下载

下载文档

相关文档