有关Apriori算法的拙见

摘要:本文分析了挖掘频繁访问模式的过程和当前Apriori算法的缺陷,提出了一种Apriori算法的改进算法:BI_Apriori算法。改进的算法采用不规则数组来保存项集信息,有效省去了扫描数据库所耗费的大量时间,将项集有序性引入到该数组上,减少了候选项集的个数,并采用二进制来表示1阶频繁访问模式,提高了模式匹配和连接的效率。试验结果表明,该改进算法能更有效地发现各种长度不同的访问模式。

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

Apriori 算法是一个布尔关联规则频繁项集挖掘算法,它主要是由迭代的方法一步一步使用搜索数据库寻找频繁项目集。主要步骤是:造成频繁1-项集的L1,扫描数据库D,在D中,每个数据项出现的是一个经常一集-项目候选集C1和对每个数据出现的次数的统计项目,比最小支持数较多(前),由项的集合定义是经常1-项集一楼;第一步亩,造成频繁亩,项目集路加,从上一步骤中频繁使用造成的(K-1)-项集路加与自己生产1的K-候选项目集一套杉木连接,扫描数据库事务数据库,计算中的每个成员杉木出现的次数会比候选人的最低支持较少删除,终于在频繁的K-项集。

该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持 度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递推的方法可能产生大量的候选集,以及可能需要重复扫描数据库,是Apriori算法的两大缺点。

Apriori算法的优点是结构简单,易于理解,没有复杂的推导。另外算法应用Apriori性质而设计的候选产生――检查方法。在许多情况下大大缩小了需要检查的候选规模,使算法效率大幅度提高。但Apriori算法依然存在两个主要的问题:

1.多次扫描数据库

Apriori算法需要在每进行一次迭代的时候扫描一次数据库,一般挖掘出的最大频繁项集的长度为N时,需要扫描N次数据库,而在实际应用中经常需要挖掘很长的模式,多次扫描数据库带来巨大开销。

2.可能产生大量候选

Apriori算法在迭代过程中要在内存中产生,处理和保存候选频繁项集,这个数量有时候是非常巨大的,导致算法在广度和深度上的适应性很差。

即Apriori算法有个严重的缺陷:因为需要多次扫描数据库和产生大量的频繁项集,使得算法的花费在I/0上的时间很多,从而导致挖掘的效率非常低。因此,为了提高Apriori算法的有效性,需要对Apriori算法进行改进。人们对Apriori算法进行了大量的改进,希望能够找出一个高效、可靠的挖掘频繁项集的算法。因此本文对Apriori算法进行了改进,提出一种基于划分的Apriori改进算法。

Apriori算法需要频繁扫描整个数据库。与Apriori算法相比,基于划分的改进算法只需要扫描整个数据库两次。在第一遍扫描中,将产生一组潜在的频繁项目集,这组项目集是最后要确定的频繁项目集的超集,它也许包含错误的选择,但绝对不会漏掉正确的选择。在第二遍扫描中,针对这些潜在的频繁项目集确定它针对整个数据库的实际支持度,从而可以最后确定所求的真正的频繁项目集。

数据挖掘的研究和应用受到了学术界、实业界和政府部门的越来越多的重视。Apriori算法是关联规则的基础算法,对于其他复杂算法的实现也有很大的作用。但对于大型数据库来说,每扫描一次数据库需要很长时间,并用Apriori算法需要k次扫描数据库才能得到k-频繁项目集,所以从性能上讲,Apriori算法并不理想。而改进后的算法,只需要扫描一次数据库得到0-1矩阵,接下来的工作就是对向量的运算就可以得到频繁项集,而且矩阵是不断变小的,这样就可以大大提高算法的执行效率。试验表明,对于大型数据库和长模式的关联规则挖掘,改进的算法有效地压缩了搜索空间,提高了频繁项集的生成效率。

作者单位:湖北省襄樊市武汉大学计算机学院