연관분석 (Association Analysis)

전체 링크

연관분석

- 데이터 안에서 항목들 간의 흥미로운 관계(패턴)를 발견하는 데이터 마이닝 기법

- 동시 발생 관계를 찾는 기법이며, 기본적으로 순서나 시간 개념이 없음

- 장바구니 분석, 서열 분석

- 강력한 비 목적성 분석 기법

- A를 구매하면 B도 구매할 가능성이 높다 : A → B (A가 발생하면 B도 발생한다)

 

지지도 (Support)

- 전체 거래 중 A와 B를 동시에 포함하는 거래의 비율

- 조건 품목과 결과 품목을 동시에 포함하는 거래의 비율을 의미

- A와 B가 함께 등장하는 비율

- 규칙의 중요도, 빈도 기준

 

신뢰도 (Confidence)

- A가 발생했을 때 B도 발생할 확률

- A 상품을 샀을 때 B 상품을 살 조건부확률에 대한 척도

- 조건 품목을 샀을 때 결과 품목을 구매할 조건부 확률을 의미

- 조건부 확률 기반의 규칙의 정확도

- 지지도 / P(A)

→ A항목이 포함된 거래 중 A항목과 B항목이 동시에 포함된 거래의 비율을 나타내는 지표

→ 신뢰도가 높은 경우 A를 구매했을 때, B를 구매할 것이라는 규칙의 신뢰도가 높다는 것을 의미

 

향상도 (Lift)

- A와 B가 동시에 나타나는 정도가, A와 B가 독립이라고 가정했을 때 기대되는 빈도보다 얼마나 큰지를 보여주는 지표

- A가 구매되지 않았을 때 품목 B의 구매확률에 비해 A가 구매되었을 때 품목 B의 구매확률의 증가 비

- A와 B가 우연 이상의 관계인지 측정

- 1보다 크면 양의 연관성 → 우연보다 더 자주 발생, 유의미한 연관규칙

- 1이면 무관 → 완전히 독립적

- 1 미만이면 음의 연관성 → A가 발생하면 B 발생 확률이 오히려 낮아짐 → 추천하면 오히려 역효과

 

- confidence를 B의 전체 발생 확률로 나눈 값

 

장점

- 대규모 거래 데이터에서 유용한 패턴을 자동으로 발견

- 직관적이고 해석이 쉬움, 계산이 간단

- 비지도학습(unsupervised) 기법으로 레이블 불필요

 

단점

- 조합 폭발(Combinatorial Explosion) 문제 (아이템 ↑ 계산량이 기하급수적으로 증가)

- 의미 없는 규칙이 너무 많이 발견될 수 있음

→ 유사한 품목을 하나의 범주로 묶기, 신뢰도 하한을 새롭게 정의

 

- 연속형 데이터 처리 어려움 (이산형 변환 필요)

- 인과관계를 말해주지 않음 (단순한 공존만 파악)

- 매우 흔한 아이템 때문에 잘못된 규칙이 만들어질 수 있음 (휴지 → 물, Confidence는 높지만 Lift는 낮을 수 있음)

---

알고리즘

Apriori

- 가장 기본적인 연관분석 알고리즘

- 항목 집합의 지지도를 산출하여 발생빈도와 최소지지도를 기반으로 거래 연관성을 밝히는 알고리즘

- 최소 지지도보다 큰 집합을 찾은 후, 해당 품목에 대해서만 연관 규칙을 계산

- 반(anti) 모노토닉 원리 사용 → 빈발 아이템 집합의 모든 부분집합도 빈발하다.

- 이를 이용해 작은 빈발 집합부터 생성 → 확장하며 큰 집합을 찾는 탐색 기반 방식

- 후보 아이템셋(Candidate Set)을 계속 생성하고, 데이터베이스를 반복해서 스캔해야 함.

- 구현이 간단

