Python Surprise lib에서 제공하는 추천 알고리즘을 코드와 함께 살펴보자

Surpriselib

Surpriselib은 추천시스템을 위한 Python 라이브러리다. 필자가 회사에서 추천시스템을 구축하면서 가장 먼저 Toy model처럼 사용했던 라이브러리였다. 제공하는 알고리즘들이 수식과 영어로 되어있어서 상대적으로 더 복잡해보여서 간단하게 해석해본 내용을 이 블로그에서 공유하고자 한다. 이 블로그에서는 무비렌즈(Movielens) 데이터를 이용해서 간단히 구현하는 법에 대해서는 다루지 않고, 나중에 추천시스템에 대한 시리즈를 시작하며 다루도록 하겠다.

Algorithms

Surpriselib에서 제공하는 추천 알고리즘들을 간단히 먼저 알아보자.

Name	Description	Base
NormalPredictor	정규분포로 가정한 학습 데이터셋(trainset)의 평점(rating) 분포에서 랜덤하게 샘플링하는 알고리즘.	Random Predict
BaselineOnly	User와 Item의 Baseline을 이용한 평점 예측 알고리즘.	Baseline Only
KNNBasic	기본적인 협업필터링(Collaborative Filtering) 알고리즘.	Knn Inspired Algorithm
KNNWithMeans	기본적인 협업필터링(Collaborative Filtering) 알고리즘, 추가적으로 평균값을 더해준다.	Knn Inspired Algorithm
KNNWithZScore	기본적인 협업필터링(Collaborative Filtering) 알고리즘, 추가적으로 z-score 분포를 적용한다.	Knn Inspired Algorithm
KNNBaseline	기본적인 협업필터링(Collaborative Filtering) 알고리즘, 추가적으로 baseline을 더해준다.	Knn Inspired Algorithm
SVD	특이값 분해(SVD) 알고리즘, 넷플릭스 Prize에서 Simon Funk에 의해서 유명해짐.	Matrix Factorization Algorithm
SVD++	특이값 분해(SVD++) 알고리즘, 추가적으로 암시적 rating이 더해진다.	Matrix Factorization Algorithm
NMF	Non-negative 행렬분해	Matrix Factorization Algorithm

크게는 KNN Inspired Algorithms, Matrix Factorization Algorithms 2가지를 제공하며, 이외에도 SlopeOne, CoClustering 알고리즘을 제공하긴하지만 이 알고리즘들에 대한 설명은 생략하도록 하겠다.

먼저 Baseline이 들어가는 알고리즘들이 동일하게 가지는 Parameter들에 대해서 알아보겠다. 이 패러미터는 어떻게 user의 bias, item의 baseline(기초선)를 구할 것인지를 결정하는 것이다. 더 쉽게 표현하자면, user A는 영화에 대해서 평가할 때 다른 사람보다 후해서 일반적으로 4점으로 평가받는 영화에도 5점을 준다면 user A의 baseline는 +1이 되는 것이다. item의 경우도 마찬가지로 같은 이치로 baseline을 구할 수 있다. 여기서 항상 기준이 되는 것은 global mean(전체 평점 평균)이 된다. 코드로 확인하면 훨씬 간단명료하다. 아래에서 코드를 통해서 자세히 살펴보자.

Baseline estimates configuration

# 밑에서 공통으로 사용되는 변수들
from recsys.models.surprise.helper import make_dataset
dataset = make_dataset()
trainset = dataset.build_full_trainset()
global_mean = trainset.global_mean
bu = np.zeros(trainset.n_users)
bi = np.zeros(trainset.n_items)

SGD

reg = 0.02 # reg: 정규화 가중치
learning_rate = 0.005 # learning_rate: 최적화를 위한 스탭 사이즈
n_epochs = 20 # n_epochs: 최적화 반복 횟수

