浙江大学王灿《数据挖掘》课程PPT_数据立方体

数据立方体计算与数据泛化（2）数据泛化数据泛化通过将相对层次较低的值（如属性age的数值）用较高层次的概念（如青年、中年、老年）置换来汇总数据主要方法：数据立方体（OLAP使用的方法）面向属性的归纳方法12345概念层(17,18,19,…,34,35,36,…,56,57,…)(青年,中年,老年)什么是概念描述？概念描述是一种数据泛化的形式。概念通常指数据的汇集如frequentbuyers，graduatestudents概念描述产生数据的特征化和比较描述，当所描述的概念所指的是对象类时，也称为类描述特征化：提供给定数据汇集的简洁汇总比较：提供两个或多个数据集的比较描述概念描述VS.OLAP相似处：数据泛化对数据的汇总在不同的抽象级别上进行呈现区别：复杂的数据类型和聚集OLAP中维和度量的数据类型都非常有限（非数值型的维和数值型的数据），表现为一种简单的数据分析模型概念描述可以处理复杂数据类型的属性及其聚集用户控制与自动处理OLAP是一个由用户控制的过程概念描述则表现为一个更加自动化的过程数据特征化的面向属性的归纳一种面向关系数据查询的、基于汇总的在线数据分析技术。受数据类型和度量类型的约束比较少面向属性归纳的基本思想：使用关系数据库查询收集任务相关的数据通过考察任务相关数据中每个属性的不同值的个数进行泛化，方法是属性删除或者是属性泛化通过合并相等的，泛化的广义元组，并累计他们对应的计数值进行聚集操作通过与用户交互，将广义关系以图表或规则等形式，提交给用户数据聚焦（1）目的是获得跟任务相关的数据集，包括属性或维，在DMQL中他们由inrelevanceto子句表示。示例：DMQL:描述Big-University数据库中研究生的一般特征useBig_University_DBminecharacteristicsas“Science_Students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”数据聚焦（2）上述DMQL查询转换为如下SQL查询，收集任务相关数据集Selectname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin{Msc,M.A.,MBA,PhD}初始工作关系NameGenderMajorBirth-PlaceBirth_dateResidencePhone#GPAJimWoodmanMCSVancouver,BC,Canada8-12-763511MainSt.,Richmond687-45983.67ScottLachanceMCSMontreal,Que,Canada28-7-753451stAve.,Richmond253-91063.70LauraLee…F…Physics…Seattle,WA,USA…25-8-70…125AustinAve.,Burnaby…420-5232…3.83…数据泛化数据泛化的两种常用方法：属性删除和属性泛化属性删除的适用规则：对初始工作关系中具有大量不同值的属性，符合以下情况，应使用属性删除：在此属性上没有泛化操作符（比如该属性没有定义相关的概念分层）该属性的较高层概念用其他属性表示属性泛化的使用规则：如果初始工作关系中的某个属性具有大量不同值，且该属性上存在泛化操作符，则使用该泛化操作符对该属性进行数据泛化操作属性泛化控制确定什么是“具有大量的不同值”，控制将属性泛化到多高的抽象层。属性泛化控制的两种常用方法：属性泛化阈值控制对所有属性设置一个泛化阈值或者是对每个属性都设置一个阈值（一般为2到8）泛化关系阈值控制为泛化关系设置一个阈值，确定泛化关系中，不同元组的个数的最大值。（通常为10到30，允许在实际应用中进行调整）两种技术的顺序使用：使用属性泛化阈值控制来泛化每个属性，然后使用关系阈值控制进一步压缩泛化的关系归纳过程中的聚集值计算在归纳过程中，需要在不同的抽象层得到数据的量化信息或统计信息聚集值计算过程聚集函数count与每个数据库元组相关联，初始工作关系的每个元组的值初始化为1通过属性删除和属性泛化，初始工作关系中的元组可能被泛化，导致相等的元组分组新的相等的元组分组的计数值设为初始工作关系中相应元组的计数和e.g.52个初始工作关系中的元组泛化为一个新的元组T，则T的计数设置为52还可以应用其他聚集函数，包括sum，avg等面向属性的归纳——示例挖掘BigUniversity数据库中研究生的一般特征name：删除属性（大量不同值，无泛化操作符）gender：保留该属性，不泛化major：根据概念分层向上攀升{文，理，工…}birth_place：根据概念分层location向上攀升birth_date：泛化为age，再泛化为age_rangeresidence：根据概念分层location向上攀升phone#：删除属性gpa：根据GPA的分级作为概念分层面向属性的归纳——示例NameGenderMajorBirth-PlaceBirth_dateResidencePhone#GPAJimWoodmanMCSVancouver,BC,Canada8-12-763511MainSt.,Richmond687-45983.67ScottLachanceMCSMontreal,Que,Canada28-7-753451stAve.,Richmond253-91063.70LauraLee…F…Physics…Seattle,WA,USA…25-8-70…125AustinAve.,Burnaby…420-5232…3.83…GenderMajorBirth_regionAge_rangeResidenceGPACountMScienceCanada20-25RichmondVery-good16FScienceForeign25-30BurnabyExcellent22…………………主泛化关系初始工作关系面向属性的归纳算法输入1.DB;2.数据挖掘查询DMQuery;3.属性列表;4.属性的概念分层;5.属性的泛化阈值；输出主泛化关系P算法描述：1.Wget_task_relevant_data(DMQuery,DB)2.prepare_for_generalization(W)1.扫描W，收集每个属性a的不同值2.对每个属性a，根据阈值确定是否删除，如果不删除，则计算其最小期望层次L，并确定映射对(v,v`)3.Pgeneralization(W)通过使用v`代替W中每个v，累计计数并计算所有聚集值，导出P1.每个泛化元组的插入或累积计数2.用数组表示P导出泛化的表示(1)泛化关系一部分或者所有属性得到泛化的关系，包含计数或其他度量值的聚集交叉表二维交叉表使用每行显示一个属性，使用每列显示另外一个属性将结果集映射到表中可视化工具：条形图、饼图、曲线和数据立方体浏览工具（用单元的大小代表计数，用单元亮度代表另外的度量）导出泛化的表示(2)量化规则使用t_weight表示主泛化关系中每个元组的典型性量化特征规则将泛化的结果映射到相应的量化特征规则中，比如：niiaqcountqcountweightt1)(/)(_]:[)(...]:[)()(_arg,mmllwtXconditionwtXconditionXclassettX%]45:[))((%]30:[))((%]25:[))(()(,tAmericanNorthXlocationtEuropeXlocationtAsiaXlocationcomputerXitemX量化特征规则中每个析取代表一个条件，一般，这些条件的析取形成目标类的必要条件，因为该条件是根据目标类的所有情况导出的。也就是说，目标类的所有元组必须满足该条件。然而，该规则可能不是目标类的充分条件，因为满足同一条件的元组可能属于其他类。E.g.挖掘类比较：区分不同的类类比较挖掘的目标是得到将目标类与对比类相区分的描述。目标类和对比类间必须具有可比性，即两者间要有相似的属性或维。本科生VS.研究生；studentVS.address很多应用于类特征化的技巧（处理单个类的多层数据的汇总和特征化）可以应用于类比较，比如属性泛化属性泛化必须在所有比较类上同步进行，将属性泛化到同一抽象层后进行比较。E.g.CityVScountry类比较的过程数据收集通过查询处理收集数据库中相关的数据，并将其划分为一个目标类和一个或多个对比类维相关分析如果存在较多的维，则应当对这些类进行维相关分析，仅选择高度相关的维进行进一步分析。（可以使用基于熵的度量）同步泛化同步的在目标类和对比类上进行泛化，泛化到维阈值控制的层，得到主目标类关系/方体和主对比类关系/方体导出比较的表示用可视化技术表达类比较描述，通常会包含“对比”度量，反映目标类与对比类间的比较(e.gcount%)类比较挖掘——示例（1）任务挖掘描述BigUniversity本科生和研究生的类比较任务的DMQL描述useBig_University_DBminecomparisonas“grad_vs_undergrad_students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafor“graduate_students”wherestatusin“graduate”versus“undergraduate_students”wherestatusin“undergraduate”analyzecount%fromstudent类比较挖掘——示例（2）进行类比较挖掘的输入：给定的属性：name,gender,major,birth_place,birth_date,residence,phone#andgpa在属性ai上定义的概念分层Gen(ai)在属性ai上定义的属性分析阈值Ui在属性ai上定义的属性泛化阈值Ti属性相关性阈值R类比较挖掘——示例（3）任务的处理过程数据收集DMQL查询转化为关系查询，得到初始目标类工作关系和初始对比类工作关系可以看成使构造数据立方体的过程引入一个新维status来标志目标类和对比类（graduate,undergraduate）其他属性形成剩余的维在两个数据类上进行维相关分析删除不相关或者使弱相关的维：name,gender,major,phone#类比较挖掘——示例（4）同步泛化在目标类和对比类上同步的进行泛化，将相关的维泛化到由维阈值控制的层，形成主目标类关系/方体和主对比类关系/方体导出比较的表示用表、图或规则等形式表达类比较描述的挖掘结果用户应该能够在主目标类关系/方体和主对比类关系/方体进行进一步的OLAP操作类比较挖掘——示例（5）MajorAge_rangeGpaCount%Science20-25Good5.53%Science25-30Good2.32%ScienceOver_30Very_good5.86%…………BusinessOver_30Excellent4.68%目标类的主泛化关系:研究生MajorAge_rangeGpaCount%Science15-20Fair5.53%Science15-20Good4.53%…………Science25-30Good5.02%…………BusinessOver_30Excellent0.68%对比类的主泛化关系:本科生类比较描述的量化判别规则表示（1）