5.2 Apriori

Challenges of Apriori

• Apriori는 DB를 scan하는 횟수와 candidate의 숫자가 너무 크다는 단점을 가짐
• transaction이 100개인 경우에, 최대 scan 수는 100번, 최대 candidate 수는 임(원소 100개가 하나의 frequent pattern인 경우)

Improving Apriori

• 이러한 문제를 해결하기 위해서 아래와 같은 향상된 알고리즘을 제시함
• Reduce the # of DB scans
• DIC
• Partition
• Sampling
• Reduce the # of candidates
• Sampling
• DHP

DIC: Dynamic Items Counting

• scan을 하면서 frequent pattern을 모으는데, 이들의 조합으로부터 superset pattern이 만들어지면, 그 순간부터 superset의 개수를 이어서 세는 방법임
• scan 도중에 {A}와 {D}가 minimum support를 넘어서 frequent pattern으로 결정되면, 그 순간부터 {A, D}를 counting함
• scan 도중에 {B, C}, {C, D}, {B, D}가 minimum support를 넘어서 frequent pattern으로 결정되면, 그 순간부터 {B, C, D}를 counting함

• DB scan 수를 줄일 수 있으므로 apriori에 비해 효율적임

Partition: Scan Database Only Twice

• DB를 메모리를 고려해 적절한 크기(k)로 자름
• 모든 partition은 하나의 메모리 안에 있어야 함

• 각 partition에서의 local frequent pattern을 찾음
• local frequent pattern을 찾기 위한 기준은 localMinSup = MinSup / k임

• local frequent pattern을 가지고 전체 DB에서 global frequent pattern을 찾음

• global frequent pattern은 적어도 하나의 partition에서는 local frequent pattern으로 나옴

Sampling

• DB 일부만 샘플링한 sampling DB(SDB)에서 Apriori를 통해 frequent pattern을 찾음
• 여기서 frequent pattern을 찾기 위한 기준은 sampleMinSup = size of SDB / size of DB임

• DIC와 달리, sampling은 정확한 frequent pattern이 아닐 수 있음(과대/과소평가 모두 가능)

• 이를 해결하기 위해서 two more scanning for verification으로 해결함
• SDB에서 찾은 frequent pattern을 S라고 가정할 때, S에는 없지만 S의 조합으로부터 만들 수 있는 모든 경우의 수(+ single items)를 NB(Negative Borders)라고 함
• NB의 모든 subset은 S에 있어야하지만, NB는 S에 없어야 함
• S와 NB를 합친 collection을 전체 DB에서 additional scan함
• minimum support를 통과한 collection 중에서 다시 한번 조합할 수 있는 itemset을 만들어 한 번 더 additional scan함
 
• S = {a}, {b}, {c}, {f}, {a, b}, {a, c}, ... / NB = {b, c}, {b, f}, {d}, {e}, ...
• 위와 같은 예시에서는 S에 {a}, {b}, {c}가 있으므로 NB에 {b, c}를 추가해 additional scan함
• 만약에 {a, b}, {a, c}, {b, c}가 frequent pattern로 확정나면, {a, b, c}를 한번 더 additional scan함

DHP: Direct Hashing and Pruning

• Apriori에서 candidates를 pruning할 때, hash table을 참고해서 candidates 제외시키는 방법임

• 우선 k개의 원소를 가진 frequent pattern(L)을 만들 때, k+1개의 원소를 가진 조합의 hash table도 만듦

• 아래의 사진에서 파란색 하이라이트가 쳐져 있는 식이 hashing의 하나의 예시임

• k개의 원소를 가진 frequent pattern(L)에서 k+1개의 원소를 가진 candidates(C)를 만들때, hash bucket count가 min_sup을 넘기지 못하면 candidates 제외시킴