序列及Apriori生成候选算法.pptx

1 Apriori介绍Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。

首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。

最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。

其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。

因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I 出现次数更多。

因此A∩I也不是频繁的。

2连接步和剪枝步在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。

Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。

1）连接步为找出L k（所有的频繁k项集的集合），通过将L k-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。

候选集合记作C k。

设l1和l2是L k-1中的成员。

记l i[j]表示l i中的第j项。

假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集l i，l i[1]<l i[2]<……….<l i[k-1]。

将L k-1与自身连接，如果(l1[1]=l2[1])&&( l1[2]=l2[2])&&……..&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接。

连接l1和l2产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。

2）剪枝步C K是L K的超集，也就是说，C K的成员可能是也可能不是频繁的。

通过扫描所有的事务（交易），确定C K中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。

Apriori算法最新研究进展
目录Apriori算法背景
Apriori算法基本思想
Apriori算法的缺陷
Apriori算法的改进
关联规则算法的发展
Apriori算法代码实现
改进Apriori算法在股票分析中的应用研究
Apriori算法背景
挖掘结果分析
由规则1可知，当X股收益率下跌的时候，丫股收益下跌的概率为98%。

由规则5可知，在X股和丫股均下跌的时候，Z股上涨的概率为62.2%。

由规则7可知，在Y股上涨的时候，Z股下跌的概率几乎会达到100%。

表3部分实验结果
Table3Pail of rx|)erinieiilal results
ID关联规则规则结论支持度％置信度％1X:F Y:F5598
2Y:F X:F5372
3X:F Y:F3657
4X:F Z:T Y:F3896.5
5X:F Y:F Z:T41622 6X:T Y:T Z:F35.166
7Y:T Z:F361
8X:T Y:T Z：F37.565
9Z：F X:T Y:T36.2635 10Y:F Z:T5176.3
改进的Apriori算法在股票分析中的应用研究
实验表明，该改进算法可以很好地对股票
走势进行预测，具有很好的现实意义和应用前
景。

详细介绍关联规则Apriori算法及实现看了很多博客，关于关联规则的介绍想做⼀个详细的汇总：⼀、概念表1 某超市的交易数据库交易号TID顾客购买的商品交易号TID顾客购买的商品T1bread, cream, milk, tea T6bread, teaT2bread, cream, milk T7beer, milk, teaT3cake, milk T8bread, teaT4milk, tea T9bread, cream, milk, teaT5bread, cake, milk T10bread, milk, tea定义⼀：设I={i1,i2,…,im}，是m个不同的项⽬的集合，每个ik称为⼀个项⽬。

项⽬的集合I称为项集。

其元素的个数称为项集的长度，长度为k 的项集称为k-项集。

引例中每个商品就是⼀个项⽬，项集为I={bread, beer, cake,cream, milk, tea}，I的长度为6。

定义⼆：每笔交易T是项集I的⼀个⼦集。

对应每⼀个交易有⼀个唯⼀标识交易号，记作TID。

交易全体构成了交易数据库D，|D|等于D中交易的个数。

引例中包含10笔交易，因此|D|=10。

定义三：对于项集X，设定count(X⊆T)为交易集D中包含X的交易的数量，则项集X的⽀持度为：support(X)=count(X⊆T)/|D|引例中X={bread, milk}出现在T1，T2，T5，T9和T10中，所以⽀持度为0.5。

定义四：最⼩⽀持度是项集的最⼩⽀持阀值，记为SUPmin，代表了⽤户关⼼的关联规则的最低重要性。

⽀持度不⼩于SUPmin 的项集称为频繁集，长度为k的频繁集称为k-频繁集。

如果设定SUPmin为0.3，引例中{bread, milk}的⽀持度是0.5，所以是2-频繁集。

定义五：关联规则是⼀个蕴含式：R：X⇒Y其中X⊂I，Y⊂I，并且X∩Y=⌀。

表⽰项集X在某⼀交易中出现，则导致Y以某⼀概率也会出现。

关联规则（Apriori算法）关联分析直观理解 关联分析中最有名的例⼦是“尿布与啤酒”。

