[데이터마이닝] 추천 알고리즘 : Association Rule Mining

2021.09.08 <데이터 마이닝> 수업 필기

1. Assocation Rule 이란?

Study of "what goes with what?"

어떤 물건을 어떤 물건과 함께 살까? 동시 발생의 가능성이 큰 사건/규칙을 발견!

예) 물건 X를 산 고객은 물건 Y도 구매한다.

= 'market basket analysis' 또는 'affinity anlaysis'라고 불린다

 

데이터의 형태 : transaction-based 또는 even-vased 

예) 한 바구니에 든 여러 개의 상품들

 

장바구니 ID (Transaction)	구매 물품 ID (Items)
1	a,b,c
2	a,d
3	b,d

 

☞ '물건 A를 산 사람은 물건 B도 사더라'하는 규칙(Rules)을 발견하는 것이 목표!

2. Generating Rules

[용어 정리]

"IF" part = antecedent(조건), "THEN" part = consequent(결과)

조건과 결과는 동시에 똑같은 물건을 가지지 않는다. 예) 고기를 산 사람은 고기도 산다. (X)

 

룰 만들기 조건 1. Many rules are Possible

장바구니 ID =1 인 데이터에 대해서 여러 가지 규칙을 만들 수 있다.

예) '물건 a를 산 사람은 b도 산다.', '물건 a,b를 산 사람은 c도 산다.', '물건 a를 산 사람은 b,c도 산다.' 등등

 

하지만 다른 장바구니에 대해서는 False인 규칙들도 있기 때문에 우리는 여러 장바구니에 대해 True 인 규칙을 찾고 싶다. 전체 트렌드를 읽을 수 있는 규칙을 찾고 싶다.

 

룰 만들기 조건 2. Frequent Item Sets

이상적으로는 모든 아이템들의 조합의 경우의 수를 다 따지면 좋겠지만, 컴퓨터 수행에 따른 시간과 비용이 너무 많이 든다. 

따라서 우리는 자주 발생하는 아이템에 대해서만 고려한다. 그 기준을support(최소 발생 횟수)라고 부른다. 

예) 모든 장바구니에서 support=2, 즉 2번 이상 담긴 물품에 대해서만 경우의 수를 고려한다. 위의 예시에서는 물품 d가 발생한 경우의 수는 고려하지 않는다.

 

Support

1) 아이템 : 전체 transactions에 대한 최소 발생 횟수(#) 또는 확률(%) 

2) 규칙 : 전체 조건과 결과에 포함한 최소 발생 횟수(#) 또는 확률(%)

 

3. Apriori Algorithm (연관규칙분석)

1. 작동 방식

0) 입력 : transaction 데이터셋

1) min_support, min_confidence 결정

2) frequent rule 생성 (Apriori Property 이용)

3) rule의 confidence, lift 계산

4) lift 순 정렬

5) min_support, min_confidence 조정 후 1단계부터 반복

6) 출력 : frequent rule

 

Apriori Property I

데이터의 부분집합인 X가 자주 발생하면, 해당 집합에 포함된 모든 요소들도 자주 발생한다.

If set X is frequent, any of its nonempty subsets is frequent

 

예) {빵, 우유}을 포함하는 transaction 비율이 5% 이상이라면, {빵}, {우유}를 포함하는 transaction 비율 모두 5% 이상이다.

 

Apriori Property II
데이터의 부분집합인 X가 자주 발생하지 않으면, 해당 집합을 포함한 집합도 자주 발생하지 않는다.

If set X is NOT frequent, any superset containing X is NOT frequent.

 

예) {빵, 우유}를 포함하는 transaction 비율이 5% 미만이면, {빵,우유,버터}를 포함하는 transaction의 비율도 5% 미만이다.

 

2. Generating Frequent Item Sets

n개의 아이템에 대해서 min_support = 2 라고 가정하자.

[1st scan]  각 아이템이 몇번 발생했는지 count한 테이블 = C1

[C1 → L1] min_support 값보다 적게 발생한 요소 삭제 = L1

[L1 → C2, 2nd scan] L1 요소들의 조합으로 2개의 아이템이 동시에 발생한 경우의 수 count한 테이블 = C2

