机器学习之FP-growth算法

短命女 2022-08-25 15:56 6阅读 0赞

# 一、背景 #

当我们用搜索引擎输入一个单词或者单词的一部分时，搜索引擎会自动补全查询词项。例如，当我输入“电脑”开始查询时，搜索引擎会推荐一些句子：“电脑管家”，“电脑蓝屏”等等。为了给出这些推荐查询词项，搜索引擎公司是使用了FP-growth算法。

#  #

前面介绍的Apriori算法也可以来发现频繁集，而FP-growth算法是基于Apriori的构建，采用了一些不同的技术。我们先将数据集存储在一个称作为FP树的结构上，然后来寻找频繁项集。即常在一块出现的元素项的集合FP树。这种算法的优点是处理速度比Apriori算法快的多。缺点是不能用于发现关联规则。

# 二、实例说明 #

## 2.1主要思路:可参考机器学习实战，李锐译这本书，说的很详细。 ##

## 2.2 FP树的类定义 ##

给出6个事务，每个事务可以当成是一句话，每个字母当成是一个词

![Image 1][]  ![Image 1][]    ![Image 1][]

生成一个FP树

![Image 1][]

代码：

''' 功能：FP树的类定义 说明：treeNode为类名 输入变量： 输出变量： ''' class treeNode: def __init__(self, nameValue, numOccur, parentNode): #注意self的用法,__init__的用法 self.name = nameValue #节点名字 self.count = numOccur #计数值 self.nodeLink = None #用于链接相似的元素项 self.parent = parentNode #父节点，用于后面根据给定叶子节点上溯整棵树。 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.values(): child.disp(ind+1) rootNode = treeNode('pyramid',9,None)
    rootNode.children['eye'] = treeNode('eye',13,None)
    rootNode.children['phoenix'] = treeNode('phoenix',3,None)
    rootNode.disp()

结果：

pyramid   9
         eye   13
         phoenix   3

## 2.3构建FP树 ##

代码：

############################################ #功能：构建FP树 #输入变量： #dataSet:数据集（字典型） #minSup:最小支持度 #输出变量： #retTree：FP数 #headerTable:头指针表 ############################################ def createTree(dataSet, minSup=1): #create FP-tree from dataset but don't mine headerTable = {} #go over dataSet twice 遍历数据集两遍 #第一遍遍历扫描数据集并统计每个元素项出现的频度 for trans in dataSet:#first pass counts frequency of occurance for item in trans: #dict.get用法：如果字典中没有某个元素，则赋值为0，否则返回该元素对应的value值 #如果字典中存在该元素，则该元素的value值在原来的基本上加上dataSet[trans] headerTable[item] = headerTable.get(item, 0) + dataSet[trans] for k in headerTable.keys(): #remove items not meeting minSup 删除出现次数少于minSup的项 if headerTable[k] < minSup: del(headerTable[k]) freqItemSet = set(headerTable.keys()) #set用法:生成不重复的元素集 ## print 'freqItemSet: ',freqItemSet if len(freqItemSet) == 0: return None, None #如果所有项都不频繁，则退出 for k in headerTable: #对头指针表扩展以便可以保存计数值及指向每种类型第一个元素项的指针 headerTable[k] = [headerTable[k], None] # print 'headerTable: ',headerTable retTree = treeNode('Null Set', 1, None) #create tree创建空集合的根节点 for tranSet, count in dataSet.items(): #go through dataset 2nd time 第二遍循环数据集 localD = {} for item in tranSet: #put transaction items in order if item in freqItemSet: localD[item] = headerTable[item][0] #对每件事务过滤，只留下频繁元素 ## print 'localD=',localD if len(localD) > 0: orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]#生成书中表12-2 ## print 'orderedItems=',orderedItems updateTree(orderedItems, retTree, headerTable, count)#populate tree with ordered freq itemset ## print retTree return retTree, headerTable #return tree and header table ############################################ #功能：更新FP数，让FP数往下产生子节点 #输入变量： #items:过滤及重排序后的事务项 #inTree:FP数 #headerTable:头指针表 #count：计数值 #输出变量： ############################################ def updateTree(items, inTree, headerTable, count): if items[0] in inTree.children:#check if orderedItems[0] in retTree.children 判断是否为子节点 inTree.children[items[0]].inc(count) #incrament count else: #add items[0] to inTree.children 添加子节点 inTree.children[items[0]] = treeNode(items[0], count, inTree) #update header table 更新头指针表 if headerTable[items[0]][1] == None: #如果原来头指针中该元素链表为空 headerTable[items[0]][1] = inTree.children[items[0]] #将该子节点赋给headerTable中链表处 else: updateHeader(headerTable[items[0]][1], inTree.children[items[0]]) #更新头指针 if len(items) > 1:#迭代updateTree，每次调用时去掉列表中的第一个元素。不怎么理解 updateTree(items[1::], inTree.children[items[0]], headerTable, count) ############################################ #功能：更新头指针表 #输入变量： #nodeToTest：头指针表中的链表 #targetNode：目标节点 #输出变量： ############################################ def updateHeader(nodeToTest, targetNode): #this version does not use recursion while (nodeToTest.nodeLink != None): #循环直至找到最后面的空链表 nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNode #目标节点链到最后 ############################################ #功能：载入数据集 ############################################ def loadSimpDat(): # simpDat = [['r','z'],['z','j']] 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 simpDat = loadSimpDat() print 'simpDat=',simpDat initSet = createInitSet(simpDat) print 'initSet=',initSet myFPtree,myHeaderTab = createTree(initSet,3) myFPtree.disp()

