《机器学习实战》第12章学习笔记（FP-growth）

一、FP-growth算法

FP-growth基于Apriori构建， 但在完成相同任务时采用了一些不同的技术。这里的任务是将数据集存储在一个特定的称作??树的结构之后发现频繁项集或者频繁项对， 即常在一块出现的元素项的集合FP树。这种做法使得算法的执行速度要快于Apriori,通常性能要好两个数量级以上。

FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori 算法快。在小规模数据集上，这不是什么问题，但当处理更大数据集时，就会产生较大问题。FP-growth只会扫描数据集两次，它发现频繁项集的基本过程如下：
(1) 构建FP树

(2)从FP树中挖掘频繁项集

1.1  FP树

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式（Frequent Pattern)。一棵FP树看上去与计算机科学中的其他树结构类似，但是它通过链接（link）来连接相 似元素，被连起来的元素项可以看成一个链表。下图给出了FP树的一个例子。

      同搜索树不同的是，一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率，  而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。 树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。

      相似项之间的链接即节点链接(node link),用于快速发现相似项的位置。

1.2 FP-growth算法一般步骤：

二、代码实现

# -*- coding: utf-8 -*-
"""
Created on Mon May 14 15:21:11 2018

@author: lizihua
"""
import copy

#FP树的数据结构
#name：存放节点名字的变量；count：计数值；nodeLink：用于链接相似的元素项
#parent:指向当前节点的父节点（通常不使用，因为通常是从上往下迭代访问节点）
#children：空子典，用于存放节点的子节点
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name =nameValue
        self.count = numOccur
        self.nodeLink =None
        self.parent = parentNode
        self.children = {}
    #给count增加给定值    
    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)

#FP树构建函数
#使用数据集和最小支持度作为参数构建FP树
#构建时，会遍历数据集两次，
#第一次统计每个元素项出现的频度，并将信息存储到头指针表中，并删除那些次数少于minSup的项
def createTree(dataSet, minSup=1):
    
    headerTable = {}         #将每个元素出现的频度的信息存储到headerTable
    #遍历两次数据集
    #第一次统计每个元素项出现的频度，并存储，然后删除那些次数少于minSup的项
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    
    #删除那些次数少于minSup的项
    headerTab = copy.deepcopy(headerTable)
    for k in headerTab.keys():  
        if headerTab[k] < minSup: 
            del(headerTable[k])
    freqItemSet = set(headerTable.keys())
    #print('freqItemSet: ',freqItemSet)
    #若所有项都不频繁，则直接退出
    if len(freqItemSet) == 0: return None, None  
    for k in headerTable:
        headerTable[k] = [headerTable[k], None] #reformat headerTable to use Node link 
    #print('headerTable: ',headerTable)
    #创建FP树
    retTree = treeNode('Null Set', 1, None) 
    #第二次遍历数据集
    for tranSet, count in dataSet.items():  
        localD = {}
        #根据全局频率对每个事务中的元素进行排序
        for item in tranSet:  
            if item in freqItemSet:
                localD[item] = headerTable[item][0]
        if len(localD) > 0:
            #按照元素项的绝对出现的次数大小进行排序,key=lambda p: p[1]代表按照字典的第2个元素进行排序
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
            #print("orderedItems:",orderedItems)
            #使用排序后的频率项集对树进行填充
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable #return tree and header table

#输入的是一个项集，让FP树生长
def updateTree(items, inTree, headerTable, count):
    #测试事务中的第一个元素项是否作为子节点存在
    if items[0] in inTree.children:
        #若是，则增加该元素项的计数
        inTree.children[items[0]].inc(count) 
    else:   #否则，则创建一个新的treeNode，并将其作为一个子节点添加到树中
        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(items[1::], inTree.children[items[0]], headerTable, count)

#更新头指针表，确保节点链接指向树中该元素项的每一个实例        
def updateHeader(nodeToTest, targetNode):   
    while (nodeToTest.nodeLink != None):    
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode
    
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

#从FP树中挖掘频繁项集

#确定节点，获得该节点的前缀路径，
#自下而上追溯，不断判断是否存在父节点，若存在，则保存该点
def ascendTree(leafNode, prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

#获得FP树某个节点的前缀路径        
def findPrefixPath(basePat,treeNode):
    #条件模式基字典condPats
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 0:
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats

#递归查找频繁项集的mineTree函数
def mineTree(inTree,headerTable, minSup,preFix, freqItemList):
    #对头指针表中的元素项按照其出现频率从小到大进行排序
    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中
        freqItemList.append(newFreqSet)
        #创建条件基
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        #利用条件基当做一个新数据集输送给createTree()函数
        myCondTree,myHead = createTree(condPattBases,minSup)
        #只要树中有元素项，递归调用mineTree()函数
        if myHead != None:
            print("condition tree for:",newFreqSet)
            myCondTree.disp(1)
            mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)
            
if __name__ == "__main__":
    """
    rootNode = treeNode("pyramid", 9, None)
    rootNode.children['eye'] = treeNode('eye',13,None)
    rootNode.children['phoenix'] = treeNode('phoenix',3,None)
    rootNode.disp()
    """
    simpDat = loadSimpDat()
    initSet = createInitSet(simpDat)
    print(initSet)
    myFPtree,myHeaderTab = createTree(initSet, 3)
    print("\n myFPtree:")
    myFPtree.disp()
    #condPats_x = findPrefixPath('x',myHeaderTab['x'][1])
    #condPats_z = findPrefixPath('z',myHeaderTab['z'][1])
    #condPats_r = findPrefixPath('r',myHeaderTab['r'][1])
    print("t的前缀：",findPrefixPath('t',myHeaderTab['t'][1]))
    #print(findPrefixPath('r',myHeaderTab['r'][1]))
    freqItems = []
    mineTree(myFPtree,myHeaderTab,3,set([]),freqItems)

三、结果显示

四、疑问，求解答

由于字典是无序的，但是，控制端直接输出的字典结果和print()的结果不一样。

如：

这直接影响到了后期的orderedItems，即将非频繁项移除并且重排序后的事务数据集，看红框的位置，

这就最终导致结果：

                       

这后期会引起某元素项的前缀路径不一样，以及后面的结果，所以想问下有没有大神可以帮忙解决一下。

我自己也百度了一些东西，说是python3.6的字典输出排序较之前python版本有了改进，说节省了内存等，所以，输出的方式改变了。自己也尝试在中间对字典进行排序，但是排序完后，重新，转换字典后，又是重新按照key排序的。

如：