Association Rules - 3

지난 글에서는 보다 빨리 Frequent itemset(이하 Fset)을 찾는 방법을 소개하였다.
그러나, 이전에 소개한 내용은 판매 상품들의 계층적인 구조를 생각하지 않았다.
실제로 판매되는 상품들은 대부분 계층적인 구조로 나타낼 수 있고
이러한 구조에서, Category1을 구입한 사람이 Category2를 구입하거나, Sub Category1을 구입하는 경우를 찾고 싶다면
어떻게 해야할까?

이번에는 계층적인 구조를 가지는 자료에서 Fset을 찾는 방법을 알아보자.

참고논문 : R. Srikant and R. Agrawal, "Mining Generalized Association Rules", VLDB 1995. 
PDF   ps.gz   Abstract   Google Scholar

Figure 1 - 논문에 있는 예제 (Example of a Taxonomy)

Jacket과 Hiking Boots를 산 사람과 Ski Pants를 사고 Hiking Boots를 구입한 데이터에서

Outerwear를 산 사람이 Hiking Boots를 사는 경향을 알고 싶은 경우 어떻게 구할 것인가?

단순히 Jacket->Hiking Boots와 Ski Pants->Hiking Boots의 합으로는 Outerwear->Hiking Boots를 구할 수 없는 것이

하나의 구매 transaction에서 Jacket, Ski Pants, Hiking Boots를 구입했을 수 있기 때문이다.

(말로 하니까 이상한데, 고등학교 때 배운 두 집합의 합을 구하는 것과 같다. A ∪ B = A + B - A∩B)

또한, Outerwear->Hiking Boots가 유효한 룰일 때, Jackets->Hiking Boots나 Clothes->Hiking Boots는 아닐 수 있다.

(전자는 minimum support를 만족하지 못할 수 있고, 후자는 minimum confidence를 만족하지 못할 수 있다.)

 

Generalized Association Rule을 찾는 방법을 스텝별로 나누면,

Step 1. 사용자가 제시한 minimum support를 만족하는 모든 item set을 찾아낸다. (Frequent item sets를 구한다.)

Step 2. Association Rules를 찾는다. (이것은 이전에 소개한 알고리즘으로 수행한다고 하자.)

Step 3. Uninteresting한 Rules들을 잘라낸다. (Pruning: *basic한 알고리즘만 짚고 넘어갈 것이므로, 본 글에서는 다루지 않겠다.)

 

Pruning을 하는 이유는 다음과 같다.

만약, Jacket is-a Outwear라는 계층 구조에서

Outwear à Hiking Boots가 8%의 지지도, 70%의 신뢰도를 보이고

Outwear 판매량의 1/4가 Jacket이라면

JacketàHiking Boots에 대해 약 2%의 지지도, 70%의 신뢰도를 예상할 수 있다.

 

자, 이제 Frequent Item set을 찾아 보자.

 

minimum support = 30%

minimum confidence = 60%

이러한 데이터에서, Frequent Itemset을 찾아내는 방법은, 각각의 Terminal item들을 상위 카테고리로도 Count 하는 것이다.
여기서, Ski PantsàHiking Boots와 JacketàHiking Boots가 minimum support를 만족하지 못한다는 것을 확인하자.
(Apriori algorithm을 적용할 수 있다.)

찾아진 Frequent Item set에서, Association Rule을 때, Pruning을 위해 참고할 사항은 다음과 같다.

{x, y}가 minimum support를 만족한다고 하자. 는 x의 상위 카테고리를 의미하고 는 y의 상위 카테고리를 의미한다고 가정하였을 때, {x, }, {, {, 도 Association Rule을 구하게 되는데, 만약 xày가 minimum support와 minimum confidence를 만족하면, xà은 minimum support와 minimum confidence를 만족하게 되지만 ày, àx 그리고 는 minimum support를 만족하되minimum confidence는 만족하지 않을 수 있다.

(*Pruning은 다루지 않을 것이므로… 그렇다는 것만 알고 있자.)

찾아진 Rule에서, OuterwearàHiking Boots가 있는데 ClothesàHiking Boots가 없는 이유는,

앞서 설명했던 minimum support는 만족하지만minimum confidence를 만족하지 못하여 룰에서 제외된 것이다.

첫 번째 룰에 대한 식을 쓰자면.

아래의 식을 잊지 말자.