def bsl_option_is_sgd():
    for dummy in range(n_epochs):
        for u, i, r in self.trainset.all_ratings():
            err = (r - (global_mean + bu[u] + bi[i]))
            bu[u] += lr * (err - reg * bu[u])
            bi[i] += lr * (err - reg * bi[i])
    return bu, bi

ALS

reg_i = 10 # reg_i: 상품에 대한 가중치
reg_u = 15 # reg_u: 유저에 대한 가중치
n_epochs = 10 # n_epochs: 최적화 반복 횟수

def bsl_option_is_als():
    for dummy in range(n_epoch):
        for i in trainset.all_items():
            dev_i = 0
            for (u, r) in trainset.ir[i]:
                dev_i += r - global_mean - bu[u]

            bi[i] = dev_i / (reg_i + len(trainset.ir[i]))

        for u in trainset.all_users():
            dev_u = 0
            for (i, r) in trainset.ur[u]:
                dev_u += r - global_mean - bi[i]

            bu[u] = dev_u / (reg_u + len(trainset.ur[u]))
    return bu, bi

아래의 코드처럼 사용하면된다.

bsl_options_als = {
    'method': 'als',
    'n_epochs': 5,
    'reg_u': 12,
    'reg_i': 5
}
algo = surprise.BaselineOnly(bsl_options=bsl_options_als)

bsl_options_sgd = {
    'method': 'sgd',
    'n_epochs': 5,
    'learning_rate': 0.01,
    'reg': 0.01
}
algo = surprise.BaselineOnly(bsl_options=bsl_options_sgd)

그 다음으로는 KNN Inspired Algorithms같은 경우에 KNN, 즉 Target item A와 비슷한 혹은 Target user A와 비슷한 K개의 item or user를 “어떻게” 찾을것인가? 하는 것을 결정하는 Similarity measure configuration에 대해서 알아보도록 하겠다.

Similarity measure configuration
- MSD(default)
  - Default값은 평균제곱차이(Mean Squared Difference) 유사도로 설정되어있다. 아래의 수식에서 I_uv은 사용자 u, v가 모두 평가한 아이템 집합을 의미한다. |I_uv|는 그 집합에 속한 원소들의 개수, 즉, 두명의 사용자가 공통적으로 평가한 아이템들의 총 개수를 의미한다(이하 다른 metric에서도 동일하게 적용된다). 당연히 같은 영화(아이템)에대한 평점이 모두 같으면 총합이 0이 되어서 비슷한 사용자라는 의미이며, 다를수록 값은 커지므로 서로 다른 사용자라는 의미가된다. (아래에서도 다 공통된 점이지만, 사용자와 아이템은 argument로 들어온 sim_options에서 user_based가 True거나 False인 경우에 따라서 switch될 수 있다.)
  $$ {msd}(u, v) = \frac{1}{\lvert I_{uv}\rvert} \cdot \sum\limits_{i \in I_{uv}}{(r_{ui} - r_{vi})^{2}} $$
- Cosine
  - Cosine은 흔하게 사용되는 Metric이므로 자세한 설명은 생략하겠다. 아래의 수식에서 볼 수 있듯이 여전히 비슷한 사용자(or 아이템)을 찾을 때는 교집합안에서만 비교를 하게된다는 점을 알 수 있다.
  $$ {cosine\ sim}(u, v) = \frac{ \sum\limits_{i \in I_{uv}} r_{ui} \cdot r_{vi}} {\sqrt{\sum\limits_{i \in I_{uv}} r_{ui}^2} \cdot \sqrt{\sum\limits_{i \in I_{uv}} r_{vi}^2} } $$
- Pearson
  - Pearson은 두 벡터의 상관계수를(pearson correlation coefficient)를 말한다. cosine과 비슷한데, 차이점은 r에서 그 사용자의 평균을 빼줘서 user별로 가지는 성격은 상대적으로 제거한 방식의 metric으로 볼 수 있다.
  $$ {pearson\ sim}(u, v) = \frac{ \sum\limits_{i \in I_{uv}} (r_{ui} - \mu_{u}) \cdot (r_{vi} - \mu_{v})} {\sqrt{\sum\limits_{i \in I_{uv}} (r_{ui} - \mu_{u})^2} \cdot \sqrt{\sum\limits_{i \in I_{uv}} (r_{vi} - \mu_{v})^2} } $$
