Association Rules

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

이번 모듈에서는
Market basket 모델에서 빈번하게 나오는 아이템셋을 찾는 기술에 대해 다룹니다.

오늘 포스팅에는
Market basket 모델과 모델에서 사용되는 척도,
모델을 적용할 수 있는 분야에 대해 다루고,
연관규칙(=association rule) 을 설명합니다.

Market-Basket Model

Market-Basket 모델은,
실제로 마트에서 소비자의 구매 패턴을 분석하기 위해 도입된 모델입니다.

이 모델은
아이템(=Item) 과 바스켓(=basket) 을 다룹니다.
아이템은 마켓에서 팔린 항목이고
바스켓은 각 소비자들이 산 아이템들의 집합입니다.
아이템 과 바스켓은 다대다(many-to-many) 관계를 갖고 있습니다.

여기서 다루는 문제는
같은 바구니에 빈번하게 보이는 아이템의 집합을 찾는 것 입니다.

빈도가 높은 아이템을 찾기 위해 support 라는 개념을 도입합니다.

Support

아이템셋 I 의 서포트(=support) 란
집합 I 에 있는 모든 아이템을 포함하는 바스켓의 수 입니다.

서포트의 임계값 s 를 설정하여
빈번하다는 기준을 정합니다.
아이템셋 I 의 서포트가 s 보다 높으면, I 는 빈번하게 나오는 것이고,
이를 빈도 아이템셋(=frequent itemsets) 이라고 합니다.

예를 들어

example 1

각 집합은 하나의 바스켓이고 단어는 아이템 입니다.

싱글톤 집합(=singleton sets) 중에 {cat},{dog} 이 빈번하게 나옵니다.
‘Dog’은 5번째 바스켓에서 빼고 다 나왔습니다. (support = 7)
‘Cat’ 은 4,8 번 빼고 나왔습니다. (support = 6)

s=3 으로 두면, 5개의 싱글톤인 빈도 아이템셋이 나옵니다.
{dot} {cat} {and} {a} {training}

이제 더블톤을 봅시다.
더블톤은 두 아이템 다 빈번하지 않으면 빈번할 수 없습니다.
위의 예시에서는 더블톤은 10개이고,

이 중에서 s=3 을 넘는 아이템셋, 빈도 아이템셋은
{dog, a} {dog, and} {dog, cat} {cat, a} {cat, and}
5개 입니다.

트리플인 경우는
{dog, cat, a} {dog, a, and}
2개가 있으며,
트리플의 부분집합(더블톤)이 빈도 아이템 셋인 것을 볼 수 있습니다.

Application

Market-Basket 모델을 실제 적용한 사례로는
‘기저귀 - 맥주’ 가 유명합니다.
일반적 상식으로는 두 아이템의 연관성을 기대하기 어렵습니다.
그러나 실제 데이터 분석에서 두 아이템 사이 연관성을 발견했고,
다음과 같은 해석이 제시되었습니다.
기저귀를 산다면, 그 집에 애기가 있을 것이고,
애기가 있다면, 밖에서 술을 마시기 어려울 것입니다.
그래서 집에서 마시기 위해 맥주를 사게됩니다.

마켓은 이러한 분석을 기반으로
기저귀와 맥주가 있는 위치 사이에 팔고자 하는 아이템을 넣던지
기저귀 가격을 낮추고 맥주 가격을 높이는 식으로
많은 고객을 유인하는 등의 판매전략을 새울 수 있습니다.

이런식으로 Market-Basket 모델을 적용할 수 있고,
이 모델은 마켓 상황 뿐 아니라 다음과 같은 상황에서도 도입할 수 있습니다.

1. Related concepts
   아이템이 단어고, 바스켓이 문서가 됩니다.
   문서는 단어를 포함합니다.
   문서들에서 많이 나오는 단어의 집합을 찾는다면,
   Market-Basket 모델을 사용하기 적합합니다.
2. Plagiarism
   여기서는 아이템이 문서가 되고, 바스켓이 문장들 입니다.
   문서는 그 문서 안에 문장이 있다면, 문장 ‘안’ 에 문서가 있습니다.
   문서와 문장은 다대다 관계로 표현될 수 있고,
   여기서는 빈번하게 나오는 문서쌍을 찾는 것이 목적이므로
   문서를 아이템으로 사용합니다.
   이런식으로 적용하면, 여러 문장을 공통으로 공유하는 두 개의 문서를 찾을 수 있고, 이를 표절한 것으로 처리할 수 있습니다.
