关联规则算法应用

① apriori算法是什么

Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

算法应用

随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求＂与＂运算，寻找频繁项集。

② 关联算法

关联, 指的是关联分析, 这里引用网络的定义.

通过关联分析, 可以挖掘出"由于某些事件的发生而引起另外一些事件的发生"之类的规则, 比如说"面包=>牛奶", 其中面包被称为规则的前项, 而牛奶则被称为规则的后项.

常用于关联分析的算法有Apriori算法, FP-growth算法, Eclat算法, 灰色关联法等, 下面将着重介绍Apriori算法.

在介绍Apriori算法之前, 我们先来了解几个概念:
1.事务: 一条交易记录称为一个事务
2.项: 交易中的每一个物品称为一个项
3.项集: 包含0个或多个项的集合
4.支持度计数: 项集在所有事务中出现的次数.
5.支持度: 支持度计数除于总的事务数.
6.频繁项集: 支持度大于等于某个阀值的项集.

关联规则的挖掘通常分为两步: 第一步, 找出所有的频繁项集; 第二步, 由频繁项集产没判答生强关联规则. 而Apriori算法则是挖掘频繁项集的基本算法.

可以看到以上每个过程均需要扫描一次数据, 为了提高频繁项集逐层迭代产生的效率, 需要利用一条重要性质, 其称为先验性质:

当然, 非频繁项集的所有超集也一定是非频繁的.

将先验性质应用到Apriori算法中就是将之枯慧前的过程分为两大部分, 连接步和剪枝步.
连接步: 连接步的目的是产生候选项集.
剪枝步: 应用先验性质对候选项集进行筛选, 将不满足先验性质的候选项集剔除, 再进而根据最小支持度找出频繁项集, 这样可以有效缩短计算量.

关联分析的目标是找出强关联规则, 因此这里的关联规则是指强关联规则, 我们把满足最小支持度和最小置信度的规则称为强关联规则.
对于规则A=>冲敏B, 置信度的计算公式就是项集{A, B}的支持度计数除于项集{A}的支持度计数.

优点: 简单, 易理解, 对数据要求低
缺点: 容易产生过多的候选项集, I/O负载大.

③ 关联规则-算法原理与案例

✓ 关联规则（Association Rules）反映一个事务与其他事务之间的相
互依存性和关联性。如果两个或者多个事务之间存在一定的关联关
系，那么，其中一个事务就能够通过其他事务预测到。
✓ 关联规则是无监督的机器学习方法，用于知识发现，而非预测
✓ 关联规则的学习器（learner）无需事先对训练数据进行打标签，因
为无监督学习没有训练这个步骤。缺点是很难对关联规则学习器进
行模型评估，一般都可以通过业务经验观测结果是否合理

关联规则之前，需要理解一些基本概念。
下图数据集中，每一组数据ti表示不同的顾客一次在商场购买的商品
的集合，以该数据为例来说明关联规则相关概念。

图片显示, 表中存储着二维结构的记录集，记为D，简称事务集D，含事务的个数称为|D|。那么图片中从t1,t2,......直到t7含7个事务，|D|=7。

设I={i1,i2,…im}是m个不同项目的集合，每个ik（k=1,2,…m）称为一个项目(Item),I是所有项目(Item)的集合，称为所有项集(Items)。图片中所有项集I={牛肉，鸡肉，牛奶，奶酪，靴子，衣服}，其中，“牛 肉”、“鸡肉”等均为项目。

在事务数据集里的一笔记录，记为事务T，{牛肉、鸡肉、牛奶}便是一个事务，每个事务T（Transaction）是所有项集I的一个子集。

项目的集合简称为项集（Itemset），其元素个数为项集的长度，长度为k的项集称为k-项集（k-Itemset）。
如{牛肉}、{鸡肉}均为1-项集，{牛肉、奶酪}为2-项集，{鸡肉、衣 服、牛奶}为3-项集。

重点概念5-项集的支持度：项集支持度用于描述X的重要性，对于项集X，count为事务集D中包含X的事务的数量，项集X的支持度就是项集X出现的概率。

项集的支持度就是该项集出现的次数除以总的记录数，例如，上述的7个事务中，{牛肉、鸡肉}出现的次数是3次，支持度就是3/7 。

我们在发现规则的时候，希望关注频次高的项集，发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支持度（Minimum Support），记为supmin。支持度大于或等于最小支持度的项集称为频繁项集，简称频繁集，反之则称为非频繁集。支持度在这个算法中通常是人为规定的参数。

规则R的支持度是交易集中同时包含X和Y的交易数与所有交易数之比；

