FP-트리(FP-Tree)의 개념
FP-트리는 입력 데이터를 압축된 형태로 표현하는 자료구조입니다. 데이터셋을 한 번에 하나의 트랜잭션씩 읽어들이면서, 각 트랜잭션을 FP-트리 내부의 하나의 경로(path)로 매핑하는 방식으로 구성됩니다.
여러 트랜잭션이 동일한 아이템을 공유할 경우 해당 경로들은 서로 겹쳐지게 됩니다. 경로가 많이 겹칠수록 FP-트리 구조를 통해 더 높은 압축 효율을 얻을 수 있습니다.
만약 FP-트리의 크기가 메인 메모리에 저장될 만큼 충분히 작다면, 디스크에 저장된 데이터를 반복해서 읽어들이는 대신 메모리상의 트리 구조에서 직접 빈발 아이템셋(frequent itemset)을 추출할 수 있습니다. 이것이 FP-트리가 반복적인 디스크 접근이 필요한 기존 방식보다 효율적인 핵심 이유입니다.
노드의 구조
트리의 각 노드는 아이템 레이블(item label)과 함께 카운터(counter)를 포함하며, 이 카운터는 해당 경로에 매핑된 트랜잭션의 수를 나타냅니다. 초기 상태에서 FP-트리는 널(null) 심볼로 정의된 루트 노드만 존재합니다.
FP-트리 구축 과정
FP-트리는 다음과 같은 단계를 거쳐 구축됩니다.
1단계: 지지도 계산 및 아이템 필터링
먼저 데이터셋을 한 차례 탐색하여 각 아이템의 지지도(support count)를 계산합니다. 이후 빈발하지 않은(infrequent) 아이템은 제거하고, 빈발한(frequent) 아이템만 지지도 내림차순으로 정렬하여 유지합니다.
2단계: 두 번째 스캔을 통한 트리 생성
이어서 알고리즘은 데이터에 대해 두 번째 스캔을 수행하여 FP-트리를 생성합니다.
첫 번째 트랜잭션 {a, b}를 읽으면, 레이블이 a와 b인 노드가 생성되고, null→a→b 형태의 경로가 만들어져 해당 트랜잭션이 인코딩됩니다. 경로상의 모든 노드는 빈도 수 1을 가집니다.
두 번째 트랜잭션 {b, c, d}를 읽으면, b, c, d에 대한 새로운 노드 집합이 생성되며, null→b→c→d 경로가 형성됩니다. 이 경로상의 노드 역시 빈도 수 1입니다. 앞선 두 트랜잭션이 공통 아이템 b를 포함하고 있지만, 서로 공유하는 빈발 접두사(prefix)가 없기 때문에 두 경로는 분리(disjoint)되어 있습니다.
세 번째 트랜잭션 {a, c, d, e}는 첫 번째 트랜잭션과 빈발 접두사 아이템 a를 공유합니다. 따라서 세 번째 트랜잭션의 경로 null→a→c→d→e는 첫 번째 트랜잭션의 경로 null→a→b와 겹치게 되며, 이로 인해 노드 a의 빈도 수는 2로 증가합니다. 반면 새롭게 생성된 노드 c, d, e의 빈도 수는 1입니다.
3단계: 전체 트랜잭션 매핑 완료
이러한 과정은 모든 트랜잭션이 FP-트리 내 경로 중 하나에 매핑될 때까지 반복됩니다.
FP-트리의 장점
FP-트리의 크기는 압축되지 않은 원본 데이터보다 작습니다. 특히 마켓 배스켓(market basket) 데이터처럼 여러 트랜잭션이 많은 아이템을 공유하는 경우 그 효과가 더욱 두드러집니다. 이러한 압축 특성 덕분에 FP-growth 알고리즘은 데이터베이스 전체를 반복 스캔해야 하는 기존 방식들과 비교해 연산 비용을 크게 줄일 수 있습니다.