Ch4 Association Analysis

Definition

  • Itemset : 一個或多個 items 的集合
    • e.g. {Milk, Bread, Diaper}
  • Support Count ($\sigma$) : 一 Itemset 出現的頻率
  • Support : 有出現某 Itemset 的交易數比例
  • Frequent Itemset : 一 Itemset 的 Support $\ge$ minsup threshold
  • Association Rule (關聯規則) : $X \to Y$
  • Rule Evaluation Metrics (規則評估指標) :
    • Support ($s$) : 有出現 $X+Y$ 之 Itemset 的交易數比例
      • $s =\color{blue}{\frac{\sigma (X+Y)} {n}}$
    • Confidence ($c$) : 在有 $X$ 之 Itemset 中，有多少 $Y$ 的 Itemset 比例
      • $c=\color{blue}{\frac{\sigma(X+Y)}{\sigma(X)}}$
  • Association Rule Mining 目標 :
    • Support $\ge$ minsup threshold
    • Confidence $\ge$ minconf threshold
    • 因無法用暴力破解法解，故要使用下面兩種方式去處理

Frequent Itemset Generation

  • Def : 產生所有 support 皆 $\ge$ minsup 的 Itemsets
  • Brute-force approach (暴力破解法) :
    • $N$ 筆交易，每筆交易有 $w$ 個Items，共可以有 $M$ 組 Candidates
    • 計算複雜度 $\approx O(NMw)$
  • 降低 Candidate 數量 ($M$) : 用 Pruning 技術降低
    • Apriori原理 : 若一 Itemset 為 frequent，則其所有 subsets 必為 frequent
      • Anti-monotone property (反單調性) : $X \in Y \Rightarrow s(X) \ge s(Y)$，即一 Itemset 的 Support 必小於等於其子集之 Support
      • Algorithm :
        1. Candidate Generation : 使用 $F_{k-1} \times F_{k-1}$ Method
          • 合併兩個 frequent $(k-1)$-itemsets，如果兩者前/後 $(k-2)$ 個 Items 相同
        2. Candidate Pruning : 用 Apriori 原則去剪
        3. Support Counting : 使用 Hashing Tree
          • 用一 Hash Function 去將 Candidates 分類

        4. Cnadidate Ellimination
      • Apriori 影響因素 :
        1. minsup threshold 的大小 : 影響 frequent itemsets 數量
        2. Dimensionality (Items 數量) : 需要更多空間去儲存每個 Item 的 Support count
        3. 資料庫大小
        4. Transaction 平均 Width
  • 降低 Transactions數量 ($N$)
  • 降低 Comparisons 次數 ($NM$) :
    • 使用有效率的資料結構去儲存 Candidates 或 Transactions
    • 無須比較每筆 Transaciton 中的每組 Candidates

Rule Generation

  • Def : 從每個 Frequent Itemset 中產生高 Confidence 的 Rules，且該 Rule 是 Frequent Itemset 的 Binary partitioning
    • e.g. 假設 {A, B, C, D} 為一 frequent itemset，而 Candidates rules 為 :

  • Confidence of rules 有 Anti-monotone 特性
    • e.g. {A, B, C, D} 為一 frequent 4-itemset，則 $c(ABC\to D) \ge c(AB\to CD) \ge c(A \to BCD)$

Maximal Frequent Itemset & Close Itemset

  • Maximal Frequent Itemset (最大頻繁項目集) :
    • Def : 一 Itemset 為 frequent，且其直接 supersets 都非 frequent
  • Closed Itemset (封閉項目集) :
    • Def : 一 Itemset 的 Support，與其直接 supersets 的 Support 都不同
  • 差異 :

Pattern Evaluation

  • Confidence 的缺點 : $c(X \to T)$ 會導致在同一筆交易中，擁有 $X$ 實際上會減少擁有 $Y$ 的機會
  • Statistical Independence 的目標 : $c(X \to Y) = s(Y)$
  • Lift (增益率) :
    • 公式 : $Lift=\frac{P(Y|X)}{P(Y)}$
    • 用於 Rules
  • Interest :
    • 公式 : $Interest=\frac{P(X, Y)}{P(X)P(Y)}$
    • 用於 Itemsets
  • 特性比較 :
    1. Variable Permutation 特性 :$M(B,A)=M(A,B)$
      • Sysmmetric measures :
        • e.g. Support、Lift…
      • Asysmmetric measures :
        • e.g. Confidence…
    2. Row/Column Scaling 特性 : e.g. $\phi$-Coefficient
    3. Inversion Operation
    4. Null Addition
  • Simpson’s Paradox (辛普森悖論) :
    • Def : 觀察到的 Relationship 會受到一些 Hidden Variables 所影響
      • Hidden Variables 可能會導致 Relationship 的消失或反轉
    • 解法 : 適當的 Stratification (分層) 能避免產生出虛假的 Rules
  • Support Distribution 的影響 :
    • $minsup$ 過高，則可能會錯過有趣的稀有 items
    • $minsup$ 過低，則可能會導致運算量過大

  • Cross-Support Patterns :
    • Def : Rules 中包含 Support degrees 差異很大的 Items
    • 測量 :
      • 假設一 Itemset 為 $X={x_1,x_2,\cdots,x_d}$，則定義$$r(X)=\frac{min ( s(x_1),s(x_2),\cdots,s(x_d))}{max ( s(x_1),s(x_2),\cdots,s(x_d))}$$
      • 可以使用此方式來修剪 Cross-Support Patterns，卻無法避免
  • H-Confidence :
    • Def : 所有從 Itemset $X$ 形成關聯規則的最小 Confidence
    • 公式 : $hconf(X)=min(conf(X_1 \to X_2))$
      • 其中，$X_1,X_2 \subset X$、$X_1\cap X_2=\emptyset$、$X_1\cup X_2=X$
      • 可推導出 $hconf(X)=\frac{s(X)}{max{s(x_1),s(x_2),\cdots,s(x_d)}}$
    • 與Cross-Support Patterns關係 : $0 \le hconf(X) \le r(X) \le 1$
  • Hyperclique :
    • 可以利用 $\text{H-Confidence} \lt h_c$ 去消除 Cross-Support Patterns
    • Def : 任何能滿足給定 H-Confidence threshold $h_c$ 的 Itemset
    • 特性 :
      1. 不一定是 Frequent Itemset
      2. 為 Anti-monotone
      3. Closed Hyperclique : 一 Itemset 的 H-Confidence，與其直接 supersets 的 H-Confidence 都不同
      4. Maximal Hyperclique : 一 Itemset 的 H-Confidence $\le h_c$，且其直接 supersets 的H-Confidence皆 $\ge h_c$
      5. High Affinity(高度親和性) :
        • Def : 具有高 H-Confidence 的 Hyperclique，擁有非常相似的 Items
      6. Hyperclique 中 Items 的 Support 都不會相差甚遠
        • 有利於 Pruning