FP - growth 알고리즘
FP 트 리
FP - growth 알고리즘 은 데 이 터 를 FP 트 리 라 는 치밀 한 데이터 구조 에 저장 합 니 다.FP 트 리 는 컴퓨터 의 다른 트 리 구조 와 유사 해 보이 지만 링크 (link) 를 통 해 비슷 한 요 소 를 연결 합 니 다. 연 결 된 요소 항목 은 링크 로 볼 수 있 습 니 다.
검색 트 리 와 달리 하나의 요소 항목 은 FP 트 리 에 여러 단어 가 나타 날 수 있 습 니 다.FP 트 리 는 항목 집합 이 나타 나 는 빈 도 를 저장 하고 모든 집 회 는 경로 로 트 리 에 저 장 됩 니 다.비슷 한 요소 가 존재 하 는 집합 은 나무의 일부분 을 공유 합 니 다.집합 사이 가 완전히 다 를 때 만 나무 가 갈 라 진다.트 리 노드 에 집합 중의 단일 요소 와 그 서열 에서 의 출현 횟수 를 제시 하고 경 로 는 이 서열 의 출현 횟수 를 제시한다.
비슷 한 항목 간 의 링크 는 노드 링크 (node link) 로 비슷 한 항목 의 위 치 를 신속하게 발견 하 는 데 사 용 됩 니 다.
FP - growth 알고리즘 의 작업 절 차 는 다음 과 같다. 먼저 FP 트 리 를 구축 한 다음 에 이 를 이용 하여 빈번 한 항목 집합 을 발굴 한다.FP 트 리 를 구축 하기 위해 서 는 데이터 세트 를 두 번 스 캔 해 야 합 니 다.처음으로 모든 원소 항목 의 출현 횟수 를 계산 하여 출현 빈 도 를 통계 하 였 다.두 번 째 스 캔 은 어떤 빈번 한 요소 만 을 고려 합 니까?
코드 목록
코드 와 사 고 는 에서 나 왔 습 니 다. 책 에서 코드 python 2, 제 가 사용 하 는 python 3 을 고 쳤 습 니 다.
# -*- coding: utf-8 -*-
# ,
# FP
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue
self.count = numOccur
self.nodeLink = None # nodeLink
self.parent = parentNode #
self.children = {} # ,
def inc(self, numOccur): # 1
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-tree
def createTree(dataSet, minSup=1):
headerTable = {}
for trans in dataSet: # :
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# , : [ ]=
for k in list(headerTable): #
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)
retTree = treeNode('Null Set', 1, None) # tree
for tranSet, count in dataSet.items(): # :
localD = {}
for item in tranSet: # put transaction items in order
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) # populate tree with ordered freq itemset
return retTree, headerTable #
def updateTree(items, inTree, headerTable, count):
if items[0] in inTree.children: #
inTree.children[items[0]].inc(count) #
else: #
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)
# 。
# nodeLink , nodeLink
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
# createInitSet()
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)
def findPrefixPath(basePat, treeNode): # : , ;
condPats = {}
while treeNode != None:
prefixPath = []
ascendTree(treeNode, prefixPath) #
if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = treeNode.count #
treeNode = treeNode.nodeLink
return condPats
#
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
# ,
bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: str(p[1]))] # python3
for basePat in bigL: #
#
newFreqSet = preFix.copy()
newFreqSet.add(basePat)
# print ('finalFrequent Item: ',newFreqSet)
freqItemList.append(newFreqSet)
#
condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
# print ('condPattBases :',basePat, condPattBases)
# 2. Tree
myCondTree, myHead = createTree(condPattBases, minSup)
# fp-tree
# print ('head from conditional tree: ', myHead)
if myHead != None: # 3.
# print('conditional tree for: ', newFreqSet)
myCondTree.disp(1)
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
# rootNode = treeNode('pyramid', 9, None)
# rootNode.children['eye'] = treeNode('eye', 13, None)
# print(rootNode.disp())
# rootNode.children['phoenix'] = treeNode('phoenix', 3, None)
# print(rootNode.disp())
#
simpData = loadSimpDat()
# print(simpData)
#
initSet = createInitSet(simpData)
# print(initSet)
myFPtree, myHeaderTab = createTree(initSet, 3)
# print(findPrefixPath('x', myHeaderTab['x'][1]))
# print(findPrefixPath('z', myHeaderTab['z'][1]))
# , ,
# print(findPrefixPath('r', myHeaderTab['r'][1]))
freqItems = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)
print(freqItems)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.