Apriori / FP-Growth Algorithm

본 개념은 Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber)서적을 바탕으로 합니다.

 

Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber) 

 

 

안녕하세요. 컴공녀신 입니다.

오늘은 연관규칙 기법 중  유용하게 활용되는 Apriori 와 FP-Growth 알고리즘에 관해 알아보고자 합니다.

 

# 1. Apriori 

Apriori 알고리즘 설명에 앞서 연관규칙에 관한 개념을 살~짝 짚고 넘어갈께요.

연관규칙이란 X->Y, X가 발생할 때 Y도 발생 할 경우를 의미합니다. 쉽게 설명하자면 {맥주}를 구매할 때 {기저귀}를 구매할 확률이 높습니다. 또한, {맥주, 기저귀, 땅콩 } 이 아이템 셋이 자주 발생한다면, {맥주, 기저귀} 또한 자주 발생합니다.

이렇게 어떤 두 아이템 집합이 번번히 발생하는가를 알려주는 일련의 규칙들을 생성하는 알고리즘입니다. 장바구니 분석이라고도 하죠.

 

알고리즘 수행 과정은 다음과 같습니다.

Aprioiri Algorithm

1. First, Scan DB once to get frequent 1-itemset. 1-itemset means that has only one itemset such as {A}, {B}, {C} etc..우선, 1개의 아이템셋 빈번 횟수(=지지도)를 얻기 위해 Database를 전체 돌며 셉니다.  

2. Second, Count support that satisfied bigger than initial minimum support. Then, generate candidate ite msets of length (K+1) from frequent itemsets of length K. At this time, use Self-Joining to generate candidate.두번째는, 초기에 지정해둔 최소 지지도 미만인 아이템셋을 지워줍니다. 그림에서는 초기 최소 지지도 = 2 보다 작은  {D} 원소가 삭제됩니다. 그리고 남은 원소들로 self-joining (=합집합)연산을 수행하여 2개의 아이템셋으로 만들어 줍니다. 

3. Third, Test the candidates against DB to get K+1 Frequent item sets. It called Pruning deleting items that do not satisfy the minimum support.세번째, 두번째 스캔을 하며 빈번 횟수를 세줍니다. 그리고 최소 지지도 =2 보다 작은 원소 집합을 삭제해 줍니다.

4. Fourth, Calculate Support and Confidence for each Frequent itemset.
   네번째, 각 빈번 아이템셋에 대한 지지도와 신뢰도를 계산해줍니다.

5. Last, The Important thing is that iterate when no frequent or candidate set can be generated.
    더이상 빈번 아이템셋이 발생하지 않을 때까지 2번 step부터 반복해 줍니다.

여기서 지지도, 신뢰도, 향상도에 수식에 관해 잠깐 알아보고 갈께요.!

* Support : probability that a transaction contains X U Y 

두 항목 X와 Y의 지지도는 전체 거래 건수 중에서 항목집합 X와 Y를 모두 포함하는 거래 건수의 비율을 말합니다.  지지도는 좋은 규칙(빈도가 많은, 구성비가 높은)을 찾거나, 불필요한 연산을 줄일 때(pruning, 가지치기)의 기준으로 사용합니다.

* Confidence : conditional probability that a transaction having not only X but also Y

항목집합 X를 포함하는 거래 중에서 항목집합 Y도 포함하는 거래 비율 (조건부 확률) 을 말합니다. 신뢰도가 높을 수록 유용한 규칙일 가능성 높다고 할 수 있습니다.

* Lift : how many times more often X and Y occur together than expected if they were statistically independent.

항목 X가 주어지지 않았을 때의 항목 Y의 확률대비 항목 X가 주어졌을 대 항목 Y의 확률 증가 비율을 말합니다. X와 Y가 서로 독립이면 Lift = 1 입니다.

이어서 Apriori sudo code를 보겠습니다.

Apriori Pseudo-code

# 2. FP-Growth

두번째 연관규칙 알고리즘은 FP-Growth 입니다. FP-Growth의 가장 큰 특징은 후보군들(candidates)을 만들지 않는다는 점인데요. Apriori 알고리즘은 각 케이스 마다 DB를 스캔하며 후보군들을 만들기 때문에 큰 데이터에 대해선 수행시간이 오래 걸립니다. 이러한 문제점을 개선하기 위한 방법이 FP-Growth 알고리즘 입니다. 이를 위해 트리와 링크드 리스트 자료구조를 사용하여 구현합니다. 그렇기에 수행시간이 Apriori 보다 훨씬 빠른 장점을 가지고 있습니다. 

 

수행과정을 보겠습니다.

 

1. 우선, DB를 한번 스캔하고, 1 빈발 품목을 찾습니다. 

2. 리스트에 빈발이 높은 순서대로 넣습니다. (내림차순 정렬)

3. DB를 한번 더 스캔하고, FP-Tree를 만듭니다. 이때 root node는 null 입니다.

4. FP-Tree 만들기. 우선, 첫번째 정렬된 빈번 아이템을 가지고 만들어 보겠습니다.

• {f, c, a, m, p} f 노드가 존재 하지 않기 때문에 f item에 대한 node를 새로 만들고 1 이라고 카운팅 합니다. 그리고 다음 c item을 c노드가 없기 때문에 f 밑에 노드를 달고 1 카운팅. a도 c밑에다가 노드를 만들고 1 카운팅. 다음 m을 a 밑에다가 노드로 만들고 1 카운팅. p를 m 밑에다가 노드로 만들고 1카운팅. 이렇게 초기엔 중복되는 노드가 존재하지 않으니깐 모두 새로 생성해서 하위 노드로 만들어 줍니다.

• {f, c, a, b, m} 다음 빈번 아이템 셋을 보겠습니다. f item은 이미 앞서 만든 노드가 있기 때문에 노드를 새로 만들지 않고 1 만 카운팅 해줍니다. 그럼 f는 2가 되겠습니다. 다음 c도 1 카운팅. 다음 a도 1 카운팅. 그 다음 b를 보면 노드가 존재하지 않습니다. 그렇기에 새 노드를 만들어 줍니다. 그리고 1 카운팅 합니다. 마지막 m은 이미 노드가 존재하기 때문에 1만 카운팅 해줍니다. 

• 이렇게 모든 빈번 아이템을 모두 스캔하며 FP-Tree를 완성합니다.

헤더 테이블의 헤드를 따라가면서 카운팅하면 해당 아이템의 support를 알 수 있고, 상위 노드 부터 원하는 노드까지 따라가면 그 마지막 노드의 카운팅 값이 따라온 경로의 집합인 support 입니다. 

e.g. f -> c 라 할 때 fc의 support = 3 입니다.

 

이렇게 트리를 만들고나면, 위의 표 처럼 Conditional pattern bases를 만들수 있습니다. 이는 가장 말단부터 작성합니다. p의 입장에서는 fcam는 2번 출현했고, bc는 1번 출현했습니다. m은 fca가 2번(트리 왼쪽부터), fcab는 1번 입니다. 이런식으로 반복하여 작성할 수 있습니다.

 

아래의 그림은 FP-Tree의 특성을 잘 나타내는 그림입니다.

m이 주어졌을 때 자주 발생하는 패턴을 뽑는 방법을 설명합니다 예를들면, m:2와 m:1 m의 두 노드가 있는데 있는데, f는 두 m에서 시작해도 항상 만나기 때문에 fm은 빈번 횟수 2와 1를 더한 3 입니다. 이와 값이 fp트리를 만들면 자주 발생하는 서브셋 또한 찾기 쉬운 장점이 있습니다.