概念描述特征化与比较课件.ppt

《概念描述特征化与比较课件.ppt》由会员分享，可在线阅读，更多相关《概念描述特征化与比较课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于概念描述特征化与比较第1页，此课件共63页哦两种不同类别的数据挖掘n从数据分析的角度看，数据挖掘可以分为描述性挖掘和预测性挖掘q描述性挖掘：以简洁概要的方式描述数据，并提供数据的有趣的一般性质。q预测性数据挖掘：通过分析数据建立一个或一组模型，并试图预测新数据集的行为。第2页，此课件共63页哦什么是概念描述？n概念描述是一种最简单的描述性挖掘q当所描述的概念所指的是一类对象时，也称为类描类描述述n概念指的是一类数据的集合qe.g.研究生，大客户n概念描述是指为数据的特征化和比较产生描述q特征化：提供给定数据集的简洁汇总。q区分：提供两个或多个数据集的比较描述。第3页，此课件共63页哦概念描

2、述 VS.OLAPn概念描述和数据仓库的联机分析处理（OLAP）都跟数据概化密切相关，即以简洁的形式在更一般的抽象层描述数据，允许数据在抽象层概化，便于考察数据的一般行为。n两者的主要区别：q概念描述n可以处理复杂数据类型的属性及其聚集n一个更加自动化的过程qOLAPn实际使用的OLAP系统中，维和度量的数据类型都非常有限（非数值型的维和数值型的数据），表现为一种简单的数据分析模型n一个由用户控制的过程第4页，此课件共63页哦数据概化n数据概化q数据库中的数据和对象通常包含原始概念层的细节信息，数据概化就是将数据库中的跟任务相关的数据集从较低的概念层抽象到较高的概念层的过程。n主要方法：q数据

3、立方体（OLAP使用的方法）q面向属性的归纳方法12345概念层第5页，此课件共63页哦数据概化：数据立方体方法n执行计算并将结果存储在数据立方体中n优点：q数据概化的一种有效实现q可以计算各种不同的度量值n比如：count(),sum(),average(),max()q概化和特征分析通过一系列的数据立方体操作完成，比如上卷、下钻等n缺点q只能处理非数值类型的维和简单聚集数值类型的度量值（大部分现有商业系统中，只能为非数值类型的维产生概念分层）q缺乏智能分析，不能自动确定分析中该使用哪些维，应该概化到哪个层次第6页，此课件共63页哦面向属性的归纳n一种面向关系数据关系数据查询的、基于汇总汇总

4、的在线在线数据分析技术。n受数据类型和度量类型的约束比较少n面向属性归纳的基本思想：q使用关系数据库查询收集任务相关的数据q通过考察任务相关数据中每个属性的不同值的个数进行概化，方法是属性删除或者是属性概化q通过合并相等的，概化的广义元组，并累计他们对应的计数值进行聚集操作q通过与用户交互，将广义关系以图表或规则等形式，提交给用户第7页，此课件共63页哦面向属性的归纳的基本步骤n数据聚焦，获得初始工作关系n进行面向属性的归纳q基本操作是数据概化，对有大量不同值的属性大量不同值的属性，进行进一步概化n属性删除n属性概化q属性概化控制：控制概化过程，确定有多少不同的值才算是有大量不同值的属性大量不

5、同值的属性n属性概化临界值控制n概化关系临界值控制第8页，此课件共63页哦数据聚焦（1）n目的是获得跟任务相关的数据集，包括属性或维，在DMQL中他们由in relevance to子句表示。n示例：qDMQL:描述Big-University数据库中研究生研究生的一般特征use Big_University_DBmine characteristics as“Science_Students”in relevance to name,gender,major,birth_place,birth_date,residence,phone#,gpafrom studentwhere status

6、 in“graduate”第9页，此课件共63页哦数据聚焦（2）q将数据挖掘查询转换为关系查询Select name,gender,major,birth_place,birth_date,residence,phone#,gpafrom studentwhere status in“Msc”,“MBA”,“PhD”n数据聚焦时的困难q用户在指定相关的数据集方面存在困难，遗漏在描述中可能起作用的属性q用户可能引进太多的属性第10页，此课件共63页哦数据概化n数据概化的两种常用方法：属性删除和属性概化q属性删除的适用规则：对初始工作关系中具有大量不同值的属性，符合以下情况，应使用属性删除：n在此