结果：

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']]
    initSet= {frozenset(['e', 'm', 'q', 's', 't', 'y', 'x', 'z']): 1, frozenset(['x', 's', 'r', 'o', 'n']): 1, frozenset(['s', 'u', 't', 'w', 'v', 'y', 'x', 'z']): 1, frozenset(['q', 'p', 'r', 't', 'y', 'x', 'z']): 1, frozenset(['h', 'r', 'z', 'p', 'j']): 1, frozenset(['z']): 1}
       Null Set   1
         x   1
           s   1
             r   1
         z   5
           x   3
             y   3
               s   2
                 t   2
               r   1
                 t   1
           r   1

## 2.4 从FP树种挖掘频繁项集 ##

（抽取条件模式基）代码：

############################################ #功能：上溯FP数，找到前缀路径 #输入变量： #leafNode：给定元素的链接节点 #prefixPath：用于保存前缀路径的列表 #输出变量： ############################################  def ascendTree(leafNode, prefixPath): #ascends from leaf node to root     if leafNode.parent != None:         prefixPath.append(leafNode.name)         ascendTree(leafNode.parent, prefixPath) ############################################ #功能：给定元素项生成一个条件模式基 #输入变量： #basePat：给定的元素项 #treeNode：头指针表中指向每种类型第一个元素项的链接节点 #输出变量： #condPats:条件路径基 ############################################      def findPrefixPath(basePat, treeNode): #treeNode comes from header table     condPats = {} #存储条件模式基的空字典     while treeNode != None: #给定元素的链接节点不为空         prefixPath = []  #用于保存前缀路径的列表         ascendTree(treeNode, prefixPath) #上溯FP树         if len(prefixPath) > 1:              condPats[frozenset(prefixPath[1:])] = treeNode.count         treeNode = treeNode.nodeLink #转到到该元素的下一个链接处     return condPats simpDat = loadSimpDat() initSet = createInitSet(simpDat) myFPtree,myHeaderTab = createTree(initSet,3) prefixPath = findPrefixPath('r',myHeaderTab['r'][1]) print 'prefixPath=',prefixPath

结果：

prefixPath= {frozenset(['x', 's']): 1, frozenset(['z']): 1, frozenset(['y', 'x', 'z']): 1}

（创建条件FP树）代码：

############################################ #功能：递归查找频繁项集 #输入变量： #inTree：FP树 #headerTable：头指针表 #minSup：最小支持度 #preFix： #freqItemList：频繁项集列表 #输出变量： ############################################   def mineTree(inTree, headerTable, minSup, preFix, freqItemList):      bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#对头指针表中的元素项按照其出现频率排序     print 'bigL=',bigL     for basePat in bigL:  #start from bottom of header table         newFreqSet = preFix.copy()         newFreqSet.add(basePat) #先将频繁项添加到临时列表中         #print 'finalFrequent Item: ',newFreqSet    #append to set         freqItemList.append(newFreqSet)  #将每一个频繁项添加到频繁项集列表中         condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) #给定元素项生成一个条件模式基         print 'condPattBases :',basePat, condPattBases         #2. construct cond FP-tree from cond. pattern base         myCondTree, myHead = createTree(condPattBases, minSup)         print 'head from conditional tree: ', myHead         if myHead != None: #3. mine cond. FP-tree             print 'conditional tree for: ',newFreqSet             myCondTree.disp(1)                         mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) myFreqList = [] mineTree(myFPtree, myHeaderTab, minSup, set([]), myFreqList)

结果：

prefixPath= {frozenset(['x', 's']): 1, frozenset(['z']): 1, frozenset(['y', 'x', 'z']): 1}
    conditional tree for:  set(['y'])
       Null Set   1
         x   3
           z   3
    conditional tree for:  set(['y', 'z'])
       Null Set   1
         x   3
    conditional tree for:  set(['s'])
       Null Set   1
         x   3
    conditional tree for:  set(['t'])
       Null Set   1
         y   3
           x   3
             z   3
    conditional tree for:  set(['x', 't'])
       Null Set   1
         y   3
    conditional tree for:  set(['z', 't'])
       Null Set   1
         y   3
           x   3
    conditional tree for:  set(['x', 'z', 't'])
       Null Set   1
         y   3
    conditional tree for:  set(['x'])
       Null Set   1
         z   3

总结：

[Image 1]: