[데이터마이닝] 연관규칙

연관규칙

연관규칙이란? 트랜잭션 집합이 주어졌을 때 트랜잭션에서 다른 항목들의 발생을 기반으로 항목의 발생을 예측하는 구간을 찾는 것

 

연관규칙의 활용

• 거래 형식의 데이터베이스에서 아이템 클러스터를 파악
• 어떤 제품들이 함께 구매되는 경향이 있는지 파악
• 교차 판매, 묶음 판매, 상품 진열, 거래 후 쿠폰 제공 등

 

용어 설명

• 항목 집합: 하나 이상의 항목 모음
  • k-항목집합: k개 항목들이 포함된 항목 집합
• 지지 횟수($\sigma$): 항목 집합의 출현 빈도
• 빈발 항목집합: minsup 임계값보다 크거나 같은 항목 집합
• 연관규칙: $X\to Y$형식의 함축적 표현식 ($X, Y$는 항목집합)
• 규칙 평가 척도
  • 지지도: 항목 집합을 포함하는 트랜잭션의 비율
  • 신뢰도: $X$가 포함된 트랜잭션에서 $Y$에 있는 항목이 나타나는 빈도 측정

 

연관규칙 생성

Ⅰ. 지지도(support): 교사건

빈발 아이템 세트에 기초하여 후보 규칙들의 집합을 결정

    지지도에 의해 결정 (대표 알고리즘은 Apriori)

    확률의 교사건

    전체 거래 중 조건부와 결론부를 모두 포함하는 거래의 비율

Ⅱ. 신뢰도(confidence): 조건부 확률

    규칙의 불확실성을 평가하기 위해 신뢰도 사용

    최소 기준 신뢰도 값을 설정

    조건부 확률

    조건부 아이템을 구매한 경우 이 중에서 얼마나 결론부 아이템을 구매할 것인지를 의미

Ⅲ. 향상도(lift)

    임의로 조합된 규칙과의 비교를 통해 해당 규칙이 얼마나 실제적인 연관성을 가지고 있는지 파악, 1보다 큰 값을 가짐

 

Note! 후보 규칙 생성

아이템 사이의 규칙들을 if-then으로 표시

if 조건부 then 결론부
{item set A} → {item set B}

Apriori 알고리즘을 이용하여 빈도수가 높은 조합을 생성한다 (지지도 이용)

 

---

Apriori 알고리즘

가장 먼저 개발된 연관 규칙 찾기 알고리즘

연관규칙을 찾기 위해 가장 먼저 아이템들 간의 연관성을 나타내기 위한 후보가 되는 모든 규칙들을 생성

단일 아이템 세트→2개로 된 아이템 세트→3개로 된 아이템 세트... 이런 방식으로 아이템 세트를 찾아낸다

목적: 빈발 아이템 세트를 찾아내는 것

주의!! 기준에 미달하는 아이템 세트가 있는 경우 상위 집합에 해당 아이템 세트를 포함한 집합은 생성하지 않음

 

향상도(lift)

정의 : 아무 조건 없이 결론부 아이템을 구매할 확률의 비에 대한 조건부 아이템을 구매할 경우 결론부 아이템을 구매한 확률의 비율

 

지지도(S): 전체 거래 중에서 얼마나 발생 빈도가 높은가?

신뢰도(C): A를 구매한 사람이 B를 살 확률은?

향상도(L): 그냥 B를 구매할 때보다 A를 구매한 사람이 B를 구매할 확률이 얼마나 높은가?

$Support(A \rightarrow B)$	$Confidence(A\rightarrow B)$	$Lift(A\rightarrow B)$
$P(A\cap B)$	$\frac{Support}{P(A)}$	$\frac{Confrdence}{P(B)}=\frac{P(B|A)}{P(B)}$

 

---

추천 시스템

추천 시스템이란? 유저의 선호도 및 과거 행동을 바탕으로 개인에 맞는 관심사나 아이템을 제공하는 것

추천 시스템에는 콘텐츠 기반 필터링과 협업 필터링, 그리고 둘을 합친 하이브리드 방식이 있다.

 

(1) 콘텐츠 기반 필터링

콘텐츠를 기반으로 분석하여 추천해주는 방식

사용자가 관심 분야에 대해 직접 입력한 정보나 구매 내역, 평점 등을 기반으로 선호 아이템을 파악한 후 선호 아이템과 가장 유사한 다른 아이템 추천

• 장점
  • 아이템의 속성(컨텐츠)을 기반으로 추천하기 때문에 이전에 선택 이력이 없는 아이템도 추천 가능
• 단점
  • 해당 고객에 대한 데이터가 부족한 경우 성능 보장이 어려움
  • 과도한 특수화(이전에 구매한 아이템과 비슷한 것들만 추천)

 

(2) 협업 필터링

특정 아이템에 대해 선호도가 유사한 고객들은 다른 아이템에 대해서도 비슷한 선호도를 보일 것이다라는 아이디어를 기반으로 추천

사용자들의 다양한 선호도를 고려하여 방대한 양의 아이템 세트로부터 연관성 있는 아이템을 추천

사용자 기반과 아이템 기반으로 나눌 수 있으며 두 방법 모두 코사인 유사도를 사용한다.

$$Sim(A,B)=cos(\theta)=\frac{A\cdot B}{\left\|A\right\| \left\|B\right\| }= \frac{\sum_{i=1}^{n}A_i\times B_i}{\sqrt{\sum_{i=1}^{n}(A_i)^{2}}\times \sqrt{\sum_{i=1}^{n}(B_i)^{2}}}$$

사용자 기반

사용자 간의 유사도를 측정하여 유사도 높은 이웃이 선택한 아이템 중에서 추천 (당신과 비슷한 고객들이 다음 상품도 구매!)

▶ 행끼리 유사도 계산

▶ 가장 유사한 사용자의 점수를 그대로 사용하거나 

▶ 유사도에 아이템 값을 곱해 모든 사용자의 정보를 사용할 수 있음

 

아이템 기반

아이템 간 유사도를 측정하여 유사도 높은 아이템을 추천 (이 상품을 선택한 다른 고객들은 다음 상품도 구매!)

▶ 열끼리 유사도 계산

▶ 가장 유사한 아이템의 점수를 그대로 사용하거나

▶ 유사도에 사용자 값을 곱해 모든 사용자의 정보를 사용할 수 있음 

The collaborative filtering algorithms: (a) user-based; (b) item-based. )