优化Apriori算法的方法

Apriori算法在挖掘过程中生成大量的候选项集，并且由候选k-项集生成频繁k-项集时必须扫描数据库，候选项集的支持度计算工作量也相当巨大，因此算法效率相对较低。在实际应用时，可以采取一些方法对Apriori算法进行优化，基本思路包括：减少交易数据库的扫描次数，或缩减候选项集的数量，或尽量使得候选项集的支持度计算更加方便。相应的主要方法有：

（1）基于划分（partition）的方法。基本思想是采用分区技术，首先将数据库划分为N个不相交的部分，使得每部分都能放进内存，扫描每个部分（相当于扫描数据库一遍）得到局部频繁1-项集。该方法采用一种特殊的数据结构，保留包含每个频繁1-项集的交易ID列表，这样在每个局部由候选k-项集生成频繁k-项集时不需要扫描数据库计算支持度，只需要匹配k项集中每个项对应的交易ID列表即可。把所有的局部频繁项集合并，得到频繁项集的超集，对此超集进行第二次扫描数据库，计算支持度，如果支持度小于用户指定的支持度阈值，则把该项集删除，第二次数据库扫描结束，得到全局频繁项集。因此，基于划分的方法只需要扫描数据库两遍即可生成所有的频繁项集。并且算法是可以高度并行的，把每一分块分别分配给一个处理器生成频繁项集，产生频繁项集的每一个循环结束后，处理器之间进行通信以产生全局的候选k-项集。

（2）基于哈希（hash）的方法。寻找频繁项集主要的计算是在生成频繁2-项集上，因此可以引入哈希技术来改进产生频繁2-项集的方法。该方法的主要思想在于，如果一个k-项集在哈希树的路径上的一个计数值低于最小支持度阈值，则其本身不可能是频繁的。方法采用如下策略：在扫描数据库由k—1候选项集生成k—1频繁项集时，同时生成候选k-项集，将其散列到哈希表中不同的桶中去，并对其计数。在散列表中支持度低于阈值的桶中项集不可能是频繁k-项集，应该删去。这样可以大大压缩要考察的k项集。

（3）基于采样的方法。该方法基于以下策略：在给定数据的子集上进行挖掘，使用小的支持度和完整性验证方法。具体方法是：使用从数据库中抽取出来的采样，得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果，算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲（data skew），分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布。之后又有研究者讨论了反扭曲（anti-skew）算法。

（4）减少交易个数的方法。该方法基于的思想是不包含任何频繁k-项集的交易也必然不包含任何大于k的频繁项集，由此可以将这些交易移去，以减少用于未来扫描的交易集的大小，在下一遍的扫描中就可以减少要进行扫描的交易个数。(www.xing528.com)

（5）采用间隔计算的方法。在扫描数据库时，不计算Ck的支持度来生成Lk，而是直接由Ck生成Ck+1，计算出Ck+1的支持度从而生成Lk+1。这样可以少扫描数据库一次。采用这种方法必须保证生成的候选项集Ck+1能放进内存，尤其是当k比较小的时候。在能够保证足够内存的情况下该方法可以进一步扩展，可以跳跃多步进行，由Ck生成Ck+1，Ck+2，…，Ck+n，最后生成Lk+n。

还有其他的一些优化措施，如交易压缩、动态项集计数等。尽管采用了各种优化措施，由于Apriori算法本身的特点决定了其必须产生大量候选集，以产生频繁项集并扫描数据库，因此效率并不十分理想。

虽然Apriori算法有上述一些优化策略，然而，Apriori算法的核心在于：用频繁的（k—1）-项集生成候选的频繁k-项集。Apriori算法需要多次扫描数据库，这个代价是相当高的，特别是在中间过程中可能产生大量的候选项集：当长度为1的频集有104个时，长度为2的候选集个数将会超过107；尤其是如果要生成一个很长的频繁模式时，如长度为100的频繁模式，将产生约2100个候选项集。“候选项集-生成-测试”成为Apriori算法的瓶颈。因此，需要设计一个能避免候选项集生成的频繁模式挖掘算法，具体将在下一小节进行介绍。