LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

关联规则学习(association rule learning)

关联规则学习介绍

关联规则学习的目标是在大数据中寻找变量之间的联系。

一般的设定是有$n$个物品(item):$i_1, \ldots, i_n$,数据为$m$条交易记录(transaction):$t_1, \ldots, t_m$。其中每个交易为$i_1, \ldots, i_n$的一个子集。

我们希望寻找形式为$\{i_{j_1}, \ldots, i_{j_p}\} \Rightarrow \{i_{l_1}, \ldots, i_{l_q}\}$的规则(rule),其含义是在已知交易包含物品$i_{j_1}, \ldots, i_{j_p}$的前提下,该交易很有可能包含物品$\{i_{l_1}, \ldots, i_{l_q}\}$。

下面的例子来自维基百科:

交易号 牛奶 面包 黄油 啤酒 尿布
1 1 1 0 0 0
2 0 0 1 0 0
3 0 0 0 1 1
4 1 1 1 0 0
5 0 1 0 0 0

在该数据中,总共有5样物品:牛奶、面包、黄油、啤酒、尿布,总共有5个交易:{牛奶,面包},{黄油},{啤酒,尿布},{牛奶,面包,黄油},{面包}。

其中一个规则为$\{\{黄油,面包\} \Rightarrow \{牛奶\}\}$:购买黄油和面包的人一定买了牛奶。

我们注意到购买牛奶的人中,有一半买了黄油,因此可以认为$\{\{牛奶\} \Rightarrow \{黄油\}\}$也是一个关联规则,但是概率只有0.5。

关联规则学习的一个重要步骤是提取高频物品集(frequent itemset),即寻找出现的频率较高的物品的子集。

比较著名的算法有先验算法(Apriori algorithm)、Eclat算法(Eclat algorithm)、FP增长算法(FP-growth algorithm)。本文介绍Apriori算法。

关联规则学习的应用

最经典的应用场景为市场分析(market basket analysis),即通过消费车的购物车消费数据分析用户行为的一些规律。通过该分析,我们可以做一些商品推荐,例如在在线购物网站上为购买A物品的用户推荐B物品,在实体超市将物品A和物品B捆绑销售或摆放在较近位置。

此外,关联规则分析还被应用在互联网分析(Web usage mining)、入侵检测系统(intrusion detection system)、连续生产过程(continuous production)、生物统计(bioinformatics)等领域。

术语

我们介绍一些常用的关联规则学习术语。

对于物品集(itemset)$X$我们定义support为该物品集出现的比例:

$$supp(X) = \#\{包含X所有元素的交易\}/m$$

例如在上面的数据集中,$supp(\{牛奶\}) = 0.4, supp(\{啤酒,尿布\}) = 0.2$。

对于两个物品集$X, Y$构成的规则$X \Rightarrow Y$,我们定义confidence,lift,和conviction如下:

例如对于$\{\{牛奶\} \Rightarrow \{面包\}\}$这个规则,其confidence为$\frac{2/5}{2/5} = 1$,而lift为$\frac{2/5}{2/5\times 3/5} = \frac{5}{3}$,conviction为$\frac{2/5}{1 - 1} = \infty$。

先验算法(Apriori algorithm)原理

提取关联规则的算法有两个步骤:

  1. 对于阈值(threshold)$\alpha$,找出所有support至少为$\alpha$的物品集,即高频物品集(frequent itemset)。
  2. 对于阈值$\beta$,找出这些高频物品集能够组成的confidence至少为$\beta$的规则$\{X \Rightarrow Y\}$。

其中第二个步骤比较直接,第一个步骤为核心部分。如果使用暴力搜索穷举所有的物品集,那么计算复杂度为$\Omega(2^nm)$,在$n$较大时不可能完成。因此我们需要效率更高的算法。

Apriori算法的目标是计算出所有出现在至少$t$个交易的物品集。

