基于关联规则的数据挖掘算法研究

摘要：首先介绍了关联规则的基本概念，然后详细地介绍了Apriori算法，同时也指出了Apriori算法的一些不足。针对这些不足提出了解决方法，描述了几种优化算法。最后对关联规则研究范围进行了拓展。

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

中图分类号：TP274文献标识码：A文章编号：1009-3044(2007)03-10593-01

1 引言

随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识手段，导致了“数据爆炸但知识贫乏”的现象。

数据挖掘（Data Mining），又称数据库中的知识发现（Knowledge Discovery in Database），在最近几年里已被数据库界所广泛研究，其中关联规则（Association Rules）的挖掘是一个重要的问题。

2 关联规则的基本概念

2.1 关联规则的基本思想

关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。

关联规则的基本思想：一是找到所有支持度大于最小支持度的频繁项集，即频集。二是使用第一步找到的频集产生期望的规则。其核心方法是基于频集理论的递推方法。

2.2 关联规则挖掘的算法

挖掘关联规则，就是在大型数据库中发现所有可能有用的或者用户感兴趣的强关联规则的过程。按照它的基本思想，挖掘关联规则一般可以分为以下两个步骤：

(1)求出支持度项集的集合（Frequent Sets），即找出目标数据库中包含的所有频度项集。

(2)使用各频度项集生成相应的强关联规则。

不难看出，在上述两步中，第二步的工作是比较简单直接的。

2.3 Apriori核心算法分析

为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：

(1) L1 = {large 1-itemsets};

(2) for (k=2; Lk-1¹F; k++) do begin

(3) Ck=apriori-gen(Lk-1); //新的候选集

(4) for all transactions tÎD do begin

(5) Ct=subset(Ck，t); //事务t中包含的候选集

(6) for all candidates cÎ Ct do

(7) c.count++;

(8) end

(9) Lk={cÎ Ck |c.count³minsup}

(10) end

(11) Answer=∪kLk;

首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。

3 频集算法的几种优化方法

针对Apriori算法存在以上一些主要的不足，要提高Apriori的效率，可以从以下两个方面去做工作：一是减少对数据库的扫描次数；二是生成较小的候选频繁项集。目前许多专家学者通过大量的研究工作，提出了一些改进的算法以提高Apriori的效率。

(1)散列技术。该算法由Park等在1995年提出。通过实验发现寻找频繁项集的主要计算是在生成频繁2-项集L2上，Park就是利用这个性质引入散列技术来改进产生频2-项集的方法。

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

(3)杂凑技术。一个高效地产生频集的基于杂凑的算法由Park等提出。通过实验我们可以发现寻找频集主要的计算是在生成频2-项集L2上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。

(4)划分技术。Savasere等设计了一个基于划分的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。

(5)抽样技术。基于前一遍扫描得到的信息，对此仔细地组合分析，可以得到一个改进的算法，Mannila等先考虑了用采样来解决这一点。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但产生的结果存在数据扭曲。

(6)动态项集计数。Brin等人给出该算法。动态项集计数技术将数据库划分为标记开始点的块。不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。该算法需要的数据库扫描比Apriori少。

4 关联规则研究范围的拓展

4.1 在数据挖掘类型方面的拓展

从挖掘的范畴看，可以分为数值型关联规则和布尔型关联规则。布尔型关联规则的挖掘相对简单，数值型关联规则挖掘则要复杂的多。处理数值型关联规则的算法大致分为两种：一种是将连续的数值型区间分割为若干离散的区间，将离散区间的值映射为连续的整数，以布尔型数据挖掘算法为基础，进行数据挖掘；另一种是引入模糊数学的理论，进行模糊关联规则的挖掘。前一种方法的主要问题是在分割连续的数值型区间时会产生一对相互矛盾的命题。即：如果区间分割过大，将导致规则的置信度下降；如果区间分割过小，则导致规则的支持度下降。

4.2 在数据挖掘空间方面的拓展

在数据挖掘空间上，关联规则还从简单的单维关联规则挖掘扩展到多维关联规则的挖掘。在关联规则中，涉及两个或者多个维或者谓词的关联规则称为多维关联规则。例如，年龄（“20，29”）∧职业（“学生”）∧购买（“台式计算机”）。在这一关联规则中，年龄和职业是顾客的两个属性维。

4.3 在数据挖掘层次方面的拓展

具有概念分层的关联规则挖掘产生的规则称为多层关联规则。在多层次关联规则的挖掘中，可能存在冗余的关联规则。例如，已知IBM计算机占整个计算机销量的25%，规则A"购买计算机"购买打印机[support＝8%，confidence＝72%]"；规则B"购买IBM计算机"购买打印机[support＝2%，confidence＝70%]"。显然，由已知条件和规则A可以近似推导出规则B，因此，从规则B中没有获得新的不确定性的消除，其信息量为0。规则A和规则B是重复的，称这种重复为规则的冗余。在多层次的关联规则挖掘中，需要对这种冗余进行检查。

4.4 在并行关联规则数据挖掘方面的拓展

随着数据量的不断增长、维数的越来越高、数据的不对称性、动态负载的平衡、并行的数据库管理系统与文件系统等，所有这些都是目前在并行数据挖掘中尚需要解决的问题。随着大规模并行计算在数据挖掘中的应用，由于挖掘系统本身的原因，并行数据挖掘无法实现任意程度的并行。

5 结束语

今天，数据量每天都在增长，其中隐含的规则也在不断变化着，如何提高关联规则挖掘和更新算法的效率是一个迫切需要解决的问题。对于关联规则的发展，可以在以下等方面进行更加深入的研究。如在处理极大量的数据时，如何提高算法效率的问题；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的过程中，提供一种与用户进行交互的方法，与用户的知识领域相结合；生成结果的可视化方面等等。

参考文献：

[1]毛国君, 等. 数据挖掘原理与算法[M]. 北京:清华大学出版社,2005.

[2]毕建欣, 张岐山. 关联规则挖掘算法综述[J]. 中国工程科学,2005,7(4):88-94.

[3]王创新. 关联规则提取中对Apriori算法的一种改进[J]. 计算机工程与应用, 2004(34):183-185.

[4]李清峰, 杨路明, 张晓峰, 等. 数据挖掘中关联规则的一种高效的Apriori算法[J]. 计算机应用与软件,2004,21(12):84-86.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。