Apriori algorithm

　　Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系，也被称为购物蓝分析 (Market Basket analysis)，因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子集。

　　关于这个算法有一个非常有名的故事："尿布和啤酒"。故事是这样的：美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并一直为众商家所津津乐道。

 【1】一些概念和定义

• 资料库（Transaction Database）：存储着二维结构的记录集。定义为：D 
  
• 所有项集（Items）：所有项目的集合。定义为：I。
• 记录 （Transaction ）：在资料库里的一笔记录。定义为：T，T ∈ D
• 项集（Itemset）：同时出现的项的集合。定义为：k-itemset（k项集），k-itemset ? T。除非特别说明，否则下文出现的k均表示项数。
• 支持度（Support）：定 义为 supp(X) = occur(X) / count(D) = P(X)。

   1. 解释一：比如选秀比赛，那个支持和这个有点类似，那么多人（资料库），其中有多少人是选择（支持）你的，那个就是支持度；
   2. 解释二：在100个人去超市买东西的，其中买苹果的有9个人，那就是说苹果在这里的支持度是 9，9/100；
   3. 解释三：P(X)，意思是事件X出现的概率；
   4. 解释四：关联规则当中是有绝对支持度（个数）和相对支持度（百分比）之分的。

• 置信度（Confidence/Strength）： 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y|X)。

在历史数据中，已经买了某某（例如：A、B）的支持度和经过挖掘的某规则（例如：A=>B）中A的支持度的比 例，也就是说买了A和B的人和已经买了 A的人的比例，这就是对A推荐B的置信度（A=>B的置信度）< /span>

• 候选 集（Candidate itemset）：通过向下合并得出的项集。定义为C[k]。
• 频繁集（Frequent itemset）：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。表示为L[k]。注意，频繁集的子集一定是频繁集。
• 提升比率（提升度Lift）：lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y))

经过关联规则分析后，针对某些人推销（根据某规则）比盲目推销（一般来说是整个数据）的比率，这个比率越高越好，我们称这个规则为强规则；

• 剪枝步

只有当子集都是频繁集的候选集才是频繁集，这个筛选的过程就是剪枝步；

__________________________________________________________________________________________________________

Apriori算法

其名字是因为算法基于先验知识(prior knowledge).根据前一次找到的频繁项来生成本次的频繁项。Apriori是关联分析中核心的算法。

Apriori算法的特点

只能处理分类变量，无法处理数值型变量；

数据存储可以是交易数据格式（事务表），或者是事实表方式（表格数据）；

算法核心在于提升关联规则产生的效率而设计的。

Apriori的思想

正如我们之前所提到的，我们希望置信度和支持度要满足我们的阈值范围才算是有效的规则，实际过程中我们往往会面临大量的数据，如果只是简单的搜索，会出现很多的规则，相当大的一部分是无效的规则，效率很低，那么Apriori就是通过产生频繁项集，然后再依据频繁项集产生规则，进而提升效率。

以上所说的代表了Apriori算法的两个步骤：产生频繁项集和依据频繁项集产生规则。

那么什么是频繁项集？

频繁项集就是对包含项目A的项目集C，其支持度大于等于指定的支持度，则C（A）为频繁项集，包含一个项目的频繁项集称为频繁1-项集，即L1。

为什么确定频繁项集？

刚才说了，必须支持度大于我们指定的支持度，这也就是说能够确定后面生成的规则是在普遍代表性上的项目集生成的，因为支持度本身的高低就代表了我们关联分析结果是否具有普遍性。

怎么寻找频繁项集？

这里不再讲述，直接说一个例子大家就都明白了。例子来源于

Apriori寻找频繁项集的过程是一个不断迭代的过程，每次都是两个步骤，产生候选集Ck（可能成为频繁项集的项目组合）；基于候选集Ck计算支持度，确定Lk。

Apriori的寻找策略就是从包含少量的项目开始逐渐向多个项目的项目集搜索。

数据如下：

我们看到，数据库存储的数据格式，会员100购买了 1 3 4三种商品，那么对应的集合形式如右边的图所示。那么基于候选集C1，我们得到频繁项集L1，如下图所示，在此表格中{4}的支持度为1，而我们设定的支持度为2。支持度大于或者等于指定的支持度的最小阈值就成为L1了，这里{4}没有成为L1的一员。因此，我们认定包含4的其他项集都不可能是频繁项集，后续就不再对其进行判断了。

 

 

此时我们看到L1是符合最低支持度的标准的，那么下一次迭代我们依据L1产生C2（4就不再被考虑了），此时的候选集如右图所示C2（依据L1*L1的组合方式）确立。C2的每个集合得到的支持度对应在我们原始数据组合的计数，如下图左所示。

 

此时，第二次迭代发现了{1 2} {1 5}的支持度只有1，低于阈值，故而舍弃，那么在随后的迭代中，如果出现{1 2} {1 5}的组合形式将不被考虑。

 

如上图，由L2得到候选集C3，那么这次迭代中的{1 2 3} { 1 3 5}哪去了？如刚才所言，{1 2} {1 5}的组合形式将不被考虑，因为这两个项集不可能成为频繁项集L3，此时L4不能构成候选集L4，即停止。

如果用一句化解释上述的过程，就是不断通过Lk的自身连接，形成候选集，然后在进行剪枝，除掉无用的部分。

根据频繁项集产生简单关联规则

Apriori的关联规则是在频繁项集基础上产生的，进而这可以保证这些规则的支持度达到指定的水平，具有普遍性和令人信服的水平。

以上就是Apriori的算法基本原理，留了两个例子，可以加深理解。

例子1：

例子2：