티스토리 뷰

최종 수정 : 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 알고리즘에 대한 구체적인 내용을 살펴 보도록 하겠습니다.

댓글
  • 프로필사진 식이 Support는 관계를 설정하기 위한 상품들이 동시에 발생될 확률 이라고 소개해 주셨는데요
    하단 수식 Support = (xUy)/n 이 이해가 되지 않습니다.
    동시에 발생하는 사건이라면 합집합이 아니라
    Support = x^y/n (x와 y의 교집합)으로 나타내야할 거같은데 왜 합집합인건가요?

    출처: http://hackability.kr/entry/Data-Mining-11-연관-법칙-Association-Rule-소개 [HACKABILITY]
    2017.09.07 11:27 신고
  • 프로필사진 hackability 헙...내용에서 중요한 문제 정의 부분이 빠져 있네요... -_-;;;;;;;;;;;;;;

    Item I = {i_1, i_2, ... i_n}
    Transaction T = (t_1, t_2, ... t_n), where t_i is set of itemset st., t_i ⊆ I

    이때 관계룰 X->Y는 X⊂I, Y⊂I, and X∩Y=ф 에서 정의 됩니다.

    이를 말로 표현하면 더욱 이해가 쉬운데요,

    사과, 배를 사고 사과를 산다라고 했을 때,

    X = {사과, 배}
    Y = {사과}

    이는 교집합 "사과" 가 생기기때문에 정의가 되지 않습니다.

    Support는 디비에서 얼마나 X와 Y를 포함하는 트렌젝션이 발생하는지 보기 위한 지표로 X와 Y의 합집합의 카운트에서 전체를 나누게 되고,

    Confidence는 디비에서 X이후 Y에 대한 트렌젝션이 발생하는지 보기 위해 X 에 대한 Y의 확률로 계산하게 됩니다.

    정리하면 Support는 관계룰 X->Y에 대해 순서에는 관심이 없고 아이템셋 X와 Y가 모두 존재하는 트렌젝션이 몇개 인지 (디비에서 X와 Y가 동시에 존재하는 확률) 관심이 있는 지표 이며

    Confidence는 X->Y에 대해 정확한 구매 순서를 가지고 있는 확률 지표 입니다.

    추가적으로 어떤 트렌젝션 T에 대해 관계룰 X->Y를 만들었을 때 Support 값이 매우 낮다 라고 하면 이 관계룰은 우연히 생긴 사건일 수 있습니다. 따라서 모델링을 할때 이러한 사건들은 유용하지가 않으며 Support는 높은데 Confidence가 낮으면 아이템셋X에 대해 Y의 구매 사건이 우연히 발생된 것이다 라고 해석할 수 있습니다.
    2017.09.07 18:39 신고
댓글쓰기 폼