연관 규칙과 순차 패턴 마이닝: Apriori, FP-Growth, SPADE 활용법

거래 로그에서 관계의 형태를 먼저 구분한다

대규모 거래·행동 로그에서 반복되는 규칙을 찾을 때는 동시발생을 볼 것인지, 시간 순서를 따라갈 것인지부터 구분해야 한다. Association Rules와 Sequential Pattern Mining은 이 차이를 기반으로 빈발 패턴을 발굴하는 기법이다.

연관 규칙은 항목 집합 X→Y의 규칙을 찾아 함께 발생하는 경향을 드러낸다. 주요 판단 지표는 지지도(support), 신뢰도(confidence), 향상도(lift)이며, lift>1이면 양의 연관 관계를 추정한다. 입력은 거래별 항목 목록을 둔 수평 형식이나 비트·ID-리스트를 사용하는 수직 형식으로 준비할 수 있다.

순차 패턴은 시간 순서가 있는 시퀀스 DB에서 〈a〉→〈b,c〉→〈d〉처럼 자주 나타나는 흐름을 찾는다. 최소 지지도를 기본으로 최대·최소 간격(gap), 윈도우, 아이템·시퀀스 길이 제한을 선택적으로 적용하며, 빈발 시퀀스와 시간 제약을 포함한 〈X〉→〈Y〉 규칙을 결과로 낼 수 있다.

임계값은 minsup, minconf, minlift를 함께 조정한다. 순차 데이터에는 mingap/maxgap, maxspan, maxlen 같은 제약이 추가된다. 표본에서 임계값을 스윕해 패턴 수가 급증하는 지점을 찾은 뒤 보수적으로 설정하는 방식이 적합하다.

수평 표현은 트랜잭션별 항목 목록이라 이해와 전처리가 쉽지만 여러 번의 스캔 비용이 생긴다. 수직 ID-list는 항목별 등장 거래 또는 시퀀스 위치를 보관해 교집합 연산 중심의 탐색을 빠르게 한다.

전처리와 규칙 정제가 결과의 품질을 좌우한다

사용자·거래·시간키를 정합하고, 시간 순서를 정렬해 세션으로 묶는 작업이 먼저다. 아이템은 카테고리 기준으로 인코딩하고 희귀 항목은 최소 빈도 기준으로 거른다. 중복과 노이즈를 제거하며, 지나치게 자주 등장하는 항목에는 빈도 상한을 적용할 수 있다.

탐색 과정에서는 비빈발 부분집합을 포함하는 집합을 더 탐색하지 않는 하향 폐포(anti-monotonicity)를 쓴다. 공통 접두나 접미를 기준으로 등가류(class)를 나누면 탐색 공간을 줄일 수 있다. 이후 lift, conviction, leverage 같은 지표로 후순위 규칙을 걸러낸다.

규칙이 많아진 뒤에는 폐쇄(closed)·최대(maximal) 패턴과 규칙 하위합 제거(MNR, redundancy)를 적용해 중복과 서열 관계를 정리한다. 교차검증·부트스트랩으로 재현성을 확인하고, 샘플 증거 트랜잭션과 카테고리 매핑을 붙여 해석성을 확보한다.

운영 환경에서는 주·일 단위 리프레시와 계절성 분리가 필요하다. 패턴 수와 평균 lift를 모니터링해 데이터 드리프트를 감지하고 임계값을 재튜닝한다. 개인 정보가 포함된 데이터는 익명화·k-익명성, 민감 항목 마스킹을 적용한다.

후보 집합, 압축 트리, ID-리스트로 갈리는 탐색 방식

Apriori는 후보 집합을 단계적으로 확장한다

Apriori는 먼저 전체 데이터를 스캔해 1-항목 빈발 집합을 구한다. 이후 k-빈발 집합을 조인해 (k+1) 후보를 만들고, 비빈발 하위집합이 있으면 제거한 뒤 재스캔으로 빈도를 집계한다.

하향 폐포를 명확하게 활용한다는 장점이 있지만, 스캔 횟수가 늘고 후보가 폭증할 수 있다. 중소 규모의 희소 데이터이거나 해석을 우선할 때 적합하다.

FP-Growth는 압축된 트리에서 빈발 집합을 찾는다

FP-Growth는 1-항목 빈도를 계산해 빈도순으로 정렬한 다음 FP-트리를 만든다. 조건부 패턴베이스와 조건부 트리를 이용해 분할 정복 방식으로 빈발 집합을 직접 발굴한다.

후보를 생성하지 않고 스캔은 2회로 제한된다. 메모리 안에서 트리를 압축해 처리하므로 대규모·고차원 트랜잭션과 메모리 여유가 있는 환경에 맞는다.

SPADE는 순서가 있는 이벤트를 수직 구조로 다룬다

