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

전편 에 서 는FP 트 리 구축 방법FP 트 리 의 모든 경로 가 최소 지지 도 를 만족 시 키 는 것 을 소개 했다.우리 가 해 야 할 일 은 한 경로 에서 더 많은 관련 관 계 를 찾 는 것 이다.
추출 조건 모드 베이스
우선 FP 트 리 포인터 의 단일 빈번 한 요소 항목 부터 시작 합 니 다.모든 요소 항목 에 대해 해당 하 는 조건 모드 기반(conditional pattern base)을 얻 고 하나의 요소 항목 의 조건 모드 기반,즉 요소 항목 의 키워드 입 니 다.조건 부 모드 기 는 찾 은 요소 항목 을 마지막 으로 하 는 경로 집합 입 니 다.모든 경 로 는 이전 종료 경로(perfix path)입 니 다.쉽게 말 하면 하나의 접두사 경 로 는 소 이 소 항목 과 나무 뿌리 노드 사이 에 있 는 모든 내용 입 니 다.
다음 그림 은{s:2}또는{r:1}을 요소 항목 으로 하 는 접두사 경로 입 니 다.

{s}의 조건 모드 기반,즉 접두사 경로 집합 은 모두 두 가지 가 있 습 니 다.{z,x,y,t},{x};{r}의 조건 모드 기 는 모두 세 개 입 니 다.{{z},{z,x,y,t},{x,s}}.
조건 부 패턴 기반 을 찾 는 과정 은 실제로 FP 나무의 모든 잎 노드 에서 뿌리 노드 로 거 슬러 올 라 가 는 과정 이다.우 리 는 헤드 포인터 목록 헤드 테이블 을 통 해 시작 하여 포인터 연결 을 통 해 모든 루트 노드 에 빠르게 접근 할 수 있 습 니 다.아래 표 는 위의 FP 트 리 의 모든 조건 모드 기반 입 니 다.

창설 조건 FP 트 리
더 많은 빈번 한 항목 집합 을 발견 하기 위해 서 는 모든 빈번 한 항목 에 조건 FP 트 리 를 만들어 야 합 니 다.방금 발 견 된 조건 모드 기반 을 입력 데이터 로 사용 하고 같은 트 리 코드 를 통 해 트 리 를 구축 할 수 있 습 니 다.그 다음 에 반복 적 으로 빈번 한 항목 을 발견 하고 조건 모델 기 를 발견 하 며 다른 조건 나 무 를 발견 했다.
빈번 한 항목 r 를 예 로 들 어 r 에 대한 조건 FP 트 리 를 구축 합 니 다.r 의 세 개의 접두사 경 로 는 각각{z},{z,x,y,t},{x,s}이 고 최소 지지 도 minSupport=2 를 설정 하면 y,t,s 가 걸 러 지고 나머지{z},{z,x},{x}이다.y,s,t 는 조건 모드 기반 의 일부분 이지 만 조건 FP 트 리 에 속 하지 않 습 니 다.즉,r 에 게 는 빈번 하지 않 습 니 다.아래 그림 에서 보 듯 이 y→t→r 와 s→r 의 전체 지지 도 는 1 이기 때문에 y,t,s 는 r 의 조건 트 리 에 있어 빈번 하지 않다.

필터 후의 r 조건 트 리 는 다음 과 같 습 니 다:

위의 절 차 를 반복 합 니 다.r 의 조건 모드 기 는{z,x},{x}입 니 다.최소 지원 도 를 만족 시 킬 수 있 는 경로 가 없 기 때문에 r 의 조건 트 리 는 하나 밖 에 없습니다.주의해 야 할 것 은{z,x},{x}에 모두 두 개의 x 가 존재 하지만{z,x}에서 z 는 x 의 부모 노드 입 니 다.구조 조건 FP 트 리 에서 부모 노드 를 직접 제거 할 수 없고 하위 노드 부터 한 단계 씩 제거 할 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:

def ascendTree(leafNode, prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)
def findPrefixPath(basePat, headTable):
    condPats = {}
    treeNode = headTable[basePat][1]
    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=1, preFix=set([]), freqItemList=[]):
    # order by minSup asc, value asc
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: (p[1][0],p[0]))]
    for basePat in bigL:
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        #               
        condPattBases = findPrefixPath(basePat, headerTable)
        myCondTree, myHead = createTree(condPattBases, minSup)
        if myHead != None:
            print('condPattBases: ', basePat, condPattBases)
            myCondTree.disp()
            print('*' * 30)
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
simpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()
condPats = findPrefixPath('z', myheader)
print('z', condPats)
condPats = findPrefixPath('x', myheader)
print('x', condPats)
condPats = findPrefixPath('y', myheader)
print('y', condPats)
condPats = findPrefixPath('t', myheader)
print('t', condPats)
condPats = findPrefixPath('s', myheader)
print('s', condPats)
condPats = findPrefixPath('r', myheader)
print('r', condPats)
mineTree(myFPTree, myheader, 2)

콘 솔 정보:

총결산
이 글 은 여기까지 입 니 다.이 예 는 두 개의 빈번 한 항목 집합{z,x}과{x}을 발견 할 수 있 습 니 다.빈번 한 항 집 을 얻 은 후에 신뢰 도 에 따라 관련 규칙 을 발견 할 수 있다.이 단 계 는 비교적 간단 하 므 로 전편 의 관련 내용 을 참고 하여 군말 하지 않 아 도 된다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 다른 멋 진 내용 에 많은 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!