Frequent Pattern

Frequent pattern: a pattern (a set of items, subsequences, substructures, etc.) that occurs frequently in a data set.

Association Rules

給定兩個東西：

1. 資料集 S
2. Minimun confidence (min.conf) 與 Minimum support (min.sup)

關聯性（Association rule）可以寫成

A → B : 集合 A 出現的話表示集合 B 會出現

Rule strength

對於所有 association rules X → Y ∈ P(S) × P(S)，我們只關心那些相關性強的 rules，相關性可以由下面兩個數據表示

• X 跟 Y 一起出現的機率 $$ support(X\cup Y)=Pr(X\cup Y)=\frac{\text{包含} X\cup Y \text{的資料數目}}{\text{資料總數}} $$

• 在 X 出現的前提下 Y 出現的機率 $$ confidence(X\cup Y)=Pr(X| Y)=\frac{\text{包含} X\cup Y \text{的資料數目}}{\text{包含}X\text{的資料數目}}=\frac{support(X\cup Y)}{support(Y)} $$

強弱則由給定的閥值判斷，只取

• support(X∪Y) ≥ min.sup
• confidence(X∪Y) ≥ min.conf

的 association rules

Example

假設 min.sup = 50%，min.conf = 50%。

其中的 frequent patterns 有：

• A:3, B:3, D:3, E:3, AD:3

符合限制的 association rules 有：

• A → D： support = 60%, confidence = 100%
• D → A： support = 60%, confidence = 75%

Apriori

概念

1. 常常出現的子集的子集也常常出現
2. 如果集合 S 不常出現， 就不用檢查 P(S) 中的集合是否常出現

避免產生出重複的 frequent pattern - Join

如果兩個有k個元素的集合 A, B，有 k − 1 個元素相同的話，就可以 join 在一起。

如 A, B, C, D, E 跟 A, B, C, D, F 可以 join 成 A, B, C, D, E, F， 而 A, B, C, D, E 跟 A, B, C, E, F 不能 join。

方法

1. 從只有一個元素的 pattern 開始，建立表格 C₁
2. 掃過所有資料，蒐集 support 夠大的 pattern，建立表格 L₁
3. Join L₁ 中的 pattern，產生表格 C₂
4. 回到2.
5. 檢查最後的 L_i 中的 pattern 的子集合以得到 association rules