基于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，数据立方体，聚合计算，关联规则，数据挖掘
引言
数据挖掘（Data Mining）是一种从大型数据库或数据仓库中发现隐藏信息和预测信息的新技术。它的目标是发现数据间潜在的模式，找出最有价值的信息。关联规则发现[2][3]作为数据挖掘的任务之一就是发现数据对象间的某种有价值的相互联系和满足一定条件的互相依赖关系，可以形式化为A1^A2^……^Ai => B1^B2^……^Bj。但是当前众多的关联规则挖掘算法存在的主要问题是实现起来困难。原因是挖掘工作在大型数据库或数据仓库中进行，大量的属性导致搜索空间过大，生成大量的无意义或有悖常识的冗余模式。
Han . J . W 等在数据立方体的基础上提出多维数据挖掘[1]的概念，将数据挖掘功能与OLAP（On_Line Analytical Processing ）的聚合计算相结合，在数据立方体中进行多维、多层次的数据挖掘。这样就可以结合OLAP和数据挖掘两方面的优点，既具有OLAP的在线、灵活性，又具有数据挖掘的深入性。这也是数据仓库技术和数据仓库工具发展的必然方向。为了探索将数据挖掘和OLAP技术实现结合，本文提出了一种基于HOLAP(Hybrid OLAP )的关联规则挖掘算法：在关系型数据库的基础上，引入一维数组来实现多维聚合数据立方体，形成一种混合型OLAP模式，然后给出一种先聚合计算然后在聚合数据的基础上进行关联规则挖掘的算法。实验结果证明基本达到了预期目的。
基于关系和内存一维数组的HOLAP的实现
ROLAP与MOLAP的分析
当前应用中多数OLAP实现方式是基于关系数据库的ROLAP和基于多维数据库的MOLAP。ROLAP是使用传统的关系数据库（RDB）通过星型结构或雪花型结构[4]来实现数据立方体，而且文献[8]还在SQL Group-By操作的基础上扩充了CUBE操作符使立方体操作具体化。ROLAP的优点是查询操作灵活，但是在数据预处理程度较低的情况下，查询效率将很低，预处理程度高时，又会带来较大的数据冗余。MOLAP是使用多维数据库（MDB）来存储OLAP分析用的数据，MDB在存储数据时，最简单的形式就是使用稀疏数组[5]来实现，数组的维作为坐标轴，将数据在立方体中的位置映射为在数组中的位置。MOLAP的优点是响应时间短，缺点是数据立方体必须事先定义好，因此灵活性差，并且经过比较复杂的预处理，内存开销大。
通过以上分析，ROLAP和MOLAP各有利弊，于是产生了两者相结合的方式HOLAP。
HOLAP的实现
HOLAP的实现方式有多种，其中较为理想的方式目前公认为是利用MDB存储聚合信息，而利用RDB存储细节数据。下面讨论如何实现聚合数据立方体。
定义1：（数据立方体）数据立方体是一个5元组，CUBE=（D，M，DOM，f，aggr）。D={d1，…，dn}称为维标识集；M={m1，…，mm}称为指标标识集；DOM=dom1…domk为属性集取值域；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 // 例如：Count≠0
{
c_index=VtoI( Vd1，…，Vdi-1，di，Vdi+1，…，Vdn);
record c_index and daggr into an element of As[x];
}
}
定义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和数据挖掘提供良好的数据模型。
图1 基于一维数组的HOLAP系统逻辑结构
数据立方体生成过程实际是对事务数据库进行聚合计算的过程。对于关系数据库的聚合计算就是Group-By操作。许多文献[6][7]都讨论了关系数据库Group-By聚合运算优化问题，文献[7]对于优化聚合立方体生成算法作了如下总结：
最小双亲：因为一个group-by可以由其他一定数量的group-by计算，因此尽量采用最小的先计算出的group-by。
主存优先：尽量利用内存中已经计算出的group-by来计算其他group-by，减少磁盘的I/O操作。
平摊扫描：在一次磁盘读操作中计算尽可能多的group-by，包括利用内存中的group-by。
共享排序：对于基于排序的算法，使多个group-by计算共享一次排序结果。
共享分区：对于基于散列的算法，当散列表太大不能一次全装入内存时，对数据和聚集进行划分，使多个group-by尽量共享一个分区。
在HOLAP中进行关联规则挖掘
3.1 关联规则的一般性的定义
许多文献[2][3]给出了关联规则的描述，一个具有一般性的描述是：
设I={i1,i2,...,im}是由m个不同的项目组成的集合，在给定事务型数据库D中，每一个事务T是一个项目集，即TI，并且与一个称为事务表标识符TID的唯一标识相联系。设X为一个项目集，当且仅当XT时，称事务T包含X。
关联规则：XY（XI，YI，并且X∩Y=）存在的条件是：（1）具有支持度（support）s，指在D中，包含X∪Y事务所占的比例为s%；（2）具有确信度（confidence）c，指在D中，c%的事务包含X的同时也包含Y。
一般的，由用户给定最小确信度和支持度，发现关联规则的任务就是从数据库中发现那些确信度和支持度都大于给定值的强壮规则。影响挖掘性能关键在于发现所有的大项目集，即发现L（LI），supp(L)>min_supp。
依据定义1中domi类型的不同，事务属性可以分为数值型和布尔型两类，关联规则的挖掘也因此可以分成数值型和布尔型两类。本文将以布尔型数据挖掘为例进行讨论。
3.2 一般的多循环扫描算法
首先由Agrawal 和Srikant[3]提出的Apriori算法是一个非常典型并且很具有影响力的算法，它的描述是：
算法3：Apriori
k=0; L ={ frequent 1-item sets };
Repeat
Generate candidate k-itemsets Ck=gen_candidate(k, Lk-1);
for all transactions in the DB
do{
for all candidates
if c ∈Ck contained in t
do c.count++
}
Lk={Ck| c ∈Ck and c.count>=min_supp};
L=L ? Lk;
k=k+1
Until Lk=;
gen_candidate(k, Lk-1)
Ck=;
For each I1,I2∈Lk-1
{If just one item is different between I1 and I2
C=I1 ? I2;
If ( k-1)-subset s of c, sLk-1
Delete c;
Else
Add c to Ck;
}
return Ck;
在这个算法中，对每个侯选频繁项目集的支持数的计算都要扫描整个数据库，对于每个新侯选项目集的生成都要扫描整个当前频繁项目集，这样必然出现一些不必要的重复，影响算法的效率。下面将讨论基于以上HOLAP的布尔型数据立方体的改进的多循环扫描挖掘算法。
基于HOLAP的改进的多循环扫描关联规则挖掘算法A- Apriori
基于OLAP的关联规则包括维内关联规则和维间关联规则，由于两者在处理上基本一致，不同主要在于预处理和频繁项目集处理上略有不同，在这里以一种统一的方式进行讨论。
算法4：A-Apriori
step1: //pre-processing
build conceptual multi-multidimensional array data cube MA；
set the mining dimension di，…，dj；
At=Dice-to-Array(di，…，dj);// di，…，dj from different dimension
(or As=Slice-to-Array(di，…，dj) ;//di，…，dj from the same dimension)
//At and As are one-dimension cache arrays for the dice or slice of conceptual
//multi-dimensional array data cube MA
if At[i].count< totalcount min_supp
delete At[i];//delete invalid data cube cell Vi if count(Vi)< totalcount min_supp
step2: //association rule mining
k=0; L ={ frequent 1-item sets };
Repeat
Generate candidate k-itemsets Ck=gen_candidate(k, Lk-1);
for each transaction in At (or As) //范围与Apriori不同
do{
for all candidates
if c ∈Ck contained in t
do c.count++
}
Lk={Ck| c ∈Ck and c.count>=min_supp};
L=L ? Lk;
k=k+1
Until Lk=;
gen_candidate(k, Lk-1)
//The same as the Apriori
3.4 算法分析与比较
设事务数据库总事务个数为N，概念数据立方体的维数是n，总层次数是m，挖掘选定的层次总数也是m。将空间矢量转换成数组偏移量的算法的时间复杂度是O（n），则在预处理阶段生成时间复杂度比切块高的切片的时间是T（2m-1n），因为n<<2m-1，所以相应的时间复杂度是O（2m）。因为如果事务数据库的属性增多相应的其事务总数理论上也会以指数速度增加，因此可以近似认为O（2m）=O（N）。所以在预处理阶段的总时间复杂度接近O（N），可见其时间还是可以接受的。
在本算法中，虽然第一步预处理耗费一定的时间，但是其挖掘效率会显著提高，主要体现在以下几点：
由于采用了一维内存数组，在扫描数据时减少了磁盘扫描，其挖掘过程要明显节省时间。
在挖掘之前进行了聚合片或聚合块的操作，减少了数据空间，因此缩小了算法扫描范围，同样缩短了时间。
聚合数据数据的使用，减少了计算时间。
清理无用数据单元Vi 如果 count(Vi)< totalcount min_supp，使生成频繁项目集的扫描空间直接减少，而且使生成候选大项目的扫描空间间接减少。
结束语
基于HOLAP的关联规则的挖掘，优点在于结合了OLAP和数据挖掘两方面的优点，提高挖掘效率只是一个方面，它应该在交互性、灵活性、在线性和可扩展性都有很大的优势，本文的算法只是一个开展进一步工作的开端，基于立方体的挖掘算法应该是数据挖掘领域的一个方向。
参考文献：
J. W. Han. Towards On_Line Analytical Mining in Large Database. ACM SIGMOD Record 27, 97-107, 1998
R. Agrawal, T. Imielinski, and A. Swami. Mining Association Rules between Sets of Items in Large Database. Proc. of ACM SIGMOD. 207-216, May, 1993
R. Agrawal and R. Srikant. Fast algorithm for mining association rules. In Proc. 1994 Int. Conf. Very Large Data Bases, 487-499, Santiago, Chile, Sept.,1994
S. Chaudhuri and U. Dayal. An overview of data warehousing and OLAP technology. ACM SIGMOD Record 26, 65-74, 1996,
Y.Zhao, P. M. Deshpandc, and J. F. Naughton. An Array-based Algorithm for Simultaneous Multidimensional Aggregates. In Proc, 1997 ACM SIGMOD Int, Conf, Management of Data, pp.159-170,Tucson, Arizona, May 1997
Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman. Implementing Data Cubes Efficiently. SIGMOD’96 6/96 Montreal Canada
S. Agarwal, R. Agarwal, P. M. Deshpande, A. Gupta, J.F. Naughton, R. Ramakrishnan and S. Sarawagi. On the Computation of Multidimensional Aggregates. In Proc. 1996 Int. Conf. VLDB, pp.506-521, Bombay, India, Sept.1996
Gray J, et al. Data Cube. A Relational Operator Generalizing Group-By, Cross-Tab and Sub-Totals. In: Proc. of the 12th Int. Conf. On Fata Engineering, 1996, 152-159
Jochen Hlpp, Ulrich Guntzer,Gholamreza. Algorithms for Association Rule Mining-A General Survey an Comparison. Volume 2,Issue 1, pp.58-64. ACM SIGKDD. July 2000
S. Agarwal, R. Agarwal, and N. Megiddo. Discovery-driven Exploration of OLAP data cubes. In Proc. Int. Conf. Of Extending Database Technology, March 1996
基于HOLAP的关联规则挖掘.doc