[C2 → L2] min_support 값보다 적게 발생한 요소 삭제 = L2

[L2 → C3] Apriori Property II 를 이용 : subsets 중에 자주 발생하지 않는 경우가 있다면 해당 candidates제거

* C2 테이블에서 {A,B}와 {A,E} 발생 횟수가 min_support 보다 작아서 제거

candidates	subsets frequent?
{A, B, C}	{A, B}	{A, C}	{B, C}
{A, B, E}	{A, B}	{A, E}	{B, E}
{A, C, E}	{A, C}	{A, E}	{C, E}
{B, C, E}	{B, C}	{B, E}	{C, E}

[C3 → L3, 3rd scan] C3 경우의 수를 count한 테이블 = L3

 

[출처 : developpaper - Association rule mining and Apriori algorithm]

 

3. 성능 평가 

1) confidence : 조건 A를 만족하는 transaction 중 결과 B를 함께 포함하고 있는 transaction의 비율 = 조건부확률 P(B|A)

(그림 예시) Rule : A → B의 confidence = P(B|A) = P(A∩B) / P(A) = 1/4 / 1/2 = 1/2

 

예를 들어 '콜라를 산 사람은 햄버거를 사더라'하는 규칙의 confidence를 구하면 매우 높은 값을 가질 수 있지만 그 데이터를 조사한 장소가 햄버거 매장이라면 '햄버거를 산다'는 행위 자체가 많이 일어나기 때문에 confidence는 의미가 없다.

결과가 전체 데이터 셋 중에 얼마나 많이 혹은  자주 발생하는지 알 필요가 있다. → lift

 

2) lift (= bencmark confidence): 전체 transaction 중 결과 B를 포함한 확률 = P(B|A)/P(B) = P(A∩B)/ (P(A)*P(B))

(그림 예시) P(A∩B)/ (P(A)*P(B)) = 1/4 / (1/2 * 3/4) = 2/3

 

※ 주의할 점

- Random한 데이터에서도 Association Rules을 발견할 수 있다. 이러한 규칙은 아무런 의미가 없다. 검사해서 걸러낸다.

 

4.  Practical Tips

1) min_support, min_confidence 선정

값이 너무 작으면 적게 발생하는 요소들이 제거되지 않아서 룰이 많이 나오고, 반대로 값이 너무 크면 룰이 적게 나온다.

min_support 값이 너무 작으면 여러 경우의 수를 고려하느라 수행시간이 오래 걸리기 때문에 일단 크게 설정하고 점점 줄여나간다.

 

2) 적절한 입도(granularity)/범위 선정 

 

(예1) '다이어트 코카콜라 250ml'를 산 사람은 '치즈버거'를 산다.

(예2) '고기'를 산 사람은 '채소'도 산다. '채소'를 산 사람은 '음료수'도 산다.

 

(예1)의 경우, 입도를 너무 작게 잡아서 발생하는 경우의 수가 작아서 min_support에 의해 걸러질 수 있다. 규칙으로 도출해내기 어렵다.

(예2)의 경우, 입도를 너무 크게 잡아서 일반적인 규칙이 도출되고, 비즈니스적으로 활용하기 어렵다. 

따라서, 적절한 입도/범위를 잡는 것이 중요하다.

 

3) 가상 아이템 Virtual Items

어떤 룰을 보고 싶은지에 따라서 다르게 지정한다.

 

4) Event 도 item

제조 데이터 분석시에 도움이 된다.

모든 item(event)는 transaction으로 볼 수 있다.

 

4. SUMMARY

• 연관규칙분석은 추천 시스템에 넓게 쓰인다.
• 연관규칙분석 중에서 가장 유명한 것이 Apriori Algorithm이다.
• 이 알고리즘의 장점은 'frequent'라는 개념을 사용해서 컴퓨터 연산 시간을 줄인다.
• 이로부터 도출된 규칙의 효용성을 confidence와 lift로 계산된다.
• 단점은 랜덤한 데이터로부터 말도 안되는 규칙이 나올 수 있다.

 

 

참고 문헌

• developpaper, Association rule mining and Apriori algorithm, https://developpaper.com/association-rule-mining-and-apriori-algorithm/