Data Science

[Data Science] Frequent Pattern Mining - Imporving Apriori

sheep_bell_door_ 2024. 3. 31. 17:34

Apriori

[Data Science] Frequent Pattern Mining - Apriori

Apriori Challenges

  • Apriori 알고리즘은 다음과 같은 문제점이 있다. 이 중 1, 2번 문제를 보완하기 위한 방법에 대해 소개하고자 한다.
  1. Transaction database scan이 여러 번 발생한다.
    → Scan 횟수를 줄여 효율을 높인다.
  2. Itemset join 시, 후보 (k+1)-itemset이 많이 나온다. 
    → 후보 itemset 수를 줄여 효율을 높인다.
  3. 후보 itemset의 support를 계산하는 양이 많다.
    → 계산하는 알고리즘을 효율 좋은 알고리즘으로 바꿔 효율을 높인다.

DIC: Dynamic Itemset Counting

  • Reduce DB scanning time
  • 어느 itemset이 frequent인 것이 결정되는 시점에서 미래의 후보 itemset에 대해서 frequent인지 확인한다. 이 방법을 사용하면 스캔의 횟수를 줄일 수 있다.
  • Item이 A, B, C, D가 있다고 가정했을 때, 아래의 예시를 보자.
  • 기존 apriori 알고리즘은 아래 그림과 같이 DB를 여러 번 반복해서 스캔하였다.

Apriori

  • DIC는 아래와 같이 A, D가 frequent라고 판단되면 해당 시점에서 AD를 frequent인지 확인한다. 마찬가지로 AB, BD가 frequent라고 판단되면 해당 시점에서 ABD가 frequent인지 확인한다.
  • 즉, 스캔을 중간부터 시작한다.

Dynamic Itemset Counting

Partition: Scan Database Only Twice

  • Reduce DB scanning time
  • Partition은 DB를 k개의 파티션으로 나누어 각각의 파티션마다 local frequent pattern을 구하는 방식의 방식이다.
  • 각각의 파티션의 크기는 (효율성을 위해) 메인 메모리의 크기에 맞춰져 있다.
    • 전체 DB에 접근 X: 메인 메모리 크기 만큼의 파티션을 메모리에 올림 → local frequent pattern 확인 → 다음 파티션 fetch → 마지막 파티션까지 반복 
  • Scan 1
    • 각 파티션에 대해 local frequent pattern을 찾는다.
    • Local minimum support는 (minimumSupport / k)이다.
    • Global frequent pattern은 무조건 하나 이상의 local database에서 local frequent pattern이라는 사실에 기반한다.  
  • Scan 2
    • Local frequent pattern에 대해 전체 DB에서 실제 frequent pattern인지 확인한다.
    • 예를 들어, # of partition = 4, minimum support = 40, local minimum support = 10 일 때, itemset {A, B, C}에 대해서 P1: 11, P2: 3, P3: 4, P4: 10이라면 local frequent pattern이지만 전체 support는 27이기 때문에 실제로 {A, B, C}는 frequent pattern이 될 수 없다.

Sampling  

  • Reduce DB scanning time, # of candidates
  • DB에서 무작위로 Sampled DB(SBD)를 추출하여 frequent pattern을 확인하는 방법이다.
  • Partition과 비슷하지만 정확도가 떨어진다. 대신 빠름.

Solutions

  • 검증을 위해 두 번의 스캔을 진행한다.
  1. Original minimum support에 대해 전체 DB를 스캔한다.
    • SDB의 frequent itemset과 negative border에 대해 frequent 여부를 확인한다.
    • Negative border: Sample DB에서는 frequent하지 않지만 전체 DB에 대해서 frequent 할 수 있는 itemset을 말한다. Itemset의 subset이 SDB에서 frequent한 itemset + single item으로 구성된 itemset이다.
      예를 들어, SDB의 frequent itemset S = {a}, {b}, {d}, {a, b}, {a, d}일 때, negative border NB = {b, d}: subset이 전부 SDB에서 frequent, {c}: single item이다.
  2. 전체 DB를 다시 한 번 스캔한다.
    • Negative border 내의 itemset에 대해 missed frequent pattern이 있는지 확인한다.
    • 예를 들어, S = {a}, {b}, {d}, {a, b}, {a, d}, NB = {b, d}, {c} 일 때, 스캔을 통해 {b, d}가 frequent 하다고 확인된다면 {a, b, d}는 frequent 하다고 할 수 있다.

DHP: Direct Hashing and Pruning

  • Reduce # of candidates
  • Frequent k-itemset을 만들 때, DB 각각의 transaction으로부터 k+1 itemset에 대해 count를 저장하는 해시테이블을 만들어 candidate itemset을 줄이는 방식이다.