[2-2] Apriori Algorithm

Contents

❑ Basic concepts and a road map

❑ Efficient and scalable frequent pattern (itemset) mining methods

❑ Mining association rules

❑ From association mining to correlation analysis

❑ Constraint-based frequent pattern and association mining

❑ Summary

 

 

이번 장에서는 (chapter5) 데이터 안에서 자주 함께 나타나는 패턴을 찾는 법을 배웁시다!

사실 이게 앞에도 말했듯이 어떤 상품 조합이 자주 같이 팔리는지, 어떤 순서의 행동이 반복되는지?... 분석하는 것이다

예 : 카메라를 사면 이후에 SD card 를 산다, 특정 DNA 패턴이 약물 반응과 관련 있다

즉, 겉으로 안 보이는 규칙을 데이터에서 찾아내는 것이 목적이다.

 

support 가 높을수록 그 itemset 은 자주 등장하는 패턴이고  자주의 기준으 정하는 게 minimum support 이다..

associatio rule 는 X가 나오면 Y 도 함께 나오는 경향이 있다는 뜻이고   confidence 는 확률이다 (즉, 규칙이 얼마나 믿을 만한지를 보여주는 값이다)

 

예시)

A -> D      support (전체 거래중 A,D 가 함께 나온다) 

                confidence (A 가 나온 거래어세는 항상 D 가 나온다)

 

 

그럼 "패턴이 너무 많아지면 어떻게 줄일까?" 왜냐....부분집합이 엄청 많아지니까

 

Closed Pattern : 자신을 포함하는 더 큰 frequent pattern 중 support 가 같은 것이 없는 패턴!!

정보 손실 없고, 중복도 줄일 수 있고, 대표 패턴만 남기는 방식  -  losesless compression

 

Max Pattern : 자신을 포함하는 더 큰 frequent pattern 이 아예 없는 패턴

즉, frequent 한 것들 중에서 가장 큰 것만 남긴다

 

이 성질이 중요한 이유는 안 되는 후부를 미리 버릴 수 있기 때문이다

즉, 작은 패턴을 먼저 검사해서 불가능한 경우를 빨리 제거한다

 

 

Apriori: A Candidate Generation-and-Test Approach - 후부 만들고 검사한

예를 들어 {A, B}가 자주 안 나오면 {A, B, C}는 더 자주 나올 수가 없다.  그래서 가능성 없는 큰 집합은 아예 만들지 않는다.

 

 

 

Important Details of Apriori

self-joining으로 후보를 만들고 pruning으로 불필요한 후보를 제거한다

 

Challenges of Frequent Pattern Mining

 

 

General ideas of improving efficiency of frequent pattern mining