《ch4 数据立方体计算与数据泛化》由会员分享，可在线阅读，更多相关《ch4 数据立方体计算与数据泛化（70页珍藏版）》请在金锄头文库上搜索。
1、2018/10/15,Data Mining: Concepts and Techniques,1,Data Mining: Concepts and Techniques Chapter 4 ,2018/10/15,Data Mining: Concepts and Techniques,2,第4章:数据立方体计算与数据泛化,数据立方体计算的有效方法 数据立方体和OLAP技术的进一步发展 面向属性的归纳 另一种数据泛化和概念描述方法,2018/10/15,Data Mining: Concepts and Techniques,3,数据立方体计算的有效方法,立方体物化（预计算）：完全立方体、
2、冰山立方体、闭立方体、外壳立方体 完全立方体/冰山立方体物化: 3种方法 Top-Down: 多路数组聚集 (Zhao, Deshpande & Naughton, SIGMOD97) Bottom-Up: BUC(自底向上构造) (Beyer & Ramarkrishnan, SIGMOD99) H-cubing技术 (Han, Pei, Dong & Wang: SIGMOD01) Top-Down和Bottom-Up结合: Star-cubing算法 (Xin, Han, Li & Wah: VLDB03) 高维OLAP计算外壳片段: 最小立方体计算方法 (Li, et al. VLDB
3、04) 例4-1例4-3,2018/10/15,Data Mining: Concepts and Techniques,4,立方体计算的一般策略,排序、散列、分组 对元组重新定序和聚类 同时聚集和缓存中间结果 由先前计算的较低层聚集计算较高层聚集 从缓存的中间结果同时聚集计算 当存在多个子女方体时，由最小的子女聚集 由最小的、先前计算的子女方体计算父母方体 使用Apriori剪枝方法有效计算冰山立方体 若给定的单元不满足最小支持度，则该后代也不满足最小支持度 显著降低冰山立方体的计算量,2018/10/15,Data Mining: Concepts and Techniques,5,完全立
4、方体计算的多路数组聚集(1),基于数组的“bottom-up”算法 使用多维块 使用数组直接寻址的典型的MOLAP方法 同时对多个维计算聚集 中间的聚集值可用于后继方体的计算 不能利用Apriori 剪枝: 无冰山优化,2018/10/15,Data Mining: Concepts and Techniques,6,完全立方体计算的多路数组聚集(2),将数组分成块。块（chunk）是一个子方，分块（chunking）是一种将n维数组划分成小的n维块的方法，每个块作为一个对象存放在磁盘上 通过访问立方体单元，计算聚集。通过优化访问单元的次序，使得每个单元必须重复访问的次数最小化，以减少存储访问
5、开销和存储开销,多路聚集最好的遍历顺序是什么？,2018/10/15,Data Mining: Concepts and Techniques,7,完全立方体计算的多路数组聚集(3),B,2018/10/15,Data Mining: Concepts and Techniques,8,完全立方体计算的多路数组聚集(4),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,2018/1
6、0/15,Data Mining: Concepts and Techniques,9,完全立方体计算的多路数组聚集(5),方法: 将3-D数组划分为小的、基于内存的块。升序扫描各块。 See the details of Example 4-4 (pp. 106-108) 思路: 将最小2-D平面保存到内存中，最大2-D平面一次只读取并计算一次 不同的块扫描次序和方体计算对整个数据立方体的计算效率有影响 局限性: 仅对维数相对较少的数据立方体成立，因为计算的方体个数随维指数增长，为避免维增长灾难： 冰山方(iceberg cube)计算方法：仅存放这样的方体分划中每个单元的聚集值大于某个最小
7、支持度或阈值,2018/10/15,Data Mining: Concepts and Techniques,10,BUC：从顶点方体向下计算冰山方体,Bottom-Up cube Construction 自底向上构造？ 可利用Apriori性质进行剪枝 对维划分，然后利用冰山剪枝 如果划分不满足最小支持度 min_sup, 则被剪枝 如果minsup = 1，则计算完全立方体 不同时聚集 BUC算法：P109,2018/10/15,Data Mining: Concepts and Techniques,11,BUC: 划分,例4-5 冰上立方体的BUC构造 通常不会将整个数据集载入内存
8、排序划分为块 优化： 划分 External Sorting, Hashing, Counting Sort 对维排序（基数、倾斜度），鼓励剪枝 以基数递减排序维 首先处理左右区分能力的维：基数越高，划分越多，为BUC剪枝提供更大的机会 维约均匀（具有较小的倾斜），对剪枝越好 分担划分开销 不在父母与子女的分组之间分享聚集计算,2018/10/15,Data Mining: Concepts and Techniques,12,Star-Cubing: 使用动态星形树结构计算冰山立方体,集成自顶向下和自底向上立方体计算，并利用多维聚集（类似于多路聚集）和类Apriori剪枝（类似于BUC） 利
9、用共享维的概念 E.g., ACD和AD具有共享维A ABD/AB 意味着方体 ABD具有共享维AB 共享维的引入有利于共享的计算 e.g., 方体AB与方体ABD同时计算 对全局计算，采用bottom-up次序；子层，采用基于top-down ，采用Apriori 剪枝 共享维采用bottom-up模式,2018/10/15,Data Mining: Concepts and Techniques,13,共享维的冰山剪枝,共享维的反单调特性 如果冰山立方体的度量是反单调的，即共享维的聚集不满足冰山条件，则沿该共享维向下的所有单元也不满足冰山条件 这样的单元和所有后代允许类Apriori剪枝
10、如果共享维上的聚集值不满足冰山条件，则后代单元也不可能满足 例4-6 剪枝共享维,2018/10/15,Data Mining: Concepts and Techniques,14,方体树,使用树表示个体方体 合并公共前缀，节省内存并允许聚集内部节点的值 节点具有聚集(计数)值 遍历树(深度优先)以检索特定的元组或节点,2018/10/15,Data Mining: Concepts and Techniques,15,星属性、星节点、星树,如果单个维在属性值p上的聚集不满足冰山条件，则在冰山立方体计算中识别这样的节点没有意义 E.g., b2, b3, b4, c1, c2, c4, d1
11、, d2, d3 这样的属性用 *替换，称为星属性(star attribute)，相应的节点称为星节点(star node)，使用星节点压缩的方体树称为星树(star tree),2018/10/15,Data Mining: Concepts and Techniques,16,星树构造实例（例4-7）,假定冰上条件minsup = 2 执行一维聚集。将 count 2的节点的属性值替换为*成为星节点。压缩（规约）星节点 星表中只显示星节点 通过压缩星节点，星树提供了原始数据的无损压缩,2018/10/15,Data Mining: Concepts and Techniques,17,星
12、树,使用规约的基本表构造方体树，称为星树 为了识别哪些节点是星节点，为每棵星树构造一个星表,2018/10/15,Data Mining: Concepts and Techniques,18,Star-Cubing算法,深度优先遍历,例4-8,2018/10/15,Data Mining: Concepts and Techniques,19,聚集阶段一：处理基本树的最左分支,2018/10/15,Data Mining: Concepts and Techniques,20,Star-Cubing AlgorithmDFS on Star-Tree,聚集阶段二：处理基本树的第二个分支,20
13、18/10/15,Data Mining: Concepts and Techniques,21,多路星树聚集（1）,从基本星树的根部开始深度优先（DFS）搜索 对于深度优先的每个节点，根据遍历顺序，为当前树的后代创建相应的星树 E.g., 在基本树中，当DFS到达a1时，生成ACD/A树 当DFS到达b*时，生成ABD/AD树 新树沿用基本树中的计数,2018/10/15,Data Mining: Concepts and Techniques,22,多路星树聚集（2）,当DFS到达叶子节点(e.g., d*)时，开始回溯 对于每个回溯分支，输出计数，销毁该树，基本树中的节点被销毁 例如：
14、当从d*回溯到c*，输出并销毁a1b*c*/a1b*c*树 当从c*回溯到b* ，输出并销毁a1b*D/a1b*树 当回溯遍历到b*时，b1中存在一个兄妹，ACD/A将留在内存，像对b*做的那样，对b1进行深度优先搜索,2018/10/15,Data Mining: Concepts and Techniques,23,Star-Cubing算法小结,对维的次序敏感 维以基数的递减序处理以获得最佳性能 基数越高，划分剪枝的可能性越高 计算完全立方体 稠密数据集：Star-Cubing与多路聚集性能相当，比BUC快得多 稀疏数据集：Star-Cubing明显比多路聚集快，大部分情况下比BUC快
15、冰山立方体： Star-Cubing比BUC快,2018/10/15,Data Mining: Concepts and Techniques,24,高维OLAP预计算壳片段,高维的完全数据立方体需要海量存储空间和不切实际的计算时间 计算一个薄的立方体外壳 计算方体量仍然很大 不支持高维OLAP OLAP外壳片段方法：因为大部分OLAP操作一次只对少数维执行 半联机计算策略 将维划分为互不相交的维片段，并转换成相应的倒排索引表示 构造外壳片断立方体，保持与立方体单元相关联的倒排索引 通过倒排索引上的集合交操作，联机动态组装和计算所需要的数据立方体的方体单元,2018/10/15,Data Mi
16、ning: Concepts and Techniques,25,高维OLAP预计算外壳片段算法特性,将数据垂直划分 将高维方体降低为多个低维方体集合 联机重构原始的高维空间 无损规约 提供预计算和联机计算速度的折衷 合理的存储开销和快速的查询响应时间,2018/10/15,Data Mining: Concepts and Techniques,26,计算实例,例4-9 构造倒排索引 例4-10 计算外壳片段 假设数据立方体的聚集函数是count将5个维划分成2个片断: (A, B, C) 和 (D, E),2018/10/15,Data Mining: Concepts and Techniques,27,1-D 倒排索引,构造倒排索引,2018/10/15,
