数据仓库与数据挖掘序论 ppt课件

数据仓库与数据挖掘 主讲教师：王浩畅 E-mail: wanghch_ School of Computer & Information Technology of NEPU 教科书和参考书 教科书 l数据挖掘：概念与技术，Jiawei Han和Micheline Kamber 著，机械工业出版社(2008) 参考书 lJ. Han and M. Kamber. Data Mining: Concepts and Techniques. 2nd ed. 机械工业出版 社 2006 lP.-N. Tan, M. Steinbach and V. Kumar, Introduction to Data Mining. 人民邮电出版社 2005 lI. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques 2nd ed.机械工 业出版社 2005 EC 课堂要求 必须在打预备铃前到教室，不得迟到、早退、 旷课。迟到一次平时成绩扣5分，旷课一次平 时成绩扣10分 上课时必须关闭手机，严禁在上课时间打电话 、短信聊天。对扰乱课堂纪律的学生将责令退 出课堂,并以旷课论处。 缺课超过1/3不能参加考试 期末成绩=平时成绩占10%+实验成绩占 10%+考试成绩占80% 第1章 引言 数据挖掘的发展动力(1) u需要是发明之母 数据爆炸问题 l自动数据收集工具和成熟的数据库技术使得 大量的数据被收集，存储在数据库、数据仓 库或其他信息库中以待分析。 我们拥有丰富的数据，但却缺乏有用的信息 解决方法：数据仓库技术和数据挖掘技术 l数据仓库(Data Warehouse)和在线分析处理 (OLAP) l数据挖掘：在大量的数据中挖掘感兴趣的知 识（规则，规律，模式，约束） 数据挖掘的发展动力(2) u数据库技术的演化 1960s和以前: l文件系统 1970s: l层次数据库和网状数据库 1980s早期: l关系数据模型, 关系数据库管理系统 (RDBMS)的实现 数据挖掘的发展动力(3) 1980s晚期: l各种高级数据库系统(扩展的关系数据库,面向对象数 据库等等.) l面向应用的数据库系统 (空间数据库，时序数据库， 多媒体数据库等等） 1990s: l数据挖掘, 数据仓库, 多媒体数据库和网络数据库 2000s l流数据管理和挖掘 l基于各种应用的数据挖掘 lXML数据库和整合的信息系统 第1章 引言 什么是数据挖掘？(1) 数据挖掘 (从数据中发现知识) l从大量的数据中挖掘哪些令人感兴趣的、有用的 、隐含的、先前未知的和可能有用的模式或知识 l挖掘的不仅仅是数据（所以“数据挖掘”并非一个 精确的用词） 数据挖掘的替换词 l数据库中的知识挖掘（KDD）知识提炼、数据/ 模式分析 数据考古 数据捕捞、信息收获等等。 并非所有东西都是“数据挖掘” l查询处理. l专家系统或是小型的数学计算/统计程序 什么是数据挖掘？(2) u数据挖掘的应用 数据分析和决策支持 l市场分析和管理 l目标市场, 客户关系管理 (CRM), 市场占有量分析, 交叉销售, 市场分割 l风险分析和管理 l风险预测, 客户保持, 保险业的改良, 质量控制, 竞争 分析 l欺骗检测和异常模式的监测 (孤立点) 其他的应用 l文本挖掘 (新闻组,电子邮件, 文档) 和WEB挖掘 l流数据挖掘 lDNA 和生物数据分析 等等。 什么是数据挖掘？(3) u数据挖掘应用市场分析和管理(1) 数据从那里来? l信用卡交易, 会员卡, 商家的优惠卷, 消费者 投诉电话, 公众生活方式研究 目标市场 l构建一系列的“客户群模型”，这些顾客具 有相同特征: 兴趣爱好, 收入水平, 消费习惯 ,等等 l确定顾客的购买模式 交叉市场分析 l货物销售之间的相互联系和相关性，以及 基于这种联系上的预测 什么是数据挖掘？(4) u数据挖掘应用市场分析和管理(2) 顾客分析 l哪类顾客购买那种商品 (聚类分析或分类预 测) 客户需求分析 l确定适合不同顾客的最佳商品 l预测何种因素能够吸引新顾客 提供概要信息 l多维度的综合报告 l统计概要信息 (数据的集中趋势和变化) 什么是数据挖掘？(5) u数据挖掘应用公司分析和风险管理 财务计划 l现金流转分析和预测 l交叉区域分析和时间序列分析（财务资金比 率，趋势分析等等） 资源计划 l总结和比较资源和花费 竞争 l对竞争者和市场趋势的监控 l将顾客按等级分组和基于等级的定价过程 l将定价策略应用于竞争更激烈的市场中 什么是数据挖掘？(6) u数据挖掘应用欺诈行为检测和异常模 式的发现 (1) 方法: 对欺骗行为进行聚类和建模，并进行孤立 点分析 应用: 卫生保健、零售业、信用卡服务、电信等 l汽车保险: 相撞事件的分析 l洗钱: 发现可疑的货币交易行为 l医疗保险 l职业病人, 医生以及相关数据分析 l不必要的或相关的测试 什么是数据挖掘？(7) u数据挖掘应用欺诈行为检测和异常模 式的发现 (2) l电信: 电话呼叫欺骗行为 l电话呼叫模型: 呼叫目的地，持续时间，日 或周呼叫次数. 分析该模型发现与期待标准 的偏差 l零售产业 l分析师估计有38的零售额下降是由于雇 员的不诚实行为造成的 l反恐怖主义 什么是数据挖掘？(8) u其他应用 体育竞赛 l美国NBA的29个球队中，有25个球队使用了IBM 分析 机构的数据挖掘工具，通过分析每个对手的数据（盖 帽、助攻、犯规等数据）来获得比赛时的对抗优势。 天文学 lJPL实验室和Palomar天文台就曾经在数据挖掘工具的帮 助下发现了22颗新的恒星 网上冲浪 l通过将数据挖掘算法应用于网络访问日志，从与市场 相关的网页中发现消费者的偏爱和行为, 分析网络行销 的有效性，改善网络站点组织。这就是新兴的WEB挖 掘研究 u数据挖掘: 数据库中的知识挖掘(KDD) l数据挖掘知识挖掘 的核心 数据清理 数据集成 数据库 数据仓库 任务相关数据 选择 数据挖掘 模式评估 什么是数据挖掘？(9) u知识挖掘的步骤 了解应用领域 l了解相关的知识和应用的目标 创建目标数据集: 选择数据 数据清理和预处理: (这个可能要占全过程60的工作量) 数据缩减和变换 l找到有用的特征，维数缩减/变量缩减，不变量的表示 。 选择数据挖掘的功能 l数据总结, 分类模型数据挖掘, 回归分析, 关联规则挖掘, 聚类分析等. 选择挖掘算法 数据挖掘: 寻找感兴趣的模式 模式评估和知识表示 l可视化，转换，消除冗余模式等等 运用发现的知识 什么是数据挖掘？(10) u典型数据挖掘系统的体系结构 数据仓库 数据清洗 过滤 数据库 数据库或数据仓库服务器 数据挖掘引擎 模式评估 图形用户界面 知识库 数据集成 什么是数据挖掘？(11) 什么是数据挖掘？(12) u为什么不是传统的数据分析 海量数据 l算法必须有高度的可扩展性，以有效处理TB级数据 高维数据 l可高达数万个不同的维 数据的高度复杂性 l流数据和传感数据 l时间数据、序列数据、时序数据 l图、社会网络、多关系数据 l异构数据库和遗产数据库 l空间数据、时空数据、多媒体、文本和web数据. 新的、复杂的应用 u并非所有的东西都是数据挖掘 基于数据仓库的OLAP系统 lOLAP系统专注于数据的汇总，而数据挖掘系统可以对数 据进行多种复杂的处理。 机器学习系统，数据统计分析系统 l这些系统所处理的数据容量往往很有限。 信息系统 l专注于数据的查询处理。 相比于上述系统，数据挖掘系统关注更广的范围， 是一个多学科的融合 海量数据处理，强调的是算法的可扩展性 li.e. 随着数据量的增加，算法运行时间的增长应该是接近 线性的 什么是数据挖掘？(13) 什么是数据挖掘？(14) 数据挖掘 数据库系统统计学 其他学科 算法 机器学习可视化 u数据挖掘:多个学科的融合 第1章 引言 在何种数据上进行数据挖掘 关系数据库 数据仓库 事务数据库 高级数据库系统和信息库 l空间数据库 l时间数据库和时间序列数据库 l流数据 l多媒体数据库 l面向对象数据库和对象-关系数据库 l异种数据库和历史(legacy)数据库 l文本数据库和万维网(WWW) 数据仓库 数据仓库 l从多个数据源收集的信息存储库 l存放在一个一致的模式之下 l通常驻留在单个站点 通常使用多维数据模型 l通过数据立方体提供数据的多维视图 l预计算和快速访问汇总数据 第三章详细讨论数据仓库技术 高级数据和信息系统与高级应用(1) u空间数据库 空间数据库是指在关系型数据库（DBMS）内部 对地理信息进行物理存储。空间数据库中存储的 海量数据包括对象的空间拓扑特征、非空间属性 特征以及对象在时间上的状态变化。 常见的空间数据库数据类型 l地理信息系统(GIS) l遥感图像数据 l医学图像数据 数据挖掘技术的应用：通过空间分类和空间趋势 分析，引入机器学习算法，对有用模式进行智能 检索 高级数据和信息系统与高级应用(2) u时间数据库和时序数据库 时间数据库和时序数据库都存放与时间有 关的数据。时间数据库通常存放包含时间 相关属性的数据。时序数据库存放随时间 变化的值序列。 对时间数据库和时序数据库的数据挖掘,可 以通过研究事物发生发展的过程，有助于 揭示事物发展的本质规律，可以发现数据 对象的演变特征或对象变化趋势。 高级数据和信息系统与高级应用(3) u流数据 与传统的数据库技术中的静态数据不同，流数据是连 续的、有序的、变化的、快速的、大量的数据输入的 数据。 通常不存放在任何数据存储库中 主要应用场合 l各类科学和工程数据；e.g.卫星监测数据 l视频监测 l气象或环境监测 l流媒体等等 lWEB点击流 与传统数据库技术相比，流数据在存储、查询、访问 、实时性的要求等方面都有很大区别。 高级数据和信息系统与高级应用(4) u多媒体数据库 多媒体数据库实现用计算机管理庞大复杂的 多媒体数据，主要包括包括图形(graphics)、 图象(image)、声音(audio)、视频(video)等等， 现代数据库技术一般将这些多媒体数据以二 进制大对象的形式进行存储。 对于多媒体数据库的数据挖掘，需要将存储 和检索技术相结合。目前的主要方法包括构 造多媒体数据立方体、多媒体数据库的多特 征提取和基于相似性的模式匹配。 高级数据和信息系统与高级应用(5) u面向对象数据库和对象-关系数据库 面向对象数据库是面向对象技术和数据库技术结合 的产物，该技术对数据以对象的形式进行存储，并 在这个基础上实现了传统数据库的功能，包括持久 性、并发控制、可恢复性、一致性和查询数据库的 能力等。 对象关系数据库基于对象关系模型构造，该模 型通过处理复杂对象的丰富数据类型和对象定位等 功能，扩充关系模型。 面向对象数据库和对象关系数据库中的数据挖掘 会涉及一些新的技术，比如处理复杂对象结构、复 杂数据类型、类和子类层次结构、构造继承以及方 法和过程等等。 高级数据和信息系统与高级应用(6) u异构数据库和历史(legacy)数据库 历史数据库是一系列的异构数据库系统的集合， 包括不同种类的数据库系统，像关系数据库、网 络数据库、文件系统等等。 有效利用历史数据库的关键在于实现不同数据库 之间的数据信息资源、硬件设备资源和人力资源 的合并和共享。 对于异构数据库系统，实现数据共享应当达到两 点：一是实现数据库转换；二是实现数据的透明 访问。 WEB SERVICE技术的出现有利于历史数据库数据的重 新利用。 高级数据和信息系统与高级应用(7) u文本数据库和万维网(WWW) 文本数据库存储的是对对象的文字性描述。 文本数据库的分类 l无结构类型（大部分的文本资料和网页） l半结构类型（XML数据） l结构类型（图书馆数据） 万维网(WWW)可以被看成最大的文本数据库 特征：信息最丰富；信息高度非结构化；缺乏预订义 的模式、类型和格式 l一些WEB挖掘的热点 l权威WEB页面分析（搜索引擎） l自动WEB页面聚类和分类 lWEB社区分析、WEB访问模式检索 上节课内容回顾 1.1 数据挖掘的发展动力 l数据爆炸 l数据库技术的演化 1.2 什么是数据挖掘 l定义:从大量的数据中挖掘哪些令人感兴趣的、有 用的、隐含的、先前未知的和可能有用的模式或 知识 l应用 l数据挖掘系统的体系结构 l和传统数据分析的区别 1.3 在何种数据上进行数据挖掘 第1章 引言 数据挖掘的主要功能 -可以挖掘什么类型的模式？ 一般功能 l描述性的数据挖掘 l预测性的数据挖掘 通常，用户并不知道在数据中能挖掘出什么 东西，对此我们会在数据挖掘中应用一些常 用的数据挖掘功能，挖掘出一些常用的模式 ，包括： l概念/类描述: 特性化和区分 l关联分析 l分类和预测 l聚类分析 l孤立点分析 l趋势和演变分析 概念/类描述: 特性化和区分 概念描述：为数据的特征化和比较产生描述（当所 描述的概念所指的是一类对象时，也称为类描述） l特征化：提供给定数据集的简洁汇总。 l例：对AllElectronic公司的“大客户”（年消费额 $1000以上）的特征化描述：4050岁，有固定职 业，信誉良好，等等 l区分：提供两个或多个数据集的比较描述。 l例： 挖掘频繁模式、关联和相关 频繁模式是在数据中频繁出现的模式 关联规则挖掘： l从事务数据库，关系数据库和其他信息存储中的大量 数据的项集之间发现有趣的、频繁出现的模式、关联 和相关性。 l广泛的用于购物篮或事务数据分析。 例： 分类和预测 根据训练数据集和类标号属性，构建模型来分类现有数据 ，并用来分类新数据（分类），用来预测类型标志为所属 的对象类（预测）。 l比如：按气候将国家分类，按汽油消耗定额将汽车分类 l导出模型的表示: 判定树、分类规则、神经网络 l可以用来预报某些未知的或丢失的数字值 例： lIF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes” lIF age = “40” AND credit_rating = “fair” THEN buys_computer = “no” 第一步建立模型 训练数 据集 分类算法 IF rank = professor OR years 6 THEN tenured = yes 分类规则 第二步用模型进行分类 分类规则 测试集 未知数据 (Jeff, Professor, 4) Tenured? 聚类分析 聚类分析 l将物理或抽象对象的集合分组成为由类似 的对象组成的多个类的过程。 l最大化类内的相似性和最小化类间的相似 性 l不像分类和预测分析标号类的数据对象， 聚类分析数据对象不考虑已知的标号类 例：对WEB日志的数据进行聚类，以发现 相同的用户访问模式 孤立点分析 孤立点分析 l孤立点:一些与数据的一般行为或模型不一致 的孤立数据 l通常孤立点被作为“噪音”或异常被丢弃，但 在欺骗检测中却可以通过对罕见事件进行孤 立点分析而得到结论。 应用 l信用卡欺诈检测 l移动电话欺诈检测 l客户划分 l医疗分析（异常） 趋势和演变分析 描述行为随时间变化的对象的发展规律或 趋势，并对其建模 l将特征化、区分、关联、分类、聚类等技 术应用于时间相关数据 一些演变分析的热点 l时间序列数据分析 l序列或周期模式匹配 l基于相似性的数据分析 u其他定向模式或统计分析 * * 4848 第1章 引言 所有模式都是有趣的吗？(1) 数据挖掘可能产生数以千计的模式或规则，但并不 是所有的模式或规则都是令人感兴趣的。 模式兴趣度的度量 l一个模式是有趣的，如果(1) 它易于被人理解 ；（2 ）在某种程度上，对于新的或测试数据是有效的； （3）具有潜在效用；（4）新颖的；（5）符合用户 确信的某种假设 模式兴趣度的客观和主观度量 l客观度量: 基于所发现模式的结构和关于它们的统计 ， 比如： 支持度、置信度等等 l主观度量: 基于用户对数据的判断。比如：出乎意料 的、新颖的、可行动的等等 所有模式都是有趣的吗？(2) u能够产生所有有趣模式并且仅产生有趣模式吗 ？ 找出所有有趣的模式: 数据挖掘算法的完全性问题 l数据挖掘系统能够产生所有有趣的模式吗? l试探搜索 vs.穷举搜索 l关联 vs. 分类 vs. 聚类 只搜索有趣的模式: 数据挖掘算法的最优化问题 l数据挖掘系统可以仅仅发现有趣的模式吗？ l方法 l首先生成所有模式然后过滤那些无趣的. l仅仅生成有趣的模式挖掘查询优化 第1章 引言 数据挖掘系统的分类 (1) 数据挖掘 数据库系统统计学 其他学科 算法 机器学习可视化 u数据挖掘:多个学科的融合 数据挖掘系统的分类 (2) 数据挖掘的多学科融合的特性，决定了数 据挖掘的研究将产生种类繁多的数据挖掘 系统。 根据所挖掘的数据库分类 l关系数据库，事务数据库，流式数据，面 向对象数据库，对象关系数据库，数据仓 库，空间数据库，时序数据库，文本数据 库，多媒体数据库，异构数据库，历史数 据库，WWW 数据挖掘系统的分类 (3) l根据挖掘的知识类型 l特征分析, 区分, 关联分析, 分类聚类, 孤 立点分析/演变分析, 偏差分析等等. l多种方法的集成和多层级挖掘 l根据挖掘所用的技术 l面向数据库的挖掘、数据仓库 、OLAP 、机器学习、统计学、可视化等等. l根据挖掘所用的应用 l金融,电信,银行, 欺诈分析, DNA分析,股 票市场, Web挖掘等等. 第1章 引言 数据挖掘技术和数据仓库技术的集成(1) 数据挖掘系统、数据库管理系统和数据仓 库系统的耦合 l不耦合, 松散耦合,半紧密耦合, 紧密耦合 联机分析和挖掘数据（OLAM） l挖掘和OLAP（联机分析处理）技术的集成 多个抽象层的交互知识挖掘 l在不同层次上通过交互地在数据空间和知 识空间下钻、上卷和转轴来挖掘知识和模 式的必要性. 多种挖掘功能的集成 l 特性化分类, 先聚类分析后关联分析 数据挖掘技术和数据仓库技术的集成(2) 数据仓库 元数据 多维数 据库 MDDB OLAM 引擎 OLAP 引擎 User GUI API Data Cube API Database API 数据清理 数据集成 第3层 OLAP/OLAM 第2层 MDDB 第1层 数据储存 第4层 用户接口 过滤&集成过滤 数据库 挖掘查询挖掘结果 uOLAM 体系结构 第1章 引言 数据挖掘的主要问题 (1) 数据挖掘是多个学科融合，但本课程所关注 的是：海量数据的挖掘的效率和可扩展性 本课程中所要涵盖的主要数据挖掘问题包括 ： l挖掘方法问题和用户交互问题 l在数据库中挖掘不同类型的知识 l在不同抽象层上的交互式知识挖掘 l背景知识的合并 l数据挖掘查询语言和特定的数据挖掘 l数据挖掘结果的表示和可视化 l处理噪声和不完全数据 l模式评估: 兴趣度问题 数据挖掘的主要问题 (2) l性能问题：数据挖掘算法的效率、可扩展 性(scalability)和并行处理 l适用于海量数据 l并行，分布式和增量挖掘算法 l关于数据库类型多样性的问题 l关系型和复杂数据类型的处理 l为特定的数据类型构建特定的数据挖掘系统 l从异构数据库中挖掘和全球信息系统挖掘信息 lWEB数据挖掘 小结 1.1 数据挖掘的发展动力 1.2 什么是数据挖掘 1.3 对何种数据进行数据挖掘 1.4 数据挖掘功能 1.5 所有模式都是有趣的吗 1.6 数据挖掘系统的分类 1.7 数据挖掘技术和数据仓库技术的集成 1.8 数据挖掘的主要问题 * * 6262 练习题 请设计一个数据挖掘系统，分析学校课程数据 库。该数据库包括如下信息：每个学生的姓名 、地址和状态（例如，本科生或研究生）、所 修课程，以及他们的GPA（平均积分点）。描 述你要选取的结构。该结构的每个成分的作用 是什么？ 与挖掘少量数据（如几百个元组的数据集合） 相比，挖掘海量数据（如数兆元组）的主要挑 战是什么？ * * 6363 * * 6464 Conferences and Journals on Data Mining KDD Conferences lACM SIGKDD Int. Conf. on Knowledge Discovery in Databases and Data Mining (KDD) lSIAM Data Mining Conf. (SDM) l(IEEE) Int. Conf. on Data Mining (ICDM) lConf. on Principles and practices of Knowledge Discovery and Data Mining (PKDD) lPacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD) nOther related conferences nACM SIGMOD nVLDB n(IEEE) ICDE nWWW, SIGIR nICML, CVPR, NIPS nJournals nData Mining and Knowledge Discovery (DAMI or DMKD) nIEEE Trans. On Knowledge and Data Eng. (TKDE) nKDD Explorations nACM Trans. on KDD * * 6565 Where to Find References? DBLP, CiteSeer, Google Data mining and KDD (SIGKDD: CDROM) lConferences: ACM-SIGKDD, IEEE-ICDM, SIAM-DM, PKDD, PAKDD, etc. lJournal: Data Mining and Knowledge Discovery, KDD Explorations, ACM TKDD Database systems (SIGMOD: ACM SIGMOD AnthologyCD ROM) lConferences: ACM-SIGMOD, ACM-PODS, VLDB, IEEE-ICDE, EDBT, ICDT, DASFAA lJournals: IEEE-TKDE, ACM-TODS/TOIS, JIIS, J. ACM, VLDB J., Info. Sys., etc. AI & Machine Learning lConferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), CVPR, NIPS, etc. lJournals: Machine Learning, Artificial Intelligence, Knowledge and Information Systems, IEEE-PAMI, etc. Web and IR lConferences: SIGIR, WWW, CIKM, etc. lJournals: WWW: Internet and Web Information Systems, Statistics lConferences: Joint Stat. Meeting, etc. lJournals: Annals of statistics, etc. Visualization lConference proceedings: CHI, ACM-SIGGraph, etc. lJournals: IEEE Trans. visualization and computer graphics, etc. * * 6666 Recommended Reference Books S. Chakrabarti. Mining the Web: Statistical Analysis of Hypertex and Semi-Structured Data. Morgan Kaufmann, 2002 R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2ed., Wiley-Interscience, 2000 T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley & Sons, 2003 U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uth