Association Rules

장용근·2024년 10월 29일

Apriori Algorithms Association Rules FP-growth Algorithm

What is Association Rule?

Find how items purchased by customers are related.

큰 규모의 데이터셋에서 어떠한 규칙을 찾는 데이터 마이닝 기법이다.
동일한 카테고리에 속하는 여러 아에팀들은 서로 연관이 있다는 보편적인 방식으로 관계를 규정하지 않고, 아이템들의 소비 및 사용되는 패턴으로 아이템들을 연관짓는다.
"카테고리"->"아이템" 으로 이어지는 Top-down 방식이 아니라
"아이템"->"연관 관계 규칙"으로 이어지는 Bottom-up방식으로 연관 규칙을 찾아낸다.

예를 들어,

기저귀를 산 경우 유아 용품을 살 확률이 높다.
신발을 장바구니에 담은 고객들의 경우 양말이나 의류를 구매할 확률이 높다.
Categorical data(범주형 자료)를 가정한다.
100% 완벽한 알고리즘은 존재하지 않다. 단, 비교적 더 효율적인 알고리즘만 나오는 것이다.
추천 시스템, 전화통신, 신용카드, 은행 업부, 의료, 스포츠 경기 등에 사용된다.

Example Transaction Dataset: Phone Faceplate Purchases

Binary Matrix (혹은 비트맵)

Transaction이란?
어떤 사람이 어느 한 시점에 구매한 물품들의 집합 (데이터베이스의 transaction과는 다른 개념)

Definitions

Transaction: e.g., t1:{bread,cheese,milk}, t2:{apple, eggs}
Item: transaction 내부에 있는 item 혹은 article
Itemset: 한개 혹은 그 이상의 아이템 혹은 article 의 집합
Transaction: Itemset의 일종
Transactional dataset(or database): transaction들의 집합
Association Rule: Itemset X(원인 또는 조건, Antecedent)가 발생했을 때 itemset Y(결과, Consequent)가 높은 확률로 일어나는 패턴

Support

Support(지지도)는 특정 아이템 또는 아이템들의 조합이 얼마나 잦은 빈도로 구매되거나 관심을 받았는지에 대한 지표이다.
하나의 상품에 대해서도 적용이 가능하지만, 상품군에 대해서 Support 지표를 구하는 것이 일반적이다.

Support를 수학적으로 표현하면,

Support(X) = X의 노출 빈도 / 전체 상품의 노출 빈도

두 상품 A, B가 동시에 노출된 횟수가 100회이고, 개별 상품의 노출 수의 총 합이 1000회라고 한다면,
Support(A, B) = 100 / 1000 = 0.1이다.

Confidence

Confidence는 신뢰도라고 불리며, 조건부 확률을 의미한다.
조건이라는 의미 자체가 전제조건과 그에 따른 결과를 수반한다.
전제 조건을 Antecedent, 조건에 따른 결과를 Consequent라고 한다.
Confidence를 문장으로 풀어서 설명하면,
상품 A를 구매하였을 때, 상품 B를 구매할 확률로 설명할 수 있다.
상황에 따라

상품 A에 관심이 있다면, 상품 B 또한 관심을 가질 확률
상품 A를 장바구니에 담았다면, 상품 B 또한 장바구니에 담길 확률
... 등으로 표현 가능하다.

Confidence(A->B) = Support(A U B) / Support(A) = Probability(B | A)

Lift

Lift는 향상도라고 불리며, 항목 A와 B의 동시 출현 빈도가 서로 독립적일 때에 비해 얼마나 더 자주 발생하는지를 나타내는 척도이다.
휩게 말해 Lift(X->Y)는 X와 Y가 함 께 일어날 확률과 Y 혼자 일어날 확률의 비율을 의미한다.

Lift(X->Y) = Confidence(X->Y) / Support(Y)

Lift(X->Y)가 1이면 X와 Y의 매출은 세트된 품목 내에서 상관관계가 없다.
Lift(X->Y)가 1보다 크면 X와 항목 집합 내에 양의 상관관계가 있다. 즉, X와 Y가 함께 구입될 가능성이 높다.
Lift(X->Y)가 1미만이면 항목 집합 내에 음의 상관관계가 있다. 즉, X와 Y를 함께 구입할 가능성이 낮다.
Lift가 1보다 작거나 같으면 선행 및 결과와 관련된 규칙을 도출할 수 없다.
Lift가 1보다 큰 경우 규칙은 향후 데이터 세트의 결과를 예측하는데 잠재적으로 유용하다.

Rule-based Algorithm