据报道，美国中西部的⼀家连锁店发现，男⼈们会在周四购买尿布和啤酒。

这样商店实际上可以将尿布与啤酒放在⼀块，并确保在周四全价销售从⽽获利。

当然，这家商店并没有这么做。

频繁项集是指那些经常出现在⼀起的物品集合，⽐如{葡萄酒，尿布, ⾖奶}就是频繁项集的⼀个例⼦⽀持度（support）　⼀个项集的⽀持度（support）被定义为数据集中包含该项集的记录所占的⽐例 {⾖奶}的⽀持度为4/5。

{⾖奶，尿布}的⽀持度为3/5可信度（confidence ）　可信度或置信度（confidence）是针对⼀条诸如{尿布} ➞ {葡萄酒}的关联规则来定义的。

这条规则的可信度被定义为“⽀持度({尿布, 葡萄酒})/⽀持度({尿布})”。

由于{尿布, 葡萄酒}的⽀持度为3/5，尿布的⽀持度为4/5，所以“尿布➞葡萄酒”的可信度为3/4=0.75。

这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适⽤。

Apriori算法的⽬标是找到最⼤的K项频繁集⽀持度和可信度是⽤来量化关联分析是否成功的⽅法。

假设想找到⽀持度⼤于0.8的所有项集，应该如何去做？⼀个办法是⽣成⼀个物品所有可能组合的清单，然后对每⼀种组合统计它出现的频繁程度，但当物品成千上万时，⾮常慢，这时就能⽤Apriori算法关联分析中最有名的例⼦是“尿布与啤酒”。

据报道，美国中西部的⼀家连锁店发现，男⼈们会在周四购买尿布和啤酒。

这样商店实际上可以将尿布与啤酒放在⼀块，并确保在周四全价销售从⽽获利。

当然，这家商店并没有这么做。

⼀般我们使⽤三个指标来度量⼀个关联规则，这三个指标分别是：⽀持度、置信度和提升度。

Support（⽀持度）：表⽰同时包含A和B的事务占所有事务的⽐例。

如果⽤P(A)表⽰使⽤A事务的⽐例，那么Support=P(A&B)Confidence（可信度）：表⽰使⽤包含A的事务中同时包含B事务的⽐例，即同时包含A和B的事务占包含A事务的⽐例。

Apriori算法python实现1. Apriori算法简介Apriori算法是挖掘布尔关联规则频繁项集的算法。

Apriori算法利⽤频繁项集性质的先验知识，通过逐层搜索的迭代⽅法，即将K-项集⽤于探察(k+1)项集，来穷尽数据集中的所有频繁项集。

先找到频繁项集1-项集集合L1，然后⽤L1找到频繁2-项集集合L2，接着⽤L2找L3，知道找不到频繁K-项集，找到每个L k需要⼀次数据库扫描。

注意：频繁项集的所有⾮空⼦集也必须是频繁的。

Apriori性质通过减少搜索空间，来提⾼频繁项集逐层产⽣的效率。

Apriori算法由连接和剪枝两个步骤组成。

2. Apriori算法步骤根据⼀个实例来解释：下图是⼀个交易单，I1⾄I5可看作5种商品。

下⾯通过频繁项集合来找出关联规则。

假设我们的最⼩⽀持度阈值为2，即⽀持度计数⼩于2的都要删除。

上表第⼀⾏（第⼀项交易）表⽰：I1和I2和I5⼀起被购买。

C1⾄L1的过程：只需查看⽀持度是否⾼于阈值，然后取舍。

上图C1中所有阈值都⼤于2，故L1中都保留。

L1⾄C2的过程分三步：遍历产⽣L1中所有可能性组合，即（I1,I2）...（I4,I5 )对便利产⽣的每个组合进⾏拆分，以保证频繁项集的所有⾮空⼦集也必须是频繁的。

即对于（I1，I2）来说进⾏拆分为I1，I2.由于I1和I2在L1中都为频繁项，所以这⼀组合保留。

对于剩下的C2根据原数据集中进⾏⽀持度计数C2⾄L2的过程：只需查看⽀持度是否⾼于阈值，然后取舍。

L2⾄C3的过程：还是上⾯的步骤。

⾸先⽣成（1，2，3）、（1，2，4）、（1，2，5）....为什么最后只剩（1，2，3）和（1，2，5）呢？因为剪枝过程：（1，2，4）拆分为（1，2）和（1，4）和（2，4）.然⽽（1，4）在L2中不存在，即⾮频繁项。

所有剪枝删除。

然后对C3中剩下的组合进⾏计数。

发现（1，2，3）和（1，2，5）的⽀持度2。

迭代结束。

所以算法过程就是 C k - L k - C k+1的过程：3.Apriori算法实现# -*- coding: utf-8 -*-"""Created on Sat Dec 9 15:33:45 2017@author: LPS"""import numpy as npfrom itertools import combinations # 迭代⼯具data = [[1,2,5], [2,4], [2,3], [1,2,4], [1,3], [2,3], [1,3], [1,2,3,5], [1,2,3]]minsp = 2d = []for i in range(len(data)):d.extend(data[i])new_d = list(set(d))def satisfy(s, s_new, k): # 更新确实存在的Le =[]ss_new =[]for i in range(len(s_new)):for j in combinations(s_new[i], k): # 迭代产⽣所有元素可能性组合 e.append(list(j))if ([l for l in e if l not in s]) ==[] :ss_new.append(s_new[i])e = []return ss_new # 筛选满⾜条件的结果def count(s_new): # 返回narray格式的Cnum = 0C = np.copy(s_new)C = np.column_stack((C, np.zeros(C.shape[0])))for i in range(len(s_new)):for j in range(len(data)):if ([l for l in s_new[i] if l not in data[j]]) ==[] :num = num+1C[i,-1] = numnum = 0return Cdef limit(L): # 删掉不满⾜阈值的Crow = []for i in range(L.shape[0]):if L[i,-1] < minsp :row.append(i)L = np.delete(L, row, 0)return Ldef generate(L, k): # 实现由L⾄C的转换s = []for i in range(L.shape[0]):s.append(list(L[i,:-1]))s_new = []# L = L.delete(L, -1, 1)# l = L.shape[1]for i in range(L.shape[0]-1):for j in range(i+1, L.shape[0]):if (L[j,-2]>L[i,-2]):t = list(np.copy(s[i]))t.append(L[j,-2])s_new.append(t) # s_new为列表s_new = satisfy(s, s_new, k)C = count(s_new)return C# 初始的C与LC = np.zeros([len(new_d), 2])for i in range(len(new_d)):C[i:] = np.array([new_d[i], d.count(new_d[i])])L = np.copy(C)L = limit(L)# 开始迭代k = 1while (np.max(L[:,-1]) > minsp):C = generate(L, k) # 由L产⽣CL = limit(C) # 由C产⽣Lk = k+1# 对最终结果去重复print((list(set([tuple(t) for t in L])))# 结果为 [(1.0, 2.0, 3.0, 2.0), (1.0, 2.0, 5.0, 2.0)]。

apriori关联规则算法
Apriori关联规则算法是在事务数据库中为挖掘关联规则而开发的一种经典的数据挖掘算法，又称频繁项集算法。

它通过计算支持度和置信度，从大量的数据里面找出一些隐藏的关联规则。

Apriori算法是一种基于事务数据库的算法。

事务数据库是存储着商品交易情况的数据库，每一行就代表一次购物行为，包括购买商品，商品的价格等信息。

Apriori算法的工作方式如下：
（1）首先计算商品的频繁项集及其支持度：Apriori算法先扫描事务数据库，计算出哪些商品是频繁项（出现次数超过预定义的最低支持度），以及每个商品的支持度。

（2）计算出所有可能的关联规则及其置信度：经过上步算法筛选后Apriori算法计算出所有可能的商品关联，同时计算每一个关联规则的置信度，置信度是用来衡量一个关联强度的度量指标。

（3）计算出具有最高置信度的频繁项集和关联规则：最后，Apriori算法会找出所有具有最高置信度的商品关联及频繁项集，这些关联规则和频繁项集，以及最高置信度，可以用来研究顾客购物习惯，制定营销策略等。

