Frequent Pattern Mining
Apriori 알고리즘
- 빈번하게 일어나는 항목 집합을 추출하는 알고리즘
- Minimum support 이상을 가지는 값을 찾은 후 association rule 생성
- 동작 원리:
- DB 스캔
- 길이 k의 itemset을 생성하고 각 itemset의 support 값을 계산
- minimum support 이상의 support를 가지는 itemset 추출
- k를 늘리면서 위의 과정 반복
- 장점:
- 간단한 원리
- 유의미한 연관성을 가지는 패턴을 찾기 쉬움
- 단점:
- 데이터가 커질때, 속도가 느려짐 (매 사이클마다 DB를 스캔하기 때문)
- 실제로 사용 시 너무 많은 연관 패턴을 찾음
- Association rule에서 사용되는 통계 척도
- support(지지도): 특정 아이템이 데이터에서 발생하는 빈도
- confidence(신뢰도): 두 아이템의 association rule이 유용할 가능성
- lift(향상도): 두 아이템의 association rule이 우연인지 나타내는 척도
FP-growth 알고리즘
- Apriori의 연산 속도를 개선하기 위해 등장
- Tree 자료구조를 이용
- 동작 원리:
- DB를 스캔하여 각 item의 support값을 계산
- 빈도가 높은 item을 순서대로 정렬
- 부모 노드를 중심으로 자식노드를 추가하며 tree 생성
- 장점:
- Apriori보다 빠름 (DB 스캔 수를 줄임)
- 1번째 스캔에서 단일항목집단 생성, 2번째 스캔에서 tree 생성
- 단점:
- 대용량 데이터셋에서 메모리를 효율적으로 사용하지 않음
- 설계가 어려움
- support 계산은 FP-tree 생성 후 가능
The Bread Basket 문제 풀어보기 (Kaggle)
- https://www.kaggle.com/datasets/mittalvasu95/the-bread-basket
- 데이터 구성: Transaction ID, Item, Date, Time
- BreadBasket_DMS.csv 파일을 받아서 실습해보자
(1단계) csv 파일 불러오기
import pandas as pd
import numpy as np
import os
from google.colab import drive
drive.mount('/content/drive')
basicPath = '/content/drive/My Drive/Colab Notebooks/'
path = basicPath + '[csv 파일 위치]' # 파일 위치
file = 'BreadBasket_DMS.csv' # 파일명
data = pd.read_csv(os.path.join(path,file), index_col=None)
data.head() # 파일 불러오는지 확인실행결과
(2단계) Data 전처리
- 영문인 경우 편의를 위해 소문자로 변경
- Data의 결측값 확인 및 제거
- Data 간단 분석 (item 당 등장횟수 확인)
- Data 형태 변환 (vertical format)
- encoding
Data cleaning
data['Item'] = data['Item'].str.lower(
data.head() 실행결과
Data의 결측값 확인 및 제거
data.isnull().sum() # 각 column별로 결측값의 수를 출력
(예제 1) 결측값을 포함한 row 추가하고 확인하기
data = data.append({'Date':None, 'Time':None, 'Transaction':9685, 'Item':None}, ignore_index=True)
data.isnull().sum() # 각 column별로 결측값의 수를 출력
(예제 2) 결측값을 포함한 row 삭제하고 확인하기
data.dropna(inplace=True)
data.isnull().sum() # 각 column별로 결측값의 수를 출력실행결과
DataFrame의 인덱스로 row의 정보 확인
data.iloc[10:20]
data.iloc[19]실행결과
DataFrame의 특정 col을 구성하는 집합 요소 확인
data['Item'].unique() # Item을 이루는 집합의 모든 요소 출력
data['Item'].nunique() # Item을 이루는 집합의 요소 수 출력
(data['Item']=='none').value_counts() # 조건에 해당하는 요소 내림차순 출력실행결과
Data 간단 분석 (item 당 등장 횟수 확인)
top10_items = data['Item'].value_counts().head(10)
top10_items
Data 형태 변환 (vertical format)
# 모든 Transaction에 대해 각각이 가지는 Item을 셀 수 있도록 vertical format으로 변환
hot_encoded_data = data.groupby(['Transaction','Item'])['Item'].count().unstack().fillna()실행결과
Encoding
# 하나의 transaction에 2개 이상의 동일한 item이 들어가는 경우 1개로 취급
# 왜? item간의 관계가 중요하기 떄문!!
def encode_units(x):
if x <= 0:
return 0
if x >= 1:
return 1
hot_encoded_data = hot_encoded_data.applymap(encode_units)
hot_encoded_data실행결과
(3단계) 모델 이용하기
Apriori 라이브러리 이용하기
from mlxtend.frequent_patterns import apriori
frequent_itemsets = apriori(hot_encoded_data, min_support=0.01, use_colnames=True)
list(hot_encoded_data.columns).index('baguette')
np.where(hot_encoded_data, columns=='baguette')실행결과
Association rule 구하기
from mlxtend.frequent_patterns import association_rules
rules = association_rules(frequent__itemsets, metric='lift', min_threshold=1.4)
rules[rules['confidence'] > 0.17]실행결과
FP tree 라이브러리 이용하기
from mlxtend.frequent_patterns import fpgrowth
frequent_itemsets_fp = fpgrowth(hot_encoded_data, min_support=0.01, use_colnames=True)
rules_fp = association_rules(frequent_itemsets_fp, metric='lift', min_threshold=1.4)
rules_fp[rules_fp['confidence'] > 0.17]실행결과
(4단계) 성능 비교
from mlxtend.frequent_patterns import apriori
%timeit -n 100 frequent_itemsets = apriori(hot_encoded_data, min_support=0.005, use_colnames=True)
%timeit -n 100 frequent_itemsets_fp = fpgrowth(hot_encoded_data, min_support=0.005, use_colnames=True)
display(rules[rules['confidence'] > 0.17], rules_fp[rules_fp['confidence'] > 0.17])실행결과
