[CS246] Frequent Itemsets: SON, Toivonen Algorithm

 

 

Recap: Frequent Itemsets & Intro.

A-Priori, PCY, Multistage, Multihash 알고리즘을 이용하면 결국 크기가 $k$인 frequent itemset을 얻기 위해서 $k$번 반복해야한다. 물론 일부는 frequent pair에 특화되어있지만 결국 $k$번 반복하는 것은 동일하다.

 

이번 포스팅에서는 pass 수가 2번 이하인 알고리즘을 알아보자. 크게 3가지 방법이 알려져있다.

• Random sampling (random sampling은 대규모 데이터셋에서 효과적이다. 무시하지 말기)
• Toivonen
• SON (Savasere, Omiecinski, Navathe)

 

Random Sampling

market basket에 대하여 랜덤 샘플링(무작위 표본 추출법)을 적용하는 방법이다.

main-memory에서 a-priori(또는 PYC, multistage, multihash와 같은 알고리즘)를 적용하기 때문에 disk I/O 시간은 없다. 대신 샘플링할 때 support threshold를 조절한다.

예를 들어 $1/100$의 basket을 샘플링 할 때, support threshold를 $s/100$으로 줄여서 a-priori를 적용한다.

일반적으로 basket의 $p\%$만큼 샘플링 할 때, support threshold는 $ps/100$이 된다.

물론 support threshold를 더 낮춰서 샘플링하기 때문에 candidate pair에는 false positive가 있다. 그러나 작은 threshold는 더 많은 메모리를 차지한다.

SON (Savasere, Omiecinski, Navathe) Algorithm

(input) 전체 파일을 입력으로 받고, 여러개의 chunk(subset, piece)로 나눈다. $p(<1)$의 비율로 나누면 $1/p$개의 chunk를 얻는다.

(pass 1) 각 chunk를 sample로 간주하고 support threshold는 $ps$인 A-Priori 등의 알고리즘을 적용하여 candidate itemset을 구한다.

(pass 2) 전체 candidate itemset을 합하고 원래 support $s$로 필터링하여 frequent itemset을 구한다.

 

Idea of SON algorithm: monotonicity

itemset이 어떠한 부분집합에서도 frequent하지 않다면, 전체집합에서도 frequent할 수 없다.

(an itemset cannot be frequent in the entire set of baskets unless it is frequent in at least one subset.)

 

SON with MapReduce

SON 알고리즘의 입력이 전체 파일의 chunk인 것에 착안하여 MapReduce와 같은 분산시스템에 적용가능하다. 각 pass마다 map/reduce를 적용할 수 있다.

• Pass 1: Candidate itemset 구하기
  • Map: 각 chunk마다 A-priori(support=$ps$)를 통해 구한 frequent itemset $F$를 구하고 $(F, 1)$를 반환한다. (value $1$은 상관없다. 어차피 사용되지 않는다.)
  • Reduce: value(여기서는 $1$)는 무시하고 최소 한번 이상 등장한 itemset을 합쳐서 candidate itemset을 만든다.
• Pass 2: True frequent itemset 구하기
  • Map: 각 candidate itemset이 몇번 등장했는지 개수를 센다. (key, value)=($C$, $v$). ($C$는 candidate set의 원소, $v$는 support)
  • Reduce: itemset을 받아 모든 value를 더한다. 각 itemset의 value의 합계가 $s$ 이상인 경우에만 itemset을 반환한다.

반응형

Toivonen's Algorithm

Negative border & Immediate subsets

Toivonen 알고리즘을 소개하기 전에 2개의 개념을 짚고 넘어가야한다. 두 개념의 정의는 다음과 같다.

• Immediate subsets
  • 어떤 부분집합에서 단 하나의 원소만 제거한 부분집합
•  Negative border
  • itemset 자체는 sample에서는 infrequent한 집합이지만,
  • 해당 itemset의 모든 immediate subset은 (sample에서) frequent해야 한다.

예시로 $\{ A,B,C,D \}$가 negative border라 하자. 그러면 조건1에 따라 $\{ A,B,C,D \}$는 sample에서 infrequant하고, immediate subuset인 $\{ A,B,C \},\ \{ B,C,D \},\ \{ A,C,D \},\ \{ A,B,D \}$는 sample에서 frequent해야 한다.

그리고 $\{ A,B,C,D \}$보다 더 큰 집합인 $\{ A,B,C,D,E \}$는 negative border가 되지 않는다. 

Negative Border (Stanford CS246)

MMDS 교재의 예시를 통해 immediate subset과 negative border를 이해해보자.

