邮局：82-946360元/年技术创新
软件时空
《PLC 技术应用200例》
您的论文得到两院院士关注
基于OLAP 的多维关联规则算法的研究
The Research and Application For Multidimensional Association Rules Algorithm Based on OLAP
(湖南大学)
吴昊
1
彭硕
2
WU Hao PENG Shuo
摘要：多维关联规则是数据挖掘中的一个重要研究方向。本文针对Apriori 算法与FP-Growth 算法在数据立方体上应用的优缺点，提出了一种基于Apriori-Growth 的多维关联规则算法，该方案将Apriori 算法与FP 树结构有机地结合起来，其优势在于不需要频繁地扫描数据立方体和产生频繁模式树，在一定程度上提高了算法效率。关键词：数据挖掘；多维关联规则；数据立方体;Apriori-Growth 中图分类号：文献标识码:A
Abstract:Multidimensional data mining association rules is an important research direction.Based on the advantages and disadvan -tages of application for Apriori algorithm and FP-Growth algorithm in the data cube.In this paper,we propose an efficient algorithm for mining multidimensial association rules based on Apriori -Growth,which combine Apriori algorithm and FP -tree structure organi -cally.The advantages of algorithm is that not need to scan data cubes frequently,which improved the efficiency of the algoritm to a certain extent.
Key words:data mining;multidimensial association;data cubel;Apriori-Growth
文章编号:1008-0570(2010)09-3-0099-03
引言
多维关联规则挖掘在近年来得到了充分地重视，目前，已经有不少学者研究了在数据立方体上用Apriori 算法对多维关联规则进行挖掘，该方法虽然可以大幅度压缩候选项集的大小，并具有很好的性能，但需要重复多次扫描数据立方体，并产生大量的候选项.为了避免这些缺陷，阎星娥等人有效提出了OLAP 中
FP-增长的关联规则挖掘算法，该方案大大减少了数据立方体的扫描次数，但是FP-Growth 算法需要递归地生成条件FP 树，这消耗了大量的时间和空间。针对以上原因，本文在算法研究过程中，极力弥补现有算法的不足，提出了一种基于Apriori-Growth 的多维关联规则算法，该方案将Apriori 算法与FP 树结构有机地结合起来，并通过实验表明该算法的执行效率较高，且
内存空间消耗较少。
1基本概念
1.1、工作数据立方体
据用户给定的挖掘任务，从数据仓库中生成数据立方体，在此数据立方体上进行关联规则挖掘，具有一定的针对性。而且由于数据仓库中数据立方体被事先全部或部分物化存储，从而为关联规则挖掘节省了大量挖掘时间，提高了挖掘效率。给定一个关联规则挖掘任务，其内容涉及d1,...,dn 个维，并根据用户
挖掘需求确定各维的维层次，然后从数据仓库中通过OLAP 操作生成数据立方体。其中每一维包含|di|+1个数值,|di|是第i 维包含的互不相同的维成员个数。前|di|行各代表di 中一个互不相同的维成员。最后一行存储了一个称之为”Sum ”的维成员，其中记录了它所对应的维的合计值，这种合计值极大地方便了关联规则的挖掘中支持度的计算。立方体的方格中记录的是对应维成员的频繁度量值，记为count 。这样涉及d1,...,dn 维数据的一个关联规则挖掘任务就对应一个n 维的数据立方体Cube(d1,...,d
n|count)d1,...,dn 是立方体的维，是立方体的事实度量count 。
1.2、多维关联规则的描述
所谓的单维规则挖掘只考虑数据集(一般是事务数据库)中一个属性或维度。若考虑数据集(一般是关系数据库或数据仓库)中多个属性或维度，则挖掘的即为多维关联规则。依据属性是否在规则中重复出现，多维关联规则分为维间关联规则和
混合维关联规则。多维关联规则和量化关联规则一般作为一个整体来研究，算法分为：基于量化属性的静态离散化多维关联规则挖掘和基于量化属性动态离散化多维关联规则挖掘。本文采用量化属性静态离散化技术，重点研究维间关联规则的挖掘。
基于数据立方体的多维关联规则的挖掘基本步骤包括以下方面:
(1)根据用户给定的挖掘任务从数据仓库中生成相关数据立方体;
(2)在生成的数据立方体上挖掘满足最小支持度的频繁谓词集;
(3)在频繁谓词集中生成用户感兴趣的关联规则。
2基于数据立方体的多维关联规则算法
2.1、基于Apriori 性质的多维关联规则算法
利用Apriori 算法的思想在数据立方体上搜索频繁谓词集的算法，在文中称之为Apriori_Cube 算法,Apriori_Cube 算法不
同之处是谓词集支持度的计算。在基于数据立方体的多维关联规则挖掘中一个谓词集就是数据立方体Cube(d1,...,dn|count )的不同维成员的一个组合。谓词集的支持计数count 就是立方体方格存储的频繁度量值。详细算法如下:
吴昊：副教授硕士生导师
99
-
-
技
术创新
《微计算机信息》(管控一体化)2010年第26卷第9-3期
360元/年邮局：82-946
《现场总线技术应用200例》
软件时空
输入:N 维数据立方体:CB[d1,d2,…dn]，最小支持度:min_sup 输出:n 维间频繁项集
(1)K=1;L=null;
(2)对于每一维产生候选1-项集C 1,di ={di 维中所有不同的维值};
(3)产生频繁1-项集L1=gen_frequent(1,C 1);(4)Repeat:K=k+1;
产生候选k-项集C k =gen_candidate(k,L k-1)；产生频繁k-项集L k =gen_frequent(k,C k );L=L ∪L k ;Until L k =null;
Function gen_frequent(k,Ck)//从候选k-项集C k 中产生频繁k-项集Lk;
1)Lk=null;
2)For 每一个候选k-项集,I=(i1,i2,…,ik)∈Ck do{
3)frequency=数据立方体中(i1,i2,…,ik,sum,..sum)数据单元的count 值
4)if (frequency>min_sup)then 5)Lk=Lk ∪I;}
Function gen_candidate (k,L k-1)//从频繁k-项集L k-1中产生候选k-项集C k ;
1)C k =null;
2)For 每个项目I1∈L k-13)For 每个项目I2∈L k-1
4)If(I1和I2的前k-2项相同and 第k-1项来自不同的维)then{
5)C=I1∞I2;
6)If ((k-1)-subset s of c,s 不属于L k-1)then 7)delete c;
8)else add c to C k
2.2、基于FP 性质的多维关联规则算法
经过实验发现，当数据立方体很大或者支持度较小时,Apri -ori_Cube 算法的运行时间会急剧增加。因为这些算法需要多次数据立方体的扫描，并且还要通过模式匹配遍历扫描得到的数据集。如果能将数据立方体的扫描次数降低到最小，则算法性能应该会有大幅的提升。基于这样的思想，有人提出了基于FP 树性质的多维关联规则的算法(FP-Growth_Cube)，该算法将利用FP-树结构，用于压缩存储数据立方体中的数据，它的结点的排
序方式使越频繁的谓词对应的树中结点越容易被共享。表1适于挖掘的数据立方体表表2基于出现频率的频繁1项集图1构造FP 树
FP-Growth_Cube 算法主要由以下几个步骤组成:
(1)扫描数据立方体表(如表1所示)，计算所有维中所有项的支持度，并不分维度按支持度递顺序排序。
(2)第2次扫描数据立方体表，每个事务中的项按频繁1-项集表(如表2)中的次序处理，删除每个事务中的
非频繁项，并对每个事物创建一个分枝.当为一个事物考虑增加分枝时，沿共同前缀上的每个节点的计数增加相应的count 值，为跟随在前缀
之后的项创建节点并创建链接指向前缀。
(3)使用FP-Growth 算法挖掘出频繁项集。
FP-Growth_Cube 算法其优势在于其前缀树结构能存储数据立方体中的信息，而且只需扫描数据立方体两次，但是FP-Growth_Cube 算法在挖掘的过程中需产生大量频繁模式基和递归地构造条件FP-树，对算法的效率造成一定影响。
2.3、基于Apriori-growth 性质的多维关联规则算法
针对以上两种算法的优缺点，本文提出了一种基于Apriori-growth 性质的多维关联规则算法(Apriori-growth_Cube)，其将Apriori_Cube 与FP-Growth_Cube 两种算法的优点结合起来，该算法同样是采用FP-树来存储数据立方体中的数据，其数据结构如图2，图3所示
图2表头项结构
图3FP-tree 结点结构
Apriori-growth_Cube 主要由两个步骤组成:
(1)扫描数据立方体，出频繁1-项集，并按照支持度递减的顺序排序，然后再次扫描数据立方体来构造FP-树(如2.2小结所介绍)。
(2)由Apriori-growth 算法替代FP-Growth 算法来挖掘FP-树。具体的算法如下所示:
Proceduce Apriori-growth_Cube
输入:N 维数据立方体:CB[d1,d2,…dn]，最小支持度:min_sup
输出:n 维间频繁项集(1)L1=frequent 1_itemset;(2)For(k=2;L k-1!=null;k++)(3){
(4)产生候选k-项集C k =gen_candidate(k,L k-1);(5)For each candidate c ∈C k (6){(7)Sup=FP-treeCount(c);/计算支持度
(8)If(Sup>min_sup)(9)Lk=Lk ∪c;}
(10)}
ÁÂÂÂÂÂÂÃÂÂÂÂÂÂÂÄÂÂÂÂÂÂÅÂÂÂÂÂÂÆÂÂÂÂÂÂÂÇÁ
ÂÂÃÁÁÁÁÂÃÃÁÁÁÄÅÆÁÁÁÁÁÄÇÆÁÁÁÁÄÂÆÁÁÁÁÁÄÂÃÁ
100--
邮局：82-946360元/年技术创新
软件时空
《PLC 技术应用200例》
您的论文得到两院院士关注Proceduce FP-treeCount
输入候选项c；输出:c 的支持度
(1)对c 中的每个维度项，按支持度递增的顺序排序;
(2)对于c 中的第一个维度项，通过寻FP-树结构中的项头表，出与维度项名称相同的节点p;
(3)q =p.link;(4)count=0;
(5)while q is not null{
(6)if (c 出现在q 的前缀路径上)(7)count +=q.count;(8)q =q.link;}(9)return count;
FP-treeCount 算法表明可以通过查相关节点以及前缀路径，计算得到候选集的支持度，从而大大减少了数据立方体的扫
描次数。
3实验结果分析
本实验数据主要来源于某移动通信公司CRM 数据仓库，数据取自2008年6月份的用户业务订购记录，依据该数据采用
Microsoft 的Analysis Service，分地区，消费水平，业务三个维度构建数据立方体。其前台开发平台采用Visual C++6.0，对Apri -ori_cube,FP-growth_Cub 和Apriori-growth_Cube 三种算法进行对比分析，实验结果如下所示:
图4Apiori_cube 与Apriori-growth_Cube 对比分析
(注：横坐标表示事实表的行数，纵坐标表示运行时间，其单位为(sec))
图4表示的是当数据立方体大小变化时,Apriori_cube 算法和Apriori-growth_Cube 算法运行时间的变化曲线，从中可以看出，两种算法的运行时间都随着数据立方体增大而增大，其中,Apriori_cube 算法受数据立方体大小的影响较大，当数据立方体很小时，两种算法差不多，虽然Apriori_cube 算法需要多次遍历数据立方体，但Apriori-growth_Cube 算法构造树结构也需要一定时间。随着数据立方体增大,Apriori-growth_Cube 算法的运行时间增长地比较缓慢，而Apriori_cube 算法得运行时间急剧增长。
图5FP-growth_Cube 与Apriori-growth_Cube 对比分析图5表示的是当数据立方体大小变化时,FP-growth_Cube 算法和Apriori-growth_Cube 算法运行时间的变化曲线，从中可以看出，两者之间的区别不大，但是Apriori-growth_Cube 算法需要的内存空间比FP-growth_Cube 小，因为Apriori-growth_Cube
算法不需要产生大量的频繁模式基和条件树。
4结论
数据挖掘中的关联规则挖掘得到了人们极大的重视，并且已经在商业领域广泛应用。多维关联规则作为关联规则的一种重要形式，在近年来也得到了很快的发展。本文首先分析了传统的多维关联规则算法的特点，然后针对传统算法的优缺点，提出了一种优化的多维关联算法。
本文作者的创新点：本文重点对基于OLAP 环境的多维关联规则算法进行研究，根据传统算法在数据立
方体应用的特点，本文提出了一种优化的多维关联算法,Apriori-growth_Cube，其将Apriori_cube 算法和FP-树结构有机地结合起来，通过实验验证,Apriori -growth_Cube 算法在运行时间效率上优于
Apriori_cube 算法，在存储空间方面优于FP-growth_Cube 算法。参考文献
[1]沈国强，覃征.一种新的多维关联规则挖掘算法[J].小型微型计算机系统,2006,27(2):12-14数据结构与算法论文
[2]陈佩佩.OLAM 体系结构和算法的研究及应用[J].微计算机信息.2008,9-3:3-6.
作者简介：吴昊(1968-1)，男，汉族，湖南大学计算机科学与技术学院，副教授，硕士生导师，研究方向：数据库，数据挖掘；彭硕(1985-10)，女，汉族，湖南大学计算机科学与技术学院硕士研究生，研究方向：数据库，数据挖掘。
Biography:PENG Shuo,1985-10,female,Han nationality,postgraduate of master of computer science,study in database,data mining.
(410082长沙湖南大学计算机与通信学院)吴昊彭硕
(College of Computer and Commuication,Hunan University,Changsha Hunan 410082,China)Wu Hao Peng Shuo 通讯地址:(410082长沙湖南大学南院18舍406-4)彭硕
(收稿日期:2009.11.16)(修稿日期:2010.02.16)
(上接第36页)
本文作者创新点：本文主要阐述了基于B/S 结构的森林景观管理系统。本系统应用于塔河林业局，实现了森林景观的自动化管理，提高了森林景观管理的工作效率。
参考文献
[1]邬伦，刘瑜，马修军.地理信息系统原理方法和应用[M].北京：科学出版社,2001:7-12
[2]ArcGIS Server Administrator and Developer Guide[R].ESRI Corp,2004
[3]宋丽，王霓虹，李瑞改.基于GIS Server 森林景观管理系统框架研究[J].微计算机信息,2009,1-1:229-231
作者简介：宋丽(1975-)，女，硕士研究生，牡丹江师范学院计算机科学与技术系，副教授，研究方向：数据库技术.
Biography:SONG Li(1975-),female,postgraduation,Department of Computer Science and Technology,
Mudanjiang Normal University,Associate Professors,Research area:Technology of Data Base .（157012黑龙江牡丹江师范学院）宋丽
(Mudanjiang Normal University,Mudanjiang,Heilongjiang,157012,China)SONG Li
通迅地址:(157011黑龙江省牡丹江市兴平路预备役军官小区2号楼3单元202,5#)宋丽
(收稿日期:2009.12.07)(修稿日期:2010.03.07)
101--

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。