[Recommendation System] 연관규칙분석(Apriori Algorithm)

결혼한 성인 남성이 마트에서 기저귀를 사면 높은 확률로 맥주를 사게 된다는 말이 있습니다. 미국의 대형 마트인 월마트는 고객들의 소비 패턴을 분석한 결과, 맥주와 기저귀가 서로 관련이 없음에도 불구하고 종종 함께 구매되는 현상을 발견했습니다. 이처럼 빅데이터 속 데이터들의 연관규칙을 분석하는 것이 큰 이익이 될 경우가 많은데요 대표적인 연관분석 알고리즘인 연관규칙분석(Apriori Algorithm) 에 대해 알아보겠습니다.

Apriori Algorithm

연관규칙분석이란 어떤 두 아이템 집합이 번번히 발생하는가를 알려주는 일련의 규칙들을 생성하는 알고리즘입니다. 경영학에서 장바구니 분석(Market Basket Analysis) 으로 널리 알려져 있는 방법론인데요, 소비자들의 구매이력 데이터를 토대로 “X 아이템을 구매하는 고객들은 Y 아이템 역시 구매할 가능성이 높다”는 식의 결론을 내는 알고리즘입니다. 인터넷 쇼핑을 할 때 어떤 상품을 고르면 그 상품을 구매한 사람들이 선택한 다른 상품을 제안해준다던지 하는 컨텐츠 기반 추천(contents-based recommendation) 의 기본이 되는 방법론입니다.

그럼 연관규칙분석에 쓰는 데이터부터 살펴볼까요? 동네 편의점의 매출이력(transaction)이 다음과 같이 주어졌다고 가정해봅시다.

ID	Items
1	달걀, 라면, 참치캔
2	라면, 햇반
3	라면, 콜라
4	달걀, 라면, 햇반
5	달걀, 콜라
6	라면, 콜라
7	라면, 햇반
8	달걀, 라면, 콜라, 참치캔
9	달걀, 라면, 콜라
10	양파

위 데이터는 이렇게 해석할 수 있습니다. 1번 고객은 편의점에 들러 달걀, 라면, 참치캔을 샀네요. 7번 고객은 라면과 햇반을, 10번 손님은 양파를 구매한 걸 확인할 수 있습니다. 이를 행렬 형태로 표현하게 되면 아래와 같이 대부분의 셀이 0의 값을 갖는 희소행렬(sparse matrix) 이 됩니다.

ID	달걀	라면	참치캔	햇반	콜라	양파
1	1	1	1	0	0	0
2	0	1	0	0	1	0
3	0	1	0	0	0	1
4	1	1	0	0	1	0
5	1	0	0	0	0	1
6	0	1	0	0	0	1
7	0	1	0	0	1	0
8	1	1	1	0	0	1
9	1	1	0	0	0	1
10	0	0	0	0	0	0

규칙 및 규칙의 효용성 지표

자, 그럼 주어진 데이터로부터 규칙을 만들어볼까요? 사실 무수히 많은 규칙을 만들 수 있을 겁니다. 첫번째 고객 데이터만 가지고도 이렇게 규칙을 만들어낼 수 있습니다. 달걀을 구매하는 사람들은 라면도 함께 산다, 달걀과 라면을 사먹는 사람들은 참치캔도 산다, 참치캔을 구매하는 사람들은 계란도 함께 산다…

우선 용어부터 정의하고 넘어가겠습니다. 조건절(Antecedent) 은 위 예시의 규칙에서 ‘만일 ~라면’에 해당하는 부분입니다. 결과절(Consequent) 은 그 뒷부분에 해당하는 내용입니다. 아이템 집합(Item set) 이란 조건절 또는 결과절을 구성하는 아이템들의 집합입니다.

예컨대 ‘달걀을 구매하는 사람들은 라면도 함께 산다’를 보겠습니다. 여기에서 ‘달걀 구매’가 조건절, ‘라면 구매’가 결과절이며 각각의 아이템 집합은 ‘달걀’, ‘라면’이 되겠습니다. 단 여기에서 조건절 아이템 집합과 결과절 아이템 집합은 말 그대로 집합, 여러개 아이템이 들어가도 되지만 상호배반(mutually exclusive) 이어야 합니다. 다시 말해 조건절에 달걀이 들어가 있다면 결과절에는 달걀이 포함되어서는 안된다는 뜻입니다.

