연관규칙 알고리즘

빈발항목을 찾는 연관 규칙 3가지 Apriori, Eclat, FP-Growth

 

연관 규칙 탐사

1단계) 트랜젝션으로 부터 최소 지지도 이상의 빈발항목을 생성하고 (search & counting)

2단계) 빈발 항목의 각 항목집합의 부분 집합을 조합하여 신뢰도나 향상도가 좋은 연관규칙을 탐사하는 과정이다.

 

 

1. Apriori 알고리즘

트랜젝션으로 부터 최소 지지도 이상의 빈발항목을 생성하는 알고리즘이다.

Apriori 원리를 이용하여 효율적으로 빈발항목을 생성하며, 너비 우선 검색을 한다. 

원리

- 빈도가 높은 항목집합(item set) I의 어떤 부분집합도 I보다 같거나 높은빈도(지지도)를 갖는다.

{a,b,c}가 5번 나타난다면, {a,b},{b,c},{a,c}는 5번 이상 나타난다. 

- 마찬가지로 항목집합 I에 추가항목 i가 추가 된다면, 이는 기존의 I보다 높은 빈도(지지도)를 가질 수 없다. 

{a,b,c}가 5번 나타난다면, {a,b,c,d}는 5번 이하로 나타난다. 

 

문제점

잦은 데이터 검색 횟수로 인해 속도가 엄청 느리다. 

 

2. Eclat 알고리즘

 

- Eclat은 Apriori의 단점인 잦은 데이터 검색 횟수를 감소시킨다.

- 동작 방식은 Apriori와 유사하나 수직 방향 vertical로 데이터를 읽어 들여, 항목 별 트랜젝션 ID 집합을 이용하여 빈발항목을 구성한다. 

- Eclat은 DB 검색이 감소되어 Apriori 대비 성능면에서 우수한 것으로 알려져 있으나(small to medium size), Eclat은 트랜젝션 건수가 커지면 메모리 사용량이 증가하여 Apriori 대비 성능이 떨어질 수 있다.(large size)

 

차이점

Apriori는 너비 우선 검색

Eclat은 깊이 우선 검색을 수행

 

문제점

많은 트랜잭션을 저장하면서 메모리 사용 문제 발생

3. FP-Growth 알고리즘 

Apriori와 Eclat의 단점을 모두 완화한 알고리즘,

- 연산 과정은 복잡

- 데이터 사이즈가 클 수록 유리

진행방식

1) 2번의 데이터 스캔으로 FP-Tree를 완성 시키고, 이를 데이터베이스에 저장한다.

2) FP-Tree를 재귀적으로 순회 하면서 Frequent Pattern 즉 빈발항목을 생성하여 별도 후보항목집합을 생성하지 않는 것이 장점이다.

 

장점

Apriori 대비 대체로 수행속도가 빠르고 메모리 사용량이 절감되는 효과