Association Rule

 

Frequent Item Set 이란?

데이터를 관측할 때, 반복적으로 발견되는 패턴을 의미한다. 반복적으로 발견되어야 미래에 대한 예측이 효과적이므로 유의미하다.

전체 벌어진 경우 중에 몇 번 그 사건이 벌어졌는지에 대한 비율이 "일정 기준 이상"이면 frequent 하다고 본다.

 

① absolute support: 그냥 개수를 세는 것

② relative support: absolute support 를 전체 경우로 나눈 것

⇨ 특정 item set 이 "Minimum Supprot Threshold" 이상이면 frequent 하다고 본다.

 

 

Association Rule 이란?

어떤 사건이 얼마나 자주 함께 발생하는지, 서로 얼마나 연관되어 있는지 표시하는 규칙이다.

Frequent Item Set 을 한 차례 더 가공한 것이 Association Rule 이다.

 

측정 Parameter

① support: 전체 경우의 수에서 두 item 이 같이 나오는 비율

② confidence: x 가 나오는 경우의 수에서 x 와 y 가 함께 나오는 비율 (조건부 확률이라고 생각하면 된다.)

 

유의미한 Association Rule 이 되기 위한 조건

① Supprot가 Supprot Minimum Threshold 이상이어야 한다. (즉, frequent item set 이어야 한다.)

 

 

② Confidence 가 Confidence Minimum Threshold 이상이어야 한다.

 

Association Rule 을 찾는 대표적인 두 가지 방법

① Apriori Algorithm

② FP-Growth Algorithm

 

 

<Apriori Algorithm>

어떠한 두 item 의 집합이 frequent 하게 발생하는지를 알려주는 규칙을 생성하는 알고리즘이다.

Lattice 구조 → 어떠한 item set 이 frequent 하지 않다면 그것의 모든 superset 은 절대로 frequent 할 수 없다.

 

알고리즘

① 각각의 item 에서 Length=1 인 것의 support 를 검사한다. (minimum supprot threshold 보다 작은 것은 제거한다.)

② Length=2 인 조합을 구성하고 support 를 검사한다.

③ 기준을 정하고(ex. 앞만 보고 결정하겠다.), 이에 따라 Length=3 인 조합을 구성한다. 

④ 만들어진 Length=3 인 조합에서, 기준에서 벗어난 것의 supprot 를 검사한다.

⑤ 조합이 더 이상 나타나지 않을 때까지 반복한다.

 

단점

① 너비 유선 탐색이므로 depth 가 길어지면 candidate 가 많아지면 메모리가 초과될 수 있다.

 

 

<FP-Growth Algorithm>

Apriori Algorithm 을 개선한 알고리즘이다.

 

알고리즘

① Length=1 의 모든 supprot 를 검사한다.

 

② Support 가 Minimum Supprot 이상인 것들만 골라낸 후, 내림차순으로 재정렬한다.

③ Root 를 시작으로, FP Tree 를 만든다. (옆에 supprot 와 link 를 함께 작성한다.)

④ 각각의 Conditional Tree 를 만든다.

⑤ 조합이 더 이상 나오지 않을 때까지 Conditional Tree 를 반복하여 만든다. 

 

장점

① Basket Data 에서 필요한 것들만 압축해서 표현한 자료구조이다.

 

② Candidate 를 만들지 않고, FP Tree 만 만들면 되므로 빠르다.

③ 깊이 유선 탐색이므로 메모리에 대한 부담이 적다.