Apriori算法主要有两个超参数：
（1）最小支持度：频繁项集的最小支持度是频繁项集的筛选标准，表示一个商品项在所有事务中出现的次数大于或等于最小支持度时，才会被继续产生新的频繁项集。

（2）最小置信度：置信度是来衡量商品关联的效果，也是筛选出关联规则的标准。

当某个关联规则的置信度大于等于最小置信度时，这个关联规则才会被保存下来。

apriori 关联规则算法Apriori算法是一种常用的数据挖掘算法，主要用于挖掘多个数据项之间的关联规则。

它的核心思想是利用频繁项集产生其他频繁项集，最终得到所有的频繁项集和其相应的支持度和置信度。

1. 数据预处理首先，需要将原始数据进行预处理，将其转化为一个二维矩阵。

每行代表一条交易记录，每列代表一个数据项。

如果该交易记录包含该数据项，则值为1，否则为0。

2. 扫描数据集接下来，需要对数据集进行扫描，找出所有的频繁一项集。

频繁一项集指出现次数达到最小支持度的数据项。

最小支持度为一个参数，是由用户自行设定的。

需要注意的是，这里的支持度指的是某个数据项出现的次数占总交易记录数的比例。

3. 生成频繁二项集根据频繁一项集，可以生成候选频繁二项集。

这里的候选频繁二项集指包含两个数据项的频繁项集。

需要注意的是，生成候选项集的过程并不是简单的组合，而是要保证其中任何一个子集都是频繁的。

4. 计算支持度计算候选频繁二项集的支持度。

如果该频繁二项集的支持度大于最小支持度，则保留该频繁项集。

5. 迭代接下来，使用频繁二项集生成频繁三项集，再计算支持度，保留满足最小支持度的频繁三项集，以此类推，直到无法生成任何频繁项集为止。

6. 生成关联规则最后，需要根据频繁项集生成关联规则。

关联规则指数据项之间的关系，例如：“如果买了牛奶，就有可能购买面包”。

通过计算置信度来衡量关联规则的强度。

置信度指当某些数据项出现时，另一些数据项同时出现的概率。

由于存在许多关联规则，因此需要设置一个最小置信度的阈值来筛选强关联规则。

总之，Apriori算法是一种高效的关联规则挖掘算法。

通过不断迭代，可以得到所有的频繁项集和关联规则，从而挖掘出数据项之间的关系，为企业决策提供支持。

机器学习（⼋）—Apriori算法 摘要：本⽂对Apriori算法进⾏了简单介绍，并通过Python进⾏实现，进⽽结合UCI数据库中的肋形蘑菇数据集对算法进⾏验证。

“啤酒与尿布”的例⼦相信很多⼈都听说过吧，故事是这样的：在⼀家超市中，⼈们发现了⼀个特别有趣的现象，尿布与啤酒这两种风马⽜不相及的商品居然摆在⼀起。

但这⼀奇怪的举措居然使尿布和啤酒的销量⼤幅增加了。

这可不是⼀个笑话，⽽是⼀直被商家所津津乐道的发⽣在美国沃尔玛连锁超市的真实案例。

原来，美国的妇⼥通常在家照顾孩⼦，所以她们经常会嘱咐丈夫在下班回家的路上为孩⼦买尿布，⽽丈夫在买尿布的同时⼜会顺⼿购买⾃⼰爱喝的啤酒。

这个发现为商家带来了⼤量的利润，但是如何从浩如烟海却⼜杂乱⽆章的数据中，发现啤酒和尿布销售之间的联系呢?这种从⼤规模的数据中发现物品间隐含关系的⽅法被称为关联分析，也就是本⽂要主要研究的⼀种常⽤的分析⽅法，Apriori算法是最著名的关联规则挖掘算法之⼀。

下⾯就围绕该算法展开学习。

⼀关联分析 关联分析是⼀种在⼤规模数据集中寻找有趣关系的任务。

这些任务有两种形式：频繁项集和关联规则。

频繁项集是经常出现在⼀块的物品的集合；关联规则暗⽰的是两种物品之间可能存在很强的关系。

