03) 나도 이해한 추천시스템 알고리즘 _ 협업필터링

References
- [토크ON세미나] 추천시스템 분석 입문

0. 글 쓰기에 앞서

추천시스템은 크게 컨텐츠 기반 추천과 협업 필터링으로 구분 할 수 있는데, 지난 포스팅에서는 컨텐츠 기반 추천 모델에 대해 알아보았다.

02) 나도 이해한 추천시스템 알고리즘 _ 컨텐츠 기반 모델

이번 포스팅에서는 협업 필터링에 대해 정리해보았다.

1. 협업필터링 개요

• 정의 : 사용자의 구매 패턴이나 평점을 가지고 다른 사람들의 구매 패턴, 평점을 통해서 추천을 하는 방법
  • 추가적인 사용자의 개인정보나 아이템의 정보가 없이도 추천 가능

💡 협업필터링은 Netflix Prize Competition 우승 알고리즘

• 종류 : 최근접 이웃기반(KNN), 잠재 요인기반

1-1. 협업 필터링의 장점

• 도메인 지식이 필요하지 않음
• 사용자의 새로운 흥미를 발견하기 좋음
• 시작단계의 모델로 선택하기 좋음 (추가적인 문맥정보등의 필요가 없음)

1-2. 협업 필터링의 단점

• 새로운 아이템에 대해서 다루기가 힘듬
• side features (고객의 개인정보, 아이템의 추가정보)를 포함시키기 어려움

2. Neighborhood based method (이웃기반)

2-1. Neighborhood based method

• Neighborhood based Collaborative Filtering은 메모리 기반 알고리즘으로 협업 필터링을 위해 개발된 초기 알고리즘이다.
• 알고리즘
  1. User-based collaborative filtering(유저 유사도)
  → 사용자의 구매 패턴(평점)과 유사한 사용자를 찾아서 추천 리스트 생성
  1. Item-based collaborative filtering(아이템 유사도)
  → 특정 사용자가 준 점수간의 유사한 상품을 찾아서 추천 리스트 생성

2-2. KNN (K Nearest Neighbors)

• 가장 근접한 K 명의 Neighbors를 통해서 예측하는 방법

(예시)

2-2-1. KNN in 유저간의 유사도

→ 가중치를 줘서 평점을 높게 주는 사람 구분

2-2-2. KNN in 아이템간의 유사도

2-2-3. KNN 장점

• 간단하고 직관적인 접근 방식 때문에 구현 및 디버그가 쉬움
• 특정 Item을 추천하는 이유를 정당화하기 쉽고 Item 기반 방법의 해석 가능성이 두드러짐
• 추천 리스트에 새로운 Item과 User가 추가되어도 상대적으로 안정적

2-2-4. KNN 단점

• User 기반 방법의 시간, 속도, 메모리가 많이 필요
• 희소성 때문에 제한된 범위가 있음
  • 비슷한 이웃중에서 아무도 특정 item을 평가하지 않으면 그 item에 대한 예측을 제공하기 어려움

3. Latent Factor Collaborative Filtering (잠재요인 기반)

Neighborhood Model (이웃기반) Collaborative Filtering

→ 아이템의 벡터와 유저스페이스의 벡터간의 조합을 통해 아이템이나 유저간의 유사도를 계산

Latent Model (잠재요인기반) Collaborative Filtering

→ Item, User Space 각각의 Latent Space를 만들고 그 두 matrix의 곱을 통해서 추천 진행

⇒ R : Rate matrix ~ U : User matrix * V : Item matrix

3-1. SVD

💡 한계 : 데이터에 결측치가 없어야 함 (대부분의 현업 데이터는 Sparse한 데이터)

3-2. SGD (Stochastic Gradient Descent)

SGD(Stochastic Gradient Descent)란?

SGD, 즉 확률적 경사 하강법이란 전체 데이터 중 단 하나의 데이터만을 이용해 경사 하강법을 1회 진행(배치 크기가 1)하는 방법

BGD, MBGD, SGD 비교

3-2-1. SGD의 장점

• Shooting이 일어나기 때문에 Local Minima(지역 최저점)에 빠질 확률이 적다
  • 각 데이터에 대한 손실값의 기울기가 약간씩 다르기 때문에, 개별 데이터에 대한 미분을 수행하면 기울기의 방향이 매번 크게 바뀜
    • ⇒ 손실값의 평균으로 경사하강을 진행하는 것이 MSGD
• BGD(Batch Gradient Descent)에 비해 적은 데이터로 학습 할 수 있고, 속도가 빠른 장점이 있다

3-2-2. SGD의 단점

• 한 번에 한개의 데이터를 이용하므로 GPU의 병렬 처리를 그다지 잘 활용하지는 못한다
• 1회 학습할 때 계산량이 줄어든다
• Global Minimum에 수렴하기 어렵다
• 노이즈가 심하다(Shooting이 심하기 때문)

