Apriori算法详解

• 主要内容
  
  • 关联分析
  • Apriori算法原理
  • 生成频繁项集
  • 生成关联规则
  • FP-Growth算法

---

  消费者在商店都买物品时，通过查看哪些商品经常在一起购买，可以帮助商店了解消费者的购买行为。这种从数据海洋中抽取的知识可以用于商品定价、市场促销、存货管理等环节。从大规模数据集中寻找物品间的隐含关系被称作关联分析（association analysis）或者关联规则学习（association rule learning）。这里的主要问题在于，寻找物品的不同组合是一项十分耗时的任务，所需的计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到频繁项集。本文介绍如何使用Apriori算法来解决上述问题。

---

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

图1
  频繁项集是指那些经常出现在一起的商品集合，图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子（一个集合即为一个项集，频繁项集即为出现频率较高的项集）。从这个数据集中也可以找到诸如”尿布➞葡萄酒”的关联规则，即如果有人买了尿布，那么他很可能也会买葡萄酒。使用频繁项集和关联规则，商家可以更好地理解他们的顾客。那么，如何定义这些关系呢？我们通过支持度和可信度来度量这些有趣的关系。
  一个项集的支持度（support）被定义为数据集中包含该项集的记录所占的比例。如上图中，{豆奶}的支持度为4/5，而在5条交易记录中有3条包含{豆奶,尿布}，因此{豆奶,尿布}的支持度为3/5（此处的支持度采用的相对支持度，即比例形式3/5。有些教材上采用绝对支持度，即只有计数3，不需要除以总的交易记录）。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留大于等于最小支持度的项集。
  可信度或置信度（confidence）是针对关联规则来定义的。规则{尿布}➞{葡萄酒}的可信度被定义为”支持度({尿布,葡萄酒})/支持度({尿布})”，由于{尿布,葡萄酒}的支持度为3/5，尿布的支持度为4/5，所以”尿布➞葡萄酒”的可信度为3/4。这意味着对于包含”尿布”的所有记录，我们的规则对其中75%的记录都适用。
  支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于0.8的所有项集，应该如何去做？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，但当物品成千上万时，上述做法非常非常慢。Apriori算法，能够有效减少关联规则学习时所需要的计算量。

2、Apriori算法原理
  假设我们在经营一家商品种类并不多的杂货店，我们对那些经常在一起被购买的商品非常感兴趣。我们只有4种商品：商品0，1，2，3，代表图1中所涉及的商品。那么所有可能被一起购买的商品组合都有哪些？这些商品组合可能只有一种商品，比如商品0，也可能包括两种、三种或者四种。我们并不关心某人买了两件商品0或者四件商品2的情况，我们只关心他购买了一种或多种商品。图2显示了所有商品之间所有可能的组合，物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。

图2
  前面说过，我们的目标是找到经常一起购买的物品集合，我们使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。例如，集合{0,3}，如何计算其支持度？我们遍历每条记录，并统计所有包含0和3的记录，统计结果除以总的交易记录数即为支持度。
  我们不难发现，上述求解项集支持度的计算过程，即使对于仅有4种物品的集合，也需要遍历数据15次。而随着物品数目的增加，遍历次数也会急剧地增加。对于包含N种物品的数据集，共有2N−1$2^N-1$种项集组合。事实上，出售10000或者更多物品的商店并不少见，即使只出售100种商品的商店也会有1.26×1030$1.26\times {10}^{30}$种可能的项集组合。这对于计算机而言，运算过程会变得异常缓慢。
  为了降低计算所需时间，研究人员发现一种所谓的Apriori原理，可以帮助我们减少计算量。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的，即如果{0,1}是频繁的，那么{0}、{1}也一定是频繁的。更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的，即如果{0}、{1}是非频繁的，那么{0,1}也一定是非频繁的。
  在图3中，已知阴影项集{2,3}是非频繁的。利用这个知识，我们就知道项集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非频繁的。也就是说，一旦计算出了{2,3}的支持度，知道它是非频繁的后（即支持度小于某个阈值minsupport），就不需要计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度，因为我们知道这些集合同样也是非频繁的。使用该原理就可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

