頻繁模式挖掘

探勘頻繁項目、項目集、子序列或其他子結構通常是分析大型資料集的第一步，多年來一直是資料探勘中的熱門研究主題。我們建議使用者參考維基百科的關聯規則學習以進一步了解相關資訊。

FP-Growth
PrefixSpan

FP-Growth

FP-growth 演算法說明載於論文 Han et al.，在沒有候選產生情況下探勘頻繁模式中，「FP」代表頻繁模式。針對交易資料集，FP-growth 的第一步是計算項目頻率並找出頻繁項目。與為相同目的而設計的 Apriori 類似演算法不同，FP-growth 的第二步使用後綴樹 (FP 樹) 結構來編碼交易，而不會明確產生候選集，後者通常需要花費高昂的產生成本。在第二步之後，可以從 FP 樹中萃取出頻繁項目集。在 spark.mllib 中，我們實作了 FP-growth 的平行版本，稱為 PFP，如 Li et al.，PFP：用於查詢建議的平行 FP-growth 中所述。PFP 會根據交易後綴來分配 FP 樹的成長工作，因此比單一機器實作更具擴充性。我們建議使用者參閱論文以進一步了解詳情。

FP-growth 運作於項目集上。項目集是唯一項目的無序集合。Spark 沒有集合類型，因此項目集會表示為陣列。

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：頻繁項目集，格式為具有下列欄位的資料框
- items: array：給定的項目集。
- freq: long：在設定的模型參數下，此項目集出現的次數。
associationRules：產生信心度高於 minConfidence 的關聯規則，格式為具有下列欄位的資料框
- antecedent: array：關聯規則假設的項目集。
- consequent: array：總是包含單一元素的項目集，代表關聯規則的結論。
- confidence: double：請參閱上方的 minConfidence，以取得 confidence 的定義。
- lift: double：前件預測後件的程度，計算方式為 support(antecedent U consequent) / (support(antecedent) x support(consequent))
- support: double：有關 support 的定義，請參閱上方的 minSupport。
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)

# Display frequent itemsets.
model.freqItemsets.show()

# Display generated association rules.
model.associationRules.show()

# transform examines the input items against all the association rules and summarize the
# consequents as prediction
model.transform(df).show()

在 Spark 儲存庫中的「examples/src/main/python/ml/fpgrowth_example.py」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 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)

// Display frequent itemsets.
model.freqItemsets.show()

// Display generated association rules.
model.associationRules.show()

// transform examines the input items against all the association rules and summarize the
// consequents as prediction
model.transform(dataset).show()

在 Spark 儲存庫中的「examples/src/main/scala/org/apache/spark/examples/ml/FPGrowthExample.scala」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 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);

// Display frequent itemsets.
model.freqItemsets().show();

// Display generated association rules.
model.associationRules().show();

// transform examines the input items against all the association rules and summarize the
// consequents as prediction
model.transform(itemsDF).show();

在 Spark 儲存庫中的「examples/src/main/java/org/apache/spark/examples/ml/JavaFPGrowthExample.java」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 R API 文件。

# Load training data

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)

# Extracting frequent itemsets

spark.freqItemsets(fpm)

# Extracting association rules

spark.associationRules(fpm)

# Predict uses association rules to and combines possible consequents

predict(fpm, df)

在 Spark 儲存庫中的「examples/src/main/r/ml/fpm.R」中尋找完整的範例程式碼。

PrefixSpan

PrefixSpan 是一種循序模式探勘演算法，其說明如下：Pei 等人，透過模式成長進行循序模式探勘：PrefixSpan 方法。我們建議讀者參閱所引用的論文，以了解循序模式探勘問題的正式定義。

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)

# Find frequent sequential patterns.
prefixSpan.findFrequentSequentialPatterns(df).show()

在 Spark 儲存庫中的「examples/src/main/python/ml/prefixspan_example.py」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 Scala API 文件。

import org.apache.spark.ml.fpm.PrefixSpan

val smallTestData = Seq(
  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()

在 Spark 儲存庫中的「examples/src/main/scala/org/apache/spark/examples/ml/PrefixSpanExample.scala」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 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(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 ArrayType(new ArrayType(DataTypes.IntegerType, true), true),
  false, Metadata.empty())
});
Dataset<Row> sequenceDF = spark.createDataFrame(data, schema);

PrefixSpan prefixSpan = new PrefixSpan().setMinSupport(0.5).setMaxPatternLength(5);

// Finding frequent sequential patterns
prefixSpan.findFrequentSequentialPatterns(sequenceDF).show();

在 Spark 儲存庫中的「examples/src/main/java/org/apache/spark/examples/ml/JavaPrefixSpanExample.java」中尋找完整的範例程式碼。

有關更多詳細資訊，請參閱 R API 文件。

# Load training data

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"))

# Finding frequent sequential patterns
frequency <- spark.findFrequentSequentialPatterns(df, minSupport = 0.5, maxPatternLength = 5L,
                                                  maxLocalProjDBSize = 32000000L)
showDF(frequency)

在 Spark 儲存庫中的「examples/src/main/r/ml/prefixSpan.R」中尋找完整的範例程式碼。

MLlib：主要指南

MLlib：基於 RDD 的 API 指南

頻繁模式挖掘

FP-Growth

PrefixSpan