关联分析频繁模式挖掘Apriori算法简介及其应用

摘 要：随着信息技术的发展，数据量变得非常庞大，如何从海量数据中找到有用、有关联的信息，数据挖掘技术应运而生。Apriori算法作为重要的关联分析算法在这些年得到了广泛应用。主要介绍了关联规则的基本模型、Apriori算法的原理以及如何使用Apriori算法挖掘出有意义的关联规则。

关键词：数据挖掘；关联规则；Apriori算法

中图分类号：TP312 文献标识码：A 文章编号：16727800（2012）011004902

________________________________________

作者简介：陈捷（1980-），男，硕士，泰州师范高等专科学校数理信息学院讲师，研究方向为计算机应用。1 关联规则基本模型

数据挖掘就是要从海量的数据中发现有价值数据的过程。而关联规则挖掘则是寻找数据项中的微妙联系，判断出哪些事件一起发生。近年来关联规则挖掘已经成为数据挖掘的热点，Aprioir算法及其优化方法就是典型研究成果。

关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。这一规则首先被Agrawal、Imielinski and Swami在1993年的SIGMOD会议上提出。

设I={i1，i2，i3，…，im}是由m个不同的数据项目组成的集合，其中的元素称为项（item），项的集合称为项集，包含k个项的项集称为k项集，给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的子集，即T I，T有一个唯一的标示符TID；当且仅当XT时，称交易T包含项集X；那么关联规则就如“X=>Y”的蕴含式表示当XI，YI，X∩Y=F，即表示满足X中的条件的记录也一定满足Y。

关联规则在D中的支持度（Support）是D中事务同时包含X、Y的百分比，即概率；置信度（Confidence）是包含X的事务中同时又包含Y的百分比，即条件概率。为发现出有意义的关联规则，必须给定两个阈值，即最小支持度和最小置信度。前者即用户规定的关联规则必须满足的最小支持度，它表示一组物品集在统计意义上需满足的最低程度；后者即用户规定的关联规则必须满足的最小可信度，它反映了关联规则的最低可靠度。一般称满足一定要求的规则为强规则，通常称满足最小支持度和最小置信度的关联规则为强关联规则。最小支持度记为minsup，最小置信度记为minconf。

2 Apriori算法

Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。Apriori算法将发现关联规则的过程分为两个步骤：第一步，通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定阈值的项集；第二步，利用频繁项集构造出满足用户最小置信度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个算法计算量的绝大多数。具体表述如下：

L1={large 1itemsets}；∥发现1项频集

For（k=2；Lk1=；k++） do begin

Ck=apriori_gen（lk1，minsup）；∥根据k1项频集产生新的k项候选集

For all transactions t∈D；∥遍历数据库确定每个候选集的支持频度

Ct=subset（ck，t）；∥事务t中包含的候选集

For all candidates c∈Ct do

c.count++；

Lk={c∈Ck|c.count≥minsup}

return L=UKLK；

在每一次遍历中，利用上一次遍历产生的大序列来产生候选序列，并在一次遍历中计算相应的支持度（Support）。在遍历的最后，候选序列的支持度用来决定大序列（剔除支持度低的候选序列）。

Apriori_gen函数以Lk1作为输入参数，返回所有大k项集的集合Lk，具体实现如下：

第一步：联合，将两个项连接在一起

Insert into Ck

Select p.item1，p.item2，…，p.item（k1），q.item（k1）

From Lk1p，Lk1q

Where p.item1=q.item1，…p.item（k2）=q.item（k2），p.item（k1）

然后，是prune（修剪）步，即对任意的c，c∈Ck， 删除Ck中所有那些（k1）维子集不在Lk1中的项目集，得到侯选项目集Ck，表述为：

For all itemset c∈Ck do

For al l （k1）维子集s of c do

if （s不属于Lk1） then

delete c from Ck

3 Apriori算法举例应用

现有A、B、C、D、E 5种商品的交易记录（见图1），找出所有频繁项集，假设最小支持度≥50%，最小置信度≥50%。

图1 交易记录

对于频繁项集{A、C、E}，它的非空子集有{A}、{c}、{E}、{A、C}、{A、E}、{C、E}。由此获得5种商品的关联规则及其置信度。

表 由表1可知同时买了C、E两类商品后，必然会买A类商品。同理，同时买了A、E两类商品后，也必然会购买C类商品。所以通过关联规则Apriori算法挖掘后建议商家将A、C、E三类商品摆在一起销售，以获得更大的销售量。

4 结语

总之，利用Apriori算法能有效挖掘出人们真正感兴趣的、有价值的信息。不过，Apriori算法虽然具有不错的挖掘效果，也依然存在一些不足。首先，它需要多次扫描数据表，加大了I/O的负担，其次产生了大量的频繁集，系统负担加重，效率降低。一些改进的频集算法陆续设计出来，其中FPgrowth算法就是其中的佼佼者，它采取“分而治之”的策略，将提供频繁集的数据库压缩成一棵频繁模式树（FPTree），再将FPTree分成一些条件库，然后对这些条件库进行挖掘。实验表明，FPGrowth算法在效率上比Apriori算法有了很大的提高。

参考文献：

[1] 赵旭俊.基于频繁模式树的正负项目集挖掘[J].太原科技大学学报，2012（1）.

[2] 刘勇，李建中，高宏.从图数据库中挖掘频繁跳跃模式[J].软件学报，2010（10）.

[3] MARGARET H.Dunham.数据挖掘教程[M].北京：清华大学出版社，2008.

[4] 王景让.Apriori算法在布尔型关联规则领域的应用[J].制造业自动化，2009（9）.