연관분석(Association Analysis) 알고리즘

장바구니 분석 또는 서열 분석이라고도 불러용

데이터베이스 내에서 상품의 구매, 조회 등 연속된 거래들 사이의 규칙을 발견하기 위해 사용합니당

Example
1. 맥주와 기저귀를 같이 구매하는 빈도는?
2. 컴퓨터를 산 고객이 다음에 가장 많이 사는 상품은?

연관 규칙 분석(Association Rule Mining)

주어진 거래Transaction 데이터에 대해서 하나의 상품 등장 시 다른 상품이 같이 등장하는 규칙을 찾는 것입니다.

Transcation	Items
1	{빵, 우유}
2	{빵, 기저귀, 맥주, 계란}
3	{우유, 기저귀, 맥주, 콜라}
4	{빵, 우유, 기저귀, 맥주}
5	{빵, 우유, 기저귀, 콜라}

1. {기저귀} -> {맥주}
2. {우유, 빵} -> {계란, 콜라}
3. {맥주, 빵} -> {우유}
   여기서 화살표는 인과 관계가 아닌 연관 규칙입니다. '반드시'가 아닌 그럴 확률에 높다고 보면 됩니당.

용어 정리 들어갑니당(feat. Metaphor)

우선 해당 알고리즘에서 사용되는 몇 용어가 있습니당. 이것부터 정리해보졉

규칙 : IF condition THEN result $\Rightarrow$ {A} $\to$ {B} 형식으로 표현
연관 규칙 : 특정 사건 발생 시 함께 빈번하게frequently 발생하는 또 다른 사건의 규칙을 의미

IF part = antecedent, THEN part = consequent

itemset = antecedent와 consequent를 이루는 상품의 set
(antecedent와 consequent는 서로소disjoint를 만족)

Example)
antecedent : {빵, 버터}, consequent : {우유} $\Rightarrow$ confident factor = 90%

자 어느정도 정리됐으니 다음으로 갑니당!

빈발 집합(Frequent Itemset)

Itemset

• 1개 이상의 item의 집합set
• k-itemset : k개의 item으로 이뤄진 itemset

Support count($\sigma$)

• 전체 transaction data에서 itemset이 등장하는 횟수
  ex. $\sigma(\text{{빵, 우유}})=3$

Support

• itemset이 전체 transaction data에 등장하는 비율
  ex. $\text{support({빵, 우유})} = \frac{3}{5} = 0.6$

Frequent itemset

• 유저가 지정한 최소 support 값 이상의 itemset
• Infrequent itemset은 반대로 유저가 지정한 최소 support보다 작은 itemset

연관규칙의 척도: support, confidence, lift

Frequent itemset들 사이의 연관 규칙을 만들기 위해선 척도measurement가 필요합니당. 그게 제목에서 언급된 support, confidence, lift입니당!

Support

• 두 itemset X, Y를 모두 포함하는 transaction의 비율
• 전체 transaction에 대한 itemset의 확률값
• support는 '빈도가 높거나, 구성 비율이 높은' 좋은 규칙을 찾거나, 불필요한 연산을 줄일 때 사용됩니다.

$s(X) = \frac{n(X)}{N} = P(X)\\ s(X \rightarrow Y) = \frac{n(X \cup Y)}{N}=P(X \cap Y)$

Confidence

• X를 포함하는 transaction 가운데 Y도 포함하는 transaction 비율(조건부 확률)
• confidence가 높을 수록 유용!

$c(X \to Y) = \frac{n( X \cup Y)}{n(X)} = \frac{s(X \to Y)}{s(X)} = \frac{P(X \cap Y)}{P(X)} = P(Y \vert X)$

lift

• $\frac{\text{[X가 포함된 `transaction` 가운데 Y가 등장될 확률]}}{\text{[Y가 등장할 확률]}}$
• lift가 1 $\to$ X, Y는 독립
• lift가 1 보다 큶 $\to$ 두 상품의 양의 상관관계를 가짐, 1 보다 작음 $\to$음의 상관관계를 가짐

$l(X \to Y) = \frac{P(X \cap Y)}{P(X)P(Y)} = \frac{x(X \to Y)}{s(X)s(Y)} = \frac{c(X \to Y)}{s(Y)}$

요 알고리즘은 일반적으로 confidence로 정렬하고, lift로 cutoff하는 방식으로 Top K을 설정한다고 합니당!

예시

위에 언급된 방식에 대한 예시를 살짝 정리해보면,

Transcation	Items
1	{맥주, 우유}
2	{빵, 기저귀, 맥주, 계란}
3	{우유, 기저귀, 맥주, 콜라}
4	{빵, 우유, 기저귀, 맥주}
5	{빵, 우유, 기저귀, 콜라, 계란}

{빵(X)} $\to$ {계란(Y)}

support

$s(X \rightarrow Y) = \frac{n(X \cup Y)}{N}=P(X \cap Y)\\ = \frac{n(2, 5)}{5} = 0.4$

confidence

$c(X \to Y) = \frac{n( X \cup Y)}{n(X)} = \frac{n(2,5)}{n(2,4,5)} = 0.66\\ = P(Y \vert X) = \frac{P(X \cap Y)}{P(X)} = \frac{0.4}{0.6} = 0.66$

lift

$l(X \to Y) = \frac{c(X \to Y)}{s(Y)} = \frac{0.66}{0.4} = 1.66 \ = \frac{x(X \to Y)}{s(X)s(Y)} = \frac{0.4}{0.6 \cdot 0.4} = 1.66$

이렇게 됩니당!

support, confidence, lift 사용법

가능한 itemset에 대해서 rule은 기하급수적으로 많아진다고 합니당. 따라서 유의미한 rule만 사용하도록 해야 합니당

사용법
1. 최소한의 support, 최소한의 condfidence로 의미 없는 rule을 screen out!
$\to$전체 transcation 중에서 너무 적게 등장하거나, 조건부확률이 아주 낮은 rule 필터링
2. lift 값으로 내림차순 정렬을 하여 의미 있는 rule을 평가
$\to$lift가 크다는 것은 rule을 구상하는 antecedent와 consequent가 연관성이 높고 유의미하다는 의미!

오늘은 여기까지 정리하겠습니당! 다음을 기대해주세요!

github: https://github.com/pray92/recommendation_system