Itemsets Computation Model

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

File Organization

일반적으로 데이터는 디스크에 저장이되고,
바스켓(=basket) 별로 저장됩니다.
데이터가 큰 경우 DFS 로 저장해서, MapReduce 로 처리할 수도 있습니다.

마켓에서 빈도 높은 품목을 분석하는 상황에서는,
아이템 데이터가 ‘맥주’, ‘콜라’ 와 같이 문자열로 구성되어 있을 것 입니다.

문자열을 그대로 사용하는 것은 공간을 많이 차지하므로
문자열을 숫자로 바꿔서 사용합니다.

예를 들어
{23,455,2003} {23,543,234,65} $\cdots$ 와 같이 표현하는데,
여기서 정수는 아이템을 나타내고, 괄호 {} 는 하나의 바스켓을 나타냅니다.
위의 경우,
2개의 바스켓을 갖고있고, 23에 해당하는 아이템을 공통적으로 갖고있는 것입니다.

일반적으로 아이템은 양의 정수(positive integer) 로 표현하고,
바스켓 사이과 바스켓 사이에 ‘-1’ 정수값을 넣어, 바스켓 간 경계를 표현합니다.
위의 예시를 실제 파일 구조로 나타내면 다음과 같습니다.

그림@@

Computation Model

계산이 어떻게 수행되는지 살펴봅시다.

디스크에 있는 바스켓 파일을 메인 메모리에 가져옵니다.
일반적으로 바스켓 파일은 메모리에 다 못올리므로, 디스크에서 읽어오면서 수행합니다.
CPU 는 바스켓에 있는 아이템들을 카운트 합니다.
이 카운트 자체는 단순한 연산이기 때문에 메모리에서의 작업 수행시간이 길진 않습니다.
카운트를 할 때 아이템 쌍(집합)을 생성해야합니다.

초반 작업의 경우에는
아이템을 하나씩 읽고, 카운트를 합니다. 메모리에 아이템-카운트 정보가 생성됩니다.(1)
그 다음, 파일을 다시 읽고 2개의 아이템 쌍을 카운트 합니다. 메모리에서 아이템 쌍- 카운트 정보가 생성됩니다.(2)

아이템이 총 n 개가 있다면,
(1) 로 인해 메모리가 n 개의 공간이 필요합니다.
(2) 과 같은 경우, n개의 아이템 중 2개를 골라 쌍을 만드므로, $n \choose 2 $ , 약 $n^2/2$ 규모의 공간이 필요합니다. (실제로는 (1)에서 만든 후보만 사용)

이와같이 n 개의 아이템에서 k 개로 구성된 집합을 만들기 위해서는
$n^k/k!$ 의 공간이 필요합니다.

수치상으로는 엄청나게 많은 공간을 필요로 하지만,
실제로는, 임계값 조정, k =2,3 으로 설정하는 등으로
패스( (1) 에서 (2)로 넘어가는 ) 마다 필요없는 아이템을 제거하고 수행되어
패스마다 생성되는 공간은 줄어듭니다.

이렇듯 Frequent Itemsets 을 찾는 문제 에서는
연산시간보다는 메인 메모리의 공간에 초점이 맞춰집니다.
CPU 의 작업시간은 오래안걸리므로,
디스크 IO 시간이 전체 실행시간에 중요한(critical) 부분을 차지합니다.

때문에 Frequent Itemsets 관련 알고리즘은
패스의 수(디스크를 읽는 횟수)를 줄이는 방향으로 제시되었습니다.

알고리즘을 다루기 앞서,
아이템 쌍을 효율적으로 표현하는 두가지 방법,
Triangluar-Matrix Method, Tripes Method 을 살피겠습니다.

아이템 쌍을 카운트하기 위해서
각 아이템, $i$, $j$ 에 대한 정보가 필요하고 그 값(카운트)을 저장해야합니다.

The Triangular-Matrix Method

삼각행렬(=Triangular-Matrix) 방식은
i와 j를 행과 열의 인덱스로 두는 행렬을 만들어 표현하는 방식입니다.
순서는 상관이 없으므로, 행렬 중 i<j 인 부분만 사용합니다.
행렬 중에 삼각형으로 보이는 절반만 사용하는 것입니다.

실제 행렬과 동일하게 구현하게되면,
절반의 공간이 버려집니다.
때문에 2차원 배열(행렬)을 1차원으로 축소시킵니다.

하나의 배열에 다음과 같이 순차적으로 저장합니다.

{1,2}, {1,3},…, {1,n},{2,3}, {2,4},…,{2,n}, {3,4},…, {3,n},…{n 􏰜1,n}.

예를들어 {1,2} 의 위치에 해당하는 값은, 아이템 쌍 {1,2} 을 카운트한 값입니다.

삼각행렬이기 때문에 일차원 배열로 표현이 가능합니다.
$i,j$ 에 대해 1차원 인덱스를 구하는 식은 다음과 같습니다.

$(i-1)(n-i/2)+j-1$

위의 식에 $i,j$ 를 대입하면, 1차원 배열의 인덱스를 얻을 수 있습니다.

이 방식은 n 개의 아이템이 주어졌을 때,
n(n –1)/2 공간이 필요하고, 정수형은 4byte 이므로,
약 $2n^2$ byte 를 사용합니다.

The Triples Method

Triples Method는
$[i,j,c]$ 으로 표현합니다.
여기서 $i, j$ 는 아이템 쌍이고, $c$ 는 카운트 값입니다.

세개의 정수를 저장하므로,
쌍 하나 당 12byte 를 사용합니다.

이 방법은 하나의 쌍을 저장하는데 공간을 더 많이 차지하지만,
없는 아이템 쌍에 대해서는 공간을 차지하지 않습니다.(있는 쌍만 저장)
삼각행렬의 경우, 아이템 쌍이 없어도 공간을 유지해야합니다.

그래서 위 두 방식을 결정하는 기준은
실제 쌍의 수 입니다.
만약 전체 조합의 1/3 이상이 있으면 Triangular-Matrix 가 효율적이고
1/3 이하인 경우 Triples Method 가 효율적입니다.

이번 포스팅에서는
Frequent Itemsets 을 찾는 작업에서 어떠한 이슈가 있는지와
데이터를 표현하는 방식에 대해 다뤘습니다.

다음 포스팅에는
연관 규칙을 찾는 A-Priori 알고리즘에 대해 다뤄보겠습니다.