可以结合某家店的交易清单来说明这两个概念：交易号码商品0⾖奶，草莓1草莓，尿布，啤酒，辣椒酱2⾖奶，尿布，黄⽠，饼⼲3黄⽠，饼⼲，尿布，啤酒4黄⽠，啤酒，尿布，黄⽠频繁项集指的就是那些经常⼀起出现的物品集合，⽐如{啤酒，尿布，饼⼲}就是频繁项集中的⼀个例⼦，⽽根据上表也可以找到尿布->啤酒这样的关联规则。

⽽我们是要通过关联分析⼤规模数据从⽽发现数据之间存在的有趣关系，那么问题来了，什么样的关系是有趣的呢？⽽这个有趣⼜是怎么定义的呢？我们可以通过⽀持度（support）和可信度（置信度confidence）来定义。

⼀个项集的⽀持度指的是数据集中包含该项集记录所占的⽐例，上例中{⾖奶}的⽀持度是2/5,{啤酒，尿布}的⽀持度是3/5；可信度是针对于像{尿布}->{啤酒}这样的关联规则来定义的，定义为：⽀持度({尿布，葡萄酒})/⽀持度（尿布）。

1.1 Apriori算法基本思想
Apriori算法是发现关联规则领域的经典算法。

该算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度
的规则[5]。

具体做法就是：首先找出频繁1-项集，记为L
1；然后利用L
1
来产生
候选项集C
2，对C
2
中的项进行判定挖掘出L
2
，即频繁2-项集；不断如此循环下去
直到无法发现更多的频繁k-项集为止。

每挖掘一层L
k
就需要扫描整个数据库一遍。

1.2 Apriori算法描述
Apriori利用层次循环发现频繁项集，算法如下：
输入：交易数据库D，最小支持阈值min-sup
输出：D中的频繁项集L
本文提出了一种基于临时表的改进算法。

关联规则挖掘（二）：Apriori算法在数据挖掘领域，Apriori算法是挖掘关联规章的经典算法。

Apriori 算法采纳的是自底向上的办法，从1-频繁集开头，逐步找出高阶频繁集。

它的基本流程是：第一次扫描交易数据库D时，产生1-频繁集。

在此基础上经过衔接、修剪产生2-频繁集。

以此类推，直到无法产生更高阶的频繁集为止。

在第k次循环中，也就是产生k-频繁集的时候，首先产生k-候选集，k-候选集中每一个项集都是对两个惟独一个项不同的属于k-1频繁集的项集衔接产生的，k-候选集经过筛选后产生k-频繁集。

2 理论基础首先来看一个频繁集的性质。

定理：假如项目集X是频繁集，那么它的非空子集都是频繁集。

按照定理，已知一个k-频繁集的项集X，X的全部k-1阶子集都绝对是频繁集，也就绝对可以找到两个k-1频繁集的项集，它们惟独一项不同，且衔接后等于X。

这证实了通过衔接k-1频繁集产生的k-候选集笼罩了k-频繁集。

同时，假如k-候选集中的项集Y，包含有某个k-1阶子集不属于k-1频繁集，那么Y就不行能是频繁集，应当从候选集中裁剪掉。

Apriori算法就是利用了频繁集的这共性质。

3 算法伪代码这是Apriori算法的主函数，它的输入是交易数据库D和最小支持度，终于输出频繁集L。

函数第一步是扫描数据库产生1-频繁集，这只要统计每个项目浮现的次数就可以了。

然后依次产生2阶，3阶，……，k阶频繁集，k频繁集为空则算法停止。

apriori_gen函数的功能是按照k-1频繁集产生k-候选集。

接着扫描交易数据库里的每一笔交易，调用b函数产生候选集的子集，这个子集里的每一个项集都是此次交易的子集，并对子集里的每一个项集的计数增一。

最后统计候选集里全部项集的计数，将未达到最小支持度标准的项集删去，得到新的频繁集。

可以看到每一次循环，都必需遍历交易数据库；而且对于每一个交易，也要遍历候选集来增强计数，当候选集很大时这也是很大的开销。