추천시스템 이론 - 협업필터링(CF)의 SVD 모델 정리

David's Data Science·2022년 2월 22일

기본적인 추천 시스템 종류 컨텐츠 기반추천(CB), 협업 필터링(CF)

컨텐츠 기반 추천시스템(Content Based)
협업 필터링(CF, Collaborative Filtering)

메모리 기반 (Memory Based)
- 유저 기반 (User Based)
- 아이템 기반 (Item Based)
모델 기반 (Machine Learning)
- 잠재요인 기반(Latent factor Based)
  - SVD(Singular Vector Decomposition)
  - MF(Matrix Factorization)
  - AutoEncoder(Latent Feature)
  - SVM(Support Vector Machine) - 한마디로 선형 결정 경계를 찾는 모델
- 기타 분류/회귀 기반
- 딥러닝 기반(Deep Learning Based)
  - NCF(Neural Collaborative Filtering)
    - DCN(Deep Cross Network)
    - Wide & Deep
  - DeepFM(Deep Fatorization Machine)

SVD (Singular Value Decomposition)

일반적으로 잘 알려진 MF 모델의 원조(?) 격으로 볼 수 있는 행렬 분할 방법으로, 강력한 성능을 자랑하여 아직까지도 많은 곳에서 사용하고 있는 모델이다
본래 고유값 분해(Eigen Value Decomposition)를 이용한 행렬분해의 경우, 정방행렬(n x n)에 이어야 하지만, SVD를 이용한다면 m x n 행렬로도 대각행렬을 통한 특이값 분해가 가능하기 때문에 유저, 아이템의 행과 열의 개수가 다른 추천모델에도 적합하다.

고유값 분해:
n x n 의 정방행렬에 대해 선형변환 후의 벡터가 얼마나 커지거나 작아졌는지를 파악하기 위한 방법이자, 3개의 행렬로 분할하는 방법이다.

특이값 분해:
SVD는 특이값 분해로, m x n으로 이뤄진 A행렬에 대한 행렬분해를 하는 것을 의미한다.
기하학에서 선형변환 시 여전히 직교하지만 얼마만큼의 크기 변화가 있는지를 파악하는 것을 의미한다.

$A = U\sum V^T$ 로 이뤄지며 두 직교행렬(U, V (Orthonormal))과 1개의 대각행렬( $\sum$ , Singular Vectors)로 만들어진다.
또한 그 중 $\sum$ 행렬은 U,V와 직교하며, 위에서부터 내림차순으로 큰 값들을 가진 행렬이다.

Compact SVD, Truncated SVD, Full SVD

이러한 $\sum$ 행렬은 r x r의 행렬로 이뤄져있는데, 대각행렬의 값인 Singular Value는 위에서부터 중요한 정보 순으로 기입되어 있으며, 0을 포함한 모든 정보를 모두 이용하는 경우 Full SVD라고 하며, 0 또는 낮은 중요도를 갖는 일부 singular vector를 제거하여 행렬곱을 취해주는 방식을 Truncated SVD라고 한다.

SVD의 내부 원리

$A = U\sum V^T$ 일때,
A: m x n 행렬
U: Left singular matrix이자, 열벡터가 $AA^T$ (대칭행렬)의 고유벡터 (m x r, orthogonal matrix)
$\sum$ : r개의 특이값을 갖는 대각행렬 (r x r, diagonal matrix)
V: Right singluar matrix이자, 열벡터가 $A^TA$ (대칭행렬)의 고유벡터 (n x r, orthogonal matrix)

orthogonal matrix: rotation & reflection과 같이 방향만 바뀔 수 있다.
diagonal matrix: scale 변화만 가능하다.

특이값(Singular Value): 특이값(대각행렬 $\sum$ 의 값)은 m x n 행렬 A의 $A^TA$ 의 고유값(Eigen Value)에 루트를 씌운 값
고유값(eigen value): 임의의 벡터 v에 선형변환 A를 했을때 Av = $\lambda$ v( $\therefore \lambda$ 는 상수)를 만족하는 $\lambda$ 값을 의미한다. 선형변환에 의해 방향이 바뀌지 않는 vector의 scale factor라고 볼 수 있다.
고유벡터(eigen vector): 임의의 벡터 v에 선형변환 A를 했을때 Av = $\lambda$ v( $\therefore \lambda$ 는 상수)를 만족하는 v를 의미한다. 선형변환에 의해 방향이 바뀌지 않은 vector를 의미한다.

