温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Apriori算法如何进行关联分析

发布时间:2021-12-28 13:49:15 来源:亿速云 阅读:124 作者:柒染 栏目:大数据

这篇文章给大家介绍Apriori算法如何进行关联分析,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

从大规模数据集中寻找物品间的隐 含关系被称作关联分析(associationanalysis)或者关联规则学习(associationrulelearning)

1、Apriori算法


(1)关联分析


      关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。频繁项集(frequentitemsets)是经常出现在一块的物品的集合,关联规则 (associationrules)暗示两种物品之间可能存在很强的关系

样本举例:

交易号码商品
0豆奶、莴苣
1莴苣,尿布,葡萄酒,甜菜
2豆奶,尿布,葡萄酒,橙汁
3莴苣,豆奶,尿布,葡萄酒
4莴苣,豆奶,尿布,橙汁

       一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例,{豆奶)的支持度为4/5。而在5条交易记录中有3条包含{豆奶,尿布},因此{豆奶,尿布}的支持度为3/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。

      可信度或置信度(confidence)是针对一条诸如{尿布}->{葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布,葡萄酒})/支持度({尿布})”。从上述表格可以看到,由于{尿布,葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布—>葡萄酒”的可信度为3/4=0.75。 这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。

      非频繁项集定义:就是项目里面没有这个商品,然后就一定不会有此商品的频繁项集合。也就是没有小项目商品,就不会有包含它的集合。

       Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输人参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉。然后,对剩下来的集合进行组合以生成包含两个元素的项集。接下来,再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。

伪代码如下:
对数据集中的每条交易记录tran
对每个候选项集can:
    检查一下can是否是tran的子集:
        如果是,则增加can的计数值
对每个候遙项集:
如果其支持度不低于最小值,则保留该项集
返回所有频繁项集列表

(1)构建第一个候选项集集合

def createC1(dataSet):
   C1 = []
   for transaction in dataSet:
       for item in transaction:
           if not [item] in C1:
               C1.append([item])
               
   C1.sort()
   return list(map(frozenset, C1))

(2)构建大于最小支持度的频繁项集

def scanD(D, Ck, minSupport):
   ssCnt = {}
   for tid in D:
       for can in Ck:
           if can.issubset(tid):
               if can not in ssCnt:
                   ssCnt[can]=1
               else: ssCnt[can] += 1
   numItems = float(len(D))
   retList = []
   supportData = {}
   for key in ssCnt:
       support = ssCnt[key]/numItems
       if support >= minSupport:
           retList.insert(0,key)
       supportData[key] = support
   return retList, supportData#返回符合支持度的子项,以及所有项目计算的支持度

当集合中项的个数大于0时
    构建一个k个项组成的候选项集的列表
    检查数据以确认每个项集都是频繁的
    保留频繁项集并构建k+1项组成的候选项集的列表

#构建多项的频繁项目集
def aprioriGen(Lk, k): #creates Ck
   retList = []
   lenLk = len(Lk)
   for i in range(lenLk):
       for j in range(i+1, lenLk):
           L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
           L1.sort(); L2.sort()
           if L1==L2: #if first k-2 elements are equal
               retList.append(Lk[i] | Lk[j]) #set union
   return retList
#整体Apriori函数代码,得到所有频繁项集和符合最小支持度要求的集合
def apriori(dataSet, minSupport = 0.5):
   C1 = createC1(dataSet)
   D = list(map(set, dataSet))
   L1, supportData = scanD(D, C1, minSupport)
   L = [L1]
   k = 2
   while (len(L[k-2]) > 0):
       Ck = aprioriGen(L[k-2], k)
       Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk
       supportData.update(supK)#update() 函数把字典dict2的键/值对更新到dict里
       L.append(Lk)
       k += 1
   return L, supportData

(2) 从频繁项集中挖掘关联规则

      对于关联规则,我们也有类似的量化方法,这种量化指标称为可信度。一条规则P—>H的可信度定义为Support(P|H)/support(P),在python中操作符丨表示集合的并操作,而数学上集合并的符号是U。P|H是指所有出现在集合P或者集合H中的元素。前面一节已经计算了所有频繁项集支持度。现在想获得可信度,所需要做的只是取出那些支持度值做一次除法运算。

      如果某条规则并不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求

def generateRules(L, supportData, minConf=0.7):  #supportData is a dict coming from scanD
   bigRuleList = []
   for i in range(1, len(L)):#only get the sets with two or more items
       for freqSet in L[i]:
           print(L[i],freqSet)
           H1 = [frozenset([item]) for item in freqSet]
           print("i",i,"H1",H1)
           if (i > 1):
               rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
           else:
               calcConf(freqSet, H1, supportData, bigRuleList, minConf)
   return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
   prunedH = [] #create new list to return
   for conseq in H:
       conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence
       if conf >= minConf:
           print(freqSet-conseq,'-->',conseq,'conf:',conf)
           brl.append((freqSet-conseq, conseq, conf))
           prunedH.append(conseq)
   return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
   print("freqSet:",freqSet)
   m = len(H[0])
   if (len(freqSet) > (m + 1)): #try further merging
       Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates
       print("Hmp1:",Hmp1)
       Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
       print("Hmp1:",Hmp1)
       if (len(Hmp1) > 1):    #need at least two sets to merge
           print("len(Hmp1):",len(Hmp1))
           rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
           print("__")


关于Apriori算法如何进行关联分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI