Pattern mining

---

# Frequent Pattern Mining

---

Association Rule vs Sequential patterns
Association rule은 연관 규칙을 찾는 것이지만, 그 순서는 고려하지 않는다. 예를 들어, 치킨과 피자를 산 사람이 콜라를 살 확률 높다는 것은 알 수 있지만, 무엇이 먼저인지는 알 수 없다. 콜라와 피자를 산 사람이 치킨을 많이 산건지 아니면 그 외인지는 알 수 없다. 이런 부분을 보완한 게 Sequential Pattern 분석이다.

이 글에서는 Association Rule에 대해서만 다루겠다.

우선 연관성 분석을 위해서는 주요지표인 Support와 Confidence라는 개념을 먼저 알아야 한다. A,B,C라는 세 물건 사이의 구매 연관성을 파악한다고 생각해보자.

Support는 전체 소비자 중 A,B,C를 구매한 고객 수

Confidence는 A와 B를 구매한 고객 중 A,B,C를 모두 구매한 고객 수를 뜻한다. 즉, {A,B → A,B,C}에 대한 신뢰도가 높으면, A,B를 구매한 고객이 C까지 구매할 확률이 높다는 것을 의미한다.

이 때, Confidence{A → A,B}는 결국 Suppot(A,B)를 Support(A)로 나눈 것과 같다.

따라서 전체적인 과정은,

1. 모든 Itemset에 대해 Support를 계산한다.
2. 모든 Itemset간의 모든 조합들의 Confidence를 계산한다.

하지만, 모든 조합의 Confidence를 계산하기란 불가능하므로, 다른 방법을 사용한다.(I = {I(1),I(2),(3),,,,I(k)}라고 할 때 I에 대한 모든 부분집합의 개수는 공집합을 제외하고 $2^k-1$ 이다)

---

# Apriori Pruning Principle

---

이 알고리즘은 최소지지도 이상을 갖는 항목만 가지고 신뢰도를 계산하도록 하는 알고리즘이다.

따라서, 최소지지도 이하인 Itemset들의 SuperSet까지 모두 Pruning할 수 있다. 

Apriori Algorithm

1. 1-itemset의 지지도를 먼저 계산하고, 그 중 최소지지도를 넘는 item만 가지고 itemset을 구성한다.

2.그리고 그걸 이용하여 2-itemset을 조합해보고 그 중 최소지지도를 넘는 item만 가지고 2-itemset을 구성하고, 넘지 못하는 itemset들의 Superset들도 모두 pruning한다. 

이 때, k-itemset을 가지고 (k+1)-itemset을 구성하는 방법은 우선, k-itemset을 먼저 Sorting 하고, (k-1)까지 똑같은 item끼리 k-1까지는 똑같이 두고 k번째 item을 조합하여 (k+1)-itemset을 구성한다. 그리고, 새롭게 구성한 (k+1)-item의 subset중에서 최소지지도를 넘지 않는 subset이 있다면, 삭제한다.