概述
- 優(yōu)點：一般要快于Apriori
- 缺點：實現(xiàn)比較困難斩个，在某些數(shù)據(jù)集上性能會下降
- 適用數(shù)據(jù)類型：標稱型數(shù)據(jù)
FP-growth算法將數(shù)據(jù)存儲在一種稱為FP樹的緊湊數(shù)據(jù)結構中皮迟。FP代表頻繁模式（Frequent Pattern）办铡。
FP樹與其他樹結構類似。但它會把相似元素連接起來荣恐，被連起來的元素項可以看作是鏈表啤贩。如下圖所示。
一個元素項可以在一棵FP樹出現(xiàn)多次嘹吨。
FP樹會存儲項集的出現(xiàn)頻率，而每個項集會以路徑的方式存儲在樹中黍聂。
相似項之間的鏈接即節(jié)點鏈接（node link）躺苦，用于快速發(fā)現(xiàn)相似項的位置。
下面再簡單說明一下产还。
| 事務ID | 事務中的元素項 | 最小支持度過濾后 |
|---|---|---|
| 001 | r,z,h,j,p | r,z |
| 002 | z,y,x,w,v,u,t,s | z,y,x,t,s |
| 003 | z | z |
| 004 | r,x,n,o,s | r,x,s |
| 005 | y,r,x,z,q,t,p | y,r,x,z,t |
| 006 | y,z,x,e,q,s,t,m | y,z,x,s,t |
上表是生成上面FP樹的數(shù)據(jù)匹厘。第二列“事務中的元素項”是原數(shù)據(jù)，然后經(jīng)過最小支持度（關于支持度可以看之前Apriori算法的文章）過濾后脐区，留下頻繁項集愈诚。
圖1樹中節(jié)點z:5說明元素項出現(xiàn)5次。從z:5出發(fā)，沿著路徑x:3炕柔、y:3酌泰，說明{z,x,y}出現(xiàn)3次。z:5 -> r:1說明{z,r}出現(xiàn)1次匕累。到這里兩條路徑陵刹，z一共被使用4次，所以剩下的一次就是它自身{z}欢嘿。通過觀察上表最后一列“最小支持度過濾后”衰琐，可以知道上述結論的正確性。以此類推炼蹦，就能大概知道FP樹和頻繁項集的對應關系了羡宙。
構建FP樹
FP樹的數(shù)據(jù)結構
因為FP樹比較復雜，所以定義一個類來保存節(jié)點信息掐隐。
class treeNode:
def __init__(self, name, count, parentNode):
self.name = name # 節(jié)點名字
self.count = count # 計數(shù)值
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)
測試一下狗热。
開始構建
除了FP樹外，還需要一個頭指針表來指向給定類型的第一個實例虑省。利用頭指針表可以快速訪問FP樹中一個給定類型的所有元素匿刮。如下圖。
集合是無序的慷妙，假設有{z,x,y}和{y,z,x}僻焚，那么在FP樹中只會表示一條路徑允悦。為了解決這個問題膝擂，在將集合添加到樹前，先基于元素項的出現(xiàn)頻率進行排序隙弛。如下表架馋。
| 事務ID | 事務中的元素項 | 最小支持度過濾后 | 排序后 |
|---|---|---|---|
| 001 | r,z,h,j,p | r,z | z,r |
| 002 | z,y,x,w,v,u,t,s | z,y,x,t,s | z,x,y,s,t |
| 003 | z | z | z |
| 004 | r,x,n,o,s | r,x,s | x,s,r |
| 005 | y,r,x,z,q,t,p | y,r,x,z,t | z,x,y,r,t |
| 006 | y,z,x,e,q,s,t,m | y,z,x,s,t | z,x,y,s,t |
進行過濾和排序之后，就可以構建FP樹了全闷。從空集開始叉寂，不斷添加頻繁項集。如下圖总珠。
大致了解FP樹構建過程后屏鳍，接下來就是代碼實現(xiàn)了。
def createTree(dataSet, minSup=1):
headerTable = {}
# 第一次遍歷數(shù)據(jù)集局服，統(tǒng)計每個元素項出現(xiàn)的次數(shù)
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 移除不滿足最小支持度的項
for k in list(headerTable.keys()):
if headerTable[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]
print('headerTable: ',headerTable)
# 創(chuàng)建樹
retTree = treeNode('根節(jié)點', 0, None)
for tranSet, count in dataSet.items(): # 第二次遍歷數(shù)據(jù)集，構建樹
localD = {}
# 過濾頻繁項集
for item in tranSet:
if item in freqItemSet:
localD[item] = headerTable[item][0]
if len(localD) > 0:
# 排序
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
# 使用排序后的頻繁項集對樹進行填充
updateTree(orderedItems, retTree, headerTable, count)
return retTree, headerTable
def updateTree(items, inTree, headerTable, count):
# 檢查items[0]是否已在子節(jié)點
if items[0] in inTree.children:
inTree.children[items[0]].inc(count) # 是的話直接增加count
else: # 否則items[0]加到inTree.children
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
第一個函數(shù)createTree()有兩個參數(shù)淫奔，數(shù)據(jù)集和最小支持度山涡。這里支持度的定義跟Apriori算法的不一樣，是元素項出現(xiàn)的次數(shù)。樹構建過程中一共遍歷數(shù)據(jù)集兩次鸭丛。
為了FP樹生長（growth）竞穷，需調用updateTree()進行填充。也就是圖3的過程鳞溉。
updateHeader()函數(shù)用于更新頭指針表瘾带，確保節(jié)點鏈接指向樹中該元素項的每一個實例。
接下來熟菲，模擬一個簡單數(shù)據(jù)集月弛，并實際構建FP樹。
def createSimpDat():
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 transToDict(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
data = transToDict(createSimpDat())
FPTree, headerTable = createTree(data, 3)
看一下data
也就是前面表中的數(shù)據(jù)科盛。
再看一下FP樹
對照最開始的圖1帽衙，可以發(fā)現(xiàn)是一樣的結構。
構建好FP樹后贞绵，就可以使用它來進行頻繁項集挖掘了厉萝。
畫圖不易吖～都看到最后了，要不~點個贊榨崩？加波關注谴垫？
