연관 규칙 분석 / support, confidence, lift

 연관 규칙 분석 

 

출처:https://www.bankrate.com/finance/credit-cards/how-to-grocery-shop-during-a-recession/

 

 

이전 글에서 보았던 가장 기본적인 인기도 기반의 추천 시스템과는 달리 아이템 간의 연관성을 파악하여 추천을 진행하는 것을 연관 규칙 분석이라고 한다. 다른 말로는 장바구니 분석 또는 서열 분석이라고도 하는데, 장바구니 분석이라고 말하는 것은 마트에 장을 보러 가는 것을 떠올려 보면 된다. 장바구니 안에 여러 개의 상품들이 담겨있는데, 이 상품들 간의 연관성을 찾아내고자 하는 것이다. 같이 구매되는 상품은 무엇인지 아니면 꼭 같이 등장하는 상품이 있지는 않은지 파악하는 것이다.

 

 

 

 

마트에서 구매한 장바구니 목록을 계속 예시를 들어 설명하자면, 5명의 사람이 구매한 아이템 목록이 아래와 같다고 생각해보자. 여기서 각 사용자가 구매한 아이템 목록 즉, 거래내역을 Transaction 이라고 부르게 된다. 이어서 아래의 구매 목록을 바탕으로 같이 많이 등장하는 아이템들이 무엇인지 예시로 연관 규칙을 들어보고자 한다.

 

 

 

Transaction	구매 목록
1	빵, 우유
2	빵, 기저귀, 맥주, 계란
3	우유, 기저귀, 맥주, 콜라
4	빵, 우유, 기저귀, 맥주
5	빵, 우유, 기저귀, 콜라

 

 

• 기저귀 $\rightarrow$ 맥주
• 맥주, 빵 $\rightarrow$ 기저귀

 

 

 

2가지 연관규칙 예시에서 화살표가 등장하였다고 해서 어떠한 인과관계가 존재함을 말하는 것이 아니다. 기저귀를 사면 맥주를 사는 것이 아니고 반대로 맥주를 사면 기저귀를 사게 되는 것도 아니다. 단지 어떠한 상품이 등장했을 때, 같이 등장할 확률이 높은 다른 아이템을 의미한다. 여기서 먼저 등장하는 "기저귀" 또는 "맥주, 빵"을 우리는 antecedent라고 하고, 뒤에 나오는 "맥주", "기저귀"를 consequent라고 한다.

 

 

 

IF (antecedent) THEN (consequent)

 

 

 

연관규칙이 되기 위해서는 또 하나의 조건을 만족하고 있어야 한다. 바로 antecedent와 consequent 가 서로소 집합을 만족하고 있어야 한다. 둘 사이의 교집합이 존재해서는 안된다. 그리고 이 두 집합의 합집합을 Itemset이라고 부른다.

 

 

 

 

 빈발집합 

 

바로 위에서 살펴본 Itemset과 새로 등장하게 되는 support라는 개념을 사용하여 빈발 집합을 정의할 수 있다. support가 말하는 것은 전체 transaction 에서 특정 Itemset이 등장하는 비율을 의미한다. 비율을 계산하기 전, 특정 Itemset이 등장하는 횟수를 support count라고 한다. 예를 들어 설명하면 다음과 같다.

 

 

• support_count( {"빵", "우유"} ) = 3
• support( {"빵", "우유"} ) = 3 / 5 = 0.6

 

 

이렇게 특정 Itemset에 대한 support 값들을 계산할 수 있다면 특정 임계값을 정하고 이 값을 넘어서는 Itemset을 우리는 빈발 집합이라고 정의한다. 빈발 집합은 말 그대로 함께 등장하는 비율이 설정한 임계값을 넘는 아이템 집합을 말하며 연관규칙을 이해하는데 중요한 개념이 된다.

 

 

 

 

 support 

 

방금 살펴본 support 를 다시 정리하자면, 두 Itemset 집합 $X$, $Y$ 를 모두 포함하는 Itemset의 비율을 의미하며 좋은 연관규칙을 찾는 척도가 된다. support에서 등장하는 Itemset집합은 그 원소가 1개여도 정의가 되며 2개 이상의 원소가 포함된 Itemset보다는 반드시 그 확률이 같거나 크다.

 

 

 

$$ \text{support}(X) = \frac{n(X)}{N} = P(X) \quad \geq \quad \text{support}(X \rightarrow Y) = \frac{n(X \cup Y)}{N} = P(X \cap Y) $$

 

• $N$ : 전체 transaction의 수

 

 

 

 

 confidence 

 

confidence는 두 Itemset 집합 $X, Y$을 가지고 만든 조건부 확률이다. 정확히 말하자면, 집합 $X$가 등장했을 때, 집합 $Y$가 등장할 확률이다. confidence가 높다는 것은 찾아낸 연관규칙이 추천을 할 때, 유의미한 정보라는 것을 의미한다.

 

 

 

$$ \text{confidence}(X \rightarrow Y) = \frac{n(X \cup Y)}{n(X)} = \frac{\text{support}(X \rightarrow Y)}{\text{support}(X)} = \frac{P(X \cap Y)}{P(X)} = P(Y \vert X) $$

 

 

 

 

 

 lift 

 

