387. 연관 규칙 탐색 (Apriori 알고리즘과 FP-Growth)

핵심 인사이트 (3줄 요약)

본질: 연관 규칙 탐색(Association Rule Mining)은 "기저귀를 사는 아빠들은 보통 맥주도 같이 산다"는 마트 영수증의 숨겨진 패턴(장바구니 분석)을 지지도(Support), 신뢰도(Confidence), 향상도(Lift)라는 3가지 통계 점수로 뽑아내는 비지도 학습 기법이다.

가치: 수천만 건의 영수증에서 모든 상품 조합을 다 계산하면 우주의 나이보다 시간이 오래 걸리지만, Apriori 알고리즘은 "단독으로 잘 안 팔리는 물건은 세트로 묶어도 안 팔린다"는 원리를 이용해 계산량을 획기적으로 쳐내는 가지치기(Pruning) 기법을 도입했다.

판단 포인트: Apriori조차 영수증(DB)을 수십 번씩 스캔해야 하는 치명적인 속도 문제가 있어서, 실무 파이프라인에서는 영수증을 딱 2번만 읽고 메모리에 거대한 나무(FP-Tree)를 그려서 빛의 속도로 규칙을 뽑아내는 FP-Growth 알고리즘을 표준 아키텍처로 사용한다.

Ⅰ. 개요 및 필요성

대형 마트에서 고객들의 영수증 수백만 장을 분석하려 한다. 목표는 "같이 잘 팔리는 물건들을 찾아 매장에 나란히 진열하는 것"이다. 단순히 "우유와 빵이 같이 1만 번 팔렸네!"라고 좋아하면 안 된다. 우유와 빵은 원래 매일 10만 번씩 팔리는 물건이라, 1만 번 겹친 건 우연일 수도 있다. 반면 '마라탕'과 '우유'는 같이 팔린 횟수가 500번밖에 안 되지만, 마라탕을 산 사람이 500명뿐이라면 마라탕을 산 사람은 100% 우유를 산다는 엄청난 인사이트가 된다.

이처럼 단순한 '같이 팔린 횟수'의 함정을 벗어나, 우연의 일치를 통계적으로 솎아내고 **진짜로 의미 있는 연결 고리(If A, then B)**를 찾아내는 수학적 채점표가 바로 연관 규칙 탐색이다. 이 채점표를 기반으로 아마존의 추천 상품과 넷플릭스의 영화 추천 시스템의 초기 뼈대가 만들어졌다.

📢 섹션 요약 비유: 우연히 길에서 10번 마주친 옆 동네 사람(단순 빈도)과, 3번밖에 안 만났지만 만날 때마다 같이 밥을 먹는 찐친(연관 규칙)을 정확하게 구별해 내는 인맥 판독기다.

Ⅱ. 아키텍처 및 핵심 원리

연관 규칙은 다음 3가지 핵심 지표로 채점되며, Apriori 알고리즘이 이를 효율적으로 찾아낸다.

┌────────────────────────────────────────────────────────┐
│             [ 연관 규칙의 3대 평가 지표 (A -> B) ]            │
├────────────────────────────────────────────────────────┤
│ 1. 지지도 (Support) : "이 세트가 전체 영수증에서 얼마나 흔한가?" │
│    - 수식: P(A ∩ B) = (A와 B가 같이 든 영수증 수) / 전체 영수증│
│    - 역할: 너무 안 팔리는 희귀한 조합은 버리는(Pruning) 기준점   │
│                                                        │
│ 2. 신뢰도 (Confidence) : "A를 샀을 때 B도 살 확률은?"       │
│    - 수식: P(B|A) = P(A ∩ B) / P(A)                   │
│    - 역할: A가 B를 끌어당기는 힘. (조건부 확률)              │
│                                                        │
│ 3. 향상도 (Lift) : "B를 그냥 살 때보다, A를 샀을 때 B를 살 확률이 얼마나 뛰는가?"│
│    - 수식: P(B|A) / P(B)                               │
│    - 결과가 1: A와 B는 아무 상관 없음 (우연히 같이 산 거임)     │
│    - 결과가 1보다 큼: A를 사면 B를 살 확률이 X배 뜀! (진짜 찐친)│
└────────────────────────────────────────────────────────┘

