연관 분석이란

연관 분석(Assosiation Analysis)

---

많은 비지니스 기업들이 고객들의 정보를 데이터로 축적한다. 예를 들면, 식료품점에서 고객의 쇼핑 데이터는 그림 1과 같다.

그림 1

각각의 고객은 TID라는 넘버를 가졌고, 각각 구매한 제품에 대한 정보가 item 열에 담겨있다. 일반적으로 각각의 행을 트랜잭션(transaction)이라고 부른다. 기업은 고객들의 구매 행동을 알고자 데이터를 분석하는데에 관심이 많다. 데이터 분석을 통해 소비자의 구매를 예측할 수 있다면, 비지니스에 도움이 되기 때문이다.

연관 분석이란 ?

큰 데이터 집합에서 숨겨진 흥미로운 관계를 발견하기 위해 연관 분석(association analysis)이라는 방법론을 사용한다. 밝혀진 관계는 트랜잭션들에 존재하는 한목들의 집합 형식으로 나타낼 수 있는데, 이것을 빈발 항목집합(frequent itemsets)이라고 한다. 예를 들면, 그림 1에서 다음의 규칙을 추출할 수 있다.

\[\{\text{Diapers}\} -> \{\text{Beer}\}\]

왜냐하면, Diapers를 구매한 사람들은 Beer를 구매했기 때문이다. 이 규칙은 diapers와 beer 판매 사이의 관계를 표현한다.

연관 분석은 꼭 그림 1처럼 트랜잭션 데이터에 대해서만 사용 가능한 것이 아니고 다양한 분야에서 사용가능하다. 예를 들면, 생물 정보학, 의료 진단, 과학 데이터 분석 등이 있다. 그러나 이번 CH5에선 트랜잭션 데이터로만 설명을 하겠다.

트랜잭션 데이터 사용 시 주의점

1. 트랜잭션 데이터를 사용할 땐 굉장히 sparse한 큰 데이터 집합이 나올 때가 많다. 그래서 큰 트랜잭션 데이터 집합에서 패턴을 발견하는 것은 계산 비용이 많이 들 수 있다.
2. 연관 분석을 통해 발견된 패턴들 중, 우연히 발생한 경우가 있다. 즉, 가짜 패턴이라는 뜻인데 이것은 가끔 다른 패턴들보다 더 흥미로울 수 있다.

1번 문제를 딥러닝 해결하고자 하는 논문을 읽은 적이 있다. 링크에 가서 보자.

연관 분석에 사용되는 기본 용어들

연관 분석에서 사용되는 기본 용어들에 대해 알아보자.

이진표현

그림 1의 트랜잭션 데이터들은 그림 2처럼 binary화 할 수 있다

그림 2

트랜잭션에서 각각의 열에 대해 항목이 존재한다면, 1로 표시한 것이다. 트랜잭션에서 1로 표시되는 항목은 0보다 더욱 중요한 가치를 갖는다. 따라서 항목은 비대칭(asymmetric) 이진 변수이다. 비대칭이란, 개수가 확연히 적은 데이터가 더욱 중요할 때를 이야기한다.

항목집합

트랜잭션 데이터에서 D개의 항목(열)들의 각각을 $i_d$라고 표현하면, 항목들의 집합을 $I={i_1,i_2,…,i_d}$라고 표현한다. N개의 트랜잭션 데이터들에서 각각을 $t_n$으로 표현하면, 트랜잭션들의 집합을 $T={t_1,t_2,…,t_N}$라고 표현한다.

$I$에서 항목들을 선택해 집합을 만들면 항목집합이라고 부르며, k개를 선택했을 시엔 k-항목집합(k-itemset)이라고 부르고, 이것은 트랜잭션 $t_i$의 부분 집합이 된다.

예를 들면, 그림 2에서 2-항목집합 {Bread,Milk}는 첫번째 트랜잭션의 부분집합이다. 그러나 {Bread,Diapers}는 부분집합이 아니다.

지지도 카운트(support count)

항목집합의 중요한 성질은 지지도 카운트이다. 이것은 특정 항목집합 $X$을 포함하는 트랜잭션들의 개수를 나타낸다. 수학적으로는 다음과 같이 표현한다.

\[\sigma(X) = |\{t_i | X \subseteq t_i,\;t_i \in T \}|\]

기호 $|\cdot|$은 집합에 속한 원소들의 개수를 표시한다. 예를 들면, 그림 2에서 3-항목집합 {Beer,Diapers,Milk}에 대한 지지도 카운트는 2이다. 왜냐하면 항목집합을 부분집합으로 포함하는 트랜잭션은 두개뿐이기 때문이다.

항목집합 $X$가 존재하는 트랜잭션들의 비율은 다음과 같이 $s(X)$로 정의한다.

