基于Ap riori算法的改进关联规则的算法研究

谢美萍，芮廷先

(上海财经大学信息管理与工程学院，上海 200433)

1 引言

关联规则的最经典算法就是Apriori算法，但是该算法在实际应用时，存在着很多缺陷，比如需要多次扫描事务数据库，需要很大的I/O负载，而且可能产生庞大的候选集.针对这些缺陷，许多学者提出了改进的算法，王培吉等［1］提出一种基于分辨矩阵的含负属性项的关联规则挖掘算法;王娟琴等［2］在研究ApriorTid算法的基础上提出了一种高效的关联规则挖掘算法AprioriTidD，在计算数据库中的频繁项集时依靠有效的裁剪减少无效项集的产生，同时可以减少候选项集，从而提高算法效率;方炜炜等［3］针对可快速在大型交易事务数据库中挖掘关联规则的问题，提出了一种基于布尔矩阵的挖掘算法，该算法通过仅需存储布尔位节约了内存，提高求解频繁项集的效率.针对关联规则的特点，本文也提出了一种基于Apriori算法的改进算法，通过内存矩阵，将事务数据库的相关信息存放到内存矩阵中，同时在找频繁项目集的时候采用数组分组的方法来减少对内存矩阵的扫描.为了减少候选集，采用从大到小筛选频繁项目集的方法，同时把相应的事务从矩阵中删除以减少扫描范围.

2 关联规则的定义

设I={i1，i2，…，im}为项目集，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID的事务组成，每个事务ti(i=1，2，…，n)都对应项目集I上的一个子集.关联规则就是一个蕴涵式，形如X⇒Y，其中X∈I，Y∈I，并且满足X∩Y=∅.其中X是关联规则的条件，Y是关联规则的结果.在使……