总览

关联规则是一种无监督学习方法。这是一种描述性(descriptive)的而非预测性(predictive)的方法，经常用于发现隐藏在大型数据集背后的有趣关系(interesting, hidden relationship)。所揭示的关系可以被表示为规则(rules)或频繁项集(frequent itemset)。通常被用于在数据库中挖掘交易。关联规则可以回答以下问题：

• 哪些产品可能会被一起购买？
• 与这个人相似的客户倾向于购买什么产品？
• 对于已经购买了该产品的客户，它们还可能查看或者购买什么其他类似的产品？

每笔交易(transaction)包括一个或者多个商品(item)。关联规则通过分析购买的物品，看看哪些商品经常(frequently)被一起购买，并发现用来描述购买行为的一系列规则。关联规则的目的是发现商品之间有趣的关系(interesting relationship)。

每个发现的规则 (Uncovered rule) 的形式是X -> Y，即当商品X被观察到(obeserved)，商品Y也会被观察到。这种情况下，规则的左边(left-hand side LHS)为X，规则的右边(right-hand side RHS)为Y。例：麦片 -> 牛奶 (90%) 代表了当麦片被购买时，90%的时间牛奶也会被购买。

由于经常被用于挖掘客户交易，关联规则有时也称为购物篮分析 (market basket analysis)。

项集 (itemset): 指的是包含某种关系的一系列项目 a collection of items (或单独的个体 individual entities)。这可以是再一次交易中一起购买的一系列零售商品，也可以是一个用户在单个会话中点击的一组超链接。

包含了k个项目的项集称为k项集 (k-itemset)，{item1, item2, …, item k}

Apriori算法

为了避免枚举所有的项集(这可能会带来指数级 exponentially 的运算)，我们将使用Apriori算法，这个算法是用于生成关联规则的最早的，最基本的算法。它使用了支持度(support)来修剪项集 (pruning itemsets) 和控制候选项集(candidate itemsets)的指数级增长(exponential growth)。

• 支持度(support): 给定商品X(item X)，其支持度是包含了X的交易的百分比。比如，如果80%的交易含有项集{bread}，则{bread}的支持度就是0.8。若60%包含{bread, butter}，则{bread, butter}的支持度为0.6。

• 频繁项集(frequent itemset): 一个频繁项集包含足够频繁地一起出现的项目。这里"够频繁(often enough)"使用最小支持度(minimum support)进行正式定义。一个频繁项集的支持度应该大于或者等于最小支持度。像之前的例子，{bread}和{bread, butter}在最小支持度为0.5时都被认为是频繁项集。如果最小支持度为0.7，则只有{bread}可以被认为是一个频繁项集。

• Apriori属性(property)或向下封闭性(downward closure property)：当一个项集是频繁的，那么该项集的任意子集也必定是频繁的。Apriori属性给Apriori算法提供了基础。如，若60%的交易包含{bread, jam}，那么至少60%的交易将包含{bread}或{jam}。换言之，若{bread, jam}的支持度是0.6，那么{bread}和{jam}的支持度都会不小于0.6。
  因此，若X是非频繁的，那么包含X的超集也必定是非频繁的。
  

算法流程

Apriori算法采用一种自下而上的迭代方式，

1. 它首先确定所有的项目(或者1项集 1-itemset，如{bread}, {milk}, {egg}, …)
2. 下一次迭代中，所识别的频繁1项集(frequent 1-itemset)被配对成2项集(2-itemsets) (如，{bread, egg})
3. 增大项集并重复这个过程。
4. 直到 (1) 支持度过低 (run out of support)，(2) 项集达到了预定长度(predefined length)。

算法输入： 1. 一个交易数据库。2. 一个最小支持度的阈值。3. 一个代表了项集可达最大长度的可选参数。

算法输出： 所有频繁k项集的集合。

从频繁k项集能够帮我们创建 候选规则(candidate rules) 的集合。{milk, eggs}能够得出候选规则: {milk} -> {eggs} 和 {eggs} -> {milk}。

评估候选规则 (Evaluation of Candidate Rules)

置信度 (Confidence)

