《数据挖掘课件第四章.ppt》由会员分享，可在线阅读，更多相关《数据挖掘课件第四章.ppt（84页珍藏版）》请在三一办公上搜索。
1、2023/10/14,1,第四章 数据立方体计算与数据泛化,数据立方体计算的有效方法多维数据库资料的探测与发现基于属性的规约另外一种数据泛化方法,2023/10/14,2,数据立方体计算的有效方法,数据立方体计算的优化技巧(Agarwal et al.96)计算完全/冰山立方体的3种方法自顶向下:多路数组聚集(Zhao,Deshpande&Naughton,SIGMOD97)自底向上方自底向上计算:BUC(Beyer&Ramarkrishnan,SIGMOD99)H-cubing技术(Han,Pei,Dong&Wang:SIGMOD01)自顶向下与自底向上相结合:Star-cubing 算法(
2、Xin,Han,Li&Wah:VLDB03)高维 OLAP:A Minimal Cubing Approach(Li,et al.VLDB04)可以计算的数据立方体类型:部分立方体，闭立方体，近似立方体等,2023/10/14,3,优化技巧(Agarwal et al.VLDB96),应当对维属性进行排序，hash，分组操作，以便对相关元组重新定序和聚类由先前计算的较低层聚集计算较高层计算，而不是由基本事实表计算最小子女:当存在多个子女立方体时，由最小的、先前计算的子女方体计算父母方体。缓存中间结果:缓存中间结果可以减少开销很大的磁盘I/O操作平摊扫描:同时尽可能多的计算方体，缓冲磁盘读共享排
3、序：当使用基于排序的方法时，在多个方体之间共享排序开销共享划分:当使用基于散列的方法时，在多个方体之间分享划分开销,2023/10/14,4,多路数组聚集,基于自底向上的算法使用多维块没有原则比较作为指导同时聚集多个维中间聚集的结果在聚集祖先方体的时候会再次被用到不能用 Apriori 算法剪枝:不满足冰山优化条件,2023/10/14,5,数据立方体计算的多路数组聚集（MOLAP）,将数组分块(分成足够小的字块，使其大小能够放入立方体计算时可用的内存).压缩稀疏数组结构:(chunk_id,offset)通过访问立方体单元计算聚集，每个单元必须重复访问的次数最小化，从而减少内存访问和存储开销
4、。,多路聚集的最佳访问次序？,2023/10/14,6,数据立方体计算的多路数组聚集,B,2023/10/14,7,数据立方体计算的多路数组聚集,A,B,29,30,31,32,1,2,3,4,5,9,13,14,15,16,64,63,62,61,48,47,46,45,a1,a0,c3,c2,c1,c 0,b3,b2,b1,b0,a2,a3,C,44,28,56,40,24,52,36,20,60,B,2023/10/14,8,数据立方体计算的多路数组聚集,方法：计算维值并按升序排列思想：将最小的维值存入内存，每次只取一个最大的维值来进行计算方法的缺陷：该方法只在维数较小的时候能够得到好的
5、计算结果当维数很高时可以使用自顶向下的算法或冰山立方体计算方法,2023/10/14,9,自底向上计算(BUC),BUC(Beyer&Ramakrishnan,SIGMOD99)自底向上立方体计算(注：实际上是自顶向下)将维度划分，以便使用冰山剪枝法如果划分不满足最小支持度，则它的子孙可以被剪枝掉如果minsup=1 计算完全立方体不能同时聚集,2023/10/14,10,BUC:划分,通常，无法将全部的数据放入主存将不同的值进行分类，划分成块然后放入主存继续处理优化划分外部排序，散列计数分类将维值排序，以便剪枝次序，歪斜压缩副本不能整体聚集,2023/10/14,11,H-Cubing:使用
6、 H-Tree 结构,自底向上计算使用 H-tree结构如果当前的H-tree计算不满足最小支持度，则不在进行下去不能同时聚集,2023/10/14,12,H-tree:A Prefix Hyper-tree,root,edu,hhd,bus,Jan,Mar,Jan,Feb,Tor,Van,Tor,Mon,Headertable,2023/10/14,13,H-Cubing:用city属性计算方体,root,Edu.,Hhd.,Bus.,Jan.,Mar.,Jan.,Feb.,Tor.,Van.,Tor.,Mon.,HeaderTableHTor,From(*,*,Tor)to(*,Jan,T
7、or),2023/10/14,14,使用月份属性计算方体,root,Edu.,Hhd.,Bus.,Jan.,Mar.,Jan.,Feb.,Tor.,Van.,Tor.,Mont.,上卷信息使用月份属性计算方体而不是用城市属性,Top-k OK mark:if Q.I.in a child passes top-k avg threshold,so does its parents.No binning is needed!,2023/10/14,15,Computing Cells Involving Only Cust_grp,root,edu,hhd,bus,Jan,Mar,Jan,Feb
8、,Tor,Van,Tor,Mon,Check header table directly,2023/10/14,16,Star-Cubing,结合了自顶向下和自底向上的算法使用共享维例如维A是维ACD和AD的共享维ABD/AB意思是ABD有共享维AB允许共享计算e.g.,cuboid AB is computed simultaneously as ABD采用自顶向下方式聚集，在子层采用自底向上方法，这样可以用 Apriori 剪枝共享维采用自底向上方式增长,2023/10/14,17,共享维的冰山剪枝,共享维的反单调性如果度量是反单调的，若共享维的聚集值不满足冰山条件，则眼该共享维向下的所有
9、单元也不可能满足冰山条件直观的:如果我们在计算实际的立方体之前 计算共享维，那么我们就可以用共享维来进行Apriori剪枝问题：当多维同时聚集是如何剪枝？,2023/10/14,18,Cell Trees,使用类似于H-tree的树结构来代替立方体合并公共前缀以节省存储空间将计数值存在结点中一条从跟到树叶节点的路径代表一个元组,2023/10/14,19,星属性和星结点,直观的:如果单个维在属性值p上的聚集不满足冰山条件，则在冰山立方体计算中识别这样的结点没有意义如：b2,b3,b4,c1,c2,c4,d1,d2,d3 解决方法:将这样的属性用*代替.这样的属性成为星属性，相应的结点成为星结点
10、。,2023/10/14,20,例：压缩星结点,假设 minsup=2执行一维聚集后，将计数小于2的属性用*来代替然后将所有的*压缩在一起将这些属性用星属性替代后，重新生成表关于冰山计算，这个表并没有丢失太多原表的信息,2023/10/14,21,星树,给定新的被压缩的表后，就可以构造相应的cell树了，我们称这个树为星树可以将星表放在星树的旁边以便查找星属性星树是对原cell树的无损压缩,2023/10/14,22,Star-Cubing 算法格子 Tree的深度优先搜索,2023/10/14,23,多路聚集,2023/10/14,24,Star-Cubing 算法对星树深度优先搜索,202
11、3/10/14,25,多路星树聚集,从基本星树的根节点开始深度优先遍历DFS中的每个新节点，构造相应的星树，该星树由当前的树派生，并与整个的遍历次序有关 例：在基本星树中，当DFS到达a1结点则 ACD/A 树被创建当DFS到达b*则创建 ABD/AD 树基本数中的计数要存放在新树种,2023/10/14,26,多路聚集(2),当DFS到达叶节点，则回溯在回溯的每个分支，输出相应的计数值，销毁该树，几本书中的节点也被销毁例：当遍历从d*回到c*则输出 a1b*c*/a1b*c*树，并将其销毁当遍历从c*回到b*则输出a1b*D/a1b*树，并将其销毁当在b*结点时则跳转到b1，重复以上过程,2
12、023/10/14,27,维灾难,前面提到的方法中没有能够处理高维数据的!含有600k个元组的数据库，每一维的基数是zipf of 2.？,2023/10/14,28,高维 OLAP产生的动机,现在的数据立方体计算的方法面临的挑战:维灾难问题冰山立方体和立方体压缩只是延迟了不可避免的数据爆炸完全物化:对磁盘的访问仍然是严重超负荷的。需要用到高维OLAP的应用科学与工程分析生物数据分析:成千上万的基因 统计调查：数以百计的变量,2023/10/14,29,快速高维OLAP,直观的:大部分OLAP操作一次只对少数维执行半连机计算模型给定的高维数据集，将维划分成互不相交将每个片段转换成相应的倒排索引
13、结构，然后构造外壳片段立方体联机动态组装和计算所需要的数据立方体的方体单元,2023/10/14,30,算法的性质,垂直的划分数据将高维立方体转化为一组低维立方体联机重构原始高维空间无损压缩可以权衡预计算的数目与联机计算的速度,2023/10/14,31,例,用计数作为聚集函数将5维空间分为两个壳片段:(A,B,C)和(D,E),2023/10/14,32,1-D 倒排序索引,构造传统的倒排索引或 RID表,2023/10/14,33,立方体壳片段,泛化一维倒排索引,2023/10/14,34,立方体壳片段(2),计算数据立方体 ABC和 DE 中的所有方体，并记录倒排索引例如，立方体壳片段A
14、BC包含7个立方体:A,B,CAB,AC,BCABC完成了脱机计算过程,2023/10/14,35,立方体壳片段(3),给定一个含有T个元组，D维，长度为F的片段，则需要的空间为：因为 F 5,the growth is sub-linear.,2023/10/14,36,立方体壳片段(4),壳片段不一定非要不相交为了得到联机的最大性能，允许片段进行任意组合已知的常用组合应该放在一起.为了平衡脱机和联机计算可以调整壳片段的长度,2023/10/14,37,ID_Measure 表,如果冰山条件中的度量不是count而是其他的度量，则将，ID_measure表的存储于壳片段分开,2023/10/
15、14,38,Frag-Shells算法,将属性(A1,An)分成k个片段(P1,Pk).扫描基本表一次并进行下列操作 将 插入 ID_measure表中.对任意维Ai的任意属性值 ai 建立倒排索引项 对每个划分片段 Pi 通过自底向上模式与tid-list取交建立局部片段立方体Si,2023/10/14,39,Frag-Shells(2),ABCCube,DEFCube,D Cuboid,EF Cuboid,DE Cuboid,Dimensions,2023/10/14,40,联机查询计算,查询的通常形式为每个 ai 有 3 个可能的值例示值聚集函数*查询谁？例如,返回一个两维的数据立方体,
16、2023/10/14,41,联机查询计算(2),给定片段立方体执行如下操作将查询分成片段，类似于壳从片段理立方体中未每个片段取出相应的TID表将片段与相关的TID表取交并构造基本例示表根据基本表用任意一种算法计算数据立方体,2023/10/14,42,联机查询计算(3),OnlineCube,Instantiated Base Table,2023/10/14,43,Experiment:Size vs.Dimensionality(50 and 100 cardinality),(50-C):106 tuples,0 skew,50 cardinality,fragment size 3.(
17、100-C):106 tuples,2 skew,100 cardinality,fragment size 2.,2023/10/14,44,Experiment:Size vs.Shell-Fragment Size,(50-D):106 tuples,50 dimensions,0 skew,50 cardinality.(100-D):106 tuples,100 dimensions,2 skew,25 cardinality.,2023/10/14,45,Experiment:Run-time vs.Shell-Fragment Size,106 tuples,20 dimensi
18、ons,10 cardinality,skew 1,fragment size 3,3 instantiated dimensions.,2023/10/14,46,Experiment:I/O vs.Shell-Fragment Size,(10-D):106 tuples,10 dimensions,10 cardinalty,0 skew,4 inst.,4 query.(20-D):106 tuples,20 dimensions,10 cardinalty,1 skew,3 inst.,4 query.,2023/10/14,47,Experiment:I/O vs.#of Inst
19、antiated Dimensions,106 tuples,10 dimensions,10 cardinalty,0 skew,fragment size 1,7 total relevant dimensions.,2023/10/14,48,使用现实世界的数据的实验,UCI Forest CoverType data set54维,581K 个元组壳片段的长度为2,计算用了33s，325MB3-D subquery with 1 instantiate D:85ms1.4 sec.Longitudinal Study of Vocational Rehab.Data24 维,8818个
20、元组壳片段长度 3 计算用了 0.9 s，60MB5-D query with 0 instantiated D:227ms2.6 sec.,2023/10/14,49,与相关工作的比较,Harinarayan96用对高维数据的进一步聚集计算低维数据立方体，与我们方法的指导思想相反倒排结构 Witten99关注一维数据或是没有聚集的多维数据.Tree-stripping Berchtold00使用了类似的对数据库的垂直划分但是没有聚集,2023/10/14,50,考虑进一步实施,增量更新:在倒排表中增加更多的TID 将 加入ID_measure表增加新的维维新的倒排表增加新的片段位图索引进一步
21、改善空间的利用和速度压缩倒排索引以 d-gaps存储探索更多的IR压缩方法,2023/10/14,51,第四章 数据立方体计算与数据泛化,数据立方体计算的有效方法多维数据库资料的探测与发现基于属性的规约另外一种数据泛化方法,2023/10/14,52,计算具有复杂冰山条件的立方体,多数计算算法都不能计算具有复杂冰山条件的立方体例：CREATE CUBE Sales_Iceberg ASSELECT month,city,cust_grp,AVG(price),COUNT(*)FROM Sales_InforCUBEBY month,city,cust_grpHAVING AVG(price)=
22、800 ANDCOUNT(*)=50需要研究如何将约束放入立方体计算过程中,2023/10/14,53,具有复杂冰山条件的立方体,反单调:如果一个过程不满足条件，继续进行会导致失败用avg查询，avg不是反单调的!(Mar,*,*,600,1800)不满足 HAVING 子句(Mar,*,Bus,1300,360)满足了该限制,CREATE CUBE Sales_Iceberg ASSELECT month,city,cust_grp,AVG(price),COUNT(*)FROM Sales_InforCUBEBY month,city,cust_grpHAVING AVG(price)=8
23、00 ANDCOUNT(*)=50,2023/10/14,54,从均值到Top-k均值,令(*,Van,*)包含1,000条记录Avg(price)是这1000条记录的平均销售价值Avg50(price)是价格最高的50条记录的平均销售价格 Top-k 平均值是反单调的Van的最高价格的50条记录的 avg(price)=800 Van的二月份的最高价格的50条记录的 avg(price)一定不超过800,2023/10/14,55,Binning for Top-k Average,计算top-k avg的开销与k的大小有关Binning ideaAvg50(c)=800压缩大值:使用sum
24、和count来概括度量不小于800的记录如果count=800,不需要检验“small”的记录小值装箱:一组箱子一个箱子可能覆盖区域如600800,400600等给每个箱子记录sum和count,2023/10/14,56,计算 top-k 均值的近似值,Top 50,Approximate avg50()=(28000+10600+600*15)/50=952,假设(*,Van,*),我们有,The cell may pass the HAVING clause,2023/10/14,57,Weakened Conditions Facilitate Pushing,积累单元的数量信息，以有
25、效的计算普通冰山立方体三部分:sum,count,top-k bins用top-k bins来估计/剪枝后代使用 sum 和 count来巩固当前结点,strongest,weakest,2023/10/14,58,使用其他负责的方法来计算冰山立方体,计算其他复杂的度量Key point:找到一个函数肯更是弱的但必须是反单调的例如Avg()v:avgk(c)v(bottom-k avg)Avg()v only(no count):max(price)v Sum(profit)(profit can be negative):p_sum(c)v if p_count(c)k;or otherwi
26、se,sumk(c)v 其他:多条件的结合,2023/10/14,59,压缩立方体:浓缩或闭立方体,W.Wang,H.Lu,J.Feng,J.X.Yu,Condensed Cube:An Effective Approach to Reducing Data Cube Size,ICDE02.冰山立方体不能解决所有的问题假设有100维，只有一个基本单元的计数为10，计数大于等于10的单元有多少？浓缩立方体只需要保存一个单元(a1,a2,a100,10),他代表了所有相关的单元集合Adv.在没有压缩的情况下进行完全预计算最小浓缩立方体的有效计算闭立方体 Dong Xin,Jiawei Han,Z
27、heng Shao,and Hongyan Liu,“C-Cubing:使用基于聚集的核算的闭立方体计算的有效方法”,ICDE06.,2023/10/14,60,第四章 数据立方体计算与数据泛化,数据立方体计算的有效方法多维数据库资料的探测与发现基于属性的规约另外一种数据泛化方法,2023/10/14,61,数据立方体的发现驱动的探查,Hypothesis-drivenexploration by user,huge search space发现驱动(Sarawagi,et al.98)智能地探查数据立方体的巨大聚集空间与计算的度量指出数据异常，在所有的聚集级知道用户的数据分析过程异常:基于某
28、种统计模型，显著的不同于期望值的数据立方体单元值可视提示（如背景色）用于反映每个单元的异常程度,2023/10/14,62,异常分类及他们的计算,参数SelfExp:指示相对于同一聚集级的其他单元的单元值奇异程度InExp:只是该单元执行某处的奇异程度，如果我们由它下钻的话PathExp:只是由该单元的每条下钻路径的奇异程度计数异常指示器可以与立方体重构交迭进行异常本身可以想与计算聚集一样被存储，索引，取出。,2023/10/14,63,Examples:发现驱动立方体,2023/10/14,64,在多粒度的复杂聚集：多特征立方体,多特征立方体(Ross,et al.1998):计算设计多粒度
29、上多个依赖聚集的复杂查询例：按 item,region,month的所有子集分组,找出1997年每组的最高价格，并找出所有最高价格的元组的总销售额select item,region,month,max(price),sum(R.sales)from purchaseswhere year=1997cube by item,region,month:Rsuch that R.price=max(price)继续上面的例子，在最高价格的元组中，找出最小火最大的商品货架寿命，及最小货架寿命元组的总销售额部分,2023/10/14,65,数据立方体梯度(Cubegrade),许多数据立方体应用需要分
30、析多维空间中的复杂度量变化查询：在房地产中，温哥华地区00年的平均房价照99年有何变化回答是：销售给West的平均房价下降了20%，销售给Metrotown 的上升了10%立方体梯度问题由Imielinski等提出.属性变化 度量变化下钻，上卷，突变,2023/10/14,66,被约束的多维梯度分析,比相关的规则更有意义用用户指定的度量获取变化挑战存在大量平凡单元“显著性约束”剪裁掉大量的平凡单元大量的单元“探测约束”选择单元子集作为考察的起点直关心感兴趣的变化“梯度约束”获取重要的变化,2023/10/14,67,被约束的多维梯度挖掘,显著性约束 Csig:(cnt100)探查约束 Cprb
31、:(city=“Van”,cust_grp=“busi”,prod_grp=“*”)梯度约束 Cgrad(cg,cp):(avg_price(cg)/avg_price(cp)1.3),Base cell,Aggregated cell,Siblings,Ancestor,Probe cell:satisfied Cprb,(c4,c2)satisfies Cgrad!,2023/10/14,68,有效的数据立方体梯度计算,使用 Csig和 Cprb计算探查立方体探查单元集合P可能很小使用P和约束来寻找梯度Pushing selection deeply对探测单元进行适合集合的处理冰山从低维向
32、高维增长在增长过程中动态的剪枝探查单元综合使用有效的冰山立方体计算方法,2023/10/14,69,第四章 数据立方体计算与数据泛化,数据立方体计算的有效方法多维数据库资料的探测与发现基于属性的规约另外一种数据泛化方法,2023/10/14,70,什么是概念描述?,描述与预测挖掘描述挖掘:用精确的，简洁的，概括的，有判断力的方式描述概念或任务相关的数据预测挖掘:基于数据及分析器结构模型并预测未知数据的发展趋势及性质概念描述:性质：对给定的数据对象进行精确地简洁的概要对照:提供两个或多个数据集的对照描述,2023/10/14,71,数据泛化和基于概要的描述,数据泛化通过将较低层的值用较高的概念置
33、换来汇总数据方法数据立方体方法(OLAP)基于属性规约的方法,1,2,3,4,5,Conceptual levels,2023/10/14,72,概念描述 vs.OLAP,相同点:数据泛化从多个概念层抽象数据交互演练，旋转。不同点:可以处理复杂类型数据的性质及其聚集Automated desired level allocation.当存在多个相关的维时维关联分析和分等级.精确地测定维和度量.解析描述:数据分布分析,2023/10/14,73,基于属性的规约,1989年提出(KDD 89 workshop)不局限于分类数据或特殊的度量方法如何执行的?使用关系数据库查询手机相关任务数据通过属性删
34、除或属性泛化来进行泛化聚集通过合并相等的广义元组，并累计他们对应的计数值进行与用户交互陈述,2023/10/14,74,属性规约的基本原则,数据聚焦:说明任务相关数据，包括属性及初始关系结果属性删除：如果初始工作关系的某个属性有大量不同的值，但是（1）对于该属性没有泛化操作符，或者（2）它的较高层概念用其他属性表示，则应当将该属性从工作关系中删除属性泛化:如果初始工作关系的某个属性有大量的不同的值，并且该属性存在泛化操作符的集合，则当选择一个泛化操作符并用于该属性 属性阈值控制:通常为 2-8广义关系阈值控制:控制最终的关系大小,2023/10/14,75,面向属性的规约:基本算法,Initi
35、alRel:关系查询，将任务相关数据收集到工作关系中.PreGen:分析每个属性的不同值的个数，确定每个属性的泛化方法:删除？或如何向高维泛化?PrimeGen:基于PreGen，进行泛化到恰当的层，构造prime泛化关系，累计计数.陈述:与用户交互：使用演练，旋转，映射到规则交叉表，可视化陈述。,2023/10/14,76,例：,DMQL:描述存放于Big-University数据库中的毕业生信息的基本特征use Big_University_DBmine characteristics as“Science_Students”in relevance to name,gender,majo
36、r,birth_place,birth_date,residence,phone#,gpafrom studentwhere status in“graduate”相应的SQL陈述:Select name,gender,major,birth_place,birth_date,residence,phone#,gpafrom studentwhere status in“Msc”,“MBA”,“PhD”,2023/10/14,77,类描述:An Example,Prime 泛化关系,初始表,2023/10/14,78,泛化结果的陈述,泛化关系:使用计数或其他的聚集度量泛化某些或者全部属性的关系
37、。交叉表:映射到交叉表的形式（类似于相依表）可视化技术:饼图,柱状图,曲线,立方体视图以及其他可视化形式.量化特征规则:将泛化结果映射到与其相关的量化信息特征规则,2023/10/14,79,挖掘类比较,对照:比较两个或多个类方法:将相关的数据划分成目标类和对比类 每个概念类应泛化到相同的概念层比较同意概念层上的元组对每个元组通过以下两种方式处理其分布在单个类中支持分布？support-distribution within single class比较类之间的分布突出具有强判别式特征的元组 相关分析:找出最能区别类的属性,2023/10/14,80,量化判别规则,Cj=目标类qa=覆盖目标类
38、的部分元组也可以覆盖对比类的部分元组d-weight在 0,1内量化判别规则记作：,2023/10/14,81,量化判别规则,量化判别规则其中 90/(90+210)=30%,广义元组研究生和本科生的计数分布,2023/10/14,82,类描述,量化特征规则必要条件量化判别规则充分条件量化描述条件充要条件,2023/10/14,83,量化描述规则,目标类 Europe的量化描述规则,交叉表，同时显示每个类相关联的t权和d权以及 AllElectronics 在1998年售出的电脑和电视的总数（单位：千）,2023/10/14,84,小结,数据立方体计算的有效方法多路数组聚集BUCH-cubingStar-cubing高维OLAP by minimal cubing数据立方体技术的进一步发展发现驱动立方体多特征立方体立方体梯度分析另外一种主要的方法：面向属性的规约,
