Apriori算法

1、算法作用：

为了在庞大的数据库中挖掘真正有用的规则，我们必须将每一项有可能的itemset列举出来。在真实情况中，假如我们的数据库数据条数为N，数据平均的itemset长度为W，而item组合为M的话，而因为M = 2d-1，所以O(NWM)这是一个无比海量的组合。是我们根本无法处理的。因此，Apriori算法的作用就是在这个无比庞大的搜索空间树中剪掉必定不符合条件的搜索空间，从而大大提高我们的搜索效率。

2、算法流程：

要知道Apriori算法的使用流程，我们必须先理解Apriori算法的核心原理。即：①任何一个频繁项，它所有的非空的子集必定是频繁的。②任何一个不频繁项，它的所有超集必定不频繁。在理解上述两条核心原理后，Apriori算法的工作流程就变得异常简单了。假如已知一个itemset不频繁，那么包含这个itemset的所有项集则必定都不频繁，因此我们就可以直接在搜索空间中去掉所有包含这个itemset的项集。

整理一下Apriori算法的流程，即：
①首先生成某一个特定大小的itemset(一般大小就为1)，依次扫描数据库，从中找出并保留频繁的itemset，去掉不频繁的itemset。
②使用已知的频繁的itemset来组合，组合成更大的可能频繁的itemset（即数量为2的itemset），再次扫描数据库，从新组合的itemset中找出真正频繁的itemset保留，去掉不频繁的itemset。
③迭代的执行上述步骤，从itemsize为1至k。

3、算法优缺点：

优点：Apriori算法采用了逐层搜索的迭代的方法，算法简单明了，没有复杂的理论推导，也易于实现。
缺点：Apriori算法要生成大量的候选项集，每生成频繁项集都要生成候选项集。依然需要每次迭代都去扫描数据库，因为大型数据库的I/O操作及其耗时。采用唯一支持度。算法的适应面窄。

4、改进措施：

①针对 Apriori算法的缺陷,引入一种新结构—链表数组 来压缩存放数据的相关信息,并结合修剪频繁集和连接优化策略，得到一种新的算法。
②更改数据库格式，采用位图数据格式。系统中会永久保留支持度为0的侯选1项集和候选2项集,当系统需要运行时,首先采用数据库的过滤技术,可以很快得到频繁2项集.突破了这一瓶颈,系统运行速度将得到较大的提升。

Q.E.D.