关联规则挖掘算法探讨

摘要：关联规则挖掘是数据挖掘领域的重要课题之一，本文对数据挖掘中的关联规则挖掘算法进行研究，总结出算法的性能缺陷，展望了关联规则挖掘的未来发展方向。

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

1、引言

在数据挖掘所有的知识模式中，关联规则模式是非常重要的一种，也是最活跃的一个分支。采用关联模型比较经典的例子是“啤酒和尿布”的案例，在美国，一些年轻的父亲下班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息进行挖掘，发现在购买婴儿尿布的年轻父亲中，有30％-40％的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是销售额明显增加了。这一案例中的关联规则可以表示为：购买了项目A和B的顾客中有某一百分比的人又买了C和D。从这些规则可找出顾客购买行为模式，从而应用于商品货架设计、生产安排、针对性的市场营销等。

2、相关概念

定义2.1 关联规则数据挖掘的数据集记为D（一般为事务数据库）， ={t1，t2，…，tk,，…，tn}, tk= {i1，i2，…，ip，…，im}, tk (k=1，2，…，n)称为事务，ip (p=1，2，…，m)称为项目。

定义2.2 设I={i1，i2，…，im}是D中全体项目组成的集合，I的任何子集A称为D中的项目集,A=Ｋ称集合A为K项目集。设tk和A分别为Ｄ中的事务和项目集，如果Ａ?坳tk，则称事务tk包含项目集A。每一个事务都有一个唯一的标识符，称为TID。

定义2.3 数据集D中包含项目集A的事务数称为项目集A的支持数，记为?滓?琢。项目集A的支持度记为：sup port(A)，及概率P(A)。

sup port(A)= ×100% （或 sup port(A)= ）

其中D是事务数据库D的事务数，若support(A)不小于指定的最小支持度（minsupport），则称A为频繁项目集，否则称为非频繁项目集。

定义2.4 若A、B为项目集，且A∩B = ?准，蕴含式A?圯B称为关联规则。关联规则A?圯B的支持度记作：sup port(A?圯B)

sup port(A?圯B) = sup port(A∪B) = P (A∪B)

关联规则A?圯B的可信度为D中事务包含A的事务的同时也包含B的百分比，即条件概率P(B| A)。记作 confidence (A?圯B) = ×100%

定义2.5 若规则的可信度confidence (A?圯B)≥min confidence，且支持度sup port(A?圯B)≥min sup port，则称关联规则A?圯B为强关联规则，否则称为弱关联规则。

关联规则挖掘就是找到支持度和可信度均大于用户指定的最小支持度和最小可信度的规则。

3、Apriori算法

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，它是一个很有影响的关联规则挖掘算法。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。关联规则的挖掘可以分两步来进行：

（1）找出所有的频繁项集：根据前面定义，这些项集出现的频率不小于预先定义的最小支持度。

（2）由频繁项集产生强关联规则：根据前面定义，这些规则的支持度和可信度不小于最小支持度与最小可信度。这两步中，第二步比较容易，挖掘关联规则的总体性能主要是由第一步决定。

Apriori算法主要就是基于第一步中的操作处理。它是R.Agrawal和R.Srikan提出的布尔关联规则挖掘频繁项集的原创性算法。

算法步骤如下：

第一步：初始化数据库，根据条件初始化数据库，扫描事务数据库，从中找出所有的项集长度为k=l的项集，形成候选1项集C1,得出每项的支持度，跟最小支持度进行比较，支持度大于minsupport，形成频繁1项集L1；

第二步：根据频繁k项集产生候选（k+1）项候选项集Ck+1，如果Ck+1≠?准进入下一步，否则循环结束；

第三步：扫描数据库，以确定每个候选项集的支持度；

第四步：删除候选项中支持度小于minsupport的候选项，形成（k+1）项频繁项集Lk+1；

第五步：k=k+1，转入第二步；

第六步：由得到的所有频繁项集产生强关联规则。

4、算法性能缺陷

第一个缺陷是在多次扫描事务数据库D的项目集时，需要很大的I/O时空开销。对于每次k循环，候选项目集Ck中的每个元素都必须通过全部扫描事务集数据库D一次来计算其支持度，因此产生巨大的I/O时空开销。

第二个缺陷是可能产生非常庞大的候选项目集。由Lk-1产生候选项目集Ck是指数增长的，产生如此多的候选项目集对执行时间和内存空间都将是一种严峻的挑战。

第三个缺陷是现有关联规则挖掘算法主要是基于“可信度-支持度”的结构。在实际应用中，仅仅考虑可信度和支持度是远远不够的，容易产生误导，挖掘出没有实际意义的规则。

第四个缺陷是关联规则挖掘算法忽视了反面事例的情况。举例说明：我们无法挖掘出“交易记录中56%买了咖啡不买奶粉，买了咖啡的人中不买奶粉的可能性为40%”，C代表咖啡，M代表奶粉，则规则c?圯M的支持度为56%，可信度为40%。这条规则在现实中很可能存在，并且对商家来说也是一条有用的信息，但是Apriori算法并不能挖掘出这些有用的反面规则。

5、发展方向

关联规则是数据挖掘中一个非常活跃的研究领域，国内外在关联规则挖掘方面的研究也已经取得了很大的进步，但关联规则挖掘技术在有些方面仍然存在着不足，需要进一步研究和改进。

（1）增强与用户的交互性

目前关联规则的衡量方法主要是基于支持度——可信度的标准，事先定义好最小支持度和最小可信度，然后通过扫描数据集找出所有的频繁项目集，并根据频繁项目集生成关联规则，最后将挖掘出的关联规则提交给用户。如果结果不符合用户的需求，则需要修改最小支持度、最小可信度等，并再次运行关联规则挖掘算法，用户要得到满意的结果可能需要上述过程的多次反复，因此需要较长时间。如何增强关联规则挖掘算法与用户的交互性，是以后的一个重点研究方向。

（2）提高挖掘的效率

数据库的规模不断增大，不仅加大了挖掘算法的搜索空间，而且也增加了盲目挖掘的可能性。为了保证数据挖掘算法的高效性，并且能从大量数据中提炼有用信息，算法的运行时间一定是可预测的和能够接受的。因此必须结合相关领域知识，去提取与我们发现任务有关的数据，删除无用的数据，有效地降低问题的维数，提高挖掘算法的效率。

（3）融合其它技术

许多其它领域的研究者从事关联规则问题的研究，使得关联规则挖掘可以吸收其它领域的研究成果。如关联规则挖掘技术与数据立方、数据仓库等数据库技术的融合将推动关联规则挖掘技术进一步实用化，关联规则与其它技术的进一步深入结合，将可以提高其应用能力和挖掘效率。

（4）可视化挖掘技术

数据挖掘技术本身具有一定的复杂性，除了专业人员以外一般用户很难掌握，用户很难理解得到的结果。图形和图像的表现方式，用户更加容易理解和接受，可视化数据挖掘技术（VDM）正在兴起，如何将可视化技术应用于数据挖掘是今后的一个研究重点。

6、结束语

数据挖掘仍然是一个不断发展的技术，因此，关联规则挖掘技术的发展也从未停止，随着新的情况的出现，关联规则技术的应用将更加广泛，其在未来还有很大的发展空间。

参考文献

[1] Jiawei Han，Micheline Kamber.数据挖掘概念与技术【M】.机械工业出版社，2007

[2] 许娅.关联规则更新算法研究与应用[D].合肥工业大学，2009.5

作者简介：

赵晨（1982-），西安电子科技大学在读研究生，讲师，工作单位：陕西交通职业技术学院，从事计算机专业教学工作与研究。