lovebet体育官网行使Apriori进行关联分析(一)使用Apriori进行关联分析(二)

  大型超市有雅量交易数据,我们得经聚类算法寻找购买相似物品的人流,从而为特定人群提供更富有个性化的劳务。但是于超市来讲,更发出价之是安寻找有商品的藏身关联,从而打包促销,以追加营业收入。其中最经典的案例就是是有关尿不沾和啤酒的故事。怎样在纷纷扬扬的数码被摸索到多少里的隐身关系?当然可以行使穷举法,但代价高昂,所以用以越来越智能的章程以情理之中时间外找到答案。Apriori就是里面的同样栽关系分析算法。

  书接上文(运用Apriori进行关联分析(一)),介绍如何扒关联规则。

基本概念

  关联分析是一模一样种在广泛数据汇总找有趣关系之莫监督上算法。这些关乎可起个别种形式:频繁项集或者关联规则。频繁项集(frequent
item sets)是经常出现在平等块的品的汇聚,关联规则(association
rules)暗示两栽物品之间可能存在好强的涉及。

  下图是一个乒乓球店的贸易记录,〇表示顾客购买了货。其中{底板,胶皮,浇水}就是一个屡屡项集;从中可以找到底板->胶皮这样的关系规则:

lovebet体育官网 1

察觉涉及规则

  我们的目标是由此反复项集挖掘到隐蔽的涉嫌规则。

  所谓关联规则,指经某元素集推导出另一个要素集。比如来一个屡屡项集{底板,胶皮,胶水},那么一个或者的关联规则是{底板,胶皮}→{胶水},即如果客户购买了底板与胶皮,则该客户有较充分概率购买胶水。这个数项集可以推导出6单涉及规则:

  {底板,胶水}→{胶皮},

  {底板,胶皮}→{胶水},

  {胶皮,胶水}→{底板},

  {底板}→{胶水, 胶皮},

  {胶水}→{底板, 胶皮},

  {胶皮}→{底板, 胶水}

  箭头左边的集称为“前件”,右边集合称为“后件”,根据前件会生出比较生概率推导出后件,这个概率就之前提到的购信度。需要专注的凡,如果A→B成立,B→A不必然立。

  一个存有N个元素的高频项集,共有M个可能的涉嫌规则:

lovebet体育官网 2

  下图是一个再三4起集的有涉规则网格示意图, lovebet体育官网 3

lovebet体育官网 4

  上图备受深色区域代表没有而信度规则,如果012→3凡是同等长长的没有可信度规则,则拥有其他3吧后件的条条框框都是不及可是信度。这要由可信度的定义去解,Confidence(012→3)
= P(3|0,1,2),Confidence(01→23)=P(2,3|0,1),P(3|0,1,2) >=
P(2,3|0,1)。由此可以针对涉嫌规则做剪枝处理。

  还是以上篇的百货商店交易数据吧例,我们发现了如下的高频项集:

lovebet体育官网 5

  对于寻找关联规则吧,频繁1起集L1不曾因此处,因为L1中的每个集合仅发生一个数据项,至少有三三两两独数据项才会生成A→B这样的关联规则。

  当尽小置信度取0.5时,L2最终能开有9久提到规则:

lovebet体育官网 6

  从数3件集开头,挖掘的经过尽管较复杂。

lovebet体育官网 7

  假设有一个屡4桩集(这是造的,文中的多少未能够生成L4),其挖掘过程如下:

lovebet体育官网 8

  因为写被的代码假设购买商品是发各个的,所以在扭转3继件时,{P2,P4}和{P3,P4}并无可知挺成{P2,P23,P4},如果想去丢假设,需要使用上篇被改善后底代码。

  发掘关联规则的代码如下:

 1 #生成关联规则
 2 #L: 频繁项集列表
 3 #supportData: 包含频繁项集支持数据的字典
 4 #minConf 最小置信度
 5 def generateRules(L, supportData, minConf=0.7):
 6     #包含置信度的规则列表
 7     bigRuleList = []
 8     #从频繁二项集开始遍历
 9     for i in range(1, len(L)):
10         for freqSet in L[i]:
11             H1 = [frozenset([item]) for item in freqSet]
12             if (i > 1):
13                 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
14             else:
15                 calcConf(freqSet, H1, supportData, bigRuleList, minConf)
16     return bigRuleList
17 
18 
19 # 计算是否满足最小可信度
20 def calcConf(freqSet, H, supportData, brl, minConf=0.7):
21     prunedH = []
22     #用每个conseq作为后件
23     for conseq in H:
24         # 计算置信度
25         conf = supportData[freqSet] / supportData[freqSet - conseq]
26         if conf >= minConf:
27             print(freqSet - conseq, '-->', conseq, 'conf:', conf)
28             # 元组中的三个元素:前件、后件、置信度
29             brl.append((freqSet - conseq, conseq, conf))
30             prunedH.append(conseq)
31 
32     #返回后件列表
33     return prunedH
34 
35 
36 # 对规则进行评估
37 def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
38     m = len(H[0])
39     if (len(freqSet) > (m + 1)):
40         Hmp1 = aprioriGen(H, m + 1)
41        # print(1,H, Hmp1)
42         Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
43         if (len(Hmp1) > 0):
44             rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

 

  由是可以看来,apriori算法需要经常扫描全表,效率并无算是大。

 


  参考文献:《机器上实战》

  作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文为习、研究以及享用为主,如需要转载,请联系自己,标明作者与出处,非商业用途! 

 

支持度

  怎样有效定义频繁与事关?其中最要害的简单只概念是支持度和置信度。

  支持过(support)从字面上懂就是是支撑之品位,一个项集的支持度(support)被定义也数汇总包含该项集的记录所占的百分比。上图备受{底板}的支持度=(5/6)
* 100%。

  这个概念实际上经常于现实生活中冒出,翻译成支持率似乎更好掌握,典型的事例就是投票,比如英国脱欧的支持率也51.89%。

  用数学去解释就是是,设W
中产生s%之作业同时支持物品集A和B,s%称作{A,B}的支持度,即:

  support({A,B}) = num(A∪B) / W =
P(A∩B)

  num(A∪B)表示含有物品集{A,B}的事务集的个数,不是数学中之并集。

置信度

  置信度(confidence)揭示了A出现时B是否定出现,如果起,则产出的几率是大半深。如果A->B的进信度是100%,则说明A出现常常B一定会冒出(返回来不一定)。上图被底板共出现5浅,其中4浅以请了人力车,底板->胶皮的采办信度是80%。

  用公式表示是,物品A->B的买进信度=物品{A,B}的支撑度
/ 物品{A}的支持度:

  Confidence(A->B) = support({A,B})
/ support({A}) = P(B|A)

Apriori原理

  本节摘自《机器上实战》

  假设我们以经一下商品品种并无多的百货公司,我们针对那些常在齐给市的货物非常感谢兴趣。我们惟有生4栽商品:商品0,商品1,商品2和商品3。那么有或给联合进之货色组合都有什么样?这些商品组合或就发生一致种植商品,比如商品0,也或包括个别种、三栽要具有四栽商品。我们连无关心某人购买了区区码商品0以及四件商品2的情况,我们只是关心他置了一如既往种植要多货。

  下图显示了物品之间所有可能的组合。为了吃该图再次爱掌握,图被以物品的编号0来取代物品0本身。另外,图备受于高达通往生之第一独集聚是Ф,表示空集或不含有其他物品的集合。物品集合之间的连线表明两个或又多聚集好结合形成一个重充分之汇聚。

lovebet体育官网 9

  前面说了,我们的目标是找到时以一道进之物料集合。我们采用集合的支持过来度量其现出的频率。一个集合的支持度是靠有微微比例之贸易记录包含该集。如何对一个加的集,比如{0,3},来算其支持度?我们遍历毎条记录并检查该记录包含0和3,如果记录确实以寓这有限桩,那么尽管添总计数值。在扫描了所有数据以后,使用统计得到的总额除以总的交易记录数,就得落支持度。上述过程及结果但是本着单个集合{0,3}。要获取每种可能集合的支撑过就需要多次重复上述过程。我们得以屡屡一下及图中之汇数目,会意识就是对于只有发生4栽物品的聚众,也待遍历数据15糟。而就物品数量的充实遍历次数会痛增长。对于含—
物品的数据集共有2N-1栽项集组合。事实上,出售10000或者更强品的小卖部并无掉见。即使只有出售100种植商品的铺面也会发生1.26×1030栽或的项集组合。对于当代的微机而言,需要好丰富之流年才会完成运算。

  为了降低所需要的测算时,研究人口发现相同栽所谓的Apriori原理。Apriori原理可以协助咱减或感兴趣的项集。Apriori原理是说如有项集是反复的,那么它的享有子集也是累之。上图给来底例证,这意味着如果{0,1}是几度的,那么{0}、{1}也必是多次之。这个规律直观上连无什么帮助,但是要转看便来因此了,也就是说要一个项集是非频繁集,那么她的兼具超集也是不频繁之,如下所示:

lovebet体育官网 10

  上图备受,已知道阴影项集{2,3}是无频繁的。利用这个文化,我们就是掌握项集{0,2,3}
,{1,2,3}以及{0,1,2,3}也是匪频繁的。这吗算得,一旦计算产生了{2,3}的支持度,知道她是休频繁的之后,就未待再计{0,2,3}、{1,2,3}和{0,1,2,3}的支持度,因为咱们懂得这些聚集不会见满足我们的求。使用该原理就是可以避免项集数目的指数提高,从而以客观时间外计算出累累项集。

Apriori算法过程

  关联分析的靶子包括个别宗:发现数项集和发现涉及规则。首先要找到频繁项集,然后才会取关联规则。

