[Data Mining] 1.1. 연관 법칙 (Association Rule) 소개

최종 수정 : 2014-11-03

안녕하세요. Hackability 입니다.

첫 번째 마이닝 포스팅 내용은 데이터 간의 연관 규칙과 순차 패턴 마이닝에 대한 내용입니다.

# 연관 법칙 (Association Rule) 소개

Association Rule은 데이터 간의 연관 법칙을 찾는 방법입니다. 가장 대표적으로 마켓 구매를 들 수 있습니다. 마켓에는 야채, 과자, 음료, 옷, 등등 여러 가지 상품을 파는데 소비자들이 상품을 구매하는 이력을 이용하여 상품간의 연관관계를 만들고, 관계 있는 상품, 관계 없는 상품 등을 구할 수 있습니다. 이처럼 연관 마이닝은 관계가 있는 아이템 찾기를 목표로 합니다.

연관 법칙 마이닝에서 가장 기본이 되는 단위인 상품을 의미하는 Item과 구매내역을 의미하는 Transaction 이라는 용어가 있습니다. Item은 말 그대로 야채, 과자, 음료 등을 의미하며 Transaction은 Item의 구매 로그 라고 생각하시면 됩니다. (DB에 관심이 있으신분은 상당히 익숙한 용어 겠죠 :-) ) 앞으로 Item 집합을 'I'로, Transaction 집합을 'T'로 정의하며 수학적인 표현으로는 아래와 같습니다.

연관 관계 마이닝에서 연관 관계를 설정하기 위해 Support, Confidence라는 두 가지 중요한 요소가 사용되게 됩니다. Support는 관계를 설정하기 위한 상품들이 동시에 발생될 확률을 의미 하며, Confidence는 특정 상품이 선택된 뒤, 다른 상품이 선택될 확률을 의미 합니다.

Support와 Confidence의 수학적인 표현은 다음과 같습니다.

Support 라는 요소는 X와 Y라는 아이템이 로그에서 얼마나 자주 발생되는지 측정해 줍니다. 만약 Support값이 매우 낮다면 그 아이템은 낮은 확률로 선택되었음을 의미합니다. Support 측정 도구를 통해 우리는 로그에서 특정 로그가 우연히 발생된건지 아니면 일반적으로 발생된건지 측정할 수 있습니다.

Confidence 라는 요소는 조건부 확률로 Y가 선택되었을 때, X가 선택되었을 확률을 의미하며 두 아이템간의 순차적인 연관성을 설명해 줍니다. 따라서, 아이템 간의 발생 순서를 고려하기 때문에 predictability (예측 가능성)을 결정할 수 있습니다. 만약 특정 아이템 간의 Confidence가 매우 낮다면 일시적으로 발생된 이벤트 시퀀스를 의미하며 정상적인 경우에는 잘 나타나지 않는 발생 순서임을 알 수 있습니다.

간단한 예를 들어, 위 요소를 설명해보도록 하겠습니다. Hackability라는 마켓에서는 PDF, Flash, WordPress, Hangul, Gom Player, MS Word 의 zero-day를 팔고 있다고 가정해 봅시다. 평소에 zero day에 관심이 많은 codered 친구들이 물품을 구매 했고, 구매 내역은 다음과 같다고 가정해봅니다.

Item = {PDF, Flash, WordPress, Hangul, Gom Player, MS Word}

Transaction = 

( 

  {PDF, Hangul, MS Word}, 

  {WordPress, Gom Player}, 

  {PDF, Hangul Gom Player, MS Word}, 

  {Flash, WordPress, Hangul, Gom Player},

  {Flash, WordPress, Gom Player, MS Word},

  {PDF, Hangul}

)

우리가 여기서 하려고 하는 것은, Transaction로그를 통해 의미 있는 내용을 도출하려고 합니다. 이 때 Support와, Confidence를 이용하여 의미있는 내용을 찾을 수 있습니다. 만약 관리자가 Minimum Support는 30%가 넘으면서 Minimum Confidence가 70%가 넘는 로그를 찾는다고 가정합니다. (sup은 support를 의미하며 conf는 confidence를 의미하며, minsup은 minimum support를 의미하며 minconf는 minimum confidence를 의미합니다.)

PDF, Hangul -> MS Word [ sup = 2/6 = 33%, conf = 2/3 = 66% ]

위와 같은 경우, 관리자가 설정한 minimum support는 충족 시켰지만 minimum confidence는 충족하지 못하였기 때문에 관심 있는 로그가 아닙니다. 그렇다면 다음 로그는 어떨 까요?

WordPress -> Gom Player [ sup = 3/6 = 50%, conf = 3/3 = 100% ]

따라서, WordPress -> Gom Player라는 관계가 관리자가 관심이 있는 로그로 판단할 수 있습니다. 물론 위 룰보다 관리자 조건을 만족하는 룰들이 있을 테고, 여기서는 Zero-Day의 임팩트 라던지 가격등을 고려하면 더욱 다양한 의미를 추출 할 수 있습니다.

위의 예를 보면, Transaction의 양이 굉장히 작기 때문에 직관적으로도 몇 가지 관계가 있는 룰을 뽑을 수 있었지만, 실생활에서는 수 많은 로그들이 발생되기 때문에 관리자가 설정한 조건을 만족하는 룰을 직관적으로 찾는 다는 것은 매우 어려운 일입니다. 그렇기 때문에 이런 작업을 컴퓨터로 맡겨야 하는데 이를 어떻게 할까요?

데이터 집합 T가 주어지고, min sup, min conf가 주어졌을 때, 만족하는 rule을 찾는 알고리즘이 바로 Apriori 알고리즘 입니다.

1.2 에서는 Apriori 알고리즘에 대한 구체적인 내용을 살펴 보도록 하겠습니다.