고전적인 추천 알고리즘: 연관 규칙 기반 추천 (Association Rule Mining)

추천 시스템은 다양한 알고리즘을 기반으로 작동하지만, 그중에서도 **연관 규칙 기반 추천(Association Rule Mining)**은 단순하면서도 강력한 고전적인 추천 방식 중 하나입니다. 이번 글에서는 연관 규칙 기반 추천의 개념, 주요 용어, 성능 지표, 알고리즘 등을 다루어 보겠습니다.

 

1. 연관 규칙 기반 추천이란?

연관 규칙 기반 추천은 거래 데이터를 분석하여 "A를 산 사람은 B도 산다"라는 규칙을 발견하고, 이를 바탕으로 추천을 제공하는 기법입니다.
예를 들어:

"기저귀를 샀던 김 씨는 맥주도 샀다. 당신도 기저귀를 샀으니 맥주를 사는 게 어떨까요?"

이 기법은 Market Basket Analysis 또는 Affinity Analysis로도 불리며, 다음과 같은 특징을 가집니다:

• 특정 도메인에서는 복잡한 알고리즘보다 더 단순하면서도 효율적인 결과를 제공.
• 대규모 데이터에서 자주 등장하는 아이템 간의 관계를 분석하여 규칙 생성

2. 주요 용어

1. 조건절 (Antecedent)
   • 규칙에서 "A를 사면"에 해당하는 부분.
   • IF에 해당.
2. 결과절 (Consequent)
   • 규칙에서 "B도 산다"에 해당하는 부분.
   • THEN에 해당.
3. 아이템 셋 (Item Set)
   • 조건절과 결과절을 구성하는 상품의 집합.
   • 단, 조건절과 결과절은 상호 배타적이어야 함.
   • 예: (햇반, 김치) → (맥주, 땅콩)은 가능하지만,
     (맥주, 땅콩) → (맥주, 기저귀)는 불가능.

3. 규칙 성능 지표

연관 규칙의 유효성을 평가하기 위해 다음과 같은 지표를 사용합니다:

1. 지지도(Support)
   • 특정 상품 조합이 전체 데이터에서 등장하는 빈도.
   • 예: "기저귀와 맥주"가 함께 등장한 비율.
2. 신뢰도(Confidence)
   • 조건절이 만족될 때, 결과절도 함께 만족될 확률.
   • 예: "기저귀를 샀을 때, 맥주도 샀을 확률."
3. 향상도(Lift)
   • 조건절과 결과절이 독립적일 때보다 얼마나 더 자주 함께 등장하는지.
   • Lift가 1보다 크면 두 상품 간 연관성이 있다고 볼 수 있음.
4. 레버리지(Leverage)
   • 두 상품이 함께 등장하는 것이 얼마나 유의미한지 측정.

4. 알고리즘 개요

연관 규칙 추천은 대규모 데이터를 처리해야 하기 때문에, 효율적인 규칙 생성 알고리즘이 필요합니다. 대표적인 알고리즘은 다음과 같습니다:

4-1. Brute Force (무차별 탐색)

• 방법: 가능한 모든 조합을 탐색하여 규칙 생성.
• 장점: 최적의 규칙을 찾을 가능성이 높음.
• 단점: 데이터 규모가 크면 계산량이 기하급수적으로 증가.

4-2. A priori

• 방법: 빈번하게 등장하는 아이템 셋만 고려하여 규칙 생성.
• Anti-monotone Property를 활용하여 계산량을 줄임:
  • 특정 아이템 셋이 빈번하지 않다면, 그 아이템 셋을 포함하는 모든 조합도 빈번하지 않음.
• 장점: Brute Force 대비 연산 효율성이 높음.

5. 입력 데이터의 형태

연관 규칙 분석에 사용되는 데이터는 장바구니 데이터 형태로 구성됩니다.

• 장바구니 형태: 각 거래(Transaction)별로 구매한 상품 목록을 나열.
  • 예: Transaction 1 → {햇반, 김치, 맥주}
• 행렬 형태: 거래와 상품의 관계를 0과 1로 표현.
  • 예:Transaction햇반김치맥주

    1	1	1	1
    2	0	1	1

6. 연관 규칙 추천의 장단점

장점

1. 단순하면서도 직관적인 방식으로 유용한 규칙을 발견할 수 있음.
2. 특정 도메인에서는 복잡한 머신러닝 모델보다 효율적으로 작동.
3. 대규모 거래 데이터를 활용해 제품 간 관계를 파악.

단점

1. 콜드 스타트 문제: 신규 상품이나 드물게 구매되는 상품에 대한 규칙 생성이 어려움.
2. 계산량이 많아질 수 있으므로 데이터 전처리 및 필터링 필요.