- Pearson baseline
  - Pearson-baseline은 pearson에서 평균을 빼준것과는 달리 baseline에서 예측한 baseline값을 빼준다.
  $$ {pearson\ baseline\ sim}(u, v) = \frac{ \sum\limits_{i \in I_{uv}} (r_{ui} - b_{ui}) \cdot (r_{vi} - b_{vi})} {\sqrt{\sum\limits_{i \in I_{uv}} (r_{ui} - b_{ui})^2} \cdot \sqrt{\sum\limits_{i \in I_{uv}} (r_{vi} - b_{vi})^2} } $$
  - 이 유사도를 사용할 때는 Shrinkage(default 100)라는 패러미터가 하나 더 존재하는데, 역할은 평점 원소의 갯수를 이용해서 정규화하여 overfitting을 피하도록 도와주는 것이다.
  $$ \frac{\lvert I_{uv}\rvert - 1}{\lvert I_{uv}\rvert - 1 + {shrinkage}} \cdot {pearson\ baseline\ sim} $$

아래의 코드처럼 사용하면된다.

sim_options = {
    'name': 'msd', # 사용할 유사도 이름. ['cosine', 'pearson_baseline', 'pearson']
    'user_based': True, # user를 base로 할것인지 item을 base로 할 것인지 결정.
    # u, v간 교집합 원소 최소 갯수를 설정한다. 이 경우는 5개 이상의 공통된 아이템(or 사용자)가
    # 존재하면 유사도를 계산하지만, 그 미만의 경우에는 sim(u, v) == 0로 설정한다.
    'min_support': 5,
    'shrinkage': 0, # 이 패러미터는 pearson_baseline을 사용할 경우에만 해당된다.
}
algo = surprise.KNNBasic(sim_options=sim_options)

이제 이 블로그의 본래 목적이었던 각 추천 알고리즘에 대해서 살펴보도록 하자.

NormalPredictor

이 알고리즘은 위에서 설명한 그대로다. 아래처럼 최대가능도 방법(Maximum Likelihood Estimation)을 이용하여 평균과 표준편차를 구한다.

$$ \hat{\mu} = \frac{1}{\lvert R_{{train}}\rvert} \sum\limits_{r_{ui} \in R_{{train}}} r_{ui} \\ \hat{\sigma} = \sqrt{\sum\limits_{r_{ui} \in R_{{train}}} \frac{(r_{ui} - \hat{\mu})^{2}}{\lvert R_{{train}}\rvert}} \\ $$

그렇게 나온

$$ \mathcal{N}(\hat{\mu}, \hat{\sigma}) $$

분포에서 랜덤하게 샘플링한 결과로

$$ \hat{r_{ui}} $$

를 구하게 되는 알고리즘이다.

BaselineOnly

역시 간단한 알고리즘이다. 위에서 이미 baseline을 구하는 법은 설명되어 있으니 생략하고 수식을 보게되면 예측 평점은 단순한 산수의 결과란 것을 알 수 있다. 여기서 평균은 전체 평점의 평균(global_mean)을 의미한다.

$$ {\hat{r}}_{ui} = b_{ui} = \mu + b_{u} + b_{i} $$

KNN Inspired Algorithms

이 알고리즘들을 설명하기 전에 앞서 Knn inspired algorithms들의 공통되는 사항들을 알려주겠다.

패러미터로는 k, mink, simoptions 3가지는 동일하게 요구한다.
만약 누구에게도 한번도 rating을 받지 못한 영화에 대해서는 default로 전체 평점 평균(global mean)이 적용되게 된다.

KNNBasic

