5.8 性能分析与优化 23

5.9 算法实现的不足 24

总 结 25

参考文献 26

致 谢 27

1 绪论

在科技迅猛发展的今天，计算机的普及，国家也大力提倡信息化，因此行业信息化的程度也越来越高。社会信息化后，社会的历史是数据的历史，多年的积淀，虽然数据量大，但问题是信息量少。数据挖掘应用而生，即从海量数据提取有用的信息。关联分析就是数据挖掘技术的一部分。关联规则一般用以发现交易数据库中不同商品（项）之间的联系，也叫购物篮分析[1]。Apriori算法是最经典的简单的布尔关联规则挖掘算法。Apriori算法的扩展性强，不仅用于超市领域，还拓展到金融，电信等多个行业。业界学者对Apriori算法进行了多个方面的改进，改进后的Apriori算法可以处理多种类型数据，拓展挖掘任务，应用于各种各样的应用，其实现的商业价值是巨大的。

1.1 Apriori算法

1.1.1 算法简介

Apriori算法是挖掘产生布尔关联规则频繁项目集的经典算法，它是一种简单的布尔关联规则挖掘算法[2]。其实现流程如图1.1所示。

Apriori算法使用逐层搜索的迭代方法，在k项集基础上求得k+1项集。第一步扫描交易（事务）记录，找到频繁1项集记做L1，然后利用L1 连接得到2候选集C2，再剪枝得到频繁2项集的集合L2，L2找L3，如此迭代，直到找不到更高的频繁集为止。最后在频繁集的基础上找出强规则，即产生用户感兴趣的关联规则。

1.1.2 算法的优缺点

根据上述步骤的描述，可知算法思想易于理解，主要用了循环迭代的方法，易于实现。这是其主要优点，但是连接步骤往往是总体性能的瓶颈。连接的条件是两个相同长度的频繁集只有最后一项不同，这样就需要循环逐项集再循环逐项比较之后，才能判断两者是否能连接。算法复杂度是O(N2)。现实情况下，项集的长度往往是很长的，计算两层循环时间耗费是很可观的。剪枝步骤中K候选项集Ck需要循环扫描数据库，计算它出现的频次，这样在数据量庞大的现实情况下，多次扫描数据库也是很耗费时间的。所以现在对算法的改进，性能是一方面

1.1.3 算法的研究的现状概述源'自:优尔-'论/文'网"www.youerw.com

现在的Apriori算法不仅仅是单纯用于哪些商品之间可以捆绑销售的的简单问题上了。现实生活中的购物篮信息既包含了交易物品的信息还有会员实体信息等多种影响购物模式的因素，数据结构越来越复杂多样化。近年来围绕关联规则的研究主要集中于两个方面，扩展经典关联规则能够解决问题的范围,改善经典关联规则挖掘算法效率和规则兴趣性[3]。

(一)由于许多应用问题比超市购物问题更复杂，多种因素都会对关联规则挖掘做出影响。将不同类别层次的属性转换成布尔属性，考虑上时态关系属性使得挖掘出来的关联规则更有意义，这对丰富关联规则的应用领域也是很有意义的。如超大型事务数据库的挖掘，分布式事务数据库的挖掘，多表挖掘以及多层挖掘和空间关联规则挖掘等。

   （二）性能优化即压缩连接步骤的比较次数，减少剪枝步骤的重复扫描数据库次数还有减少或不产生候选频繁集。其中比较典型的有以下两个：

（1）FP_Tree算法

它只需要扫描两次数据库。首先通过新的搜索策略和剪枝策略,将事务数据库D压缩为内存中的FP-tree,然后按照相反次序逐个处理项集中的项目,每次迭代得到以某个项目开头的所有频繁项集。从而提高算法的搜索效率,减少了对内存的占用,算法的空间复杂性低[4]。