频繁模式挖掘技术简介

挖掘频繁模式的项，项集，子序列或者子结构通常是分析大型的数据集的第一步，这个方法在数据挖掘领域已经使用了多年。挖掘频繁项集有很多的算法，在MLlib中实现了一个并行的挖掘频繁项集的算法——FP-growth。

FP-growth算法是韩家炜教授在他的论文Mining frequent patterns without candidate generation中提出的，其中FP代表频繁模式（Frequent Pattern）。给定一个交易数据集，FP-growth算法分析的第一步就是计算项的频率，并确定其中的频繁项。虽然FP-growth算法和Apriori算法解决的的是同一类问题，但是FP-growth在第二步时采用前缀树（也称FP_- tree）的数据结构去编码交易信息而不像Apriori算法需要生成大量的候选短频繁模式，避免了大量候选集的产生。第二步之后就可以从FP-tree中提取频繁项集。在MLlib中，实现了一个并行版本的FP-growth叫做PFP，PFP将FP-tree的生成工作进行分发，使得算法比单机实现更加具有扩展性。

MLlib中FP-growth的实现需要接受如下的参数。

● minSupport：定义某个项集的支持度，即定义项集出现的频率。举个例子来说，如果一个子项在5个交易数据中出现了3次，那么它的支持度为3/5=0.6。(www.xing528.com)

● numPartitions：用于分发工作的分区的数量。

下面的【例4-74】调用了MLlib对FP-growth算法的具体实现FPGrowth类。在算法调用前，需要一个交易信息的JavaRDD，其中包含原始的数据集。调用FPGrowth.run方法，将会返回存储着频繁子集和其频率的FPGrowthModel。

【例4-74】FPGrowth方法示例。