본문
빈발 패턴 마이닝(Mining Frequent Patterns) #1
대형 슈퍼마켓에서는 매일 고객들이 구매하는 물품들에 대한 정보가 축적되고 있는데, 5명의 고객이 상품을 구입한 목록은 아래와 같이 표현될 수 있다. 고객마다 구입한 상품의 수와 종류가 다른데, 한 고객이 구입한 상품 모두에 대한 처리를 하였을 때, 이를 트랜잭션(transaction)데이터를 하나 처리하였다고 한다. 즉, 하나의 장바구니=하나의 트랜잭션
고객1: {사과, 빵, 버터, 계란}, 고객2: {우유, 빵, 버터, 콜라},
고객3: {사과, 우유}, 고객4: {사과, 우유, 빵, 버터}, 고객5: {사과, 우유, 빵, 콜라}
빈발 패턴(frequent pattern)들은 데이터 집합에서 빈번하게 발생하는 패턴들이다. 예를 들어, 트랜잭션 데이터에서 자주 동시에 나타나는 '버터'와 '빵'(혹은 '우유'와 '빵' 등..)이라는 항목은 빈발 항목집합(frequent itemset)이다. PC를 구입하고 다음에 디지털 카메라를 구입하고 그 후 다시 메모리카드를 구입하는 것과 같이 쇼핑 이력 데이터베이스에서 자주 나타나는 부분순차(subsequence)를 (빈발)순차 패턴(sequential pattern)이라 한다.
빈발 패턴 마이닝은 주어진 데이터 집합에서 재귀 관계(recurring relationships)를 찾는다. 빈발 항목집합 마이닝의 전형적인 예는 장바구니분석(market basket analysis)이다. 예를 들어, "고객이 우유를 샀다고 한다면, 그 쇼핑에서 빵을 함께 살 가능성은 얼마나 되겠는가? " 이 질문에 답하기 위하여 상점의 고객 트랜잭션에 관한 데이터에 대해 장바구니 분석을 수행한다. 상점에서 제공되는 상품의 집합으로 이루어진 세계가 있다 가정하고, 각 상품들은 상품의 존재유무를 표현하는 이진(boolean/binary)변수를 갖는다고 하자. 그러면 각 장바구니는 이 변수들에 할당된 값으로 구성된 이진벡터(boolean/binary vector)로 표현할 수 있다.
데이터베이스가 총 n개의 트랜잭션 데이터로 구성되며, 전체 m개의 항목을 포함하고 있을 때, 슈퍼마켓 예제에서 모든 상품들의 항목집합을 i={i1, i2, ... ,im}라 하고 모든 고객 트랜잭션들의 집합을 T={t1, t2, ... ,tn}이라 표현할 수 있다. 각각의 트랜잭션 T는 T⊆I인(T는 I의 부분집합) 항목들의 집합이다. 아래 표는 각 상품의 구매여부를 1과 0으로 표시하여 이진벡터(데이터)로 나타낸 것이다. 장바구니 데이터를 구매여부에 대한 이항데이터로 표시하는 것은 가장 간단한 형태로서, 상품의 개수나 구매한 상품의 가격과 같은 정보는 포함하고 있지 않는다.
고객번호 |
사과(i1) |
우유(i2) |
빵(i3) |
버터(i4) |
계란(i5) |
콜라(i6) |
t1 |
1 |
0 |
1 |
1 |
1 |
0 |
t2 |
0 |
1 |
1 |
1 |
0 |
1 |
t3 |
1 |
1 |
0 |
0 |
0 |
0 |
t4 |
1 |
1 |
1 |
1 |
0 |
0 |
t5 |
1 |
1 |
1 |
0 |
0 |
1 |
k개의 항목을 갖는 항목집합을 k-항목집합이라고 한다. 예를 들어 집합{우유, 빵}은 2-항목집합이다. X와 Y를 서로 공통원소가 없는 항목들의 집합(즉, X⊂I, Y⊂I, X∩Y=공집합)이라 할때, 연관 규칙 R은 R: X⇒Y로 표시하며, 'X가 일어나면 Y도 일어난다'는 의미를 갖는다. 항목집합의 발생빈도(occureence frequency) n(X)를 전체 트랜잭션 중에서 항목집합 X를 포함하는 트랜잭션의 수라 하며, 또는 간단하게 빈도(frequency), 지지도 개수(support count), 항목집합의 개수(count of the itemset)라고 한다. 이는 집합기호로 다음과 같이 정의될 수 있다. n(x)=|{ti|X⊆ti, ti∈T}|
규칙 X⇒Y는 트랜잭션 집합 D에서, 집합 X와 Y를 동시에 포함하는 트랜잭션의 백분율이 s인경우(즉 n개의 전체 트랜잭션에서 연관 규칙에 해당하는 데이터의 비율), 지지도 s를 갖는다고 한다. 이는 확률 P(X∪Y)를 계산함으로써 얻을 수 있다. 집합 X를 포함하는 트랜잭션 중에서 집합 Y도 포함하고 있는 트랜잭션의 백분율이 c인 경우, 규칙 X⇒Y가 신뢰도 c를 갖는다고 한다. 신뢰도는 조건부확률 P(X|Y)를 계산함으로써 얻을 수 있다. 즉
support(X⇒Y)=P(X∪Y),
confidence(X⇒Y)=P(X|Y)=support(X∪Y)/support(X)=support_count(X∪Y)/support_count(X)
위 표에서 연관규칙 '{우유, 빵} ⇒ [버터]'의 지지도는 {우유, 빵}∪{버터}={우유, 빵, 버터}를 모두를 포함하는 트랜잭션인 t2, t4의 전체에 대한 비율이므로 2/5=0.4이고, {우유, 빵}을 포함하고 있는 트랜잭션은 t2, t4, t5 이므로 2/3=0.67이다.
지지도(support)와 신뢰도(confidence)는 규칙의 흥미도를 측정하는 두가지 기준이다. 이 기준 각각은 발견된 규칙의 유용성(usefulness)과 확실성(certainty)를 반영한다. 위 연관규칙에서 지지도 0.4는 분석에 사용된 모든 트랜잭션의 40%가 우유, 빵, 버터를 함께 구매한다는것을 나타낸다. 또한 신뢰도 0.67은 우유와 빵을 구매한 고객의 67%가 버터도 구매한다는 것을 의미한다.
지지도가 낮은 연관규칙은 여러 트랜잭션에 적용되지 않는 규칙이어서 우연히 발생할 수 있는 규칙 또는 흥미가 없는 규칙일 가능성이 많다. 따라서 최소 지지도 임계값(minimum support threshold)을 정하여 그 이하의 규칙은 버린다. 지지도는 좋은 규칙을 찾거나 흥미없는 규칙을 버릴 때의 기준으로 사용된다. 반면에 신뢰도는 연관규칙의 신뢰성에 대한 측도이다. 주어진 연관규칙 X⇒Y가 있을 때, 신뢰도가 높을수록 항목 X를 포함하는 트랜잭션은 항목 Y도 포함할 가능성이 많게 된다.
사용자나 해당 분야의 전문가들에 의해 결정되는 최소지지도를 min_sup, 최소신뢰도를 min_conf라 할떄, 연관규칙을 탐색하는 일반적인 원칙은 최소지지도보다 크면서 동시에 최소신뢰도보다 큰 연관규칙, 즉 강한(strong)규칙을 찾는 것이다. 하지만 모든 가능한 연관규칙을 찾기위한 경우의 수가 너무 많아서 효율적인 탐색 알고리즘에 대한 연구가 계속되어왔다.
댓글