연관 규칙 (2): Apriori 알고리즘

Apriori 알고리즘

연관규칙의 1세대 알고리즘..?!

 

1️⃣ 효율적인 연관규칙 탐색 알고리즘이 필요한 이유

 

아이템 개수가 많을수록 기하급수적으로 증가함

 

2️⃣ 연관규칙 생성 전략 및 알고리즘 종류

1. 모든 가능한 항목집합의 개수(M)를 줄이는 전략 ➡️ Apriori
2. Transaction(N) 개수를 줄이는 전략 ➡️ DHP
3. 비교하는 수(W)를 줄이는 전략 ➡️ FP-growth

 

3️⃣ Apriori 원리

1. 빈발항목집합
   - 최소 지지도 이상의 빈발항목집합을 추출
   - 지지도를 계산하는 대신, 최소 지지도 이상인 빈발항목집합만 추출하여 연관규칙을 계산
2. Apriori Principle
   - 첫 번째 원칙: 하나의 항목집합이 빈발하다면, 그 항목집합의 모든 부분집합도 빈발해야 한다.
   - 두 번째 원칙: 하나의 항목집합이 비빈발하다면, 이 항목집합을 포함하는 모든 집합도 비빈발이다.
3. Apriori Pruning Principle:
   - 빈발하지 않은 항목집합이 존재하면 그 집합을 포함하는 상위 항목집합도 생성하거나 테스트하지 않습니다.
   즉, 비빈발 항목집합을 제거하는 가지치기 기법이다.
4. 빈발항목집합 후보 생성:
   - (k-1) 항목 빈발항목집합에서 (k-2) 항목이 같은 항목들만 혼합하여 k-항목 빈발항목집합 후보를 생성
   - 예를 들어, 2-항목 빈발항목집합에서 {B}를 포함하는 {B, C}와 {B, E}를 혼합하여 3-항목 빈발항목집합 후보 {B, C, E}를 만듭니다.
5. 연관규칙 생성:
   - 빈발항목집합에서 가능한 모든 부분집합 X, Y를 나누어 연관규칙 X -> Y를 생성합니다.
   - 생성된 연관 규칙은 최소 신뢰도 조건을 만족하지 않으면 제거됩니다.
6. 반복 과정:
   - 빈발항목집합 추출, 후보 생성, 연관 규칙 생성 및 가지치기를 반복하여 더 이상 연관규칙이 없을 때까지 진행

 

4️⃣ Apriori 실습

 

연관 규칙 분석 절차

1. 모든 거래에서 발생하는 모든 항목에 대한 빈도 테이블을 생성
2. support가 임의의 값보다 큰 것들로 필터링
3. 중요 항목의 모든 가능한 조합을 만들기
4. 모든 조합의 발생 횟수 계산
5. Association Rules 적용
6. 해석

 

Data Set

Market_Basket_Optimisation.csv

df = pd.read_csv('Market_Basket_Optimisation.csv', header = None)
df.head()

(7501, 20) 인 데이터 셋

 

 

트랜잭션 데이터로 변환

# 동일한 크기의 리스트에 각 손님들의 쇼핑 목록을 넣기
trans = []
for i in range(0, 7501):
    trans.append([str(df.values[i,j]) for j in range(0, 20)])

# numpy array 로 변환
trans = np.array(trans)
print(trans.shape)
# (7501, 20) -> 총 스물가지의 장바구니

from mlxtend.preprocessing import TransactionEncoder

te = TransactionEncoder()
data = te.fit_transform(trans)
data = pd.DataFrame(data, columns = te.columns_)

data.shape
# (7501, 121) -> 트랜잭션 데이터 (모든 항목이 들어간)

 

 

중요 항목의 모든 가능한 조합을 만들기

frequent_itemsets = apriori(data, min_support = 0.01, use_colnames=True)
frequent_itemsets.sort_values("support", ascending=False)

 

Association Rules 적용 - 연관 규칙 학습 함수

from mlxtend.frequent_patterns import association_rules

 

• df: DataFrame
  • 빈발 항목 집합을 포함하는 데이터프레임입니다. 이 데이터프레임은 apriori 함수에서 생성한 빈발 항목 집합 결과를 포함하고 있어야 합니다.
• metric: str (기본값은 'lift')
  • 연관 규칙을 평가할 메트릭을 지정합니다. 가능한 메트릭은 다음과 같습니다:
    • 'lift': 리프트 (lift) 지표를 기준으로 규칙을 생성
    • 'confidence': 신뢰도 (confidence) 지표를 기준으로 규칙을 생성
    • 'support': 지원도 (support) 지표를 기준으로 규칙을 생성
    • 'leverage': 레버리지 (leverage) 지표를 기준으로 규칙을 생성
    • 'conviction': 확신도 (conviction) 지표를 기준으로 규칙을 생성
• min_threshold: float (기본값은 1.0)
  • metric으로 지정한 지표에서 규칙을 선택할 때 사용되는 최소 임계값입니다. 예를 들어, lift 기준으로 규칙을 생성하려면 min_threshold=1.0으로 설정할 수 있습니다. lift가 1보다 크면 두 항목은 서로 연관성이 있다고 볼 수 있습니다.
• support_only: bool (기본값은 False)
  • True로 설정하면, support만을 기준으로 규칙을 반환합니다. 신뢰도(confidence), 리프트(lift) 등 다른 지표는 고려하지 않습니다.
• return_metrics: bool (기본값은 True)
  • True일 경우, 규칙을 반환할 때 각 규칙의 지표(예: lift, confidence 등)를 포함합니다.

해석

예시

 

antecedents	consequents	antecedent support	consequent support	support	confidence	lift	representativity	leverage	conviction	zhangs_metric	jaccard	certainty	kulczynski
(ground beef, eggs)	(mineral water)	0.019997	0.238368	0.010132	0.506667	2.125563	1.0	0.005365	1.543848	0.540342	0.040816	0.352268	0.274586

 

groupd beef와 egg가 함께 나타날 때 mineral water가 나타날 확률은 약 50.7%이고, 이 규칙의 향상도는 2.13배입니다. 즉, ground beef와 eggs가 함께 있을 때 mineral water가 나타날 확률은 무작위로 나타날 확률보다 2배 더 높다는 의미이다.

 

참고

[R 연관규칙(Association Rule) ] Apriori algorithm

https://rfriend.tistory.com/193

[R 연관규칙 (Association Rule)] R arules package로 연관규칙 분석하기