Apriori의 가지치기 (Apriori Principle): 100개 상품의 조합은 $2^{100}$개다. Apriori 알고리즘은 "우유 단독으로 안 팔리면, 우유+콜라 세트도 볼 필요 없이 안 팔린다"라는 하향식(Downward Closure) 성질을 이용해, 지지도가 낮은 놈이 포함된 모든 세트 경우의 수를 통째로 계산에서 날려버린다.
향상도(Lift)의 중요성: 삼각김밥(A)을 사면 생수(B)를 산다는 신뢰도가 90%가 나왔다. 엄청 높아 보이지만, 원래 마트 고객의 90%가 생수를 산다면? 삼각김밥은 생수 판매에 아무런 기여(향상도 1.0)를 하지 못한 것이다. 따라서 실무에서 가장 중요한 핵심 지표는 언제나 **향상도(Lift)**다.

📢 섹션 요약 비유: 지지도(Support)는 오디션의 예선전(너무 인기 없는 팀 탈락)이고, 신뢰도(Confidence)는 본선 점수이며, 향상도(Lift)는 이 팀이 낙하산(원래 인기 많음)인지 진짜 실력파인지 걸러내는 심사위원의 날카로운 송곳 질문이다.

Ⅲ. 비교 및 연결

연관 규칙을 찾는 알고리즘 1세대와 2세대를 비교하면, 데이터 파이프라인의 진화를 볼 수 있다.

비교 항목	Apriori (아프리오리)	FP-Growth (Frequent Pattern Growth)
동작 원리	1개짜리 세트 $\rightarrow$ 2개짜리 세트로 늘려가며 계속 DB 스캔	전체 DB를 한 번 읽어 거대한 트리(Tree)를 메모리에 그림
DB 스캔 횟수	조합 개수가 늘어날 때마다 수십 번 DB 전체를 스캔	정확히 딱 2번만 DB 스캔
메모리 사용량	적게 듦 (후보군만 만들고 지움)	FP-Tree를 램(RAM)에 띄워야 해서 메모리 많이 먹음
연산 속도	빅데이터에서 숨넘어가게 느림	Apriori보다 수십 배~수백 배 압도적으로 빠름

아마존 같은 거대 이커머스에서 영수증(DB)이 수천만 장 쌓이면 Apriori는 영원히 끝나지 않는 무한 루프에 빠진다. 그래서 메모리(RAM)를 빵빵하게 늘려놓고, 영수증 데이터를 압축된 나무(FP-Tree) 형태로 메모리에 한 번에 다 올려서 탐색하는 FP-Growth가 현대 추천 시스템의 절대적인 뼈대가 되었다.

📢 섹션 요약 비유: Apriori는 손님이 올 때마다 창고(DB)에 가서 물건이 있는지 하나하나 찾아보는 바보 알바생이고, FP-Growth는 아침에 창고를 싹 다 뒤져서 노트에 물건 위치 지도(Tree)를 한 번만 그려놓고 그다음부턴 노트만 보고 빛의 속도로 대답하는 에이스 점장이다.

Ⅳ. 실무 적용 및 기술사 판단

실무 적용 시나리오: 넷플릭스 초창기 영화 추천 파이프라인이다. '유저의 시청 기록'을 하나의 '영수증'으로 본다. 파이썬 mlxtend의 fpgrowth 알고리즘을 돌린다. 조건은 min_support=0.01 (전체 유저의 1%는 본 영화만 취급). 결과로 "[아이언맨, 토르] $\rightarrow$ [어벤져스]"라는 규칙이 튀어나오고, 이 규칙의 Lift(향상도)가 15.0으로 측정된다. 즉, 앞의 두 영화를 본 유저는 평범한 유저보다 어벤져스를 볼 확률이 15배 뛴다는 팩트를 기반으로 홈 화면에 해당 영화를 강제 추천한다.

