基于频繁项目集链式存储方法的关联规则算法

尹士闪，马增强，毛晚堆

（1.石家庄铁道大学 教务处，河北 石家庄050043；2.石家庄铁道大学 电气与电子工程学院，河北 石家庄050043；3.石家庄铁道大学 工程训练中心，河北 石家庄050043）

0 引 言

数据挖掘 （data mining）是一门交叉学科，是从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有兴趣知识的过程。关联规则挖掘则是数据挖掘中最活跃的研究方法之一［1－3］。Agrawal等于1993年首先提出了关联规则问题，随后他们建立了项目集格空间理论，提出了著名的Apriori算法［4－14］。Apriori其核心算法就是根据频集理论的一种逐层迭代搜索方法，通过项目集元素数目不断增长来逐步完成频繁项目集的发现。算法过程中需要多次扫描事务数据库，并产生庞大的候选集来完成频繁项目集的发现，如此大的候选集对时间和存储空间都是一种挑战。针对Apriori算法的这些缺点，近年来，许多学者对此提出了许多不同的算法。比较典型算法有DHP，Partition，Sampling，FP－tree。在这些研究基础之上，本文提出了一个有效生成频繁项目集的算法，它是采用一种链式存储结构用来存储频繁项目集，并生成最大频繁项目集，通过改变事务的存储方式和增加链式存储方式能够高效的生成最大频繁项目集，避免了多次扫描事务数据库，减少了庞大的候选集的生成，从而提高了效率。

1 关联规则基本概念及理论

定义1（项目） 关联规则挖掘的数据集记作D（D为事务数据库），D＝ ｛t1，t2，…，tn｝，tk＝ ｛i1，i2，…，ij｝（k＝1，2，…，n）为一条事务；tk中的元素ij（j＝1，2，…，p）称为项目 （Item）。

定义2（项目集） 设I＝ ｛i1，i2，…，im｝是事务数据库D中全体项目组成的集合，I的任何子集X称为D的项目集 （Itemset），｜X｜＝k称集合X为k项目集。……