\[s(X) = \frac{\sigma(X)}{N}\]

만약 $s(X)$가 사용자가 정의한 threshold 보다 크다면, 항목집합 X는 빈발(frequent)하다고 부른다.

연관 규칙

X,Y는 서로 공통원소를 갖지 않는 항목집합이라고 할 때, 연관 규칙은 $X\;->\;Y$ 형식으로 사용한다. 연관 규칙의 강도는 지지도(support)와 신뢰도(confidence)로 측정된다.

• 지지도

  규칙 $X\;->\;Y$가 주어진 트랜잭션 집합에 적용되는 빈도

  \[s(X->Y) = \frac{\sigma(X\cup Y)}{N}\]

• 신뢰도

  Y에 속한 항목들이 X를 포함하는 트랜잭션들에 나타나는 빈도

  \[c(X->Y) = \frac{\sigma(X\cup Y}{\sigma(X)}\]

지지도는 말이 와닿는데 신뢰도는 약간 말이 와닿지 않는다. 신뢰도를 다시 정의하자면, 항목집합 X를 포함하는 트랜잭션에 항목집합 Y가 존재할 가능성을 의미한다. 신뢰도가 1에 가까울수록 항목집합 X만 갖는 데이터는 Y가 존재할 것으로 믿어 의심치 않다! 라고 생각되는 것이다.

그림 2로 예시를 들어보자. 규칙 $X={\text{Milk,Diapers}}->{\text{Beer}}를 고려하자. $X\cup Y={\text{Milk,Diapers,Beer}}$에 대한 지지도 카운트는 2이다. 전체 트랜잭션의 수는 5이므로 지지도는 2/5=0.4이다. 신뢰도는 $X\cup Y={\text{Milk,Diapers,Beer}}$에 대한 지지도 카운트를 $X={\text{Milk,Diapers}}$에 대한 지지도 카운트로 나누어서 얻는다. 2/3 = 0.67이다.

지지도와 신뢰도는 왜 사용할까?

지지도가 매우 낮다는 것은 우연히 발생한 규칙이라는 의미를 갖는다. 따라서 우리는 threshold를 지정해서 일정 값 이상의 지지도를 갖는 규칙을 찾게 될 것이다. 그래야 항목집합 X만 구매한 손님에게 Y를 추천할 수 있게 되는 것이다. 왜냐하면 우연히 발생한 규칙이 아니기 때문이다.

신뢰도는 규칙에 의해 만들어진 추론의 신뢰성을 측정한다. 만들어진 규칙 $X->Y$에 대해 신뢰도가 높을 수록, X를 포함하는 트랜잭션에 Y가 존재할 가능성이 더 높아지는 것이다.

연관 규칙 탐사 문제의 형식화

연관 규칙 $X->Y$는 사실 너무나 많은 경우의 수가 존재한다. 모든 경우를 확인하기 위해서 Brute-force 접근법을 사용하게 될텐데, cost가 너무 많이 든다. d개의 항목을 갖는 데이터 집합에서 추출되는 가능한 규칙들의 경우의 수 $R$은 다음과 같이 계산된다.

\[R=3^d-2^{d+1}+1\]

그림 1에서 d=5인데, 위 식을 통해 얻는 규칙의 경우의 수는 무려 602개나 된다.. 그래서 미리 가지치기를 한다고 한다.

가지치기의 핵심은 규칙 $X->Y$의 지지도$s(X->Y)$는 사실 $s(X\cup Y)$로 표현되는 것이나 마찬가지다. 그래서 항목 A,B,C를 2개의 항목집합 X,Y로 만드는 경우의 수를 모두 확인할 필요가 없다! 즉, 단순하게 A,B,C를 하나로 하는 항목집합 Z를 생성해서 $s(Z)$를 계산하여 threshold를 기준으로 미만이라면 미리 가지치기로 잘라버리는 것이다! 왜냐하면 threshold 미만이면 frequent하지 않은 항목집합이기 때문이다.

따라서 연관 규칙 탐사 알고리즘들에 채택된 공통 전략은 문제를 두개의 주요 부분 과제들로 분해하는 것이다.

1. 빈발(frequent) 항목집합 생성
   
   threshold를 만족하는 모든 항목집합들을 찾는 것이 목표다.
   
   
2. 규칙 생성
   
   1.에서 얻은 빈발 항목집합에서 높은 신뢰도를 갖는 규칙들을 모두 추출하는 것이 목표다. 이것들을 강한 규칙들(strong rules)이라고 한다.

다음 섹션부턴 위 과제들에 대해서 배울 것이다! 완전 처음 접하는 개념들이라서 재밌다 ㅎㅎ