그렇다면 무수히 많은 규칙 가운데서도 좋은 규칙이란 무엇일까요? 규칙의 효용성을 드러내주는 지표는 크게 지지도(support) 와 신뢰도(confidence), 향상도(lift) 가 있습니다. 빈발 아이템 집합을 판별하는 데 쓰는 ‘지지도’는 아래와 같이 ‘조건절($A$)이 일어날 확률’로 정의됩니다.

$For \ the \ rule \ A → B,$

$support(A)=P(A)$

아이템 집합 간의 연관성 강도를 측정하는 데 쓰는 신뢰도는 아래와 같이 조건절($A$)이 주어졌을 때 결과절($B$)이 일어날 조건부확률로 정의됩니다.

$confidence(A→B)= \dfrac{P(A,B)}{P(A)}$

생성된 규칙이 실제 효용가치가 있는지를 판별하는 데 사용되는 향상도는 아래와 같이 조건절과 결과절이 서로 독립일 때와 비교해 두 사건이 동시에 얼마나 발생하는지 비율로 나타납니다. 바꿔 말해 향상도가 1이라면 조건절과 결과절은 서로 독립임을 뜻합니다. 규칙 사이에 유의미한 연관성이 없다는 걸로 받아들이면 될 것 같습니다. 향상도가 2라면 두 사건이 독립이라는 걸 가정했을 때 대비 2배로 긍정적인 연관관계를 나타냅니다.

$lift(A→B)= \dfrac{P(A,B)}{P(A)⋅P(B)}$

규칙의 효용성은 지지도, 신뢰도, 향상도 세 가지를 모두 반영해 평가하게 됩니다. 임의의 규칙1이 규칙2보다 효과적인 규칙이라는 이야기를 하려면 세 지표 모두 클 경우에만 그렇다고 결론을 내릴 수 있게 된다는 이야기입니다.

규칙 생성

자 그럼 이제 규칙들을 실제로 만들어볼 차례입니다. 가능한 모든 경우의 수를 탐색하여 지지도, 신뢰도, 향상도가 높은 규칙들을 찾아내는 방식이 가장 이상적일 겁니다. 하지만 아이템 수가 증가할 수록 계산에 소요되는 시간이 기하급수적으로 증가하게 됩니다(아이템이 $n$개일 때 탐색해야할 모든 경우의 수 : $n∗(n−1)$). 이 때문에 빈발 집합(frequent item sets) 만을 고려하여 연관 규칙을 생성하는 Apriori algorithm 이 제안되었습니다. 핵심 아이디어는 이렇습니다.

예컨대 아이템 집합 {$A$}의 지지도, 즉 $P(A)$가 0.1로 나타났다고 가정해봅시다. 그렇다면 아이템 집합 {$A$, $B$}의 지지도는 아무리 높아도 0.1을 넘지 못할 겁니다. 왜냐하면 $A$가 단독으로 등장할 확률인 $P(A)$는 $A$와 $B$가 동시에 나타날 확률인 $P(A, B)$ 보다는 크거나 같을 것이기 때문입니다. 이 때 {$A$, $B$}는 {$A$}, {$B$}의 초월집합(superset) 이라고 부릅니다.

다시 규칙을 생성하는 과정을 떠올려 봅시다. 만약 임의의 아이템 집합의 지지도가 일정 기준을 넘지 못한다면 해당 아이템 집합의 초월집합의 지지도는 그 기준보다 명백히 더 작을 것이고, 그렇기 때문에 유용한 규칙으로 인정받을 수가 없게 됩니다. 최소지지도 요건을 만족하지 못하는 아이템집합의 규칙들은 애당초 계산할 필요가 없다는 이야기인데요. 이를 그림으로 나타내면 이와 같습니다.