SGD 설명

3-2-3. 추천 시스템에서의 SGD

목표 : R - (U x Vt) 를 최소화하는 U와 Vt를 찾자

R : 평점 매트릭스

U : 유저 매트릭스

Vt : 아이템 매트릭스

Weight 값의 경우 Regularization을 해주지 않으면 폭발적으로 증가하는 경우가 있음

→ Regularization이 반드시 필요!!

U(User Latent matrix)에서의 column, V(Item Latent matrix)에서의 row의 크기는 사용자가 정한다 ⇒ 보통 20을 많이 사용!!

💡 U와 V의 값들은 randomly initialize

3-2-4. SGD(협업필터링에서) 장점

• 매우 유연한 모델로 다른 Loss function을 사용할 수 있음
• parallelized가 가능함 (병렬처리) ⇒ 더 빠름

3-2-5. SGD(협업필터링에서) 단점

• 수렴속도가 매우 느림 (딥러닝 모델을 좋은 것을 사용하면 빠르다 → 즉 걱정X)

3-3. ALS

3-3-1. ALS의 정의

• 기존의 SGD가 두개의 행렬(User Latent, Item Latent)을 동시에 최적화하는 방법이라면, ALS는 두 행렬중 하나를 고정시키고 다른 하나의 행렬을 순차적으로 반복하면서 최적화
  • 기존의 최적화 문제가 convex 형태로 바뀌기에 수렴된 행렬을 찾을 수 있다

3-3-2. ALS 알고리즘

1. 초기 아이템, 사용자 행렬을 초기화
2. 아이템 행렬을 고정하고 사용자 행렬을 최적화
3. 사용자 행렬을 고정하고 아이템 행렬을 최적화
4. 위의 2,3 과정을 반복

3-3-3. ALS 장점

• SGD보다 수렴속도가 빠름
• paralledlized가 가능함 (병렬처리)

3-3-4. ALS 단점

• 오직 Loss Squares만 사용가

4. 정리

이번 포스팅에서는 협업필터링이란 무엇인지 또 최근접 이웃기반(KNN), 잠재 요인기반에는 각각 어떤 예시가 있는지 알아보았다. 다음 포스팅에서는 추천시스템의 평가 함수에 대해서 정리할 것이다.

 

(추가) 행렬곱과 내적

협업필터링을 공부 하다보니 내적과 행렬곱 개념이 헷갈려 추가로 정리해봤다.

np.dot과 np.matmul의 차이

• np.dot : 내적
• np.matmul (@으로도 사용 가능) : 행렬곱

⇒ 2차원에서는 내적과 행렬곱은 같은 역할을 한다

⇒ 3차원 이상부턴 다르다 (이때는 행렬곱 = 외적)

• 4차원 예시코드 

  import numpy as  np
  a = [[[[0 for k in range(4)] for j in range(3)] for i in range(6)] for z in range(1)]
  b = [[[[0 for k in range(1)] for j in range(4)] for i in range(1)] for z in range(4)]
  print("a shape: ",np.array(a).shape)
  print("b shape: ",np.array(b).shape)
  print("np.dot(a,b).shape: ",np.dot(a,b).shape)
  print("np.matmul(a,b.shape): ",np.matmul(a,b).shape)
  
  # a shape:  (1, 6, 3, 4)
  # b shape:  (4, 1, 4, 1)
  # np.dot(a,b).shape:  (1, 6, 3, 4, 1, 1)
  # np.matmul(a,b.shape):  (4, 6, 3, 1)
  

  import numpy as  np
  ~~~~a = [[[[0 for k in range(4)] for j in range(3)] for i in range(1)] for z in range(1)]
  b = [[[[0 for k in range(2)] for j in range(4)] for i in range(1)] for z in range(10000)]
  print("a shape: ",np.array(a).shape)
  print("b shape: ",np.array(b).shape)
  print("np.dot(a,b).shape: ",np.dot(a,b).shape)
  print("np.matmul(a,b.shape): ",np.matmul(a,b).shape)
  
  # a shape:  (1, 1, 3, 4)
  # b shape:  (10000, 1, 4, 2)
  # np.dot(a,b):  (1, 1, 3, 10000, 1, 2)
  # np.matmul(a,b):  (10000, 1, 3, 2)
  

  a.shape = (a1,a2,a3,a4), b.shape = (b1,b2,b3,b4)
  • 내적(dot)이 계산되려면 a4==b3(인덱스로 뒤에서 두번째)
  • 행렬곱(matmul,@)이 계산되려면 a1==b1,a2==b2 (이때 1이면 상관없다⇒numpy의 broadcasting)이면서 a4==b3