4-第四讲(数据挖掘原语、语言和系统结构及DMQL语言)

《数据挖掘》概念与技术第四讲数据挖掘原语、语言和系统结构为什么要数据挖掘原语和语言？没有精确的指令和规则，数据挖掘系统就没法使用。一个完全自动（不需要人为干预或指导）的数据挖掘机器如果进行自由挖掘，其造成的结果如下：会产生大量模式（重新把知识淹没）直接挖掘整个数据仓库，会涵盖所有数据，使挖掘效率低下缺少人类判断致使大部分有价值的模式集可能被忽略挖掘出的模式可能难以理解，缺乏有效性、新颖性和实用性——令人不感兴趣。解决途径：用数据挖掘原语和语言来指导数据挖掘过程，进行有目的的挖掘。数据挖掘原语的组成部分数据挖掘原语应该包括以下部分：说明数据库的部分或用户感兴趣的数据集而非整个数据仓库要挖掘的知识类型（关联模式或分类预测？你要挖掘什么？）用于指导挖掘的相关领域的专业背景知识模式评估、兴趣度量如何显示发现的知识（更加有效地显示挖掘出来的有趣模式）数据挖掘原语用于用户和数据挖掘系统通信，让用户能从不同的角度和深度审查和发现结果，并指导挖掘过程。说明数据挖掘任务的原语（5个部分）指定任务相关的数据数据库（仓库）名、数据立方体、选择条件、相关属性、分组条件指定要挖掘的知识类型从数据挖掘功能方面分要挖掘的知识类型：特征化、区分、关联、分类/预测、聚类通过数据挖掘原语说明挖掘过程中的已知背景知识概念分层，关联的确信度模式兴趣度度量简单性（利于人类理解）、确定性、实用性、新颖性发现模式的可视化规则、表、图表、图、判定树…1、指定任务相关的数据用户感兴趣的只是数据库或数据仓库的一个子集（select语句）。相关的操作：数据库DB－选择、投影、连接、聚集等；数据仓库DW－切片（获取具体的某一项的数据子集）、切块（获取某个范围区间内的数据）通过上述操作我们得到初始数据关系数据子集选择过程产生的新的数据关系在数据挖掘领域上述初始数据关系就是可挖掘的视图可挖掘的视图用于描述数据挖掘相关任务的数据集举例：任务相关的数据------举例挖掘加拿大顾客和他们常在AllElectronics购买的商品间的关联规则限定数据库（仓库）名字：（e.g.AllElectronics_db）限定感兴趣的包含相关数据的表或数据立方体名：（e.g.item,customer,purchases,item_sold）选择相关数据的限制条件（e.g.我只要时间地点的数据：今年（time）、加拿大（location））利用相关的属性或维进一步缩小要挖掘的数据集：（e.g.item表的name和price，customer表的income和age）2、指定要挖掘的知识类型（重要）要挖掘的知识类型将直接决定所要使用的数据挖掘功能。概念描述（特征化和区分），关联规则（例如挖掘顾客年龄与购买商品的联系），分类/预测（例如挖掘按照收入阶层分顾客分为多少类），聚类和演化分析等模式模板（用计算机能理解的形式化的方法来指定数据类型所满足的条件）又称元模式或元规则，用来指定所发现模式所必须匹配的条件，用于指导挖掘过程。举例：关联规则元模式研究AllElectronics的顾客购买习惯，使用如下关联规则：P(X:customer,W)∧Q(X,Y)=buys(X,Z)X----------customer表的关键字P,Q----------谓词变量W,Y,Z----------对象变量模板具体化age(X,“30…39”)∧income(X,“40k…49k”)=buys(X,“VCR”)[2.2%,60%][支持度,置信度]occupation(x,“student”)∧age(X,“20…29”)=buys(X,“computer”)[1.4%,70%]注意：支持度超过1%就相对来说该模式就比较有价值。3、通过数据挖掘原语说明背景知识：概念分层（最通用的最简单的指定背景知识的方法之一）背景知识是关于挖掘领域的知识，概念分层是背景知识的一种，它允许在多个抽象层上发现知识（因为越往上汇总等级越高越概化，越往下越细节，数量越多）。概念分层以树形结构的节点集来表示，其中每个节点本身代表一个概念，根节点称为all，而叶节点则对应于维的原始数据值（每一个非叶节点都是数据的汇总）。概念分层中两个操作—上卷和下钻在概念分层中应用上卷操作（概化），使得用户可以使用较高层次概念替代较低层次概念，从而可以在更有意义，跟抽象的层次观察数据，从而更加容易发现知识。同时上卷操作带来的数据归约还能有效的节省I/O支出。概念分层的下钻操作使用较低层概念代替较高层概念，从而使用户能够对过于一般化的数据做更详细分析。上卷和下钻操作让用户以不同视图观察数据，洞察隐藏的数据联系。概念分层还可以自动生成（根据数量多少自动形成）。概念分层的常见四种类型模式分层（根据数据相互之间的关系）E.g.,streetcityprovincecountry集合分组分层（针对数值类型的数据）E.g.,{20-39}=young,{40-59}=middle_aged操作导出的分层（有些数据本身就隐含层次结构关系）Email：[e-mail]基于规则的分层（人为形式化的规则产生概念分层）low_profit_margin(X)=price(X,P1)andcost(X,P2)and(P1-P2)$50high_profit_margin(X)=price(X,P1)andcost(X,P2)and(P1-P2)$250通过上述方法进行分类分层定义，人为地实现概念分层4、兴趣度度量没有兴趣度度量，挖掘出来的有用模式，很可能会给淹没在用户不感兴趣的模式中。简单性确定性实用性新颖性兴趣度的客观度量方法：根据模式的结构和统计，用一个临界值来判断某个模式是不是用户感兴趣的。简单性和确定性简单性(simplicity)模式是否容易被人所理解通过模式结构的函数来衡量挖掘出的知识是否简单是否能被理解。（包括模式的长度、属性的个数、操作符个数等）。e.g.规则长度或者判定树的节点个数。确定性(certainty)表示一个模式在多少概率下是有效的。置信度(A=B)=(包含A和B的元组值)/(包含A的元组值)，e.g.buys(X,“computer)=buys(X,“software”)[30%,80%]注意：若置信度是100%，则表示准确的描述，即由A必然推出B，然而它只是对以往结果的总结，置信度是动态变化的。实用性和新颖性实用性可以用支持度来进行度量：支持度(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%]5、发现模式的表示和可视化以多种形式显示挖掘出来的模式：表、图、判定树、数据立方体等等，以适合不同背景的用户的需要。使用概念分层，用更有意义，更容易理解的高层概念来替代低层概念；并通过上卷、下钻等操作从不同的抽象级审视所发现的模式。特定知识类型的表示（结合不同专业领域特点去表示对应知识）。一种数据挖掘查询语言：DMQL语言一种数据挖掘查询语言DMQLDMQL的设计目的支持特别的和交互的数据查询，以便利于灵活和有效的知识发现提供一种类似于SQL的标准化查询语言希望达到SQL在关系数据库中的地位系统开发和演化的基础方便的信息交互，广泛的技术支持，商业化，广为认可设计挑战数据挖掘任务涉及面宽数据特征、关联规则、分类、演变分析…每种任务都有不同的需求DMQL的语法DMQL采用与SQL相类似的语法，便于与SQL的集成。DMQL允许在多个抽象层上，由关系数据库和数据仓库进行多类型知识的特殊挖掘DMQL的设计基于数据挖掘原语，语法中应该包括对以下任务的指定（DMQL的语法要说明数据挖掘的五个要求）：1、说明数据库的部分或用户感兴趣的数据集2、要挖掘的知识类型（因为所挖掘的知识类型决定了所用到的数据挖掘功能）3、用于说明数据挖掘的背景知识（有表达专业背景知识的能力）4、模式评估、兴趣度量（便于获取感兴趣的部分，否则知识太多繁杂冗余）5、如何显示发现的知识1、任务相关数据说明的DMQL语法任务相关数据说明应包括的内容：包含相关数据的数据库或数据仓库数据库（仓库）中相关的表名或数据立方体的名字选择相关数据的条件探察的相关属性或维关于检索数据的排序和分组指令任务相关数据的DMQL说明子句说明相关的数据库或数据仓库usedatabasedb_name或usedatawarehousedw_name指定涉及的表或数据立方体，定义检索条件Fromrelation(s)/cube(s)[wherecondition]列出要探察的属性或维Inrelevancetoattributeordimension_list相关数据的排序orderbyorder_list相关数据的分组groupbygrouping_list相关数据的分组条件：havingcondition举例：任务相关数据说明挖掘加拿大顾客与在AllElectronics经常购买的商品之间的关联规则usedatabaseAllElectronics_dbinrelevancetoI.name,I.price,C.income,C.agefromcustomerC,itemI,purchasesP,items_soldSwhereI.item_ID=S.item_IDandS.trans_ID=P.trans_IDandP.cust_ID=C.cust_IDandC.country=“Canada”（**连接起各个表，并且规定选择条件顾客国籍是加拿大**）groupbyP.date（**按照购买日期进行分组**）2、指定挖掘知识类型要挖掘的知识类型将决定所使用的数据挖掘功能。几种主要的数据挖掘功能a、特征化目标数据的一般特征或特性汇总b、数据区分将目标对象的一般特性与一个或多个对比类对象的特性相比较c、关联分析发现关联规则，这些规则展示属性－值频繁的在给定数据中集中一起出现的条件d、分类找出区分数据类或概念的模型（或函数），以便用之标志未知的对象类。e、聚类分析、孤立点分析、演变分析…（后面三种算法非常复杂）下面我们介绍下A、B、C、D四种知识类型（数据挖掘功能）如何用DMQL语言表达。a、指定挖掘知识类型——特征化目标数据的一般特征或特性汇总语法Mine_Knowledge_Specification::=minecharacteristics[aspattern_name]analyzemeasure(s)patternname模式名，analyze子句指定聚集度量（count,sum,count%），通过这些度量对每个找到的数据特征进行计算示例：顾客购买习惯的特征描述，对于每一特征，显示满足特征的任务相关元组的百分比minecharacteristicsascustPurchasinganalyzecount%b、指定挖掘知识类型—数据区分将目标对象的一般特性与一个或多个对比类对象的特性相比较语法Mine_Knowledge_Specification::=minecom