FP-Growth

FP-Growth(Frequent Pattern Growth) 알고리즘은 트리 구조(FP-Tree라고 부른다)다. 데이터베이스에서 항목의 발생 횟수를 세어 헤더 테이블에 저장하여 트리를 만든다.

두 번에 거쳐 인스턴스를 삽입하여 트리가 만들어진다. 최소 지지도 임계값을 만족시키지 못하는 아이템은 버려진다. 그렇지 않다면 내림차순으로 정렬된다.

FP-Growth 알고리즘이 4장에서 배운 베이지안 네트워크와 비슷하다고 생각할 수 있다. 줄여 놓은 데이터 세트를 가지고 FP-Growth 알고리즘은 바닥(가장 긴 가지가 있는 곳)에서 시작하여 주어진 조건 하에 있는 모든 인스턴스를 탐색한다. 더 이상 지지도 임계값을 만족하는 단독 아이템이 없을 때 트리는 확장을 멈추고, FP 트리의 다음 부분에서 시작한다.