Apriori 알고리즘의 한계점
Apriori 알고리즘에서 병목 현상이 가장 크게 발생하는 지점은 후보 생성 단계입니다. 예를 들어, 전체 아이템이 π = {item1, item2, ..., itemm}이라면, 가능한 아이템 세트의 개수는 2m이 됩니다. 이 알고리즘은 단계별로 실행되는 구조이므로 먼저 후보 생성 단계에서 규칙을 만드는 과정이 끝나야 다음 단계로 넘어갈 수 있습니다. 이러한 구조상의 단점 때문에 Apriori 알고리즘은 많은 수의 아이템을 처리하는 데는 적합하지 않습니다.
FP-growth 알고리즘
FP-growth 알고리즘 또는 빈출 패턴 성장(frequent pattern growth)은 Apriori 알고리즘의 개선 버전입니다. 이 알고리즘은 다음과 같은 두 단계로 구성됩니다.
• FP-트리 생성
• 빈출 패턴 마이닝
각 단계를 하나씩 알아봅시다.
FP-트리 생성
다음 테이블과 같은 거래 데이터를 예로 들어 보겠습니다. 이 테이블은 0이 많이 들어 있는 희소 행렬(sparse matrix)입니다.
▼ 표 6-4 거래 기록 예시(0이 많이 들어 있는 희소 행렬)
|
ID |
bat |
wickets |
pads |
helmet |
ball |
|
t1 |
0 |
1 |
1 |
0 |
0 |
|
t2 |
1 |
1 |
1 |
1 |
0 |
|
t3 |
0 |
0 |
0 |
1 |
1 |
|
t4 |
1 |
0 |
1 |
1 |
0 |