이제 KNN Inspired algorithms들을 살펴보자. 첫 번째는 가장 기본이되는 KNNBasic이다. 수식에서 sim은 우리가 argument로 넣게되는 sim_options의 name에 해당하는 유사도 알고리즘을 의미한다(이하 알고리즘에서도 동일함). 아래의 식을 먼저 살펴보자.

$$ \hat r_{ui} = \frac{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)\ \cdot r_{vi}}{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)} $$

default setting에 해당하는 user_based:True라고 가정하고 설명하자면, 우리는 사용자 U가 아직 보지않은 영화 i에 대해서 평가하게될 예측 점수를 구하고 싶은 것이다. 순서는 아래와 같다.

우리는 우선 사용자 U와 유사한 유저를 k명만큼 찾는다. 여기서 유사하다고 판단하는 기준이 되는 유사도는 우리가 설정해주는 것이다(msd, cosine, pearson, pearson_baseline).
- 여기서 주의할 점은 k는 최대치일뿐 보장되지 않는다. 만약 유사도가 음수인 경우에는 그 사람의 데이터를 사용하는 것이 말이 안되게돼서 제외하게 되기 때문이다(surpriselib에서 이렇게 설명하고 있다).
이렇게 찾은 k명의 유사 사용자들이 영화 i에 대해 평가한 평점들을 가중합을 하고, normalization해준다. 여기서 좀 더 가까운 사람의 sim(u, v)가 더 높게 되므로, 그 사람이 평가한 i에 대한 평점이 더 큰 가중치를 갖게되는 것을 알 수 있다.

KNNwithMeans

KNNBasic과 차이점은 k명의 유사 사용자들이 영화 i에 대해 평가한 평점들을 그대로 가중합하지않고,

$$ (r_{v \in k, i} - \mu_{v \in k}) $$

를 가중합하게 된다. 그리고 최종적으로는 우리가 영화 i에대해 예측하려는 사용자 U의 평균을 더해주는 방법으로 사용자 U의 특성을 좀 더 부가하는 방법을 쓰고 있다. 예를들어 U는 원래 평점을 조금 낮게주는 스타일이어서 정말 재밌다고 느끼는 영화에도 4점을 준다고 가정해보자. 이 경우에 k명의 유사 유저들이 영화 i에 대해 다 5점을 줬단 이유로 5점에 가까운 예측 값이 나오게 된다면 문제가 발생할 수 있게 되는 것이다. KNNwithMeans에서는 이런 경우를 조금 더 방지할 수 있게 된다.

아래의 전체 공식을 보면 좀 더 명료하다.

$$ \hat r_{ui} = \mu_{u} + \frac{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)\ \cdot (r_{vi} - \mu_{v})}{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)} $$

KNNwithZScore

이 알고리즘은 KNNwithMeans와 흡사하지만 조금 더 나아간 버젼이긴하지만, RMSE와 같은 평가기준으로 평가했을 때 성적은 보장되지는 않는다 어쨋든 순서는 아래와 같다.

영화 i에 대한 k 유사 유저들의 평점에서 각 k 유사 유저의 평균을 빼주고 표준편차를 나눠준다.
다시 우리의 타겟 사용자 U의 표준편차를 곱하고, 평균은 더해준다.

$$ \hat r_{ui} = \mu_{u} + \sigma_{u} \frac{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)\ \cdot (r_{vi} - \mu_{v})/\sigma_{v}}{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)} $$

KNNBaseline

마지막으로 KNNBaseline이다. KNNwithMeans랑 매우 유사한데 차이점은 평균대신 Baseline(위에서 이미 구하는 법은 설명했으니 궁금하신 분은 확인하면 된다)을 빼주고, 사용자 U의 Baseline을 더해주는 방식이다. 위의 알고리즘들과 parameter상의 한가지 차이점은 bsl_options도 추가된다는 점이다.

$$ \hat r_{ui} = b_{ui} + \frac{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)\ \cdot (r_{vi} - b_{vi})}{\sum\limits_{v\in N_{i}^{k}(u)}\ sim(u, v)} $$

MatrixFactorization

