整理写一份比较易懂的Apriori算法：

关联规则想必大家都是听说过 尿布和啤酒的故事；

在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：”跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在“尿布与啤酒”背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒

从这个例子中引出里 关联规则

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性，是数据挖掘的一个重要技术，用于从大量数据中挖掘出有价值的数据项之间的相关关系。

常见的购物篮分析

该过程通过发现顾客放人其购物篮中的不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。其他的应用还包括价目表设计、商品促销、商品的排放和基于购买模式的顾客划分。

可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则

 

本篇文章主要讲解 关联规则的基本算法：Apriori算法

（一）相关的指标：

1、支持度

支持度是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。例如，“牛奶 + 面包”出现了 3 次，那么这 5 笔订单中“牛奶 + 面包”的支持度就是 3/5=0.6。

2、置信度

置信度是个条件概念，就是说在 A 发生的情况下，B 发生的概率是多少。即就是当你购买了商品 A，会有多大的概率购买商品 B。例如，置信度（牛奶→啤酒）=2/4=0.5，代表如果你购买了牛奶，有50%的概率会购买啤酒。

3、提升度

提升度代表的是“商品 A 的出现，对商品 B 的出现概率提升的”程度。计算公式如下：提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)
所以提升度有三种可能：
（1）提升度 (A→B)>1：代表有提升；
（2）提升度 (A→B)=1：代表有没有提升，也没有下降；
（3）提升度 (A→B)<1：代表有下降。

(二)Apriori的工作原理

Step1:K=1，计算 K 项集的支持度；
Step2:筛选掉小于最小支持度的项集；
Step3:如果项集为空，则对应 K-1 项集的结果为最终结果。
否则 K=K+1，重复 1-3 步。

Apriori 在计算的过程中有以下几个缺点：
（1）可能产生大量的候选集，因为采用排列组合的方式，把可能的项集都组合出来了；
（2）每次计算都需要重新扫描数据集，来计算每个项集的支持度。
所以 Apriori 算法会浪费很多计算空间和计算时间，为此提出了 FP-Growth 算法进行改进，其特点是：创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间；整个生成过程只遍历数据集 2 次，大大减少了计算量。

算法不好看 不易懂，来个例子解释一下：

(三)实例解释

算法推导：

我们的数据集D有4条记录，分别是{1,3,4},{2,3,5},{1,2,3,5},{2,5}

1.设置最小支持度：50%

2.针对数据集生成频繁1项集,并计算其支持度

根据数据集，{1},{2},{3},{4},{5},对应的出现次数为2，3，3，1，3，其支持度为2/4=0.5，3/4=0.75，3/4=0.75，1/4=0.25，3/4=0.75

3.排除支持度<0.5的项集，那么就剩下{1},{2},{3},{5}

4.生成频繁2项集，（根据步骤三剩下的项生成）

{1,2},{1,3},{1,5},{2,3},{2,5},{3,5} 此时第一轮迭代结束了

5.进入第二轮迭代

{1,2},{1,3},{1,5},{2,3},{2,5},{3,5}对应出现的次数为：1，2，1，2，3，2，其支持度为0.25，0.5，0.25，0.5，0.75，0.5

6.排除<0.5的支持度的项集，剩下的{1,3},{2,3},{2,5},{3,5}

7.生成频繁3项集

{1,2,3},{1,2,5},{1,3,5},{2,3,5}此时第二轮迭代结束

8.进入第三轮迭代

{1,2,3},{1,2,5},{1,3,5},{2,3,5}对应的次数为：1，2，1，1，其支持度为：0.25，0.5，0.25，0.25

9.排除<0.5的项集，剩下的 {2,3,5}

10.此时数量为3不支持生成频繁4项集，迭代结束。