频繁模式挖掘
挖掘频繁项、项集、子序列或其他子结构通常是分析大规模数据集的第一步，这多年来一直是数据挖掘中的一个活跃研究课题。我们建议用户查阅维基百科的 关联规则学习 获取更多信息。
目录
FP-Growth
FP-growth 算法在论文中有所描述
Han et al., Mining frequent patterns without candidate generation
，
其中“FP”代表频繁模式。
给定一个交易数据集，FP-growth 的第一步是计算项频率并识别频繁项。
不同于
Apriori-like
算法为相同目的而设计，
FP-growth 的第二步使用后缀树（FP-tree）结构来编码交易，而无需显式生成候选集，
通常生成候选集是非常昂贵的。
在第二步之后，可以从 FP-tree 中提取频繁项集。
在
spark.mllib
中，我们实现了一种名为 PFP 的 FP-growth 并行版本，
如
Li et al., PFP: Parallel FP-growth for query recommendation
中所述。
PFP 根据交易的后缀分配增长 FP-tree 的工作，
因此比单机实现更具可扩展性。
我们建议用户查阅相关论文以获取更多细节。
FP-growth 操作于 itemsets 。一个 itemset 是一个无序的唯一项目集合。Spark 没有 set 类型，因此 itemsets 表示为数组。
spark.ml
的 FP-growth 实现采用以下（超）参数：
-
minSupport: 被识别为频繁项集的最小支持度。例如，如果某个项在 5 笔交易中出现了 3 次，则其支持度为 3/5=0.6。 -
minConfidence: 生成关联规则的最小置信度。置信度是指关联规则被认为为真的频率。例如，如果在交易项集中X出现 4 次，而X和Y只共同出现 2 次，则规则X => Y的置信度为 2/4 = 0.5。该参数不会影响频繁项集的挖掘，但指定了生成关联规则的最小置信度。 -
numPartitions: 用于分配工作的分区数。默认情况下，该参数未设置，将使用输入数据集的分区数量。
该
FPGrowthModel
提供：
-
freqItemsets: 频繁项集，格式为一个包含以下列的 DataFrame：-
items: array: 给定的项集。 -
freq: long: 该项集出现的次数，基于配置的模型参数。
-
-
associationRules: 生成的关联规则，其置信度高于minConfidence，格式为一个包含以下列的 DataFrame：-
antecedent: array: 作为关联规则假设的项集。 -
consequent: array: 始终包含表示关联规则结论的单个元素的项集。 -
confidence: double: 请参阅上文的minConfidence以获取confidence的定义。 -
lift: double: 衡量前件如何预测后件的效果，计算公式为support(antecedent U consequent) / (support(antecedent) x support(consequent)) -
support: double: 请参阅上文的minSupport以获取support的定义。
-
-
transform: 对于itemsCol中的每笔交易，transform方法将其项与每个关联规则的前件进行比较。如果记录包含特定关联规则的所有前件，则该规则将被视为适用，并且其后件将被添加到预测结果中。transform方法将总结所有适用规则的后件作为预测。预测列与itemsCol具有相同的数据类型，并且不包含itemsCol中的现有项。
示例
有关更多细节，请参阅 Python API 文档 。
from pyspark.ml.fpm import FPGrowth
df = spark.createDataFrame([
(0, [1, 2, 5]),
(1, [1, 2, 3, 5]),
(2, [1, 2])
], ["id", "items"])
fpGrowth = FPGrowth(itemsCol="items", minSupport=0.5, minConfidence=0.6)
model = fpGrowth.fit(df)
# 显示频繁项集。
model.freqItemsets.show()
# 显示生成的关联规则。
model.associationRules.show()
# transform 方法会检查输入项与所有关联规则，并将结果汇总为预测
model.transform(df).show()有关更多详细信息，请参阅 Scala API 文档 。
import org.apache.spark.ml.fpm.FPGrowth
val dataset = spark.createDataset(Seq(
"1 2 5",
"1 2 3 5",
"1 2")
).map(t => t.split(" ")).toDF("items")
val fpgrowth = new FPGrowth().setItemsCol("items").setMinSupport(0.5).setMinConfidence(0.6)
val model = fpgrowth.fit(dataset)
// 展示频繁项集。
model.freqItemsets.show()
// 展示生成的关联规则。
model.associationRules.show()
// transform 方法检查输入项与所有关联规则，并总结预测的
// 结果
model.transform(dataset).show()有关详细信息，请参阅 Java API 文档 。
import java.util.Arrays;
import java.util.List;
import org.apache.spark.ml.fpm.FPGrowth;
import org.apache.spark.ml.fpm.FPGrowthModel;
import org.apache.spark.sql.Dataset;
import org.apache.spark.sql.Row;
import org.apache.spark.sql.RowFactory;
import org.apache.spark.sql.SparkSession;
import org.apache.spark.sql.types.*;
List<Row> data = Arrays.asList(
RowFactory.create(Arrays.asList("1 2 5".split(" "))),
RowFactory.create(Arrays.asList("1 2 3 5".split(" "))),
RowFactory.create(Arrays.asList("1 2".split(" ")))
);
StructType schema = new StructType(new StructField[]{ new StructField(
"items", new ArrayType(DataTypes.StringType, true), false, Metadata.empty())
});
Dataset<Row> itemsDF = spark.createDataFrame(data, schema);
FPGrowthModel model = new FPGrowth()
.setItemsCol("items")
.setMinSupport(0.5)
.setMinConfidence(0.6)
.fit(itemsDF);
// 显示频繁项集。
model.freqItemsets().show();
// 显示生成的关联规则。
model.associationRules().show();
// transform函数会检查输入项与所有关联规则的匹配，并总结
// 后果作为预测结果。
model.transform(itemsDF).show();有关更多详情，请参阅 R API 文档 。
# 加载训练数据
df <- selectExpr(createDataFrame(data.frame(rawItems = c(
"1,2,5", "1,2,3,5", "1,2"
))), "split(rawItems, ',') AS items")
fpm <- spark.fpGrowth(df, itemsCol="items", minSupport=0.5, minConfidence=0.6)
# 提取频繁项集
spark.freqItemsets(fpm)
# 提取关联规则
spark.associationRules(fpm)
# 预测使用关联规则并结合可能的结果
predict(fpm, df)前缀序列模式挖掘
PrefixSpan 是一种序列模式挖掘算法，描述见于 Pei et al., Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach 。我们建议读者参考引用的论文，以正式化序列模式挖掘问题。
spark.ml
的 PrefixSpan 实现接受以下参数：
-
minSupport: 被认为是频繁序列模式所需的最小支持度。 -
maxPatternLength: 频繁序列模式的最大长度。任何超过此长度的频繁模式将不包括在结果中。 -
maxLocalProjDBSize: 在开始对投影数据库进行本地迭代处理之前，前缀投影数据库中允许的最大项目数。此参数应根据执行器的大小进行调整。 -
sequenceCol: 数据集中序列列的名称（默认为“sequence”），此列中为null的行将被忽略。
示例
有关更多详细信息，请参阅 Python API 文档 。
from pyspark.ml.fpm import PrefixSpan
df = sc.parallelize([Row(sequence=[[1, 2], [3]]),
Row(sequence=[[1], [3, 2], [1, 2]]),
Row(sequence=[[1, 2], [5]]),
Row(sequence=[[6]])]).toDF()
prefixSpan = PrefixSpan(minSupport=0.5, maxPatternLength=5,
maxLocalProjDBSize=32000000)
# 查找频繁序列模式。
prefixSpan.findFrequentSequentialPatterns(df).show()有关更多细节，请参考 Scala API 文档 。
import org.apache.spark.ml.fpm.PrefixSpan
val smallTestData = Seq(
Seq(1, 2), Seq(3)),
Seq(Seq(1), Seq(3, 2), Seq(1, 2)),
Seq(Seq(1, 2), Seq(5)),
Seq(Seq(6)))
val df = smallTestData.toDF("sequence")
val result = new PrefixSpan()
.setMinSupport(0.5)
.setMaxPatternLength(5)
.setMaxLocalProjDBSize(32000000)
.findFrequentSequentialPatterns(df)
.show()请参阅 Java API 文档 以获取更多详细信息。
import java.util.Arrays;
import java.util.List;
import org.apache.spark.ml.fpm.PrefixSpan;
import org.apache.spark.sql.Dataset;
import org.apache.spark.sql.Row;
import org.apache.spark.sql.RowFactory;
import org.apache.spark.sql.SparkSession;
import org.apache.spark.sql.types.*;
List<Row> data = Arrays.asList(
RowFactory.create(Arrays.asList(1, 2), Arrays.asList(3))),
RowFactory.create(Arrays.asList(Arrays.asList(1), Arrays.asList(3, 2), Arrays.asList(1,2))),
RowFactory.create(Arrays.asList(Arrays.asList(1, 2), Arrays.asList(5))),
RowFactory.create(Arrays.asList(Arrays.asList(6)))
);
StructType schema = new StructType(new StructField[]{ new StructField(
"sequence", new <
有关更多详细信息，请参阅 R API 文档 。
# 加载训练数据
df <- createDataFrame(list(list(list(list(1L, 2L), list(3L))),
list(list(list(1L), list(3L, 2L), list(1L, 2L))),
list(list(list(1L, 2L), list(5L))),
list(list(list(6L)))),
schema = c("sequence"))
# 查找频繁序列模式
frequency <- spark.findFrequentSequentialPatterns(df, minSupport = 0.5, maxPatternLength = 5L,
maxLocalProjDBSize = 32000000L)
showDF(frequency)