SPADE(Sequential PAttern Discovery using Equivalence classes)는 아이템을 (SID, EID) 형태의 ID-리스트로 변환한다. 동시 확장과 후속 확장에 따라 등가류를 나눈 뒤 ID-리스트 교집합으로 지지도를 계산하며 빈발 시퀀스를 확장한다.

수직 교집합 연산이 빠르고 디스크 분할·메모리 관리를 통해 확장성을 확보한다. 클릭스트림이나 세션 로그처럼 순서가 중요한 데이터에 적합하다.

데이터 유형에 따라 탐색 경로를 선택한다

⤢✕

알고리즘	성능(속도)	확장성	일관성(재현)	안정성(메모리)	운영 편의
Apriori	중	중	높음	높음	높음
FP-Growth	높음	높음	높음	중	중
SPADE	높음	높음	높음	중	중

데이터 분포, 희소도, 임계값 설정에 따라 결과는 달라진다. 후보 폭증이 문제가 되면 대체로 FP-Growth나 SPADE가 우위에 있다.

Apriori, FP-Growth, SPADE 실행 예시

환경은 Python 3.10+, pandas 2.x, mlxtend 0.23+, Java 8+이며, SPADE에는 SPMF를 사용한다. 아래 예시는 소규모 데이터의 로컬 실행을 전제로 한다.

Association Rules: Apriori / FP-Growth (mlxtend)

# pip install pandas mlxtend
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, fpgrowth, association_rules

transactions = [
    ['milk', 'bread', 'eggs'],
    ['bread', 'butter'],
    ['milk', 'bread', 'butter', 'jam'],
    ['beer', 'chips'],
    ['milk', 'bread', 'butter'],
]

te = TransactionEncoder()
oht = te.fit(transactions).transform(transactions)
df = pd.DataFrame(oht, columns=te.columns_)

# Apriori
freq_ap = apriori(df, min_support=0.4, use_colnames=True)
rules_ap = association_rules(freq_ap, metric='confidence', min_threshold=0.6)
rules_ap = rules_ap[rules_ap['lift'] > 1.0].sort_values('lift', ascending=False)
print("Apriori rules:\n", rules_ap[['antecedents','consequents','support','confidence','lift']])

# FP-Growth
freq_fp = fpgrowth(df, min_support=0.4, use_colnames=True)
rules_fp = association_rules(freq_fp, metric='confidence', min_threshold=0.6)
rules_fp = rules_fp[rules_fp['lift'] > 1.0].sort_values('lift', ascending=False)
print("FP-Growth rules:\n", rules_fp[['antecedents','consequents','support','confidence','lift']])

초고차원 데이터에서는 one-hot 표현의 메모리 비용이 커질 수 있으므로 희귀 항목을 사전에 필터링한다.

Sequential Patterns: SPADE (SPMF via Java)

# 1) SPMF 다운로드
# Linux/Mac
curl -L -o spmf.jar http://www.philippe-fournier-viger.com/spmf/spmf.jar
# Windows는 브라우저 다운로드 권장

# 2) 예시 시퀀스 파일 생성 (SPMF 형식)
cat > seq.txt << 'EOF'
# 각 줄: 시퀀스. -1: 아이템셋 종료, -2: 시퀀스 종료
1 -1 2 3 -1 4 -1 -2
1 2 -1 3 -1 -2
1 -1 3 4 -1 -2
2 -1 3 -1 4 -1 -2
EOF

# 3) SPADE 실행 (minsup=50%)
java -Xmx1G -jar spmf.jar run SPADE seq.txt out.txt 50%
# 결과 확인
head -n 20 out.txt

입력은 공백으로 구분하며, 아이템셋 종료에는 -1, 시퀀스 종료에는 -2를 사용하고 숫자 아이템 ID를 쓴다. 패턴 수가 급증하면 minsup을 높이거나 maxlen을 제한한다. gap 제약이 필요하면 SPMF의 Gap-constrained 알고리즘을 사용한다.

임계값과 메모리 제약을 운영 규칙에 반영한다

초기 탐색에서는 높은 minsup으로 구조를 파악한 뒤 점진적으로 완화한다. 규칙 수가 10^4 이상이면 폐쇄·최대 패턴을 우선한다. lift만 단독으로 쓰기보다 conviction, leverage를 함께 보고, 희귀하지만 강한 규칙은 표본 왜곡 가능성을 점검한다.

메모리가 제한된 환경에서는 FP-트리 압축이 실패할 수 있다. SPADE는 ID-리스트가 빽빽하면 I/O 부담이 커질 수 있으므로 샘플링, 분할, 병렬화로 완화한다. 룰 엔진 배포 시에는 유효기간과 적용 대상을 관리하고, 비식별화로 프라이버시를 준수한다.

동시발생 관계를 분석할 때는 Apriori와 FP-Growth를, 시간 순서가 핵심인 데이터에는 SPADE를 선택한다. 전처리의 일관성, 임계값 튜닝, 후처리 정제, 운영 모니터링이 반복 패턴을 실제 의사결정 규칙으로 바꾸는 조건이다.