두 벡터 $v_1, v_2$ 가 수직인 경우, $v_1 v_2$ = 0이며 직교한다고 표현함.
$AA^T$ 와 $A^TA$ 의 공통의 고유값을 구한 뒤 루트를 씌워준 값들이 대각행렬에 내림차순으로 이뤄진 것이 $\sum$ 행렬이며, 해당 행렬을 이용해 truncated 또는 Full SVD를 위한 행렬곱을 진행한다.

본 포스팅에는 numpy 패키지로 이론을, sklearn 패키지로 SVD를 이용한 추천모델을 구현해본다.

Numpy 로 SVD 구현


import numpy as np
from numpy.linalg import svd

# 4 x 4 행렬 생성
np.random.seed(42)
a = np.random.randn(4,4)  # 평균 0, 표준편차 1의 가우시간 난수 생성
print(np.round(a, 3))

[output]
[[ 0.497 -0.138  0.648  1.523]
 [-0.234 -0.234  1.579  0.767]
 [-0.469  0.543 -0.463 -0.466]
 [ 0.242 -1.913 -1.725 -0.562]]

이렇게 임의의 4 x 4 매트릭스를 생성한 뒤, Numpy SVD를 통해3개의 행렬로 분할해본다.

# SVD 함수 적용해서 각 U, Sigma, Vt 확인해보기
U, Sigma, Vt = svd(a)
print('U:', np.round(U,3))
print('Sigma:', np.round(Sigma,3))  # 시그마의 경우, 대각행렬의 요소값인 Singular Value를 내림차순으로 가져온다.
print('Vt:', np.round(Vt,3))

[output]
U: [[-0.373 -0.598  0.642 -0.302]
 [-0.488 -0.35  -0.745 -0.289]
 [ 0.113  0.444  0.062 -0.887]
 [ 0.781 -0.568 -0.168 -0.197]]
Sigma: [3.08  1.926 0.92  0.342]
Vt: [[ 0.021 -0.412 -0.783 -0.466]
 [-0.291  0.775 -0.086 -0.554]
 [ 0.461  0.479 -0.544  0.512]
 [ 0.838  0.017  0.289 -0.462]]

위와 같이 $\sum$ 행렬의 특잇값들을 바탕으로 대각행렬을 만들어준다.

# 시그마의 대각행렬을 원상복구 해주는 방법: np.diag
Sigma_matrix = np.diag(Sigma)
print('Sigma :', np.round(Sigma_matrix, 3))

[output]
Sigma : [[3.08  0.    0.    0.   ]
 [0.    1.926 0.    0.   ]
 [0.    0.    0.92  0.   ]
 [0.    0.    0.    0.342]]

특잇값 행렬( $\sum$ )이 준비 되었으면 본래의 행렬 A로 다시 복원해보도록 한다.

a_ = np.dot(np.dot(U,Sigma_matrix), Vt)
print(np.round(a, 3) )  # 맨 처음의 매트릭스 a와 같음을 확인할 수 있다.

[output]
[[ 0.497 -0.138  0.648  1.523]
 [-0.234 -0.234  1.579  0.767]
 [-0.469  0.543 -0.463 -0.466]
 [ 0.242 -1.913 -1.725 -0.562]]

맨 처음 만들었던 임의의 매트릭스와 동일함을 알 수 있다.

sklearn 패키지 SVD를 이용해 영화 추천 구현해보기

데이터셋은 surprise 패키지 내에서 유용하게 사용할 수 있는 무비렌즈 데이터셋을 이용한다.
우선 패키지 설치를 한 뒤에 데이터셋을 정리해나가본다.

필요한 모듈 설치

!pip install scikit-surprise

데이터셋 불러오기

from surprise import SVD
from surprise import Dataset
from surprise.model_selection import cross_validate

# 패키지 내에서 유용하게 사용할 수 있는 무비렌즈 데이터 불러오기
data = Dataset.load_builtin('ml-100k', prompt = False)

