数据挖掘-数据冰山立方体计算.ppt

《数据挖掘-数据冰山立方体计算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容冰山立方体计算在很多情况下，数据立方体的空间大多被低度量值的数据单元所占据，而这些数据单元往往是分析者很少关心的内容。冰山立方体的计算能够减少物化数据单元所占有的存储空间。计算方法BUC：Bottom-UpComputationStar-CubingMMCubing,C-Cubing等计算方式allABCACBCABCABDACDBCDADBDCDDABCDABallABCACBCABCABDACDBCDADBDCDDABCDABBottom-UpComputation自底向上计算Top-DownComputation自顶向下计算基本

2、方体顶点方体MultiWayBUCBUC:Bottom-UpComputation1999年由KevinBeyer等在“Bottom-UpComputationofSparseandIcebergCUBEs”一文中提出；一种从顶点立方体逐步向下到基本立方体的计算方法，用于计算稀疏冰山立方体；BUC主要思想：首先计算整个数据立方体的度量值,然后沿着每个维度进行划分，同时检查冰山条件，对不满足条件的分枝进行剪枝操作，对满足的在下一个维度进行递归搜索。allABCACBCABCABDACDBCDADBDCDDABCDAB12345789101113

3、151214166BUC计算流程首先，扫描整个输入，计算整个度量（如总计数）；针对方体的每一维进行划分；针对每一个划分，对它进行聚集，为该划分创建一个元组并得到该元组的计数。判断其分组计数是否满足最小支持度；如果满足，输出该划分的聚集元组，并在该划分上对下一维进行递归调用，否则进行剪枝操作。例：已知立方体有四个维：A,B,C和D，每个维的基数也就是每个维不同值的个数也已知，A和B分别有4个不同的值，C有2个不同值。计算维A,B,C和D而且最小支持度计数为3的冰山立方体。BUC性能分析BUC算法中采用了分治策略，优点在于能够分担划分开销，减少不

4、必要的计算消耗。BUC的性能容易受到维的次序以及不平衡数据的影响，应当以维基数的递减顺序进行划分。例（优化：排序、散列和分组技术）BUC不像多路数组聚集（MultiWay），不能利用父子关系共享聚集计算。例b1c12c23b2c11b3c22b4c12c1b12b21b42c2b13b32假设有两个维B和C，其中B维有4个不同的值b1,b2,b3,b4，C维有2个不同的值c1,c2，最小支持度为3。思考MultiWay自底向上计算多维共享聚集计算无Apriori剪枝BUC自顶向下计算无共享聚集计算Apriori剪枝共享聚集与Apriori剪枝

5、结合Star-Cubing2003年，由DongXin和JiaweiHan等在“Star-Cubing:ComputingIcebergCubesbyTop-DownandBottom-UpIntegration”一文中提出。一种集成自顶向下和自底向上的立方体计算方法，结合了多路数组聚集中的同时聚集和BUC中的Apriori剪枝策略。利用星型树数据结构进行存储，其中核心的部分就是引入共享维的概念。如果共享维的聚集值不满足冰山条件，则共享维向下的所有单元都不满足冰山条件。共享维allABCACBCABCABDACDBCDADBDCDDABCDA

6、BallABCDABC/ABCABD/ABACD/ABCDAC/AC剪裁：AB/ABAD/A剪裁：A/A剪裁：B/BC/CD/DBC/BCBD/BCD通过观察左图发现，在以ABD为根的子树中的所有方体都包含维AB，以ACD为根的子树中的所有方体都包含维A，我们把子树中所有方体都包含的维叫做这些子树的共享维。共享维便于共享计算在ABD/AB中，计算ABD方体时同时计算扩展的方体AB自顶向下扩展共享维扩展的自底向上计算方式为Apriori剪枝提供条件如果共享维的聚集值不满足冰山条件，则沿该共享维向下的所有单元也不可能满足冰山条件方体树树的每一层代

7、表一个维，每个节点代表一个属性值。每个节点有4个字段：属性值，聚集值，指向可能后代的指针和指向可能兄妹的指针。采用了树结构来表示方体；合并了公共前缀，能够节省内存；能够聚集内部节点的值，可用于基于共享维的剪枝；对树结构的遍历即可得到一个特定元组星树假设单个维A在属性值p上的聚集不满足最小支持度，则将这样的节点用*替换，进一步压缩方体树。我们称属性A中的节点p为星节点，使用星节点压缩后的方体树为星树。ABCDCounta1b1c1d11a1b1c4d31a1b2c2d21a2b3c3d41a2b4c3d41ABCDCounta1b1**1a1b

8、1**1a1***1a2*c3d41a2*c3d41假设最小支持度为2星树ABCDCounta1b1**2a1***1a2*c3d42ABCDCounta1b1c1