Park-Chen-Yu Algorithm
해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.
PCY Algorithm
PCY 알고리즘은 A-Priori 알고리즘에서, 첫번째 패스의 사용되지 않는 메모리 공간을 활용하는 알고리즘입니다.
백만개의 아이템이 있고 메모리 용량이 GB 단위라면,
첫번째 패스에서 메모리 공간은 전체의 약 10% 만 사용됩니다.
첫번째 패스에서 메모리는 item 이름을 정수로 변환하기 위한 테이블(translation table)과, 그 정수(아이템) 의 카운트를 저장한 테이블, 이 두개의 공간만 필요합니다.
PCY 알고리즘에서는 블룸 필터(=Bloom Filter, 원소가 집합에 속하는지 검사하는데 사용) 개념을 도입하여, 정수들의 배열을 위한 공간을 사용합니다.
이 개념은 다음과 같이 도식화할 수 있습니다.
이 배열을 해시 테이블로 생각해봅시다. 여기서 버킷은 키들의 집합이나 비트 대신 정수들을 갖습니다.
아이템들의 pair는 해시 테이블의 버킷으로 해시됩니다.
첫번째 패스에서 바스켓을 검사하면서, 각 바스켓에 있는 아이템의 카운터에 1을 더하고(A-Priori), 모든 pair를 생성합니다.
생성된 각 pair를 해시하고 pair가 해시된 버킷에 1을 더합니다. 여기서 pair 자체가 버킷에 들어가는 것이 아닙니다. pair는 버킷의 단일 정수에게만 영향을 끼칩니다.
FOR (each basket) {
FOR (each item in the basket)
add 1 to item’s count;
FOR (each pair of items) {
hash the pair to a bucket;
add 1 to the count for that bucket
}
}
첫번째 패스가 끝나면, 각 버킷은 카운트를 갖습니다.
이 카운트 그 버킷으로 해시된 모든 pair들의 카운트의 합입니다.
한 버킷의 카운트가 s 보다 크다면, 이것을 ‘frequent bucket’ 이라고 합니다.
frequent bucket 으로 해시되는 pair 를 그대로 빈번하다고 볼 수는 없습니다.(Bloom filter 의 False Negative)
그러나 버킷이 s 이하로 카운트 된다는 것은, 그 버킷에 빈번해질 수 있는 pair가 없다고 봅니다.
여기서 그 pair의 아이템들이 모두 빈번하더라도 pair 에 대해 수행하므로, pair 자체의 빈도에 대한 정보를 얻을 수 있는 것입니다.
이 정보는 두번째 패스 때 활용됩니다. 후보 pair C2 에 대한 정의를 다음과 같이 바꿀 수 있습니다.
- i 와 j 는 freqent item 이다.
- {i,j} 가 frequent bucket 에 해시된다.
PCY에서 패스를 거치면서, 해시테이블은 각 버켓에 대해 하나의 비트, bitmap으로 요약됩니다. (버킷이 빈번 하면 bit가 1 이고, 아니면 0 )
버킷의 32bit의 정수는 bitmap의 단일 bit 로 대체됩니다.
그리고 비트맵은 위의 6.5 그림과 같이 기존의 1/32 의 공간만 차지합니다.
대부분의 버킷이 infrequent 하다면, 후보 pair 집합 C2가 줄어들게 되므로, 두번째 패스에서 계산되는 전체 pair 가 많이 줄어들게 됩니다.
그래서 PCY 는 두번째 패스에서 데이터 셋을 효율적으로 다룰 수 있습니다.
Data Structure for counts of pairs in the PCY
PCY에서 pair 의 카운터를 저장하는 경우 삼각행렬을 사용하지 않습니다.
A-Priori 에서는 두번째 패스에서 삼각행렬을 사용하는 것이 가능했지만(1-m 으로 리넘버링 하면서), PCY 에서는 쓸 수 없습니다.
빈도 아이템들로 만들어낸 pair 들은 삼각행렬안에 있는 임의로 위치합니다.
이 중에는 첫번째 패스에서 frequent bucket으로 해시되지 않은 pair 가 있을 수 있습니다.
1~m 으로 리넘버링된 행렬에는 후보가 아닌 pair가 포함되어 있으므로 해시로 버킷을 만드는 작업의 의미가 없어집니다.
PCY 에서는 triple 방식을 사용합니다.
이 제약은 빈번한 아이템이 많이 나오지 않는 상황에는 괜찮지만, 많은 pair들이 빈번하게 나오는 경우는 비효율적입니다.
그래서 PCY 에서, C2 에 빈도 아이템의 pair의 2/3 이상 줄여주지 않는다면 A-Priori 대신 PCY 를 쓰는 이점이 없어집니다.
:Triple을 사용할 때, 실제 pair 가 전체의 1/3 이하인 경우에 삼각행렬 보다 효율적입니다.
PCY로 frequent pair을 찾는 작업은 A- Priori와 크게 다르지만, frequent triple 이나 더 큰 세트를 찾는 단계는 본질적으로 A-Priori와 동일합니다.
이와 관련된 내용은 다른 다시 섹션에서 다룹니다.
Comments