数据课设报告.docVIP

《数据挖掘概念与技术》课程设计 ——Apriori算法的改进研究 编写人：王肖程 学号：111001114 班级：111001 日期：2014年6月26日 引言：数据挖掘(Data Mining)， 就是从大量的、 不完全的、 有噪声的、 模糊的、 随机的实际应用数据中，提取隐含在其中的、 人们事先不知道的、 是潜在有用的信息和知识的过程。数据挖掘算法有决策树算法、 分类算法、 聚类分析算法、 关联算法等。其 中， 随着数据量的逐年增加和人们对各个数据项之间关系的关注， 关联规则挖掘在数据挖掘中占有了重要的地位， 也是数据挖掘的主要任务之一。关联规则是由R.Agrawal等人于 1993年提出的!是数据挖掘问题中的一个重要研究内容它最典型的应用是在销售事务数据库中发现新的有用信息。例如85%的顾客在购买商品A和B的同时也购买商品 C和D找出所有的类似规则。对于确定销售策略是很有帮助的。由于数据库通常是相当庞大的，因此需要高效的算法来挖掘关联规则Apriori算法是最经典的挖掘关联规则的算法。 Apriori算法的基本原理 Apriori是最有影响的挖掘布尔关联规则频繁项目集的经典算法。在Apriori算法中,通过遍历数据库得到大一项集L1。如果L1非空,由L1产生长度为2的候选项集合C2,然后对事务数据库中的每一个事务t,求出t在C2中的全部子集Ct,对于Ct中的每一个长度为2的候选项集c,令c的计数加1。当扫描事务数据库一遍后,筛选出候选项集合C2中所有计数满足最小支持度的项集组成了长度为2的频繁项集合。用以上步骤重复处理新得到的频繁项集合,直到没有频繁项集合产生。其中候选项集产生的过程被分为连接与剪技两个部分。采用这种方式,使得所有的频繁项集既不会遗漏又不会重复。 Apriori算法的缺陷 （1）如果在生成候选频繁项目集之前能判断某些候选频繁项目集是非频繁项目集，则可以不生成这些能事先判断出的非频繁项目集，这样既可避免连接生成这些候选频繁项目集的时 间开销，又可避免在扫描数据库时的时间开销 （2）连接程序中相同的项目重复比较太多，如果能避免这些重复的比较,则可提高算法的效率。 （3）在每次生成候选频繁项目集后，又要回去扫描数据库来判断这些候选频繁项目集是否是频繁项目集，在扫描数据库的过程中,有些可以判断出不必再去扫描的项目或事务被多次扫描!如果能避免这些不必要的扫描,则可以提高 Apriori算法的效率。 相关性质 性质1：任何频繁项集的所有非空子集是频繁项集,非频繁项集的超集是非频繁项集。 性质2 ：如果频繁k项集还能产生频繁k+1项集,则频繁k项集中的项集的个数必大于k。 性质3 ：支持频繁项集Lk的任意一条事务至少支持Lk-1中的k个k-1项集。 Apriori改进 4.1 Apriori算法的进一步分析 设Tmax表示最大交易长度,N表示事务数据库的交易数,则第一遍数据库扫描时间为O(N*Tmax),在每一步中,连接时间开销是O(|Lk-1|*|Lk-1|),剪枝时间是O(|Ck|),扫描计数时间是 O(N*|Ck|)。由此可见,Apriori算法的时间开销主要集中在频繁k项目集的生成以及候选频繁项目集Ck的计数过程中。因此,减少连接次数以及扫描数据库的次数从而减少数据库扫描时间;在此过程中同时进行事务压缩和项目压缩,即在生成候选项目集Ck的同时,剔除事务数据库中的不支持Lk的事务,以及事务中的项目,同时在进行连接操作时,可以优化连接策略,则算法的性能会有所提高,这是本文提出的改进方法的基本出发点。 4.2 优化思想 基于上述提到的三个性质，可以采用如下通过事务压缩而进行库优化的策略。将数据库读入一个二维数组A[][],其中数组的每一行只存储一条事务记录,且每一行的第0个元素存储为一个标志位M(0或者1),M=0是表示该行需要扫描,当M=1时,表示该行不需要再扫描了。主要基于如下2点: 1、对已知规模的数据库,任意k项集的支持度与规模小于k的事务无关,因此可删除规模小于k的事务。 2、当一个事务不包含长度为k的频繁项集,则必然不包含长度为k+1的频繁项集[10]。因此可以在生成k+1频繁项集之前先删除这样的事务,以减少下次扫描数组的时间。 Apriori算法需要大量进行的2个操作是