A-Priori Algorithm

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

A-Priori Algorithm

A-Priori Algorithm이란 연관규칙을 찾는 알고리즘입니다.

빈도 쌍을 찾을 때,
메모리가 충분하면 하나의 패스로 바스켓 파일을 읽으면서,
가능한 모든 아이템 쌍을 만들고 1을 더하면서 카운트합니다.
카운트가 끝나면 모든 아이템 쌍에 대해 임계값 s 가 넘는지 검사합니다.

그러나 이러한 방식은, 전체 아이템 쌍이 메모리에 다 못 올라가면 사용할 수 없습니다.
앞선 포스팅에서 언급했던 것 처럼,
약 $2n^2$ byte 의 크기가 필요하여 메모리에 다 올리기가 어렵습니다.

그래서 A-Priori 알고리즘은,
한 번이 아닌 두 번의 데이터 패스로 나워서 수행하여
계산해야하는 쌍의 수를 줄이는 방식으로 설계되었습니다.

우선, A-Priori 알고리즘으로
두번의 패스로 빈도 아이템 쌍을 찾는 방식을 살펴보겠습니다.

The First Pass of A-Priori

첫번째 패스에서 두개의 테이블을 만듭니다.
첫번째 테이블을, 아이템의 이름을 1부터 n 사이의 정수로 변환해주는 테이블입니다. 이미 정수로 표현되어 있다면 사용할 필요는 없습니다.
다른 테이블은 카운트의 배열입니다.
i 번째 배열의 요소는 i 번호인 아이템이 나타난 횟수를 나타냅니다. 처음에는 0으로 초기화 됩니다.

바스켓을 읽을 때, 각 이이템을 보고, 정수로 변환합니다.
그리고, 정수를 카운트 배열의 인덱스로 사용하고 거기에 1을 더합니다.

Between The Passes of A-Priori

첫번째 패스가 끝난 후,
아이템의 카운트를 검사하고 s에 따라
어떤 싱글톤이 빈번한지 결정합니다.

이곳에서 아마 빈번한 아이템이 많지 않을 것 입니다.
이전에 s 를 충분히 높게 설정해서, 너무 많은 빈도 집합은 발생하지 않도록 정하였습니다. 일반적으로 s 이상인 아이템의 비율은 바스켓에서 1% 정도 되도록 설정합니다.

두번째 패스에 사용될,
빈도 아이템들에 대해 1부터 m 까지 새로운 숫자를 부여해줍니다.
이 테이블은 1부터 n 까지로 인덱스된 배열입니다.
i 에 대한 엔트리는 i 가 빈번하지 않으면 0 이고,
아니면, 1부터 m 까지의 유일한 정수를 갖습니다.
우리는 이 테이블을 frequent-items table 이라고 합니다.

The Second Pass of A-Priori

두번째 패스동안에는, 두개의 빈도 아이템으로 구성된 모든 쌍을 셉니다.
이전에 아이템이 빈번하지 않다면, 아이템으로 만들어진 쌍 또한 빈번하지 않다고 하였습니다.
그래서 이 작업으로 모든 가능한 빈번한 쌍을 구할 수 있습니다.
두번째 패스에서 필요한 공간은 $2m^2$ 바이트입니다. 이는 기존의 $2n^2$ 보다 작습니다.
바로 전 작업에서 넘버링 작업은 삼각행렬에서 인덱스를 표현하기 위해 필요합니다.
첫번째와 두번째 패스에서 사용된 메모리의 구조는 다음 그림과 같습니다.

빈번하지 않은 아이템을 제거하는 경우,
빈번하지 않은 아이템 절반을 제거하면, 다음 패스에서 아이템 쌍을 위한 공간을 3/4 절약할 수 있습니다.
3개 쌍을 사용하기 위해서는, 적어도 하나의 바스켓에서 나타난 두개의 빈도 아이템 쌍들만 세면 됩니다.

두번째 패스의 처리 방식은 다음과 같습니다.

1. 각 바스켓에 대해, 그것의 아이템들이 빈번한지 보기 위해 freq-item table을 봅니다.
2. 이중 루프를 사용해 바스켓에 있는 모든 빈도 아이템의 쌍을 발생시킵니다.
3. 각 쌍들에 대해, 데이터 구조(triangle or triple)에 카운트에 1을 더합니다.

2번째 패스 마지막에 쌍들이 빈번한지 파악하기 위해 카운트를 검사합니다.

A-Priori for All Frequent Itemsets

아이템 집합 크기 k 에서 다음 크기 k+1 로 넘어가는 패턴은 다음과 같이 정리 할 수 있습니다.
각 아이템 집합의 크기 k 에 대해 두 종류의 집합이 있습니다.

1. $C_k$ 는 k 크기의 후보 아이템셋들의 집합입니다. - 이 아이템셋은 실제로 빈번한지 결정하기 위해 세어봐야 합니다.
2. $L_k$ 는 k 크기의 실제 빈도 아이템셋의 집합입니다.

( + 여기서 k 는 다음과 같이 아이템들의 집합의 크기입니다.  $pair - {i_1, i_2},\ triple - {i_1,i_2,i_3}, k-size -{i_1,i_2,\dots,i_k}\ $)

한 집합에서 다음으로 가는 패턴은 다음과 같습니다.

C1 에서 시작하고 모두 싱글톤입니다. 데이터를 검사하기전, 어떠한 아이템도 빈번해질 가능성이 있습니다.
첫번째 Filter 단계는 모든 아이템을 세는 것입니다. 그리고 이 중 카운트가 s 가 넘는 아이템들이 집합 L1 이 됩니다.

C2 집합은 L1의 아이템에서 만들 수 있는 쌍입니다.
L1에 아이템이 둘다 있는지 검사합니다.
알고리즘의 두번째 패스는 모든 후보쌍을 세고, s 번 이상 나온 것들을 찾습니다. 그 쌍들은 L2를 형성합니다.

이 패턴은 2개 이상의 크기에서도 적용할 수 있습니다.
C3 는 L2안에 있는 쌍들 3개로 구성할 수 있는 후보 트리플의(3개짜리) 집합입니다.
여기서 L2가 많지는 않기 때문에 후보가 되는 쌍이 많지는 않을 것입니다. 그래서 삼중에서도 충분히 계산할 수 있습니다.
4개로 구성된 후보 쌍은, 같은 방식으로 트리플을 사용해 구성합니다.
마찬가지로, 우리는 k-1 크기의 집합을 사용하여 k 크기의 집합을 계산할 수 있습니다.

더 큰 빈도 아이템셋과 후보 집합의 구성은 패스에서 새로운 빈도 아이템셋을 찾을 수 없을 때까지 다음과 같이 동일한 방식으로 진행합니다.

1. $C_k$ 를 정의합니다.
   크기가 k 인 모든 아이템이 되는, 모든 후보들은 $L_{k-1}$ 에 있습니다.
2. $L_k$를 찾습니다.
   바스켓을 읽을 때 $C_K$에 있는 아이템셋만 세고, 카운트가 s 이상인 것들을 $L_k$ 로 둡니다.