[지디넷코리아]지난 시간에 공부한 데이터 마이닝을 토대로 이번 시간에는 어떤 사건이 일어나면 다른 사건이 일어날 수 있는 지지도와 신뢰도를 바탕으로 트랜잭션 데이터의 각 아이템간의 연관성을 찾는 연관 규칙에 대해 알아보고 아울러 의사결정트리의 알고리즘과 이를 이용한 패턴 탐사에 대해 공부해 보도록 하겠다.

연재순서
1회(99.12) : 뉴밀레니엄의 경영 도구, 데이터 마이닝
2회(2000.01) : 연관 규칙과 의사결정트리를 이용한 패턴 탐사
3회 : 신경망을 이용한 예측 시스템, 다중퍼셉트론의 구현

컴퓨터 시스템의 급속한 발전과 데이터베이스 시스템 사용의 보편화는 데이터베이스에 저장되는 데이터의 양적 증가를 초래하게 됐고 그러한 대용량의 데이터베이스 안에는 일정한 형식의 질의로는 검색이 쉽지 않은, 그래서 사용자가 미처 파악하지 못한 중요한 정보가 존재할 수가 있게 됐다. 본 프로젝트에서 구현한 데이터 마이닝 시스템은 이러한 대용량의 데이터베이스 안에 숨겨져 있는 유용한 패턴, 지식을 추출하는 방법론이라는 것을 지난 시간을 통해 얘기한바 있다. 그러므로 이번 시간에는 많은 지식 탐사 기법 중에서 연관 규칙과 의사결정트리에 대해 알아본다.


연관 규칙의 정의
연관 규칙이란 어떤 사건이 일어나면 다른 사건이 일어난다와 같은 연관성을 이야기한다. 주어진 트랜잭션의 집합이 있고 서로 소 관계인 두 개의 부분 집합의 연관 규칙은 "A→B"로 표시할 수 있다. 이때 전체 항목들의 집합 A는 결론 항목들의 집합 B를 야기한다고 정의할 수 있다. 트랜잭션의 모임으로부터 한 항목 집합의 존재와 다른 항목 집합과의 연관 관계를 요약할 수 있는데, 연관 관계는 항목들 사이에 존재하는 유사성 또는 패턴을 의미한다. 연관 규칙의 기본 개념은 item set, 즉 트랜잭션의 집합이 있고 이 트랜잭션 집합을 I라고 표현했을 경우 공집합이 아닌 항목 집합 X, Y에 대해서 X⊂I, Y⊂I일 경우 가정 X라는 사건이 발생했을 때 결과 Y라는 사건이 발생한다라는 것을 말한다. X와 Y의 교집합이 공집합이라는 특성을 갖고 항목 집합 I의 부분 집합 X에 대해 X⊆T이면 T는 X를 만족한다고 정의할 수 있다
.
예를 들면 편의점에서 목요일에 기저귀를 구매하는 고객들은 맥주도 동시에 구매한다는 연관성이 있음을 연관 규칙 탐사의 결과로 얻어 낼 수 있는 것이다. 편의점에서 각 고객이 구매하는 물품들의 집합을 한 트랜잭션이라고 하고 이런 물품 구매에 관련한 트랜잭션이 일정한 기간동안 데이터베이스에 저장돼 있다면 기저귀를 사는 사람이 맥주를 구매하는 연관성을 연관 규칙으로 다음과 같이 표현할 수 있다.

기저귀→맥주(2% 지지도, 30% 신뢰도)

여기에서 의미하는 2%의 지지도(Support)는 주어진 데이터베이스의 트랜잭션들 중에서 2%가 기저귀와 맥주를 동시에 구입한다는 것이고 30%의 신뢰도(Confidence)라는 것은 기저귀를 사는 고객들 중에서 30%가 맥주를 산다는 것을 의미한다. 바꿔 얘기하면 물품 구매 트랜잭션 중에서 2%의 지지도는 맥주와 기저귀를 모두 구입한 트랜잭션의 비율을 의미하며, 30%의 신뢰도는 맥주를 구입한 고객 중에서 기저귀를 구입한 고객의 비율을 의미한다. 연관 규칙 탐사에서는 사용자가 지지도와 신뢰도의 값을 적절하게 명시해 트랜잭션 데이터베이스에서 사용자가 정한 정도의 모든 상호 연관성을 발견해 낼 수 있고, 편의점 데이터베이스와 같은 성격의 데이터베이스에서 고객들의 구매 패턴을 찾을 수 있다. 이러한 연관성과 구매 패턴을 바탕으로 시장성 예측에 적용할 수도 있을 것이다.

지지도와 신뢰도
앞에서 밝힌 바와 같이 연관 규칙이란 지지도와 신뢰도를 바탕으로 트랜잭션 데이터의 각 아이템간의 연관성을 찾는 것을 말한다. 그러면 여기에서 연관 규칙의 척도라 말할 수 있는 지지도와 신뢰도의 개념에 더욱 확실하게 정리하는 것이 필요할 것이다. 지지도란 다음과 같이 전체 트랜잭션에 대한 x와 y를 만족하는 트랜잭션의 비율을 의미한다.