Model-Based Algorithm과 반대되는 머신러닝 학습방식이다.
Model-Based Algorithm은 데이터의 패턴을 학습한 후 적절한 Rule을 찾아서 Prediction을 수행한다.

Linear Regression의 경우 Model-based algorithm을 통해서 feature 값인 bias값과 기울기 값을 얻을 수 있다.

Association Rules의 경우에는 보통 Rule-based algorithm을 사용한다. Association rules은 대개 비지도학습의 케이스가 많기 때문에 Label과 Dataset에 해당하는 상관관계를 추출하기 어렵다. 그래서, Support threshold, confidence threshold를 어떤 값으로 할지 등을 기반으로 Rule을 사전에 정의한다.

Support and Confidence Example

(1) Support for an itemset {Chiken, Clothes, Milk}

Itemset X 개수 / 전체 Transaction 개수 = 3 / 7

(2) Confidence for an itemset
X: {clothes} -> Y: {Milk, Chicken}
-> confidence(X->Y) = Support(X, Y) / Support(X) = 3/7 / 3/7 = 1

X: {Beef, Cheese} -> Y: {Chicken}
-> confidence(X->Y) = Support(X, Y) / Support(X) = Support(X,Y) / Support(X) = 2/7 / 3/7 = 2/3

(3) Lift for an itemset
-> X: {Beef, Cheese} -> Y: {Chicken}
lift or rule {Beef,Cheese}->{Chicken} = confidence(X->Y) / Support(Y) = {Support(X,Y)/Support(X)} / Support(X) = (2/3) / (5/7)
-> 만약 lift == 1이면, antecedent와 consequent사이에는 correlation이 없다.
만약, lift > 1이면, positive correlation이 존재한다.
만약, lift < 1이면, negative correlation이 존재한다.
만약, lift <=1이면, 아무런 규칙이 없다.

Association Rule Mining Task

주어진 transaction T에 대하여, association rule의 목표는 존재하는 모든 규칙들을 찾아내는 것이다.

min_support_threshold: 최소 support
min_confidence_threshold: 최소 confidence

Frequent Itemset Generation

Frequent Itemset을 생성하기 위해서는 Brute Force 방식을 사용할 수 있다. 가능한 모든 연결 규칙들을 나열하고, 각 규칙에 대한 Support 및 Confidence 계산한 후 minimum_support_threshold, minimum_confidence_threshold에 실패하는 규칙을 제거하는 것이다. 이는 너무 많은 계산 시간을 요구한다. 따라서, 우리는 Apriori algorithm과 FP(Frequent Pattern) growth algorithm을 사용한다.

Apriorio Algorithm

사용자 지정 support 및 confidence를 충족하는 규칙을 생성한다.

1단계: 빈번하게 나타나는 항목 집합(충분한 support가 있는 항목)을 찾는다.
2단계: 충분한 confidence를 가지고 있는 항목 집합에서 규칙을 생성한다.
minimum_support_threshold & minimum_confidence_threshold 설정
지원 조건을 충족하는 단일 항목 집합 목록 생성
단일 항목 집합 목록을 사용하여 지원 기준을 충족하는 두 항목 집합 목록을 생성
두 항목 집합의 목록을 사용하여 지원 기준을 충족하는 세 항목 집합의 목록 생성
k 항목 집합까지 반복
k가 증가하면 support가 감소하므로 생성할 후보 항목 집합의 수를 줄일 수 있다.

Walkthrough Example

아래와 같은 Transaction dataset에서 Association Rule을 찾아보자

minimum_support_threshold = 0.5
minimum_confidence_threshold = 0.8

one-item candidates

2-item candidates

3-item candidates

Confidence test 를 적용하여 최종적으로 association rules set을 찾는다.

Python Code

import numpy as np
import matplotlib.pyplot as plt import pandas as pd
from apyori import apriori

# Import the data
movie_data = pd.read_csv(‘C:\Python\MarketBasket\Movie Example\movie_dataset.csv’,header = None) 
num_records = len(movie_data)
print(num_records)

# Data preprocessing
# The Apriori requires the dataset to be in the form of a list of lists.
# Currently, we have data in the form of a Pandas dataframe.
records = []
for i in range(0, num_records): 
	records.append([str(movie_data.values[I,j]) for j in range(0, 20)])

association_rules = apriori(records,min_support=0.0053,min_confidence=0.20, min_lift=3, min_length=2)

# Convert the rules found by the apriori class into a list to make it easier to view.
association_results = list(association_rules)

# Find the total number of rules mined by the apriori class.
print(len(association_results))

# Print the first item in the association_rules list to see the first rule.
print(association_results[0])