FP-growth算法挖掘频繁项集
概述FP-growth算法基于Apriori构建,但在完成相同任务时采用了一些不同的技术。这里的任务是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或者频繁项对,即常在一块出现的元素项的集合FP树。这种做法使得算法的执行速度要快于Apriori,通常性能要好两个数量级以上。 FP树的构建FP树是一种前缀树,有点类似于Trie树但是每个节点有三个指针,分别指向parent,children和nodeLink。此外,算法中还包含有一个头指针表,头指针表中记录每个元素出现的第一个位置(结点),结点中的nodeLink将所有相同的元素连接起来。 第一遍扫描数据库的时候统计每个元素(单项集)出现次数。 第二遍扫描数据库的时候对于原来的每个数据,将数据中支持度小于阈值的元素删除,然后将这个数据按照刚才元素出现次数排序。排序后每个项集都有一个唯一的顺序,这样可以保证后续算法找出所有不重复的频繁项集。然后将这个数据插入到FP树中,并且更新头指针表和nodelink。 挖掘频繁项集在挖掘频繁项集的时候,类似于Apriori算法,从单项集出发每次增加一个元素。对于每一个频繁项集,我们获得这个频繁项集作为结尾的所有前缀路径(起点为根节点),这些路径的集合称为条件模式基(conditional pattern base)。这里就用到了之前的nodeLink指针,我们可以获得当前所有以某个元素结尾的结点指针。 例子考虑以下数据集 为了构造FP树,首先第一遍扫描数据计算所有单项集的支持度。然后将支持度大于阈值的单项集按照降序排列{ B(6),E(5),A(4),C(4),D(4) }.。 对于第二个数据BEC,插入到FP树中,如下 将剩下的数据做相同的操作,最后得到初始的FP树 然后开始挖掘频繁项集 Python实现代码from numpy import *
# FP-Growth算法
# 构造数据集
def loadData():
return [ ['r','z','h','j','p'],['z','y','x','w','v','u','t','s'],['z'],['r','n','o',['y','r','q','e','s','m']]
def createInitSet(dataSet):
retDic = {}
for trans in dataSet:
retDic[frozenset(trans)] = 1
return retDic
# 定义FP树的结构
class Node:
def __init__(self,name,count,parent):
self.name = name
self.count = count
self.nodeLink = None
self.parent = parent
self.children = {}
def inc(self,numOccur):
self.count += numOccur
def disp(self,ind=1):
print(' '*ind,self.name,' ',self.count)
for child in self.children:
self.children[child].disp(ind+1)
# 用字典来保存头指针表
def createTree(dataSet,minSup=1):
headerTable = {}
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item,0) + dataSet[trans]
for i in list(headerTable.keys()):
if headerTable[i] < minSup:
headerTable.pop(i)
else:
headerTable[i] = [headerTable[i],None]
if len(headerTable) == 0: return None,None
retTree = Node('Null Set',1,None)
for trans,count in dataSet.items():
localD = {}
for item in trans:
if item in headerTable:
localD[item] = headerTable[item][0]
newD = [(v[1],v[0]) for v in localD.items()]
newD.sort(reverse=True)
updateTree([v[1] for v in newD],retTree,headerTable,count)
return retTree,headerTable
# 根据所给的项集更新树
def updateTree(items,node,count):
if len(items) == 0: return
if items[0] in node.children:
node.children[items[0]].inc(count)
else:
newChild = Node(items[0],node)
node.children[items[0]] = newChild
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = newChild
else:
updateNodeLink(headerTable[items[0]][1],newChild)
updateTree(items[1:],node.children[items[0]],count)
def updateNodeLink(preNode,newNode):
while preNode.nodeLink != None:
preNode = preNode.nodeLink
preNode.nodeLink = newNode
# 寻找前缀路径
def ascendTree(node,path):
if node.parent != None:
path.append(node.name)
ascendTree(node.parent,path)
def findPrefixPath(node):
condPats = {}
while node != None:
prefixPath = []
ascendTree(node,prefixPath)
if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = node.count
node = node.nodeLink
return condPats
def mineTree(node,minSup,prefix,freqItemList):
bigL = [v[0] for v in sorted(headerTable.items(),key=lambda p:p[0])]
for basePat in bigL:
newFreqSet = prefix.copy()
newFreqSet.add(basePat)
freqItemList.append(newFreqSet)
condPattBases = findPrefixPath(headerTable[basePat][1])
newCondTree,newHeaderTable = createTree(condPattBases,minSup)
if newCondTree != None:
mineTree(newCondTree,newHeaderTable,newFreqSet,freqItemList)
simpDat = loadData()
initSet = createInitSet(simpDat)
fpTree,headerTable = createTree(initSet,3)
#fpTree.disp()
#condPats = findPrefixPath(headerTable['x'][1])
#print(condPats)
freqItems = []
mineTree(fpTree,3,set([]),freqItems)
print(freqItems)
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |