全网自媒体平台,网站推广和优化教程,wordpress 酒店中文主题,网站域名空间管理使用Apriori进行关联分析#xff08;一#xff09;大型超市有海量交易数据#xff0c;我们可以通过聚类算法寻找购买相似物品的人群#xff0c;从而为特定人群提供更具个性化的服务。但是对于超市来讲#xff0c;更有价值的是如何找出商品的隐藏关联#xff0c;从而打包促…使用Apriori进行关联分析一大型超市有海量交易数据我们可以通过聚类算法寻找购买相似物品的人群从而为特定人群提供更具个性化的服务。但是对于超市来讲更有价值的是如何找出商品的隐藏关联从而打包促销以增加营业收入。其中最经典的案例就是关于尿不湿和啤酒的故事。怎样在繁杂的数据中寻找到数据之间的隐藏关系当然可以使用穷举法但代价高昂所以需要使用更加智能的方法在合理时间内找到答案。Apriori就是其中的一种关联分析算法。基本概念 关联分析是一种在大规模数据集中寻找有趣关系的非监督学习算法。这些关系可以有两种形式频繁项集或者关联规则。频繁项集frequent item sets)是经常出现在一块的物品的集合关联规则(association rules)暗示两种物品之间可能存在很强的关系。 下图是一个乒乓球店的交易记录〇表示顾客购买了商品。其中{底板,胶皮,浇水}就是一个频繁项集从中可以找到底板-胶皮这样的关联规则支持度 怎样有效定义频繁和关联其中最重要的两个概念是支持度和置信度。 支持度(support)从字面上理解就是支持的程度一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。上图中{底板}的支持度(5/6) * 100%。 这个概念其实经常在现实生活中出现翻译成支持率似乎更好理解典型的例子就是投票比如英国脱欧的支持率为51.89%。 用数学去解释就是设W 中有s的事务同时支持物品集A和Bs称为{AB}的支持度即: 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本身。另外图中从上往下的第一个集合是Ф表示空集或不包含任何物品的集合。物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。 前面说过我们的目标是找到经常在一起购买的物品集合。我们使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。如何对一个给定的集合比如{03}来计算其支持度我们遍历毎条记录并检查该记录包含0和3如果记录确实同时包含这两项那么就增加总计数值。在扫描完所有数据之后使用统计得到的总数除以总的交易记录数就可以得到支持度。上述过程和结果只是针对单个集合{0,3}。要获得每种可能集合的支持度就需要多次重复上述过程。我们可以数一下上图中的集合数目会发现即使对于仅有4种物品的集合也需要遍历数据15次。而随着物品数目的增加遍历次数会急剧增长。对于包含— 物品的数据集共有2N-1种项集组合。事实上出售10000或更多种物品的商店并不少见。即使只出售100种商品的商店也会有1.26×1030种可能的项集组合。对于现代的计算机而言需要很长的时间才能完成运算。 为了降低所需的计算时间研究人员发现一种所谓的Apriori原理。Apriori原理可以帮我们减少可能感兴趣的项集。Apriori原理是说如果某个项集是频繁的那么它的所有子集也是频繁的。上图给出的例子这意味着如果{0,1}是频繁的那么{0}、{1}也一定是频繁的。这个原理直观上并没有什么帮助但是如果反过来看就有用了也就是说如果一个项集是非频繁集那么它的所有超集也是非频繁的如下所示 上图中已知阴影项集{23}是非频繁的。利用这个知识我们就知道项集{0,2,3} {1,2,3}以及{0,1,2,3}也是非频繁的。这也就是说一旦计算出了{2,3}的支持度知道它是非频繁的之后就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长从而在合理时间内计算出频繁项集。Apriori算法过程 关联分析的目标包括两项发现频繁项集和发现关联规则。首先需要找到频繁项集然后才能获得关联规则。Apriori算法过程 发现频繁项集的过程如上图所示由数据集生成候选项集C11表示每个候选项仅有一个数据项再由C1通过支持度过滤生成频繁项集L11表示每个频繁项仅有一个数据项。将L1的数据项两两拼接成C2。从候选项集C2开始通过支持度过滤生成L2。L2根据Apriori原理拼接成候选项集C3C3通过支持度过滤生成L3……直到Lk中仅有一个或没有数据项为止。 下面是一个超市的交易记录 Apriori算法发现频繁项集的过程如下 具体代码 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项集C14 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, minSupport0.2) 控制台信息 代码中的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 | L2if L1_2 not in Ck:Ck.append(L1 | L2)return Ck发现关联规则 下篇继续。
