找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

关联规则方法之apriori算法

admin 2019-8-11 17:02 106人围观 C++相关



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

关联规则挖掘可以让我们从数据集中发现项与项(item 与 item)之间的关系,它在我们的生活中有很多应用场景,“购物篮分析”就是一个常见的场景。

在今天的内容中,希望你能带着问题,和我一起来搞懂以下几个知识点:

  1. 搞懂关联规则中的几个重要概念:支持度、置信度、提升度;

  2. Apriori 算法的工作原理;

  3. 在实际工作中,我们该如何进行关联规则挖掘。

搞懂关联规则中的几个概念


我举一个超市购物的例子,下面是几名客户购买的商品列表:
编号购买的商品
1牛奶、面包、尿布
2可乐、面包、尿布、啤酒
3牛奶、尿布、啤酒、鸡蛋
4面包、牛奶、尿布、啤酒
5面包、牛奶、尿布、可乐

什么是支持度呢?


支持度是个百分比,它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高,代表这个组合出现的频率越大。

在这个例子中,我们能看到“牛奶”出现了 4 次,那么这 5笔订单中“牛奶”的支持度就是 4/5=0.8。

同样“牛奶 + 面包”出现了 3 次,那么这 5 笔订单中"牛奶 + 面包”的支持度就是 3/5=0.6。

什么是置信度呢?


它指的就是当你购买了商品 A,会有多大的概率购买商品 B,在上面这个例子中:

置信度(牛奶→啤酒)=2/4=0.5,代表如果你购买了牛奶,有多大的概率会购买啤酒?

置信度(啤酒→牛奶)=2/3=0.67,代表如果你购买了啤酒,有多大的概率会购买牛奶?

我们能看到,在 4 次购买了牛奶的情况下,有 2 次购买了啤酒,所以置信度 (牛奶→啤酒)=0.5,而在 3 次购买啤酒的情况下,有 2 次购买了牛奶,所以置信度(啤酒→牛奶)=0.67。

所以说置信度是个条件概念,就是说在 A 发生的情况下,B 发生的概率是多少。

        先上一下apriori的python实现的代码:

    #! -*- coding:utf-8 -*-#code write by guohaoimport itertoolsclassApriori(object):def__init__(self,min_sup=0.2,dataDic={}):self.data = dataDic #构建数据记录词典self.size = len(dataDic) #统计事务个数self.min_sup = min_sup #最小支持度阈值self.min_sup_val = min_sup * self.size #最小支持度计数deffind_frequent_1_itemsets(self): FreqDic = {} #用于统计物品的支持度计数for event inself.data:#event为每一条记录for item inself.data[event]: #item为项if item inFreqDic: FreqDic[item] += 1else: FreqDic[item] = 1 L1 = []for itemset inFreqDic:if FreqDic[itemset] >=self.min_sup_val:#过滤掉小于最小支持度计数的1-项集 L1.append([itemset])return L1defhas_infrequent_subset(self,c,L_last,k):#c为当前集合,L_last为上一个频繁项集的集合,k为当前频繁项集内的元素个数#该函数用于检查当前子集是否都为频繁项集 subsets = list(itertools.combinations(c,k-1))for each insubsets: each = list(each)if each notinL_last:return Truereturn Falsedefapriori_gen(self,L_last): #连接步实现 k = len(L_last[0]) + 1 Ck = []for itemset1 inL_last:for itemset2 inL_last: flag = 0for i in range(k-2):if itemset1[i] != itemset2[i]: #如果前k-2项中有一项不相等,则合并的项集必定不为频繁项集 flag = 1breakif flag == 1:continueif itemset1[k-2] < itemset2[k-2]: c = itemset1 + [itemset2[k-2]] #合成待定k项集else: continueifself.has_infrequent_subset(c,L_last,k): #判断是否为1-项集 continueelse: Ck.append(c)return Ckdefdo(self): L_last = self.find_frequent_1_itemsets() #找到频繁一项集 L = L_last i = 0while L_last != []: Ck = self.apriori_gen(L_last) #合并形成新的待定频繁项集 FreqDic = {} #项集的频数集合for event inself.data:for c inCk:if set(c) <= set(self.data[event]): #判断新合成的频繁集是否是事务记录的子集if tuple(c) inFreqDic: FreqDic[tuple(c)] += 1else: FreqDic[tuple(c)] = 1 Lk = []for c inFreqDic:if FreqDic[c] > self.min_sup_val:#判断新形成的待定频繁项集是否为为真正的频繁项集 Lk.append(list(c)) L_last = Lk L += Lkreturn L#*****************************Test*****************************print('======================Test===================')Data = {'T100':['I1','I2','I5'],'T200':['I2','I4'],'T300':['I2','I3'],'T400':['I1','I2','I4'],'T500':['I1','I3'],'T600':['I2','I3'],'T700':['I1','I3'],'T800':['I1','I2','I3','I5'],'T900':['I1','I2','I3']}a = Apriori(dataDic = Data)print(a.do())

         apriori算法的核心是连接步与剪切步,要想了解具体的算法思想以及连接步剪切步原理的话,可以看一下这篇文章

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

            这里解释一下代码中比较难理解的一段代码:

      for itemset1 in L_last:for itemset2 in L_last: flag = 0for i inrange(k-2):if itemset1[i] != itemset2[i]: #如果前k-2项中有一项不相等,则合并的项集必定不为频繁项集 flag = 1breakif flag == 1:continueif itemset1[k-2] < itemset2[k-2]: c = itemset1 + [itemset2[k-2]] #合成待定k项集else:continue

              对于项集L_last中包含k-1个项的任意两个频繁项集itemset1,itemset2,要使其合成为包含k个项的待定频繁项集,要完成这样的事,即就是给itemset1添加itemset2中其不存在的项;但为什么要在合成的时候保证itemset1和itemset2中的前k-2个项相同呢?

             我们这样来思考,合成的待定频繁项集Lk可以看做为Lk-1与L1连接而成,这里连接的时候保证连接时的L1的项要大于Lk-1的项,因为如果不大于的话,可能会出现这样的无序项集['I1','I2','I5','I3'],由于频繁项集的子集也是频繁项集,故而['I1','I2','I3']是频繁项集,故而其与L1连接可生成['I1','I2','I3','I5'],它与['I1','I2','I5','I3']是等价的,故而我们不妨将项集的格式都设为有序的,其并不影响我们的频繁项集的合成过程。新频繁项集Lk是建立在Lk-1上的,直接用Lk-1与L1连接有时在我们看来有点大材小用,因为对于一些L1中的元素,其与Lk-1连接后形成的Lk的子集,有可能不在Lk-1中,L1的范围有点大,为简化期间,我们可以直接让Lk-1中的项集与Lk-1中其他项集中该项集不具备的项连接,这样就简化了问题,在广度上降低算法的复杂度。

      转自:

      https://blog.csdn.net/bai_and_hao_1314/article/details/81981746


      ----------------------------------------------------------------------------------------------------------------------
      我们尊重原创,也注重分享,文章来源于微信公众号:Hadoop大数据与机器学习,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
      ----------------------------------------------------------------------------------------------------------------------

      鲜花

      握手

      雷人

      路过

      鸡蛋

      yafeilinux和他的朋友们微信公众号二维码

      微信公众号

      专注于Qt嵌入式Linux开发等。扫一扫立即关注。

      Qt开源社区官方QQ群二维码

      QQ交流群

      欢迎加入QQ群大家庭,一起讨论学习!

      我有话说......