其它常用关联规则挖掘算法

## 1. Apriori算法的改进技术

- 散列技术。其用于压缩候选K-项集$$C_k$$。例如, 当由$$C_1$$中的候选 1-项集产生频繁 1-项集 $$L_1$$ 时, 将每个事务产生所有 2- 项集散列到散列表结构的不同桶中, 并增加对应的桶计数。基于散列表中对应的桶计数小于支持度阈值的 2-项集不可能是频繁 2-项集特征, 可从候选集中删除。从而可以大大压缩要考察的 K-项集。

- 事务压缩技术。用于减少末来扫描事务集的大小。其为 AprioriTid 算法的基本 思想。相关原理：不包含任何 -项集的事务不可能包含任何 (K+1)-项集。因此在考 察这种事务时, 可加上标记或删除。

- 划分处理技术及算法。该算法从逻辑上把数据库分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁集，然后把产生的频集合并，用来生成所有可能的频繁项集，最后计算这些频繁项集的支持度。其分块大小的选择标准是，每个分块可以被放入主存，且每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁集至少在某一个分块中是频繁集保证。使用划分技术产生频繁项集，只需扫描事务集两遍。

- 采样技术。其从数据库中抽取样本，得到可能在整个数据库中成立的规则，然后对数据库的剩余部分验证这个结果。该技术显著减少I/O使用，但存在结果不精确，即所谓数据扭曲（data skew）的不足。原因在于，同一页面数据时常高度相关，可能不能表示整个数据库中的模式分布，由此导致采样5%的交易数据代价可能同扫描一遍数据库相近。Lin 和 Dunham 提出反扭曲（anti-skew)算法的改进，以减少扫描遍数。

- 动态项集计数技术。将给定事务集划分为标记开始点，可以在任何开始点添加新的候选项集。动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。

## 2.其他常用关联规则算法

Apriori 方法一些固有的缺陷还是无法克服，具体问题有二：

- 可能产生大量的候选集；

- 无法对稀有信息进行分析。

由于频繁集使用了参数$$min_c$$，就无法对小于$$min_c$$的事件进行分析；而如果将 $$min_c$$设置成一个很低的值，算法的效率就成了一个很难处理的问题。

- 问题一的解决方法（FP-增长法），采用了分而治之的策略：

(1)在经过了第一次的扫描之后，把数据库中的频繁集压缩进一棵频繁模式树（FPtree），同时依然保留其中的关联信息。

(2)随后再将 FP-tree 分化成一些条件库，每个库和一个长度为1的频繁集相关。然后再对这些条件数据库分别进行挖掘。

(3)当原始数据量很大时，也可以结合划分的方法,使得一个 FP-tree 可以放入主存中。
FP-增长对不同长度的规则都有很好的适应性，效率上较之 Apriori 算法有很大的提高

- 解决第二个问题基于如下想法：Apriori 算法得出的关系都是频繁出现的，但是在实际的应用中，可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在 Apriori 算法中，起决定作用的是支持度，而现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。

对于这个问题的一个解决方法是将整个算法基本上分成三个步骤：`计算特征、生成候选集、过滤候选集`。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。