MLlib: メインガイド

MLlib: RDDベースAPIガイド

頻出パターンマイニング

頻繁なアイテム、アイテムセット、サブシーケンス、またはその他の部分構造のマイニングは、通常、大規模データセットの分析の最初のステップの 1 つであり、長年にわたってデータマイニングの活発な研究トピックとなっています。詳細については、Wikipedia の アソシエーションルール学習 を参照してください。

目次

FP-Growth

FP-growth アルゴリズムは、論文 Han et al., Mining frequent patterns without candidate generation で説明されています。ここで「FP」は頻繁パターンを表します。トランザクションのデータセットが与えられた場合、FP-growth の最初のステップは、アイテムの頻度を計算し、頻繁なアイテムを特定することです。同じ目的のために設計された Apriori ライクなアルゴリズムとは異なり、FP-growth の 2 番目のステップでは、サフィックスツリー (FP-tree) 構造を使用して、通常は生成にコストがかかる候補セットを明示的に生成せずにトランザクションをエンコードします。2 番目のステップの後、頻繁なアイテムセットは FP-tree から抽出できます。spark.mllib では、Li et al., PFP: Parallel FP-growth for query recommendation で説明されている PFP という FP-growth の並列バージョンを実装しました。PFP は、トランザクションのサフィックスに基づいて FP-tree を成長させる作業を分散するため、単一マシン実装よりもスケーラブルです。詳細については、論文を参照してください。

FP-growth はアイテムセット上で動作します。アイテムセットは、一意のアイテムの順序付けられていないコレクションです。Spark にはセット型がないため、アイテムセットは配列として表されます。

spark.ml の FP-growth 実装は、次の (ハイパー) パラメータを取ります。

FPGrowthModel は以下を提供します。

例

詳細については、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 et al., Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach で説明されているシーケンシャルパターンマイニングアルゴリズムです。シーケンシャルパターンマイニング問題の形式化については、参照論文を参照してください。

spark.ml の PrefixSpan 実装は、次のパラメータを取ります。

例

詳細については、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" にあります。