[데이터 사이언스] 3. Association

Backgrounds

• Support count: 아이템셋이 몇번 빈번하게 나타났는가?
• Support: 전체 아이템 종류로 support를 나눈 값
• Frequent itemset: support가 정해진 threshold를 넘긴 itemset
• Confidence: $X \rightarrow Y$ 관계에서 $\sigma(X, Y) / \sigma(X)$를 계산한 값.
• Association rule: $X \rightarrow Y$ 관계

Association Rules

• Frequent Itemset Generation: minsup보다 큰 아이템셋을 모두 정의
• Rule generation: frequent itemset에서 confidence가 높은 rule을 정의.

  대체로 frequent itemset generation이 시간복잡도가 더 높다.

Frequent itemset generation

Brute-force approach

• 그냥 모든 데이터 종류 $d$에 대해서 존재/미존재로 모든 조합 만들어내서 candidate로 사용.
  $M=2^d$
  $O(NMw)$
  $R=3^d-2^{d+1}+1$
• 역시 꽤 비싸다. 주로 candidates의 수($M$)을 줄이거나 comparison의 수($NM$)을 줄여서 개선할 수 있다.

Candidate 줄이기 : Apriori

• 기반이 되는 성질: 만약 아이템셋이 frequent하다면, 그 아이템셋으로 만든 subset도 당연히 frequent할 것이다.
  $(X \subseteq Y) \rightarrow s(X) \ge s(Y)$
• 이 성질은 support의 anti-monotone 성질이라고 알려져 있다.
• 이를 활용하면 infrequent한 superset 하나만 고려하고 나머지는 가지치기가 가능해진다.

Comparisons 줄이기 : Hash structure

• Hash function을 정의해서 frequent itemset에 대한 트리를 미리 만들어놓고, 새로운 transaction 데이터가 올 때마다 빈번한 요소를 갖고 있는지 체크 가능.
• support의 anti-monotone 성질 덕분의 길이 5의 transaction의 빈번도는 길이 3의 빈번한 요소가 내부에 포함되어 있는지 확인하는 것만으로도 체크가 가능해진다.

Complexity에 영향을 미치는 요소

• Choice of minimum support threshold
• Dimensionality of the data set
• Size of database
• Average transaction width

DB scan 줄이기 : FP-Growth

• 목적: Candidate generation 없이 그냥 frequent한 데이터셋을 알아내자.
• 기반이 되는 성질: Frequent itemset $P$이 있다고 할 때, $S$는 아이템셋 $P$를 포함하고 있는 transactions이라 하자. 이 때, $S$에 있는 아이템 $x$가 빈번하다면, $\{x\} \cup P$도 무조건 빈번하다.
• 이걸 사용하면 candidate generation이 필요 없다. 대신 빈번한 아이템셋에 대한 마이닝을 위해서 FP-tree라는 자료구조를 만들 것이다.
• FP-tree를 만드는 과정. 이 과정은 DB를 단 두번만 스캔한다.

  1) 사용자가 정의한 minsup에 의거해 frequent 1-itemset을 먼저 만든다.
  2) frequent 1-itemset을 내림차순 정렬한다.
  3) DB를 스캔해서 FP-tree를 만든다.

• FP-tree를 mine 하는 방법

  1) 어떤 데이터 $x$에 대해서 conditional pattern bases를 만든다.
  2) conditional FP-trees를 만든다.
  3) 재귀적으로 계속 FP-trees를 마이닝한다.

• Conditional pattern base: 그 데이터에 도달하기까지 과정
• Conditional pattern tree: Conditional pattern base에서 공통부분

Frequent itemset $\alpha$가 있다고 할 때, $B$는 아이템셋 $\alpha$를 포함하고 있는 conditional pattern base라고 하자. 이 때, $B$에 있는 아이템 $\beta$가 빈번하다면, $\alpha \cup \beta$도 무조건 빈번하다.

