빈발 패턴 마이닝

빈발 패턴 마이닝 (Frequent Pattern Mining)

대규모 데이터셋을 분석할 때 첫 단계로 흔히 수행하는 빈발 아이템·아이템셋·부분수열 마이닝을 소개하는 문서예요. FP-Growth 알고리즘과 PrefixSpan 시퀀스 패턴 마이닝을 Python·Scala·Java·R 예제와 함께 알아볼게요.

출처: 문서

본문

빈발 아이템, 아이템셋, 부분수열(subsequence) 또는 기타 하부 구조를 마이닝하는 것은 대규모 데이터셋을 분석하는 첫 단계 중 하나로, 수년간 데이터 마이닝의 활발한 연구 주제였어요. 자세한 내용은 Wikipedia의 association rule learning 문서를 참고하세요.

FP-Growth

FP-growth 알고리즘은 Han et al., Mining frequent patterns without candidate generation 논문에 설명되어 있는데, "FP"는 빈발 패턴(frequent pattern)을 뜻해요. 트랜잭션 데이터셋이 주어졌을 때, FP-growth의 첫 단계는 아이템 빈도를 계산하고 빈발 아이템을 식별하는 것이에요. 같은 목적을 위해 설계된 Apriori류 알고리즘과 달리, FP-growth의 두 번째 단계는 후보 집합(candidate set)을 명시적으로 생성하지 않고 FP-tree라는 접미사 트리(suffix tree) 구조로 트랜잭션을 인코딩해요. 후보 집합 생성은 보통 비용이 많이 들거든요. 두 번째 단계 이후에는 FP-tree에서 빈발 아이템셋을 추출할 수 있어요. spark.mllib에서는 PFP라고 하는 FP-growth의 병렬 버전을 구현했는데, 이는 Li et al., PFP: Parallel FP-growth for query recommendation에 설명되어 있어요. PFP는 트랜잭션의 접미사에 기반해 FP-tree를 성장시키는 작업을 분산하므로 단일 머신 구현보다 확장성이 뛰어나요. 자세한 내용은 논문들을 참고하세요.

FP-growth는 아이템셋(itemset)에 대해 동작해요. 아이템셋은 고유 아이템들의 순서 없는 집합이에요. Spark에는 집합(set) 타입이 없으므로 아이템셋은 배열로 표현돼요.

spark.ml의 FP-growth 구현은 다음 (하이퍼)파라미터를 사용해요:

• minSupport: 아이템셋이 빈발(frequent)로 식별되기 위한 최소 지지도(support)예요. 예를 들어 어떤 아이템이 5개 트랜잭션 중 3개에 나타나면, 그 지지도는 3/5=0.6이에요.
• minConfidence: 연관 규칙(Association Rule) 생성을 위한 최소 신뢰도(confidence)예요. 신뢰도는 연관 규칙이 얼마나 자주 참인지 나타내는 지표예요. 예를 들어 트랜잭션에서 아이템셋 X가 4번 나타나고, X와 Y가 2번만 동시에 나타난다면, 규칙 X => Y의 신뢰도는 2/4 = 0.5예요. 이 파라미터는 빈발 아이템셋 마이닝에는 영향을 주지 않지만, 빈발 아이템셋에서 연관 규칙을 생성할 때의 최소 신뢰도를 지정해요.
• numPartitions: 작업을 분산하는 데 사용하는 파티션 수예요. 기본적으로 이 파라미터는 설정되지 않으며, 입력 데이터셋의 파티션 수가 사용돼요.

FPGrowthModel은 다음을 제공해요:

• freqItemsets: 다음 컬럼을 가진 DataFrame 형식의 빈발 아이템셋이에요:
  • items(array): 주어진 아이템셋이에요.
  • freq(long): 구성된 모델 파라미터를 기준으로 이 아이템셋이 몇 번 나타났는지에 대한 개수(count)예요.
• associationRules: minConfidence 이상의 신뢰도를 가진 연관 규칙으로, 다음 컬럼을 가진 DataFrame 형식이에요:
  • antecedent(array): 연관 규칙의 가설(hypothesis)이 되는 아이템셋이에요.
  • consequent(array): 연관 규칙의 결론을 나타내는, 항상 단일 요소를 포함하는 아이템셋이에요.
  • confidence(double): confidence의 정의는 위 minConfidence를 참고하세요.
  • lift(double): 선행 조건(antecedent)이 결과(consequent)를 얼마나 잘 예측하는지를 나타내는 척도로, support(antecedent U consequent) / (support(antecedent) x support(consequent))로 계산해요.
  • support(double): support의 정의는 위 minSupport를 참고하세요.
• transform: itemsCol의 각 트랜잭션에 대해 transform 메서드는 그 아이템들을 각 연관 규칙의 선행 조건과 비교해요. 레코드가 특정 연관 규칙의 모든 선행 조건을 포함하면 해당 규칙이 적용 가능한 것으로 간주되고, 그 결과(consequent)가 예측 결과에 추가돼요. transform 메서드는 모든 적용 가능한 규칙의 결과를 종합해 예측으로 만듭니다. 예측 컬럼은 itemsCol과 같은 데이터 타입이며 itemsCol에 이미 있는 아이템은 포함하지 않아요.

예제 (Examples)

자세한 내용은 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에 설명된 시퀀스 패턴 마이닝(sequential pattern mining) 알고리즘이에요. 시퀀스 패턴 마이닝 문제의 정형화는 참조된 논문을 참고하세요.

spark.ml의 PrefixSpan 구현은 다음 파라미터를 사용해요:

• minSupport: 빈발 시퀀스 패턴으로 간주되기 위한 최소 지지도예요.
• maxPatternLength: 빈발 시퀀스 패턴의 최대 길이예요. 이 길이를 초과하는 빈발 패턴은 결과에 포함되지 않아요.
• maxLocalProjDBSize: 사영(프로젝션)된 데이터베이스의 로컬 반복 처리가 시작되기 전에, 접두사-사영 데이터베이스(prefix-projected database)에 허용되는 최대 아이템 수예요. 이 파라미터는 여러분의 executor 크기에 맞춰 튜닝해야 해요.
• sequenceCol: 데이터셋에서 시퀀스 컬럼의 이름이에요 (기본값 "sequence"). 이 컬럼에서 null인 행은 무시돼요.

예제 (Examples)

자세한 내용은 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 에서 찾을 수 있어요.

더 알아보기 (Learn more)

• 아파치 스파크 빈발 패턴 마이닝 (원문)
• MLlib 가이드 (원문) — MLlib 전체 가이드
• MLlib 빈발 패턴 마이닝 — RDD 기반 빈발 패턴 마이닝