数据立方体计算与数据泛化

湘潭大学商学院管理科学与工程韦波第四章数据立方体的计算与数据泛化本章，我们将更详细的考察描述性数据挖掘。描述性数据挖掘，它以简洁和汇总的方式描述数据，并提供数据有趣的一般性质。本章内容主要包括三节：第一节：考察如何有效地在不同的抽象层计算数据立方体，深入考察数据立方体计算的具体方法。第二节：提供OLAP和数据立方体的进一步探查方法。第三节：介绍另一种数据泛化方法，面向属性的归纳。湘潭大学商学院管理科学与工程韦波第一节数据立方体计算的有效方法湘潭大学商学院管理科学与工程韦波1、不同类型立方体物化的路线图数据立方体有利于多维数据的联机分析处理。本节将完全立方体物化与部分立方体物化的各种策略进行比较。为完整起见，我们首先回顾设计数据立方体的基本术语。■立方体物化数据立方体是方体的格。每个方体用一个group-by表示。基本方体是数据立方体中泛化程度最低的方体，泛化程度最高的方体是顶点方体，通常用all表示。它包含一个值，对于存放在基本方体中的所有元组聚集度量M。对立方体下钻，就是从顶点方体沿方体格向下移动；上卷就是从基本方体向上移动。本章讨论的目的是使用术语数据立方体的格而不是单个方体。基本方体的单元是基本单元，非基本方体的单元是聚集单元。聚集单元在一个或多个维聚集。湘潭大学商学院管理科学与工程韦波聚集单元在一个或多个维聚集，其中每个聚集维用单元记号中的＊指示。聚集的维数不同，单元之间可能存在祖先-子孙关系。为了确保联机分析处理，有时希望预计算整个立方体，但是，预计算整个立方体需要海量空间，常常超过存储容量。尽管这样，完全立方体计算的算法仍然很重要。部分物化则在存储空间和OLAP的响应时间之间提供了有趣的折衷。冰山立方体就是一种部分物化的方法，这种方法只对满足阙值的方体物化。冰山立方体的SQL查询：computercubesales_icebergasSelectmonth,city,customer_group,count(*)FromsalesinfoCubebymonth,city,customer_groupHavingcount(*)﹥﹦min_sup湘潭大学商学院管理科学与工程韦波为了系统的压缩数据立方体，需要引入闭覆盖的概念。一个单元c是闭单元，即如果不存在单元d使得d是单元c的特殊化（后代）（即d通过将c中的*值用非*值替换），并且d与c具有相同的度量值。闭立方体是一个仅由闭单元组成的数据立方体。部分物化的另一种策略是仅预计算涉及少数维（如3到5个维）的方体，这些方体形成对应数据立方体的外壳，对附加的维组合的查询必须临时计算。湘潭大学商学院管理科学与工程韦波■立方体计算的一般策略一般，有两种基本数据结构用于存储方体。关系表是关系OLAP实现的基本数据结构，而多维数组是多维OLAP实现的基本数据结构。尽管ROLAP和MOLAP可能使用不同的立方体计算技术，但是某些“优化”技巧可以在不同的数据表之间共享。下面介绍一些数据立方体有效计算的一般优化技术：●排序、散列和分组应当对维属性使用排序、散列和分组操作，以便对相关元组重新定序和聚类。在立方体计算中，聚集对共享一组相同的纬值的元组（或单元）进行。这样，重要的是利用排序、散列和分组操作一起访问和分组这样的数据，以利于聚集的计算。●同时聚集和缓存中间结果在立方体计算中，由先前计算的较低层聚集计算叫高层聚集，而不是由基本事实表计算。此外，从缓存的中间计算结果同时聚集可以减少开销很大的磁盘I/O操作。湘潭大学商学院管理科学与工程韦波●当存在多个子女方体时，由最小的子女聚集当存在多个子女立方体时，由最小的，先前计算的子女方体计算父母方体（即更泛化的方体）通常更有效。●可以使用Apriori剪枝方法有效地计算冰山立方体Apriori性质表述如下：如果给定的单元不满足最小支持度，则该单元的后代也都不满足最小支持度。使用这个性质可以显著地降低冰山立方体的计算量。湘潭大学商学院管理科学与工程韦波2、完全立方体计算的多路数组聚集多路数组聚集方法使用多维数组作为基本数据结构，计算完全数据立方体。它是一种使用数组直接寻址的典型MOLAP方法，其中维值通过位置或对应数组位置的下标访问。因此，多路数组聚集不能使用任何基于值的重新排序作为优化技术。所使用的一种不同的方法是为基于数组的立方体结构开发的：●将数组分成块。块是一个子立方体，其大小能够放入立方体计算时可用的内存。分块是一种将n维数组划分成小的n维块的方法，其中每块作为一个对象存放在磁盘上。●通过访问立方体单元（即存取立方体单元的值）计算聚集。由于分块设计“重叠”某些聚集计算，称该技术为多路数组聚集，它进行同时聚集——即同时对多个维计算聚集。湘潭大学商学院管理科学与工程韦波我们现在通过一个具体的例子来说明多路数组立方体计算。考虑一个包含维A、B、C的3-D数组。维A组织成4个相等划分的a0、a1、a2、a3。维B、C类似地划分成4部分。●基本方体记作ABC（其他方体间接或直接的由它计算）。该方体业已计算，并对应于给定的3-D数组。●2-D方体AB,AC和BC分别对应于按AB，AC和BC分组。这些方体必须计算。●1-D方体A，B和C,分别对应于按A，B和C分组。这些方体必须计算。●0-D方体，记作all，即没有分组。该方体必须计算。它包含一个值。现在，我们来看一看如何用多路数组技术进行这种计算，假设我们想计算BC方体中的b0c0块。在块内存中为该块分配内存，通过扫描ABC的1-4块，计算出b0c0。即b0c0单元在a0-a3上聚集。然后，块内存分给下一个块b1c0，在扫描ABC紧接着的4个块5-8后完成b1c0的计算。如此继续下去。湘潭大学商学院管理科学与工程韦波我们可以看到，在计算BC方体中，我们已经扫描了64块中的每一块。那么我们在计算其他方体，如AC、AB等的时候，就可以避免重新扫描所有的块。这也就是“多路计算”和“同时聚集”思想。接下来，我们要讨论的问题是，不同的块扫描和方体计算次序对整个数据立方体的计算效率的影响。这个计算效率主要指在内存的占用方面。湘潭大学商学院管理科学与工程韦波3、BUC：从顶点方体向下计算冰山立方体BUC是一种计算稀疏冰山立方体的算法。与Multiway不同，BUC从顶点方体向下到基本方体，构造立方体。这允许BUC分担数据划分开销。这种处理次序也允许BUC在构造立方体时使用Apriori性质进行剪枝。BUC代表“自底向上构造”（Bottom-UPconstruction),然而，BUC的处理次序实际上是自顶向下！BUC的作者以相反的次序观察方体的格，顶点方体在底部，而基本方体在顶部。从这种角度，BUC确实是自底向上构造。然而，由于我们采用应用观点，下钻表示从顶点方向下到基本方体，因此BUC的探查过程视为自顶向下。我们来解释下BUC算法。初始，用输入关系（元组集）调用该算法。BUC聚集整个输入并输出结果总数。对于每个维，输入沿维划分。检查划分的最小支持度。也就是说，如果划分中的元组数满足最小支持度。湘潭大学商学院管理科学与工程韦波现在，我们用一个例子解释BUC是如何工作的用SQL表达的冰山立方体：computercubeiceberg_cubeasselectA，B，C，D，count(*)fromRcubebyA,B,C,Dhavingcount(*)﹥﹦3让我们来看看BUC如何构造维ABCD的冰山立方体，其中最小支持度计数为3.假设维A有4个不同值a1a2a3a4;B有4个不同值b1b2b3b4;C有2个不同值c1c2;而D有两个不同值d1d2.如果将每个分组看成一个划分，则必须计算分组属性的满足最小支持度（即有3个元组）的每个组合。湘潭大学商学院管理科学与工程韦波为了进行划分，BUC扫描输入，聚集元组得到all的计数，对应于单元（*，*，*，*）。使用维A将输入分为4个划分，每个对应于A的一个不同值。A的每个不同值的元组数（计数）记录在datacount中。在搜索满足冰山条件的元组时，BUC使用Apriori性质节省搜索时间。从维的值a1开始，聚集a1的划分为A的分组创建一个元组，对应于单元（a1,*,*,*,).假设这个满足最小支持度，此时再在这个划分上进行递归调用。通过在每次递归使用之前检查冰山条件，只要单元计数不满足最小支持度，BUC就节省大量处理时间。湘潭大学商学院管理科学与工程韦波4、Star-cubing：使用动态星形树结构计算冰山立方体star-cubing结合了我们已经研究过的其他方法的优点。它集成自顶向下和自底向上立方体计算，并利用多维聚集。它从一个称作星形树的数据结构操作，进行无损数据压缩，从而降低计算时间和内存需求量。star-cubing算法利用自底向上和自顶向下的计算模型如下：对全局计算次序，它使用自底向上模型。然而，它下面还有一个基于自顶向下的子层，利用共享维的概念。这种集成允许算法在多个维上聚集，而仍然划分父分组并剪裁不满足冰山条件的子女分组。湘潭大学商学院管理科学与工程韦波ABCDABC/ABCABD/ABACD/ABCDJ剪裁：AB/ABAC/ACAD/ABC/BCBD/BCD剪裁：A/A剪裁：B/BC/CD/DALLStar-cubing方法如上图所示。如果我们只遵循自底向上模型，则star-cubing标记为被剪裁的方体仍然被考察。Star-cubing能够剪裁指示的方体，因为它考虑共享维。湘潭大学商学院管理科学与工程韦波子树方体总都包含的维成为子树共享维。共享维的引入有利于共享计算。由于共享维在树扩展之前识别，可以避免以后重新计算。如：ABD扩展的方体AB实际上被剪枝，因为AB已经在ABD/AB中计算。类似地，由AD扩展的方体A也被剪枝，因为AB已经在ABD/AB中计算。如果冰山立方体度量是反单调的，则共享维允许类Apriori剪枝。也就是说，如果共享维的聚集值不满足冰山条件，则沿该共享维向下的所有单元也不可能满足冰山条件。为了解释star-cubing算法如何工作，我们需要解释更多的概念，即方体树、星节点和星树。湘潭大学商学院管理科学与工程韦波方体树：方体树的每一层代表一个维，每个节点代表一个属性值。每个节点有4个字段：属性值、聚集值，指向可能后代的指针和指向可能兄妹的指针。方体中的元组逐个插入树中。一条从根到树叶节点的路径代表一个元组。这种表示合并了公共前缀，节省内存并允许聚集内部节点的值。利用内部节点的聚集值，可以进行基于共享维的剪枝。如果单个维在属性值p上的聚集不满足冰山条件，则在冰山立方体计算中识别这样的节点没有意义。这样的节点可以用*替换，使方体树可以进一步压缩。如果单个维在p上的聚集不满足冰山条件，则称属性A的节点p是星节点。使用星节点压缩的方体树称为星树。湘潭大学商学院管理科学与工程韦波5、为快速高维OLAP预计算壳片段数据立方体有利于多维数据空间的快速联机分析。然而，高维的完全数据立方体需要海量存储空间和不切实际的计算时间。冰山立方体提供了一个更可行的替代方案，正如我们已经看到的那样，其中冰山条件用来指定只计算完全立方体单元的一个子集。然而冰山立方体有如下的一些缺点：第一、冰山立方体本身的计算和存储的开销仍然可能很高；第二，很难确定合适的冰山阙值；第三，冰山立方体不可能增量的更新，一旦一个聚集单元低于冰山阙值，就被剪枝，它的度量值就丢失，任何增量更新都需要从头重新计算。一种可能的替代方法是计算一个薄的立方体外壳。例如，可以计算一个60维的数据立方体中的具有3维或更少维的所有方体，导致厚度为3的立方体外壳。然而，这种方法有两个缺点。第一：需要计算的方体其实很多的。第二，这种方体不支持高维OLAP。湘潭大学商学院管理科学与工程韦波取代计算立方体外壳，可以只计算它的一部分或片段。本节主要讨论查询处理的外壳片段方法，这主要是基于对高维空间OLAP的如下观察：尽管数据立方体可能包含许多维，但是大部分OLAP操作一次只对少数维执行。所以，我们的做法是这样的，首先找到某些感兴趣的方体，然后沿一两个维钻取，考察几个相关维上的变化。外壳片段算法遵循半联机