FP-growth算法挖掘頻繁項集

概述

FP-growth算法基于Apriori建構，但在完成相同任務時采用了一些不同的技術。這裡的任務是将資料集存儲在一個特定的稱作FP樹的結構之後發現頻繁項集或者頻繁項對，即常在一塊出現的元素項的集合FP樹。這種做法使得算法的執行速度要快于Apriori，通常性能要好兩個數量級以上。

FP-growth算法隻需要對資料庫進行兩次掃描，而Apriori算法對每個潛在的頻繁項集都會掃描資料集判定給定模式是否頻繁，是以FP-growth算法的速度要比Apiori算法要快。Apriori算法的缺點是多次掃描資料庫帶來了巨大的IO開銷，而FP-growth算法是典型的基于記憶體的算法，其優點是減少掃描次數來減少IO開銷。

FP-growth發現頻繁項集的基本過程如下：

(1)建構FP樹

(2)從FP樹中挖掘頻繁項集

FP樹的建構

FP樹是一種字首樹，有點類似于Trie樹但是每個節點有三個指針，分别指向parent，children和nodeLink。此外，算法中還包含有一個頭指針表，頭指針表中記錄每個元素出現的第一個位置（結點），結點中的nodeLink将所有相同的元素連接配接起來。

第一遍掃描資料庫的時候統計每個元素（單項集）出現次數。

第二遍掃描資料庫的時候對于原來的每個資料，将資料中支援度小于門檻值的元素删除，然後将這個資料按照剛才元素出現次數排序。排序後每個項集都有一個唯一的順序，這樣可以保證後續算法找出所有不重複的頻繁項集。然後将這個資料插入到FP樹中，并且更新頭指針表和nodelink。

挖掘頻繁項集

在挖掘頻繁項集的時候，類似于Apriori算法，從單項集出發每次增加一個元素。對于每一個頻繁項集，我們獲得這個頻繁項集作為結尾的所有字首路徑（起點為根節點），這些路徑的集合稱為條件模式基（conditional pattern base）。這裡就用到了之前的nodeLink指針，我們可以獲得目前所有以某個元素結尾的結點指針。

上面說了，FP-growth類似于Apriori算法，從單項集出發每次增加一個元素。FP-growth算法對于每一個頻繁項集以字首路徑構造一棵FP樹，然後向目前的頻繁項集中添加一個元素，然後以深度優先的政策遞歸的進行這個過程知道發現所有頻繁項集。

例子

考慮以下資料集

為了構造FP樹，首先第一遍掃描資料計算所有單項集的支援度。然後将支援度大于門檻值的單項集按照降序排列{ B(6), E(5), A(4), C(4), D(4) }.。

對于第一個資料BEAD，将它插入到FP樹中，如下

對于第二個資料BEC，插入到FP樹中，如下

将剩下的資料做相同的操作，最後得到初始的FP樹

然後開始挖掘頻繁項集

第一次調用的時候利用上面構造的初始樹，第一步獲得頻繁項集{D, C, A, E，B}，用深度優先的政策，以D為字尾的字首路徑構造一棵新的FP樹，然後可以得到頻繁項集{DA, DE，DB}，然後這樣遞歸下去，直到找到所有頻繁項集{ DAE, DAEB, DAB, DEB, CE, CEB, CB, AE, AEB, AB, EB }。流程如下圖所示

Python實作代碼

from numpy import *


# FP-Growth算法

# 構造資料集
def loadData():
    return [  ['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']]

def createInitSet(dataSet):
    retDic = {}
    for trans in dataSet:
        retDic[frozenset(trans)] = 
    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=):
        print(' '*ind, self.name, ' ', self.count)
        for child in self.children:
            self.children[child].disp(ind+)


# 用字典來儲存頭指針表
def createTree(dataSet, minSup=):
    headerTable = {}
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, ) + dataSet[trans]
    for i in list(headerTable.keys()):
        if headerTable[i] < minSup:
            headerTable.pop(i)
        else:
            headerTable[i] = [headerTable[i], None]
    if len(headerTable) == : return None, None
    retTree = Node('Null Set', , None)
    for trans, count in dataSet.items():
        localD = {}
        for item in trans:
            if item in headerTable:
                localD[item] = headerTable[item][]
        newD = [(v[], v[]) for v in localD.items()]
        newD.sort(reverse=True)
        updateTree([v[] for v in newD], retTree, headerTable, count)
    return retTree, headerTable

# 根據所給的項集更新樹
def updateTree(items, node, headerTable, count):
    if len(items) == : return
    if items[] in node.children:
        node.children[items[]].inc(count)
    else:
        newChild = Node(items[], count, node)
        node.children[items[]] = newChild
        if headerTable[items[]][] == None:
            headerTable[items[]][]  = newChild
        else:
            updateNodeLink(headerTable[items[]][], newChild)
    updateTree(items[:], node.children[items[]], headerTable, 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) > :
            condPats[frozenset(prefixPath[:])] = node.count
        node = node.nodeLink
    return condPats

def mineTree(node, headerTable, minSup, prefix, freqItemList):
    bigL = [v[] for v in sorted(headerTable.items(), key=lambda p:p[])]
    for basePat in bigL:
        newFreqSet = prefix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(headerTable[basePat][])
        newCondTree, newHeaderTable = createTree(condPattBases, minSup)
        if newCondTree != None:
            mineTree(newCondTree, newHeaderTable, minSup, newFreqSet, freqItemList)


simpDat = loadData()
initSet = createInitSet(simpDat)
fpTree, headerTable = createTree(initSet, )
#fpTree.disp()
#condPats = findPrefixPath(headerTable['x'][1])
#print(condPats)
freqItems = []
mineTree(fpTree, headerTable, , set([]), freqItems)
print(freqItems)