支持度计算在事务集中，既有A又有B的概率。
例：在7条记录中，既有牛肉又有鸡肉的记录有3条，则 R:牛肉 鸡肉的支持度为3/7，即 ，表示在所有顾客当中有3/7同时购买了牛肉和鸡肉，其反映了同时购买牛肉和鸡肉的顾客在所有顾客当中的覆盖范围。

规则R的置信度是指包含X和Y的交易数与包含X的交易数之比。

规则的置信度的意义在于项集{X，Y}同时出现的次数占项集{X}出现次数的比例，即发生X的条件下，又发生Y的概率。

关联规则的最小支持度也就是衡量频繁集的最小支持度（Minimum
Support），记为supmin，它用于衡量规则需要满足的最低重要性。
Minimum Support是一个阈值参数，必须在处理关联规则之前指定该
参数。该参数表示用户对某些项集和规则感兴趣，这些规则表示数
据集的最低支持度。它是用于对项集进行限制，而不是对规则进行
限制。

✓ 如果关联规则R: A→B满足Support(A→B )>=supmin 且
Confidence( A→B )>=confmin,则称关联规则R: 为强关联规则，否
则称关联规则为弱关联规则;
✓ 在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，
筛选出来的强关联规则才能用于指导商家的决策;

引入例题来计算这个概念，例：在所分析的10000个事务中，6000个事务包含计算机游戏，7500包含游戏机游戏，4000个事务同时包含两者。
下面我们计算：关联规则（计算机游戏 → 游戏机游戏）支持度=4000/10000=0.4，置信度=4000/6000=0.67，但其实这个关联规则是一个误导。

在用户购买了计算机游戏后有（4000/6000）=0.667的概率去购买游戏机游戏，而在没有任何前提条件下，用户反而有（7500/10000） =0.75的概率去购买游戏机游戏，也就是说设置了购买计算机游戏这样的条件反而会降低用户去购买游戏机游戏的概率，所以计算机游戏和游戏机游戏是相斥的。

此时需要引入提升度的概念。

如果两个条件相互独立，则P(XY)=P(X)· P(Y),即提升度为1；如果小于1，说明使用这条规则来进行推荐，还不如不推荐（推荐无效）；
一般在数据挖掘中当提升度大于3时，我们才承认挖掘出的关联规则是有价值的。

上述例子中，假设购买计算机游戏为X，购买游戏机游戏为Y，则有提升度数=0.667/0.75<1

这表明这样的推荐是无效的，提升度小于1，还不如不推荐。

第一步，生成候选项集，然后根据指定的最小支持度，过滤掉非频繁项集，生成频繁项集。
该步骤需要多次遍历：第一次遍历，对所有单项的支持度进行计数并确定频繁项；在后续的每次遍历中，利用上一次遍历所得频繁项集作为种子项集，产生新的频繁项集-候选项集，并对候选项集的支持度进行计数，在本次遍历结束时统计满足最小支持度的候选项集，本次遍历对应的频繁项集就算是确定了，这些频繁项集又成为下一次遍历的种子；重复此遍历过程，直到再不能发现新的频繁项集。

第二步，找出第一步的频繁项集中的规则，然后根据指定的最小置信度，过滤掉弱规则。第一步的计算量比第二步的计算量大。

步骤1：
✓ 生成候选1-项集C1,计算支持度
✓ 根据最小支持度，生成频繁1-项集L1

步骤2：
✓ 生成候选2-项集C2,计算支持度
✓ 根据最小支持度，生成频繁2-项集L2

✓ 生成关联规则时，最简单的方法就是对于每个频繁项集，列出其所有非空
真子集，任取其中两个分别作为LHS和RHS，形成关联规则，并计算每条关
联规则的置信度，删除弱规则
✓ 上例中 ， 对于频繁项集 {B,C,E} ， 它的非空子集有 {B},{C},{E},
{B,C},{B,E},{C,E}。据此获得的关联规则及其置信度，置信度>=50%(最小
置信度)，都是强关联规则

✓ Apriori原理可以帮助减少计算量
✓ Apriori原理：某个项集是频繁的，那么它的所有子集也是频繁的；
更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的
所有超集也是非频繁的（称为项集的反单调性，向下闭合性）

已知阴影项集{2,3}是非频繁的。利用Apriori原理，我们知道项集{0,2,3}， {1,2,3}以及{0,1,2,3}也是非频繁的。也就是说，一旦计算出了{2,3}的支持 度 ， 知 道 它 是 非 频 繁 的 ， 就 可 以 紧 接 着 排 除 {0,2,3} ， {1,2,3} 和 {0,1,2,3}。

✓ 反单调性能迅速剪枝，提高搜索频繁项集的处理效率

在商品列表中找出频繁项集,构建商品列表。

创建模型，传入数据，输出的support就是支持度。

该段输出结果如下

