연관 규칙(Assicuation Rule) : 특정 사건이 발생했을 때 함께 빈번하게 발생하는 또 다른 사건의 규칙을 의미

support(지지도)

: 전체 거래 중 항목 A와 항목 B를 동시에 포함하는 거래의 비율

confidence(신뢰도)

: 항목 A가 포함된 거래 중에서 B도 포함하는 거래의 비율(A가 등장했을 때 B가 등장할지에 대한 조건부 확률)

lift(향상도)

: 두 사건이 동시에 얼마나 발생하는지에 대한 비율(B가 혼자 등장한 확률과 A→B가 등장한 확률을 비교하여 A, B간 상관성을 측정)

예시)

연관규칙 탐색

• Brute-force : 가능한 모든 연관 규칙에 대해 support와 confidence를 계산

• Apriori 알고리즘 : 가지치기를 통해 탐색해야 하는 itemset 개수(M)을 줄이는 방법

  • 빈번하지 않은 itemset은 하위 itemset 또한 빈번하지 않을 것이라고 가정

    

• DHP 알고리즘 : 탐색하는 transaction의 숫자(N)를 줄이는 방법

• FP-Growth : 효율적인 자료구조(FP 트리)를 사용하여 탐색횟수(NM)를 줄이는 방법

  • 트리, 링크드리스트 사용
  • 빈발패턴을 찾기위해 Apriori처럼 전체 트리를 탐색하지 않고,Header table(hash)에서 해당 item을 찾아 Linked-list를 통해 차례로 접근하면 되기에 속도상 엄청난 이득을 가져올 수 있음

    • 아이템을 빈도 순으로 정렬하고, 이 순서를 기준으로 interaction을 트리에 넣음