[Recommender System] 1.추천시스템의 이해 (연관분석, Apriori, FP-Growth)

T아카데미에서 오픈된 토크ON세미나 강연 동영상을 보고 정리해보았다.

 

추천시스템이란?

- 사용자(user)에게 상품(item)을 제안하는 기술이다.

- 어떤 상품을 구매할 지, 어떤 음악을 들을지, 어떤 동영상을 볼지와 같은 의사결정과 연관이 있다.

- 어떤 사용자에게 어떤 상품을 어떻게 추천할지 (20대에게, 오징어게임을...)

 

추천시스템의 활용

- 당근 마켓 : 관련 상품 추천

- 카카오 브런치 : 유사한 글 추천

- 유투브 알고리즘 ( 방대한 양 - 딥러닝 활용 )

 

파레토와 롱테일의 법칙

- 파레토 법칙 : 상위 20%가 80%의 가치를 창출한다.

- 롱테일 법칙 : 하위 80%가 상위 20%의 가치보다 크다.

인터넷의 발전에 따라 롱테일의 법칙이 온라인 상에서 중요해졌다.

 

추천시스템의 역사

2005 ~ 2010 : Apriori 알고리즘 - 연관상품 추천

2010 ~ 2015 : 협업 필터링 - SVD / 넷플릭스 추천대회(2006~2009)

2013 ~ 2017 : Spark를 이용한 빅데이터 - FP-Growth / Matrix Factorization

2015 ~ 2017 : 딥러닝을 이용한 추천시스템 - 협업필터링 + 딥러닝 / Item2Vec, Doc2Vec / Wide & Deep Model / YouTube 추천

2017 ~           :  개인화 추천시스템 - Factorization Machine / Hierarchical RNN / 강화학습 + Re-Ranking / 딥러닝

 

---

[Rule 기반의 추천시스템]

연관분석 (Association Analysis)

1. 얼마나 같이 구매가 되는지 (frequent)

2. A아이템을 구매하는 사람이 B아이템을 구매하는지 (장바구니 분석 - 월마트 맥주/기저귀 사례)

 

[평가지표]

- support (지지도)  =  P(A,B) : A와 B를 모두 구매할 확률

- confidence (신뢰도)  =  P(A,B) / P(A)  : A를 구매했을 때 B를 구매할 확률

- lift (향상도)  =  P(A,B)  /  ( P(A)*P(B) )  : A와 B가 동시에 얼마나 발생하는지 비율

 

[규칙 생성]

가능한 모든 경우의 수를 탐색해서 지지도, 신뢰도, 향상도가 높은 규칙들을 찾아내야 한다.

 

[문제점]

아이템의 증가에 따라 규칙의 수가 기하급수적으로 증가함. 아이템이 100개라면 1.26 * 10^30개....

 

---

Apriori 알고리즘

- 연관분석의 문제점을 해결하기 위함

- 아이템셋의 증가를 줄이기 위한 방법 = "빈번한 아이템셋을 하위 아이템셋 또한 빈번할 것이다"를 이용해서 아이템셋의 증가를 줄임

( = "빈번하지 않은 아이템셋은 하위 아이템셋 또한 빈번하지 않다"

 

[원리]

1. k개의 Item을 가지고 단일항목집단 생성 (one-item frequent set)

2. 단일항목집단에서 최소 지지도 이상의 항목만 선택

3. 2에서 선택된 항목만을 대상으로 2개항목집단 생성

4. 2개항목집단에서 최소 지지도 혹은 신뢰도 이상의 항목만 선택 = "빈번하지 않은 아이템셋은 하위 아이템셋 또한 빈번하지 않다"

5. 위의 과정을 k개의 k-item frequent set을 생성할 때까지 반복

 

[장점]

- 원리가 간단하여 사용자가 쉽게 이해할 수 있다.

- 유의한 연관성을 갖는 구매패턴을 찾아준다.

 

[단점]

- 데이터가 클 경우 (item이 많은 경우)에 속도가 느리고 연산량이 많다.

- 실제 사용시에 많은 연관상품들이 나타난다.

- 연관상품들이 상관관계는 유의미해도 인과관계는 성립되지 않는다.

 

---

FP-Growth 알고리즘

- Apriori의 속도측면의 단점을 개선한 알고리즘이다.

- Apriori와 비슷한 성능을 내지만 FP Tree라는 구조를 사용해서 빠른 속도를 가진다.

- 하지만, 동일하게 발생하는 아이템셋 (frequent itemsets)을 찾는데는 좋지만 아이템간의 연관성을 찾는 것은 어렵다.

 

[원리]

1. 모든 거래를 확인하여, 각 아이템마다의 지지도를 계산하고 최소 지지도이상의 아이템만 선택 = Apriori와 동일

2. 모든 거래에서 빈도가 높은 아이템 순서대로 순서를 정렬

3. 부모 노드를 중심으로 거래를 자식노드로 추가해주면서 tree를 생성

4. 새로운 아이템이 나올 경우에는 부모노드부터 시작하고, 그렇지 않으면 기존의 노드에서 확장

5. 위의 과정을 모든 거래에 대해 반복하여 FP Tree를 만들고 최소 지지도 이상의 패턴만을 추출

 

[장점]

- Apriori 알고리즘보다 빠르고 2번의 탐색만 필요로 함 : db를 두번만 스캔하면 되기 때문.

- 후보 itemsets을 생성할 필요없이 진행 가능 : Apriori와 다르다.

 

[단점]

- 대용량의 데이터셋에서 메모리를 효율적으로 사용하지 않음

- Apriori 알고리즘에 비해서 설계하기 어려움

- 지지도의 계산이 FP-Tree가 만들어지고 나서야 가능함

 

 

[실습 링크]

https://www.kaggle.com/chocozzz/00-apriori-fp-growth

00. 추천시스템 이해 -Apriori, FP-Growth

https://github.com/yoonsungsong/TIL/blob/main/RecommenderSytem/Apriori_and_FP-Growth.ipynb

GitHub - yoonsungsong/TIL: Today I Learned..

 

단점이 너무 critical해서 현업에서는 잘 활용되지 않는다.

 

 

Reference : 

https://www.youtube.com/watch?v=43gb7WK56Sk&t=2349s