从大规模数据集中寻找物品间的隐含关系被称作关联分析或关联规则学习。过程分为两步：1.提取频繁项集。2.从频繁项集中抽取出关联规则。
频繁项集是指经常出现在一块的物品的集合。
关联规则是暗示两种物品之间可能存在很强的关系。
一个项集的支持度被定义为数据集中包含该项集的记录所占的比例，用来表示项集的频繁程度。支持度定义在项集上。
可信度或置信度是针对一条诸如{尿布}->{葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布，葡萄酒})/支持度({尿布})”。
寻找频繁项集
Apriori原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。反过来，如果一个项集是非频繁项集，那么它的所有超集也是非频繁的。
Apriori算法是发现频繁项集的方法。该算法首先生成所有单个物品的项集列表，接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度的项集会被去除掉。然后对剩下来的集合进行组合以生成包含两个元素的项集。接下来重新扫描交易记录，去掉不满足最小支持度的项集，该过程重复进行直到所有项集都被去掉。
Apriori伪代码
当列表中项的个数大于0时：
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表
从频繁项集中挖掘关联规则
当可信度大于最小可信度时，可以认为是含有关联规则的。可以观察到，如果某条规则不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。
可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试，接下来合并，通过合并所有剩余规则右部来创建新的规则列表，其中规则右部包含两个元素，以此类推。
每个频繁项集：
while(len(L)>1)
(k规则列表)
满足最小置信度
创建k+1规则
整体代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
import numpy as np
def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dateSet):
c1 = []
for line in dateSet:
for item in line:
if not [item] in c1:
c1.append([item])
c1.sort()
return list(map(frozenset,c1))
def scanData(data,ck,minSupport):#寻找满足最小支持度的项集
ssCnt = {}
for tid in data:
for can in ck:
if can.issubset(tid):
if can not in ssCnt.keys():
ssCnt[can] = 0
ssCnt[can] += 1
numItems = len(data)
retList = []
supportData = {}
for key in ssCnt.keys():
support = ssCnt[key]/numItems
if support >= minSupport:
retList.append(key)
supportData[key] = support
return retList,supportData
def aprioriGen(Lk,k): #根据k-1项集生成k项集
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:
retList.append(Lk[i] | Lk[j])
return retList
def apriori(dataSet,minSupport = 0.5):#生成频繁项集
c1 = createC1(dataSet)
D = list(map(set,dataSet))
l1,supportData = scanData(D,c1,minSupport)
L = [l1]
k = 2
while(len(L[k-2])>0):
ck = aprioriGen(L[k-2],k)
lk,supk = scanData(D,ck,minSupport)
k = k + 1
L.append(lk)
supportData.update(supk)
return L,supportData
def generaterRules(L,supportData,minConf=0.7):#生成规则
bigRuleList = []
for i in range(1,len(L)):
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]
if i>1:
rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
else:
calcConf(freqSet,H1,supportData,bigRuleList,minConf)
return bigRuleList
def calcConf(freqSet,H,suppurtData,brl,minConf = 0.7):#计算满足置信度的规则
prunedH = []
for conseq in H:
conf = suppurtData[freqSet]/suppurtData[freqSet-conseq]
if conf > minConf:
brl.append((freqSet-conseq,conseq,conf))
prunedH.append(conseq)
return prunedH
def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):#递归生成规则
m = len(H[0])
if len(freqSet)>=(m+1):
Hmp1 = calcConf(freqSet,H,supportData,brl,minConf)
if (len(Hmp1) > 1):
Hmp1 = aprioriGen(Hmp1,m+1)
rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)
data = [line.split() for line in open('mushroom.dat').readlines()]
L,support = apriori(data,minSupport=0.3)
for i in range(len(L)):
for item in L[i]:
if item & {'2'}:
print(item)
|
代码及数据集下载：Apriori
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/weixin_37895339/article/details/78650100