• 왜 중요한가? 어떤 아이템 $\alpha$가 빈번하다는 사실을 안다고 가정하자. 이 때 사용자가 $\beta$를 정해서 쿼리한다면, $\alpha$를 기반으로 conditional pattern base를 결정한 뒤 거기서 $\beta$가 몇 번이나 support count가 나오는지만 보아도 전체 빈번도를 알 수 있다.
• 즉, 1-itemset만 사용해서 트리를 만들기만 했는데 데이터의 빈번도를 알게 되었음을 의미한다.
• Single path tree는 그 트리를 구성하는 요소들의 조합만으로도 빈번도가 계산이 가능하다.
• Apriori와 비교하면 minsup이 적더라도 압도적으로 FP-growth가 효율적인 모습을 볼 수 있다.

Maximal, closed frequent itemsets

• Maximal: Support가 minsup 이상이며, 더 이상 확장할 수 없는 frequent 아이템셋
• Closed: Support가 minsup 이상이며, 어떠한 상위 아이템셋도 동일한 support를 가지지 않는 frequent 아이템셋
• Closed는 패턴을 요약하는데 도움이 되며, maximal은 흥미로운 패턴을 찾는데 도움이 된다.

Rule generation

• 일반적으로 confidence는 anti-monotone 성질이 없다.

  즉, c(ABC $\rightarrow$ D)는 c(AB $\rightarrow$ D)보다 크거나 작을 수도 있다.

• 하지만 같은 데이터셋 내부에서는 ani-monotone 성질을 갖고 있다.
  $c(ABC\rightarrow D) \ge c(AB \rightarrow CD) \ge c(A \rightarrow BCD)$
• 다시 말해, 만약 $A \rightarrow B$가 minsup보다 낮다면, $A \rightarrow B, C$도 무조건 minsup보다 낮다. 따라서 $A, B, C \rightarrow D$가 minsup보다 낮다는 것이 확인된다면, $(A, B \rightarrow C, D)$, $(A \rightarrow B, C, D)$도 minsup보다 무조건 낮을 것이다.

Interestingness Measures

• lift = confidence / probability of consequent
• 보통 lift가 1을 넘기면 두 Antecedent/Consequent가 서로 연관되어 있다고 본다.
• 다시 말해 confidence가 데이터의 신뢰도를 나타내지는 않는다는 것이다.
• Null-transaction invariacne이 매우 높다면, lift도 크게 나온다. 하지만 이것이 두 사건이 서로 같이 일어날 확률이 높게 보이는 착각을 불러 일으킨다.
• 이처럼 null-transaction이 높을 때, 이를 보완할 수 있는 지표로써 null-invariant measure가 사용될 수 있다.

Null-invariance

• Null-invariance는 correlation analysis를 하는데 중요한 역할을 수행한다.

• Null-invariant는 두 개의 사건이 독립적일 떄 기댓값과 비교하여 상호작용 빈도를 측정하는 척도이다. 즉, 두 사건이 서로 독립적인지 확인하는 역할을 수행한다.

  만약 Null-invariant measure가 1에 가깝다면, 두 사건은 독립적이라는 뜻이 된다.

• Positively Correlated: 두 제품을 따로 사는 사람에 비해 두 제품을 동시에 사는 사람이 더 크다.
  Negatively Correlated: 두 제품을 따로 사는 사람에 비해 두 제품을 동시에 사는 사람이 더 적다.

• 위와 같은 특별한 경향성이 나오지 않는다면 Kulczynski는 0.5로, 중립적으로 나온다.

• 반면 '제품 하나만 사는 경우' 가 서로 불균등할 경우, IR이 크게 증가한다.

• Lift나 $\chi^2$는 null-invariant가 아니다.

• Null-invariant 측정은 5가지가 있다.
  1) AllConf(a,b)
  2) Coherence(a,b)
  3) Cosine(a,b)
  4) Kulc(a,b)
  5) MaxConf(a,b)

• IR(Imbalance Ratio)는 두 데이터가 서로 얼마나 얼마나 불균등한지 나타낸다.

• Kulczynski(=Kulc)와 IR은 각 데이터셋의 분포 상태를 나타내는데 사용된다.