5장 정형 데이터 마이닝

7절 연관분석

(1) 연관규칙

개념

• 연관성 분석(Association Analysis)
  • 연관성 분석은 흔히 장바구니 분석(Market Basket Analysis) 또는 서열 분석(Sequence Analysis)이라고 불림
• 연관성 규칙의 개념
  • 기업의 데이터베이스에서 상품의 구매, 서비스 등 일련의 거래 또는 사건들 간의 규칙을 발견하기 위해 적용
  • 장바구니 분석 : '장바구니에 무엇이 같이 들어 있는지에 대한 분석'
    ex) 1.주말을 위해 목요일에 기저귀를 사러 온 30대 직장인 고객은 맥주도 함께 사 간다.
    2. 이전에 동일한 제조사의 전자제품을 주로 구매했던 고객은 신제품 구매에서도 동일한 회사의 제품을 구매한다.
  • 서열 분석 : 'A를 산 다음에 B를 산다'
    ex) 1.가죽 재킷을 구매한 여성은 한 달 내에 가죽 부츠를 구매한다.
    2. 휴대전화를 새로 구매한 고객은 한 달 내에 휴대전화 케이스를 구매한다.
    

형태

• 조건과 반응의 형태(if-then)
  
  - '아메리카노를 마시는 손님 중 10%가 브라우니를 먹는다.'
  - '샌드위치를 먹는 고객의 30%가 탄산수를 함께 마신다.'
  
  

측도

• 연관성 분석의 측도는 산업의 특성에 따라 지지도(support), 신뢰도(confidence), 향상도(lift)값을 잘 보고 규칙을 선택해야 함

• 지지도(support) : 전체 거래 중 항목 A와 항목 B를 동시에 포함하는 거래의 비율로 정의
  

• 신뢰도(confidence) : 항목 A를 포함한 거래 중에서 항목 A와 항목 B가 같이 포함될 확률. 연관성의 정도를 파악할 수 있음
  

• 향상도(lift) : A가 주어지지 않았을 때의 품목 B의 확률에 비해 A가 주어졌을 때으 ㅣ품목 B의 확률의 증가 비율.
  연관규칙 A => B는 품목 A와 품목 B의 구매가 서로 관련이 없는 경우에 향상도가 1이 됨
  

절차

• 최소 지지도(minimum support)보다 큰 집합만을 대상으로 높은 지지도를 갖는 품목 집합을 찾는 것
  연관성 분석은 흔히 장바구니 분석(Market Basket Analysis) 또는 서열 분석(Sequence Analysis)이라고 불림
  - 처음에는 5%로 잡고 규칙이 충분히 도출되는지를 보고 다양하게 조절하여 시도
  - 처음부터 너무 낮은 최소 지지도를 선정하는 것은 많은 리소스가 소모되어 불필요함
  
• 절차
  (1)최소지지도 결정 -> (2)품목 중 최소 지지도를 넘는 품목 분류 -> (3)2가지 품목 집합 생성 -> (4)반복적으로 수행해 빈발 품목 집합을 찾음
  

특징

• 연관규칙의 장점
  • 탐색적인 기법 : 조건 반응(if-then)으로 표현되는 연관성 분석의 결과를 쉽게 이해할 수 있음
  • 강력한 비목적성 분석 기법 : 분석 방향이나 목적이 특별히 없는 경우 목적 변수가 없으므로 유용하게 활용됨
  • 사용이 편리한 분석 데이터의 형태 : 거래 내용에 대한 데이터를 변환 없이 그 자체로 이용할 수 있는 간단한 자료구조를 갖는 분석 방법
  • 계산의 용이성 : 분석을 위한 계산이 간단해 계산이 용이하므로 구매 가능성이 큰 상품군을 찾는 것에 활용 가능
• 연관규칙의 단점
  • 상당한 수의 계산과정 : 품목 수가 증가하면 분석에 필요한 계산은 기하급수적으로 증가
    -> 이를 개선하기 위해 유사한 품목을 한 범주로 일반화하는 방법
    -> 연관 규칙의 신뢰도 하한을 새롭게 정의해 실제 드물게 관출되는 의미가 적은 연관규칙은 제외하는 방법이 있음
  • 적절한 품목의 결정 : 너무 세분화한 품목을 갖고 연관성 규칙을 찾으면 의미 없는 분석이 될 수 있음
    -> 적절히 구분되는 큰 범주로 구분해 전체 분석에 포함시킨 후 그 결과 중에서 세부적으로 연관을 찾는 작업을 수행할 수 있음
  • 품목의 비율 차이 : 사용될 모든 품목들 자체가 전체 자료에서 동일한 빈도를 갖는 경우, 연관성 분석은 가장 좋은 결과를 얻음. 거래량이 적은 품목은 당연히 포함된 거래 수가 적을 것이고, 규칙 발견 시 제외되기 쉬움
    -> 이런 경우, 그 품목이 관련성이 살펴보고자 하는 중요한 품목이라면 유사한 품목들과 함께 범주로 구성하는 방법 등을 통해 연관성 규칙의 과정에 포함시킬 수 있음

