데이터마이닝 기법 : 연관규칙의 탐사

데이터마이닝 기법 : 연관규칙의 탐사

(포항공대 전 치 혁 교수)
 

1. 서언

연관규칙(association rule)이란 간단히 말하면 데이터의 항목들 간의 조건-결과 식으로 표현되는 유용한 패턴을 말한다. 연관규칙의 탐사는 기업의 활동, 특히 마케팅에서 가장 널리 사용되고 있다. 예를 들면, 미국의 슈퍼마켓에서 목요일 기저귀를 사는 고객은 맥주도 동시에 구매한다는 연관성을 알아냈다고 한다. 이때, 조건은 ‘목요일, 기저귀’이며 결과는 ‘맥주’라 할 수 있다. 이와 같은 연관규칙의 탐사가 가능하게 된 것은 컴퓨터기술의 발전을 들 수 있겠다. 한 고객이 슈퍼마켓의 계산대에서 계산할 때 쇼핑카트에 담긴 물품들이 바코드를 통하여 컴퓨터에 데이터베이스 형태로 입력되고 이로부터 고객들의 구매행태를 분석할 수 있게 되었다.

위에서 언급한 데이터의 형태는 소위 바스켓(basket) 데이터라 한다. 이 때 한 고객, 즉 한 바스켓의 정보를 하나의 트랜잭션(transaction)이라 한다. 바스켓 형태의 데이터에서는 주로 트랜잭션 내의 연관성을 살펴보고자 하는 것으로, 수많은 트랜잭션을 분석하여 빈번히 나타나는 규칙을 찾아내는 것이다. 이렇게 찾아낸 규칙은 마케팅에 활용된다. 예를 들어, 위의 기저귀-맥주의 규칙을 활용하여 기저귀와 맥주를 가까운 곳에 진열함으로써 매출 신장을 기할 수 있다. 이와 같이 바스켓 데이터로부터 연관규칙을 탐사하는 것을 시장바구니분석(market basket analysis)이라 한다.

연관규칙의 탐사는 한 고객의 시간에 따른 구매정보를 활용하여 이루어지기도 한다. 예를 들면, 가전제품 대리점에서 고객별 시간별 구매제품의 데이터를 활용하여 ‘제품 A를 사는 고객은 추후에 제품 B도 구매한다’는 연관규칙을 이끌어낼 수 있을 것이다. 이와 같은 패턴을 얻어 제품 A를 구매하였으나 제품 B를 구매하지 않은 고객에게 판매활동을 할 수 있다. 이런 시간에 따른 고객데이터를 시퀀스(sequence) 데이터라 한다.

당 연한 사실이지만 탐사에서 도출된 연관규칙은 분명하고 유용한 것이어야 한다. 유용하다(useful)는 것은 새롭고도 실행가능하며 설명할 수 있는 것을 말한다고 하겠다. 이에 비해 사소한(trivial) 규칙이란 이미 잘 알려진 사실을 말한다. 예를 들면, ‘페인트를 사면 페인트 붓을 산다’ 는 규칙 같은 것이다. 또한, 설명할 수 없는 규칙은 데이터의 오류일 가능성도 있으며 마케팅에 활용할 수 없기 때문에 역시 유용하다고 볼 수 없다.


2. 연관규칙의 정의 및 성능척도

데이터베이스가 총 n개의 트랜잭션 데이터로 구성되며 전체 m개의 항목으로 구성된다고 하고 이를 I 라 하자. 연관규칙 R은 조건부와 결과부로 구성되며 항목집합인 X와 Y에 대하여 ‘X가 일어나면 Y 도 일어난다’는 의미로 다음과 같이 표현할 수 있다.

R : X ⇒ Y

여기서 X,Y⊆I 이고, X∩Y=Φ이어야 한다. 따라서 연관규칙을 탐사함은 적절한 항목집합 X와 Y를 선택하는 문제로 볼 수 있으며 이를 위해 몇 가지 척도를 고려하고 있다. 우선, 항목집합 X 및 규칙 R에 대한 지지도(support)는 각각 다음과 같이 정의된다.