- 지지도가 낮은 후보 집합 생성 시 아이템 수가 많아지면 계산 복잡도가 증가

 

FP-Growth

- Apriori의 단점을 극복하기 위해 고안

- Candidates(후보) 생성 없음 → 패턴 압축 구조(FP-tree) 사용

- 데이터베이스를 두 번만 스캔 (빈도 계산, FP-tree 구성)

- FP-tree를 조건부로 분기하며 빈발 아이템셋을 도출

- 후보 생성이 없고 DB 스캔이 적기 때문에 Apriori보다 빠름

- 대규모 데이터 처리, 중복 구조를 압축 효율화

- FP-tree 구축 과정이 복잡, 트리가 커지면 메모리 사용량 증가

- 대용량 데이터 세트에서 메모리가 효율적이지 않고, 설계가 어려움

 

Eclat (Equivalence Class Transformation)

- 수직 데이터 형식 이용 : 아이템 → 등장 트랜잭션 ID 목록(TIDset)

- 아이템셋 교집합을 이용해 빈발 아이템셋 찾기 : Support = TIDset 교집합 크기

- Apriori의 개선버전이지만 FP-Growth와는 접근 방식이 다름

- 교집합 연산만 수행 → 속도가 빠름

- 데이터가 희소(sparse)할수록 매우 효율적

---

Example

(A → B)의 향상도를 구하라

 

지지도 P(A∩B) : 3 / 10

P(A) : 6 / 10

P(B) : 6 / 10

 

정답 :

 

 

---

(A → C)의 향상도를 구하라

데이터 1 : (A, B, C)
데이터 2 : (A, B, C)
데이터 3 : (A, B)
데이터 4 : (C, D, E)
데이터 5 : (C, D, E, A)

 

정답 :

P(A) = 4 / 5

P(C) = 4 / 5

P(A∩C) = 3 / 5

---

(A → B, C)의 향상도를 구하라

품목 / 건수
A / 5
B, D / 10
D / 5
A, B, C, D / 2
B, C / 1
A, B, C / 3
A, C / 4

 

정답 : 

총 거래수 = 30건

A가 있으면 B와 C가 동시에 있는 경우를 계산

 

P(A) = (5 + 2 + 3 + 4) / 30 = 14 / 30

P(B ∩ C) = (2 + 1 + 3) / 30 = 6 / 30

P(A ∩ B ∩ C) = (2 + 3) / 30 = 5 / 30

---

(맥주, 기저귀 → 라면)의 지지도와 신뢰도를 구하라

[맥주, 기저귀, 라면]
[과자, 휴지, 기저귀, 수건]
[휴지, 수건]
[맥주, 기저귀, 수건, 라면]
[과자, 휴지, 수건, 라면]
[맥주, 기저귀]

 

정답 : 

맥주 & 기저귀 & 라면이 함께 있는 거래 = 2 

맥주 & 기저귀 거래 수 = 3

---

A → B의 지지도는 0.3이고, 신뢰도가 0.6이다.

A와 B의 판매 수량이 동일할 때, 향상도를 구하라

 

정답 : 

 

판매 수량이 동일하다면 P(A) = P(B)

---

(B → C)의 지지도와 신뢰도를 구하라

데이터 1 : A B
데이터 2 : A C D
데이터 3 : A B C E
데이터 4 : A E C
데이터 5 : A B C F

 

정답 : 

B와 C가 동시에 있는 거래 = 2

B가 있는 거래 = 3

---

(맥주 → 기저귀)의 향상도를 구하라

맥주, 기저귀, 라면 = 100
맥주, 라면 = 400
기저귀, 라면, 수건 = 150
기저귀, 맥주, 수건 = 200
라면, 수건 = 150

 

정답 : 

전체 거래 수 = 1000

P(맥주 ∩ 기저귀) = 300 / 1000 = 0.3

P(맥주) = 700 / 1000 = 0.7

P(기저귀) = 450 / 1000 = 0.45