[科普中国]-单机挖掘算法

单机（single-machine）挖掘算法指的是运行在一台机器上的频繁项集挖掘算法，它们的特点是数据量小，对机器的内存大小和计算性能要求不高，在一台机器上即可完成挖掘任务。一些经典的算法，如Apriori 和 FP-growth 等经典的频繁项集挖掘算法，都是单机频繁项集挖掘算法。

定义单机（single-machine）挖掘算法是指在单台机器运行的频繁项集挖掘算法，这种算法对机器要求不大，对应数据量小。和其他频繁项集挖掘算法一样，单机（single-machine）挖掘算法主要分两步来完成：第一步是找出数据库中所有满足最小支持度阈值的频繁项集；第二步是由频繁项集产生所有满足最小置信度阈值的关联规则。由于关联规则挖掘的整体性能主要是由第一步的性能所决定，因此，关联规则挖掘的关键和难点都集中在了频繁项集的挖掘上1。

频繁项集挖掘算法频繁项集挖掘是数据挖掘研究课题中一个很重要的研究基础，它可以告诉我们在数据集中经常一起出现的变量，为可能的决策提供一些支持。频繁项集挖掘是关联规则、相关性分析、因果关系、序列项集、局部周期性、情节片段等许多重要数据挖掘任务的基础。因此，频繁项集有着很广泛的应用，例如：购物蓝数据分析、网页预取、交叉购物、个性化网站、网络入侵检测等。

对频繁项集挖掘算法进行研究的方向大概可归纳为以下四个方面：一、在遍历方向上采取自底向上、自顶向下以及混合遍历的方式；二、在搜索策略上采取深度优和先宽度优先策略；三、在项集的产生上着眼于是否会产生候选项集；四、在数据库的布局上，从垂直和水平两个方向上考虑数据库的布局。对于不同的遍历方式，数据库的搜索策略和布局方式将会产生不同的方法，研究表明，没有什么挖掘算法能同时对所有的定义域和数据类型都优于其他的挖掘算法，也就是说，对于每一种相对较为优秀的算法，它都有它具体的适用场景和环境。所以，应该了解不同挖掘算法的不同特性和适用场景，掌握不同算法的适用环境和条件，这样才可以使研究者清楚算法的改进点，明白自己的研究方向，从而使用户更加方便地把算法应用到实际的生产活动中。

随着大数据时代的到来，传统的算法，比如 Apriori 算法、FP-growth 算法等，都无法处理这些处理大量的数据，主要原因有：一、时间消耗太大。面对大量数据，即使是比 Apriori快一个数量级的 FP-growth 算法，也无法在较短的时间内完成挖掘任务；二、内存无法满足要求。由于 Apriori 算法（包括类 Apriori算法）需要产生大量的候选项集，所以在处理大量数据的时候，就会由于内存消耗殆尽而无法使算法继续进行下去，即使是不需要生成候选项集的 FP-growth 算法，也会因为 FP-tree 太大无法放入内存，而使得算法无法运行。

面对这样的问题，众多的研究学者开始着眼研究基于多处理器系统的并行频繁项集挖掘算法，以及基于 Hadoop 等分布式集群的分布式频繁项集挖掘算法。比如 Agrawal 等人 CD 算法、DD 算法和 Ca D 算法，以及 Zaiane 等人的 MLFPT算法和 Li 等人的 PFP 算法等等，都是一些很优秀的并行或分布式频繁项集挖掘算法。

频繁项集挖掘是数据挖掘研究领域中的一个重要课题，它是关联规则、因果关系、相关性分析、情节片段、序列项集、局部周期性等许多数据挖掘任务的基础。所以，频繁项集有着广泛的实际应用，例如：购物蓝数据分析、网页预取、交叉购物、个性化网站以及网络入侵检测等。

算法类型Apriori

算法 1993 年，Agrawal 等人在文章《Mining Association Rules between Sets of Items in Large Databases》提出了一个挖掘布尔关联规则的经典算法——Apriori 算法，该算法使用了一种分层的完备搜索算法，即宽度优先搜索。 首先，它通过扫面事务数据库，得到频繁 1-项集；然后，利用频繁 1-项集产生候选的频繁 2-项集，再一次扫描事务数据库，从候选的频繁2-项集中筛选出满足最小支持度的 2-项集，得到频繁 2-项集；接着又利用频繁 2-项集产生候选的频繁 3-项集……如此反复进行下去，直到无法发现新的频繁项集，算法结束。

Apriori 算法充分利用了项集的反单调性这一先验知识：如果一个项集它是非频繁的，那么它的所有超集也一定是非频繁的，这个性质也被称为向下闭合性。