3. Biomarkers
   환자가 바스켓, 그 환자의 질병, 유전자, 혈액 정보 등을 아이템으로 사용합니다.
   이런식으로 질병이나 유전자 간 관계를 분석하고,
   어떤 질병에 걸렸을 때 빈번하게 나오는 다른 질병을 검사해보는 식으로 적용 할 수 있습니다.

Association Rules

support 를 사용하는 작업은 빈도 아이템셋을 찾을 수 있지만,
빈도만으로는, 아이템 간 연관 관계를 파악하기 어렵습니다.
때문에 아이템셋의 연관 규칙(=association rule)을 찾는 작업이 필요합니다.

연관 규칙은 $I \rightarrow j$ 형태로 표현됩니다.
$I$ 는 아이템들의 집합이고, $j$ 는 하나의 아이템입니다.
if - then 관계로,
바스켓 안에서 아이템 집합 $I$ 가 나타난다면, $j$ 가 나타날 가능성이 높다(likely)
를 의미합니다.

여기서 ’likely’ 의 개념을 신뢰도(=confidence) 를 정의하여 도입할 수 있습니다.

Confidence

신뢰도는 연관규칙에 대하여 나타내는 수치입니다.
연관규칙 $I \rightarrow j$ 에 대한 신뢰도는
$I$ 의 서포트 분에 $ I\cup {j}$ 에 대한 서포트로 정의됩니다.

\[(I \rightarrow j)'s \ confidence =  \frac{I\cup j's \ support}{I's\ support}\]

연관규칙의 신뢰도 임계값 c 를 기준으로,
해당 연관규칙이 신뢰도가 있는지 판별합니다.

example 2

위의 example 1 상황에서 연관규칙을 찾아봅시다.

연관규칙 ${cat,dog} \rightarrow and$ 의 신뢰도는 3/5 입니다.
‘cat’, ‘dog’ 은 5개의 바스켓에서 나왔고, ( $I$ )
‘and’ 는 그 중 3개의 바스켓에서 나왔습니다. ( $I \cup j$ )

${cat} \rightarrow kitten$ 는 1/6 입니다. cat 은 6번 나왔고 그 중 kitten 은 그 중 하나(5) 에서만 나왔습니다.

Finding Association Rules

연관규칙을 찾는 문제는 다음과 같이 주어집니다.

서포트가 s 보다 크고($\geq$), 신뢰도가 c 보다 큰($\geq$) 모든 연관 규칙을 찾아라.

여기서 연관규칙의 서포트는 왼쪽에 있는, $I \rightarrow j$ 에서 $I$ 의 서포트를 의미합니다.
$I$ 가 s 이상의 서포트를 갖고, 이 규칙의 신뢰도가 c 보다 크면 빈번(frequent) 합니다.

연관 규칙의 특성을 보면,
$I = { i_1,i_2,\dots,i_k}$ 가 서포트 s 를 갖고, 연관 규칙의 신뢰도가 c 라면
$I \cup j = { i_1,i_2,\dots,i_k,j}$ 의 서포트는 연관 규칙의 서포트와 신뢰도의 곱, cs 가 됩니다.

위 특성을 활용하여 다음과 같이 연관규칙을 찾을 수 있습니다.

1. 서포트가 cs 이상인 모든 집합을 찾는다.
2. 서포트가 s 이상인 모든 집합을 찾는다.
3. 집합 ${ i_1,i_2,\dots,i_k,j}$ 가 cs 이상이라면,
   이 중 하나를 뺀 부분집합 들 중 서포트가 s 이상인 것을 찾는다. ( $j$ 라 두고)
4. ${ i_1,i_2,\dots,i_k} $ 의 서포트가 s 이상이고 ${ i_1,i_2,\dots,i_k,j}$ 의 서포트가 cs 이상이므로,
   규칙 ${ i_1,i_2,\dots,i_k} \rightarrow j$ 의 신뢰도는 c 이상이되고, 이는 연관규칙으로 간주한다.

이번 포스팅에서는
Market-basket 모델과 그 적용사례에 대해 알아보았고,
빈도 아이템셋과 연관 규칙을 찾기위한 기본적인 개념에 대해 다루었습니다.

다음 포스팅에서는
데이터가 실제로 어떻게 처리 되는지와
대규모의 데이터에 아이템셋을 찾는 작업에서 발생할 수 있는 문제에 대해 다루겠습니다.