Apriori算法使用了自下而上(bottom-up)的方法,从出现次数至少为$t$的单个物品出发,每次从所有至少出现$t$次的$i$个物品组成的集合构造所有出现次数至少为$t$次的$i + 1$个物品组成的集合。

该算法用到了向下封闭性质(downward closure property):对于一个出现次数至少为$t$的集合$S$,任取$S$的子集$T$,则$T$的出现次数至少为$t$。

根据向下封闭性质,若$i + 1$个物品构成的物品集出现至少$t$次,则其中任何$i$个物品组成的大小为$i$的物品集出现次数一定至少为$t$。

因此在已经有所有出现次数为$t$的i元集$L_i = \{l_1, \ldots, l_k\}$的前提下,我们对于每一个$l_j$增加一个元素$x$,并检查$l_j \cup \{x\}$的所有$k$元子集是否均属于$L_i$。可以生成元素个数为$i + 1$的所有候选物品集(candidate set):$C_{i + 1}$。再检查每个候选集是否出现次数至少为$t$,可以得到所有次数为$t$的$i + 1$元集:$L_{i + 1}$。

我们将Apriori算法的步骤整理如下:

实例

考虑4个物品的7个交易:$$\{1, 2, 3, 4\}, \{1, 2, 4\}, \{1, 2\}, \{2, 3, 4\}, \{2, 3\}, \{3, 4\}, \{2, 4\}$$需要找出所有出现次数至少为$t = 3$的物品集。

Python实现

Python中可以使用mlxtend库运行Apriori算法。

import pandas as pd
from mlxtend import preprocessing, frequent_patterns

# support阈值
support_threshold = 0.2
# confidence阈值
confidence_threshold = 0.5

# 篮子数据
basket = []
basket.append(['Milk', 'Cheese', 'Butter'])
basket.append(['Milk', 'Apples', 'Cheese'])
basket.append(['Apples', 'Banana'])
basket.append(['Milk', 'Cheese'])
basket.append(['Apples', 'Banana', 'Tea'])
basket.append(['Milk', 'Cheese', 'Banana'])
basket.append(['Beer', 'Cheese'])
basket.append(['Cheese', 'Banana'])
basket.append(['Cheese', 'Milk', 'Beer'])

# 转换为稀疏矩阵
encoder = preprocessing.TransactionEncoder()
X = encoder.fit(basket).transform(basket, sparse=True)
X = pd.SparseDataFrame(X, columns=encoder.columns_, default_fill_value=False)

# 运行Apriori提取出现比例超过support阈值的物品集
frequent_itemsets = frequent_patterns.apriori(X, min_support=support_threshold, use_colnames=True)
# 提取关联规则
rules = frequent_patterns.association_rules(frequent_itemsets, metric='confidence', min_threshold=confidence_threshold)

print('购物篮为%s' % (basket, ))
print('confidence至少为%.2f%%的关联规则为' % (confidence_threshold * 100, ))
for left, right, confidence in zip(rules['antecedants'], rules['consequents'], rules['confidence']):
    print('%s => %s: %.2f%%' % (set(left), set(right), confidence * 100))
        
输出:

购物篮为[['Milk', 'Cheese', 'Butter'], ['Milk', 'Apples', 'Cheese'], ['Apples', 'Banana'], ['Milk', 'Cheese'], ['Apples', 'Banana', 'Tea'], ['Milk', 'Cheese', 'Banana'], ['Beer', 'Cheese'], ['Cheese', 'Banana'], ['Cheese', 'Milk', 'Beer']]
confidence至少为50.00%的关联规则为
{'Banana'} => {'Apples'}: 50.00%
{'Apples'} => {'Banana'}: 66.67%
{'Banana'} => {'Cheese'}: 50.00%
{'Beer'} => {'Cheese'}: 100.00%
{'Cheese'} => {'Milk'}: 71.43%
{'Milk'} => {'Cheese'}: 100.00%
	

常见面试问题

Q:简述Apriori算法的原理。

更多机器学习相关问题见本网站论坛机器学习理论版面机器学习实践版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