lift는 이전의 support와 confidence값 처럼 어떤 확률 또는 비율로 계산되는 것이 아니라, 그 값이 1인지 1보다 큰지, 1보다 작은 지를 기준으로 판단한다. lift가 계산되는 방식은 $X$가 등장했을 때, $Y$가 등장할 확률을 $Y$가 등장할 확률로 나누어준 값이다.

 

 

 

$$ \begin{aligned} \text{lift}(X \rightarrow Y) &= \frac{P(Y \vert X)}{P(Y)} = \frac{P(X \cap Y)}{P(X)P(Y)} \\\\ &= \frac{\text{support}(X \rightarrow Y)}{\text{support}(X) \text{support}(Y)}\\\\ &= \frac{\text{confidence}(X \rightarrow Y)}{\text{support}(Y)} \end{aligned} $$

 

 

 

• $\text{lift}(X \rightarrow Y) = 1$ : $X, Y$가 서로 독립
• $\text{lift}(X \rightarrow Y) > 1$ : $X, Y$가 양의 상관관계를 갖는다.
• $\text{lift}(X \rightarrow Y) < 1$ : $X, Y$가 음의 상관관계를 갖는다.

 

 

 

 

 

 

 연관 규칙 척도의 사용 

 

Itemset의 개수가 많아질 수록 연관 규칙의 개수는 기하급수적으로 많아지는데, 여기서 유의미한 연관 규칙을 찾도록 만들어야 한다. 이때, 주로 만들어진 연관 규칙을 lift 값을 기준으로 정렬하거나, 앞서서 정의한 support 임계값 이나 confidence 임계값을 사용하여 쓸모없을 것 같은 연관규칙을 미리 배제할 수 있다.

 

 

 

 

먼저 임계값을 기준으로 필터링을 하게 되면, 같이 등장할 확률이 낮은 연관 규칙들은 배제가 되기 때문에 가장 단순하게 제거가 가능하다. 그렇다면 support나 confidence 값이 아닌 lift를 사용하여 정렬하고 더 높은 양의 상관관계를 갖는 연관 규칙을 찾는 이유에 대해 살펴보아야 한다. 강의에서는 와인($X$), 와인 오프너($Y$), 생수($Z$)를 예시로 들면서 그 이유를 설명한다. 먼저 와인을 샀을 때, 다른 상품들을 같이 사게 될 확률을 아래와 같다고 하자.

 

 

 

• $P(Y \vert X) = 0.1 $ : 와인을 샀을 때, 와인오프너를 구매할 확률 (confidence)
• $P(Z \vert X) = 0.2 $ : 와인을 샀을 때, 생수를 구매할 확률 (confidence)

 

 

 

위의 조건부확률의 결과로만 놓고 보았을 때, 와인을 살 경우에 생수를 구매할 확률이 더 높기 때문에 와인과 생수와의 관계가 더 높다고 생각하게 된다. 하지만 현실적으로 생각해보았을 때, 와인과 와인 오프너와의 상관관계가 더 높다. 현실과 상반되는 위와 같은 결과가 주어진 것은 와인 오프너와 생수가 평소에 구매되는 확률이 배제되었기 때문이다. 생수는 사람들이 평소에도 많이 구매하는 상품인 것을 고려하여 다시 계산하면 다음과 같다.

 

 

 

• $P(Y) = 0.01$ : 와인 오프너를 구매할 확률 (support)
• $P(Z) = 0.2$ : 생수를 구매할 확률 (support)

 

 

 

새롭게 추가된 위의 확률을 보면 생수 하나만 구매될 확률도 평소에 높은 것을 알 수 있다. 그렇기 때문에 생수는 이전에 와인이나 와인오프너 어떤 상품을 구매했어도 조건부 확률 값인 confidence가 높게 계산되었을 것이라고 예상할 수 있다. 이번에는 lift를 계산해보면 아래와 같다.

 

 

 

• $\text{lift}(X \rightarrow Y) = 0.1 / 0.01 = 10$ : 와인을 구매했을 때, 와인 오프너를 구매한 lift 값
• $\text{lift}(X \rightarrow Z) = 0.2 / 0.2 = 1$ : 와인을 구매했을 때, 생수를 구매한 lift 값

 

 

 

이렇게 되면 평소에 각 상품들이 구매되는 support 값도 같이 고려되기 때문에 더 정확한 비교가 가능하다. 그렇기 때문에 연관 규칙들을 정렬할 때, 그 기준으로 lift 값을 사용하게 되는 것이다.

 

 

 

 

---

 

 

이번에는 만들어진 수 많은 연관 규칙들 중에서 어떻게 의미 있는 연관 규칙을 찾아내는지 그 방법에 대해서 살펴보았다. 하지만, Itemset이 많아지면 만들어야 하는 연관 규칙이 많다는 것 자체가 매우 많은 계산양을 요구하게 된다. 따라서 다음 글에서는 효율적으로 연관 규칙을 탐색하는 3가지 방법에 대해서 소개한다.