아프리오리 알고리즘
IT 위키
(Apriori 알고리즘에서 넘어옴)
- Apriori Algorithm
- 최소 지지도를 넘는 빈발 항목집합을 항목 수를 하나씩 늘려 가며 찾는 연관 분석 알고리즘
1994년 아그라왈과 스리칸트가 제안했다. 아래의 성질을 미리(a priori) 이용해 검사할 후보를 줄이는 것이 핵심이다.
- 어떤 항목집합이 빈발하면 그 부분집합도 모두 빈발하다.
- 뒤집으면 어떤 항목집합이 빈발하지 않으면 그것을 포함하는 어떤 집합도 빈발하지 않다.
- 그래서 빈발하지 않은 집합을 포함하는 후보는 아예 만들지 않고 가지치기한다.
- 최소 지지도를 설정한다.
- 개별 품목 중에서 최소 지지도를 넘는 것을 모두 찾는다.
- 앞 단계에서 찾은 개별 품목만을 이용해 두 항목 집합의 후보를 만들고, 그중 최소 지지도를 넘는 것을 찾는다.
- 앞 단계에서 찾은 집합을 결합해 세 항목 집합을 만들고 같은 방식으로 추린다.
- 더 이상 빈발 항목집합이 나오지 않을 때까지 반복한다.
- 찾은 빈발 항목집합에서 연관 규칙을 뽑는다.
- 단계마다 데이터베이스를 처음부터 다시 훑어야 해 입출력 부담이 크다.
- 후보 항목집합이 많아지면 메모리를 많이 쓴다.
- 이를 개선한 것으로 FP-Growth, DHP 등이 있다.