DHP 算法1995 年，J.S Park 等人在文章《An Effective Hash-Based Algorithm for Mining Association Rules》中提出了一种通过删减不必要的候选项集来完善挖掘效率的算法——DHP 算法。DHP 以 Apriori 为基础，并且引入一个 hash table 结构，根据统计学原理，将其转化为非频繁项集的刷选机制，以减少算法执行过程中不必要的项集数量，从而降低计算成本，提高挖掘效率。DHP 算法的执行步骤如下：

1、首先利用频繁 1-项集建立候选频繁 2-项集，并保存在 HASH 表中；

2、然后根据 HASH 表中的候选项集，从中筛选出频繁项集，接着再利用频繁项集缩减数据库的大小；

3、在产生频繁 2-项集之后，后面就可以按照经典的 Apriori 算法的步骤挖掘频繁项集，直到无法产生更高层次的频繁项集为止。

DHP 算法利用 hash table 来删除不必要的候选 2-项集，虽然在开始的时候需要花时间来建立 hash table，但是它对后来频繁项集的生成却有很大的改善，总体说来，该方法在一定程度上改善了Apriori 算法。

DIC 算法

1997 年，Bring 等人在文章《Dynamic Itemset Counting and Implication Rules for Market Basket Data》中提出了 DIC（Dynamic Itemset Counting）算法。DIC 算法的整体思想为：在同一次的数据库搜索中，对 k 值不同的候选 k-项集计数。DIC算法将数据库 D 分成N个大小均为 M 的子数据库1D 进行搜索。首先它搜索1D 并计算 1-项集的支持度，然后用这些 1-项集产生候选的频繁 2-项集；接着，算法搜索2D并得到 1-项集和候选 2-项集，也就是当前有所的候选项集，计算它们的支持度，并用所得的 2-项集产生候选 3-项集。重复这一搜索过程，直到nD 完成。在对数据库D的第一次搜索中，当算法搜索到kD 的时候，DIC就开始计算候选 k-项集的支持度，当所有的子数据库都处理过一次之后，IDC 重新开始第二次搜索，当算法回到kD 搜索时，就能够算出 k-项集的全局支持度。DIC 算法一次又一次循环搜索数据库，直到kD 没有新的候选项集出现，并且所有的候选项集的支持度都已经计算完成，此时算法结束。

Eclat算法

1998 年，M.J Zaki 等人在文章《Scalable Data Mining for Rules》中提出了一种新的频繁项集挖掘算法——Eclat 算法。Eclat 算法使用的是数据库的一个垂直表示方式，并且使用了集合的交集运算方法来计算项集（itemset）的支持度计数。在计算候选项集的时候，它采用的是深度优先搜索的方式来产生候选的频繁项集，并且在频繁 k-项集的基础之上，通过合并频繁 k-项集，产生以该频繁 k-项集为前缀的候选频繁(k+1)-项集。通过上面的方法，不断地扩展该项集，直到该项集已经不能再进行扩展了为止，算法才结束。

FP-growth 算法

2000 年，Jiawei Han 等在文章《Mining Frequent Patterns without Candidate Generation》中提出了一种基于频繁模式树（Frequent Pattern tree，FP-tree）的频繁项集挖掘算法——频繁模式增长算法，简称 FP-growth。

算法的整体思路是这样的：首先，通过数据库的一次扫描，计算并得到频繁1-项集，并对频繁 1-项集按照支持度的递减顺序排序放在项头表（header table）中；接着，第二次扫描数据库，构建 FP-tree：对于数据库中的每一条事务记录T ，根据项头表对T 中的项按递减顺序排序并删除不在项头表中的项，之后按照构造FP-tree 的方法将T 插入 FP-tree 中并更新项头表的节点链接，当数据库扫描完成之后，FP-tree 也同时建立好了；最后，在 FP-tree上进行频繁项集挖掘：在项头表（header table）中，从项头表的下面往上开始，由长度为1 的频繁模式（即频繁 1-项集，初始的后缀模式）开始，构造它的条件模式基。这些条件模式基可以看成是一个子事务数据库，它是由 FP-tree 中与后缀模式一起出现的前缀路径集所组成。接着，算法开始构造这个初始后缀模式的条件 FP-tree，构造方式与构造 FP-tree的方式一样，然后递归地在该条件 FP-tree 上实现挖掘，这个过程是一个递归挖掘的过程，模式的增长方式是通过将后缀模式与条件 FP-tree 产生的频繁模式连接起来，从而实现模式的增长。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所