一、关联分析介绍

商场的销售过程，涉及很多机器学习的应用，商品的陈列，购物卷的提供，用户忠诚度等等，通过对这些大量数据的分析，可以帮组商店了解用户的购物行为，进而对商品的定价、市场促销、存货管理等进行决策帮组。

从大规模数据集中寻找物品间的隐含关系被称作关联分析（association analysis）或者关联规则学习（association rule learning）。这里的主要问题在于，寻找物品的不同组合是一项十分耗时的任务，所需的计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到频繁项集。

关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集或者关联规则。频繁项集（frequent item sets）是经常出现在一块的物品的集合，关联规则（association rules）暗示两种物品之间可能存在很强的关系。
下图给出了某个杂货店的交易清单。

频繁项集是指那些经常出现在一起的物品集合，上图中的集合{葡萄酒，尿布, 豆奶}就是频繁项集的一个例子。从下面的数据集中也可以找到诸如尿布➞葡萄酒的关联规则。这意味着如果有人买了尿布，那么他很可能也会买葡萄酒。使用频繁项集和关联规则，商家可以更好地理解他们的顾客。

当寻找频繁项集时，什么样的数据才是频繁项集呢？频繁（frequent）的定义是什么？

常用的频繁项集的评估标准有支持度，置信度两个。

• 支持度：数据集中，包含该项集的记录出现的次数占总数据集的比重。
• 可信度：也称为置信度，体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。针对一条关联规则来定义的。

从上图交易清单中可以得到，{豆奶}的支持度为4/5。而在5条交易记录中有3条包含{豆奶，尿布}，因此{豆奶，尿布}的支持度为3/5。

针对一条诸如{尿布}➞{葡萄酒}的这条关联规则，这条规则的可信度被定义为“支持度({尿布, 葡萄酒})/支持度({尿布})”。由于{尿布, 葡萄酒}的支持度为3/5，尿布的支持度为4/5，所以“尿布➞葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。

因此，我们可以利用支持度和可信度是用来量化关联分析是否成功。但是，当数据量非常大的时候，物品成千上万时，按照上述方法生成一个物品所有可能组合的清单非常非常慢，统计每一种组合它出现的频繁程度也很非常慢。这催生了关联规则挖掘的算法Apriori，该原理会减少关联规则学习时所需的计算量。

二、Apriori算法原理

一杂货店有四种商品 0，1，2，3.这些商品的组合可能有一种，二种，三种，四种。我们的关注点：用户购买一种或者多种商品，不关心具体买的商品的数量。
集合{0，1，2，3}中所有可能的项集组合如下图

四种商品要遍历15次，随着物品数目的增加遍历次数会急剧增加。对于包含N种商品的数据集一共有2^N-1种项集组合。

Apriori原理：

• 如果某个项集是频繁的，那么它的所有子集也是频繁的。
• 如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

根据Apriori原理，假设集合{2，3}是非频繁项集，则{0，2，3}，{1，2，3}，{0，1，2，3}也是非频繁的，它们的支持度就不需要计算了。

Apriori算法采用迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

第i次的迭代过程包括扫描计算候选频繁i项集的支持度，剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。

上面的数据集D有4条记录，分别是134，235，1235和25。现在用Apriori算法来寻找频繁k项集，最小支持度设置为50%。首先生成候选频繁1项集，包括所有的5个数据并计算5个数据的支持度，计算完毕后进行剪枝，数据4由于支持度只有25%被剪掉。最终的频繁1项集为1235，现在我们链接生成候选频繁2项集，包括12，13，15，23，25，35共6组。此时第一轮迭代结束。

进入第二轮迭代，扫描数据集计算候选频繁2项集的支持度，接着进行剪枝，由于12和15的支持度只有25%而被筛除，得到真正的频繁2项集，包括13，23，25，35。现在链接生成候选频繁3项集，123， 125，135和235共4组，这部分图中没有画出。通过计算候选频繁3项集的支持度，发现123，125和135的支持度均为25%，因此接着被剪枝，最终得到的真正频繁3项集为235一组。由于此时无法再进行数据连接，进而得到候选频繁4项集，最终的结果即为频繁3三项集235。

使用该原理就可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

三、算法实现

算法伪代码：

3.1 apriori算法辅助函数

辅助函数有creat_c1、scan_d

可以看出，支持度不小于0.5的项集被选中到L中作为频繁项集，可以根据不同的需求设定最小支持度的值，从而得到想要的频繁项集。

3.2 组织完整的Apriori发现频繁项集

3.3 从频繁项集中挖掘关联规则

要找到关联规则，先从一个频繁集开始，我们想知道对于频繁项集中的元素能否获取其它内容，即某个元素或者某个集合可能会推导出另一个元素。从表1 可以得到，如果有一个频繁项集 {豆奶，莴苣}，那么就可能有一条关联规则 "豆奶 --> 莴苣"，意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。但是这一条反过来并不一定成立。

一个频繁项集可以产生许多可能的关联规则，如果能在计算规则可信度之前就减少规则的数目，就会很好的提高计算效率。有一条规律就是：如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求，例如下图的解释：

结果中给出三条规则：{1} ➞ {3}、{5} ➞ {2}及{2} ➞ {5}。可以看到，后两条包含2和5的规则可以互换前件和后件，但是前一条包含1和3 的规则不行。下面降低可信度阈值之后看一下结果：

一旦降低可信度阈值，就可以获得更多的规则。

四、示例：发现毒蘑菇的相似特征

首先看一下毒蘑菇的数据集：

第一个特征表示有毒或者可食用。如果某样本有毒,则值为2。如果可食用,则值为1。下一个特征是蘑菇伞的形状,有六种可能的值，分别用整数3-8来表示。

为了找到毒蘑菇中存在的公共特征，可以运行Apriori算法来寻找包含特征值为2的频繁项集。

扩大范围到3个：

接下来需要观察一下这些特征，以便知道了解野蘑菇的那些方面。

五、小结

关联分析是用于发现大数据集中元素间有趣关系的一个工具集，可以采用两种方式来量化这些有趣的关系。第一种方式是使用频繁项集,它会给出经常在一起出现的元素项。第二种方式是关联规则，每条关联规则意味着元素项之间的“如果……那么”关系。

Apriori的方法简化了计算量，在合理的时间范围内找到频繁项集：Apriori原理是说如果一个元素项是不频繁的，那么那些包含该元素的超集也是不频繁的。

Apriori算法从单元素项集开始，通过组合满足最小支持度要求的项集来形成更大的集合。支持度用来度量一个集合在原始数据中出现的频率。

每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。下一篇会介绍FP-growth算法，和Apriori算法相比，该算法只需要对数据库进行两次遍历，能够显著加快发现繁项集的速度。