毕业论文移动版

关联规则从频繁项集中提取的方法：将一个频繁项集分成两个非空的子集和，满足置信度阈值的所有规则就是要提取的关联规则。这些规则都是从频繁项集中产生的，所以它们必然满足支持度的阈值。排除掉两个子集为空集的规则，每个频繁k-项集可以产生最多个关联规则。文献综述

计算关联规则的置信度不需要再扫描事务数据库。例如，对于一个规则

,

它是由一个频繁项集生成的。这条规则的置信度是

。

2。3 Apriori算法

Apriori算法是挖掘频繁项目集的数据挖掘算法。而且该算法堪称关联规则挖掘的经典算法，使用来发现，找出所有的频繁项集。

Apriori算法利用了一个非常重要的性质在挖掘频繁项集的过程中来压缩搜索空间：

性质：  k维数据项集X是频繁项集的必要条件是它的所有k-1维子集都是频繁项集。

Apriori算法的步骤如下：

①首先，通过遍历数据库得到所有的候选1-项集的集合，记为，筛选出所

有满足最小支持度minsup的所有的频繁1-项集的集合，记为；

②然后根据与的连接得到候选2-项集的集合，通过扫描数据库找出频繁2-项集的集合；

③一直循环计算，在第k次循环中，先由连接并剪枝产生候选k-项集的集

合，然后扫描数据库计算出每个项集的支持度，保留支持度大于等于最小支持度的项集产生频繁k-项集的集合；

④ 循环直到为空。

 其中的产生包括两个步骤连接、剪枝：

连接：中的每一个项集都是由中的两个项集连接产生的，并且这两个项集满足要求：项集中的前面k-2项都相同，最后一项不同。

剪枝: 由连接产生的中的成员有可能是频繁的也有可能不是频繁的，所以要通过性质1和性质2来压缩，减小后面扫描数据库的次数。

2。4  Apriori算法的缺点

Apriori是一种宽度优先的算法，Apriori算法基于Apriori的性质产生候选项集时候大大压缩了频繁集的大小，表现出良好的性能。但是Apriori算法依旧存在的三个主要的问题：

（1）需要多次扫描数据库。来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

（2）产生大量候选集。

（3）在扫描数据库的时候要对候选项集和事务进行匹配，要花费大量的时间。

2。5  Apriori算法的优化方法

针对Apriori算法在实际的应用中，存在一些不太令人满意的地方，人们提出了一些优化的方法：

（1）基于hash的算法---Dynamic Hashing and Pruning（DHP）算法。

（2）基于划分的方法。 

（3）基于采样的算法。     

（4）动态项集计数算法。

此外，还有我国学者近年来提出的基于栈变换的算法；基于事务压缩和项目压缩；关联规则的矩阵算法等等，这些算法都对关联规则算法，尤其是Apriori算法在不同方面和不同程度进行了优化。