In [1]:
pip list
构建 FP 树¶
辅助类：FP树的数据结构¶
In [2]:
class treeNode:
"""
parameters：
nameValue：当前节点项名称
numOccur：项的频数
parentNode：当前结点的父节点
"""
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue # 当前节点项名称
self.count = numOccur # 项的频数
self.nodeLink = None # 用于连接相似元素项（FP树蓝色的虚线）
self.parent = parentNode # 当前父节点
self.children = {} # 用于存放子节点的字典
def increase(self, numOccur):
self.count += numOccur
def show(self, ind=1):
print(' '*ind, self.name, ' ', self.count)
for child in self.children.values():
child.show(ind+1) #子节点向右缩减
In [3]:
#创建一个单节点
rootNode = treeNode('这是父节点',9,None)
#创建一个子节点
rootNode.children['这是子节点'] = treeNode('这是子节点',13,None)
#显示节点
rootNode.show()
In [4]:
#再增加一个子节点
rootNode.children['这是另一个子节点'] = treeNode('这是另一个子节点',3,None)
#显示节点
rootNode.show()
辅助函数1：创建数据集¶
In [5]:
def loadSimpDat():
"""
Return:
simpDat：list，数据集
"""
simpDat = [
['I1', 'I2', 'I5'],
['I2', 'I4'],
['I2', 'I3'],
['I1', 'I2', 'I4'],
['I1', 'I3'],
['I2', 'I3'],
['I1', 'I3'],
['I1', 'I2', 'I3', 'I5'],
['I1', 'I2', 'I3']
]
return simpDat
主函数：创建数据集¶
In [6]:
simpDat = loadSimpDat()
simpDat
Out[6]:
辅助函数2：格式化数据集¶
现在输入的数据集是列表，需要进行格式化操作，将其转变为固定格式（frozenset）
转换为 项列表 : 频数 的形式。
In [7]:
def createInitSet(dataSet):
"""
parameters：
dataSet：list，数据集
Return:
retDict：dict，格式化后的数据集
"""
retDict = {}
for trans in dataSet:
fset = frozenset(trans)
retDict.setdefault(fset, 0) # python字典自带函数，如果字典中包含有给定键，则返回该键对应的值，否则（不存在于字典中)，添加键并将值设为默认值，返回为该键设置的值。
retDict[fset] += 1
return retDict
In [8]:
retDict = createInitSet(simpDat) # 辅助函数2：格式化数据集
retDict
Out[8]:
辅助函数3：更新头指针表¶
确保FP树中每一条蓝色的虚线都指向树中的每一个结点。
Ps：这一部分涉及到数据结构中的指针指向问题。看不懂的需要自行复习指针内容。
In [9]:
def updateHeader(nodeToTest, targetNode):
"""
parameters:
targetNode：treeNode自定义的数据结构，
targetNode：treeNode自定义的数据结构，目标结点
"""
while (nodeToTest.nodeLink != None): # nodeToTest的下一个相似项不为空，即不是最后一个结点。最后一个目标结点的nodeLink为null
nodeToTest = nodeToTest.nodeLink # nodeToTest指向nodeToTest的nodeLink，相当于结点指针后移。
nodeToTest.nodeLink = targetNode # 最后一个结点的nodeLink存放targetNode的地址。
辅助函数4：FP树的生长函数¶
首先测试事务中第一个元素项是不是子节点，
如果是子节点，则更新count参数（+1）；
如果不是子节点，则创建一个新的treeNode作为子节点添加到树中。此时，头指针表也要跟着更新以指向新的节点（调用updateHeader()函数）。如果item中不止一个元素项的话，则将剩下的元素项作为参数进行迭代。
In [10]:
def updateTree(items, myTree, headerTable, count):
"""
Parameters:
items：项名称
myTree：treeNode类的对象，FP树
headerTable：dict，头指针表
count：int，计数
"""
# 检查事务项中的第一个元素是否作为树的直接子节点存在
if items[0] in myTree.children:
# 如果是子节点，则更新count参数（+1）；
myTree.children[items[0]].increase(count)
else:
# 不存在则更新树结构
myTree.children[items[0]] = treeNode(items[0], count, myTree) # 创建一个新的treeNode作为子节点添加到树中
# 更新表结构
if headerTable[items[0]][1] == None: # 如果头指针表未更新，即未指向新的结点。
headerTable[items[0]][1] = myTree.children[items[0]]
else:
updateHeader(headerTable[items[0]][1], myTree.children[items[0]])
# 递归调用此树生长函数
if len(items) > 1:
updateTree(items[1:], myTree.children[items[0]], headerTable, count) # 递归使得FP树生长。
辅助函数5：创建树¶
In [11]:
def createTree(dataSet, minSup=1):
"""
Parameters:
dataSet：dict，格式化后的数据集
minSup：int，最小支持度
Return:
myTree：treeNode类的对象，FP树
headerTable：dict，头指针表
"""
# 连续两次遍历数据集。第一次获取所有数据项及个数；第二次会支持度过滤。
# 获取所有数据项及个数
headerTable = {}
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 支持度过滤
for k in headerTable.keys():
if headerTable[k] < minSup:
continue
# 单元素的频繁项集（不含次数）
freqItemSet = set(headerTable.keys())
# 如果所有数据都不满足最小支持度，则退出
if len(freqItemSet) == 0:
return None, None
# 对表数据结构进行格式化，使之能够存放指针。
for k in headerTable:
headerTable[k] = [headerTable[k], None]
# 新建初始化树节点
retTree = treeNode('φ', 1, None)
#第二次遍历数据集，构建fp-tree
for tranSet, count in dataSet.items():
# 根据最小支持度处理一条训练样本，字典中 key:项名称，value:该样例的的全局支持度
localD = {} # 当前事务的单元素集（含次数）
for item in tranSet:
if item in freqItemSet:
localD[item] = headerTable[item][0]
if len(localD) > 0:
# 根据全局频繁项对localD（每个事务中）的所有元素进行降序排序
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
# 更新 FP 树
updateTree(orderedItems, retTree, headerTable, count)
# 返回FP树和表头结构
return retTree, headerTable
主函数：创建FP树¶
In [12]:
myTree, headerTable = createTree(retDict,minSup=2) # 主函数：创建树
In [13]:
myTree.show() # 显示FP树
In [14]:
headerTable # 记录每个数据项的支持度
Out[14]:
二、从FP树中挖掘频繁项集¶
条件模式基的抽取¶
辅助函数6：¶
In [15]:
def ascendTree(leafNode, prefixPath):
"""
获取FP树某个叶子节点的前缀路径
"""
if leafNode.parent != None:
prefixPath.append(leafNode.name)
ascendTree(leafNode.parent, prefixPath)
辅助函数7：创建条件模式基¶
In [16]:
def findPrefixPath(basePat, headerTable):
"""
Parameters:
basePat：string，项名称
headerTable：dict，头指针表
Return：
condPats：dict,
"""
condPats = {}
treeNode = headerTable[basePat][1]
while treeNode != None:
prefixPath = []
ascendTree(treeNode, prefixPath)
if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = treeNode.count
treeNode = treeNode.nodeLink
return condPats
主函数：创建条件模式基¶
项：Head Table item列第一个不要，剩下的倒叙写。
可参考：https://gaozhiyuan.me/machine-learning/fp-growth.html#FP3
In [17]:
condPats = findPrefixPath('I5', headerTable)
print('I5', condPats)
condPats = findPrefixPath('I4', headerTable)
print('I4', condPats)
condPats = findPrefixPath('I3', headerTable)
print('I3', condPats)
condPats = findPrefixPath('I1', headerTable)
print('I1', condPats)
创造条件FP树¶
辅助函数8：由条件模式基创建条件FP树¶
In [18]:
def mineTree(inTree, headerTable, minSup=1, preFix=set([]), freqItemList=[]):
"""
Parameters:
inTree：__main__.treeNode，FP树
headerTable：dict，头指针表
minSup：int，最小支持度
preFix：
freqItemList：
Return:
null
"""
#排序minSup asc, value asc。对表结构进行重排序(由小到大)
bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p:p[1][0])]
# 遍历表结构
for basePat in bigL:
# 生成新频繁子项
newFreqSet = preFix.copy()
newFreqSet.add(basePat)
# 加入频繁集
freqItemList.append(newFreqSet)
# 挖掘新的条件模式基
condPattBases = findPrefixPath(basePat, headerTable) # 主函数：创建条件模式基
# 建立新的条件FP树
myCondTree, myHead = createTree(condPattBases, minSup) # 主函数：创建树
# 若表结构非空，递归挖掘。
if myHead != None:
print('条件FP树：')
myCondTree.show()
print('\n')
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
主函数：创造条件FP树并输出频繁项集¶
In [19]:
# simpDat = loadSimpDat() # 加载数据集
# retDict = createInitSet(simpDat) # 辅助函数2：格式化数据集
# myTree, headerTable = createTree(retDict,minSup=2) # 主函数：创建树
my_freq_list = []
mineTree(myTree, headerTable, 2, set([]), my_freq_list)
print("支持度大于2的频繁项集：", my_freq_list)
print("支持度大于2的频繁项集数：", len(my_freq_list))
In [ ]: