HTML5网站建设案例,chinacd.wordpress变装,珠海网站建站模板,网站建设客户调查需求表转自穆晨 阅读目录 前言关联分析领域的一些概念Apriori算法基本原理频繁项集检索实现思路与实现代码关联规则学习实现思路与实现代码小结回到顶部前言 想必大家都听过数据挖掘领域那个经典的故事 - 啤酒与尿布 的故事。 那么#xff0c;具体是怎么从海量销售信息中… 转自穆晨 阅读目录 前言关联分析领域的一些概念Apriori算法基本原理频繁项集检索实现思路与实现代码关联规则学习实现思路与实现代码小结 回到顶部 前言 想必大家都听过数据挖掘领域那个经典的故事 - 啤酒与尿布 的故事。 那么具体是怎么从海量销售信息中挖掘出啤酒和尿布之间的关系呢 这就是关联分析所要完成的任务了。 本文将讲解关联分析领域中最为经典的Apriori算法并给出具体的代码实现。 回到顶部 关联分析领域的一些概念 1. 频繁项集: 数据集中经常出现在一起的物品的集合。例如 啤酒和尿布 2. 关联规则: 指两个物品集之间可能存在很强的关系。例如 {啤酒} - {尿布} 就是一条关联规则。 3. 支持度: 数据集中出现了某个物品集的数据项占总数据项的比重某些地方也解释为次数。 4. 可信度: 这个概念是针对某条关联规则而定的。它是指两个物品集的支持度和其中某个物品集的支持度之比如 支持度{啤酒尿布} / 支持度{尿布}。 因此用这些属于来解释啤酒与尿布的故事那就是{啤酒尿布}是一个频繁项集{啤酒} - {尿布} 就是一条关联规则顾客买尿布的同时买啤酒的可能性为 支持度{啤酒尿布} / 支持度{尿布}。 那么对海量的数据假如要得到支持度大于0.8的所有频繁项集该怎么做 如果用蛮力法一个个统计是根本不现实的那样计算量实在太大。 本文将要介绍的Apriori关联分析算法意义就在于能够大幅度减少这种情况的计算量并从频繁项集中高效检索出关联规则从而大大减少关联规则学习所需要消耗的计算量。 回到顶部 Apriori算法基本原理 如果{0,1}是频繁项集那么{0}和{1}也都是频繁项集。 这显然是正确的命题。 其逆否命题 - ”如果{0}和{1}不都是频繁项集那么{0,1}不是频繁项集 自然也是正确的。- 这就是 Apriori 算法的核心思想之一。 这样一旦发现某个集合不是频繁项集那么它的所有超集也都不是频繁项集就不用浪费功夫去对它们进行检索了。 检索出频繁项集之后接下来检索出所有合乎要求的关联规则。 如果某条规则不满足最小可信度要求那么该规则的所有子集也不会满足。 - 这是 Apriori 算法的核心思想的另一部分。 PS这里务必思考清楚规则是怎么划分的什么叫某个规则的子集。 这样和上一步同理也能高效的从频繁项集中检索出关联规则了。 具体实现将分为频繁集检索和关联规则学习两个部分进行讲解。 回到顶部 频繁项集检索实现思路与实现代码 一种经典的实现方法是 分级法 算法框架是在两个大的步骤 - 筛选/过滤之间不断迭代直到所有情况分析完毕。 每次筛选的结果都要指定元素个数的情况因此所谓分级也就是依次讨论指定元素个数情况的项集。 在筛选之后就是过滤。 过滤有两层意义一个是项集必须在数据集中存在。这是第一层过滤还有一层过滤是指支持度过滤。只有满足支持度要求的项集才能保存下来。 过滤之后基于过滤集再进行筛选每次筛选的元素个数都比上一次筛选的元素个数多一个。 然后继续过滤。如此反复直到最后一次筛选过滤完成。 伪代码实现 1 当集合中项的个数大于0时:
2 构建一个 k 个项组成的候选项集的列表
3 检查数据以确认每个项集都是频繁的
4 保留频繁项集并构建 k1 项组成的候选项集列表 其中检查每个项集是否频繁部分的伪代码 1 对数据集中的每条交易记录:
2 对每个候选集元素:
3 检查是否为数据集元素是才保留。
4 对每个数据集
5 如果支持度达到要求才保留
6 返回过滤后的频繁项集 - 也即过滤集 Python实现及测试代码 1 def loadDataSet():2 返回测试数据3 4 return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]5 6 #7 # 输入:8 # dataSet: 数据集9 # 输出:10 # map(frozenset, C1): 候选集11 #12 def createC1(dataSet):13 创建候选集14 15 C1 []16 for transaction in dataSet:17 for item in transaction:18 if not [item] in C1:19 C1.append([item])20 21 C1.sort()22 23 # 返回的集合元素都是frozenset类型 - 因为以后要用来做键。24 return map(frozenset, C1)25 26 #27 # 输入:28 # D: 数据集 (set格式)29 # Ck: 候选集30 # minSupport: 最小支持度31 # 输出:32 # retList: 过滤集33 # supportData: 支持集(挖掘关联规则时使用)34 #35 def scanD(D, Ck, minSupport):36 由候选集得到过滤集37 38 # 统计候选元素出现的次数39 ssCnt {}40 for tid in D:41 for can in Ck:42 if can.issubset(tid):43 if not ssCnt.has_key(can): ssCnt[can]144 else: ssCnt[can] 145 46 # 构建过滤集和支持集47 numItems float(len(D))48 retList []49 supportData {}50 for key in ssCnt:51 support ssCnt[key]/numItems52 if support minSupport:53 retList.insert(0,key)54 supportData[key] support55 56 return retList, supportData57 58 #59 # 输入:60 # Lk: 过滤集61 # k: 当前项集元素个数62 # 输出:63 # retList: 候选集64 #65 def aprioriGen(Lk, k):66 由过滤集得到候选集67 68 # 重组过滤集得到新的候选集。69 retList []70 lenLk len(Lk)71 for i in range(lenLk):72 for j in range(i1, lenLk): 73 # 留意下重组技巧74 L1 list(Lk[i])[:k-2]; L2 list(Lk[j])[:k-2]75 L1.sort(); 76 L2.sort()77 if L1L2:78 retList.append(Lk[i] | Lk[j])79 80 return retList81 82 #83 # 输入:84 # dataSet: 数据集85 # minSupport: 最小支持度86 # 输出:87 # L: 频繁集88 # supportData: 支持集(挖掘关联规则时使用)89 #90 def apriori(dataSet, minSupport 0.5):91 求频繁项集及其对应支持度92 93 C1 createC1(dataSet)94 D map(set, dataSet)95 L1, supportData scanD(D, C1, minSupport)96 L [L1]97 k 298 while (len(L[k-2]) 0):99 Ck aprioriGen(L[k-2], k)
100 Lk, supK scanD(D, Ck, minSupport)
101 supportData.update(supK)
102 L.append(Lk)
103 k 1
104
105 return L, supportData
106
107 def main():
108 Apriori频繁集检索
109
110 L, s apriori (loadDataSet())
111
112 print L
113 print s 测试结果 回到顶部 关联规则学习实现思路与实现代码 上一部分的工作是从数据集中检索出频繁集而这一部分是根据频繁集学习关联规则。 上一部分的工作是通过筛选集中的元素个数进行分级而这一部分是针对规则右部的元素个数进行分级。 另外还要注意只用检索单个频繁集之内的关联规则就可以了。 实现代码 1 #2 # 输入:3 # L: 频繁集4 # supportData: 支持集5 # minConf: 最小可信度6 # 输出:7 # bigRuleList: 规则集8 #9 def generateRules(L, supportData, minConf0.7):
10 从某个频繁集中学习关联规则
11
12 bigRuleList []
13 for i in range(1, len(L)):
14 for freqSet in L[i]:
15 H1 [frozenset([item]) for item in freqSet]
16 if (i 1):
17 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
18 else:
19 calcConf(freqSet, H1, supportData, bigRuleList, minConf)
20 return bigRuleList
21
22 #
23 # 输入:
24 # L: 频繁集
25 # supportData: 支持集
26 # minConf: 最小可信度
27 # 输出:
28 # bigRuleList: 规则集
29 #
30 def calcConf(freqSet, H, supportData, brl, minConf0.7):
31 可信度过滤
32
33 prunedH []
34 for conseq in H:
35 conf supportData[freqSet]/supportData[freqSet-conseq]
36 if conf minConf:
37 brl.append((freqSet-conseq, conseq, conf))
38 prunedH.append(conseq)
39
40 return prunedH
41
42 def rulesFromConseq(freqSet, H, supportData, brl, minConf0.7):
43 从某个频繁项集中学习关联规则
44
45 # 本次学习的规则右部中的元素个数
46 m len(H[0])
47 if (len(freqSet) (m 1)):
48 # 重组规则右部
49 Hmp1 aprioriGen(H, m1)
50 # 规则学习
51 Hmp1 calcConf(freqSet, Hmp1, supportData, brl, minConf)
52 if (len(Hmp1) 1):
53 # 递归学习函数
54 rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
55
56 def main():
57 关联规则学习
58
59 L, s apriori (loadDataSet())
60
61 rules generateRules(L, s)
62 print rules 测试结果 测试数据为: [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]。 结果的意思也就是说1-35-22-5 的概率为 1。 显然这是和预计相吻合的。 回到顶部 小结 1. Apriori关联算法在网络购物网站中用的非常多可以基于此算法搭建商品推荐系统。 2. 但Apriori算法也有一个缺点那就是频繁集的检索速度还是不够快因为每级都要重新检索一遍候选集(虽然候选集越来越小)。 3. 针对 2 中的问题下篇文章将介绍一个更为强大的发现频繁集的算法 - FP-growth。(PS但它不能用来发现关联规则)转载于:https://www.cnblogs.com/fujian-code/p/7637728.html
