빈출패턴 성장(FP-Growth) 알고리즘

 

 

빈출패턴 성장(FP-Growth) 알고리즘

·       ≒ Frequent Pattern Growth Algorithm

·       아프리오리 알고리즘은 나름대로 효율적으로 아이템 집합의 수를 제한함으로써 연관규칙 생성을 효율화하였지만, 결국 데이터 집합에 있는 각각의 아이템을 살피면서 빈발항목 집합의 조건에 포함되는지 아닌지를 판정해야 하므로, 빅데이터 상황에서는 이러한 처리 프로세스 자체가 엄청난 부담이 될 수 있습니다. 따라서 빅데이터 상황에서는 더욱 효율적으로 빈발항목 집합을 찾아내는 알고리즘이 필요하게 됩니다. 빈출패턴 성장(FP-Growth) 알고리즘은 바로 이런 목적을 위해 아프리오리 알고리즘을 개선한 알고리즘입니다.

 

·       기본적으로 최소 지지도 임계치 이상의 항목 집합을 찾은 뒤 최소 신뢰도를 넘는 연관규칙을 생성한다는 점에서는 아프리오리 알고리즘과 동일하나, 빈출패턴 성장(FP-Growth) 알고리즘은 빈발항목 집합을 찾을 때 아프리오리 알고리즘보다 개선된 자료구조를 사용하여 검색시간을 크게 줄입니다. 즉, 빈발항목 집합을 찾기 위해 FP-Tree(Frequent Pattern Tree)라는 자료구조에 데이터 집합을 생성합니다.

 

·       FP-Tree는 일반적으로 트리(Tree)와 유사하지만, 유사한 아이템 간에 서로 연결링크를 가지고 있다는 점에서 다릅니다. 데이터베이스에서 아이템의 발생횟수를 센 뒤 헤더 테이블에 저장하여 트리를 만들고 최소 지지도 임계값을 만족시키지 못하는 아이템은 버려지고 내림차순으로 정렬됩니다. 이렇게 줄여진 데이터 세트를 가지고 가장 긴 트리 가지가 있는 곳에서부터 주어진 최소 지지도 임계치 조건에 부합하는 모든 객체를 탐색하게 됩니다. 더 이상 최소 지지도 임계값을 만족하는 단독 아이템이 없다면, FP-Tree는 확장을 멈추게 됩니다. 이러한 빈출패턴 성장(FP-Growth) 알고리즘은 아프리오리 알고리즘과는 달리, FP-Tree라는 특별한 자료구조를 도입함으로써, 데이터 집합을 단 2번만 검색하게 되어 훨씬 효율적인 처리와 빠른 속도를 내게 됩니다. 첫 번째 검색 때는 모든 아이템의 발생 빈도를 계산하여 FP-Tree에 저장한 뒤, 두 번째 검색 때는 빈발 아이템에만 접근하게 됩니다.

 

https://en.wikipedia.org/wiki/Association_rule_learning