图3

3、生成频繁项集
  关联分析的目标包括两项：发现频繁项集和发现关联规则。首先需要找到频繁项集，然后才能获得关联规则（正如前文所讲，计算关联规则的可信度需要用到频繁项集的支持度）。
  Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个元素的项集列表。接着扫描数据集来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉（剪枝）。然后，对剩下来的集合进行组合以生成包含两个元素的项集（连接）。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。
  例如，图1中，只包含一个元素的项集的支持度如下表1：

表1
  令最小支持度为0.5，即表1中支持度大于等于0.5的项集，才能进行组合以生成包含两个元素的项集。{豆奶}、{莴苣}、{尿布}、{葡萄酒}，支持度大于等于最小支持度，可以进行两两组合。组合后，包含两个元素的项集的支持度如下表2：

表2
  由于最小支持度为0.5，因此表2中支持度大于等于0.5的项集，才能进行组合以生成包含三个元素的项集。{豆奶,莴苣}、{豆奶,尿布}、{莴苣,尿布}、{尿布,葡萄酒}，支持度大于等于最小支持度，可以进行两两组合。组合后，包含三个元素的项集的支持度如下表3：

表3
  由于表3中，所有项集的支持度均小于最小支持度0.5，因此算法终止。上述过程中，表1、表2中绿色标注的项集即为频繁项集。

4、生成关联规则
  一旦找出所有频繁项集，就可以直接由他们产生强关联规则（强关联规则满足最小支持度以及最小可信度）。对于可信度，可用式(1)计算：

  条件概率用项集的支持度表示，其中，support(AB)$support(AB)$是包含元素A、B的项集的支持度，support(A)$support(A)$是包含元素A的项集的支持度。根据式(1)，关联规则可以由如下方式产生：

• 对于每个频繁项集S$S$，产生S$S$的所有非空子集。
• 对于S$S$的每个非空子集s$s$，如果support(t)support(s)≥min_confidence$\frac{support(t)}{support(s)}\ge min\mathrm{\_}confidence$，则输出规则”s→(S−s)$s\to (S-s)$”。其中，min_confidence$min\mathrm{\_}confidence$为最小置信度阈值。

  由于规则由频繁项集产生，因此每个规则都自动的满足最小支持度。
  关于关联规则的获取，此处借用上文中的例子进行讲解。例如，表2中的一个频繁项集S=$S=${豆奶,莴苣}，那么由S$S$可以产生哪些关联规则呢？由于S$S$的非空子集为{豆奶}、{莴苣}，因此根据式(1)可以得到如下规则，以及对应的可信度：

（1）{豆奶}➞{莴苣}，confidence=3/4=0.75$confidence=3/4=0.75$
（2）{莴苣}➞{豆奶}，confidence=3/4=0.75$confidence=3/4=0.75$
  假设最小置信度min_confidence=70%$min\mathrm{\_}confidence=70\mathrm{\%}$，则上述两条规则均满足要求，均为强关联规则。所得规则（1）的语义为：若消费者购买“豆奶”，则其有75%$75\mathrm{\%}$的概率购买“莴苣”；所得规则（2）的语义为：若消费者购买“莴苣”，则其有75%$75\mathrm{\%}$的概率购买“豆奶”。

5、FP-Growth算法
  Apriori算法能够有效发现频繁项集并获取关联规则，但是每次计算频繁项集的支持度（主要是指：项集所构成的超集的支持度）都要遍历整个数据库，因此造成过多的时间开销，无法高效处理大规模数据集。为了克服Apriori算法这一缺点，FP-Growth算法应运而生，FP-Growth算法能够有效提高Apriori算法提取频繁项集支持度的效率，详细的介绍可以参考FP-Growth算法详解。