Frequent Pattern Mining

Frequent Pattern Mining

Frequent Pattern이란

Frequent pattern이란 주어진 데이터에서 빈번하게 발생하는 패턴이다.

Frequent pattern으로 set of iterms(순서 의미 없음), subsequences(순서가 의미 있는 나열), substructures(그래프의 구조 등)이 될 수 있다.

 

Frequent Pattern Analysis

데이터 속에서 빈번하게 발생하는 패턴을 찾는 테스크이다.

거래 내역(transaction)에서 어떤 상품들이 함께 구매되는가, PC를 산 뒤에 어떤 상품이 다음에 구매되는가 등을 찾는 과정이다.

 

Basket data analysis(장바구니 분석), cross-marketing, catalog design, web log analysis, DNA seuqnece analasis 등 다양한 분야에서 활용될 수 있다.

 

Frequent Pattern Mining

주어진 data set에서 중요한 특징이나 정보를 발견하는 것이다.

많은 data mining task를 수행하는데 있어서 매우 중요한 기반이 된다.

Association, correlation, classification, cluster analysis 등의 data mining task에서 활용된다.

 

Frequent pattern analysis는 처리 시간이 너무 오래 걸기 때문에 data size가 linear하게 증가할 때 처리시간은 exponential하게 증가할 수 있다.

이는 큰 문제이므로 scalable하게 처리할 수 있어야 한다.

 

---

Scalable Frequent Pattern Mining Method

가장 간단한 방법은 brute-force로 모든 조합을 다 만들고 테스트 해볼 수 있다.

그러나 이는 시간이 너무 오래 걸리고 데이터셋이 증가함에 따라 $2^n$으로 exponential하게 time cost가 증가한다.

 

Downward Closure Property

때문에 주로 frequent pattern의 downward clousre property를 이용한다.

Downward closure 특성이란 어떤 itemset이 frequent 하기 위해서는 그것의 모든 subset이 frequent해야 함을 말한다.

 

대표적인 방법

• Apriori
  • 여러번 수행하는 DB scan의 cost가 비싸다
  • long pattern을 mining하는 것은 여러 번의 scan과 많은 수의 candidate 생성이 필요하다.
• FP-Growth : frequent pattern growth
• Vertical data format approach