기술사 판단 포인트 (Trade-off): 연관 규칙 아키텍처를 설계할 때 기술사는 **'최소 지지도(Minimum Support)의 문턱'**을 결정하는 비즈니스 타협을 해야 한다.

min_support를 0.1(10%)로 너무 높게 잡으면, 우유나 계란처럼 흔해 빠진 쓰레기 규칙만 남고 기발한 아이디어(롱테일 법칙)는 다 잘려 나간다.
min_support를 0.001(0.1%)로 너무 낮게 잡으면, FP-Tree가 램(RAM) 메모리 용량을 뚫고 터져버리거나(OOM), "A볼펜을 샀더니 B지우개를 사더라"는 식의 너무 사소한 우연의 일치까지 규칙으로 나와버린다.
따라서 기술사는 도메인의 희소성(이커머스 vs 의료 등)을 파악하여 적당한 Support 가지치기 기준을 잡고, Lift 기준으로 상위 100개의 룰만 현업 마케터에게 대시보드로 뽑아주는 필터링 구조를 짜야 한다.

📢 섹션 요약 비유: 강물에서 사금을 채취할 때, 그물코(최소 지지도)를 너무 크게 하면 큼지막한 돌멩이(뻔한 규칙)만 남고 진짜 사금(희귀한 꿀팁)은 다 빠져나간다. 반대로 너무 촘촘하면 뻘물(노이즈 데이터)이 다 올라와 무거워서 그물이 찢어져 버린다.

Ⅴ. 기대효과 및 결론

연관 규칙 탐색은 "데이터가 너무 많아서 뭘 봐야 할지 모르겠다"는 기업들에게 묻지도 따지지도 않고 직관적인 마케팅 전략(교차 판매, 패키지 구성)을 던져주는 최초의 데이터 마이닝 캐시카우(Cash Cow)였다.

결론적으로 FP-Growth 같은 트리 압축 기술의 발전 덕분에 빅데이터 시대에도 연관 규칙은 죽지 않았다. 비록 최신 딥러닝 추천 알고리즘(행렬 분해, 오토인코더)들이 '사용자의 숨겨진 취향(Latent Factor)'까지 섬세하게 파악하며 왕좌를 가져갔지만, "A를 사면 B를 산다"는 이 단순무식하고 직관적인 설명력(XAI)은 현업 마케터들을 설득하고 기획안을 통과시킬 때 여전히 가장 강력하고 사랑받는 통계적 무기다.

📢 섹션 요약 비유: 최신 딥러닝이 "제 감상 이 고객은 100% 이 옷을 좋아할 겁니다!"라고 말하는 영험한 무당이라면, 연관 규칙 탐색은 "과거 영수증 100만 장을 까보니, 이 바지를 산 사람은 무조건 이 벨트를 샀습니다. 숫자가 증명합니다"라고 말하는 가장 믿음직한 회계사다.

📌 관련 개념 맵

상위 개념: 데이터 마이닝 (Data Mining), 비지도 학습 (Unsupervised Learning)
하위 개념: 지지도 (Support), 신뢰도 (Confidence), 향상도 (Lift)
연결 개념: Apriori 알고리즘, FP-Growth, 추천 시스템 (Recommendation System)

👶 어린이를 위한 3줄 비유 설명

슈퍼마켓 영수증 1만 장을 봤더니, 라면을 산 아저씨들이 항상 김밥을 같이 샀어요!
하지만 라면은 원래 많이 팔리는 거니까, 이게 진짜 찰떡궁합인지 확인하려고 '향상도(Lift)'라는 채점표를 꺼냈어요.
채점해보니 "그냥 김밥을 살 때보다, 라면을 집었을 때 김밥을 살 확률이 무려 5배나 뛴다!"는 진짜 찰떡궁합(연관 규칙)을 찾아내어 매대에 나란히 진열했답니다!