本课程是中国大学慕课《机器学习》的“关联规则”章节的课后代码。
课程地址：
https://www.icourse163.org/course/WZU-1464096179
课程完整代码：
https://github.com/fengdu78/WZU-machine-learning-course
代码修改并注释：黄海广，haiguang2000@wzu.edu.cn
Apriori算法实现
import numpy as np
def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 获取候选1项集，dataSet为事务集。返回一个list，每个元素都是set集合
def createC1(dataSet):
C1 = [] # 元素个数为1的项集（非频繁项集，因为还没有同最小支持度比较）
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort() # 这里排序是为了，生成新的候选集时可以直接认为两个n项候选集前面的部分相同
# 因为除了候选1项集外其他的候选n项集都是以二维列表的形式存在，所以要将候选1项集的每一个元素都转化为一个单独的集合。
return list(map(frozenset, C1)) #map(frozenset, C1)的语义是将C1由Python列表转换为不变集合（frozenset，Python中的数据结构）
# 找出候选集中的频繁项集
# dataSet为全部数据集，Ck为大小为k（包含k个元素）的候选项集，minSupport为设定的最小支持度
def scanD(dataSet, Ck, minSupport):
ssCnt = {} # 记录每个候选项的个数
for tid in dataSet:
for can in Ck:
if can.issubset(tid):
ssCnt[can] = ssCnt.get(can, 0) + 1 # 计算每一个项集出现的频率
numItems = float(len(dataSet))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key] / numItems
if support >= minSupport:
retList.insert(0, key) #将频繁项集插入返回列表的首部
supportData[key] = support
return retList, supportData #retList为在Ck中找出的频繁项集（支持度大于minSupport的），supportData记录各频繁项集的支持度
# 通过频繁项集列表Lk和项集个数k生成候选项集C(k+1)。
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i + 1, lenLk):
# 前k-1项相同时，才将两个集合合并，合并后才能生成k+1项
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] # 取出两个集合的前k-1个元素
L1.sort(); L2.sort()
if L1 == L2:
retList.append(Lk[i] | Lk[j])
return retList
# 获取事务集中的所有的频繁项集
# Ck表示项数为k的候选项集，最初的C1通过createC1()函数生成。Lk表示项数为k的频繁项集，supK为其支持度，Lk和supK由scanD()函数通过Ck计算而来。
def apriori(dataSet, minSupport=0.5):
C1 = createC1(dataSet) # 从事务集中获取候选1项集
D = list(map(set, dataSet)) # 将事务集的每个元素转化为集合
L1, supportData = scanD(D, C1, minSupport) # 获取频繁1项集和对应的支持度
L = [L1] # L用来存储所有的频繁项集
k = 2
while (len(L[k-2]) > 0): # 一直迭代到项集数目过大而在事务集中不存在这种n项集
Ck = aprioriGen(L[k-2], k) # 根据频繁项集生成新的候选项集。Ck表示项数为k的候选项集
Lk, supK = scanD(D, Ck, minSupport) # Lk表示项数为k的频繁项集，supK为其支持度
L.append(Lk);supportData.update(supK) # 添加新频繁项集和他们的支持度
k += 1
return L, supportData
dataSet = loadDataSet() # 获取事务集。每个元素都是列表
# C1 = createC1(dataSet) # 获取候选1项集。每个元素都是集合
# D = list(map(set, dataSet)) # 转化事务集的形式，每个元素都转化为集合。
# L1, suppDat = scanD(D, C1, 0.5)
# print(L1,suppDat)
L, suppData = apriori(dataSet,minSupport=0.7)
print(L,suppData)
[[frozenset({5}), frozenset({2}), frozenset({3})], [frozenset({2, 5})], []] {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5}
FP树
# FP树类
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue #节点元素名称，在构造时初始化为给定值
self.count = numOccur # 出现次数，在构造时初始化为给定值
self.nodeLink = None # 指向下一个相似节点的指针，默认为None
self.parent = parentNode # 指向父节点的指针，在构造时初始化为给定值
self.children = {} # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值，初始化为空字典
# 增加节点的出现次数值
def inc(self, numOccur):
self.count += numOccur
# 输出节点和子节点的FP树结构
def disp(self, ind=1):
print(' ' * ind, self.name, ' ', self.count)
for child in self.children.values():
child.disp(ind + 1)
# =======================================================构建FP树==================================================
# 对不是第一个出现的节点，更新头指针块。就是添加到相似元素链表的尾部
def updateHeader(nodeToTest, targetNode):
while (nodeToTest.nodeLink != None):
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
# 根据一个排序过滤后的频繁项更新FP树
def updateTree(items, inTree, headerTable, count):
if items[0] in inTree.children:
# 有该元素项时计数值+1
inTree.children[items[0]].inc(count)
else:
# 没有这个元素项时创建一个新节点
inTree.children[items[0]] = treeNode(items[0], count, inTree)
# 更新头指针表或前一个相似元素项节点的指针指向新节点
if headerTable[items[0]][1] == None: # 如果是第一次出现，则在头指针表中增加对该节点的指向
headerTable[items[0]][1
] = inTree.children[items[0]]
else:
updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
if len(items) > 1:
# 对剩下的元素项迭代调用updateTree函数
updateTree(items[1::], inTree.children[items[0]], headerTable, count)
# 主程序。创建FP树。dataSet为事务集，为一个字典，键为每个事物，值为该事物出现的次数。minSup为最低支持度
def createTree(dataSet, minSup=1):
# 第一次遍历数据集，创建头指针表
headerTable = {}
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 移除不满足最小支持度的元素项
keys = list(headerTable.keys()) # 因为字典要求在迭代中不能修改，所以转化为列表
for k in keys:
if headerTable[k] del(headerTable[k])
# 空元素集，返回空
freqItemSet = set(headerTable.keys())
if len(freqItemSet) == 0:
return None, None
# 增加一个数据项，用于存放指向相似元素项指针
for k in headerTable:
headerTable[k] = [headerTable[k], None] # 每个键的值，第一个为个数，第二个为下一个节点的位置
retTree = treeNode('Null Set', 1, None) # 根节点
# 第二次遍历数据集，创建FP树
for tranSet, count in dataSet.items():
localD = {} # 记录频繁1项集的全局频率，用于排序
for item in tranSet:
if item in freqItemSet: # 只考虑频繁项
localD[item] = headerTable[item][0] # 注意这个[0]，因为之前加过一个数据项
if len(localD) > 0:
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
updateTree(orderedItems, retTree, headerTable, count) # 更新FP树
return retTree, headerTable
# =================================================查找元素条件模式基===============================================
# 直接修改prefixPath的值，将当前节点leafNode添加到prefixPath的末尾，然后递归添加其父节点。
# prefixPath就是一条从treeNode（包括treeNode）到根节点（不包括根节点）的路径
def ascendTree(leafNode, prefixPath):
if leafNode.parent != None:
prefixPath.append(leafNode.name)
ascendTree(leafNode.parent, prefixPath)
# 为给定元素项生成一个条件模式基（前缀路径）。basePet表示输入的频繁项，treeNode为当前FP树中对应的第一个节点
# 函数返回值即为条件模式基condPats，用一个字典表示，键为前缀路径，值为计数值。
def findPrefixPath(basePat, treeNode):
condPats = {} # 存储条件模式基
while treeNode != None:
prefixPath = [] # 用于存储前缀路径
ascendTree(treeNode, prefixPath) # 生成前缀路径
if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = treeNode.count # 出现的数量就是当前叶子节点的数量
treeNode = treeNode.nodeLink # 遍历下一个相同元素
return condPats
# =================================================递归查找频繁项集===============================================
# 根据事务集获取FP树和频繁项。
# 遍历频繁项，生成每个频繁项的条件FP树和条件FP树的频繁项
# 这样每个频繁项与他条件FP树的频繁项都构成了频繁项集
# inTree和headerTable是由createTree()函数生成的事务集的FP树。
# minSup表示最小支持度。
# preFix请传入一个空集合（set([])），将在函数中用于保存当前前缀。
# freqItemList请传入一个空列表（[]），将用来储存生成的频繁项集。
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
# 对频繁项按出现的数量进行排序进行排序
sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0]) #返回重新排序的列表。每个元素是一个元组，[（key,[num,treeNode],()）
bigL = [v[0] for v in sorted_headerTable] # 获取频繁项
for basePat in bigL:
newFreqSet = preFix.copy() # 新的频繁项集
newFreqSet.add(basePat) # 当前前缀添加一个新元素
freqItemList.append(newFreqSet) # 所有的频繁项集列表
condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) # 获取条件模式基。就是basePat元素的所有前缀路径。它像一个新的事务集
myCondTree, myHead = createTree(condPattBases, minSup) # 创建条件FP树
if myHead != None:
# 用于测试
print('conditional tree for:', newFreqSet)
myCondTree.disp()
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 递归直到不再有元素
# 生成数据集
def loadSimpDat():
simpDat = [['r', 'z', 'h', 'j', 'p'],
['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
['z'],
['r', 'x', 'n', 'o', 's'],
['y', 'r', 'x', 'z', 'q', 't', 'p'],
['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
return simpDat
# 将数据集转化为目标格式
def createInitSet(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
minSup = 3
simpDat = loadSimpDat() # 加载数据集
initSet = createInitSet(simpDat) # 转化为符合格式的事务集
myFPtree, myHeaderTab = createTree(initSet, minSup) # 形成FP树
# myFPtree.disp() # 打印树
freqItems = [] # 用于存储频繁项集
mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems) # 获取频繁项集
print(freqItems) # 打印频繁项集
conditional tree for: {'y'}
Null Set 1
x 3
z 3
conditional tree for: {'y', 'z'}
Null Set 1
x 3
conditional tree for: {'s'}
Null Set 1
x 3
conditional tree for: {'t'}
Null Set 1
y 3
z 2
x 2
x 1
z 1
conditional tree for: {'z', 't'}
Null Set 1
y 3
conditional tree for: {'x', 't'}
Null Set 1
y 3
conditional tree for: {'x'}
Null Set 1
z 3
[{'r'}, {'y'}, {'y', 'x'}, {'y', 'z'}, {'y', 'x', 'z'}, {'s'}, {'x', 's'}, {'t'}, {'y', 't'}, {'z', 't'}, {'y', 'z', 't'}, {'x', 't'}, {'y', 'x', 't'}, {'x'}, {'x', 'z'}, {'z'}]
参考
- https://www.cnblogs.com/lsqin/p/9342926.html