supp(X) = 집합 X의 항목을 동시에 포함하는 트랜잭션 수의 전체 수(n)에 대한 비율
supp(R) = supp(X∪Y)

즉, 규칙 R에 대한 지지도는 집합 X 또는 집합 Y에 있는 항목을 동시에 포함하는 트랜잭션수의 비율을 나타낸다.

예 1. 다음과 같은 5개의 트랜잭션을 고려해 보자.

트랜잭션	항목
1	b, c, g
2	a, b, d, e, f
3	a, b, c, g
4	b, c, e, f
5	b, c, e, f, g

이때 전체 항목집합 I는 I = {a, b, c, d, e, f, g} 이다. 몇 가지 항목집합에 대한 지지도를 구하면 다음과 같다.

supp({a}) = 2/5 = 0.4, supp({b, c}) = 4/5 = 0.8

다음과 같은 규칙을 고려해 보자.

R: “항목 b와 항목 c가 일어나면, 항목 g도 일어난다”

이 때 규칙 R에 해당하는 항목집합 X와 Y는 다음과 같다.

X={b, c}, Y={g}.

이 경우 X 및 규칙 R에 대한 지지도는 각각 아래와 같이 산출된다.

supp(X) = supp({b, c}) = 0.8
supp(R) = supp({b, c, g}) = 3/5 = 0.6

연관규칙 R의 가치를 평가할 때 통상 다음과 같이 정의되는 신뢰도(confidence)를 사용한다.

conf(R)= supp(X∪Y)/supp(X)

이 신뢰도는 조건부 확률의 개념으로 집합 X(조건)가 발생한다고 할 때 집합 Y(결과)도 동시에 발생할 확률을 의미한다. 즉, 트랜잭션에 X의 항목들을 포함하는 경우 Y의 항목들도 동시에 포함할 확률을 나타내며, 신뢰도가 큰 규칙일수록 의미가 크다고 하겠다.
또한, 신뢰도 이외에 연관규칙의 개선도(lift or improvement)를 함께 사용하는데, 이는 결과가 단독으로 발생할 빈도에 대한 조건과 연계하여 결과가 발생할 가능성의 빈도의 비로 정의된다.

개선도가 1이 됨은 가 성립하므로 항목 집합 X와 Y의 발생이 독립임을 의미한다고 하겠다. 그리고 개선도가 1 전후의 값에 따라 다음과 같은 해석을 할 수 있다.

- lift(R) > 1인 경우, X와 Y의 발생이 양의 상관관계
- lift(R) < 1인 경우, X와 Y의 발생이 음의 상관관계

따라서 개선도가 1보다 큰 규칙이야말로 우연한(랜덤한) 관계가 아닌 필연적 관계를 나타낸다고 하겠다.

3. 연관규칙의 탐사

연 관규칙의 탐사는 결국 신뢰도 또는 개선도가 높은 규칙 R을 트랜잭션 데이터로부터 도출하는 과정이다. 따라서 규칙이 R : X ⇒ Y의 형태일 때 적절한 항목집합 X와 Y를 찾는 것이라 할 수 있겠다. 그러나 모든 항목의 조합을 고려하여 성능이 좋은 규칙을 찾는 일은 쉬운 것이 아니므로 이를 위한 효율적인 알고리즘이 요구된다. 예로써 예 1.의 7개 항목으로 구성된 5건의 트랜잭션 데이터에 대하여 집합 X의 후보가 되는 경우수를 볼 때, 1개 항목으로 구성되는 경우가 7가지, 2개의 항목으로 구성되는 경우가 21가지, 3개의 항목으로 구성되는 경우가 35가지 등이 될 것이다.
연관규칙의 탐사를 위한 알고리즘으로 기본적이며 가장 널리 사용되는 것은 1994년에 Agrawal 및 Srikant가 발표한 Apriori 알고리즘으로 다음의 두 단계로 구성된다.

단계 1. 미리 결정된 최소지지도 smin 이상의 지지도를 갖는 모든 빈발 항목집합들(large itemsets)을 찾는다.
단계 2. 빈발 항목집합 L에 대한 부분집합 A를 고려한다. 미리 결정된 최소신뢰도 cmin에 대하여 supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 지지도는 supp(R)=supp(L)이며, 신뢰도는 conf(R)=supp(L)/supp(A) 가 된다.

3.1. 빈발 항목집합 생성

빈발 항목집합을 도출하기 위하여 우선 하나의 항목으로 이루어지는 후보집합군(C1)을 형성하고 최소지지도 이상을 갖는 집합군(L1)을 생성한다. 다음으로 L1으로부터 두개의 항목으로 이루어지는 후보집합군(C2)를 만들고 최소지지도 이상을 갖는 집합군(L2)을 생성하며, 다시 L2로부터 세 항목으로 이루어지는 후보집합군(C3)과 빈발 항목집합군 L3를 만드는 등 이러한 과정을 더 이상 새로운 집합이 생성되지 않을 때까지 반복한다.
로부터 를 생성할 때 접합(join)연산자(*)를 사용한다. L1으로부터 C2를 만드는 경우에는 L1의 한 항목에 대한 모든 조합이 2-항목 집합인 C2가 될 것이다. 그러나 L2에서 두 집합의 조합은 최대 4개의 항목을 포함할 수 있으므로 C3를 형성할 때 L2의 집합 중 하나의 항목이 동일한 것들만 대상으로 하여야 한다. 마찬가지로 L3로부터 C4를 형성할 때는 L3의 집합 중 두개의 항목이 동일할 때 가능하게 된다. 예로써, L2=[{a,b}, {a,c}, {b,d}]라 할 때 {a,b,c}와 {a,b,d}가 3-항목 집합의 후보가 될 것이다. 그러나, C3를 구성할 때 {a,b,c}는 제외된다. 왜냐하면, {a,b,c}의 지지도는 {b,c}의 지지도 이하인데 {b,c}가 L2에 포함되지 않았다는 것은 이의 지지도가 최소지지도 미만이라는 것을 나타내기 때문이다. 이러한 과정은 Apriori 알고리즘 중 'apriori-gen' 함수에 의하여 수행된다.

예 2. (예 1.의 계속). 예 1.의 트랜잭션 데이터를 바탕으로 빈발 항목집합을 만들어보자. 우선, C1은 다음과 같다.

C1=[{a}, {b}, {c}, {d}, {e}, {f}, {g}]

최소 지지도를 0.4(5개의 트랜잭션 중 2개)라 하면 1-항목으로 이루어지는 빈발 항목집합군은 다음과 같다.

L1=[{a}, {b}, {c}, {e}, {f}, {g}]

2-항목 빈발집합의 후보 C2에 다시 최소지지도 0.4를 적용하면 L2는 다음과 같다.

L2=[{a,b}, {b,c}, {b,e}, {b,f}, {b,g}, {c,e}, {c,f}, {c,g}, {e,f}]

C3를 구성하기 위하여 L2의 집합에 접합연산자를 적용하면 다음과 같다.

C3=[{b,c,e}, {b,c,f}, {b,c,g}, {b,e,f}, {c,e,f}]

이 때 {a,b,c} 는 {a,c}가 L2에 포함되지 않았으므로 C3에 포함될 수 없음을 볼 수 있다.
C3의 모든 집합은 최소지지도 이상이므로 L3는 C3와 동일하다.

Apriori 알고리즘을 단계별로 정리하면 다음과 같다.

단계 0. 최소지지도 smin을 정한다.

