《机器学习实战》学习笔记第十一章 —— Apriori算法

def createC1(dataSet): #生成单位项集
C1 = []
for transaction in dataSet: #枚举每一条数据
for item in transaction: #枚举每条数据中的每个元素
if not [item] in C1:
C1.append([item]) #将素有元素加入列表中
C1.sort() #必要的排序
return map(frozenset, C1) # use frozen set so we can use it as a key in a dict def scanD(D, Ck, minSupport): #计算项集的支持度，并过滤掉支持度低于阈值的项集，从而形成频繁项集。Ck的k代表项集的项数
ssCnt = {}
for tid in D: #统计项集在数据中的出现次数
for can in Ck:
if can.issubset(tid):
if not ssCnt.has_key(can):
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 def aprioriGen(Lk, k): # 用于生成下一层的频繁项集（即项数是当前一次的项数+1狼，即k）
retList = []
lenLk = len(Lk)
for i in range(lenLk): #O(n^2)组合生成新项集
for j in range(i + 1, lenLk):
L1 = list(Lk[i])[:k - 2]; L2 = list(Lk[j])[:k - 2] #去除两者的前k-2个项
L1.sort(); L2.sort()
if L1 == L2: # 如果前k-2个项相等，那么将Lk[i]和Lk[j]并在一起，就形成了k+1个项的项集
retList.append(Lk[i] | Lk[j]) # set union
return retList def apriori(dataSet, minSupport=0.5): #Apriori算法
D = map(set, dataSet) #set形式数据集（即去除重复的数据）
C1 = createC1(dataSet) #单位项集
L1, supportData = scanD(D, C1, minSupport) #单位频繁项集
L = [L1]
k = 2
while (len(L[k - 2]) > 1): #如果当层的频繁项集的个数大于1，那么就可以根据当层的频繁项集生成下一层的频繁项集
Ck = aprioriGen(L[k - 2], k) #生成下一层的项集
Lk, supK = scanD(D, Ck, minSupport) # 生成下一层的频繁项集，同时得到项集的支持度
supportData.update(supK) #更新支持度库
L.append(Lk) #把下一层的频繁项集加入到“层叠”里面
k += 1 #将下一层作为当层
return L, supportData

def calcConf(freqSet, H, supportData, brl, minConf=0.7): #计算关联规则的可信度，关联规则的右端的元素个数是固定的
prunedH = [] # create new list to return
for conseq in H: #conseq作为关联规则的右端
conf = supportData[freqSet] / supportData[freqSet - conseq] # 计算可信度
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):
m = len(H[0]) #关联规则的右端的元素个数
if (len(freqSet) > m): #如果总的元素个数大于关联规则的右端的元素个数，则继续生成关联规则
Hitem = calcConf(freqSet, H, supportData, brl, minConf) #生成关联规则， 同时过滤出有用的频发项集
if (len(Hitem) > 1): # 频繁项集的个数超过一个，则可以生成下一层的项集（即关联规则的元素个数右端加一，对应地左端减一）
Hnext = aprioriGen(Hitem, m + 1) # create Hm+1 new candidates
rulesFromConseq(freqSet, Hnext, supportData, brl, minConf) def generateRules(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] #将频繁项集中的元素单独作为一个集合，然后这些集合构成一个列表
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) #递归地将freqSet中的元素移到关联规则的右端，从而生成关联规则
return bigRuleList