基于HOLAP的关联规则挖掘基于HOLAP的关联规则挖掘Association Rule Mining on Hybrid OLAP周爱广 李玉忱 蒋志芳 曹璐（山东大学计算机科学与技术系 250061）摘要：本文提出了一种基于关系数据库和一维内存数组相结合的HOLAP的实现方式，以及基于这种数据立方体的改进的关联规则挖掘算法。在预处理的基础上，减少扫描空间和扫描次数，利用聚合数据减少计算时间，以达到一种OLAP和数据挖掘相结合的高效模式。Abstract: In this article, we introduced a realization of HOLAP based on the RDBMS and one dimensional cache array. An improved association rule mining algorithm on this kind of data cube was presented at the same time. Pre-processing of data helps to reduce the room and times for scan. Information of multidimensional aggregation reduce the time on computation. The goal of this article is to generalize a combined efficient paten of OLAP and data mining.关键词：OLAP，HOLAP，数据立方体，聚合计算，关联规则，数据挖掘1、 引言数据挖掘（Data Mining）是一种从大型数据库或数据仓库中发现隐藏信息和预测信息的新技术。它的目标是发现数据间潜在的模式，找出最有价值的信息。关联规则发现23作为数据挖掘的任务之一就是发现数据对象间的某种有价值的相互联系和满足一定条件的互相依赖关系，可以形式化为A1A2Ai = B1B2Bj。但是当前众多的关联规则挖掘算法存在的主要问题是实现起来困难。原因是挖掘工作在大型数据库或数据仓库中进行，大量的属性导致搜索空间过大，生成大量的无意义或有悖常识的冗余模式。Han . J . W 等在数据立方体的基础上提出多维数据挖掘1的概念，将数据挖掘功能与OLAP（On_Line Analytical Processing ）的聚合计算相结合，在数据立方体中进行多维、多层次的数据挖掘。这样就可以结合OLAP和数据挖掘两方面的优点，既具有OLAP的在线、灵活性，又具有数据挖掘的深入性。这也是数据仓库技术和数据仓库工具发展的必然方向。为了探索将数据挖掘和OLAP技术实现结合，本文提出了一种基于HOLAP(Hybrid OLAP )的关联规则挖掘算法：在关系型数据库的基础上，引入一维数组来实现多维聚合数据立方体，形成一种混合型OLAP模式，然后给出一种先聚合计算然后在聚合数据的基础上进行关联规则挖掘的算法。实验结果证明基本达到了预期目的。2、 基于关系和内存一维数组的HOLAP的实现2.1 ROLAP与MOLAP的分析当前应用中多数OLAP实现方式是基于关系数据库的ROLAP和基于多维数据库的MOLAP。ROLAP是使用传统的关系数据库（RDB）通过星型结构或雪花型结构4来实现数据立方体，而且文献8还在SQL Group-By操作的基础上扩充了CUBE操作符使立方体操作具体化。ROLAP的优点是查询操作灵活，但是在数据预处理程度较低的情况下，查询效率将很低，预处理程度高时，又会带来较大的数据冗余。MOLAP是使用多维数据库（MDB）来存储OLAP分析用的数据，MDB在存储数据时，最简单的形式就是使用稀疏数组5来实现，数组的维作为坐标轴，将数据在立方体中的位置映射为在数组中的位置。MOLAP的优点是响应时间短，缺点是数据立方体必须事先定义好，因此灵活性差，并且经过比较复杂的预处理，内存开销大。通过以上分析，ROLAP和MOLAP各有利弊，于是产生了两者相结合的方式HOLAP。2.2 HOLAP的实现HOLAP的实现方式有多种，其中较为理想的方式目前公认为是利用MDB存储聚合信息，而利用RDB存储细节数据。下面讨论如何实现聚合数据立方体。定义1：（数据立方体）数据立方体是一个5元组，CUBE=（D，M，DOM，f，aggr）。D=d1，dn称为维标识集；M=m1，mm称为指标标识集；DOM=dom1domk为属性集取值域；f为D到M的在DOM上的部分映射；aggr为D上的聚合函数。这是数据立方体的一个一般的形式化定义。更具体化的定义根据实现方式的不同而不同，主要区分在存储方式上。下面给出MDB存储方式下的数据立方体的定义。定义2：（稀疏数组数据立方体）稀疏数组数据立方体是一个多维数组MD=D1，Dn，其中维数组Di=di1，di2，diaggr表示第i维，dij代表维Di的j层次, diaggr为该维的聚合。|Di| 表示维数组Di的长度，因此每一维都有|Di|+1长度，并且用矢量V（v1, vn）表示数据立方体中的单元。显然，多维数组MD与CUBE存在着完全对应关系。然而站在应用的角度，数据立方体根据查询驱动设置的，而具体查询所要求的维的数目事先未知，因此，多维数组的维数事先未知，所以在面临具体查询要求时必须动态生成合乎要求的数据立方体。一种方案是动态生成多维数组，用多维数组中的位置来标识它在数据立方体中的单元位置，然而当数据立方体非常稀疏时，会造成空间的巨大浪费，因此不得不考虑分块或压缩，这又是一种时间换空间的方法；另一种方案是用一维数组代替多维数组，只记录那些非空单元的值和在数据立方体中的偏移量，这样既不影响应用又节约空间。因此我们把多维数组数据立方体只作为概念上的，而具体实现上使用一维数组。下面将讨论基于定义2改造的一维数组数据立方体的生成算法。算法1：VtoI /将多维空间矢量转化为一维数组的下标输入：数据立方体单元矢量V（V1, Vn）/n是数据立方体维数输出：数组下标index方法：index=0; for(i=1; i=n;i+) index=Vi + index; index=Vi (|Di+1| +1) + index; index=index+Vn; return index;切片与切块是数据立方体OLAP的最重要两个操作，在本文中切片和切块还是基于数据立方体进行关联规则挖掘的实际操作空间，因此下面基于概念多维数组立方体引进聚合片、聚合块的定义，然后讨论在一维数组上的实现。定义3：（聚合片）多维数据立方体MD的一个聚合片是一个多维数组S=D1，Di-1，Di+1，Dn，Di是选定维，diDi是选定维上的选定层次。算法2：Slice-to-Array聚合片S转化为一维数组A输入：S，di输出：As方法：c_index=0;for( d1=0;d1=|D1|+1;d1+) for( di-1=0;di-1=|Di-1|+1;di-1+) for( di+1=0;di+1=|Di+1|+1;di+1+) for( dn=0;dn=|Dn|+1;dn+) daggr= aggregation(Vd1，Vdi-1，di，Vdi+1，Vdn) if daggr is valuable / 例如：Count0 c_index=VtoI( Vd1，Vdi-1，di，Vdi+1，Vdn); record c_index and daggr into an element of Asx; 定义4：（聚合块）多维数据立方体MD的一个聚合块是一个多维数组T= D1，Di-1，Di+1，Dj-1，Dj+1，Dk-1，Dk+1，Dn，Di，Dj，Dk是选定维，diDi，djDj，dkDk是选定维上的选定层次。聚合块Q转化为一维数组的算法(Dice-to-Array)类似于算法2，此处不再赘述。以上给出了概念多维数组立方体的切片与切块如何转化为一维数组，目的是说明一种多维聚合数据立方体的实现方式。在实现HOLAP的时候，应该在尽量保持时间效率的同时减少对空间的要求。本文提出的使用RDB存储原始细节数据，而使用一维数组存储聚合数据的HOLAP（系统逻辑结构见图1），因为多维数组聚合数据立方体只是一个概念上的，仅仅用于指导对立方体的操作，而实际立方体数据使用一维数组存储，这是因为应用中每次用到的往往只是数据立方体中的一部分，因此在概念数据立方体的基础上动态的求取它的切片或切块，数据量不但大大减少，节省大量存储空间，而且可以保持一定较短的响应时间。这种实现的另一个优点就是在数据挖掘中以部分立方体代替事务数据库，不但可以减少数据挖掘的空间，而且可以节省计算时间，提高挖掘的效率。通过以上分析可以得出，基于关系和内存一维数组的HOLAP可以结合ROLAP和MOLAP的优点，为OLAP和数据挖掘提供良好的数据模型。 切片切块 虚拟Data cubeOLAPGroup -by一维数组Data Mining图1 基于一维数组的HOLAP系统逻辑结构数据立方体生成过程实际是对事务数据库进行聚合计算的过程。对于关系数据库的聚合计算就是Group-By操作。许多文献67都讨论了关系数据库Group-By聚合运算优化问题，文献7对于优化聚合立方体生成算法作了如下总结：l 最小双亲：因为一个group-by可以由其他一定数量的group-by计算，因此尽量采用最小的先计算出的group-by。l 主存优先：尽量利用内存中已经计算出的group-by来计算其他group-by，减少磁盘的I/O操作。l 平摊扫描：在一次磁盘读操作中计算尽可能多的group-by，包括利用内存中的group-by。l 共享排序：对于基于排序的算法，使多个group-by计算共享一次排序结果。l 共享分区：对于基于散列的算法，当散列表太大不能一次全装入内存时，对数据和聚集进行划分，使多个group-by尽量共享一个分区。3、 在HOLAP中进行关联规则挖掘3.1 关联规则的一般性的定义许多文献23给出了关联规则的描述，一个具有一般性的描述是：设I=i1,i2,.,im是由m个不同的项目组成的集合，在给定事务型数据库D中，每一个事务T是一个项目集，即TI，并且与一个称为事务表标识符TID的唯一标识相联系。设X为