Frequent Itemset Generation의 원리

itemset A가 frequent itemset이라면, A의 모든 부분집합은 frequent itemset이다.

$$ \tt \forall X,Y:(X\sube Y) \Longrightarrow s(X) \ge s(Y), \qquad\text{ X and Y are itemsets.} $$

itemset A의 support는 A의 부분집합의 support보다 절대 클 수 없다.

support의 anti-monotone 속성

Apriori Algorithm은 위의 성질을 이용하여, 만약 {AB}가 infrequent itemset이라면, {AB}의 자식 노드를 모조리 가지치기를 해버린다.