$\{ A,B,C,D,E \}$ 중에서 $\{ A \},\ \{B\},\ \{C\}, \{D\},\ \{B,C\},\ \{C, D\}$ 는 frequent하다고 파악했다고 하자. ($\emptyset$ 역시 frequent하다.)

• $\{ E \}$는 negative border이다. 왜냐면 $\{ E \}$의 immediate subset은 $E$를 제거한 $\emptyset$뿐이고 $\emptyset$은 sample에서 frequent하기 때문이다.
• $\{  A, B\}$는 negative border이다. $\{ A,B \}$의 immediate subset은 $\{A\},\ \{ B \}$ 2개이고 2개 모두 sample에서 frequent하기 때문이다.
• 마찬가지로 $\{A,C\},\ \{A,D\},\ \{ B,D \}$ 모두 negative border이다.
• $\{ B,C \}$와 $\{ C,D \}$는 이미 sample에서 frequent하기 때문에 negative border가 아니다.
• $\{ A,E \},\ \{ A,E \},\ \{ A,E \},\ \{ B,E \}$는 immediate subset에 $\{ E \}$가 있으므로(sample에서 infrequent) negative border가 아니다.
• 또한, (주어진 예시에서) 크기가 3 이상인 집합은 negative border가 될 수 없다. $\{ B,C,D \}$의 immediate subset 중 하나인 $\{ B,D \}$가 infrequent하기 때문이다.
• 즉, 전체 negative border는 $ \{ E \},\ \{ A,B \},\ \{ A,C \},\ \{ A,D \},\ \{ B,D \}$ 뿐이다.

Algorithm process

support=$s$, sampling 할 비율을 $p(<1)$이라 하자. 즉 $1/p$ 개의 random sample이 주어진다.

 

Pass 1

각 random sample마다 약간 작은 threshold(e.g. $0.8ps,\ 0.9ps$)를 통해 (candidate) frequent itemset을 구한다. (truly frequent itemset을 놓치지 않도록 하는 것이 목적이다.)

(sample에서 frequent한) frequent itemset에서 negative border를 더해 candidate frequent itemsets을 만든다.

 

Pass 2

pass 1에서 구한 candidate itemset과 negative border의 모든 itemset의 개수를 구한다.

• 모든 negative border의 원소가 infrequent할 경우, frequent itemset이 전체 frequent itemset이다.
• negative border 원소 중 일부는 frequent 할 경우, 새로운 random sample로 전체 알고리즘을 다시 돌린다!
  • 혹은 support threshold를 더 작게하여 실패확률을 낮춘다. 이방법은 memory 사용량이 많아지는 trade-off에 주의한다.

 

Why Toivonen's Algorithm Works

이제 Toivonen 알고리즘이 왜 동작하는지 알아보자.

우선 이 알고리즘은 false positive는 존재하지 않는다.

왜냐면 전체 데이터셋에서 frequent itemset을 확인하기 때문이다. (by pass 2)

 

또한 이 알고리즘은 false negative도 존재하지 않는다.

 

false negative가 없다면 다음을 만족하는 itemset이 존재하지 않는다.

1. 전체 데이터셋에서는 frequent하지만,
2. negative border나 sample의 frequent itemset에서 infrequent 해야(없어야) 한다.

 

귀류법으로 모순을 보여 증명할 수 있다.

false negative 정의에 따라 어떤 itemset $S$가 전체 데이터에서 frequent하지만 negative border에는 속하지 않으면서 sample에선 infrequent하다고 하자.

그런데 monotonicity에 따라 $S$의 부분집합 역시 전체 데이터셋에서 frequent하다. 

$T$를 정의하길, $S$의 부분집합중 sample에서 infrequent한 최소부분집합이라 하자. (당연히 $T$는 전체 데이터에서 frequent하다)

그렇다면 $T$는 반드시 negative border여야 하고, 실제로 negative border 조건을 만족한다.

1. $T$는 sample에서 infrequent하다. ($T$를 그렇게 정의했다.)
2. $T$의 immediate subset은 sample에서 frequent하다. (아래에서 확인)

만일 $T$가 2번 조건을 만족하지 않아서 negative border가 아니라 하자. 그러면 $T$의 immediate subset 중 sample에서 infrequent한 부분집합이 존재한다는 것이고, 곧 그 부분집합은 $S$의 원소가 된다. 그러나 우리는 $T$가 $S$의 부분집합 중 sample에서 infrequent한 최소부분집합이라고 했기 때문에 모순이다. 그러므로 $T$는 nagative border이다.

그렇다면 $T$는 negative border에 존재하면서 동시에 전체 데이터에서 frequent하다. 결과적으로 Toivonen  알고리즘은 이러한 $T$를 answer로 하지 않는다. 이러한 $T$가 없으므로 superset인 $S$(false negative) 역시 존재하지 않는다.