关联算法总结

1.FP-growth

基本原理：FrequencyPattern-growth频繁模式增长算法，也是决策树算法，在产生候选项目集的时候采用模式增长的方法递归挖掘全部频繁模式，并且只需扫描事务数据库两次。它采用分而治之的思想：经过一片扫描后，将提供频繁项集的事务数据库压缩成一颗频繁模式树，但仍保留项集的关联信息。然后，将这种压缩后的事务数据库分成一组条件数据库，每个条件数据库关联一个频繁项集，并分别挖掘每一个条件数据库

2.WFP

基于加权的优化算法WeightFrequencyPattern是在FP-Growth算法的基础上发现频繁一项集，然后构建频繁模式增长的兄弟孩子树，通过遍历构造的频繁模式树找到频繁项集，最后从加权频繁项集中计算出满足加权最小支持度和最小置信度的强关联规则

3.Aprior

Aprior先验算法通过项目数目的不断增加逐步完成频繁项集发现。算法大体分为两步：第一步，从根据候选项目集生成的逐层迭代找出频繁项目集；第二步，找出关联规则

4.Sampling

Sampling属于抽样的优化算法，先使用数据库的抽样数据得到一些可能成立的规则，然后利用数据库的剩余部分验证这些关联规则

5.Partition

Partition算法基于划分的优化算法：首先将大容量的数据库从逻辑上分成几个不同的互不相交的块，每块用关联规则算法Aprior生成局部的频繁项集，然后将这些频繁项集作为候选的全局频繁项目集，通过测试它们的支持度得到最终的全局频繁项目集

5DHP

基于hash的优化算法（DirectHashandPruningDHP）利用散列技术改进产生2频繁项目集的方法：把扫描的项目放在不同的hash桶中，这样可以对每个桶的项目子集进行测试，减少候选集生成的代价