1. 정의

ex 어떤 제품들이 종종 함께 판매되는가? = 연관 규칙
프린터 구매 후 이어질 구매는 어떤 것인가? = 순차 패턴

• 데이터베이스 내에서 항목(item)들간의 관계 즉, 빈번하게 발생하는 패턴를 발견하기 위한 규칙 기반 학습(Rule-Based Learning) 방법이다.

• 이는 마케팅에서 고객들의 상품 구매 데이터를 이용하여 품목 간의 연관성을 알아본다는 의미에서 장바구니 분석(Market Basket Analysis) 이라고도 한다.

• 일반적으로 트랜잭션 내에서 또는 트랜잭션 전반에서 항목의 순서는 고려하지 않는다는 특징을 가진다.

1.1 아이템과 트랜잭션

• 아이템 : 가장 기본이 되는 단위로, 항목 및 상품을 의미
• 트랜잭션 : 아이템 구매 로그 = 구매 내역

1.2 목적

아이템들 간의 Frequent patterns을 발견하기 위해서
💡 Frequent patterns : 데이터베이스 내에서 빈번하게 발생하는 패턴 (아이템들의 집합)

1.3 활용 분야

• 장바구니 분석
• 카탈로그 디자인
• 판매 캠페인 분석
• 웹로그 분석

2. 연관규칙 분석 지표

X→Y with 최소 지지도를 만족하는 모든 연관규칙 X→Y들을 발견한 후 이들을 사용한다.

✅ 지지도 (Support) $Support(X→Y)$

• 전체 매장 판매 中 X와 Y를 동시 포함하는 판매의 확률

✅ 신뢰도 (Confidence) $Confidence(X→Y)$

• X를 샀을 때, X와 Y를 둘 다 구매할 확률

✅ 향상도 (Lift) $Lift(X→Y) = Corr_x,y$

• X는 구매하지 않고 Y를 구매했을 때 대비 X를 사고 Y를 구매했을 때 확률의 증가비
• 1보다 큰 값일 때 의미를 가진다
  Lift > 1 : 양의 관계를 가진다
  ex) X를 샀을 때 Y를 살 확률이 높다
  Lift < 1 : 음의 관계를 가진다
  ex) X를 샀을 때, Y를 사지 않을 확률이 높다
  Lift = 1 : 아이템 X와 Y는 독립적이다

2-1 예제

3. 알고리즘 종류

Apriori, Eclat 및 FP-Growth 알고리즘은 잘 알려진 연관규칙 알고리즘이지만 빈발항목집합(frequent itemsets)을 마이닝하는 알고리즘이기 때문에 절반만 수행한다. 다음 단계는 데이터베이스에서 발견된 빈발항목집합에서 규칙을 생성하는 것이다.

3.1 Apriori 알고리즘

• 빈발항목집합(Frequent itemset)을 고려하여 연관 규칙을 발견하는 알고리즘
• 빈발항목집합 이란?
  최소 지지도를 넘는 항목 집합

3.1.1 절차

최소 지지도(min support) 경계값 결정
→ 후보군(Candidate) 생성
→ 후보군에서 최소 지지도 경계값을 넘는 빈발항목집단을 추출
→ 위 과정을 반복하여 최종 빈발항목집합 생성

✔ 후보군 검증
한 아이템셋의 지지도가 최소 지지도보다 클 경우에만 frequent

❓ 만약 {beer, diaper, nuts} 집합이 frequent하다면?
→ {beer,diaper}, {beer,nuts}, {diaper, nuts} 모두 최소 지지도 넘는 frequent여야 함

❓ 만약 frequent하지 않은 아이템 셋이 있다면?
그 아이템셋으로 다른 집합이 생겨서는 안되니까 Apriori 가지치기 원리로 제거!

3.1.2 후보군 생성

step 1. 결합 (Self joining)
itemset L1 = {abc, abd, acd, ace, bcd} 가 존재할 때,
결합을 통하여 (L1 * L1)

ex
abc, abd, acd, bcd로부터 abcd 생성
acd, ace, ade, cde로부터 acde 생성

❌ but, ade, cde가 L1에 포함되지 않으므로 acde는 제거 = 가지치기

4. 순차 패턴 분석

연관 규칙에 시간의 개념을 더한 것!
따라서 구매 순서가 중요하다!
→ 이후에 이어질 구매는 어떤 것인가?
연관규칙분석이 '거래 중심'이라면, 순차패턴분석은 한 사람이 순차적으로 구매한 '상품 중심'이다.

Sequence의 집합이 주어졌을 때, 빈번히 발생하는 Sequence 집합을 찾는것
💡 Sequence : 항목 집합을 순서로 나타낸 리스트

A sequence : < (ef) (ab) (df) c b > 라는 시퀀스가 주어졌을 때,
(ef) (ab) (df) c b 각 요소(element)는 서브 시퀀스이다.
한 요소 내의 아이템들은 (괄호 묶음) 순서를 고려하지 않는다!

4.1 절차

정렬 및 빈발항목집합 도출
→ 시퀀스로 변환
→ 빈발 시퀀스 도출
→ 최대 시퀀스 탐색

4.2 특성

순차 패턴의 기본특성은 Apriori와 동일하다.

• 최소 지지도 넘는 빈발 시퀀스 항목 추출
• frequent 하다면 서브 시퀀스도 frequent 해야한다! (=최소 지지도 넘어야한다)
  ex
  < hb >가 frequent하지 않다면, hb가 속한 < hab >, < (ah)b >도 frequent하지 않음

4.3 후보군 생성

후보군 수를 계산한 후 최소 지지도 검증을 통해 후보군을 도출하는 과정을 반복하여
최종 후보군 시퀀스를 도출한다.