뽀또12

인공지능을 공부하는 사람들하고 많은 지식을 공유하고, 제가 아는 것을 많이 알려드리고 싶습니다.

정말 하고 싶은게 너무 많아요. 모두들 항상 즐겁고 행복하게 열심히 삽시다! 오늘도 파이팅입니다!

업데이트:

카테고리: , ,

빈발 항목집합 생성

그림 1은 $I={a,b,c,d,e}$에 대한 항목집합 격자(lattice) 구조를 보여준다.

그림 1
그림 1

그림 1에서 보는 바와 같이 가능한 모든 항목집합 후보군을 생성하고 각각의 지지도 카운트를 측정해야한다. 그림 2는 그런 과정을 보여준다.

그림 2
그림 2

그러나 이런 접근법은 $O(NMw)$의 계산 복잡도가 필요하므로 비용이 많이 들 수 있다. N은 트랜잭션의 수, $M=2^k-1$은 항목집합들의 경우의 수이고 w는 하나의 트랜잭션에 존재하는 항목들의 개수인 트랜잭션 폭(transiaction width)이다.

계산 복잡도를 줄이기 위한 3개의 주요 접근법들은 다음과 같다.

  1. 후보 항목집합들의 개수(M)을 줄이기
  2. 비교 횟수 줄이기
  3. 트랜잭션들의 개수 줄이기

후보 항목집합을 만들었을 때, 크기가 3이라고 해보자. 그럼 그림 2의 TID=1인 트랜잭션은 지지도 카운트를 할 필요가 없다. 그래서 항목집합의 길이보다 작은 것은 아예 제외하고 시작한다.

먼저 1번 방법부터 알아보겠다.


Apriori 원리

Apriori 원리란, 만약 한 항목집합이 빈발하다고 여겨졌으면, 그것의 모든 부분 집합들도 빈발함을 의미한다. 아래 그림 3은 항목집합 ${c,d,e}$가 빈발하다고 여겨짐으로써 아래의 관련된 모든 부분집합들이 빈발 항목집합들로 여겨짐을 보여준다.

그림 3
그림 3

사실 당연한 얘기다. ${c,d,e}$가 빈발하다는 것은 지지도 카운트가 threshold를 넘었다는 것이므로, 각 요소 c,d,e가 많은 트랜잭션에 포함된다는 이야기다. 그렇다는 것은 c,d,e의 조합으로 이루어진 부분집합들은 무조건 포함된다는 뜻이 된다. 즉, 한 항목집합의 부분집합들은 부모 항목집합의 지지도를 절대 초과하지 못한다. 이런 성질을 지지도 척도의 비-단조형(anti-monotone)이라고 한다. 이것을 이용하면 빈발 항목집합이 되지 못하는 경우엔 나머지 부분집합들을 전부 가지치기(pruning)할 수 있다는 것이다. 그림 4는 그 예시를 보여준다.

그림 4
그림 4

이 방식을 지지도-기반 가지치기(support-based pruning)이라고 부른다.


Apriori 알고리즘

Apriori 알고리즘은 Apriori 원리를 통한 지지도-기반 가지치기를 사용한 최초의 연관 규칙 탐사 알고리즘이다. 그림 6은 그림 5의 트랜잭션 데이터를 바탕으로 지지도 threshold를 60%로 가정(지지도 카운트 >= 3)한 가지치기 과정을 보여준다.

그림 5
그림 5
그림 6
그림 6

왼쪽 테이블은 1-항목집합을 보여준다. 개수는 $\binom{6}{1}=6$이다. Cola와 Eggs는 지지도 카운트가 threshold를 넘지 못했으니 Apriori 원리에 의해 버리도록 하자.

가운데 테이블은 남은 항목들을 이용해서 2-항목집합을 만들고 지지도 카운트를 측정한 모습이다. 가지치기를 하지 않았다면 2-항목집합의 개수는 $\binom{6}{2}=15$가 된다. 그러나 가지치기를 통해 $\binom{4}{2}=6$이 된다. {Beer,Bread}와 {Beer,Milk}는 지지도 카운트가 threshold를 넘지 못했으니 제거하자.

오른쪽 테이블은 2-항목집합 4개로 3-항목집합을 만든 모습이다. Bread,Diapers,Milk가 겹쳐있기 때문에 만들 수 있는 3-항목집합은 1개이다. 그러나 모든 항목들로 3-항목집합을 만든다면 개수는 $\binom{6}{3}=20$ 이다.

자, 그럼 Apriori 가지치기 전략의 유효성을 판단해보자. 먼저 가지치기를 하지 않았을 때의 모든 k-항목집합(k=1,2,3)의 개수는 다음과 같다.

\[\binom{6}{1} + \binom{6}{2} + \binom{6}{3} = 6+15+20 = 41\]

Apriori 가지치기를 했을 때의 개수는 다음과 같다.

\[\binom{6}{1} + \binom{4}{2} + 1 = 6+6+1 = 13\]