나머지 행렬분해(Matrix Factorization)에 해당하는 알고리즘들은 복잡하여 자세히 설명하는 것은 포기하고, 간단한 내용만 소개하고자 한다. 공식과 같은 자세한 설명은 링크에서 확인하시길 바란다. 필자도 해당 사이트의 내용을 참고해서 작성하였음을 미리 밝힌다.

Matrix Factorization 방법은 다음 오차 함수를 최소화하는 요인 벡터를 찾아내게된다.

$$ R \approx PQ^{T} $$

여기에서

$$ R \in R^{m\times n} : {m\ 사용자와\ n\ 영화의\ 평점\ Matrix} \\ P \in R^{m\times n} : {m\ 사용자와\ k\ 요인의\ 관계\ Matrix} \\ Q \in R^{m\times n} : {n\ 영화와\ k\ 요인의\ 관계\ Matrix} \\ $$

를 의미한다.

SVD 방법은 행렬분해를 푸는 방법 중 하나이며, 다음과 같은 오차 함수를 갖는다.

$$ R = U\Sigma V^{T} $$

이 식에서

$$ U \in m\times m {크기의\ 행렬로\ 역행렬이\ 대칭인\ 행렬} \\ \Sigma \in m\times n {크기의\ 행렬로\ 비대각\ 성분은\ 0} \\ V \in n\times n {크기의\ 행렬로\ 역행렬이\ 대칭인\ 행렬} \\ $$

$\Sigma$의 대각 성분을 특이치(Singular value)라고 부르며, 전체 중에서 가장 큰 값 k개의 특이치를 사용하여(Truncated SVD), 다음과 같은 행렬을 만들 수 있다.

$\hat U$는 값이 가장 큰 k개의 특이치에 대응하는 k개의 feature만을 남긴 $m\times k$크기의 행렬
$\hat \Sigma$는 값이 가장 큰 k개의 특이치에 대응하는 k개의 feature만을 남긴 $k\times k$크기의 행렬
$\hat V$는 값이 가장 큰 k개의 특이치에 대응하는 k개의 feature만을 남긴 $k\times n$크기의 행렬

이렇게 조합한 행렬은 아래와 같은 유사 행렬이 된다.

$$ \hat U \hat \Sigma \hat V^{T} = \hat R \approx R $$

하지만 실제로 평점 행렬은 0이 많은 sparse 행렬이어서 SVD를 바로 적용하기는 힘들다. 그래서 Surpriselib에서의 Matrix Factorization 알고리즘들의 Basic Form은 아래처럼 되어있다.

$$ \hat r_{ui} = \mu + b_{u} + b_{i} + q_{i}^{T}p_{u} $$

이 링크에서도 같은 이야기를 하고 있는데, SVD는 missing value가 많은 경우에는 NMF보다는 좋은 결과를 내기 어려울 수 있다는 점을 알아두자.

Conculusion

필자가 회사에서 추천시스템을 구축하는 일을 하면서 Surpriselib을 최초에 사용한 것은 baseline모델로써 대략적인 방향을 잡기위해서였다. 결국은 회사에서 실제 프로젝트로 진행하면 회사의 아이템에 최적화된 모델을 직접 만들어야하기 때문이다. 어쨋든 Surpriselib에서 제공하는 알고리즘들을 사용해보고 간단하게 movielens 데이터로 toy model로써의 추천시스템을 만들기에는 시간을 아낄 수 있고, 전체적인 감을 잡기에도 매우 좋기때문에 누구든 추천시스템에 처음 뛰어든 사람이라면 추천한다.

앞으로 추천시스템에 대해서는 간단한 Tutorial 방식으로 블로그를 쓸 예정이니, 관심이 있으신 분들은 공유를 해주시거나 자주 들려주시면 정말 큰 힘이 될 것 같다!

부족한 내용 끝까지 읽어주셔서 정말 감사합니다! 궁금한 점이 있거나 부족한 점을 발견했다면 댓글로 남겨주시면 고맙겠습니다!