浅析关联规则及其Apriori算法

摘要:为有助于人们深入研究关联规则挖掘技术,该文给出了关联规则及其相关术语的定义,阐述了关联规则apriori算法,总结了经典算法的优化方案以及关联规则在经典算法基础上的扩展应用。

关键词:关联规则;Apriori算法;优化;数据挖掘

中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)22-6268-02

Brief Analysis of Associative Rule and Apriori Algorithm

ZHANG Feng-yun

(Computer Science and Technology Institute, China University of Mining and Technology, Xuzhou 221116, China)

Abstract: The concept of the associative rule and its relative definitions are given in the paper, which helps us to further understand the associative rule mining technology. The Apriori algorithm of the associative rule is presented. Then the optimized methods of classic algorithms are summarized and the extended application of the associative rule is discussed.

Key words: associative rule; Apriori algorithm; optimize; data mining

关联规则挖掘是在海量的数据中发现数据项之间的关系,是数据挖掘领域中研究的热点问题,最早是由Agrawal等人于1993年提出。他们提出这一观点是针对货蓝问题进行分析,目的是为了发现交易数据库里不同商品之间的相关关系。

1 关联规则理论

1.1 定义

关联规则。设I = { i1 , i2 , …, im }是项的集合,其中的元素ij ( j = 1 , 2 , …, m) 称为项( item) 。记D为事务T的集合,事务T是项的集合,并且T?哿I 。设X是一个I中项的集合,如果X?哿T,那么称事务T包含X。

一个关联规则是形如X=>Y的蕴涵式,这里X?奂I , Y?奂I,并且X∩Y =?I。关联规则X=>Y 成立的条件是:

1) 它具有支持度S,即数据库D中至少有S %的记录包含X∪Y , 它是概率P (X∪Y )。

2) 它具有置信度C,即在数据库D中包含的X记录至少有C % 同时也包含Y,这是条件概率P (Y |X )。

support(X=> Y ) = P (X∪Y ) = | T: X∪Y?哿T, T∈D | / |D |

confidence (X=>Y ) = P (Y |X) =| T: X∪Y?哿T, T∈D | / | T: X?哿T, T∈D |

其中,支持度定义了项目在整个数据库中所占的比例;置信度定义了发现规则的强度。他们分别反映发现规则的有用性和确定性,习惯上将关联规则表示为X=>Y( S % ,C %) 。

给定一个事务集D,挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度(minsup) 和最小置信度(minconf) 的关联规则。同时满足最小支持度阈值(min_sup) 和最小置信度阈值(min_conf) 的规则称做强规则。

1.2 关联规则挖掘的一般步骤

关联规则挖掘的基本任务就是首先通过用户指定最小支持度和最小置信度,挖掘出大型数据库中的强关联规则。可分成两个步骤:

1) 挖掘频繁项集:通过用户给定的最小支持度,找出所有频繁项集,即支持度不小于最小支持度的所有项集。

2) 生成关联规则:使用频繁项集生成置信度大于预先给定的最小置信度阀值的关联规则。

挖掘关联规则的整个性能主要是由第一步(挖掘频繁项集)决定的,所以有效地计算频繁项集就成了关联规则挖掘算法研究的重点。

2 经典算法Apriori

Apriori算法是1993年由Agrawal等设计的一个经典算法[1-2],通过对数据库D的多趟扫描来发现所有的频繁项集。

2.1 Apriori算法基本思想

该算法采用“逐层搜索”的迭代方法,用k-项集生成(k+1)-项集。首先,扫描数据库计算出频繁1-项集的集合(记为:L1);然后,执行下面的迭代过程计算频繁k-项集,直到生成频繁k-项集的集合(记为:Lk)为空:

①连接:Lk-1进行自连接运算,生成候选k-项集的集合,记为C k。所有的频繁k-项集都包含在C k集合中。

②剪枝:①生成的C k是Lk的超集,扫描数据库计算C k中每个候选项目集的支持度,支持度大于用户给定最小支持度的候选k-项目集就是频繁k-项目集。

通过上述的迭代过程,可以发现项目集I在给定数据库D中满足最小支持度的所有频繁项目集。

2.2 算法分析

Apriori算法在执行“连接-剪枝”过程中,需多次扫描数据库。寻找每个k -频繁项集( k = 1 ,2 , …,m) 都需要扫描数据库一次,共需要扫描m次。因此当数据库或者m太大时, 算法的耗时太大甚至无法完成,并且在迭代过程中,候选项集Ck是以指数速度增长,Lk-1自连接会产生大量的候选k-项集,例如有104个1-项集,自连接后就可产生约107个候选2-项集。这些都严重影响了Apriori算法的效率。

3 Apriori 算法的优化和改进

Apriori算法是一种多层迭代算法。如果数据集中项数为n,则Apriori 算法将要计算2n-1个项目,当n较大时,会产生组合爆炸问题。各国学者先后以Apriori 算法为基础,在算法的效率和算法的实现上进行了改进:

3.1 动态项集计数方法

Brin等人提出了动态计数DIC(dynamic itemset counting)方法。其基本思想是在对k-项集进行支持度计算的同时也对某些(k+1)-项集进行支持度计算。该技术动态地评估已被计数的所有项集,不像Apriori算法仅在每次完整的数据库扫描之前确定新的候选,它可以在任何点添加,一旦一个项集的所有子集被确定为是频繁的,就可以启动对该项集支持度的计算。因此,该算法所需的数据库扫描次数要比Apriori算法少。

