Association Rules Mining

Association Rules Mining

由于花括号会被解析成JS表达式.. 所以这一节的很多花括号都会莫名其妙的代码块包起来.. 见谅

Basic Concepts

Frequent Pattern Mining

1. Frequent Itemset: 组合。
   比如超市购物篮中 - {Milk, Bread}，{Milk, Eggs}，{Bread, Eggs}，{Milk, Bread, Eggs}
2. Frequent Seqiential Pattern: 序列。
   比如先买蔬菜，再买啤酒
3. Freqent Structured Pattern: 结构。 比如社交网络中频繁出现的连结子图模式。

Market Basket Analysis

• Co-marketing: 捆绑
• Shelf placement: 常一起买的商品放一起 -> 促销；分开放 -> 增加客户滞留时间
• Cross-marketing: 打折Milk，也可能刺激Bread销量

Rule Strcture

{Antecedent} -> {Consequent}

• Antecedent: 前件，前提条件
• Consequent: 后件，结论

eg. {Bread, Egg} -> {Milk}

caution

这只是共现(Co-occurrence)，并不是因果关系(Causality)

这应该算正题开始了..?

Generating Itemsets

比如商品集合里有20个东西，要生成所有可能的Itemsets时，组合数是: $2^20 - 1$ 爆炸了。

解决方法：
用Support来提前筛选掉无关的Itemsets。

Suport

$$Support(X=>Y) = \frac{Transactions \ containing \ X \cup Y}{Total \ Count}$$

这是一个衡量某个Itemset在数据集中出现频率的指标。

info

支持度单调性（Support Monotonicity）: Itemset越大，支持度越小或相等。

也就是说 $Support(X) \geq Support(X \cup Y)$

Minimum Support Threshold（最小支持度阈值）

为了避免保存所有的Itemsets，设置一个最小支持度阈值 --> 只保留支持度大于这个阈值的Itemsets，它们被称为频繁项集(Frequent Itemsets)。

这里是筛选问题，那么生成问题就交给Apriori

Apriori Principle

核心思想：
如果一个Itemset是不频繁的，那么它的任何超集也是不频繁的。

基本流程：

1. 从单个项(1-Itemset)开始
2. 计算所有1-Itemset的支持度，筛选出频繁项集
3. 合并频繁项集，生成新的候选项集(k-Itemset)
   • 合并的方法：只合并那些前k-1项集相同的Itemsets（eg. {Milk, Bread}和{Milk, Eggs} -> {Milk, Bread, Eggs}）
4. 重复2和3，直到没有新的候选项集

note

这是一个剪枝原则，可以大大减少我们需要检查的Itemsets数量。

Rules from Itemsets（从Itemsets中生成规则）

从频繁项集中生成规则时，是将其进行所有可能的二元划分(Binary Partitions)

eg. 频繁项集{Milk, Bread, Eggs}，可以划分为：

- {Milk, Bread} -> {Eggs}
- {Milk, Eggs} -> {Bread}
- {Bread, Eggs} -> {Milk}
- {Milk} -> {Bread, Eggs}
- {Bread} -> {Milk, Eggs}
- {Eggs} -> {Milk, Bread}

规则的方向matters!

比如{Milk} -> {Bread} 和 {Bread} -> {Milk} 是不同的规则。

Generating Association Rules（生成关联规则）

一旦我们在Apriori Principle的第二部得到了频繁项集，就可以从中生成Candidate Rules.
但这里又有问题了：Itemsets本来就多，规则还更多..

解决方法：
用Confidence来筛选掉一些无意义的规则。

Confidence

$$Confidence(X=>Y) = Support(X \cup Y) / Support(X) = P(Y|X)$$

与Support不同的是，Confidence是一个条件概率，也就是说它有方向性。

属于Confidence的剪枝

如果一个规则 $A \rightarrow B \cup C$ 不满足最小置信度阈值，
那么它的任何子集 $A \rightarrow B$ 和 $A \rightarrow C$ 也不满足最小置信度阈值。

不过呢，Confidence也有问题：
Strong Association不一定是Useful Association..

Lift（提升度）

$$Lift(X=>Y) = \frac{P(X \cup Y)}{P(X) \cdot P(Y)} = \frac{Confidence(X=>Y)}{Support(Y)} = \frac{Support(X \cup Y)}{Support(X) \cdot Support(Y)} = \frac{P(Y|X)}{P(Y)}$$

解释：

• Lift > 1: X和Y是正相关的，X的出现会增加Y的出现概率 -> Interesting rule
• Lift = 1: X和Y是独立的，X的出现不会影响Y的出现概率
• Lift < 1: X和Y是负相关的，X的出现会减少Y的出现概率

Terms（术语

名称	定义
Frequent	passes the support threshold
Strong	passes the confidence threshold
Closed	no superset with the same support
Closed Frequent	closed and frequent
Maximal Frequent	a frequent itemset that is not a subset of any other frequent superset