그림 5의 간단한 예조차도 무려 68%의 감소를 보인다. 그림 6의 방식을 알고리즘으로 작성하면 다음과 같이 작성된다고 한다. 보기만 하고 넘어가자.

그림 7
그림 7

Apriori 알고리즘의 빈발 항목집합 생성 부분에는 2개의 중요한 특성이 있다.

  1. 레벨별(level-wise) 알고리즘

    1-항목집합의 빈발 항목집합들을 찾고 다음으로 2-, 3-, … Max- 의 최대 크기의 빈발 항목집합들을 찾을 때까지 한 레벨씩진행함을 의미한다.

  2. 생성 및 검사(generate-and-set) 전략

    k+1 레벨의 새로운 후보 항목집합은 k 레벨에서 찾아진 빈발 항목집합에 의해 생성되고 지지도 카운트를 계산한 후, threshold를 사용해서 검사를 한다. 여기서 알고리즘에 필요한 총 반복 횟수는 $k_{max}+1$이고, $k_{max}$란 빈발 항목집합의 최대 크기를 얘기한다.


후보 생성과 가지치기

그림 7의 알고리즘에서 5번째 줄의 candidate-gen 함수와 6번째 줄의 candidate-prune 함수는 다음의 두가지 연산을 수행한다.

  1. 후보 생성(candidate-get)

    이 함수는 k번째 레벨에서 찾아진 빈발 k-항목집합을 기반으로 새로운 후보 (k+1)-항목집합을 생성한다.

  2. 후보 가지치기(candidate-prune)

    이 함수는 지지도-기반 가지치기를 사용해 k 레벨에서 빈발하지 않은 부분집합을 가진 후보 k-항목집합들을 제거한다.

후보 생성(Candidate Generation)

먼저 후보 생성에 대해서 알아보자. 후보 생성 절차로 인해 k번째 레벨에서의 모든 빈발 k-항목집합들이 k+1번째 레벨에서의 빈발 (k+1)-항목집합들의 부분집합에 속한다면 이를 완전하다(complete)하다고 한다. 이 개념은 계속해서 언급될 것이므로, 미리 정의를 했다.

그림 8
그림 8

후보를 생성하는 가장 기본적인 방법은 그림 8의 완전 탐색(Brute Force)이 있다. 이 방법은 그냥 말그대로 모든 조합의 경우를 다 만드는 것이므로 너무 비효율적이다. 그래서 $F_{k-1}\times F_1$ 방법과 $F_{k-1}\times F_{k-1}$ 방법을 사용한다. 전자에 대해선 설명하지 않겠다. 왜냐하면 Apriori 알고리즘의 candidate-gen 함수에 사용되는 후보 생성 방법은 후자를 사용하기 때문이다.

  • $F_{k-1}\times F_{k-1}$ 방법

    이 방법을 사용하기 위해서 항상 모든 빈발 항목집합들을 사전순으로 배열하는 것을 잊지 말자. 2개의 빈발 (k-1)-항목집합들이 있다고 해보자. 이 방법은 두 항목집합들의 처음에 k-2번째까지의 항목들을 서로 비교해서 전부 같다면, 두 항목집합을 병합해서 새로운 후보 항목집합을 생성한다. 예를 들어, 3-항목집합을 만들기 위해 2-항목집합들 {Bread,Diapers}, {Bread,Milk}가 있다고 해보자. k-2=3-2=1번째 항목들을 비교하면, Bread,Bread로 같으므로 두 항목집합은 합쳐서 새로운 후보 항목집합 {Bread,Diapers,Milk}을 생성할 수 있다. 그림 9는 예시를 보여준다.

    그림 9
    그림 9

    두 빈발 항목집합을 합병하는 방법은 여러가지가 있다곤 하는데 이정도만 일단 알아두자.

후보 가지치기(Candidate Pruning)

이제 후보 항목집합들이 생성됬다고 가정하고, 가지치기를 어떻게 할 것인지 알아보자. 후보 k-항목집합인 X={a,b,c,d,…z}가 있다고 해보자. 여기서 항목들을 한번씩 빼서 k-1개의 항목들로 이루어진 부분집합들이 하나라도 빈발하지 않다면, 그 후보는 가지치기된다. 예를 들어 항목 e를 뺀 {a,b,d,…z} 부분집합이 있다고 해보자. 이것이 빈발하지 않다면, 원래 항목집합인 X를 후보군에서 빼버리는 것이다.

k-1보다 작은 부분집합들은 고려하지 않아도 되는게, 애초에 k-1개의 항목을 갖는 부분집합들이 k-2개의 항목을 갖는 부분집합들이 빈발하기 때문에 가지치기 후 살아남은 것들이기 때문이다.


지지도 계산 (Support Counting)

후보 가지치기 단계에서 살아남은 각 후보 항목집합에 대해 발생 빈도수를 결정하는 과정을 지지도 계산이라고 한다.