순차 패턴분석

• 동시에 구매될 가능성이 큰 상품군을 찾아내는 연관성 분석에 시간이라는 개념을 포함시켜 순차적으로 구매 간으성이 큰 상품군을 찾아내는 것
• 연관성 분석에서의 데이터 형태에서 각각의 고객으로부터 발생한 구매 시점에 대한 정보가 포함됨
  '새 컴퓨터를 구입한 사람들 중 25%는 그다음 달에 레이저 프린트를 구입할 것이다.'

---

(2) 최근 연관성 분석 동향

개요

• 기존 연관성 분석의 이슈
  • 대용량 데이터에 대한 연관성 분석이 불가능
  • 시간이 많이 걸리거나 기존 시스템에서 실행 시 시스템 다운되는 현상
• 최근 연관성 분석 동향
  • 메모리를 효율적으로 사용함으로써 SKU 레벨의 연관성 분석을 성공적으로 적용
• 연관성 분석 활용 방안
  • 장바구니 분석의 경우는 실시간 상품 추천을 통한 교차 판매에 응용
  • 시차분석은 A를 구매한 사람들에게 B를 구매하지 않을 경우, B를 추천하는 교차판매 캠페인에 사용

Apriori 알고리즘

• 연관규칙 마이닝(Association Rules Mining) : 간단히 ARM이라 함
• 트랜젝션들의 집합이 주어졌을 때, 연관규칙 마이닝이란 다음 조건을 만족하는 모든 규칙을 찾는 작업
  • support ≥ minsup (support = 항목집합의 지지도, minsup = 주어진 최소지지도)
  • confident ≥ minconf (confidence = 규칙의 신뢰도, mincof = 주어진 최소신뢰도)
• 주먹구구식 방식(Brute-force approach)
  • 가능한 모든 연관규칙을 나열
  • 각 규칙의 지지도와 신뢰도를 계산
  • 주어진 minsup, mincof를 만족하지 않는 규칙을 제거(prune)
    -> 엄두도 못 낼 정도로 계산이 복잡해짐(Computationally prohibitive)

• Observations

  • 모든 규칙은 {Milk, Diaper, Beer}의 동일한 항목집합에서 비롯되었다.
  • 동일한 항목집합에서 나온 규칙들은 지지도는 동일하나 신뢰도는 다를 수 있다.
  • d개 항목에 대해, 2^d개의 항목집합을 고려해야 함 -> 부분집합의 개수
    

• 주먹구구식 접근법

  • 격차의 모든 항목집합이 후보 빈발 항목집합(candidate frequent itemset)이 됨

  • 트랜젝션 데이터베이스를 스캔하면서 각 후보에 대해 지지도를 카운트
    

  • 카운트를 위해, 모든 후보에 대해서 각 트랜젝션을 매치
    복잡도 ≃ O(NMw) -> Too Expensive since M = 2^d

• 계산 복잡도 분석

  • 항목이 d개 주어졌을 때,
  1. 가능한 항목집합의 개수 = 2^d
  2. 가능한 연관규칙의 개수 = 3^d - 2^{d+1} + 1
     

• Apriori(후보 개수 줄이기) 원리

  • 어떤 항목집합이 빈발하다면, 그 항목집합의 모든 부분집합도 빈발
  • 예 : {Milk,Bread, Diaper}가 빈발 항목집합이면, 이의 부분집합인 {Milk,Bread}, {Bread, Diaper} 등도 빈발 항목집합

• Apriori 원리가 성립하는 이유는 다음의 지지도 성질 때문

  $\forall X, Y : (X \subseteq Y) \Rightarrow s(X) \geq s(Y)$
  • 어떤 항목집합의 지지도는 그 부분집합들의 지지도를 넘을 수 없음
  • 이는 지지도가 anti-monotone성질을 가지기 때문이다.(a>b -> f(a) < f(b))

• Apriori원리의 도식화
  

---

(3) 연관분석 예제

분석 내용

• Groceries 데이터셋은 식료품 판매점의 1달 동안의 POS데이터이며, 총 169개의 제품과 9835건의 거래건수를 포함하고 있음
• 거래내역을 inspect함수로 확인할 수 있음

• apriori함수로 최소지지도와 신뢰도는 각각 0.01, 0.3으로 설정한 뒤 연관규칙분석을 시시한 결과, 총 88개의 아이템으로 연관규칙을 만들어냈으며 125개의 Rule이 발견되었음
• 규칙의 수가 너무 적으면 지지도와 신뢰도를 낮추소, 너무 많으면 지지도와 신뢰도를 높여야 함

• 항상도를 기준으로 내림차순으로 정렬한 후 상위 5개의 규칙을 확인해봤을 때, rhs의 제품만 구매할 확률에 비해 lhs의 제품을 샀을 때 rhs제품도 구매할 확률이 약 3배 가량 높음
• 따라서 rhs와 lhs제품들간 결합상품 할인쿠폰 혹은 품목배치 변경 등을 제안할 수 있음