FP-growth 알고리즘 빈번 한 항목 집합 발견-FP 트 리 구축

FP 는 빈번 한 모드(Frequent Pattern)를 대표 하고 알고리즘 은 주로 두 단계 로 나 뉜 다.FP-tree 구축,빈번 한 항목 발굴 집합 이다.
FP 트 리 표현법
FP 트 리 는 사 무 를 하나씩 읽 고 FP 트 리 에 비 친 경 로 를 통 해 구성 합 니 다.서로 다른 업무 에 몇 개의 같은 항목 이 있 을 수 있 기 때문에,그들의 경 로 는 부분적으로 중 첩 될 수 있다.경로 가 서로 겹 칠 수록 FP 트 리 구 조 를 사용 하면 압축 효과 가 좋 습 니 다.만약 FP 트 리 가 충분 하 게 작 아서 메모리 에 저장 할 수 있다 면,이 메모리 의 구조 에서 빈번 한 항목 집합 을 직접 추출 할 수 있 으 며,하드디스크 에 저 장 된 데 이 터 를 다시 스 캔 하지 않 아 도 된다.
다음 그림 과 같은 FP 트 리:

일반적으로 FP 트 리 의 크기 는 압축 되 지 않 은 데이터 보다 작 습 니 다.데이터 의 사 무 는 항상 공통 항목 을 공유 하기 때 문 입 니 다.가장 좋 은 상황 에서 모든 사 무 는 같은 항목 집합 을 가지 고 있 습 니 다.FP 트 리 는 하나의 노드 경로 만 포함 합 니 다.모든 사무 가 유일한 항목 집합 을 가지 고 있 을 때 최 악의 상황 이 발생 합 니 다.사무 에 공 통 된 항목 이 포함 되 어 있 지 않 기 때문에 FP 트 리 의 크기 는 실제 적 으로 원래 데이터 의 크기 와 같 습 니 다.
FP 나무의 뿌리 노드 용φ나머지 노드 는 하나의 데이터 항목 과 이 데이터 항목 이 이 경로 에서 의 지원 도 를 포함한다.모든 경 로 는 하나의 훈련 데이터 에서 최소 지원 도 를 만족 시 키 는 데이터 항목 집합 이다.FP 트 리 는 같은 항목 을 링크 로 연결 하고 위의 그림 에서 파란색 연결선 으로 표시 합 니 다.
트 리 의 같은 항목 에 빠르게 접근 하기 위해 서 는 같은 항목 을 가 진 노드 를 연결 하 는 포인터 목록(head Table)을 유지 해 야 합 니 다.모든 목록 요 소 는 데이터 항목,이 항목 의 전체 최소 지지 도,FP 트 리 에 있 는 이 목걸이 표 의 표 두 를 가리 키 는 지침 을 포함 합 니 다.

FP 트 리 구축
현재 다음 과 같은 데이터 가 있 습 니 다.
　　
FP-growth 알고리즘 은 FP 트 리 를 구축 하기 위해 원본 훈련 집 을 두 번 스 캔 해 야 합 니 다.
첫 번 째 스 캔 은 최소 지지 도 에 만족 하지 않 는 모든 항목 을 걸 러 냅 니 다.최소 지원 도 를 만족 시 키 는 항목 에 대해 서 는 전체 최소 지원 도 에 따라 순 위 를 매 깁 니 다.이 를 바탕 으로 처리 가 편리 하도록 항목 의 키워드 에 따라 다시 정렬 할 수 있 습 니 다.

첫 번 째 스 캔 결과
두 번 째 스 캔,구조 FP 트 리.
스 캔 에 참여 한 것 은 필터 후의 데이터 입 니 다.만약 에 데이터 항목 이 처음 만나면 이 노드 를 만 들 고 헤드 테이블 에 이 노드 를 가리 키 는 지침 을 추가 합 니 다.그렇지 않 으 면 경로 에 따라 해당 하 는 노드 를 찾 아 노드 정 보 를 수정 합 니 다.구체 적 인 과정 은 다음 과 같다.

사무 001,{z,x}

사무 002,{z,x,y,t,s}

사무 003,{z}

사무 004,{x,s,r}

사무 005,{z,x,y,t,r}

사무 006,{z,x,y,t,s}
위 에서 보 듯 이 헤드 테이블 은 FPTree 와 함께 만 든 것 이 아니 라 첫 번 째 스 캔 때 이미 만 들 어 졌 으 며,FPTree 를 만 들 때 해당 노드 를 가리 키 기만 하면 된다.사무 004 부터 노드 간 의 연결 을 만 들 고 서로 다른 경로 의 같은 항목 을 링크 로 연결 해 야 합 니 다.
코드 는 다음 과 같 습 니 다:

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:
        fset = frozenset(trans)
        retDict.setdefault(fset, 0)
        retDict[fset] += 1
    return retDict
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        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)

def createTree(dataSet, minSup=1):
    headerTable = {}
    #        ，            
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + 1
    #         
    lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))
    for k in lessThanMinsup: del(headerTable[k])
    freqItemSet = set(headerTable.keys())
    #               ，  None, None
    if len(freqItemSet) == 0:
        return None, None
    for k in headerTable:
        headerTable[k] = [headerTable[k], None]
    retTree = treeNode('φ', 1, None)
    #        ，  fp-tree
    for tranSet, count in dataSet.items():
        #               ，key:        ，value:          
        localD = {}
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0]
        if len(localD) > 0:
            #                    ,    order by p[1] desc, p[0] desc
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable

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)
        if headerTable[items[0]][1] == None:  # update header table
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    if len(items) > 1:  # call updateTree() with remaining ordered items
        updateTree(items[1:], inTree.children[items[0]], headerTable, count)

def updateHeader(nodeToTest, targetNode):  # this version does not use recursion
    while (nodeToTest.nodeLink != None):  # Do not use recursion to traverse a linked list!
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode
simpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()

위의 코드 는 첫 번 째 스 캔 후 모든 훈련 데 이 터 를 걸 러 낸 항목 의 정렬 이 아니 라 두 번 째 스 캔 에 정렬 을 두 었 을 때 코드 의 복잡 도 를 간소화 할 수 있다.
콘 솔 정보:

항목 의 순서 가 FP 트 리 에 미 치 는 영향
주의해 야 할 것 은 항목 의 키워드 정렬 이 FP 트 리 의 구조 에 영향 을 줄 수 있다 는 점 이다.아래 두 그림 은 같은 훈련 집합 에서 생 성 된 FP 트 리 로 그림 1 은 최소 지지 도 에 따라 정렬 하 는 것 을 제외 하고 항목 에 대해 어떠한 처리 도 하지 않 았 다.그림 2 는 항목 을 키워드 에 따라 내림차 순 으로 정렬 했다.나무의 구조 도 후속 발견 빈번 한 항목 의 결과 에 영향 을 줄 것 이다.

그림 1 항목 에 대한 키워드 정렬 되 지 않 음

그림 2 항목 의 키워드 내림차 순 정렬
총결산
본 파 의 글 은 여기까지 입 니 다.다음 편 은 계속 하 겠 습 니 다.빈번 한 항목 집 을 어떻게 발견 하 는 지 소개 하 겠 습 니 다.도움 이 되 셨 으 면 좋 겠 습 니 다.저희 의 더 많은 내용 에 관심 을 가 져 주 셨 으 면 좋 겠 습 니 다!