S(x,y) = P(x, y) / 전체 트랜잭션의 수

이러한 지지도는 규칙의 통계적 중요성으로 인식될 수 있으며 빈번하게 발생하는 패턴 또는 규칙의 빈도를 의미하므로 그 패턴이나 규칙의 유용성이 증대되려면 지지도가 커야 한다는 것을 알 수 있다. 신뢰도는 x를 만족하는 트랜잭션에 대한 y를 만족하는 트랜잭션의 비율을 의미하며, 이러한 신뢰도는 가정 x일 경우 결론 y의 규칙에 대한 정확도를 측정할 수 있는 지표가 되고, 따라서 높은 지지도는 정확한 예측을 가능하게 해준다.

C(x,y) = P(x,y) / p(x)

예를 들어 빵과 버터를 구입한 고객 중에서 90%의 고객이 우유도 함께 구매한다는 규칙이 있다고 하자. 식료품점에는 다양한 구매 패턴이 존재할 수 있고 모든 경우의 구매 패턴 가지수는 식료품점의 전체 트랜잭션 수가 된다. 이중에서 전체 트랜잭션 수에 대한 빵, 버터, 우유를 구매한 패턴의 비율이 바로 지지도가 된다.

지지도(Support) = 빵, 버터, 우유를 구입한 트랜잭션의 수 / 전체 트랜잭션의 수

신뢰도는 빵과 버터를 구입한 트랜잭션 수에 대해 빵, 버터, 우유를 구입한 트랜잭션의 수에 대한 비율로 나타낼 수 있다.

신뢰도 = 빵, 버터, 우유를 구입한 트랜잭션의 수 / 빵, 버터를 구입한 트랜잭션의 수

결론적으로 어떤 규칙의 신뢰도는 얼마나 조건부에 대해 결과부가 자주 적용될 수 있는지를 나타내고, 반면에 지지도는 그 규칙의 전부가 얼마나 믿을만한지를 나타낸다고 말할 수 있다.

빈발 항목 집합
트랜잭션 데이터베이스는 중복을 허용하지 않고 순수한 집합의 개념을 확장해 트랜잭션과 다른 모든 항목 집합들 내에 존재하는 항목들은 이미 정렬돼 있는 것으로 가정해야 한다. n개의 트랜잭션들로 이루어진 데이터베이스 D가 존재할 때 고유한 트랜잭션 번호인 TID가 부여된다. 어떤 항목들의 집합 X를 포함하는 트랜잭션 T를 생각해 보자. 만일 트랜잭션 T가 X⊆T일 경우 연관 규칙은 X→Y 형태로 나타날 수 있고 항목들의 부분 집합인 X와 Y의 교집합은 공집합이 된다.

트랜잭션 데이터베이스에서 연관 규칙을 찾는다는 것은 사용자가 명세한 최소 지지도(minsup)와 최소 신뢰도(minconf) 보다 큰 지지도와 신뢰도를 갖는 아이템셋을 찾는 것이라고 말할 수 있고, 최소 지지도보다 큰 지지도를 갖는 집합들을 빈발하다라고 말한다. 이런 경우에 항목들의 집합 X를 빈발 항목 집합(Large Itemset)이라고 한다. 우리가 최소 지지도에 관심이 있는 이유는 트랜잭션 데이터베이스에 대해 관심있을 정도로 자주 일어나는 항목만을 고려해야 하기 때문이다. 지금까지의 내용을 간략하게 정리한다면 주어진 데이터베이스에서 연관 규칙을 찾는다는 것을 다음과 같이 두 단계로 나눠 생각할 수 있다.

단계 1
명세된 최소 지지도 이상의 트랜잭션 지지도를 갖는 모든 항목 집합(itemsets)들을 찾는다. 하나의 항목 집합에 대한 지지도는 해당 항목 집합을 포함한 트랜잭션의 수로 생각할 수 있으며, 최소 지지도를 만족하는 항목 집합을 빈발 항목 집합(Large Itemsets)이라 하며, 그외 모든 항목 집합들을 작은 항목 집합(Small Itemsets)이라 한다. 본 프로젝트에서는 빈발 항목 집합을 찾기 위해서 Apriori 알고리즘을 사용할 것이다.

단계 2
데이터베이스로부터 연관 규칙을 생성하기 위해 빈발 항목 집합을 사용하게 되는데, 모든 빈발 항목 집합 l에 대해서 l의 공집합이 아닌 모든 부분 집합을 찾아야 한다. 이러한 각각의 부분 집합 a에 대해 만약 지지도(a)에 대한 지지도(1)의 비율이 적어도 최소 신뢰도 이상이면, 다시 말해 '지지도(1)/지지도(a) ≥ 최소 신뢰도'이면 'a→(l-a)' 형태의 규칙을 찾을 수 있다. 이 규칙의 지지도는 지지도(1)이고 신뢰도는 지지도(l)/지지도(a)가 된다. 실제적으로 연관 규칙 탐사의 전체적인 성능은 첫째 단계에서 결정되고 먼저 빈발 항목 집합을 확인한 후에 해당되는 연관 규칙을 단계 2의 방법으로 쉽게 유도할 수 있다.