추천#1) 룰 기반의 연관 분석, Apriori, FP-Growth

이 글은 유튜브의 T아카데미에 공개되어있는 추천 시스템 분석 입문하기를 기반으로 작성 되었습니다.

추천 시스템 기초

 추천시스템의 목표는 어떤 사용자에게 어떤 상품을 어떻게 추천할지에 대한 것이다. 즉, 사용자를 정의하고, 서비스에서 제공하는 상품(아이템)을 제안하는 기술이다. 이는 다양한 의사결정과 관련이 있다. 예를 들어, 영화나 쇼핑몰에서 사용하기 쉽다. 실제로 당근 마켓의 상품 추천, 카카오 브런치의 글 추천에서도 사용되고 있다.

 

 추천 시스템이 중요해진 이유는 페로토와 롱테일의 법칙을 통해 설명할 수 있다. 페로토 법칙 : 상위 20%가 80%의 가치를 창출한다. 롱테일 법칙 : 하위 80%가 상위 20%의 가치보다 크다.  롱테일의 법칙은 인터넷 환경에서 중요한데, 이는 하위 80%에게 영업기회가 남아있다라고 보기때문이고, 실제로 이를 통해 이익을 올릴수 있다.

 

 아래의 이미지는 추천 시스템의 발전과정을 볼 수 있는데, 초기에는 룰 기반의 방식에서 대용량 데이터와 ML, DL의 사용으로 발전되어 왔다.

 

연관 분석

룰 기반의 모델, 상품과 상품 사이에 어떠한 연관이 있는치 찾는 알고리즘이다. 연관을 찾는 방법은 아래의 두가지 방법이다.

1. 두 상품이 같이 구매되는 경우
2. A를 구매하는 사람이 B도 구매하는가?

다음은 규칙 평가 지표이다.

 

support(지지도) : support(A) = P(A) or P(A,B)

 -> 전체 거래 건수 중에서 항목집합 A와 B를 모두 포함하는 거래 건수의 비율을 말합니다. 

confidence(신뢰도) : confidence(A→B) = P(A,B)/P(A)

 -> 항목집합 A를 포함하는 거래 중에서 항목집합 B도 포함하는 거래 비율 (조건부 확률) 을 말합니다.

lift(향상도) : P(A,B) / P(A) * P(B)

 -> 이는 두 사건이 얼마나 동시에 발생하는지를 독립성으로 찾는것. 즉 항목집합 A가 주어지지 않았을 때의 항목집합 B의 확률 대비 항목집합 A가 주어졌을 대 항목집합 B의 확률 증가 비율을 말합니다.

 

 규칙 생성 방식으로는 모든 아이템에 대해서 전체의 경우의 수를 구한다. 예를 들어 상품이 4개이면, 4C1 + 4C2 + 4C3 + 4C4 = 15이다. 강 방식에 대해서 실제 거래를 통해서 가장 높은 확율을 구하는 방식이라고 볼 수 있다. 이는 아이템의 증가에 따라서 규칙의 수가 기하급수적으로 증가하는 단점을 가지고 있다.

 

Apriori 알고리즘

 앞선 연관 분석의 단점을 개선한 방식이다. 기본 방식은 "빈번하지 않은 아이템 셋은 하위 또한 빈번하지 않다." 라는 것이다. 즉, {2,3}이 빈번하지 않으면, {0,2,3}, {1,2,3} 과 같은 케이스를 제거하는 것이다. 알고리즘은 아래의 3단계를 통해서 확률을 구하게 된다.

1. 단일 항목 집잔 생성
2. 단일항목집단에서 최소 지지도(suppport) 이상의 항목만 선택 → 사용자의 지정 파라미터, 사실상 이부분을 통해 적게 전체에서 적게 선택되는 항목에 대한 것을 알수가 없음.
3. 위의 방식을 선택 항목을 늘려가며 반복

 실제로는 거래목록을 통해서 Sparse Matrix로 변경하고, 계산하게 된다. 이와 같이 거래목록과 같은 데이터를 Implicit Feedback라 하는데, 이는 평점이 없어서 이렇게 표현한다. 

 

 이 방식의 장점은 원리 쉽고, 사용자가 쉽게 이해 가능, 의미 파악도 쉽다. 또한, 연관성을 가지는 구매패턴을 찾을 수 있다. 단점으로는

아이템이 많아지면 여전히 연산량이 높고, 실제로는 너무 많은 연관상품이 나오는 케이스가 있음. ⇒ 연관 상품이 실제로 인과관계를 의미하지 않을 가능성이 있다.

 

FP-Growth

 이 알고리즘은 Apriori 알고리즘의 속도를 개선한 방식으로 FP tree구조를 통해 계산하게 되고, 전체 거래를 2번만 탐색하면 완료되기에 속도가 빠르고, 후보 itemset 또한 만들 필요가 없다. 원리는 아래의 4단계이다. 

1. 모든 거래에서 단일 선택에 대한 지지도 계산, 최소 지지도 이상만 선택.
2. 모든 거래를 단일 항목에 대한 빈도 순으로 정렬(높은 게 앞으로).
3. 거래에 대해서 트리를 구축. 루트를 하나를 만들고 선택된 거래에 대해서 정렬을 통해 앞에 있는 항목을 루트랑 가까운 곳에 배치.
4. 모든 데이터에 대해서 반복, 새로운 아이템이 나오면 분기하여 확장.

 장점으로 이야기한 2번의 탐색은 모든 거래에서 단일 지지도 계산에서 1회, 트리 구축에서 1회이다. 여전히 메모리 비효율과 설계의 어려움을 가지고 있다.