Apriori算法关联规则挖掘技术研究(5)
c) 基于采样的方法
基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在中讨论了反扭曲算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。
Brin等提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则”的一个新方法，这是基于他们的工作基础上的。
d) 减少交易的个数
减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是AprioriTid的基本思想。
2.3.3 其他的频集挖掘方法
以上都是基于Apriori的频集方法。即使进行了优化，但是Apriori方法一些固有的缺陷还是无法克服：
问题1：可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集个数将会超过10M。还有就是如果要生成一个很长的规则的时候，要产生的中间元素也是巨大量的。
问题2：无法对稀有信息进行分析。由于频集使用了参数minsup，所以就无法对小于minsup的事件进行分析；而如果将minsup设成一个很低的值，那么算法的效率就成了一个很难处理的问题。
于是出现了以下两种方法，分别用于解决以上两个问题。
在之前提到了一种解决问题1的方法。采用FP-growth算法。即采用分而治之的策略：在经过了第一次的扫描之后，把数据库中的频集压缩进一棵频繁模式树——FP-tree，同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之apriori算法有巨大的提高。:
第二个问题是基于这样的一个想法：Apriori算法得出的关系都是频繁出现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在Apriori算法中，起决定作用的是支持度，而我们现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。整个算法基本上分成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有两类：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再对这两个方法比较一下。MH的遗漏率为零，错误率可以由k严格控制，但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。