아프리오리(Apriori) 알고리즘 동작원리

 

 

아프리오리(Apriori) 알고리즘 동작원리

아프리오리 알고리즘의 대략적인 절차는 아래와 같습니다.

상향식(bottom-up) 접근 방법을 사용하는 Apriori 알고리즘은 한 번에 하나씩 아이템 집합을 순회하며 동작합니다. 후보 그룹은 데이터를 검증받습니다. 더 이상 집합 확장이 없으면 알고리즘은 멈춥니다.

 

 

	아이템 집합 다음과 같은 아이템 집합이 있으며, 지지도 임계값이 3이라고 가정하겠습니다.   {1,2,3,4} {1,3,4} {1,2} {2,3,4} {3,4} {2,4}
가	개별 아이템 (1-항목집합) 중에서 최소 지지도 임계치를 넘는 모든 빈발품목 집합(frequent item set) 즉, 1-항목 빈발항목집합을 찾는다.   각 아이템의 지지도를 계산한다. {1} = 3 {2} = 4 {3} = 4 {4} = 5
나	'가' 단계에서 찾은 개별 아이템(1-항목집합)만을 이용해서 2가지 아이템으로 이루어진 2-항목집합의 빈발품목 집합 후보 세트들을 생성한다.   다음 단계에서는 쌍(pairs)으로 지지도 구합니다. {1,2} = 2 {1,3} = 2 {1,4} = 2 {2,3} = 2 {2,4} = 3 {3,4} = 4
다	'나' 단계에서 만들어진 빈발항목 집합 후보 세트 중 최소 지지도 이하인 2-항목 집합들을 제거합니다. 즉, 최소지지도 임계치를 넘는 2-항목 빈발항목 집합들을 찾는다.   {1,2}, {1,3}, {1,4}, {2,3}은 앞서 정한 지지도 임계값(3) 이하이므로 원소가 세 개인 집합 후보에서 기각한다. {1,2} = 2 {1,3} = 2 {1,4} = 2 {2,3} = 2 {2,4} = 3 {3,4} = 4
라	위의'다' 단계에서 찾아진 2-항목 집합을 이용하여, 최소 지지도를 넘는 3-항목 집합의 빈발항목 집합들을 찾는다.   이 예제에서는 임계값이 넘는 2, 3, 4 원소를 가진 세 개인 집합 조합이 하나 나온다. {1,2,3,4}는 1이 존재하므로 제외됩니다. 제외시킨 연산으로 빈도 아이템 집합을 구하였다.   {2,3,4} = 1
마	위의 과정과 같은 방법으로 k-항목 빈발항목 집합을 확정할 때까지 반복합니다. 새로운 빈발항목 집합이 생성되지 않으면 집합 확장을 중단합니다.
바	'마' 단계까지 완료된 후 생성된 빈발항목 집합을 대상으로 최소 신뢰도 임계치를 넘는 모든 연관 규칙을 생성합니다.   예를 들어 '마' 단계까지 진행하고 난 뒤, 결과 빈발항목 집합 {A,B}를 찾았다면, 해당 빈발항목 집합에서 생성될 수 있는 모든 후보 연관규칙 {A}→{B}와 {B}→{A}를 찾은 뒤, 이 중에서 최소 신뢰도 임계치를 넘는 연관규칙만 최종 연관규칙으로 결정하게 됩니다.

 

위와 같이 검색할 아이템(항목)집합을 제한함으로써, 방대한 거래 데이터에서의 가능한 모든 조합들의 경우의 수를 고려하지 않고, 효율적으로 연관 규칙을 만들어 낼 수 있게 됩니다.