가장 쉬운 brute-force 방법은 모든 후보 항목집합들을 전부 일일이 모든 트랜잭션에 비교해보는 것인데, 이것은 너무나도 비효율적인 접근이다. 그래서 우린 해시 트리를 이용해서 지지도 계산을 해야한다!

해시 트리를 이용한 지지도 계산

이 방법을 사용하기 전에, 먼저 트랜잭션을 후보 k-항목집합들과 비교하기 위해서 k개의 항목으로 이루어진 부분집합으로 쪼개야한다.

  • 트랜잭션의 k개로 이루어진 부분집합 만들기

    이것을 가장 효율적으로 구현하는 것이 바로 DFS를 이용하는 것이다. DFS를 이용하면 사전순으로 나열된 부분집합들을 만듦으로써 중복이 없는 부분집합들을 생성할 수 있다. 그림 10을 보자.

    그림 10
    그림 10

    트랜잭션 t가 {1,2,3,5,6}으로 주어진다면, 우리는 첫 번째 수를 1,2,3으로만 선택할 수 있다. 왜냐하면 5,6은 사전순으로 나열된 3개를 만들 수 없기 때문이다. 그게 바로 그림 10의 Level 1 과정이다.

    이어서 두 번째 수는 각 가지마다 경우가 다른데, 1이 첫번째 수라고 한다면 두 번째로 올 수 있는 수는 2,3,5가 된다. 6이 되면 세 번째 수로 올 수 있는 것이 없기 때문에 배제한다. 이것이 Level 2 과정이다.

    마지막으로 Level 3은 각각의 가지에 따라 수를 써주면 되고, 이로써 현재 트랜잭션 t가 가질 수 있는 모든 3-항목집합의 경우가 완성된다.

    한창 자료구조 알고리즘을 공부하고 있어서 DFS와 백트래킹을 사용해서 3-항목집합을 작성해봤다.

      
import copy 
  
subsets = []
transaction = [1,2,3,5,6]
len_tran = len(transaction)
K = 3
def dfs(n,subset):
  global K,len_tran
  if len(subset) == K :
    subsets.append(copy.deepcopy(subset))
    return
  
  for i in range(n,min(len_tran,len_tran-K+n+1)) :
    subset.append(transaction[i])
    dfs(i+1,subset)
    subset.pop()
dfs(0,[])
  
print(subsets)

  • 해시 트리 생성

    그림 11
    그림 11

    그림 11은 항목 1,2,3,5,6에서 여러 단계의 후보 생성 및 가지치기를 거친 후 리프노드에 있는 3-항목집합들 15개를 해시 트리로 구분해 놓은 것이다. (15개를 일일이 나열하기엔 귀찮아서 생략~!) 3개의 가지는 해시 함수 $h(p)=(p-1) \% 3$으로 쪼개지게 된다. 그림 11의 상단에 나와있다.

    그럼 이제 트랜잭션 t={1,2,3,5,6}을 가져와서 해싱하는데, 앞서 우린 t의 부분집합들을 DFS로 구했었다. 그래서 해시 함수를 따라들어가면서 만나는 리프노드에 각각의 부분집합들이 존재하는지 확인해서 카운팅을 하면 그것이 바로 지지도 계산(support counting)이 되는 것이다.


계산 복잡도

실행 시간과 저장 공간을 둘 다 포함하는 Aprior 알고리즘의 계산 복잡도는 다음의 요소들로 영향을 받는다.

지지도 threshold

threshold가 낮을 수록 더 많은 빈발 항목집합들이 생성되고 크기 또한 커지므로 탐색과정에서 계산 비용을 증가시킨다.

항목들의 개수(차원)

항목들의 개수가 증가하면 항목들의 지지도 카운트들을 저장하기 위해 공간이 늘어난다.

트랜잭션들의 개수

Apriori 알고리즘은 모든 트랜잭션에 대해 항목집합들을 계속 비교하므로 당연히 시간이 늘어난다.

평균 트랜잭션 폭(average transaction width)

트랜잭션 폭이란, 트랜잭션의 항목들의 수를 얘기한다. 이것의 평균이 크다는 것은, 빈발 항목집합의 최대 크기를 키우고, 지지도를 계산할 때 해시 트리 순회 횟수를 증가시킨다.

빈발 1-항목집합들

빈발 1-항목집합들의 계산 비용은 트랜잭션의 폭 w와 트랜잭션의 개수 N으로 O(Nw)의 시간을 요구한다.

후보 생성

후보 k-항목집합을 생성할 땐 $F_{k-1}\times F_{k-1}$ 방법 을 사용하는데, 최대 k-2번의 equality comparison이 필요하다. (나중에 다시보자)

지지도 계산

지지도를 계산할 떄도 계산 비용이 든다. (나중에 다시보자)

나중에 볼 사이트 : https://medium.com/analytics-vidhya/association-analysis-in-python-2b955d0180c

5 분 소요

참고