지금까지 클러스터링(Clustering), 분류(Classification), 회귀(Regression)에 대해 알아보았다. 어떤 문제에 어떤 방법을 적용해야하는지 정확히 이해하는 게 중요한니까 초반에는 암기하듯이 외워두는 것이 좋다.
| 비지도 학습 (Unsupervised Learning) | 지도 학습 (Supervised Learning) |
|---|---|
| 데이터 내 패턴 찾기 | 데이터로 모델을 학습하여 예측 |
| 기술적(Descriptive) | 예측적(Predictive) |
| 클러스터링, 연관 규칙 마이닝, 텍스트 마이닝 | 분류, 회귀, 텍스트 마이닝 |
■ 연관 규칙 마이닝이란?
클러스터링, 회귀 등은 그래도 익숙할텐데 연관 규칙 마이닝이란 단어는 다소 생소할지도 모른다. 마케팅 시간에 배운 “맥주와 기저귀 사례”가 바로 연관 규칙 마이닝으로 알게 된 관계다. 맥주와 기저귀 관계를 처음 보는 사람들을 위해 간단히 설명하자면, 기저귀와 맥주를 같이 사는 사람이 많아 해당 상품을 양 옆으로 진열했더니 매출이 올랐다더라… 카는 이야기다.
연관 규칙 마이닝은 이렇게 장바구니 분석(Market Basket Analysis)에 처음으로 고안되어 사용되었다. 즉, 고객이 사는 아이템끼리 어떤 관계가 있는지 찾기 위한 노력의 일환이라고 생각하면 된다. 레이블 되어 있지 않은 아이템들의 경향을 보는 것이기 때문에 비지도학습 중 하나이다.
다만, 연관 규칙에서 찾아지는 규칙은 동시에 나타나는 것을 의미하지 인과 관계(Causality)를 의미하는 것이 아님을 주의깊게 보고 넘어가자.
■ 지지도와 신뢰도
무수히 많은 아이템 구매 내역 중에 중요한 것(또는 중요할 것 같은)만 찾아볼 수는 없을까? 라는 질문을 대답하기 위해서는 지지도(Support)와 신뢰도(Confidence)에 대해 먼저 알아야 한다.
지지도는 아이템셋의 빈도를 말한다. 위와 같은 아이템 구매 기록이 있다고 하자. 우유, 달걀, 맥주 아이템셋의 지지도는 전체 5개의 데이터 중에 2개가 있으므로 0.4 이다.
신뢰도는 조건부 확률을 의미한다. 조건부 확률은 수학에서는 p(Y|X) 라고 쓰는데 X라는 조건이 주어졌을 때 Y가 발생할 확률을 의미한다. 위의 {고기, 두부} -> {맥주} 를 수식으로 옮기면 p(맥주 | 고기, 두부) 이다. 즉 {고기, 두부}가 포함되어 있는 아이템셋 중에 {맥주}가 있는 아이템셋이 몇개 있는지 확인하면 된다. 위의 그림처럼 {고기, 두부}가 있는 아이템셋은 2개이고 {고기, 두부, 맥주}가 있는 아이템셋은 1개 이므로 확률은 0.5이다.
연관 규칙 마이닝은 T라는 거래 내역이 있을 때 지지도와 신뢰도가 연구자가 정해놓은 임의의 값(threshold)보다 큰 아이템셋을 추출해서 살펴보는 것으로 시작한다.
■ 다양한 접근법 (Brute-force, Apriori algorithm, FP-growth)
Brute-force 접근법은 모든 가능성 있는 연관 규칙을 나열한 뒤에 지지도와 신뢰도를 계산하고 임의의 값보다 작은 것은 없애는 방식을 취한다. 당연히 계산적으로 비싸고 시간도 오래 걸릴 수밖에 없다.
Apriori 알고리즘은 먼저 빈도가 높은 아이템셋(지지도가 >= 최소 지지도, 즉 연구자가 설정한 임의의 값)을 먼저 찾은 뒤 규칙을 찾는 방식이다. 이 때 계산 방식은 단순화하기 위해 지지도와 신뢰도가 갖는 특성을 이용한다.
첫 번째는 지지도의 Anti-monotonicity 특징이다. X가 Y의 서브셋일 때 Y의 지지도가 그 어떤 X의 지지도보다 항상 더 크다는 특성인데 그림으로 살펴보자.
우유의 지지도는 0.8이다. 우유의 서브셋을 나열하고 각각의 지지도를 구한 결과가 오른쪽에 있다. 살펴보면 서브셋의 지지도는 우유의 지지도인 0.8보다 항상 더 낮다는 것을 알 수 있다. 이를 통해 우리는 Apriori principle을 도출해 낼 수 있다. 즉, X(우유의 서브셋)가 자주 나타나는 아이템이라면 Y(우유) 역시 자주 나타나는 아이템이란 사실이다. 이게 연관 규칙 찾는 데에 무슨 의미인고 하면…
우유, 계란, 맥주, 두부 4가지 아이템이 있는 경우에 원래 Brute-force 접근법을 사용하면 위의 경우의 수를 모두 나열하고 각각의 지지도와 신뢰도를 구한다고 했다. 즉 2의 n승의 경우의 수를 고려해야 한다(위 예시 그림에서는 총 16가지 경우의 수가 있다).
Apriori 알고리즘은 만약에 {우유, 계란}의 지지도나 신뢰도가 연구자가 정의한 임의의 값보다 작을 경우 서브셋을 계산할 필요없이 빨간색 점선으로 묶여진 모든 그룹을 지우게 해준다.
두 번째는 신뢰도는 왼쪽에서 오른쪽으로 이동할 때 항상 작아진다는 규칙이다. 이는 s({A})가 s({A, B})보다 항상 더 크다는 지지도의 규칙이 있기 때문에 발생하는 현상이다. 간단하니 그림을 살펴보면 이해할 수 있을 것이다.
Apriori principle과 마찬가지로 신뢰도의 특징을 이용해서 아이템셋의 신뢰도가 최소 신뢰도보다 작을 경우 해당 아이템셋의 서브셋을 모두 가지치기 한 후 계산하면 된다. Brute-force보다 간편하나 여전히 모든 데이터베이스를 읽고 계산해야한다는 단점이 있다.
그래서 도입된 알고리즘이 바로 FP-growth Algorithm이다. FP-tree라는 데이터베이스의 집약체를 이용하는데 원리가 어떤지 간략하게만 소개하도록 하겠다.
먼저 첫 번째 데이터 셋을 읽어와 오른쪽과 같이 트리를 그린다.
두 번째 Egg는 이미 그려져 있기에 포인터를 사용해서 화살표로 표시한다.
세 번째 데이터 셋은 첫 번째 데이터셋과 같으므로 카운터만 1개씩 늘린다.
2단계와 마찬가지로 포인터를 이용해 연결하고 새로운 아이템이 있을 경우 추가한다. 이러한 방식을 반복적으로 수행하면 FP-Growth 를 구현할 수 있다. FP-Growth의 장점은 데이터베이스를 두 번만 스캔하면 된다는 것이다(첫 번째 스캔을 하면서 모든 아이템셋을 카운트하고, 두 번째 스캔을 하면서 FP-tree를 만든다). 연관 규칙은 한 번 만들어진 FP-tree를 보고 찾으면 끝!
또한 용량도 비교적 적게 사용할 수 있는데 만약 {우유, 계란}이라는 아이템셋이 1번과 3번에 동일하게 나타날 경우 나무 사이즈가 늘지 않고 빈도수(카운트)만 늘어나기 때문이다. 이 외에도 빈도수로 정렬이 가능하고 포인터만 따라가면 지지도를 구하기 쉽다는 점, 비슷한 거래일수록 잘 압축해서 표현 가능하다는 점에서 유용하다.