7、属性上没有概化操作符（比如该属性没有定义相关的概念分层）n该属性的较高层概念用其他属性表示q属性概化的使用规则：如果初始工作关系中的某个属性具有大量不同值，且该属性上存在概化操作符，则使用该概化操作符对该属性进行数据概化操作第11页，此课件共63页哦11-12王王 灿灿数据挖掘数据挖掘0703004第12页，此课件共63页哦属性概化控制n确定什么是“具有大量的不同值”，控制将属性概化到多高的抽象层。n属性概化控制的两种常用方法：q属性概化临界值控制n对所有属性设置一个概化临界值或者是对每个属性都设置一个临界值（一般为2到8）q概化关系临界值控制n为概化关系设置一个临界值，确定概化关系中，不同元

8、组的个数的最大值。（通常为10到30，应该允许在实际应用中进行调整）q两种技术的顺序使用：使用属性概化临界值控制来概化每个属性，然后使用关系临界值控制进一步压缩概化的关系。n相等元组的合并、累计计数和其他聚集值第13页，此课件共63页哦面向属性的归纳示例n挖掘Big-University数据库中研究生的一般特征qname：删除属性qgender：保留该属性，不概化qmajor：根据概念分层向上攀升文，理，工qbirth_place：根据概念分层location向上攀升qbirth_date：概化为age，再概化为age_rangeqresidence：根据概念分层location向上攀升qph

9、one#：删除属性qgpa：根据GPA的分级作为概念分层第14页，此课件共63页哦面向属性的归纳示例主概化关系主概化关系初始工作关系初始工作关系第15页，此课件共63页哦面向属性的归纳算法n输入q1.DB;2.数据挖掘查询DMQuery;3.属性列表;4.属性的概念分层;属性的概化临界值；n输出q主概化关系Pn算法描述：1.W get_task_relevant_data(DMQuery,DB)2.prepare_for_generalization(W)1.扫描W，收集每个属性a的不同值2.对每个属性a，根据临界值确定是否删除，如果不删除，则计算其最小期望层次L，并确定映射对(v,v)3.P

10、 generalization(W)q通过使用v代替W中每个v，累计计数并计算所有聚集值，导出P1.每个概化元组的插入或累积计数2.用数组表示P第16页，此课件共63页哦导出概化的表示(1)n概化关系q一部分或者所有属性得到概化的关系，包含计数或其他度量值的聚集n交叉表q二维交叉表使用每行显示一个属性，使用每列显示另外一个属性将结果集映射到表中q可视化技巧：n条形图、饼图、曲线和数据立方体浏览工具（用单元的大小代表计数，用单元亮度代表另外的度量）第17页，此课件共63页哦导出概化的表示(2)n量化规则q使用t_weight表示主概化关系中每个元组的典型性n量化特征规则q将概化的结果映射到相应的

11、量化特征规则中，比如：量化特征规则中每个条件的析取成为目标类的一个必要条件；亦即，如果X在目标类中，则X满足conditioni的概率是wi第18页，此课件共63页哦特征化过程中的困难n特征化过程中的两大困难q复杂数据类型的处理q缺乏一种自动概化的过程，用户必须告诉系统n哪些属性或维应该包括在类特征化中n每个维应该概化到多高的程度第19页，此课件共63页哦为什么进行属性相关分析？n数据仓库和OLAP系统中的多维数据分析缺乏一个自动概化过程自动概化过程，这使得这个过程中需要有很多用户干预q用户必须告诉系统哪些维或属性应当包含在类分析中(难)n属性太少，则造成挖掘的描述结果不正确n属性太多，浪费计

