关联算法

关联规则挖掘算法就是从事务数据库，关系数据库或其他信息存储中的大量数据的项集之间发现频繁出现的模式、关联和相关性。关联算法在科学数据分析、雷达信号分选、分类设计、捆绑销售、生物信息学、医疗诊断及网页挖掘等领域成果颇丰。
典型的关联算法包括Aprior 算法、FP-G（Frequent pattern Growth，频繁模式增长树）算法、FreeSpan 算法及prefixspan 算法等。上述各种算法的简单介绍如下。

Apriori 算法

Apriori 算法是第一个关联规则挖掘算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则。其过程由连接与剪枝组成。

** Apriori 算法的优点**

1.对原始数据要求很低；
2. 这种算法思路比较清晰直接，实施起来比较简单。

Apriori 算法的缺点
1.Aprior 算法只适合发现短的频繁模式，对长频繁模式比较困难；
2.Aprior 算法需要不断扫描数据库从中寻找候选集，涉及大量I/O 操作；
3.每一步产生侯选集时循环产生的组合过多，未排除不应该参与组合的元素。

FP-G 算法

针对Apriori 算法的固有缺陷，韩家炜在2000 年提出了不产生候选挖掘频繁项集的FP-G 算法。该算法采取分治策略，将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息。

FP-G 算法的优点
1.不产生候选集；
2.使用FP-G 结构表示一个无序的项集很合理；
3. FP-G 算法对不同长度的规则都有很好的适应性；
4. 通过FP-树数据结构对原始数据进行压缩，效率较高；
5. FP-G 算法只需进行两次事务数据库扫描，避免I/Ｏ瓶颈。

FP-G 算法的缺点

1. 利用FP-G 算法表示一个有序的项集并进行挖掘很困难；
2. FP-G 算法对由原始数据得到的FP-树分支庞大的情况，会造成存储压力。

FP-G 算法应用实例：FP-G 算法在2015 年4 月发表于期刊《指挥信息系统与技术》上的论文题目为“基于Spark 平台的海量电子对抗数据分析”中被采用。论文从辐射源识别角度出发，以挖掘辐射源完整重频参数为主要目标，采用聚类分析和频繁项集挖掘算法，在Spark 平台上对海量电抗数据进行分析，测试数据总量达700 多万条。电抗数据仿真试验表明，Spark 平台能够很好地进行海量电抗数据分析，且并行处理效率较高。

FreeSpan 算法

FreeSpan 算法是频繁模式投影的序列模式的挖掘。算法利用频繁项递归地将序列数据库投影到更小的投影数据集中，在每个投影数据库中生成子序列片段。

FreeSpan 算法的优点
1.不需要产生大量的候选集
2.将频繁系列和频繁模式的挖掘统一起来
3.挖掘工作限制在投影数据库中，还能限制序列分片的增长

FreeSpan 算法的缺点
1.存储结构不具有紧凑性；
2. 可能会产生许多投影数据库，如果一个模式在数据库的每个序列中出现，该模式的投影数据库将不会缩减；
3. 一个长度为K 的序列可能在任何位置增长，那么长度为K+1 的候选序列必须对每个可能的组合情况进行考察，将产生很大的开销。

Prefixspan 算法

Prefixspan 算法是韩家炜在2004 年提出的序列模式算法，该算法和他在2000 提出的FP_G 算法有很大的相似之处，都避免产生候选序列。算法采用分治思想，不断产生系列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。

Prefixspan 算法的优点
1.Prefixspan 算法消耗相对稳定的内存
2.Prefixspan 算法不产生候选序列的模式增长
3.Prefixspan 算法投影数据库随着挖掘过程不断缩减

Prefixspan 算法的缺点
1.存储结构不具有紧凑性；
2. 挖掘过程是不断约简投影数据库而进行的，故只有当投影数据库为空时，这一分支的挖掘结束，因此产生了大量的投影数据库；
3. 当数据库中具有大量相同的后缀子序列，所产生的投影数据库中则具有大量相同的序列，在挖掘过程中会造成对相同投影数据库的重复挖掘。

小结

关联算法的比较如表所示。

算法名称	时间复杂度	是否存在大量I/O 操作	产生候选集	数据紧凑性
Aprior	O（n^2）	存在	产生	不紧凑
FP-G	O（n）	不存在	不产生	紧凑
FreeScan	–	存在	不产生	不紧凑
prefixspan	–	不存在	不产生	不紧凑