(精品)4、数据挖掘原语、语言和系统结构

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,9-10,王 灿,数据挖掘,sjwj,0703004,数据挖掘原语、语言和系统结构,为什么要数据挖掘原语和语言？,一个完全自动（不需要人为干预或指导）的数据挖掘机器只可能是,“一只疯了的怪兽”。,会产生大量模式（重新把知识淹没）,会涵盖所有数据，使得挖掘效率低下,大部分有价值的模式集可能被忽略,挖掘出的模式可能难以理解，缺乏有效性、新颖性和实用性,令人不感兴趣。,没有精确的指令和规则，数据挖掘系统就没法使用。,用数据挖掘原语和语言来指导数据挖掘。,数据挖掘原语的组成部分,数据挖掘原语应该包括以下部分：,说明数据库的部分或用户感兴趣的数据集,要挖掘的知识类型,用于指导挖掘的背景知识,模式评估、兴趣度量,如何显示发现的知识,数据挖掘原语用于用户和数据挖掘系统通信，让用户能从不同的角度和深度审查和发现结果，并指导挖掘过程。,说明数据挖掘任务的原语,任务相关的数据,数据库（仓库）名、数据立方体、选择条件、相关属性、分组条件,挖掘的知识类型,特征化、区分、关联、分类,/,预测、聚类,背景知识,概念分层，关联的确信度,模式兴趣度度量,简单性、确定性、实用性、新颖性,发现模式的可视化,规则、表、图表、图、判定树,任务相关的数据,用户感兴趣的只是数据库或数据仓库的一个子集。,相关的操作：,DB,选择、投影、连接、聚集等；,DW,切片、切块,初始数据关系,数据子集选择过程产生的新的数据关系,可挖掘的视图,用于数据挖掘相关任务的数据集,任务相关的数据,例子,挖掘加拿大顾客和他们常在,AllElectronics,购买的商品间的关联规则,数据库（仓库）名 （,e.g.,AllElectronics_db,）,包含相关数据的表或数据立方体名,（,e.g. item, customer, purchases,item_sold,）,选择相关数据的条件（今年、加拿大）,相关的属性或维（,item,表的,name,和,price,，,customer,表的,income,和,age,）,要挖掘的知识类型,要挖掘的知识类型将决定使用什么数据挖掘功能。,概念描述（特征化和区分），关联规则，分类,/,预测，聚类和演化分析等,模式模板,又称元模式或元规则，用来指定所发现模式所必须匹配的条件，用于指导挖掘过程。,关联规则元模式,例子,研究,AllElectronics,的顾客购买习惯，使用如下关联规则：,P(X: customer, W) Q(X, Y) =,buys(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 city province country,集合分组分层,E.g., 20-39 = young, 40-59 =,middle_aged,操作导出的分层,Email,：,abc,基于规则的分层,low_profit_margin,(X) =,price(X, P1) and cost (X, P2) and (P1 - P2) $50,high_profit_margin,(X) $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%,指定挖掘知识类型,数据区分,将目标对象的一般特性与一个或多个对比类对象的特性相比较,语法,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,),analyze,子句指定聚集度量（,count, sum, count%,），将对每个描述进行计算或显示,示例：用户将客户区分为大顾客与小顾客，并显示满足每个区分的元组数,Mine_Knowledge_Specification,:=,mine comparison,as,purchaseGroups,for,bigSpenders,where,avg(I.price,),$100,versus,budgetSpenders,where,avg(I.price,),$100,analyze,count,指定挖掘知识类型,关联,发现关联规则，这些规则展示属性值频繁的在给定数据中集中一起出现的条件,语法,Mine_Knowledge_Specification,:=,mine associations,as,pattern_name,matching,子句后面往往可以跟元模式，用来指定用户有兴趣探察的数据束或假定,示例：使用元模式指导的挖掘来指定用于描述顾客购买习惯的关联规则挖掘,Mine_Knowledge_Specification,:=,mine associations,as,buyingHabbits,matching,P(X: customer, W) Q(X, Y) =,buys(X, Z),指定挖掘知识类型,分类,找出区分数据类或概念的模型（或函数），以便用之标志未知的对象类,语法,Mine_Knowledge_Specification,:=,mine classification,as,pattern_name,analyze,classifying_attribute_or_dimension,analyze,子句说明根据某个属性或维进行分类，通常每个分类属性的或维的值就代表一个分类,示例：挖掘客户的信用等级模式,mine classification,as,classifyCustCreditRating,analyze,credit_rating,概念分层说明的语法,每个属性或维可能有多个概念分层，已适应用户从不同角度看待问题的需要；用户可以使用如下语句指定使用哪个概念分层：,use hierarchy,for,示例,1,：定义模式分层,location,，,location,中包含一个概念分层的全序（,streetcityprovincecountry),，相应的,DMQL,语法定义如下所示：,Define hierarchy,location_hierarchy,on,location,as,street, city, province, country,概念分层说明的语法,集合分组分层,Level 0,Level 1,Level2,define hierarchy,age_hierarchy,for,age,on,customer,as,level1: young,middle_aged, senior level0:,all,level2: 2039 level1: young,level2: 4059 level1:,middle_aged,level2: 6089 level1: senior,兴趣度度量说明的语法,兴趣度的度量包括置信度、支持度、噪声和新颖度等度量，可以通过将模式的兴趣度度量与相应的临界值相比较决定一个模式是否为感兴趣的模式。,with,threshold,=,threshold_value,示例：挖掘关联规则时限定找到的感兴趣模式必须满足最小支持度为,5%,，最小置信度为,70%,with,support,threshold,= 5%,with,confidence,threshold,= 70%,模式表示和可视化说明的语法,对挖掘出来的模式，可以使用多种形式进行表示，包括：规则、表、饼图、立方体、曲线等,display as,为了方便用户在不同的角度或者不同的概念层观察发现的模式，用户可以使用上卷、下钻、添加或丢弃属性或维等操作,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,查询的完整示例,查询,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,其他数据挖掘语言和数据挖掘原语的标准化,关联规则语言规范,MSQL (,Imielinski,& Virmani99),MineRule,(,Meo,Psaila,and Ceri96),Query flocks based on,Datalog,syntax (,Tsur,et al98),数据挖掘的,OLE DB,基于,OLE DB,和,OLE DB for OLAP,技术,整合数据库，数据仓库和数据挖掘,CRISP-DM (,CRoss,-Industry Standard Process for Data Mining),提供了一个有效的数据挖掘平台和处理结构,强调使用数据挖掘技术解决商务问题的需要,数据挖掘系统的体系结构,一个好的系统体系结构，可以使数据挖掘系统在性能、可交互性、可使用性以及可扩展性等多个方面的都得到良好的保证。,当前大部分数据都是存储在数据库或者是数据仓库之中，在此基础上往往还构建了综合的信息处理和信息分析功能。,数据挖掘系统体系结构的核心问题：我们是否应当将数据挖掘系统与数据库,/,数据仓库系统集成（或耦合）,不耦合,松散耦合,半紧密耦合,紧密耦合,DM,与,DB/DW,的耦合方式,(1),不耦合,DM,系统不利用,DB/DW,系统的任何功能。,简单，但是没有利用数据库的功能意味着信息分析处理借助第三方工具，这使得系统的构建和集成变得很困难。,松散耦合,DM,系统将使用,DB/DW,系统的某些功能。,简单的利用,DB/DW,提供的数据查询功能，没有使用,DB/DW,的后台优化，算法大部分是基于内存的，性能和可扩展性差,DM,与,DB/DW,的耦合方式,(2),半紧密耦合,除了将,DM,系统连接到一个,DB/DW,系统之外，一些基本数据挖掘原语（通过分析频繁遇到的数据挖掘功能确定）可以在,DB/DW,系统中实现。,一些中间的挖掘结果可以在,DB/DW,上实现计算或有效的即时计算，性能会有较大提高。,紧密耦合,DM,系统平滑的集成到,DB/DW,系统中。数据挖掘子系统被视为信息挖掘子系统的一部分，数据挖掘查询和功能根据,DB,或,DW,系统的挖掘查询分析、数据结构、索引模式和查询处理方法优化。,提供了一个统一的信息处理平台，功能、性能等方面都会达到一个高水平。,