Academic Research学术研究www.cismag.com.cn84
陈宇王廷， 张保稳， 何德全（上海交通大学，上海 ２００２４０）
【摘 要】关联规则的发现是数据挖掘的一个重要方面，由于信息数据的急剧增长，面对浩如烟海的海量数据，为把这些数据转换成被人类充分利用的有价值信息，对关联规则挖掘算法进行研究就显得异常重要。总结了当今各种关联规则挖掘算法并对其加以分类，阐述了各类关联规则算法的特点，列举算法之间的差异，在时间和空间上进行比较，并且在此基础上对关联规则挖掘的未来趋势进行了分析和展望。【关键词】数据挖掘；关联分析；Aprior算法；频繁项集【中图分类号】TP181 【文献标识码】A 【文章编号】1009-8054(2010) 02-0084-04
Research Progress on Association AnalysisCHEN Yu-ting, ZHANG Bao-wen, HE De-quan(Shanghai Jiaotong University, Shanghai 200240, China)【Abstract】The discovery of association rule is an important aspect of data mining. Due to the tremendous increase ofinformation data and in order to transform these raw data into valuable information which could be best used by thepeople, it's extremely important to study the mining algorithm. The paper summarizes various prevailing association rulemining algorithms, classifies them into four different types and makes comparisons between among various types ofalgorithms. And based on this, the future developments of the association rule mining algorithms are analyzed and forecasted.【Keywords】data mining; association analysis; Apriori; frequent itemset
关联分析研究的进展
收稿日期：２００９－０８－１７作者简介：陈宇王廷，１９８５年生，男，上海交通大学在读硕士，研究方向：数据挖掘、关联分析；张保稳，男，上海交通大学副教授，研究方向：数据挖掘；何德全，男，中国工程院院士，上海交通大学信息安全工程学院院长，研究方向：信息安全。
０ 引言当今世界正处在一个信息迅速发展的时代，信息数量急剧增长，面对浩如烟海的海量数据，把这些数据转换成被人类充分利用的有价值信息的强烈需求，激发了数据挖掘技术的产生，其中关联规则的挖掘是目前数据挖掘领域中研究最为广泛的课题之一[1]。强有力的关联规则挖掘算法，可以帮助决策者从海量数据中发现重要的数据模式，从而提取有价值的知识，逾越丰富数据到有用信息之间的鸿沟，对商业决策和科学研究做出巨大贡献。１ 关联规则挖掘文中在对典型的关联规则挖掘技术进行分析后，对关联分析进行了归纳。关联规则挖掘技术从整体上分为如下几类：按照事务数据集数据类型的不同可以划分为二值型关联规则挖掘与数值型关联规则挖掘；由于数据挖掘处理的多是大规模的数据库，一个挖掘任务的完成经常需要较长的时间，故按照处理器处理数据的方式不同可以划分为串行关联规则挖掘与并行关联规则挖掘；由于数据分布的分散性，有价值的模式经常出现在较高的概念层中，仅从较低的概念层上很难发现有用的模式，故按照是否对事务数据集进行概念分层又可以划分为单层次关联规则挖掘与多层次关联规则挖掘；由于当前事务数据库是多用户共享的共同资源，频繁的数据库更新通常是不可避免的，故按照事务数据集是否动态改变又可以划分为增量式关联规则挖掘与静态关联规则挖掘(见图1)。
1.1 二值型关联规则挖掘（１） 基于ＳＱＬ的关联规则挖掘算法—ＳＥＴＭ［２］事务通常以关系数据库的格式存储，一条事物对应关系
图１ 关联规则挖掘的分类学术研究Academic Research
信息安全与通信保密・2010.285
表的一条记录。如果借助关系数据库的查询功能，将关联规则挖掘的过程转化为SQL语句的方式来执行，可以有效地提高挖掘的效率。SETM算法利用中间表Rk存储事物的标识和其中包含的k-项集。对k-1阶项集的中间表Rk-1与R1作连接操作，就得到k阶项集的连接表Rk`，对连接表按照项集字段分组，每个项集构成一组，组内的记录个数就是该项集的支持度计数，那些达到最小支持度阈值的项集就是频繁k-项集。然后，利用频繁项集对连接表过滤，只保留频繁项集对应的交易记录，得到k-项集的中间表记作Rk。以此类推，直到某个中间表为空时算法结束。（２） 关联规则挖掘的基本算法——Ａｐｒｉｏｒｉ［３］Apriori算法是第一个典型的关联规则挖掘算法，它开创性地使用基于支持度的剪枝技术，系统地控制候选项集指数增长。该算法中使用Apriori-gen函数通过如下两个操作产生候选项集：① 候选项集的产生：该操作由前一次迭代发现的频繁(k-1)-项集产生新的候选k-项集；② 候选项集的剪枝：该操作采用基于支持度的剪枝策略，删除一些候选k-项集。函数Apriori-gen的候选产生过程合并一对频繁(k-1)-项集，仅当它们的前k-2个项都相同。令A={a1，a2，…，ak-1}和B={b1，b2，…，bk-1}是一对频繁(k-1)-项集，合并A和B，如果它们满足如下条件：ai=bi(i=1，2，…，k-2)并且ak-1≠bk-1。（３） ＦＰ增长算法FP算法不同于Apriori算法的“产生-测试”，而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。FP增长是一个有趣的算法，它展示了如何使用事务数据集的压缩表示来有效地产生频繁项集。此外，对于某些事务数据集，FP增长算法比标准的Apriori算法要快几个数量级[4]。FP增长算法的运行性能依赖于数据集的压缩因子，如果生成的条件FP树非常茂盛，则算法的性能显著下降，因为算法必须产生大量的子问题，并且需要合并每个子问题返回的结果。（４） ＱＴＴＰ算法［５］QTTP算法直接把事物操作数据当作候选集，通过扫描保存各项集的超集信息，从而对扫描过的信息不再重复扫描。为了保存扫描信息，存储结构规定如下：用Kset表示层的索引号；NO.T表示每层中TID的序号；ID用来标识没有超集的记录，有超集记录的ID与其超集的ID相同；标识位(flag)用来判断“记录k项集是记录(k+1)项集的子集”是否出现过，取0表示未出现过，取1表示已出现过。上述4个算法的比较如表1所示。1.2 数值型关联规则挖掘（１） 数值型关联规则挖掘算法［６］数值型关联规则的挖掘是通过先将数据转换为二值型，再利用二值型规则的挖掘方法来实现的。对于分类型属性和值域(属性的取值空间)较小的数值型属性，每个取值映射为一个变量，对值域较大的数值型属性先分段，每个区间映射为一个变量，取值落在该区间中的数据转换为1，反之为0。数值型关联规则的挖掘就是发现这样的规则X→Y，满足以下方面：① 对于给定的支持度阈值，该规则满足б(X∪Y)≥s；② 对于给定的置信度阈值，该规则满足conf≥minconf；③ 对于给定的兴趣阈值，该规则是有趣的。（２） 模糊关联规则挖掘算法［７］模糊关联规则挖掘[8]就是要发现模糊概念之间的关联。一般来说，模糊关联规则挖掘包括两个步骤：搜索频繁模糊项集和生成模糊关联规则。其中后者的过程与二值型关联规则挖掘相同，以下是频繁模糊项集搜索的过程：① 定义属性上的模糊概念，可以用手工的方式定义，也可以通过其他方法自动生成；② 扫描数据库，得到频繁1-模糊项集，在第k次循环利用Apriori-gen运算根据k-1阶候选项集，计算候选项集的支持度计数，得到k阶频繁项集。1.3 并行关联规则挖掘[9]
并行算法是进行大规模计算的有效方法，利用多个处理器并行地处理数据，关键是计算、通信、内存利用和并发之间的协调。根据硬件的体系结构，并行关联规则挖掘算法分为内存分布的并行挖掘算法和共享内存的并行挖掘算法。（１） 内存分布的并行挖掘算法［１０］Count分布算法(CD算法)是最典型的内存分布的并行关联规则挖掘算法。它把数据分布到各处理器，每次循环时在每个处理器的内存中复制全部候选项集，建立候选项集的Hash树结构，然后各处理器分别扫描局部数据，计算局部支持度计数，通过处理器之间的通信得到全局支持度计数。（２） 共享内存的并行挖掘算法［１１］CCPD算法是基于Apriori算法的共享内存的并行算法，它将数据库划分为若干逻辑分区，各处理器并行地生成候选项集，构造共享的Hash树。由于对Hash树的插入操作是并行执行的，当两个以上的处理器同时修改一个叶节点时，就
表１ 二值型关联规则挖掘算法的比较Academic Research学术研究www.cismag.com.cn86
会造成访问冲突的问题。CCPD算法采用了新的Hash函数，构造Hash平衡树，缩短了搜索时间。1.4 多层次关联规则挖掘在许多应用中，由于数据分布的分散性，有价值的模式经常出现在较高的概念层中，仅从较低的概念层上很难发现有用的模式，所以数据挖掘应该提供在多个层次上进行挖掘的功能。根据规则涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。同层关联规则考虑相同概念层次上的项之间的关系，而层间关联规则中出现的项可以属于不同的概念层次。（１） 同层关联规则的挖掘同层关联规则挖掘可以采用下面两种支持度策略：① 统一的支持度阈值：对于不同的层次，都使用一个支持度阈值。这种方法的缺点是在低层次上难以找到满足支持度阈值的项集；② 递减的支持度阈值：对不同的概念层次指定不同的支持度阈值，较低层次的支持度阈值相对较小。假设指定第k层的最小支持度计数是minsup[k]，如果第k层的项集X的支持度计数X.sup≥minsup[k]，那么称X是频繁项集。ML_T2[12]算法是一种典型的同层关联规则挖掘算法，采用交易削减的方法，减少了扫描的数据量，从而提高了算法的效率。（２） 层间关联规则的挖掘层间关联规则又称广义关联规则，形式为X→Y，其中X，Y是任意概念层次上的频繁项集，满足X∩Y=Ф，且Y不包括X中的项的祖先。广义关联规则的挖掘包括3个步骤：① 找到满足支持阈值的频繁项集，频繁项集可以由任意概念层次上的项构成；② 生成关联规则，计算规则的置信度，找到满足置信阈值的规则；③ 计算规则的期望支持度和期望置信度，删除冗余规则。其中，第①步是这个过程的核心，对此也有各种不同的算法，如Basic算法、Cumulate算法等等。1.5 增量式关联规则挖掘增量关联规则挖掘的主要思想是在原有规则的基础上，去掉那些不满足条件的旧规则，发现满足条件的新规则，其目的是尽量减少计算量。增量关联规则算法主要解决两类问题，即支持度阈值的动态调整和支持数据库的更新。（１） 支持度阈值的动态调整阈值的调整一般分为以下3类：① 置信阈值调整带来的问题很容易解决，由于保留了原来的频繁项集，置信阈值改变后，很容易由频繁项集重新生成满足条件的规则；② 当支持度阈值增大时，规则的更新也很简单，只要去掉那些不满足新支持度阈值的频繁项集和规则就可以完成更新任务；③ 当支持度阈值减小时，原来的非频繁项集可能成为新的频繁项集，这类情况需要重新计算支持度。（２） 数据库的更新数据库的更新可以引起某些关联规则的失效，也可产生新的关联规则。FUP(Fast Update)[13]算法是一种典型的支持数据库更新的关联规则挖掘算法。当数据库中增加了一批新的记录时，设L表示原始事务数据库的频繁项集，L`表示数据库增量后的频繁项集。该算法的主要思想是从L中删除(L-L`)的项集，并且识别出属于(L`-L)的频繁项集。而在计算后