3.2 基于散列表的方法

Park等人于1995年提出。其基本思想:在由C1中的候选1-项集产生频繁1-项集L1时,可使用散列函数将每个交易的所有项集散列到不同的桶中,并对对应的桶进行计数,通过桶的计数寻找候选频繁项集。这种技术可以大大压缩待考察的k-项集,尤其有利于改进频繁2-项集的发现效率。

3.3 分区方法

Savasere等人提出了一种发现频繁项集的划分算法,这是一种常见而有效的算法设计思想。该算法把数据库分成小块,然后逐次调入内存,第一遍扫描时,根据支持度在每个子块上的分配,对每个子块应用Apriori算法;第二遍扫描,着眼于全局频繁项目集的搜索。每个全局频繁项目集必在某个子块上是频繁的,根据这个性质,第二遍只在第一遍扫描所得频繁项目集的结果中进行搜索。该算法可以高度并行计算,但是进程之间的通信是算法执行时间的主要瓶颈。

3.4 选样

基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息,仔细地组合分析,可以得到一个改进的算法,Mannila等先考虑了这一点,他们认为采样是发现规则的一个有效途径。

随后,Toivnen进一步发展了这个思想。它不是将算法直接作用于整个数据库,而是作用于数据库的样本,然后扫描整个数据库,以确定样本上的频繁项目集是否在整体上也频繁。Toivonen的算法显著地减少了I/O代价,但是一个很大的缺点就是产生的结果不精确,存在数据扭曲(data skew)。

3.5 事务压缩

Agrawal等提出压缩进一步迭代扫描的事务数的方法。因为不包含任何k项集的事务,不可能包含任何(k+1)项集,可对这些事务加上删除标志,扫描数据库时不再考虑。

4 关联规则的扩展

4.1 多层次关联规则

数据项可以有概念层次,如果将数据项沿概念层次向上提升,则会使多个数据项合并为一个新的概念,从而增加了支持度。例如牛奶和啤酒沿概念层次向上提升为饮料。

对于许多应用,由于数据的稀疏性,在低层或原始层的数据项之间很难找出强关联规则。例如:“面包=>牛奶”可能没有足够的支持度,而“面包=>饮料”则可能是一个强关联规则。

挖掘多层次关联规则一般有两种途径:一种是把单层次关联规则挖掘算法直接应用于多层次;另一种是在不同的层次应用不同的支持度阀值和置信度阀值。

4.2 多维关联规则

传统的关联规则算法讨论的都是基于同一个字段之间的关系,但实际上很多规则都是在多维数据库中挖掘的。例如,规则:年龄(x,“25,35”),职业(x,“3000,4000”)=>购买(x,“计算机”)中,它涉及年龄、职业、购买这三个维度,是多维关联规则。

现在,比较流行的做法是建立数据立方体存储多维数据,然后采用Apriori算法分别求出各个维的频繁项集。

4.3 定量关联规则

传统关联规则算法处理的只是布尔属性的情况,对于有多个值的数值属性和类别属性,人们提出了定量关联规则挖掘问题。

处理数值型关联规则的算法大致分为两种:一种是将连续的数值型区间分割为若干离散的区间,将离散区间的值映射为连续的整数,以布尔型数据挖掘算法为基础进行数据挖掘;另一种是引入模糊数学的理论,进行模糊关联规则的挖掘[3-4]。

4.4 加权关联规则

为了反映各个项目的重要性不同,可以给每个项目分配一个反映其重要性程度的权值。目前加权关联规则主要有两种:第一种是项加权关联规则,即引入项权重,但项权值在数据库的各个事务中固定不变。第二种是项完全加权关联规则,其认为各个项在数据库及各个事务中的重要性都不同,项集的权值随着数据库中事务记录不同而各异。

4.5 序列模式分析

在典型的关联规则中,各个事务之间没有先后顺序关系,但实际应用中,经常会用到序列关系。序列模式挖掘是指从序列数据库中寻找频繁子序列列作为模式的知识发现过程。

5 总结

关联规则算法的研究,人们已经探索了许多各种各样的不同方法。目前研究主要集中在算法的改进、数据挖掘的范畴等方面。因此,提高算法效率,减少算法的时间和空间复杂度是基本方向。由于数据挖掘的对象有布尔数据、数值型数据、字符型数据等多种数据类型,因此需要改进原有算法或者提出新算法来解决多种类型数据的挖掘问题和多维、多层次的数据挖掘问题。实践证明,没有一种挖掘算法对所有类型的数据都优于其他算法,每种算法都有他具体的适应环境[6],所以,熟知不同算法的不同特征和适用条件,可使研究者明确算法的改进点和研究方向,更易于使用。

参考文献:

[1] 吴建芹,吴建红,张雷.基于CWM的企业数据仓库体系结构设计[J].计算机工程与应用,2002,38(21):202-204.

[2] 蔡伟杰,张晓辉.关联规则挖掘综述[J].计算机工程,2001,l27(5).

[3] 邓景毅.关联规则数据挖掘综述[J].电脑学习,2006(3):4-5.

[4] 程岩,卢涛,黄梯云.在数据库中挖掘定量关联规则的方法研究[J].管理科学学报,2001,4(4):41-48.

[5] 陆建江.加权关联规则挖掘算法的研究[J].计算机研究与发展,2002(10):1281-1286.

[6] 秦亮曦,史忠植.关联规则研究综述[J].广东大学学报:自然科学版,2005,30(4):310-317.