数据仓储与数据挖掘讲义 第5章：数据立方体计算与数据泛化

第五章数据立方体计算与数据泛化5.1数据立方体计算的有效方法方体计算的有效方法基于ROLAP的方体算法(Agarwaletal’96)基于数组的算法(MOLAP)(Zhaoetal’97)自底向上的计算方法(Beyer&Ramarkrishnan’99)H-cubing技术(Han,Pei,Dong&Wang:SIGMOD’01)基于ROLAP的方法将排序、散列(hashing)和分组操作应用于维的属性，以便对相关元组重新排序和聚类在某些子聚集上分组，作为“部分分组步骤”。可以由以前计算的聚集计算新的聚集，而不必有基本事实表计算方体计算的多路数组聚集方法(p105)将数组分成块（chunk,一个可以装入内存的小子方）压缩的稀疏数组寻址：(chunk_id,offset)通过访问立方体单元，计算聚集。可以优化访问单元组的次序，使得每个单元被访问的次数最小化，从而减少内存访问和磁盘I/O的开销。A(month)B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)B(city)442856402452362060哪个是多路数组聚集的最佳遍历次序？方体计算的多路数组聚集方法(2)A(month)40B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)4000442856402452362060B(city)400ABBCAC方体计算的多路数组聚集方法(3)AB29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C442856402452362060B方体计算的多路数组聚集方法(4)方法：各平面要按他们大小的升序排列进行排序和计算详见书P106例4.4思想：将最小的平面放在内存中，对最大的平面每次只是取并计算一块这种方法的限制：只有在维数比较小的情况下，效果才比较理想(要计算的立方体随维数指数增长)如果维的数目比较多，可以考虑使用“自底向上的计算”或者时“冰山方体”计算结论:对于方体计算的多路数组聚集方法，应该将最小的平面放在内存中，对最大的平面每次只是取并计算一块。图5-3要求：内存＞最小平面所需存储空间(40*400)＋次小平面一行所需存储空间(40*1000)＋最大平面一个单元所需存储空间(100*1000)当内存空间不够时,则需要多次扫描数据库．冰山查询:仅对立方体中满足每个单元的聚集值大于某个最小支持度或者阈值的分划进行计算.*索引的使用:加快检索存取速度.基于假设驱动的探查方法explorationbyuser,hugesearchspace基于发现驱动的探查方法(Sarawagi,etal.’98)EffectivenavigationoflargeOLAPdatacubespre-computemeasuresindicatingexceptions,guideuserinthedataanalysis,atalllevelsofaggregationVisualcuessuchasbackgroundcolorareusedtoreflectthedegreeofexceptionofeachcell5.2数据立方体中的数据分析探查方法一、数据立方体中基于发现驱动的探查方法Exception:significantlydifferentfromthevalueanticipated,basedonastatisticalmodel异常的种类及其描述KindsofExceptionsandtheirComputationInExp:surprisebeneaththecellPathExp:surprisebeneathcellforeachdrill-downpathSelfExp:surpriseofcellrelativetoothercellsatsamelevelofaggregation因此可以在数据立方体中构建相应的模型，通过计算，三个异常指示器SelfExp,InExp,andPathExp的值来指示可能存在的数据异常，指导用户进行数据探察和分析。Exceptionthemselvescanbestored,indexedandretrievedlikeprecomputedaggregates2002200320042005200620072008…08……18…SelfExpPathExpInExpExamples:Discovery-DrivenDataCubes提供了对数据分析中潜在问题的导航作用从顶向下的计算策略，而MIS中一般是自底向上计算数据的泛化与细化（各个层次的聚集）特点：5.3面向属性的归纳：另一种数据概化一、什么是数据概化？数据库中的数据和对象通常包含原始概念层的细节信息，数据概化就是将数据库中的跟任务相关的数据集从较低的概念层抽象到较高的概念层的过程。用较高层次的概念来代替较低层次的概念例如:用老、中、青分别代替（20-35，36-50，51-70）的年龄区间值。用省代替地市级的概念等和概念描述方法描述性挖掘数据挖掘预测性挖掘概念描述特征化比较数据挖掘的分类什么是概念描述？描述性挖掘VS.预测性挖掘描述性挖掘：以简洁概要的方式描述数据，并提供数据的有趣的一般性质。预测性数据挖掘：通过分析数据建立一个或一组模型，并试图预测新数据集的行为。概念描述：为数据的特征化和比较产生描述（当所描述的概念所指的是一类对象时，也称为类描述）特征化：提供给定数据集的简洁汇总。例如按专业的成绩分布表区分：提供两个或多个数据集的比较描述。如男生与女生的对比。二、数据特征化：面向属性的归纳（AOI）Attribute-orientedinduction,AOI(KDD`89Workshop)受数据类型和度量类型的约束比较少面向属性归纳的基本思想：使用关系数据库查询收集任务相关的数据通过考察任务相关数据中每个属性的不同值的个数进行概化，方法是属性删除或者是属性概化通过合并相等的，概化的广义元组，并累计他们对应的计数值进行聚集操作通过与用户交互，将广义关系以图表或规则等形式，提交给用户面向属性的归纳的基本步骤数据聚焦，获得初始工作关系进行面向属性的归纳基本操作是数据概化，对有大量不同值的属性，进行进一步概化属性删除属性概化属性概化控制：控制概化过程，确定有多少不同的值才算是有大量不同值的属性属性概化临界值控制：如果一个属性的不同值个数大于属性概化阈值(属性不同值个数的概化临界值），则应当进一步删除或者概化该属性。概化(广义）关系临界值控制：如果概化关系中不同元组的个数超过该阈值，则应当进一步概化。1、数据聚焦目的是获得跟任务相关的数据集，包括属性或维，在DMQL中他们由inrelevanceto子句表示。示例-----例5.20:（p129)DMQL:描述Big-University数据库中研究生的一般特征useBig_University_DBminecharacteristicsas“Science_Students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”数据聚焦时的困难用户在指定相关的数据集方面存在困难，遗漏在描述中可能起作用的属性用户可能引进太多的属性将数据挖掘查询转换为关系查询Selectname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin{“Msc”,“MA”,“MBA”,“PhD”}2、数据概化属性删除的适用规则：对初始工作关系中具有大量不同值的属性，符合以下情况，应使用属性删除：在此属性上没有概化操作符（比如该属性没有定义相关的概念分层）该属性的较高层概念用其他属性表示如:name：要被删除的属性，为什么？phone#：要被删除的属性属性概化控制属性概化的使用规则：如果初始工作关系中的某个属性具有大量不同值，且该属性上存在概化操作符，则使用该概化操作符对该属性进行数据概化操作。什么是“具有大量的不同值”？要将属性概化到多高的抽象层？属性概化控制的两种常用方法：属性概化临界值控制：对所有属性设置一个概化临界值或者是对每个属性都分别设置一个临界值（一般为2到8）两种技术的顺序使用：使用属性概化临界值控制来概化每个属性，然后使用关系临界值控制进一步压缩概化的关系。概化关系临界值控制：为概化关系设置一个临界值，确定概化后的关系中，不同元组的个数的最大值。（通常为10到30，应该允许在实际应用中进行调整）三、面向属性的归纳——示例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…RemovedRetainedSci,Eng,BusCountryAgerangeCityRemovedExcl,VG,..1、初始工作关系挖掘Big-University数据库中研究生的一般特征2、数据概化name：要被删除的属性，为什么？gender：保留该属性，不概化major：根据概念分层向上攀升{文，理，工…}birth_place：根据概念分层location向上攀升birth_date：概化为age，再概化为age_rangeresidence：根据概念分层location向上攀升phone#：删除属性gpa：根据GPA的分级作为概念分层3、得到概化关系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…RemovedRetainedSci,Eng,BusCountryAgerangeCityRemovedExcl,VG,..GenderMajorBirth_regionAge_rangeResidenceGPACountMScienceCanada20-25RichmondVery-good16FScienceForeign25-30BurnabyExcellent22…………………Birth_RegionGenderCanadaForeignTotalM161430F102232Total263662主概化关系初始工作关系四、面向属性的归纳算法输入：1.DB;2.数据挖掘查询DMQuery;3.属性列表;4.属性的概念分层;5.属性的概化临界值；输出：主概化关系P算法描述：1.Wget_task_relevant_d