k=1
C₁=[{i₁},{i₂},...,{im}]
L₁={c∈C₁| supp(c) ≥ smin

단계 1. k=k+1

Lk-1로부터 Ck 형성 (apriori-gen 함수)
단계 1-1. (join) Lk-1의 집합들을 접합하여 k- 항목 집합군을 형성한다.

C= Lk-1 * Lk-1

단계 1-2. (prune) C의 (k-1)- 항목 부분집합이 Lk-1에 속하지 않을 때 이를 모두 제거한 후 Ck를 형성한다. Ck=Φ이면 Stop.

단계 2. Ck의 집합 중 지지도가 최소지지도 이상인 것을 모아 Lk를 생성한다.

Lk={c∈Ck | supp(c) ≥ smin}

3.2. 규칙의 탐사

앞에서 언급한 바와 같이 규칙의 탐사를 위하여 우선 도출된 빈발 항목집합 L 각각에 대한 부분집합 A를 고려한다. 여기서 L은 위의 L2, L3 등을 포함한다. 그리고, 미리 결정된 최소신뢰도 cmin에 대하여 supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 신뢰도 conf(R)=supp(L)/supp(A) 가 cmin 이상 되도록 하는 것이다.
현실의 경우 결과부에 하나의 항목만을 포함시키는 규칙을 도출하는 것이 이의 적용성 때문에 널리 사용되나, Agrawal & Srikant (1994)의 알고리즘에는 모든 가능한 규칙을 보다 효율적으로 탐사하는 방법이 소개되고 있다.

예 3. 예 1.의 트랜젝션 데이터에 대하여 예 2.에서 구해진 빈발 항목집합군 중 집합 L={b,c,g}을 고려해 보자. 이 때 결과부에 1-항목을 포함하는 규칙의 후보와 이에 대응되는 신뢰도는 다음과 같다.

R1: {b,c}⇒{g} conf(R1)=0.6/0.8 = 0.75
R2: {b,g}⇒{c} conf(R2)=0.6/0.6 = 1
R3: {c,g}⇒{b} conf(R3)=0.6/0.6 = 1

따라서 최소신뢰도를 0.7이라 하면 R1, R2, R3 모두 최소신뢰도 이상이 된다.

4. 결언

서 언에서 언급한 시퀀스 데이터에 대하여도 유사한 알고리즘이 적용되고 있으나 여기서는 생략한다
한 편, 분석할 트랜잭션 데이터에 어떤 항목들을 포함시킬 것인가는 분석에 앞서 결정하여야 할 중요한 문제 중 하나라 하겠다. 통상 슈퍼마켓 등에서 취급하는 제품 수는 수만 가지가 넘기 때문에 이러한 제품 하나하나를 모두 항목으로 선정하기에는 여러 어려움이 있다. 따라서 제품을 계층적으로 분류하여 적절한 계층에 속하는 것들을 항목으로 선정하는 방안을 사용한다. 제품분류에서 상위수준으로 갈수록 보다 포괄적인 항목(generalized item)이 사용된다.

항목이 너무 세분화되어 많은 경우 공통 항목의 트랜잭션 수가 적어 유용한 규칙을 도출하기 어려울 수 있으며, 반대로 항목이 너무 작은 경우에는 도출된 규칙이 쓸모없을 수 있기 때문에 항목의 선정이 중요하다 하겠다. 또한, 항목이 증가함에 따라 규칙탐사에 소요되는 계산시간이 급속도로 증가하기 때문에 원하는 계산복잡도에 알맞은 항목수를 결정할 필요가 있다. 항목을 선정하는데 있어 하나의 가이드라인은, 트랜잭션 데이터에 드물게 나타나는 것은 제품의 계층적 분류에서 보다 상위 수준의 항목을 사용하고, 자주 나타나는 경우에는 보다 하위 수준의 항목을 사용하여 결과적으로 트랜잭션 데이터에 빈도수가 비슷하게 되도록 하라는 것이다.