연관 규칙 학습법
연관 규칙 학습법(Association Rule Learning)은 대규모 데이터 집합에서 항목들 간의 흥미로운 관계(연관 규칙)를 자동으로 찾아내는 데이터 마이닝 및 통계적 학습 기술이다. 주로 장바구니 분석(Market‑Basket Analysis) 등에서 “어떤 상품을 함께 구매하는 경향이 있는가?”를 탐색하는 데 활용되며, 전자 상거래, 의료 진단, 추천 시스템, 사기 탐지 등 다양한 분야에 적용된다.
정의
연관 규칙 학습법은 데이터베이스 내 트랜잭션(또는 사건) 집합을 입력으로 받아, ‘전건(antecedent) → 후건(consequent)’ 형태의 규칙을 생성한다. 각 규칙은 다음과 같은 품질 지표를 통해 평가된다.
| 지표 | 설명 |
|---|---|
| 지지도(support) | 전체 트랜잭션 중 해당 규칙(전건 ∪ 후건)을 포함하는 비율. |
| 신뢰도(confidence) | 전건이 발생했을 때 후건이 동시에 발생할 확률, 즉 *P(후건 |
| 향상도(lift) | 전건과 후건이 독립적인 경우 대비 실제 동시 발생 빈도의 비율, confidence / P(후건). |
이러한 지표를 기준으로 사용자는 최소 지지도와 최소 신뢰도를 설정하여 의미 있는 규칙만을 추출한다.
배경 및 역사
연관 규칙 학습법은 1990년대 초 IBM 연구원인 Agrawal, Imieliński, Swami가 발표한 논문 “Mining Association Rules between Sets of Items in Large Databases”에서 처음 제시되었다[^1]. 이후 Apriori 알고리즘이 대표적인 구현으로 자리 잡았으며, 1997년 Han, Pei, Yin에 의해 FP‑Growth 알고리즘이 제안되어 메모리 효율성과 속도 면에서 획기적인 개선을 이루었다.
주요 알고리즘
1. Apriori
- 핵심 아이디어: ‘빈번한(itemset)’은 그 모든 부분집합도 빈번해야 한다는 ‘Apriori property’를 이용해 후보 집합을 단계적으로 축소한다.
- 절차: ① 최소 지지도 기준으로 1‑itemset을 찾는다 → ② 빈번한 k‑itemset을 이용해 (k+1)‑itemset 후보를 생성 → ③ 후보 집합에 대해 지지도 검증을 반복한다.
2. Eclat (Equivalence Class Transformation)
- 핵심 아이디어: 아이템-트랜잭션 매핑을 수직 데이터 형식으로 변환하고, 교집합 연산을 이용해 빈번한 아이템 집합을 탐색한다.
- 특징: 메모리 사용량이 적고, 깊이 우선 탐색을 통해 빠르게 탐색 가능하지만, 트랜잭션 수가 매우 큰 경우 성능이 저하될 수 있다.
3. FP‑Growth (Frequent Pattern Growth)
- 핵심 아이디어: 전체 데이터베이스를 FP‑Tree라는 압축된 구조로 변환한 뒤, 조건부 FP‑Tree를 재귀적으로 탐색해 빈번한 패턴을 추출한다.
- 장점: 후보 생성 단계가 없으며, 대규모 데이터에서도 높은 효율성을 보인다.
4. 기타 변형
- 연속적 연관 규칙(Sequential Pattern Mining): 시간 순서가 있는 이벤트 시퀀스에서 규칙을 찾아낸다(예: SPADE, PrefixSpan).
- 고차원 연관 규칙(High‑dimensional Association Rules): 희소하고 고차원 데이터에 특화된 알고리즘(예: H-Mine).
핵심 개념
| 용어 | 설명 |
|---|---|
| 빈번한 아이템 집합(frequent itemset) | 지정된 최소 지지도 수준을 만족하는 아이템들의 집합. |
| 폐쇄 빈번 아이템 집합(closed frequent itemset) | 상위 집합이 동일 지지도를 갖지 않는 빈번 아이템 집합으로, 정보 손실 없이 압축 가능. |
| 극대 빈번 아이템 집합(maximal frequent itemset) | 더 이상 확장될 수 없는 가장 큰 빈번 아이템 집합. |
| 제약 기반 연관 규칙(constraint-based association rules) | 특정 속성(예: 특정 아이템 포함, 규칙 길이 제한 등)을 강제하여 탐색 범위를 축소한다. |
응용 분야
- 마케팅 및 소매: 장바구니 분석을 통한 교차 판매 전략 수립.
- 추천 시스템: 사용자의 과거 행동과 연관된 아이템을 실시간으로 제안.
- 의료 데이터: 질병·증상·처방 간 연관성 파악(예: 약물 부작용 탐지).
- 네트워크 보안: 비정상적인 트래픽 패턴을 규칙으로 모델링하여 침입 탐지.
- 텍스트 마이닝: 단어·구절 간 연관성을 분석해 주제 추출에 활용.
제한점 및 개선 연구
- 스팸 규칙: 낮은 신뢰도·높은 지지도를 가진 규칙이 과다 생성될 수 있다. → 레시프리즘(Resampling)·이벤트 샘플링 등으로 해결 시도.
- 대규모 데이터: 메모리와 연산량이 급증 → *분산 처리 프레임워크(예: Apache Spark’s MLlib)*를 이용한 구현이 활발히 연구된다.
- 다차원 종속성: 단순한 2‑항목 규칙으로는 복잡한 상호작용을 포착하기 어려움 → 다중 레벨 연관 규칙, 베이지안 네트워크 기반 확장 등 복합 모델이 제안된다.
관련 소프트웨어 및 라이브러리
| 도구 | 주요 특징 |
|---|---|
| Weka | Apriori, Eclat 등 여러 연관 규칙 알고리즘을 GUI 기반으로 제공. |
| R (arules 패키지) | Apriori, Eclat, FP‑Growth 구현 및 시각화 기능 포함. |
| Python (mlxtend.frequent_patterns) | Pandas와 연동하여 Apriori 및 연관 규칙 추출을 손쉽게 수행. |
| Apache Spark MLlib | 대규모 분산 환경에서 FP‑Growth 기반 연관 규칙 학습 지원. |
| RapidMiner | 데이터 흐름 기반 GUI에서 연관 규칙 작업을 직관적으로 구성 가능. |
참고문헌
- Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.
- Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1‑12.
- Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372‑390.
- Tan, P.-N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Pearson.
이 문서는 연관 규칙 학습법에 대한 기본적인 개념과 주요 알고리즘, 응용 분야를 위키백과 스타일로 정리한 것으로, 최신 연구 동향이나 세부 구현에 대해서는 각 분야별 최신 논문 및 기술 문서를 참고하시기 바랍니다.