本节书摘来自华章出版社《Python数据挖掘：概念、方法与实践》一书中的第2章，第2.2节，作者[美] 梅甘·斯夸尔（Megan Squire），更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.2 迈向关联规则
频繁项集的内容都很好，但是我们的终极目标是关联规则，那更激动人心。关联规则是从频繁项集中经过一些小曲折形成的。我们对如下关于频繁项集的陈述感兴趣：购买香草威化的人有60%的可能性同时购买香蕉。换言之，我们需要学习如何计算几个附加指标，首先是被称为“支持度”和“置信度”的两个指标。
2.2.1 支持度
如果你打算寻找频繁项集，那么还需要一种表示在篮子中看到这些组合出现的频繁程度以及这个数量是否可称为“频繁”的手段。如果我看到90%的篮子中有{香草威化，香蕉}这样的组合，可以认为是频繁的吗？50%的篮子呢？5%呢？我们称这一数字为项集的支持度。支持度就是在所有篮子中看到项集的次数。
为了使支持度更有意义，再来谈论“兴趣度”，我们必须设置最小支持阈值。最小支持阈值是对问题领域有意义的百分比（0%～100%）。如果我们将最小支持阈值设置为5%，就意味着如果在所有篮子中至少有5%能发现该项集，则视其为频繁项集。
2-项集的支持度通常用概率标记法书写：
换言之，我们可以将上式读成“X->Y的支持度等于同时包含X和Y的篮子的百分比”。在本例中，项目X可能是香草威化，Y可能是香蕉。为了计算项集的支持度，我们统计同时包含这两种商品的篮子数量，将结果除以篮子总数。如果项集的支持度超过最小支持阈值，则我们认为该项集可能是有用的。
2.2.2 置信度
一旦发现了频繁项集，我们就可以开始考虑项集中的一个或者多个项目是否引发其他项目的购买。例如，知道在购物篮里放入香草威化的顾客中，有75%的人同时购买香蕉，这是很有用的。但是，另一方面，在购物篮中包含香蕉的客户中，可能只有1%的人将购买香草威化。为什么？这是因为购买香蕉的人比购买香草威化的人多得多。香蕉较为常见，而香草威化则较为少见。所以，购买关系的方向不一定是对称的。
这就引出了一个关键的概念—置信度。有向关系的置信度写作：
我们可以将上式读成“X导致Y的置信度为已知X的情况下Y的概率”。或者用另一种方式书写为：
X->Y的置信度是同时包含X和Y的篮子的百分比除以只包含X的篮子百分比。
一旦有了支持度和置信度，我们就可以开始将频繁项集扩展为关联规则了。
2.2.3 关联规则
既然我们已经知道如何确定某个项集是否频繁出现，也知道如何设置支持度和置信度，就可以从频繁项集中建立可能的关联规则。
下面是关联规则的一个例子：
香草威化->香蕉，生奶油
[支持度＝1%，置信度＝40%]
我们可以将这条规则读作：在所有篮子中，有1%包含香草威化、香蕉和生奶油的组合；在购买香草威化的客户中，有40%同时购买了香蕉和生奶油。
规则的左侧是确定项，称作先导。右侧是结果项，称作后继。如果我们切换左侧和右侧的项目，则必须计算不同的关联规则，由于香蕉很受欢迎，得到的规则可能是：
香蕉->香草威化，生奶油
[支持度＝0.001%，置信度＝10%]
2.2.4 包含数据的示例
想象我们拥有一家商店，且有下表所示的10个商品篮子。你马上就可以看出有人为的痕迹，因为这家商店中的所有篮子都正好有3件商品，这在真实的商店中不太可能出现。
篮 子 商品1 商品2 商品3
1 香草威化 香蕉 狗粮
2 香蕉 面包 酸奶
3 香蕉 苹果 酸奶
4 香草威化 香蕉 生奶油
5 面包 香草威化 酸奶
6 牛奶 面包 香蕉
7 香草威化 苹果 香蕉
8 酸奶 苹果 香草威化
9 香草威化 香蕉 牛奶
10 香蕉 面包 花生酱
首先，我们需要计算商店中所有单独商品的支持度。在这10个篮子中共有9种商品：
商 品 支 持 度 商 品 支 持 度
苹果 3 花生酱 1
香蕉 8 香草威化 6
面包 4 酸奶 4
狗粮 1 生奶油 1
牛奶 2
为了简化例子，我们现在只考虑频繁项集{香草威化，香蕉}。该项集的支持度是同时包含香草威化和香蕉的篮子的百分比。数据中有4个篮子（1、4、7、9）同时包含这两项。因此，香草威化->香蕉或者香蕉->香草威化这两条规则的支持度都是40%，因为10个篮子中有4个同时包含两者。
现在，我们可以使用这些支持度计算提议的两条关联规则的置信度：
香草威化->香蕉
香蕉->香草威化
置信度（香草威化->香蕉）＝支持度（香草威化U香蕉）/支持度（香草威化）＝4/6＝67%
置信度（香蕉->香草威化）＝支持度（香草威化U香蕉）/支持度（香蕉）＝4/8＝50%
写成关联规则，可以得到：
香草威化->香蕉[支持度＝40%，置信度＝67%]
香蕉->香草威化[支持度 ＝40%，置信度＝50%]
规则“香草威化->香蕉”强于（支持度相同，置信度更高）规则“香蕉->香草威化”。
2.2.5 附加值—修复计划中的漏洞
香草威化->香蕉[s＝40%，c＝67%]这样的规则是引人注目、令人满意的。但是，这是一个非常小的数据集，只是为了举例而人为制作的。在某些情况下，关联规则可能很容易引起误导，我们应该小心为之。考虑下面的例子。
想象在一家不同的商店中，香草威化和香蕉的支持度可能是这样的：
商 品 支 持 度
{香草威化} 50%
{香蕉} 80%
{香草威化，香蕉} 30%
在这种情况下，商品的单独支持度相当高，但是商品组合的支持度较低。
在这个例子中，香草威化->香蕉的置信度为0.3/0.8＝37.5%。
有什么问题呢？有些商品自身的表现好于作为关联规则后继时的表现。即使规则符合某些最小支持阈值，我们也必须考虑商品在规则之外的表现。为此，我们计算一个称作关联规则附加值的测度。香草威化->香蕉规则的附加值通过从规则置信度减去香蕉的支持度计算。如果附加值是大的正数，那么规则是好的、有用的。如果附加值接近于0，则这条规则可能是正确的，但是没太大用处。如果附加值是大的负数，那么规则中的商品实际上是负相关的，这时单独使用表现会更好。
我们这样计算附加值：
附加值＝规则置信度-右侧的支持度
使用上表，可以计算出：
规则置信度＝0.375
右侧（香蕉）的支持度＝0.8
附加值＝0.375―0.8＝―0.425
这个数字告诉我们，实际上香蕉自己的表现更好。而且，我们提出的将香蕉展示柜移到香草威化旁边的建议可能是个错误，因为利用香蕉和威化之间关系的尝试没有任何收益。
我们可以稍微改变一下数据，人为生成正面的有用规则：
商 品 支 持 度
{香草威化} 50%
{香蕉} 30%
{香草威化，香蕉} 30%
现在，香草威化->香蕉的置信度为0.3/0.3=100%。
规则置信度＝1.0
香蕉的支持度＝0.3
附加值＝1―0.3＝0.7
在这种情况下，商店中的香蕉和香草威化应该放在一起，因为明显没有任何人将香蕉作为唯一商品购买！
计量关联规则兴趣度的方法还有很多，但是这超出了本书的范围。建议感兴趣的读者在谷歌学术上搜索介绍这一主题的最新论文。使用“关联规则兴趣度计量”等搜索词可以找到许多好的信息来源。在这些论文中，对于不同类型的数据和问题，有许多出色的“兴趣度”计量。
2.2.6 寻找频繁项集的方法
目前，我们已经知道，寻找关联规则的基础是首先寻找频繁项集。此后，只需要根据之前找到的计数进行计算。帮助我们更快找到频繁项集的一条重要原则称为向上闭包属性。向上闭包指的是，只有在项集的所有项目都频繁出现时，该项集才是频繁项集。换言之，如果项集中包含的项目不都是频繁出现的，则计算项集的支持度就毫无意义。
为什么了解闭包原则很重要？因为知道这一原则将节约许多计算可能项集的时间。在拥有数十万种商品的商店中计算每个可能项集的支持度明显不实际！尽可能减少项集的数量对我们绝对有好处。降低项集数量的策略之一是利用向上闭包减少项集数量，构建如下算法：
1）首先，设置一个支持阈值。
2）构建一个1-项集（单例）列表，该列表称为CandidateSingletonList：
为此，从每种可能项目的列表开始。这个列表称作CandidateSingletonList。
计算CandidateSingletonList中每个单独项目的支持度。
仅保留符合支持阈值的单例，并将其加入SingletonList列表。
3）构造一个2-项集列表（双个体集）：
为此，从SingletonList入手。
建立SingletonList中项目的所有可能配对的列表，这个列表称作Candidate-Doubleton-List。
仅保留符合支持阈值的候选二元组，将其添加到列表DoubletonList中。
4）构建3-项集（三个体集）列表：
为此，从DoubletonList入手。
建立DoubletonList中出现的每个可能单项的列表，将其与DoubletonList中的每个项目匹配，建立三元组。这个列表称为CandidateTripletonList。
仅保留符合支持阈值的候选三元组，将其添加到列表TripletonList中。
5）重复第4）步，用前面构建的列表中的单项生成n-项集，直到频繁项集用完。
这个算法称作Apriori算法，1994年Agarwal和Srikant的论文“Fast algorithms for mining association rules in large databases”（挖掘大型数据库中关联规则的快速算法）中率先概述了该算法。从那时起，人们提出了许多其他算法，对其进行优化，包括利用并行性和更有趣数据结构（如树）的方法。还有用于特种篮子数据的算法；例如，我们的篮子中是有序的项目，或者篮子中包含分类或者层次数据。但是，对于基本的频繁项集生成，Apriori算法是经典的选择。
在实现Apriori算法之前，我们要特别关注生成候选项集的几条重要方针。虽然计算2-项集是很费时的，但这是整个过程中最为密集的工作了。由于前面提到的闭包属性，后续的数据可能构建的项集比之前更少。本身，减少在二元组阶段需要比较的项目数量对我们肯定有利。为此，我们将设置一个最小支持阈值，但是这个阈值可以根据你所承担项目的需要进行调整。
在下一节中，我们将用Python实现Apriori算法，用它找出一个现实世界的数据库中的关联规则。
