数据挖掘精品讲义

数 据 挖 掘 主讲教师：王灿 E-mail: 教科书和参考书 教科书 数据挖掘：概念与技术， Jiawei Han和 Micheline Kamber 著，机械工业出版社 (2001) 参考书 数据挖掘原理 , David Hand, Heikki Mannila和 Padhraic Smyth著，机械工业出版社 (2003) 中文版 英文影 印版 数据挖掘的发展动力 -需要是发明之母 数据爆炸问题 自动数据收集工具和成熟的数据库技术使得大量的数据被收集，存储在数据库、数据仓库或其他信息库中以待分析。 我们拥有丰富的数据，但却缺乏有用的信息 解决方法：数据仓库技术和数据挖掘技术 数据仓库 (Data Warehouse)和在线分析处理 (OLAP) 数据挖掘：在大量的数据中挖掘感兴趣的知识（规则，规律，模式，约束） 数据库技术的演化 (1) 1960s和以前 : 文件系统 1970s: 层次数据库和网状数据库 1980s早期 : 关系数据模型 , 关系数据库管理系统 (RDBMS)的实现 数据库技术的演化 (2) 1980s晚期 : 各种高级数据库系统 (扩展的关系数据库 ,面向对象数据库等等 .) 面向应用的数据库系统 (空间数据库，时序数据库，多媒体数据库等等） 1990s: 数据挖掘 , 数据仓库 , 多媒体数据库和网络数据库 2000s 流数据管理和挖掘 基于各种应用的数据挖掘 XML数据库和整合的信息系统 什么是数据挖掘？ 数据挖掘 (从数据中发现知识 ) 从 大量的数据 中挖掘哪些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识 挖掘的不仅仅是数据（所以“数据挖掘”并非一个精确的用词） 数据挖掘的替换词 数据库中的知识挖掘（ KDD） 知识提炼、 数据 /模式分析 数据考古 数据捕捞、信息收获等等。 数据挖掘 : 数据库中的知识挖掘 (KDD) 数据挖掘 知识挖掘的核心 数据清理 数据集成 数据库 数据仓库 任务相关数据 选择 数据挖掘 模式评估 KDD的步骤 从 KDD对数据挖掘的定义中可以看到当前研究领域对数据挖掘的狭义和广义认识 1. 数据清理 : (这个可能要占全过程 60的工作量 ) 2. 数据集成 3. 数据选择 4. 数据变换 5. 数据挖掘（选择适当的算法来找到感兴趣的模式） 6. 模式评估 7. 知识表示 典型数据挖掘系统的体系结构 数据仓库 数据清洗 过滤 数据库 数据库或数据仓库服务器 数据挖掘引擎 模式评估 图形用户界面 知识库 数据集成 并非所有的东西都是数据挖掘 基于数据仓库的 OLAP系统 OLAP系统专注于数据的汇总，而数据挖掘系统可以对数据进行多种复杂的处理。 机器学习系统，数据统计分析系统 这些系统所处理的数据容量往往很有限。 信息系统 专注于数据的查询处理。 相比于上述系统，数据挖掘系统关注更广的范围，是一个多学科的融合 在何种数据上进行数据挖掘 关系数据库 数据仓库 事务数据库 高级数据库系统和信息库 空间数据库 时间数据库和时间序列数据库 流数据 多媒体数据库 面向对象数据库和对象 -关系数据库 异种数据库和历史 (legacy)数据库 文本数据库和万维网 (WWW) 空间数据库 空间数据库是指在关系型数据库（ DBMS）内部对地理信息进行物理存储。空间数据库中存储的海量数据包括对象的空间拓扑特征、非空间属性特征以及对象在时间上的状态变化。 常见的空间数据库数据类型 地理信息系统 (GIS) 遥感图像数据 医学图像数据 数据挖掘技术的应用：通过空间分类和空间趋势分析，引入机器学习算法，对有用模式进行智能检索 时间数据库和时序数据库 时间数据库和时序数据库都存放与时间有关的数据。时间数据库通常存放包含时间相关属性的数据。时序数据库存放随时间变化的值序列。 对时间数据库和时序数据库的数据挖掘 ,可以通过研究事物发生发展的过程，有助于揭示事物发展的本质规律，可以发现数据对象的演变特征或对象变化趋势。 流数据 与传统的数据库技术中的静态数据不同，流数据是连续的、有序的、变化的、快速的、大量的数据输入的数据。 主要应用场合 网络监控 网页点击流 股票市场 流媒体 等等 与传统数据库技术相比，流数据在存储、查询、访问、实时性的要求等方面都有很大区别。 多媒体数据库 多媒体数据库实现用计算机管理庞大复杂的多媒体数据，主要包括包括图形 (graphics)、图象 (image)、声音 (audio)、视频 (video)等等，现代数据库技术一般将这些多媒体数据以二进制大对象的形式进行存储。 对于多媒体数据库的数据挖掘，需要将存储和检索技术相结合。目前的主要方法包括构造多媒体数据立方体、多媒体数据库的多特征提取和基于相似性的模式匹配。 面向对象数据库和对象 -关系数据库 面向对象数据库是面向对象技术和数据库技术结合的产物，该技术对数据以对象的形式进行存储，并在这个基础上实现了传统数据库的功能，包括持久性、并发控制、可恢复性、一致性和查询数据库的能力等。 对象关系数据库基于对象关系模型构造，该模型通过处理复杂对象的丰富数据类型和对象定位等功能，扩充关系模型。 面向对象数据库和对象关系数据库中的数据挖掘会涉及一些新的技术，比如处理复杂对象结构、复杂数据类型、类和子类层次结构、构造继承以及方法和过程等等。 异构数据库和历史 (legacy)数据库 历史数据库是一系列的异构数据库系统的集合，包括不同种类的数据库系统，像关系数据库、网络数据库、文件系统等等。 有效利用历史数据库的关键在于实现不同数据库之间的数据信息资源、硬件设备资源和人力资源的合并和共享。 对于异构数据库系统，实现数据共享应当达到两点：一是实现数据库转换；二是实现数据的透明访问。 WEB SERVICE技术的出现有利于历史数据库数据的重新利用。 文本数据库和万维网 (WWW) 文本数据库存储的是对对象的文字性描述。 文本数据库的分类 无结构类型（大部分的文本资料和网页） 半结构类型（ XML数据） 结构类型（图书馆数据） 万维网 (WWW)可以被看成最大的文本数据库 数据挖掘内容 内容检索 WEB访问模式检索 数据挖掘应用 市场分析和管理 (1) 数据从那里来 ? 信用卡交易 , 会员卡 , 商家的优惠卷 , 消费者投诉电话 , 公众生活方式研究 目标市场 构建一系列的“客户群模型”，这些顾客具有相同特征 : 兴趣爱好 , 收入水平 , 消费习惯 ,等等 确定顾客的购买模式 交叉市场分析 货物销售之间的相互联系和相关性，以及基于这种联系上的预测 数据挖掘应用 市场分析和管理 (2) 顾客分析 哪类顾客购买那种商品 (聚类分析或分类预测 ) 客户需求分析 确定适合不同顾客的最佳商品 预测何种因素能够吸引新顾客 提供概要信息 多维度的综合报告 统计概要信息 (数据的集中趋势和变化 ) 数据挖掘应用 公司分析和风险管理 财务计划 现金流转分析和预测 交叉区域分析和时间序列分析（财务资金比率，趋势分析等等） 资源计划 总结和比较资源和花费 竞争 对竞争者和市场趋势的监控 将顾客按等级分组和基于等级的定价过程 将定价策略应用于竞争更激烈的市场中 数据挖掘应用 欺诈行为检测和异常模式的发现 方法 : 对欺骗行为进行聚类和建模，并进行孤立点分析 应用 : 卫生保健、零售业、信用卡服务、电信等 汽车保险 : 相撞事件的分析 洗钱 : 发现可疑的货币交易行为 医疗保险 职业病人 , 医生以及相关数据分析 不必要的或相关的测试 电信 : 电话呼叫欺骗行为 电话呼叫模型 : 呼叫目的地，持续时间，日或周呼叫次数 . 分析该模型发现与期待标准的偏差 零售产业 分析师估计有 38的零售额下降是由于雇员的不诚实行为造成的 反恐怖主义 数据挖掘的主要功能 可以挖掘哪些模式？ 一般功能 描述性的数据挖掘 预测性的数据挖掘 通常，用户并不知道在数据中能挖掘出什么东西，对此我们会在数据挖掘中应用一些常用的数据挖掘功能，挖掘出一些常用的模式，包括： 概念 /类描述 : 特性化和区分 关联分析 分类和预测 聚类分析 孤立点分析 趋势和演变分析 概念 /类描述 : 特性化和区分 概念描述：为数据的特征化和比较产生描述（当所描述的概念所指的是一类对象时，也称为类描述） 特征化：提供给定数据集的简洁汇总。 例：对 AllElectronic公司的“大客户”（年消费额 $1000以上）的特征化描述： 40 50岁，有固定职业，信誉良好，等等 区分：提供两个或多个数据集的比较描述。 例： S t a t u s B i r t h _ c o u n t r y A g e _ r a n g e G p a C o u n tG r a d u a t e C a n a d a 2 5 - 3 0 G o o d 90U n d e r g r a d u a t e C a n a d a 2 5 - 3 0 G o o d 2 1 0关联分析 关联规则挖掘： 从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。 广泛的用于购物篮或事务数据分析。 例： %70%,20 s u p) ,( )48.42 ,( )39.30 ,( c on f i d e n c ep o r tc omp u t e rXb u y skkXi n c omeXage分类和预测 根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据（分类），用来预测类型标志未知的对象类（预测）。 比如：按气候将国家分类，按汽油消耗定额将汽车分类 导出模型的表示 : 判定树、分类规则、神经网络 可以用来预报某些未知的或丢失的数字值 例： IF age = 40 AND credit_rating = excellent THEN buys_computer = yes IF age = 40 AND credit_rating = fair THEN buys_computer = no 聚类分析 聚类分析： 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。 最大化类内的相似性和最小化类间的相似性 例：对 WEB日志的数据进行聚类，以发现相同的用户访问模式 孤立点分析 孤立点分析 孤立点 :一些与数据的一般行为或模型不一致的孤立数据 通常孤立点被作为“噪音”或异常被丢弃，但在欺骗检测中却可以通过对罕见事件进行孤立点分析而得到结论。 应用 信用卡欺诈检测 移动电话欺诈检测 客户划分 医疗分析（异常） 趋势和演变分析 描述行为随时间变化的对象的发展规律或趋势（时序数据库） 趋势和偏差 : 回归分析 序列模式匹配：周期性分析 基于类似性的分析 所有模式都是有趣的吗？ 数据挖掘可能产生数以千计的模式或规则，但并不是所有的模式或规则都是令人感兴趣的。 模式兴趣度的度量 一个模式是有趣的，如果 (1) 它易于被人理解 ；（ 2）在某种程度上，对于新的或测试数据是有效的；（ 3）具有潜在效用；（ 4）新颖的；（ 5）符合用户确信的某种假设 模式兴趣度的客观和主观度量 客观度量 : 基于所发现模式的结构和关于它们的统计， 比如： 支持度、置信度等等 主观度量 : 基于用户对数据的判断。比如：出乎意料的、新颖的、可行动的等等 5-6 王 灿 数据挖掘 0703004 能够产生所有有趣模式并且仅产生有趣模式吗？ 找出所有有趣的模式 : 数据挖掘算法的完全性问题 数据挖掘系统能够产生所有有趣的模式吗 ? 试探搜索 vs.穷举搜索 关联 vs. 分类 vs. 聚类 只搜索有趣的模式 : 数据挖掘算法的最优化问题 数据挖掘系统可以仅仅发现有趣的模式吗？ 方法 首先生成所有模式然后过滤那些无趣的 . 仅仅生成有趣的模式 挖掘查询优化 数据挖掘 :多个学科的融合 数据挖掘 数据库系统 统计学 其他学科 算法 机器学习 可视化 数据挖掘系统的分类 (1) 数据挖掘的多学科融合的特性，决定了数据挖掘的研究将产生种类繁多的数据挖掘系统。 根据所挖掘的数据库分类 关系数据库，事务数据库，流式数据，面向对象数据库，对象关系数据库，数据仓库，空间数据库，时序数据库，文本数据库，多媒体数据库，异构数据库，历史数据库， WWW 数据挖掘系统的分类 (2) 根据挖掘的知识类型 特征分析 , 区分 , 关联分析 , 分类聚类 , 孤立点分析 /演变分析 , 偏差分析等等 . 多种方法的集成和多层机挖掘 根据挖掘所用的技术 面向数据库的挖掘、数据仓库 、 OLAP、机器学习、统计学、可视化等等 . 根据挖掘所用的应用 金融 ,电信 ,银行 , 欺诈分析 , DNA分析 ,股票市场 , Web挖掘等等 . 数据挖掘的主要问题 (1) 数据挖掘是多个学科融合，但本课程所关注的是： 海量数据的挖掘的效率和可扩展性 本课程中所要涵盖的主要数据挖掘问题包括： 挖掘方法问题和用户交互问题 在数据库中挖掘不同类型的知识 在不同抽象层上的交互式知识挖掘 背景知识的合并 数据挖掘查询语言和特定的数据挖掘 数据挖掘结果的表示和可视化 处理噪声何不完全数据 模式评估 : 兴趣度问题 数据挖掘的主要问题 (2) 性能问题 数据挖掘算法的效率和可扩展性 (scalability) （什么是可扩展性？） 并行，分布式和增量挖掘算法 （数据的分块挖掘） 其他和多样化的数据库类型相关的问题 关系型和复杂数据类型的处理 为特定的数据类型构建特定的数据挖掘系统 从异构数据库中挖掘 WEB数据挖掘 数据仓库和数据挖掘的OLAP技术 数据仓库数据挖掘的有效平台 数据仓库中的数据清理和数据集成，是数据挖掘的重要数据预处理步骤 数据仓库提供 OLAP工具，可用于不同粒度的数据分析 很多数据挖掘功能都可以和 OLAP操作集成，以提供不同概念层上的知识发现 分类 预测 关联 聚集 什么是数据仓库 ? 数据仓库的定义很多，但却很难有一种严格的定义 它是一个提供决策支持功能的数据库，它与公司的操作数据库分开维护。 为统一的历史数据分析提供坚实的平台，对信息处理提供支持 数据仓库区别于其他数据存储系统 “数据仓库是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策过程 .W. H. Inmon 数据仓库关键特征一 面向主题 面向主题，是数据仓库显著区别于关系数据库系统的一个特征 围绕一些主题，如顾客、供应商、产品等 关注决策者的数据建模与分析，而不是集中于组织机构的日常操作和事务处理。 排除对于决策无用的数据，提供特定主题的简明视图。 数据仓库关键特征二 数据集成 一个数据仓库是通过集成多个异种数据源来构造的。 关系数据库，一般文件， 联机事务处理记录 使用数据清理和数据集成技术。 确保命名约定、编码结构、属性度量等的一致性。 当数据被移到数据仓库时，它们要经过转化。 数据仓库关键特征三 随时间而变化 数据仓库是从历史的角度提供信息 数据仓库的时间范围比操作数据库系统要长的多。 操作数据库系统 : 主要保存当前数据。 数据仓库 :从历史的角度提供信息（比如过去 5-10 年） 数据仓库中的每一个关键结构都隐式或显式地包含时间元素，而操作数据库中的关键结构可能就不包括时间元素。 数据仓库关键特征四 数据不易丢失 尽管数据仓库中的数据来自于操作数据库，但他们却是在物理上分离保存的。 操作数据库的更新操作不会出现在数据仓库环境下。 不需要事务处理，恢复，和并发控制等机制 只需要两种数据访问 : 数据的初始转载和数据访问（读操作） 数据仓库的构建与使用 数据仓库的构建包括一系列的数据预处理过程 数据清理 数据集成 数据变换 数据仓库的使用热点是商业决策行为，例如： 增加客户聚焦 产品重定位 寻找获利点 客户关系管理 数据仓库与异种数据库集成 异种数据库的集成方法 传统的异种数据库集成 :（ 查询驱动 ） 在多个异种数据库上建立包装程序（ wrappers）和中介程序（ mediators ） 查询驱动方法 当从客户端传过来一个查询时，首先使用元数据字典将查询转换成相应异种数据库上的查询；然后，将这些查询映射和发送到局部查询处理器 数据仓库 : （ 更新驱动 ） 将来自多个异种源的信息预先集成，并存储在数据仓库中，供直接查询和分析 查询驱动方法和更新驱动方法的比较 查询驱动的方法 需要负责的信息过滤和集成处理 与局部数据源上的处理竞争资源 对于频繁的查询，尤其是涉及聚集（汇总）操作的查询，开销很大（决策支持中常见的查询形式） 更新驱动的方法（带来高性能） 数据经预处理后单独存储，对聚集操作提供良好支持 不影响局部数据源上的处理 集成历史信息，支持负责的多维查询 数据仓库与操作数据库系统 操作数据库系统的主要任务是联机事务处理OLTP 日常操作 : 购买，库存，银行，制造，工资，注册，记帐等 数据仓库的主要任务是联机分析处理 OLAP 数据分析和决策支持，支持以不同的形式显示数据以满足不同的用户需要 OLAP VS. OLTP (1) 用户和系统的面向性 面向顾客（事务） VS. 面向市场（分析） 数据内容 当前的、详细的数据 VS. 历史的、汇总的数据 数据库设计 实体联系模型 (ER)和面向应用的数据库设计 VS. 星型 /雪花模型和面向主题的数据库设计 OLAP VS. OLTP (2) 数据视图 当前的、企业内部的数据 VS. 经过演化的、集成的数据 访问模式 事务操作 VS. 只读查询（但很多是复杂的查询） 任务单位 简短的事务 VS. 复杂的查询 访问数据量 数十个 VS. 数百万个 OLAP VS. OLTP (3) 用户数 数千个 VS. 数百个 数据库规模 100M-数 GB VS. 100GB-数 TB 设计优先性 高性能、高可用性 VS. 高灵活性、端点用户自治 度量 事务吞吐量 VS. 查询吞吐量、响应时间 为什么需要一个分离的数据仓库 ? 提高两个系统的性能 DBMS是为 OLTP而设计的：存储方式 ,索引 , 并发控制 , 恢复 数据仓库是为 OLAP而设计：复杂的 OLAP查询 , 多维视图，汇总 不同的功能和不同的数据 : 历史数据 : 决策支持需要历史数据，而这些数据在操作数据库中一般不会去维护 数据汇总：决策支持需要将来自异种源的数据统一（如聚集和汇总） 数据质量 : 不同的源使用不一致的数据表示、编码和格式，对这些数据进行有效的分析需要将他们转化后进行集成 多维数据模型 (1) 数据仓库和 OLAP工具基于多维数据模型 在多维数据模型中，数据以数据立方体 (data cube)的形式存在 数据立方体 允许以多维数据建模和观察。它由 维 和 事实 定义 维 是关于一个组织想要记录的视角或观点。每个维都有一个表与之相关联，称为 维表 。 多维数据模型围绕中心主题组织，该主题用 事实表 表示 事实表 包括事实的名称或度量以及每个相关维表的关键字 事实 指的是一些数字度量 多维数据模型 (2) 示例 time_key day day_of_the_week month quarter year time 维表 location_key street city state_or_province country location 事实表 Sales 事实表 time_key item_key branch_key location_key units_sold dollars_sold avg_sales 度量 item_key item_name brand type supplier_type item 维表 branch_key branch_name branch_type branch 维表 多维数据模型 (3) 在数据仓库中，数据立方体是 n-D的 (n维） （关系表和电子表格是几维的？） 示例 AllElectronics的销售数据按维 time, item的 2-D视图 (P30, 表2-2) AllElectronics的销售数据按维 time, item和 location的 3-D视图 (P30, 表 2-3) AllElectronics的销售数据按维 time, item和 location的 3-D视图的 3-D数据立方体表示 (P31, 图 2-1) 销售数据的 4-D立方体表示 (P31, 图 2-2) 多维数据模型为不同角度上的数据建模和观察提供了一个良好的基础 多维数据模型 (4) 在数据仓库的研究文献中，一个 n维的数据的立方体叫做 基本方体 。给定一个维的集合，我们可以构造一个 方体的格 ，每个都在不同的汇总级或不同的数据子集显示数据，方体的格称为数据立方体 。 0维方体存放最高层的汇总，称作顶点方体 ；而存放最底层汇总的方体则称为 基本方体 。 数据立方体 一个方体的格 all time item location supplier time,item time,location time,supplier item,location item,supplier location,supplier time,item,location time,item,supplier time,location,supplier item,location,supplier time, item, location, supplier 0-D(顶点 ) 方体 1-D方体 2-D 方体 3-D 方体 4-D(基本 ) 方体 数据仓库的概念模型 最流行的数据仓库概念模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式的形式存在。 星型模式（ Star schema） : 事实表在中心，周围围绕地连接着维表（每维一个），事实表含有大量数据，没有冗余。 雪花模式（ Snowflake schema） : 是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加表中。结果，模式图形成类似于雪花的形状。 事实星座（ Fact constellations） : 多个事实表共享维表 , 这种模式可以看作星型模式集，因此称为星系模式（ galaxy schema），或者事实星座（ fact constellation） 星型模式实例 time_key day day_of_the_week month quarter year time location_key street city state_or_province country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch 雪花模式实例 time_key day day_of_the_week month quarter year time location_key street city_key location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_key item branch_key branch_name branch_type branch supplier_key supplier_type supplier city_key city state_or_province country city 事实星座模式实例 time_key day day_of_the_week month quarter year time location_key street city province_or_state country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch Shipping Fact Table time_key item_key shipper_key from_location to_location dollars_cost units_shipped shipper_key shipper_name location_key shipper_type shipper 一种数据挖掘查询语言 : DMQL DMQL首先包括定义数据仓库和数据集市的语言原语，这包括两种原语定义：一种是立方体定义，一种是维定义 立方体定义 (事实表 ) define cube : 维定义 (维表 ) define dimension as () 特殊案例 (共享维表的定义 ) 第一次作为维表定义 “ cube definition” 然后： define dimension as in cube 实例：使用 DMQL定义星型模式 define cube sales_star time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(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) 实例：使用 DMQL定义雪花模式 define cube sales_snowflake time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(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, province_or_state, country) 实例：使用 DMQL定义事实星座模式 define cube sales time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(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: dollar_cost = sum(cost_in_dollars), unit_shipped = 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 度量的分类 一个数据立方体的度量是一个 数值 函数，该函数可以对数据立方体的每一个点求值。 (刚才的示例中用的是什么函数？ ) 度量可以根据其所用的聚集函数分为三类： 分布的 (distributive)：将函数用于 n个聚集值得到的结果和将函数用于所有数据得到的结果一样。 比如： count()， sum()， min()， max()等 代数的 (algebraic)：函数可以由一个带 M个参数的代数函数计算（ M为有界整数），而每个参数值都可以有一个分布的聚集函数求得。 比如： avg()， min_N()， standard_deviation() 整体的 (holistic)：描述函数的子聚集所需的存储没有一个常数界。 比如： median()， mode()， rank() 5-6 王 灿 数据挖掘 0703004 概念分层 (1) 一个概念分层（ concept hierarchy）定义一个映射序列，将低层概念映射到更一般的高层概念 E.g. 表示 location的概念：杭州 浙江 中国 亚洲 概念分层允许我们在各种抽象级审查和处理数据 概念分层可以由系统用户、领域专家、知识工程师人工的提供，也可以根据数据分布的统计分析自动的产生 概念分层 (2): location维的一个概念分层 all Europe North_America Mexico Canada Spain Germany Vancouver M. Wind L. Chan . . . . . . all region office country Toronto Frankfurt city 许多概念分层的定义隐含在数据库的模式中。比如： location维的定义，officebuys(X, Z) X-customer表的关键字 P,Q-谓词变量 W, Y, Z-对象变量 模板具体化 age(X, 3039) income(X, 40k49k)=buys(X, VCR) 2.2%, 60% occupation(x, student) age(X, 2029)=buys(X, computer) 1.4%, 70% 背景知识：概念分层 背景知识是关于挖掘领域的知识 概念分层是背景知识的一种，它允许在多个抽象层上发现知识。 概念分层以树形结构的节点集来表示，其中每个节点本身代表一个概念，根节点称为 all，而叶节点则对应于维的原始数据值。 概念分层中，自顶向底进行层的标识，即 all为 0层，向下依次为 1， 2， 3等层 概念分层 上卷和下钻 在概念分层中应用上卷操作（概化），使得用户可以使用较高层次概念替代较低层次概念 可以在更有意义，更高、更抽象的层次观察数据，从而使发现的模式更加容易理解。 上卷操作使得数据得到压缩，在这个压缩的数据集上进行挖掘可以减少 I/O操作，使得挖掘的效率提高。 概念分层的下钻操作使用较低层概念代替较高层概念，从而使用户能够对过于一般化的数据做更详细分析。 上卷和下钻操作让用户以不同视图观察数据，洞察隐藏的数据联系。 概念分层的自动生成。 在同一个维上，可能根据用户的观点不同，存在多个概念分层。 概念分层的类型 四种常用的概念分层类型 模式分层 E.g., street $250 兴趣度度量 没有兴趣度度量，挖掘出来的有用模式，很可能会给淹没在用户不感兴趣的模式中。 兴趣度的客观度量方法：根据模式的结构和统计，用一个临界值来判断某个模式是不是用户感兴趣的。 常用的四种兴趣度的客观度量： 简单性 确定性 实用性 新颖性 简单性和确定性 简单性 (simplicity) 模式是否容易被人所理解 模式结构的函数（模式的长度、属性的个数、操作符个数）。e.g. 规则长度或者判定树的节点个数。 确定性 (certainty) 表示一个模式在多少概率下是有效的。 置信度 (A=B)=(包含 A和 B的元组值 )/(包含 A的元组值 )， e.g. buys(X, computer)=buys(X, software) 30%, 80% 100%置信度：准确的。 实用性和新颖性 实用性 可以用支持度来进行度量：支持度 (A=b) = (包含 A和 B的元组数 )/(元组总数 ) e.g. buys(X, computer)=buys(X, software)30%, 80% 同时满足最小置信度临界值和最小支持度临界值的关联规则称为 强关联规则 。 新颖性 提供新信息或提高给定模式集性能的模式 通过删除冗余模式来检测新颖性（一个模式已经为另外一个模式所蕴涵） Location(X, Canada)=buys(X, Sony_TV) 8%, 70% Location(X, Vancouver)=buys(X, Sony_TV) 2%, 70% 发现模式的表示和可视化 以多种形式显示挖掘出来的模式：表、图、判定树、数据立方体等等，以适合不同背景的用户的需要。 使用概念分层，用更有意义，更容易理解的高层概念来替代低层概念；并通过上卷、下钻等操作从不同的抽象级审视所发现的模式。 特定知识类型的表示。 一种数据挖掘查询语言 DMQL DMQL的设计目的 支持特别的和交互的数据查询，以便利于灵活和有效的知识发现 提供一种类似于 SQL的标准化查询语言 希望达到 SQL在关系数据库中的地位 系统开发和演化的基础 方便的信息交互，广泛的技术支持，商业化，广为认可 设计挑战 数据挖掘任务涉及面宽 数据特征、关联规则、分类、演变分析 每种任务都有不同的需求 DMQL的语法 采用与 SQL相类似的语法，便于与 SQL的集成。 允许在多个抽象层上，由关系数据库和数据仓库进行多类型知识的特殊挖掘 DMQL的设计基于数据挖掘原语，相应的，其语法中应该包括对以下任务的指定： 说明数据库的部分或用户感兴趣的数据集 要挖掘的知识类型 用于指导挖掘的背景知识 模式评估、兴趣度量 如何显示发现的知识 任务相关数据说明的语法 任务相关数据说明应包括的内容： 包含相关数据的数据库或数据仓库 相关的表名或数据立方体的名字 选择相关数据的条件 探察的相关属性或维 关于检索数据的排序和分组指令 任务相关数据说明子句 说明相关的数据库或数据仓库 use database 或 use data warehouse 指定涉及的表或数据立方体，定义检索条件 From where 列出要探察的属性或维 In relevance to 相关数据的排序 order by 相关数据的分组 group by 相关数据的分组条件： having 任务相关数据说明 示例 挖掘加拿大顾客与在 AllElectronics经常购买的商品之间的关联规则 use database AllElectronics_db in relevance to I.name, I.price, C.income, C.age from customer C, item I, purchases P, items_sold S where I.item_ID=S. item_ID and S.trans_ID=P.trans_ID and P.cust_ID=C.cust_ID and C.country=“Canada” group by P.date 指定挖掘知识类型 要挖掘的知识类型将决定所使用的数据挖掘功能。 几种主要的数据挖掘功能 特征化 目标数据的一般特征或特性汇总 数据区分 将目标对象的一般特性与一个或多个对比类对象的特性相 比较 关联分析 发现关联规则，这些规则展示属性值频繁的在给定数据中集中一起出现的条件 分类 找出区分数据类或概念的模型（或函数），以便用之标志未知的对象类。 聚类分析、孤立点分析、演变分析 指定挖掘知识类型 特征化 目标数据的一般特征或特性汇总 语法 Mine_Knowledge_Specification := mine characteristics as pattern_name analyze measure(s) analyze子句指定聚集度量（ count, sum, count%），通过这些度量对每个找到的数据特征进行计算 示例：顾客购买习惯的特征描述，对于每一特征，显示满足特征的任务相关元组的百分比 mine characteristics as custPurchasing analyze count