Apriori算法过程

lovebet体育官网 11

  发现数项集的过程要齐图所示:

  1. 出于数集生成候选项集C1(1代表每个候选项仅来一个数项);再由C1通过支撑过滤,生成频繁项集L1(1象征每个频繁项就发生一个数据项)。
  2. 以L1的数量项两简单合接成C2。
  3. 自打候选项集C2初始,通过支撑过滤生成L2。L2根据Apriori原理拼接成候选项集C3;C3经支持度滤生成L3……直到Lk中单来一个要尚未数量项为止。

  下面是一个杂货店的交易记录:

lovebet体育官网 12

  Apriori算法发现数项集的经过如下:

lovebet体育官网 13  具体代码:

 1 def loadDataSet():
 2     return [[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]
 3 #1.构建候选1项集C1
 4 def createC1(dataSet):
 5     C1 = []
 6     for transaction in dataSet:
 7         for item in transaction:
 8             if not [item] in C1:
 9                 C1.append([item])
10 
11     C1.sort()
12     return list(map(frozenset, C1))
13 
14 #将候选集Ck转换为频繁项集Lk
15 #D:原始数据集
16 #Cn: 候选集项Ck
17 #minSupport:支持度的最小值
18 def scanD(D, Ck, minSupport):
19     #候选集计数
20     ssCnt = {}
21     for tid in D:
22         for can in Ck:
23             if can.issubset(tid):
24                 if can not in ssCnt.keys(): ssCnt[can] = 1
25                 else: ssCnt[can] += 1
26 
27     numItems = float(len(D))
28     Lk= []     # 候选集项Cn生成的频繁项集Lk
29     supportData = {}    #候选集项Cn的支持度字典
30     #计算候选项集的支持度, supportData key:候选项, value:支持度
31     for key in ssCnt:
32         support = ssCnt[key] / numItems
33         if support >= minSupport:
34             Lk.append(key)
35         supportData[key] = support
36     return Lk, supportData
37 
38 #连接操作,将频繁Lk-1项集通过拼接转换为候选k项集
39 def aprioriGen(Lk_1, k):
40     Ck = []
41     lenLk = len(Lk_1)
42     for i in range(lenLk):
43         L1 = list(Lk_1[i])[:k - 2]
44         L1.sort()
45         for j in range(i + 1, lenLk):
46             #前k-2个项相同时,将两个集合合并
47             L2 = list(Lk_1[j])[:k - 2]
48             L2.sort()
49             if L1 == L2:
50                 Ck.append(Lk_1[i] | Lk_1[j])
51 
52     return Ck
53 
54 def apriori(dataSet, minSupport = 0.5):
55     C1 = createC1(dataSet)
56     L1, supportData = scanD(dataSet, C1, minSupport)
57     L = [L1]
58     k = 2
59     while (len(L[k-2]) > 0):
60         Lk_1 = L[k-2]
61         Ck = aprioriGen(Lk_1, k)
62         print("ck:",Ck)
63         Lk, supK = scanD(dataSet, Ck, minSupport)
64         supportData.update(supK)
65         print("lk:", Lk)
66         L.append(Lk)
67         k += 1
68 
69     return L, supportData
70 
71 dataset = loadDataSet()
72 L, supportData = apriori(dataset, minSupport=0.2)

   控制高信息:

lovebet体育官网 14

  代码中之scanD方法而发一下窜:

 1 def scanD(D, Ck, minSupport):
 2     #候选集计数
 3     ssCnt = {}
 4     #数据集过滤
 5     D2 = [item for item in D if len(item) >= len(Ck[0])]
 6     for tid in D2:
 7         for can in Ck:
 8             if can.issubset(tid):
 9                 if can not in ssCnt.keys(): ssCnt[can] = 1
10                 else: ssCnt[can] += 1
11     ……
12 
13     return Lk, supportData

   需要专注的凡,在上述代码的aprioriGen方法吃,假定购买商品是出各个的,可以由此反复2项集{P1,P2},{P1,P3}推导出数项{P1,P2,P3},但是不能够通过反复2项集{P3,P4},{P1,P3}推导出累累项{P1,P3,P4}。如果错过丢假设,则需修改aprioriGen的代码:

#将频繁Lk-1项集转换为候选k项集
def aprioriGen(Lk_1, k):
    Ck = []
    lenLk = len(Lk_1)
    for i in range(lenLk):
        L1 = Lk_1[i]
        for j in range(i + 1, lenLk):
            L2 = Lk_1[j]
            if len(L1 & L2) == k - 2:
                L1_2 = L1 | L2
                if L1_2 not in Ck:
                    Ck.append(L1 | L2)
    return Ck

意识涉嫌规则

   下篇继续。

 


  参考文献:《机器上实战》

 
作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文为攻、研究暨享受为主,如用转载,请联系我,标明作者和出处,非商业用途!