달력

2

« 2020/2 »

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29


 

 

아프리오리(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}를 찾은 뒤, 이 중에서 최소 신뢰도 임계치를 넘는 연관규칙만 최종 연관규칙으로 결정하게 됩니.

 

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

 

 

Posted by codedragon codedragon

댓글을 달아 주세요