数据挖掘原语、语言和系统结构.ppt

数据挖掘原语、语言和系统结构 * 为什么要数据挖掘原语和语言？ n一个完全自动（不需要人为干预或指导）的数据挖掘 机器只可能是“一只疯了的怪兽”。 n会产生大量模式（重新把知识淹没） n会涵盖所有数据，使得挖掘效率低下 n大部分有价值的模式集可能被忽略 n挖掘出的模式可能难以理解，缺乏有效性、新颖性和实用性 令人不感兴趣。 n没有精确的指令和规则，数据挖掘系统就没法使用。 n用数据挖掘原语和语言来指导数据挖掘。 * 数据挖掘原语的组成部分 n数据挖掘原语应该包括以下部分： n说明数据库的部分或用户感兴趣的数据集 n要挖掘的知识类型 n用于指导挖掘的背景知识 n模式评估、兴趣度量 n如何显示发现的知识 n数据挖掘原语用于用户和数据挖掘系统通信，让 用户能从不同的角度和深度审查和发现结果，并 指导挖掘过程。 * 说明数据挖掘任务的原语 n任务相关的数据 n数据库（仓库）名、数据立方体、选择条件、相关属性、分 组条件 n挖掘的知识类型 n特征化、区分、关联、分类/预测、聚类 n背景知识 n概念分层，关联的确信度 n模式兴趣度度量 n简单性、确定性、实用性、新颖性 n发现模式的可视化 n规则、表、图表、图、判定树 * 任务相关的数据 n用户感兴趣的只是数据库或数据仓库的一个子集 。 n相关的操作：DB选择、投影、连接、聚集等；DW 切片、切块 n初始数据关系 n数据子集选择过程产生的新的数据关系 n可挖掘的视图 n用于数据挖掘相关任务的数据集 * 任务相关的数据例子 n挖掘加拿大顾客和他们常在AllElectronics购买的 商品间的关联规则 n数据库（仓库）名 （e.g. AllElectronics_db） n包含相关数据的表或数据立方体名（e.g. item, customer, purchases, item_sold） n选择相关数据的条件（今年、加拿大） n相关的属性或维（item表的name和price，customer 表的income和age） * 要挖掘的知识类型 n要挖掘的知识类型将决定使用什么数据挖掘功能 。 n概念描述（特征化和区分），关联规则，分类/预测 ，聚类和演化分析等 n模式模板 n又称元模式或元规则，用来指定所发现模式所必须匹 配的条件，用于指导挖掘过程。 * 关联规则元模式例子 n研究AllElectronics的顾客购买习惯，使用如下关联规则 ： nP(X: customer, W) Q(X, Y) =buys(X, Z) nX-customer表的关键字 nP,Q-谓词变量 nW, Y, Z-对象变量 n模板具体化 nage(X, “3039”) income(X, “40k49k”)=buys(X, “VCR”) 2.2%, 60% noccupation(x, “student”) age(X, “2029”)=buys(X, “computer”)1.4%, 70% * 背景知识：概念分层 n背景知识是关于挖掘领域的知识 n概念分层是背景知识的一种，它允许在多个抽象层上 发现知识。 n概念分层以树形结构的节点集来表示，其中每个 节点本身代表一个概念，根节点称为all，而叶节 点则对应于维的原始数据值。 n概念分层中，自顶向底进行层的标识，即all为0层， 向下依次为1，2，3等层 * 概念分层 上卷和下钻 n在概念分层中应用上卷操作（概化），使得用户可以使 用较高层次概念替代较低层次概念 n可以在更有意义，更高、更抽象的层次观察数据，从而使发 现的模式更加容易理解。 n上卷操作使得数据得到压缩，在这个压缩的数据集上进行挖 掘可以减少I/O操作，使得挖掘的效率提高。 n概念分层的下钻操作使用较低层概念代替较高层概念， 从而使用户能够对过于一般化的数据做更详细分析。 n上卷和下钻操作让用户以不同视图观察数据，洞察隐藏 的数据联系。 n概念分层的自动生成。 n在同一个维上，可能根据用户的观点不同，存在多个概 念分层。 * 概念分层的类型 n四种常用的概念分层类型 n模式分层 nE.g., street $250 * 兴趣度度量 n没有兴趣度度量，挖掘出来的有用模式，很可能 会给淹没在用户不感兴趣的模式中。 n兴趣度的客观度量方法：根据模式的结构和统计 ，用一个临界值来判断某个模式是不是用户感兴 趣的。 n常用的四种兴趣度的客观度量： n简单性 n确定性 n实用性 n新颖性 * 简单性和确定性 n简单性(simplicity) n模式是否容易被人所理解 n模式结构的函数（模式的长度、属性的个数、操作符个数） 。e.g. 规则长度或者判定树的节点个数。 n确定性(certainty) n表示一个模式在多少概率下是有效的。 n置信度 (A=B)=(包含A和B的元组值)/(包含A的元组值)，e.g. buys(X, “computer)=buys(X, “software”)30%, 80% n100%置信度：准确的。 * 实用性和新颖性 n实用性 n可以用支持度来进行度量：支持度(A=b) = (包含A和 B的元组数 )/(元组总数) e.g. buys(X, “computer)=buys(X, “software”) 30%, 80% n同时满足最小置信度临界值和最小支持度临界值的关联规则称为强 关联规则。 n新颖性 n提供新信息或提高给定模式集性能的模式 n通过删除冗余模式来检测新颖性（一个模式已经为另外一个模式所 蕴涵） nLocation(X, “Canada”)=buys(X, “Sony_TV”) 8%, 70% nLocation(X, “Vancouver”)=buys(X, “Sony_TV”) 2%, 70% * 发现模式的表示和可视化 n以多种形式显示挖掘出来的模式：表、图、判定 树、数据立方体等等，以适合不同背景的用户的 需要。 n使用概念分层，用更有意义，更容易理解的高层 概念来替代低层概念；并通过上卷、下钻等操作 从不同的抽象级审视所发现的模式。 n特定知识类型的表示。 * 一种数据挖掘查询语言DMQL nDMQL的设计目的 n支持特别的和交互的数据查询，以便利于灵活和有效 的知识发现 n提供一种类似于SQL的标准化查询语言 n希望达到SQL在关系数据库中的地位 n系统开发和演化的基础 n方便的信息交互，广泛的技术支持，商业化，广为认可 n设计挑战 n数据挖掘任务涉及面宽 n数据特征、关联规则、分类、演变分析每种任务都有不 同的需求 * DMQL的语法 n采用与SQL相类似的语法，便于与SQL的集成。 n允许在多个抽象层上，由关系数据库和数据仓库进行多 类型知识的特殊挖掘 nDMQL的设计基于数据挖掘原语，相应的，其语法中应 该包括对以下任务的指定： n说明数据库的部分或用户感兴趣的数据集 n要挖掘的知识类型 n用于指导挖掘的背景知识 n模式评估、兴趣度量 n如何显示发现的知识 * 任务相关数据说明的语法 n任务相关数据说明应包括的内容： n包含相关数据的数据库或数据仓库 n相关的表名或数据立方体的名字 n选择相关数据的条件 n探察的相关属性或维 n关于检索数据的排序和分组指令 * 任务相关数据说明子句 n说明相关的数据库或数据仓库 nuse database 或use data warehouse n指定涉及的表或数据立方体，定义检索条件 nFrom where n列出要探察的属性或维 nIn relevance to n相关数据的排序 norder by n相关数据的分组 ngroup by n相关数据的分组条件： nhaving * 任务相关数据说明示例 n挖掘加拿大顾客与在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 * 指定挖掘知识类型 n要挖掘的知识类型将决定所使用的数据挖掘功能。 n几种主要的数据挖掘功能 n特征化 n目标数据的一般特征或特性汇总 n数据区分 n将目标对象的一般特性与一个或多个对比类对象的特性相比较 n关联分析 n发现关联规则，这些规则展示属性值频繁的在给定数据中集中一起出现的条 件 n分类 n找出区分数据类或概念的模型（或函数），以便用之标志未知的对象类。 n聚类分析、孤立点分析、演变分析 * 指定挖掘知识类型特征化 n目标数据的一般特征或特性汇总 n语法 Mine_Knowledge_Specification := mine characteristics as pattern_name analyze measure(s) nanalyze子句指定聚集度量（count, sum, count%），通过这些 度量对每个找到的数据特征进行计算 n示例：顾客购买习惯的特征描述，对于每一特征，显示 满足特征的任务相关元组的百分比 mine characteristics as custPurchasinganalyze count% * 指定挖掘知识类型数据区分 n将目标对象的一般特性与一个或多个对比类对象的特性相比较 n语法 Mine_Knowledge_Specification := mine comparison as pattern_name for target_class where target_condition versus contrast_class_i where contrast_condition_i analyze measure(s) nanalyze子句指定聚集度量（count, sum, count%），将对每个描述进行计算 或显示 n示例：用户将客户区分为大顾客与小顾客，并显示满足每个区分 的元组数 Mine_Knowledge_Specification := mine comparison as purchaseGroups for bigSpenders where avg(I.price) $100 versus budgetSpenders where avg(I.price) $100 analyze count * 指定挖掘知识类型关联 n发现关联规则，这些规则展示属性值频繁的在给定数 据中集中一起出现的条件 n语法 Mine_Knowledge_Specification := mine associations as pattern_name nmatching 子句后面往往可以跟元模式，用来指定用户有兴趣探 察的数据束或假定 n示例：使用元模式指导的挖掘来指定用于描述顾客购买 习惯的关联规则挖掘 Mine_Knowledge_Specification := mine associations as buyingHabbits matching P(X: customer, W) Q(X, Y) =buys(X, Z) * 指定挖掘知识类型分类 n找出区分数据类或概念的模型（或函数），以便用之标 志未知的对象类 n语法 Mine_Knowledge_Specification := mine classification as pattern_name analyze classifying_attribute_or_dimension nanalyze子句说明根据某个属性或维进行分类，通常每个分 类属性的或维的值就代表一个分类 n示例：挖掘客户的信用等级模式 mine classification as classifyCustCreditRating analyze credit_rating * 概念分层说明的语法 n每个属性或维可能有多个概念分层，已适应用户从不同 角度看待问题的需要；用户可以使用如下语句指定使用 哪个概念分层： use hierarchy for attribute_or_dimension n示例1：定义模式分层location，location中包含一个概 念分层的全序（street threshold = threshold_value n示例：挖掘关联规则时限定找到的感兴趣模式必须满足 最小支持度为5%，最小置信度为70% with support threshold = 5% with confidence threshold = 70% * 模式表示和可视化说明的语法 n对挖掘出来的模式，可以使用多种形式进行表示 ，包括：规则、表、饼图、立方体、曲线等 display as n为了方便用户在不同的角度或者不同的概念层观 察发现的模式，用户可以使用上卷、下钻、添加 或丢弃属性或维等操作 Multilevel_Manipulation := roll up on attribute_or_dimension | drill down on attribute_or_dimension | add attribute_or_dimension | drop attribute_or_dimension 例：假定描述是基于维location, age和income的挖掘。用户可以 ”roll up on location”, “drop age”, 概化发现的模式。 * 一个DMQL查询的完整示例 n查询AllElectronics购买商品的价格不小于$100的，用 AmEx信用卡结帐的加拿大顾客的购买习惯特征（年龄 ，商品类型和产地），以表的形式表示挖掘的模式 use database AllElectronics_db use hierarchy location_hierarchy for B.address mine characteristics as customerPurchasing analyze count% in relevance to C.age, I.type, I.place_made from customer C, item I, purchases P, items_sold S, works_at W, branch where I.item_ID = S.item_ID and S.trans_ID = P.trans_ID and P.cust_ID = C.cust_ID and P.method_paid = AmEx and P.empl_ID = W.empl_ID and W.branch_ID = B.branch_ID and B.address = Canada“ and I.price = 100 with noise threshold = 0.05 display as table * 其他数据挖掘语言和数据挖掘原语的标准化 n关联规则语言规范 nMSQL (Imielinski & Virmani99) nMineRule (Meo Psaila and Ceri96) nQuery flocks based on Datalog syntax (Tsur et al98) n数据挖掘的OLE DB n基于OLE DB和OLE DB for OLAP技术 n整合数据库，数据仓库和数据挖掘 nCRISP-DM (CRoss-Industry Standard P