MLlib: メインガイド

MLlib: RDD ベースの API ガイド

頻出パターンマイニング

頻出アイテム、アイテムセット、サブシーケンス、またはその他のサブ構造をマイニングすることは、通常、大規模データセットを分析する最初のステップであり、データマイニングにおける長年の活発な研究トピックです。詳細については、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 には *set* 型がないため、アイテムセットは配列として表現されます。

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" にあります。