[RecSys] 연관 분석 | Association Analysis | 장바구니 분석 | 서열 분석 | support | confidence | lift

연관 분석(Association Rule Analysis, Association Rule Minig)

• 주어진 거래(Transaction) 데이터에 대해서, 하나의 상품이 등장했을 때 다른 상품이 같이 등장하는 규칙을 찾는 알고리즘
• 장바구니 분석 혹은 서열 분석이라고 하기도 함

 

빈발 집합(Frequent Itemset)에 대한 이해

• k-Itemset: k개의 item으로 이루어진 itemset (k≥1)
• Support Count: 전체 거래 데이터에서 itemset이 등장하는 횟수
• Support (Ratio): itemset이 전체 거래 데이터에서 등장하는 비율
• Frequent Itemset: 엔지니어가 지정한 min support 값 이상의 itemset

 

 

연관 규칙의 기본 척도

frequent itemset(X, Y)들 사이에 연관 규칙을 찾기 위한 기본 척도

• support
  • 전체 거래 데이터에서 두 itemset X, Y를 모두 포함하는 거래 비율
  • 빈도나 구성 비율이 높은 규칙을 찾아서 불필요한 연산을 줄이는데 사용
• confidnece
  • itemset X가 포함된 거래 데이터 가운데, Y도 포함하는 거래의 비율 (Y의 X에 대한 조건부 확률)
  • confidence가 높을수록 유용한 규칙을 뜻함
• lift
  • Y의 X에 대한 조건부 확률(confidence) ÷ Y가 등장할 확률
  • lift > 1 : X, Y가 양의 상관 관계를 가짐
  • lift = 1 : X, Y는 독립
  • lift < 1: X, Y가 음의 상관 관계를 가짐

 

연관 규칙 탐색의 사용방법

1. 의미없는 규칙(rule)을 제외해야 함(screen out)
   • item의 수가 많아질수록 rule도 기하급수적으로 많아지기 때문에 screen out 필요
   • min support, min confidence를 이용하여 전체 거래 데이터에서 너무 적게 등장하거나 조건부 확률이 아주 낮은 규칙을 제거
2. lift 값으로 내림차순 정렬을 하야 의미있는 규칙(rule)을 평가 및 선정
   • lift가 크다는 것은 규칙을 구성하는 선행과 결과가 연관성이 높고 유의미하다는 것으로 해석할 수 있음

 

 

그렇다면 min support / min confidence를 만족하는 모든 규칙을 어떻게 찾을 것인가?

• Brute-force approach
  1. 가능한 연관 규칙을 모두 나열
  2. 모든 연관 규칙에 대해서 개별 support와 confidence 계산
  3. min support & min confidence를 만족하는 규칙만 남기고 모두 prunning
  → 아이템이 늘어날수록 연관 규칙의 개수는 기하급수적으로 증가하기 때문에, 연산량에 매우 큰 부담이 됨

 

 

어떻게 규칙을 계산하는 Cost를 줄일 것인가?

• Frequent Itemset Generation: min support 이상의 모든 itemset 생성
  • 가능한 후보 itemset의 개수를 줄인다 → Apriori 알고리즘: 가지치기를 활용하여 탐색해야 하는 M을 줄인다
  • 탐색하는 transaction의 숫자를 줄인다 → itemset의 크기가 커짐에 따라 전체 N개 transaction보다 적은 개수를 탐색한다 → DHP(Direct Hashing & Pruning) 알고리즘
  • 탐색 횟수를 줄인다 → 효율적인 자료구조를 사용하여 후보 itemset과 transaction을 저장하고, 해당 데이터에 대해서만 탐색한다 → FP-Growth 알고리즘
• → 가장 computation cost가 크므로, 이 부분을 최적화 해야함
• Rule Generation: min confidence 이상의 연관 규칙 생성 → 이 때 규칙의 선행과 결과는 서로소를 만족해야 함