위 그림을 기준으로 설명해드리면 만일 아이템 집합 {$A$, $B$}의 지지도가 사용자가 정한 최소 지지도 요건을 충족시키지 못했을 경우 {$A$, $B$}는 물론 {$A$, $B$}의 초월집합인 {$A$, $B$, $C$}, {$A$, $B$, $D$} 등 8가지 경우의 수를 계산에서 제외하게 됩니다. 이로써 계산효율성을 달성하는 셈이지요.

분석 예시

그럼 예시 데이터를 기준으로 연관규칙분석을 수행해보겠습니다. 최소 지지도 요건을 0.2로 설정했다고 칩시다. 지지도는 이렇게 구합니다. 우선 라면은 전체 10개 레코드 가운데 8번 등장했네요. 그럼 라면의 지지도는 0.8입니다. 마찬가지로 달걀(0.5), 콜라(0.5), 햇반(0.3), 참치캔(0.2), 양파(0.1)의 지지도 역시 구할 수 있습니다. 그런데 양파는 최소 지지도 요건을 만족하지 못했으므로 양파가 끼어있는 모든 규칙은 이후 분석에서 제외합니다.

이번에는 앞 단계에서 살아남은 아이템들을 이용하여 최소 지지도 조건을 만족하는 2개짜리 아이템 집합을 생성합니다. 아래 표와 같습니다.

구분	라면	달걀	콜라	햇반	참치캔
라면		0.4	0.4	0.2	0.2
달걀			0.3	0	0.2
콜라				0	0.1
햇반					0
참치캔

위 표는 이렇게 작성하면 됩니다. 우선 라면과 라면, 달걀과 달걀처럼 중복되는 아이템 숫자는 셀 필요가 없습니다. 따라서 위 행렬의 대각성분은 0으로 놔두면 됩니다. 그럼 라면과 달걀이 한 레코드에 동시에 등장한 빈도를 세어볼까요? 레코드 1, 4, 8, 9, 이렇게 10개 데이터 가운데 네 가지 경우가 있군요. 따라서 라면과 달걀의 지지도는 0.4입니다.

그런데 여기서 아이템 집합 내에서의 순서는 고려하지 않기 때문에 달걀과 라면의 지지도 또한 0.4인데요, 이는 위 행렬이 대칭행렬(symmetric matrix) 라는 뜻입니다. 다만 대각성분 아래쪽으로는 중복된 숫자라 따로 적지 않았습니다.

마찬가지로 다른 아이템들의 지지도를 구해서 행렬을 채우면 되는데요, 이번에도 ‘달걀과 햇반’, ‘콜라와 햇반’, ‘콜라와 참치캔’, ‘햇반과 참치캔’은 최소 지지도 요건(0.2)를 채우지 못했으니 다음 분석에서는 이 경우의 수를 고려하지 않습니다.

이러한 방식으로 더 이상 최소 지지도 이상을 나타내는 아이템 집합이 없을 때까지 아이템 집합의 크기를 1씩 증가시키면서 반복 수행합니다. 이렇게 구한 상위 연관규칙 3가지는 아래와 같습니다. 동네 편의점의 매출이력 10건을 토대로 가장 강한 연관규칙은 ‘참치캔을 구매하는 소비자는 달걀과 라면을 동시에 산다’가 되는 셈입니다.

조건절	결과절	지지도	신뢰도	향상도
참치캔	달걀, 라면	2	1	2.5
참치캔	달걀	2	1	2
라면,참치캔	달걀	2	1	2

‘문서 요약’에 적용

연관규칙을 문서 요약(document summarization) 에도 적용할 수 있습니다. 한 문장을 트랜잭션 데이터로 상정하고, 문장 내 출현한 단어를 아이템으로 놓고 같은 방식으로 분석하는 것입니다. 여기서 도출된 유의미한 규칙은 단어의 co-ouccerrence 정보를 함축할 것입니다. 예컨대 조건절이 {발, 없는, 말이}이라면 결과절은 {간다}가 나온다던지 하는 식입니다. 생각해볼 수록 많은 응용이 가능할 것 같습니다.