# 어레이화 진행
raw_data = np.array(data.raw_ratings, dtype = int)

# user와 movie의 index를 0부터 시작할 수 있도록 1씩 빼준다.
raw_data[:, 0] -= 1
raw_data[:, 1] -= 1

# user개수, movie 개수 지정
n_users = np.max(raw_data[:, 0])
n_movies = np.max(raw_data[:, 1])

# shape 자체는 위에서 1씩 빼준것을 감안하여 1씩 더해준 것을 shape으로 둔다.
shape= (n_users +1, n_movies +1)
shape

[output]
(943, 1682)

인접행렬 생성하기

이후 인접행렬을 생성해 유저가 영화에 대한 평가를 한 경우 1, 아닌경우 0 을 두어 매트릭스를 생성한다.

# 인접행렬 생성, 유저, 아이템 개수에 맞는 0으로 이루어진 매트릭스
adj_matrix = np.ndarray(shape, dtype=int)


adj_matrix = np.ndarray(shape, dtype = int)
for user_id, movie_id, rating, time in raw_data:
  adj_matrix[user_id][movie_id] = rating # 유저 x 영화 행렬로 유저가 매긴 점수를 나타낸다
adj_matrix

[output]
array([[5, 3, 4, ..., 0, 0, 0],
       [4, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       ...,
       [5, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 5, 0, ..., 0, 0, 0]])

0번 유저에 대한 추천진행을 위해 ID, vector를 모두 0에 맞춰서 진행한다.
우선 각 0 번유저에 대한 벡터와 다른 유저 벡터를 행렬곱을 취해 가장 비슷한 유저를 찾아본다.

# 추천 진행할 id와 matrix에서의 해당 id 설정
id, vector = 0, U[0]
best_match_id, best_match_vector, best_match = -1, [], -1

for user_id, user_vector in enumerate(U):
  if id != user_id:
    cosine_similarity = compute_cos_similarity(vector, user_vector)
    if cosine_similarity > best_match:
      best_match_id = user_id
      best_match_vector = user_vector
      best_match = cosine_similarity

print(f'Best Match: {best_match} \nBest Match ID: {best_match_id} \nBest_Match_Vector: {best_match_vector}')

[output]
Best Match: 0.9999942295956324 
Best Match ID: 235 
Best_Match_Vector: [0.03467744 0.00326754]

이후 0번 유저는 보지 않았고, 가장 유사한 유저가 본 영화를 추천리스트에 담아서 출력해본다.

recommendation = []
for i, log in enumerate(zip(adj_matrix[id], adj_matrix[best_match_id])):
  log1, log2 = log # 유저 0이 본 영화정보 vector(log1)와 유저 0과 비슷한 유저가 본 영화정보 best_match_vector(log2)를 비교하기 위함
  if log1 <1. and log2 >0.:
    recommendation.append(i)
print(recommendation)

[output]
[272, 273, 274, 281, 285, 288, 293, 297, 303, 306, 312, 317, 327, 332, 369, 410, 418, 419, 422, 426, 428, 431, 434, 442, 461, 475, 477, 482, 495, 503, 504, 505, 506, 509, 519, 520, 522, 525, 531, 545, 548, 590, 594, 595, 613, 631, 654, 658, 660, 672, 684, 685, 691, 695, 698, 704, 716, 728, 734, 749, 755, 863, 865, 933, 1012, 1038, 1101, 1327, 1400]

참고한 글들
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=spin898&logNo=221139853857
https://deep-learning-study.tistory.com/481
https://hichoe95.tistory.com/57
http://elearning.kocw.net/contents4/document/lec/2013/Chungbuk/LeeGeonmyeong1/15.pdf
https://techblog-history-younghunjo1.tistory.com/66
https://techblog-history-younghunjo1.tistory.com/107
https://angeloyeo.github.io/2019/08/01/SVD.html
https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-20-%ED%8A%B9%EC%9D%B4%EA%B0%92-%EB%B6%84%ED%95%B4Singular-Value-Decomposition
https://jeongchul.tistory.com/603
https://m.blog.naver.com/skkong89/221354114678
https://rfriend.tistory.com/182