SON Algorithm
해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.
The Simple, Randomized Algorithm
전체 파일을 사용하는 대신, 바스켓의 무작위 부분직합을 선택합니다.
여기서는 샘플에서는 빈도 수가 줄어드므로, 기존 support 임계값 s 를 조절해야합니다.
예를 들자면, 임계값을 s 로 사용하면 1% 만 선택할 때 s/100 을 사용하여 검사합니다.
일반적으로 각 버스켓에 대해 확률 p 를 가지고 바스켓을 샘플로 선택합니다.
전체 파일에 m 개의 바스켓이 있다면,
m개의 바스켓을 읽으면서 각각 p 확률로 선택합니다.
이 작업으로 약 pm개의 바스켓 샘플을 얻게 됩니다.
파일에 바스켓 순서가 무작위로 되어있는 경우,
전체 파일을 읽을 필요없이, 앞에서부터 pm 개의 바스켓만 선택하면 됩니다.
파일이 분산 파일 시스템에 저장되어 있는 경우에는 무작위로 pm개의 청크를 선택하여 수행합니다.
(+ 무작위로 수행하지 않으면, 편향된 데이터로 수행될 수 있습니다.)
전체 중 일부의 바스켓만 사용하므로,
이 메모리의 일부를 샘플 바스켓들을 저장하는데 사용해도 됩니다.
메모리의 남은 공간들은 A-Priori, PCY, Multistage 등의 알고리즘을 수행하는데 사용합니다.
알고리즘은 메모리에 있는 샘플을 거치면서 빈도 아이템 셋을 찾습니다.
샘플이 메모리에 올려져 있기 때문에 샘플을 읽기 위한 디스크 접근이 필요없습니다.
빈도 아이템셋을 다 찾으면, 디스크로 쓸(write) 수 있습니다.
디스크에서 샘플을 처음 읽는 것과, 수행 후 쓰는 것이 알고리즘에서 수행하는 유일한 디스크 IO입니다.
물론 위 알고리즘들이 샘플 저장 후 남은 메모리 공간으로 실행될 수 없는 경우, 알고리즘이 실패합니다.
메모리가 더 필요한 경우, 각 패스마다 디스크IO 로 샘플을 읽는 것입니다.
일반적으로 샘플을 메모리에 올려서 사용할 수 있도록 설정하여 디스크 IO를 피합니다.
Avoding Errors in Sampling Algorithms
Simple 알고리즘에서는,
전체 데이터 셋의 빈도 아이템셋 전부를 만들지 못하고,
전체 중에 빈도 아이템셋 중 일부만 만들어 냅니다.(샘플에서만 빈번한)
전체에서 빈번하지만 샘플에서 그렇지 않은 아이템 셋을, false negative 라고 합니다.
반면, 샘플에서는 빈번하지만, 전체에서는 빈접하지 않은 아이템 셋을 false positive 라고 합니다.
샘플이 충분히 큰 경우에는 이 현상이 문제가 되지 않습니다.
서포트가 임계값 s 보다 훨씬 더 큰 아이템셋은 무작위 샘플에서도 대부분 확인됩니다.
s 보다 훨씬 더 작은 아이템셋은 샘플에서 거의 나타나지 않습니다.
그러나 s 와 서포트가 비슷한 아이템셋은 샘플에서 자주 발생하지 않을 가능성이 있습니다.
전체 데이터셋을 읽어서,
샘플에서의 빈번하다고 나오는 아이템셋이 실제로 빈번한지 조사하여
false positive 를 줄일 수 있습니다.
이러한 작업은 샘플에서만 빈번한 아이템셋을 제거하므로
모든 false positive 를 처리할 수 있습니다.
그러나 이 방법으로는 false negative를 처리할 수 없습니다..
이 작업을 단일 패스 안에서 수행하기 위해서는
메모라에서 전체의 빈도 아이템셋을 한번에 카운트 해야합니다.
사용 가능한 메모리를 사용하여 Simple 알고리즘을 성공적으로 실행할 수 있다면
다음과 같은 이유로 빈도 아이템셋을 한 번에 계산할 수 있습니다.
- 빈도 아이템과 pair 모두 빈도 아이템셋의 모음에 대부분 나타나고, 첫번째 패스에서 그것들 모두 카운트했어야 했습니다.
- 샘플을 메인 메모리에 저장할 필요가 없으므로 이제 모든 메인 메모리를 사용할 수 있습니다.
false negative를 완전하게 없앨 순 없지만, 메모리 크기가 허용한다면 그 숫자를 줄일 수 있습니다.
서포트 임계값이 s, 샘플의 비중이 p 이면, ps 를 샘플에 대한 서프트 임계값으로 설정하였습니다.
여기서 샘플에 대한 임계값을 더 낮게 설정할 수 있습니다. (0.9ps 와 같이)
더 낮은 임계값을 설정하면 각 샘플에서 아이템셋이 더 많이 카운트 됩니다.
대신 필요한 메모리가 늘어나게 됩니다. 만약 메모리가 충분히 있다면,
0.9ps 로 두어 찾는 경우, 샘플에서 s 가 넘는 아이템셋을 더 많이 구할 수 있습니다.(후보)
샘플에서 빈번하지만 전체에서 빈번하지 않은 아이템 셋을 제거하기 위해 전체 파일을 거치는 패스를 만들면,
false positive 는 없고,(직접확인해서 아닌 경우 처리)
false negative 아주 적게 만들 수 있습니다.(샘플의 임계값을 낮춰 후보를 더 많이 뽑아서 줄인다.)
The Algorithm of Savasere, Omiecinski and Navathe
SON 알고리즘은 두 번의 full 패스를 사용하여 false negative, false positive 모두를 해결합니다.
이는 입력 파일을 청크(=chunk)로 나누는 방식으로 수행됩니다.
각 청크는 샘플로써 다뤄집니다. 그리고 청크 마다 위의 simple 알고리즘이 수행됩니다.
전체와 청크의 비중 p 로, ps 를 임계값으로 사용합니다.
ps로 찾은 청크의 모든 빈도 아이템셋을 디스크에 저장합니다.
이러한 방식으로 모든 청크에서 작업이 수행된다음,
여기서 나온 모든 빈도 아이템셋의 합집합을(union) 을 구합니다.
이 집합을 candidate itemset 이라고 합니다.
여기서 한 아이템셋이 어떠한 청크에서도 빈번하지 않으면, 그 아이템셋의 서포트는 모든 청크에서 ps 보다 낮습니다.
청크의 숫자는 1/p 이기 때문에, 그 아이템셋에 대한 서포트가 s 보다 적다고 결론지을 수 있습니다.(ps(1/p)=s 이므로)
그래서 전체에서 빈번한 모든 아이템 셋은 적어도 하나의 청크에서는 빈번합니다,
그래서 candidate itemset 중에 실제로 빈번한 아이템 셋을 모두 포함한다고 확신할 수 있습니다.(no false negative)
각 청크를 읽고 처리하면서 데이터를 총 한번 거쳤습니다.(첫번째 패스)
두번째 패스에서, 모든 후보 아이템셋을 세고, 그 중 s 이상인 것을 빈도 아이템 셋이라고 선택할 수 있습니다.
The SON Algorithm and MapReduce
SON 알고리즘은 병렬 컴퓨팅 환경에 적합합니다.
각 청크들은 병렬로 처리될 수 있고, 각 청크에서 빈도 아이템셋은 후보를 만들기 위해 결합됩니다.
다수의 프로세서들에게 이 candidate itemset을 분산할 수 있습니다.
각 프로세서는 바스켓의 부분집합에 있는 각 후보들에 대해 서포트 카운트를 갖습니다.
그리고 마지막으로 전체 데이터셋의 후보 아이템셋들 각각에 서포트를 얻기 위해 서포트들을 합칩니다.
이러한 과정은 꼭 맵리듀스에서 구현될 필요는 없지만, 맵리듀스의 연산으로 두 패스를 표현하는 것이 자연스럽습니다.
Frist Map Function
바스켓의 할당된 부분집합을 인자로 받아서, 부분집합안의 아이템셋 빈도를 찾습니다.(Simple 알고리즘 사용)
각 맵 태스크가 전체 입력 파일 중 p 크기를 얻는 경우 임계값을 ps로 설정합니다.
이 함수의 출력은 key-value (F,1) 의 집합입니다.
여기서 F 는 샘플의 빈도 아이템셋이고, 여기서 value은 항상 1로 둡니다.
First Reduce Function
각 리듀스작업은 key들의 집합 하나가 할당됩니다. (이 키는 아이템셋입니다.)
value 는 신경쓰지 않고 단순히 한번 이상 나타난 키들을 생성합니다.
그래서 첫번째 리듀스 함수의 출력은 candidate itemset 입니다.
Second Map Function
두번째 맵 함수는 첫번째 리듀스 함수의 출력과 입력 데이터 파일의 청크를 입력으로 받습니다.
각 맵테스크는 할당된 일부의 데이터셋의 바스켓에 있는 후보 아이템셋 각각의 빈도 수를 셉니다.
함수의 출력은 key-value 쌍 (C,v) 의 집합입니다.
여기서 C 는 candidate itemset 중 하나이고,
v는 입력으로 받은 바스켓에서의 해당 아이템셋의 support 입니다.
Second Reduce Function
리듀스 작업은 키로 제공된 아이템셋을 인자로 받아 value 를 합합니다.
합한 결과는 할당된 아이템셋의 각각의 전체 support 입니다.
이 value의 합이 s 이상인 아이템셋들은 전체 데이터 셋에서 빈번한 것입니다.
전체 서포트가 s 가 넘는 아이템을 출력하고 s 가 안되는 아이템셋들은 출력으로 내보내지 않습니다.
Comments