12、算、淹没知识q告诉系统每个维应当概化到多高的层次（易）n直接通过概化的临界值，说明给定维应当达到的概化程度n对概化层次不满意，则可以指定需要上卷或下钻的维第20页，此课件共63页哦解析特征化：属性相关分析n属性相关分析q通过识别不相关或者是弱相关的属性，将它们排除在概念描述过程之外，从而确定哪些属性应当包含在类特征化和类比较中。q解析特征化n包含属性相关分析的类特征化q解析比较n包含属性相关分析的类比较第21页，此课件共63页哦属性相关分析（1）n通过属性相关性分析，滤掉统计上不相关或弱相关的属性，保留对手头数据挖掘任务最相关的属性。n对于给定的属性，一个属性或维被认为是高度相关的，如果该属性

13、或维的值可能用于区分该类和其他类。q比如：区分昂贵汽车和便宜汽车（可选择的属性：颜色，型号，品牌.）第22页，此课件共63页哦属性相关分析（2）n在同一个维内，对于区分一个类与其他类不同层的概念可能有很不同的能力q比如：birth_date维，day,month与salary无关，而year（或将其进一步概化为birth_decade）则与salary有关n类特征化中的比较类q除特征化的数据集外，数据库中可比较的数据集都作为对比类n比如：研究生特征化的例子，对比类为不是研究生的学生的集合（e.g.本科生）（可选择的属性：性别、籍贯、专业、平均成绩、年龄段）第23页，此课件共63页哦属性相关分析

14、的方法n属性相关分析的基本思想是计算某种度量，用于量化属性与给定类或概念的相关性。q可采用的度量包括：信息增益、Gini索引、不确定性和相关系数。（涉及机器学习、统计、模糊和粗糙集理论等方面的相关知识）q比如：信息增益通过计算一个样本分类的期望信息期望信息和属性的熵属性的熵来获得一个属性的信息增益属性的信息增益，判定该属性与当前的特征化任务的相关性。第24页，此课件共63页哦信息增益(1)nS是一个训练样本训练样本的集合，该样本中每个集合的类编号类编号已知。每个样本为一个元组元组。有个属性用来判定某个训练样本的类编号（类似于学生记录中的status属性）n假设S中有m个类，总共s个训练样本，每

15、个类ci有Si个样本(i1,2,3.m)，那么任意一个样本属于类Ci的概率是si/s，那么用来分类一个给定样本的期望信息期望信息是：第25页，此课件共63页哦信息增益(2)n一个有v个值的属性Aa1,a2,.,av可以将S分成v个子集S1,S2,.,Sv，其中Sj包含S中属性A上的值为aj的样本。假设Sj包含类Ci的sij个样本。根据A的这种划分的期望信息称为A的熵熵nA上该划分的获得的信息增益定义为：n具有高信息增益的属性，是给定集合中具有高区分度的属性。所以可以通过计算S中样本的每个属性的信息增益，来得到一个属性的相关性的排序。第26页，此课件共63页哦概念描述的属性相关分析步骤(1)n数

16、据收集q通过查询处理，收集目标类和对比类数据n使用保守的AOI进行预相关分析q识别属性和维的集合，它们是所选择的相关性分析度量的应用对象n因为不同的概念层对某个类描述的相关性可能很不同，因此在这个过程中同时要包含概念分层q对有大量不同值的属性进行删除或概化q在这一级进行概化时，临界值要相应比较高，以便在后续步骤的分析中包含更多属性（保守的）q产生候选关系第27页，此课件共63页哦概念描述的属性相关分析步骤(2)n使用选定的相关分析度量删除不相关和弱相关的属性q使用选定的相关分析度量（e.g.信息增益），评估候选关系中的每个属性q根据所计算的相关性对属性进行排序q低于临界值的不相关和弱相关的属性

17、被删除q产生初始目标类工作关系（或初始对比类工作关系）n使用AOI产生概念描述q使用一组不太保守的属性概化临界值进行AOI第28页，此课件共63页哦解析特征化示例(1)n任务:使用解析特征化挖掘BigUniversity的研究生的一般特征描述n给定q属性name,gender,major,birth_place,birth_date,phone#和gpaqUi=属性分析阀值qTi=属性概化阀值qR=属性相关阀值第29页，此课件共63页哦解析特征化示例(2)n1.数据收集q目标类：研究生q对比类：本科生n2.使用保守的阀值Ui和Ti进行AOIq属性删除nname和phone#q属性概化n概化ma

