Apriori

상향식(bottom-up) 접근 방법을 사용하는 Apriori 알고리즘은 한 번에 하나씩 아이템 집합을 순회하며 작동한다. 후보 그룹은 데이터를 검증받는다. 더 이상 집합 확장이 없으면 알고리즘은 멈춘다. 예를 들어 지지도 임계값이 3이라고 하자.

다음과 같은 아이템 집합이 있으면,

{1,2,3,4}

{1,3,4}

{1,2}

{2,3,4}

{3,4}

{2,4}

우선 각 아이템의 지지도를 계산한다.

{1} = 3

{2} = 5

{3} = 4

{4} = 5

다음 단계에서는 쌍(pairs)으로 구한다.

{1,2} = 2

{1,3} = 2

{1,4} = 2

{2,3} = 2

{2,4} = 3

{3,4} = 4

{1,2}, {1,3}, {1,4}, {2,3}은 앞서 정한 지지도 임계값(3) 이하이므로 원소가 세 개인 집합 후보에서 기각한다. 이 예제에서는 원소가 세 개인 집합 조합이 하나 나온다.

{2,3,4} = 1 ({1,2} 그룹에서 하나는 제외시켰다).

제외시킨 연산으로 빈도 아이템 집합을 구하였다.