Association Analysis / Association Rule / Apriori 알고리즘 - 1 of 3

연관글 보기

Association Analysis / Association Rule / Apriori 알고리즘 - 1 of 3

Association Analysis / Association Rule / Apriori 알고리즘 - 2 of 3

Association Analysis / Association Rule / Apriori 알고리즘 - 3 of 3

이 번에는 연관분석에 살펴보도록 하자. 연관분석을 장바구니 분석(market basket analysis)라고도 불린다. 또는 Association Rule, Apriori 알고리즘이라고도 불린다.

가장 많이 언급되는 예시는 월마트에서 기저귀를 구매하는 사람이 맥주도 많이 구매하는 패턴을 파악해서, 진열대에 함께 두면 잘 팔린다는 것이다.

(중요한 것은 아니지만 사실 이 예시는 정확하지 않다는 이야기가 있다.^[각주:1] )

기저귀를 구매하면 맥주도 구매한다고 할 때, association rule이 생성 되었다면, 확률이 얼마인지도 알아야 신뢰성이 생길 것이다. 

연관분석에서는 지지도(support)와 신뢰도(confidence)라는 두 가지 지표를 사용하여 신뢰성을 판단한다.(뒤에서 Lift라는 지표도 나온다)

\(지지도 = support(X\rightarrow Y) = X\cap Y / Z = \) 전체 건수 중 X와 Y가 모두 포함되어 있는 건수의 비

\(신뢰도 = confidence(X\rightarrow Y) = X\cap Y / X = \) 항목 X를 포함하는 건수 중에서 X와 Y를 모두 포함하는 건수의 비

지지도는 X와 Y가 동시에 존재하는 확률이고, 신뢰도는 X가 존재할 때 Y가 존재할 조건부 확률과 같다. 우리는 지지도와 신뢰도가 최소한보다 높은 것을 사용해야 한다. 따라서 연관규칙의 탐색 원칙은 아래와 같다.

support >= min(support) and confidence >= max(confidence)

보통은 최소지지도를 정하여 그 이하는 버리고 신뢰도가 어느 정도 높은 것만 사용한다. X와 Y의 조합의 수가 많기 때문에 최소지지도 이상의 데이터를 찾기 위해 모든 경우의 수를 만드는 것에는 많은 비용이 발생한다. Z는 상수이기 때문에 \(X \cap Y\)를 구하는데 문제가 되는데 이것을 구하는 과정을 빈발항목집합의 생성이라고 한다.(Frequent Item Set Generation)

모든 항목의 집합을 \( X = {x_1, x_2, x_3, ..., x_n} \)일 때 모든 가능한 부분 집합의 수는 공집합 제외시 \(2^n-1\)이다.

\(X={a, b, c}\)로 구성되었을 때, 이것의 부분집합의 개수는 7개이고, 7개 중 최소한의 빈발항목집합을 골라내야 한다. 하지만 항목이 많다면 많은 시간과 비용이 발생할 것이다. 이럴 때는 선험적 규칙(Apriori Principle)을 적용할 수 있다. 이 규칙을 사용하면 경우의 수를 아주 많이 줄일 수 있다. 

규칙1. 한 항목집합이 빈발하면 그 집합의 모든 부분집합은 빈발항목집합이다.

규칙2. 한 항목집합이 비빈발이면 이 항목집합을 포함하는 모든 집합은 비빈발항목집합이다.

(선험적 규칙에 대한 상세한 설명을 나중에 추가할 것이다.)

또 하나의 연관규식을 평가하는 하는데 많이 쓰이는 것은 리프트(lift)이다. 이 것을 향상도라고도 불리며 연관규칙의 신뢰도 \(c(A \rightarrow B)\)의 결과에 대한 지지도 s(B)로 나눈 값이다. 이 지수는 지지도와 신뢰도를 동시에 고려한다는 장점이 있다.

$$ Lift(A, B) = {c(A \rightarrow B) \over s(B)} $$

항목 A, B가 서로 독립이면 Lift는 1이 되어 향상도가 0이라는 의미가 된다. Lift라 1보다 크면 A, B가 양의 상관을 갖고 Lift가 1보다 작으면 음의 상관을 갖는다는 의미이다.

요즘은 Apriori 알고리즘보다 속도가 빠르고 효율적인 다양한 알고리즘을 사용한다. 그 중 FP-growth 알고리즘을 많이 사용한다.

FP-growth 알고리즘에 대해서는 다음에 다시 이야기 하도록 하자.

연관글 보기

Association Analysis / Association Rule / Apriori 알고리즘 - 1 of 3

Association Analysis / Association Rule / Apriori 알고리즘 - 2 of 3

Association Analysis / Association Rule / Apriori 알고리즘 - 3 of 3

---

Reference

http://ar-eum.com/

1. 사실은 미국의 "Osco Drug"라는 상점의 사례이며, 실제롤 적용을 하지 않았다고 한다. http://www.dssresources.com/newsletters/66.php [본문으로]