18、jor,birth_place,birth_date 和 gpaq进行累积计数q候选关系候选关系：gender,major,birth_country,age_range 和gpa第30页，此课件共63页哦目标类候选关系：研究生目标类候选关系：研究生(=120)对比类候选关系：本科生对比类候选关系：本科生(=130)(可以在类比较时使用）可以在类比较时使用）解析特征化示例(3)第31页，此课件共63页哦n3.相关性分析q计算给定的样本分类所需要的期望信息q计算每个属性的熵:e.g.majorNumber of grad students in“Science”Number of undergr

19、ad students in“Science”解析特征化示例(4)第32页，此课件共63页哦n如果样本根据major划分，则计算给定的样本进行分类所需的期望信息：n计算该属性的信息增益：q所有属性的信息增益解析特征化示例(5)第33页，此课件共63页哦n4.导出初始工作关系qR=0.1（临界值）q从候选关系中去处不相关/弱相关的属性=去处 gender,birth_countryq因为类描述任务是类特征化，所以这里去处候选对比类关系n5.在 W0 上用进行不保守的AOI初始目标类工作关系初始目标类工作关系 W0:研究生研究生解析特征化示例(6)第34页，此课件共63页哦挖掘类比较：区分不同的类

20、n类比较挖掘的目标是得到将目标类与对比类相区分的描述。q目标类和对比类间必须具有可比性，即两者间要有相似的属性或维。n本科生 VS.研究生；student VS.addressn很多应用于概念描述的技巧可以应用于类比较，比如属性概化。q属性概化必须在所有比较类上同步进行，将属性概化到同一抽象层后进行比较。nCity VS country第35页，此课件共63页哦类比较的过程n数据收集q通过查询处理收集数据库中相关的数据，并将其划分为一个目标类和一个或多个对比类n维相关分析q使用属性相关分析方法，使我们的任务中仅包含强相关的维n同步概化q同步的在目标类和对比类上进行概化，得到主目标类主目标类 关

21、系关系/方体方体 和 主对比主对比类类 关系关系/方体方体n导出比较的表示q用可视化技术表达类比较描述，通常会包含“对比”度量，反映目标类与对比类间的比较(e.g count%)第36页，此课件共63页哦类比较的有效实施n目标类和对比类的同步概化，以在相同抽象级别上进行类比较n使用数据立方体技术有效的实施类比较q引入一个标志位（数据立方体的一个新维）来表示目标类或对比类q目标类和对比类除了这个新维外，其他部分在数据立方体中的表示是相同的n通过上卷和下钻来同步概化或具体化第37页，此课件共63页哦类比较挖掘示例（1）n任务q比较Big-University本科生和研究生的一般特征n任务的DMQL

22、描述use Big_University_DBmine comparison as“grad_vs_undergrad_students”in relevance to name,gender,major,birth_place,birth_date,residence,phone#,gpafor“graduate_students”where status in“graduate”versus“undergraduate_students”where status in“undergraduate”analyze count%from student第38页，此课件共63页哦类比较挖掘示例（

23、2）n进行类比较挖掘的输入：q给定的属性：name,gender,major,birth_place,birth_date,residence,phone#and gpaq在属性ai上定义的概念分层 Gen(ai)q在属性ai上定义的属性分析临界值 Uiq在属性ai上定义的属性概化临界值Tiq属性相关性临界值R第39页，此课件共63页哦类比较挖掘示例（3）n任务的处理过程q数据收集nDMQL查询转化为关系查询，得到初始目标类工作关系初始目标类工作关系和初始对比类工作关系初始对比类工作关系 n可以看成使构造数据立方体的过程q引入一个新维status来标志目标类和对比类（graduate,unde

24、rgraduate）q其他属性形成剩余的维q在两个数据类上进行维相关分析n根据Ui与R，删除不相关或者使弱相关的维：name,gender,major,phone#第40页，此课件共63页哦类比较挖掘示例（4）q同步概化n在目标类和对比类上同步的进行概化，将相关的维概化到由属性概化临界值Ti决定的同样的层次，形成主目标类主目标类 关关系系/方体方体 和主对比类主对比类 关系关系/方体方体q导出比较的表示n用表、图或规则等形式表达类比较描述的挖掘结果n用户应该能够在主目标类主目标类 关系关系/方体方体 和主对比类主对比类 关系关系/方体方体进行进一步的OLAP操作第41页，此课件共63页哦类比较

25、挖掘示例（5）目标类的主概化关系目标类的主概化关系:研究生研究生对比类的主概化关系对比类的主概化关系:本科生本科生第42页，此课件共63页哦类比较描述的表示n用可视化的方式将类比较描述呈现给用户，有助于用户对挖掘结果的理解。q概化关系q交叉图q柱状图q饼图q曲线q量化规则量化规则第43页，此课件共63页哦类比较描述的量化区分规则表示（1）n类比较描述中的目标类和对比类的区分特性也可以用量化规则来表示，即量化区分规则q量化区分规则使用d-weight作为兴趣度度量（特征化使用什么作为兴趣度度量？）nqa概化元组nCj目标类nqa的d-weight是初始目标类工作关系中被qa覆盖的元组数 与 初始

26、目标类和对比类工作关系中被qa覆盖的总元组数的比第44页，此课件共63页哦类比较描述的量化区分规则表示（2）n目标类中较高的d-weight表明概化元组所代表的概念主要来自于目标类n较低的d-weight值则表明该概念主要来自于对比类对给定的status=“Graduate”,Birth_coutry=“Canada”,Age_range=“25-30”,Gpa=“Good”概化元组，其d-weight=90/(90+210)=30%(什么意思？)第45页，此课件共63页哦类比较描述的量化区分规则表示（3）n使用类比较描述的量化区分规则表示可以更好的描述上述的情况，其形式为：n比如，刚才的挖掘

27、结果可以使用量化区分规则表达如下：n请注意该区分规则表达的是充分条件，即X满足条件，则X为研究生的概率为30%(特征化量化规则表达的是什么条件？)第46页，此课件共63页哦类描述：特征化和比较的表示n类特征化和类比较是形成类描述的两个方面，我们可以通过综合类特征化规则和类区分规则来形成类描述规则。q量化特征化规则n必要条件q量化区分规则n充分条件q量化描述规则n充要条件第47页，此课件共63页哦量化描述规则示例(1)n一个给定类的概化元组的t-weight表明给定类中该元组的典型性（e.g.欧洲的销售(类)中，电视机(元组)占多少百分比?）n一个元组的d-weight表明，给定类的元组和对比类

28、的元组相比，有多大区别（e.g.欧洲(类)的电视机(元组)销售和北美的电视机销售比如何？）第48页，此课件共63页哦量化描述规则示例(2)n对于上述交叉表，可以直接用量化描述规则来表示q表明对99年AllElectronics公司的TV和计算机销售，如果一商品在欧洲售出，则其为TV的概率为25该公司40的TV在欧洲售出第49页，此课件共63页哦在大型数据库中挖掘描述统计度量n对于数据挖掘任务，用户经常关心的数据特征包括数据的中心趋势和离散特征，这些度量帮我们更好的理解数据的分布q中心趋势的度量包括：mean,median,mode 和 midrangeq数据离散度量包括：quartiles,o

29、utliers,variance 和其他度量n从数据挖掘的角度看，我们关心的是在大数据量的情况下，如何有效的计算上述度量n关系数据库中，系统提供了以下聚集函数：count(),sum(),avg(),max(),min()q在大型数据库中挖掘用户感兴趣的描述统计计量涉及到如何利用关系数据库现有的函数来计算上述两类用户感兴趣的度量值第50页，此课件共63页哦度量中心趋势n算术平均值q 加权算术平均n中位值：使用一个近似的计算来度量q如果值的个数n是奇数，则中位数(median)是有序集合的中间值，否则它是中间两个数的平均值q用插值法(interpolation)来近似计算n模(mode)q表示数

30、据集中出现频率最高的值q单模态、双模态、三模态、多模态和没有模的情况q单模态近似值计算的经验公式:n中列数：最大值和最小值的平均第51页，此课件共63页哦度量数据的离散度（1）n最常用度量：五数概括（基于四分位数）、中间四分位数区间和标准差n四分位数、孤立点和盒图q百分位数(percentile)：第k个百分位数是具有如下性质的值x：数据项的k%在x上或低于xq四分位数：Q1(25th percentile),Q3(75th percentile)q中间四分位数区间(IQR)：IQR=Q3 Q1 q对倾斜分布的描述，除了IQR还常需两个四分位数Q1和Q3，以及中位数M，一个识别孤立点的常用规则

31、是：挑出落在至少高于第三个四分位数或低于第一个四分位数 1.5IQR处的值第52页，此课件共63页哦度量数据的离散度（2）n五数概括:min,Q1,M,Q3,maxn盒图：数据分布的一种直观表示n方差和标准差q方差s2：n个观测之x1,x2.xn的方差是q标准差s是方差s2的平方根ns是关于平均值的离散的度量，因此仅当选平均值做中心度量时使用n所有观测值相同则 s0，否则 s0n方差和标准差都是代数度量第53页，此课件共63页哦盒图示例n盒图：数据分布的一种直观表示，在盒图中：q端点在四分位数上，使得盒图的长度是IQRq中位数M用盒内的线标记q胡须延伸到最大最小观测值n该盒图为在给定时间段在A

32、llElectronics的4个分店销售的商品单价的盒图n分店1q中位数$80qQ1:$60qQ3:$100第54页，此课件共63页哦基本统计类描述的图形显示直方图n常用的显示数据汇总和分布的方法：q直方图、分位数图、q-q图、散布图和局部回归曲线n直方图q一种单变量图形方法q由一组矩形组成，这些矩形反映类在给定数据中出现的技术或频率第55页，此课件共63页哦分位数图n显示所有的数据，允许用户评估总的情况和不寻常情况的出现n绘出了分位数信息q设xi是递增排序的数据，则每个xi都有相对应的fi，指出大约有100 fi 的数据小于等于xi第56页，此课件共63页哦分位数分位数图（q-q图）n对着另

33、一个单变量的分位数，绘制一个单变量分布的分位数n允许用户观察是不是有从一个分布到另外一个分布的迁移第57页，此课件共63页哦散布图n确定两个量化的变量之间看上去是否有联系、模式或者趋势n散布图中的每个值都被视作代数坐标对，作为一个点画在平面上n易于观察双变量数据在平面上的分布第58页，此课件共63页哦Loess曲线nLoess曲线为散布图添加一条平滑的曲线，以便更好的观察两个变量间的依赖模式nLoess(local regression)意指“局部回归”，为了拟合Loess曲线，需要两个参数：平滑参数，被回归拟合的多项式的阶 第59页，此课件共63页哦概念描述：面向数据库的方法与机器学习的方法

34、比较n面向数据库的方法：面向大型数据库的概念描述的概化方法q使用基于数据立方体的方法q面向属性的归纳的方法n机器学习：使用示例学习的范例，在概念集或标定训练样本集上进行，通过检验这些集合在学习中导出关于描述类的假定第60页，此课件共63页哦面向数据库的方法与机器学习的方法的差异(1)n所用的基本原理不同，关于概念描述的基本假定也不同q在示例学习的范例中，分析样本划分为两个集合：正样本和负样本，正样本用于概化，负样本用于特化，最后的概念描述会覆盖所有正样本而不覆盖任何负样本q在面向数据库的方法中，只存在正样本，因此大部分面向数据库的方法都是基于概化的（使用该方法时，下钻操作用于回溯到前一状态的概化过程）第61页，此课件共63页哦面向数据库的方法与机器学习的方法的差异(2)n训练样本集大小上的差异q机器学习训练样本集小，容易找到覆盖所有正样本而不覆盖任何负样本的描述q面向数据库的方法通常面对大量数据，因此概念描述的目标是尽量的涵盖正面数据（概率分布）n所使用的概化方法不同q机器学习方法是逐个元组的进行概化q面向数据库的方法是逐个属性（或维）的进行概化，从而使得数据挖掘的过程能够与面向集合的数据库操作集成第62页，此课件共63页哦感感谢谢大大家家观观看看第63页，此课件共63页哦