被定义为与每个发现规则相关联的确定度(certainty)或可信度(trustworthiness)。

最小置信度(Minimum Confidence):
当算法识别出的关系的置信度大于或等于最小置信度(能被设定的阈值)时，该关系可能会被认为是有趣的。根据样本数据集，较高的置信度表示规则 (X->Y) 更有趣或更可靠。所有的规则都能通过支持度或者置信度进行排序，以过滤无趣的规则并保留有趣的规则。

问题 (issue) :
给定规则 X-> Y，置信度只考虑先导(X)和共存的(X和Y)，它没有将规则的后继(Y)考虑进去。因此，置信度不能 确定规则是包含这个关系的真正含义(true implication of the relationship)还是纯属巧合(purely coincidental)。

提升度 (Lift)

测量当X和Y相互统计独立时，X和Y一起出现的次数比预期多多少。提升度是X和Y真正相关性(而非巧合地共同出现)的一种度量。

如果X和Y相互统计独立，那么提升度就是1.相比之下，规则X->Y的提升度大于1则表示规则是有用的。提升度的值越大，表明X和Y之间的关联性更强。

杠杆率 (leverage)

是和提升度类似的概念，但使用的不是比率而是使用差。杠杆率测量的是，X和Y在数据集中一起出现的概率与X和Y相互统计独立(statistically independent)时一起出现的概率，这两者的差 (difference)。

当X和Y相互统计独立时，杠杆率为0。如果X和Y具有某种关系，杠杆率将大于0。较大的杠杆率表示X和Y之间有更强的联系。

对比

置信度(confidence)能够识别有相关性的规则但是它不能确定这个规则是否是巧合。高置信度的规则有时候会产生误导，因为置信度没有考虑规则右边(RHS)项集的支持度。提升度(lift)和杠杆率(leverage)等度量不但能确保识别出有趣的规则，还能过滤出巧合的规则。

结合方法 (Combination of Measures)

这些方法通常会被结合使用。例如：找到所有具有最低置信度的规则，然后在这些规则中，按照提升度或者杠杆率以降序对规则进行排序。

提升度和置信度是成正比的， Lift = Confidence / Support(Y)。因此当Y的支持度保持不变时，提升度和置信度成正比，线性趋势的斜率是 Support(Y)的倒数。

问题: 这些措施不能反映规则的新颖性(novelty of rules)，即区分已知规则和对观察者来说有趣的新规则。因此，规则的新颖性和价值都需要由人类观察者评估。

验证和测试

1. 通过置信度，提升度和杠杆率之类的统计度量来建立。如果规则涉及互相独立地项目或涵盖极少数交易，则被认为是无趣的，因为它们捕捉到的可能是虚假的关系。
   巧合(coincidental)示例：如果 95%的客户购买 X，90%的客户购买 Y，那么 X 和 Y 会同时发生的可能性至少为 85%，即使这二者之间没有任何关系。
2. 可以通过主观角度来建立另一组标准(subjective criteria)。即使有较高的置信度，可以从主观上认为一条规则是无趣的，除非它揭示了任何非预期的盈利行为。如 {paper}->{pencil}这种规则可能是无趣的。但是{diaper}->{beer}这样的规则在满足了最小支持度和最小置信度的情况下，就可以在主观上认为是有趣的，因为这条规则是非预期的，可能会给零售商提供一个交叉销售的机会。

诊断

1. 像置信度，提升度和杠杆率这样的度量应该与人们的主观见解一起使用，以解决无趣和巧合规则的问题。
2. 执行模型之前必须适当地指定最小支持度，这能够减少出现导致太多或者太少的规则的可能性。
3. Apriori算法可以是计算昂贵的，因为对于每个级别的支持度，该算法需要扫描整个数据库以获得结果。因此，随着数据库的增长，它在每次运行计算时会需要更多时间。一些方法可以提高Apriori的效率：分区，采样，交易压缩，基于哈希的项集技术和动态项集计数等。

应用

• 购物车/购物篮分析 (market basket analysis)
• 推荐系统 (recommender system)
• 点击流分析 (clickstream analysis)