추천시스템 입문하기 - 추천시스템의 이해

T아카데미 토크온 세미나 강의를 통해서 추천시스템을 공부해보기로 했다.

추천 시스템은 사용자(user)에게 상품(item)을 제안하는 기술이다. 다양한 기업에서 추천시스템을 사용하기 때문에 실제로 추천 시스템 전문가를 채용하는 공고가 많은 편이다.

추천시스템의 역사

연관분석(Association Analysis)

룰 기반의 모델로 상품간에 어떤 연관이 있는지 찾아내는 알고리즘. 아이패드를 구매하면 애플 펜슬도 구매한다 같은 것으로 장바구니 분석이라고 표현하기도 한다.

연관이란?

• 얼마나(frequent) 같이 구매가 되는가
• A item을 구매하는 사람이 B item을 구매하는가?

support(지지도)는 a라는 상품을 구매할 확률을 의미한다. $P(A)$
confidence(신뢰도)는 a라는 상품을 구매했을 때 b라는 상품까지 구매할 확률로 ${P(A,B)\over P(A)}$
lift(향상도)는 두 사건이 동시에 얼마나 발생하는지의 비율로 독립성을 측정한다. $P(A,B)\over P(A)\cdot P(B)$

가능한 모든 경우의 수를 탐색해서 지지도, 신뢰도, 향상도가 높은 규칙들을 찾아내는 방식. 아이템 수가 증가함에따라 규칙의 수가 지수적으로 증가해서 문제점이 있다.

Apriori는 아이템셋의 증가를 줄이기 위한 방법으로 빈번한 아이템 셋은 하위 아이템 셋또한 빈번할 것이다라는 아이디어 기반의 방법. 많이 보지 않는 상위 아이템 셋은 하위 아이템셋도 많이 안 볼 것이다 생각해서 아이템셋의 증가를 줄이는 방법

Apriori 알고리즘
1. k개의 item을 가지고 단일항목집단 생성 (one-item frequent set)
2. 단일항목집단에서 최소 지지도 이상의 항목만 선택
3. 2에서 선택된 항목만을 대상으로 2개항목집단 생성
4. 2개항목집단에서 최소 지지도 혹은 신뢰도 이상의 항목만 선택
5. 위의 가정을 k개의 k-item frequent set을 생성할 때까지 반복

예시

1. 5개의 item을 가지고 단일항목집단 생성: 우유, 양상추, 기저귀, 쥬스, 맥주
2. 단일항목집단에서 최소 지지도 이상의 항목만 선택 (ex. 0.5)
   쥬스의 경우 4번의 거래중 1번 구매 $P(쥬스):0.25$로 제거
3. 선택된 항목만으로 2개항목집단 생성 {우유, 양상추, 기저귀, 맥주}
   {우유, 양상추}, {우유, 기저귀}, {우유, 맥주}, {양상추, 기저귀}, {양상추, 맥주}, {기저귀, 맥주}
4. 3에서 최소 지지도 이상의 항목만 선택
   {우유, 양상추}: 0.25 , {우유, 맥주}: 0.25로 제거
5. k개의 set을 생성할 때까지 반복

• {우유}, {양상추}, {기저귀}, {맥주}
• {우유, 기저귀}, {양상추, 기저귀}, {양상추, 맥주}, {기저귀, 맥주}
• {양상추, 기저귀, 맥주}

apriori의 장점은 원리가 간단해서 사용자기 쉽게 이해할 수 있고 의미를 파악할 수 있다. 그리고 유의미한 연관성을 갖는 구매 패턴을 찾아준다. 하지만 데이터가 큰 경우 속도가 느리다. 실제 데이터셋에서는 많은 연관 상품이 나타난다.

그래서 단점을 보완하기 위해서 FP-Growth라는 알고리즘이 나온다. Apriori 알고리즘보다 빠르고 2번의 탐색만 필요하다. 후보 item set을 생성할 필요없이 진행이 가능하다. 하지만 역시 대용량에서 메모리가 효율적이지 않고, tree를 다 만들고 계산을 할 수 있다는 단점이 있다.

1. 모든 거래를 확인해서 각 아이템마다 지지도를 계산하고 최소 지지도 이상의 아이템만 선택
2. 모든 거래에서 빈도가 높은 아이템을 순서대로 정렬
   
3. 부모 느드를 중심으로 거래를 자식노드로 추가해주면서 tree를 생성
4. 새로운 아이템이 나올 경우에는 부모 노드부터 시작하고 그렇지 않으면 기존 노드에서 확장
   
5. 지지도가 낮은 순서부터 시작해서 조건부 패턴을 생성
   
6. 모든 아이템에 대해서 반복
7. Conditional Pattern bases를 기반으로 패턴 생성

상품이 많아서 추천을 하는 것일 텐데 아이템 수가 많아질 때 사용하기 어려우면 현업에서 사용하기는 어려울 것 같다. 아이템 수가 적다면 알고리즘보다는 도메인 지식이 있는 사람이 직접 추천을 해주는 게 더 효과적일 것 같다.