接下来可以筛选支持度大于某特定值的二项集

输出结果

④ 关联规则算法(The Apriori algorithm)

        关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物篮分析 (market basket analysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是"尿布和啤酒"的故事了。

        本篇的Apriori算法主要是基于频繁集的关联分析。其主要目的就是为了寻找强关联规则。

        要理解频繁集、强关联规则，要先借助下面的一个情境，来介绍几个重要概念。

        下表是一些购买记录：

将购买记录整理，可得到下表，横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。

        置信度，表示这条规则有多大程度上值得可信。

        设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A->B)=P(B|A)。例 如计算"如果Orange则Coke"的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke。其置信度为0.5。

        支持度，计算在所有的交易集中，既有A又有B的概率。

        例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Coke）会有40%的可能发生。

支持度大于预先定好的最小支持度的项集。

       关联规则：令项集I={i1,i2,...in}，且有一个数据集合D，它其中的每一条记录T，都是I的子集。那么关联规则是形如A->B的表达式，A、B均为I的子集，且A与B的交集为空。这条关联规则的支持度：胡颂support = P(A并B)。这条关联规则的置信度：confidence = support(A并B）/suport(A)。

       强关联规则：如果存在一条关联规则，它的支持度和置信度都大于预先定义好的最小支持度与置信度，我们就称它为强关联规则。

下面用一个例子说明算法的过程：

项目集合 I={1，2，3，4，5};

事务集 T：

设定最小支持度（minsup）=3/7，最小置信度（misconf）=5/7。

假设：n-频繁项目集为包含n个元素的项目集，例如1-频繁项目集为包含1个元素的项目集

则这里，1-频繁项目集有：{1}，{2}，{3}，{4}，{5}

生成2-频繁项目集的过程如下：

       裤燃郑 首先列出所有可能的2-项目集，如下：

        {1，2}，{1，3}，{1，4}，{1，5}

        {2，3}，{2，4}，{2，5}

        {3，4}，{3，5}

        {4，5}

        计算它们的支持度，发现只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度    满足要求，因此求得2-频繁项目集：

        {1，2}，{1，3}，{1，4}，{2，3}，{2，4}

生成3-频繁项目集：

对于现有的2-频繁项目集，两两取并集，并段纯确保第三个二元组也在2-频繁项目集内，把得到的所有3-项目集分别计算支持度，剔除不满足最小支持度的项目集；

例如，

{1，2}，{1，3}的并集得到{1，2，3}；

{1，2}，{1，4}的并集得到{1，2，4}；

{1，3}，{1，4}的并集得到{1，3，4}；

{2，3}，{2，4}的并集得到{2，3，4}；

但是由于{1，3，4}的子集{3，4}不在2-频繁项目集中，所以需要把{1，3，4}剔除掉。{2，3，4} 同理剔除。

然后再来计算{1，2，3}和{1，2，4}的支持度，发现{1，2，3}的支持度为3/7 ，{1，2，4}的支持度为2/7，所以需要把{1，2，4}剔除。因此得到3-频繁项目集：{1，2，3}。

重复上面步骤继续寻找n-频繁项目集，直到不能发现更大的频繁项目集。所以，到此，频繁项目集生成过程结束。

这里只说明3-频繁项目集生成关联规则的过程，即以集合{1，2，3}为例：

回顾事物集，先生成1-后件的关联规则：

（1，2）—>3，置信度=3/4（出现（1，2）的记录共4条，其中有3条包含3，所以3/4）；

（1，3）—>2，置信度=3/5；

（2，3）—>1，置信度=3/3；

第二条置信度<5/7，未达到最小置信度，所以剔除掉。所以对于3-频繁项目集生成的强关联规则为：（1，2）—>3和（2，3）—>1。

这表示，如果1、2出现了，则极有可能出现3；2、3出现，则极有可能有1。

http://www.cnblogs.com/junyuhuang/p/5572364.html

⑤ 关联规则分析怎么做

关联规则是反映一个事物与其他事物之间的相互依存性和关联性，常用于实体商店或在线电商的推荐系统：通过对顾客的购买记录数据库进行关联规则挖掘，最终目的是发现顾客群体的购买习惯的内在共性，例如购买产品A的同时也连带购买产品B的概率，根据挖掘结果，调整货架的布局陈列、设计促销组合方案，实现销量的提升，最经典的应用案例莫过于<啤酒和尿布>。

关联规则分析中的关键概念包括：支持度(Support)、置信度(Confidence)与提升度(Lift)。首先，我们简单温故下这3个关键指标：

支持度 (Support)
支持度是两件商品（A∩B）在总销售笔数(N)中出现的概率，即A与B同时被购买的概率。

公式：

例子说明：
比如某超市2016年有100w笔销售，顾客购买可乐又购买薯片有20w笔，顾客购买可乐又购买面包有10w笔，那可乐和薯片的关联规则的支持度是20%，可乐和面包的支持度是10%。

置信度 (Confidence)
置信度是购买A后再购买B的条件概率。简单来说就是交集部分C在A中比例，如果比例大说明购买A的客户很大期望会购买B商品。

公式：

例子说明：
某超市2016年可乐购买次数40w笔，购买可乐又购买了薯片是30w笔，顾客购买可乐又购买面包有10w笔，则购买可乐又会购买薯片的置信度是75%，购买可乐又购买面包的置信度是25%，这说明买可乐也会买薯片的关联性比面包强，营销上可以做一些组合策略销售。

提升度 (Lift)
提升度表示先购买A对购买B的概率的提升作用，用来判断规则是否有实际价值，即使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效，小于1则无效。

公式：

例子说明：
可乐和薯片的关联规则的支持度是20%，购买可乐的支持度是3%，购买薯片的支持度是5%，则提升度是1.33>1, A-B规则对于商品B有提升效果。

理论很简单，真正实践起来却会遇到种种困难，印证了那句"数据分析师的50%～80%的时间都花在了处理数据上”，例如一般POS明细是以下图表形式展现：

要计算支持度(Support)、置信度(Confidence)与提升度(Lift)，首先需要知道Freq(A∩B)、Freq(A)、Freq(B)和总笔数数值，那么需要对商品进行排列组合。

所以，我们希望转换成下表形式，如销售ID=000001， 4种商品的两两组合（种）：

若一个收银小票（销售ID）有30种商品，则组合数达到:

而可视化层级上还需要展现集团下每个分公司、每个城市、每个门店、月度、季度或者年度时间的关联规则分析，如果用传统的工具来实现上述分析无异于大海捞针。

下面我们就来看看在BDP中如何实现Apriori算法，实现关联规则分析：

商品两两组合的初步想法是通过量化的思想对商品进行编码，比方说可按照增序（从1开始），算出每笔销售单最大值，求出两者差值得到一组数组，通过数组行转列形式实现2种商品两两组合。

图：销售单2种商品两两组合逻辑图

操作①：

【工作表】-【创建合表】-【SQL创建】

图：商品量化

上图转换成日期的形式，主要目的是为下一步的数组转列做准备，为配合explode（）函数使用。其中需要说明的是上图[日期]字段是自定义日期，可以更改成任意日期，没有实际日期意义。

图：商品组合数效果

上图主要使用的关键函数是FILL_DATES（[日期1],[日期2]），Explode（）。组合效果初显现，只是缺另一个商品名，然后把[下一日期]字段通过LEFT JOIN 关联出商品B的名称。

操作②：

【工作表】-【创建合表】-【多表关联】 用于创建表关联 包括（LEFT/INNER/ FULL JOIN）

图：商品组合数实现

从上图可以看到A商品和B商品两两组合逻辑已完成，在当前表基础上我们已经可以去做连带分析内容。

在这里，求Freq(A)和Freq(B)和总笔数数值就不祥述了，思想大致是求出所有销售商品的A 和B商品的频次，通过合表关联，整合到一张大表。

操作③：

【工作表】-【创建合表】-【追加合并】合并订单总数 ，A商品订单数，B商品订单数和A∩B商品连带笔数

图：追加合并逻辑实现

追加合并可以把相同字段商品合并在一起，方便计算三个指标（支持度、置信度、提升度）有利于可视化展现。

操作④：

可视化展现：【BDP】-【仪表盘】

图：仪表盘全局展示

注：为了更好体现可视化效果，这部分的可视化展示成果并非使用上述的测试数据或某个企业数据。

制作三个图表进行购物篮分析：

图： TOP 20商品连带次数

上图反映季度连带最高频次商品，高联带商品意味着对客户吸引力大商品粘性强，同时也可以查看不同分公司的TOP20连带情况。根据结果我们可以合理设计促销策略，例如买2送1等。

图：商品组合指标

置信度高说明商品连带紧密，说明客户连带意愿强，同时关注支持度，支持度高说明是需求量大，如果支持度低，置信度高其实对市场作用是有限小的。

图：购物篮分析详情

通过单价，支持度，置信度，提升度综合指标来看待商品组合，发现高价值关联商品，有助于提升客单价，同时也需要考虑提升度，提升度小于1，提升效果有限，可以把精力花在提升度大于1的商品组合。

同样地，我们是否可以实现三种商品的组合呢？答案是显然的，只要我们深入理解以上过程，三种商品关联也是可以在BDP中实现的。 作者 熊辉 本文转载自 BDP商业数据平台，转载需授权