Recommender System

추천 시스템

추천 시스템(recommender system)이란, 누적된 기록 등을 기반으로 사용자(user)가 선호하는 상품(item)을 예측하는 시스템이다.

파이썬의 surprise 패키지는 다양한 추천시스템 알고리즘을 제공한다.

# 먼저 설치가 필요하다
!pip install surprise
import surprise

평점 데이터

surprise 패키지에서는 MovieLense라는 영화 추천 웹사이트의 데이터를 샘플 평점 데이터로 제공한다. MovieLense의 데이터 중 10만개의 샘플데이터셋을 다음과 같이 로드한다.

data = surprise.Dataset.load_builtin('ml-100k')

이 데이터를 데이터프레임으로 변환하면 다음과 같다.

df = pd.DataFrame(data.raw_ratings, columns=["user", "item", "rate", "id"])
del df["id"]
df.head(10)

user 열은 사용자 아이디, item 열은 상품 아이디, rate 열은 각 행의 사용자가 영화에 대해 준 평점에 해당한다. 여기서 볼 수 있듯이, 추천 시스템은 사용자아이디와 상품아이디라는 두 개의 카테고리 입력과 평점 출력을 가지는 예측 시스템 이다.

위 데이터프레임을 피봇테이블로 만들면 x축이 상품, y축이 사용자인 평점 행렬(rate matrix) $R$ 이 된다. 평점행렬의 일부를 살펴보면 다음과 같이 평점데이터가 일부 위치에만 존재하는 sparse matrix임을 알 수 있다.

df_table = df.set_index(["user", "item"]).unstack()
df_table.iloc[212:222, 808:817].fillna("")

평점행렬의 빈칸을 흰색, 점수를 검은색으로 시각화하면 다음과 같다.

plt.imshow(df_table)
plt.grid(False)
plt.xlabel("item")
plt.ylabel("user")
plt.title("Rate Matrix")
plt.show()

추천 시스템 알고리즘

추천시스템은 두 개의 카테고리값 입력에 대한 하나의 실수 출력값을 예측해내는 회귀모형이지만, 여러가지 방법을 통해 예측성능을 향상시키고 있다. 추천시스템에서 사용되는 알고리즘들은 다음과 같다.

1. 베이스라인 모형
2. Collaborative Filtering
   • 2-1. Neighborhood Models
     • User-based CF
     • Item-based CF
   • 2-2. Latent Factor Models
     • Matrix Factorization
     • SVD
   • Content-Based Recommendation
3. Content-Based Recommendation

1) 베이스라인 모형

baseline_model = surprise.BaseLineOnly(bsl_options={}, verbose=True)

베이스라인 모형(baseline model)은 사용자 아이디 $u$, 상품아이디 $i$ 라는 두 카테고리 입력값에서 평점 $r_{ui}$ 의 예측치 $\hat{r}_{ui}$ 를 예측하는 가장 단순한 회귀분석모형으로 다음과 같이 사용자와 상품 특성에 의한 평균 평점의 합으로 구한다. $\mu$ 는 전체 평점의 평균, $b_u$ 는 동일한 사용자에 의한 평점 평균값, $b_i$ 는 동일한 상품에 대한 사용자들의 평점 평균값이다.

$$\hat{y}_{ui} = \mu + b_u + b_i$$

베이스라인 모형은 오차함수를 최소화하는 것을 목적으로 한다.

$$\sum_{r_{ui}\in R_{train}}(r_{ui} - (\mu + b_u + b_i))^2$$

여기서 $R_{train}$은 트레이닝을 위한 데이터셋을 의미한다.

과최적화를 피하기 위해 다음처럼 정규화(regularization) 항을 추가할 수도 있다.

$$\sum_{r_{ui}\in R_{train}}(r_{ui} - (\mu + b_u + b_i))^2 + \lambda (b_u^2 + b_i^2)$$

surprise 패키지는 오차함수를 최소화하기 위해 다음과 같은 두 가지 최적화 알고리즘을 제공한다. 알고리즘을 선택할 때는 method 인수를 사용한다. 선택한 알고리즘에 따라 나머지 최적화인수도 설정해야 한다.

• SGD (Stochastic Gradient Descent)의 인수
  • reg : 정규화 가중치. 디폴트는 0.02
  • learning_rate : 최적화 스텝사이즈. 디폴트는 0.005
  • n_epochs : 최적화 반복 횟수. 디폴트는 20
• ALS(Alternating Least Squares)의 인수
  • reg_i: 상품에 대한 정규화 가중치. 디폴트는 10
  • reg_u: 사용자에 대한 정규화 가중치. 디폴트는 15
  • n_epochs: 최적화 반복횟수. 디폴트는 10

모형 사용법

베이스라인 모형을 비롯한 surprise 패키지 모형을 사용하기 위해서는 다음 순서를 거친다.

1. 데이터셋의 split, folds 메서드를 사용해 K-Folds 트레이닝셋과 테스트셋을 만든다.
2. 모형알고리즘 객체를 생성한다.
3. 모형 알고리즘 객체의 train메서드와 트레이닝셋으로 모수를 추정한 후, test 메서드로 테스트셋에 대한 예측을 실시한다.
4. accuracy 서브패키지의 성능평가함수를 사용해 예측 성능을 계산한다.

추천성능 평가기준

accuracy 서브패키지에서는 다음과 같은 추천성능 평가기준들을 제공한다. 아래 식들에서 $\hat{R}$ 은 테스트 셋을 의미한다.

• RMSE(Root Mean Squared Error)

$$\text{RMSE} = \sqrt{\frac{1}{|\hat{R}|}\sum_{\hat{r}_{ui}\in \hat{R}}(r_{ui}-\hat{r}_{ui})^2}$$

• MAE(Mean Absolute Error

$$\text{MAE} = \frac{1}{\hat{R}}\sum_{\hat{r}_{ui}\in \hat{R}}|r_{ui}-\hat{r}_{ui}|$$

• FCP(Fraction of Concordant Pairs)

$$\text{FCP} = \frac{\text{number of concordant pairs}}{\text{number of discordant pairs}}$$

회귀분석에서 $i$번째 데이터와 $j$번째 데이터에 대해 실제 데이터 $y_i, y_j$ 와 예측데이터 $\hat{y_i}, \hat{y_j}$ 사이의 증가 방향이 같으면 concordant pair라고 한다.

$$\text{sign}(y_i-y_j) = \text{sign}(\hat{y_i}-\hat{y_j})$$

우선 RMSE 평가기준에 따라 베이스라인 모형의 성능을 평가해보자.

from surprise.model_selection import KFold

bsl_options = {
    'method': 'als',     # method 인수에서 최적화 알고리즘을 'ALS'로 지정
    'n_epochs': 5,
    'reg_u': 12,
    'reg_i': 5
}
algo = surprise.BaselineOnly(bsl_options) # 베이스라인 모형 생성

np.random.seed(0)
acc = np.zeros(3)
cv = KFold(3)
for i, (trainset, testset) in enumerate(cv.split(data)):
    algo.fit(trainset)
    predictions = algo.test(testset)
    acc[i] = surprise.accuracy.rmse(predictions, verbose=True)
acc.mean()           # accuracy 서브패키지의 rmse 평가기준 사용

model_selection 서브패키지의 cross_validate 명령을 사용하면 위 코드를 아래처럼 짧게 줄이면서도 다양한 평가기준으로 성능을 평가할 수 있다.

surprise.model_selection.cross_validate(algo, data)

2) Collaborative Filter

CF(Collaborative Filter) 방법은 모든 사용자의 데이터를 균일하게 사용하는 것이 아니라 평점행렬이 가진 특정한 패턴을 찾아서 이를 평점 예측에 사용하는 방법이다. CF 방법으로 만들 수 있는 모형은 다음 두 가지가 있다:

1. Neighborhood 모형
   • 사용자나 상품 기준으로 평점의 유사성을 살핌
2. Latent Factor 모형
   • 평점행렬의 수치적 특징을 이용

(1) Neighborhood 모형

Neighborhood 모형은 Memory-based CF라고도 한다. 특정 사용자의 평점을 바로 예측하는 것이 아니라, 해당 사용자와 유사한 사용자에 대해 가중치를 주어 계산해낸다.

평점행렬에서 유사한 사용자정보, 즉 행벡터의 유사도를 기반으로 빈 데이터를 계산하는 방법을 사용자기반 (User-based) CF 라고 하며, 특정 상품에 대해 사용자가 준 점수, 즉 평점행렬의 열벡터끼리의 유사도에 따라 해당 상품의 빈 데이터를 예측하는 방법을 상품기반(item-based) CF 라고 한다.

유사도 계산

사용자 특성벡터 혹은 상품특성벡터의 유사도를 비교하기 위한 기준도 여러가지가 있다. surprise 패키지가 제공하는 유사도 기준은 다음과 같다.

• 평균제곱차이 유사도 (Mean Squared Difference Similarity)
• 코사인 유사도 (Cosine Similarity)
• 피어슨 유사도 (Pearson Similarity)
• 피어슨-베이스라인 유사도 (Pearson-Baseline Similarity)

- 평균제곱차이 유사도 (Mean Squared Difference Similarity)

일단 다음과 같이 msd(Mean Squared Difference)를 계산한다. msd는 유클리드거리의 제곱에 비례하는 값이다.

• 사용자 $u$ 와 $v$ 벡터 간의 msd

  $$\text{msd}(u,v) = \frac{1}{|I_{uv}|}\cdot \sum_{i\in I_{uv}}(r_{ui}-r_[vi])^2$$

  • $I_{uv}$ : 사용자 $u$ 와 $v$ 모두에 의해 평가된 상품의 집합

  • $|I_{uv}|$ : 사용자 $u$ 와 $v$ 모두에 의해 평가된 상품의 수

• 상품 $i$ 와 $j$ 벡터 간의 msd

  $$\text{msd}(i,j) = \frac{1}{|U_{ij}|} \cdot \sum_{u\in U_{ij}}(r_{ui}-r_{ui})^2$$
  • $U_{ij}$ : 상품 $i$ 와 $j$ 모두를 평가한 사용자의 집합
  • |$U_{ij}$| : 상품 $i$ 와 $j$ 모두를 평가한 사용자의 수

유사도는 이렇게 계산된 msd 값과 반비례관계에 있다. 즉 거리가 멀수록 유사도는 떨어진다. msd값이 0이 되는 경우를 대비해 1을 더해준 후 역수를 취해준 값이 유사도가 된다.

$$\text{msd_sim}(u,v) = \frac{1}{\text{msd}(u,v)+1}$$ $$\text{msd_sim}(i,j) = \frac{1}{\text{msd}(i,j)+1}$$

- 코사인 유사도 (Cosine Similarity)

코사인 유사도(Cosine Similarity)는 두 벡터의 각도에 대한 코사인 값을 말한다. 벡터 $x$ 와 $y$ 사이의 각도 $\theta$ 는 두 벡터의 내적 $x\cdot y$ 와 다음과 같은 관계가 있다.

$$x\cdot y = |x| |y| \cos\theta$$ $$\cos\theta = \frac{x\cdot y}{|x| |y|}$$

• 사용자 $u$ 와 $v$ 벡터 간의 msd $$\text{cosine_sim} (u,v) = \dfrac{\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^2_{vi}}}$$

• 상품 $i$ 와 $j$ 벡터 간의 msd

$$\text{cosine_sim} (i,j) = \dfrac{\sum\limits_{u\in U_{ij}}r_{ui}\cdot r_{uj}}{\sqrt{\sum\limits_{u\in U_{ij}}r_{ui}^2}\cdot \sqrt{\sum\limits_{u\in U_{ij}}r^2_{uj}}}$$

- 피어슨 유사도 (Pearson Similarity)

피어슨 유사도는 두 벡터의 상관계수(Pearson correlation coefficient)로, 다음과 같이 정의한다.

• 사용자 $u$ 와 $v$ 벡터 간의 msd

$$\text{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}}$$

​ - $\mu_u$ : 사용자 $u$ 의 평균 평점

• 상품 $i$ 와 $j$ 벡터 간의 msd

$$\text{pearson_sim}(i, j) = \frac{\sum\limits_{u\in U_{ij}}(r_{ui}-\mu_i)\cdot (r_{uj}-\mu_j)}{\sqrt{\sum\limits_{u\in U_{ij}}(r_{ui}-\mu_i)^2}\cdot \sqrt{\sum\limits_{u\in U_ij}(r_{uj}-\mu_j)^2}}$$

​ - $\mu_i$ : 상품 $i$ 의 평균 평점

- 피어슨-베이스라인 유사도 (Pearson-Baseline Similarity)

피어슨-베이스라인 유사도는 피어슨유사도와 같이 상관계수를 구하지만, 각 벡터의 기댓값을 단순 평균이 아니라 베이스라인 모형에서 예측한 값으로 사용한다.

• 사용자 $u$ 와 $v$ 벡터 간의 msd $$\text{pearson_baseline_sim}(u,v) = \hat{\rho}_{uv}$$

$$= \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}}$$

• 상품 $i$ 와 $j$ 벡터 간의 msd $$\text{pearson_baseline_sim(i,j)} = \hat{\rho}_{ij}$$

$$= \frac{\sum\limits_{u\in U_{ij}}(r_{ui}-b_{ui})\cdot (r_{uj}-b_{uj})}{\sqrt{\sum\limits_{u\in U_{ij}}(r_{ui}-b_{ui})^2}\cdot \sqrt{\sum\limits_{u\in U_ij}(r_{uj}-b_{uj})^2}}$$

피어슨-베이스라인 유사도는 벡터의 차원, 즉 두 사용자나 상품에 공통적으로 있는 평점 원소의 개수를 이용해 정규화하는 shrinkage 를 추가해 사용한다.

$$\text{pearson_baseline_shrunk_sim}(u,v) = \frac{|I_{uv}|-1}{|I_{uv}|-1+\text{shrinkage}} \cdot \hat{\rho}_{uv}$$ $$\text{pearson_baseline_shrunk_sim}(i,j) = \frac{|U_{ij}|-1}{|U_{ij}|-1+\text{shrinkage}} \cdot \hat{\rho}_{ij}$$

surprise 패키지에서 유사도를 설정하는 옵션은 다음과 같다.

• name : 사용할 유사도의 종류를 나타내는 문자열. 디폴트는 MSD

• user_based : True 면 사용자기반, False면 상품기반

• min_support : 두 사용자나 상품에서 공통적으로 있는 평점원소 개수의 최소값

• shrinkage : Shrinkage 가중치. 디폴트는 100

KNN 가중치 예측 방법

일단 유사도가 구해지면 평점을 예측하고자 하는 사용자(혹은 상품)와 유사도가 큰 $k$ 개의 사용자(혹은 상품) 벡터를 사용하여 가중평균을 구해 가중치를 예측한다. 이러한 방법을 KNN(K Nearest Neighbors) 기반 예측 방법이라고 한다.

surprise 패키지는 다음과 같은 3가지 KNN 기반 가중치 예측 알고리즘 클래스를 제공한다.

• KNNBasic

  • 평점들을 단순히 가중평균한다.
  $$\hat{r}_{ui} = \frac{\sum\limits_{v \in N_i^k(u)}\text{sim}(u,v)\cdot r_{vi}}{\sum\limits_{v\in N_i^k(u)}\text{sim}(u,v)}$$

  또는

  $$\hat{r}_{ui} = \frac{\sum\limits_{j \in N_u^k(i)}\text{sim}(i,j)\cdot r_{uj}}{\sum\limits_{j\in N_u^k(j)}\text{sim}(i,j)}$$

• KNNWithMeans

  • 평점들을 평균값을 기준으로 가중평균한다.
  $$\hat{r}_{ui} = \frac{\sum\limits_{v \in N_i^k(u)}\text{sim}(u,v)\cdot (r_{vi}-\mu_v)}{\sum\limits_{v\in N_i^k(u)}\text{sim}(u,v)}$$

  또는

  $$\hat{r}_{ui} = \frac{\sum\limits_{j \in N_u^k(i)}\text{sim}(i,j)\cdot (r_{uj}-\mu_j)}{\sum\limits_{j\in N_u^k(j)}\text{sim}(i,j)}$$

• KNNBaseline

  • 평점들을 베이스라인 모형의 값을 기준으로 가중평균한다.

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

​ 또는

$$\hat{r}_{ui} = b_{ui} + \frac{\sum\limits_{j \in N_u^k(i)}\text{sim}(i,j)\cdot (r_{uj}-b_{uj})}{\sum\limits_{j\in N_u^k(j)}\text{sim}(i,j)}$$

Neighborhood 모형을 사용하여 추천시스템을 만들고 평가하는 코드는 아래와 같다.

sim_options = {'name': 'msd'} # 평균제곱차이 유사도
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.model_selection.cross_validate(algo, data)

sim_options = {'name': 'cosine'} # 코사인 유사도
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.model_selection.cross_validate(algo, data)

sim_options = {'name': 'pearson'} # 피어슨 유사도
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.model_selection.cross_validate(algo, data)

sim_options = {'name': 'pearson_baseline'} # 피어슨-베이스라인 유사도
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.model_selection.cross_validate(algo, data)

(2) Latent Factor 모형

사용자의 특성벡터나 상품의 특성벡터의 길이는 수천에서 수십억에 달하는 크기가 될 수도 있다.

Latent Factor 모형은 이렇게 긴 벡터를 몇개의 요인벡터로 간략화(approximate)할 수 있다는 가정에서 출발한다. PCA를 사용하면 긴 특성벡터를 작은 수의 차원으로 축소할 수 있는 것처럼 사용자와 상품의 특성도 차원축소할 수 있다.

영화에 대한 평점을 주는 경우, 영화에는 코미디/액션/드라마 등 다양한 장르가 있고 사용자는 그 중 특정한 장르를 선호할 수 있다. 하나의 영화에도 이러한 장르요소가 복합적으로 존재할 수 있기 때문에 하나의 영화에 대한 한 사용자의 평점은, 사용자의 선호장르요인벡터와 영화 자체의 장르요인벡터의 내적으로 표시할 수 있게 된다.

예를 들어 액션을 싫어하고(-1) 코미디(2)나 드라마(3)를 좋아하는 사용자의 장르 요인 벡터는 다음과 같다.

$$p_u^T = (-1, 2, 3)$$

그리고 어떤 영화가 액션요소 2, 코미디요소 1, 드라마요소 1을 갖고 있다면 해당 영화의 장르 요인벡터를 다음과 같이 나타낼 수 있다.

$$q_i^T = (2,1,1)$$

해당 영화에 대한 위 사용자의 평점은 다음과 같을 것이다.

$$r_{ui} = q_i^Tp_u = -1\cdot 2 + 2\cdot 1 + 3\cdot 1 = 3$$

Matrix Factorization

Matrix Factorization 방법은 모든 사용자와 상품에 대해 다음 오차함수를 최소화하는 요인벡터를 찾아낸다. 즉, 다음과 같은 행렬 $P, Q$ 를 찾는다.

$$R \approx PQ^T$$

여기서

• $R \in \R^{m\times n}$ : $m$ 사용자와 $n$ 상품의 평점 행렬
• $P \in \R^{m\times k}$ : $m$ 사용자와 $k$ 요인의 관계 행렬
• $Q \in \R^{n\times k}$ : $n$ 상품의와 $k$ 요인의 관계 행렬

SVD (Singular Value Decomposition)

SVD (Singular Value Decomposition)는 Matrix Factorization 문제를 푸는 방법 중 하나이다.

$m \times n$ 크기의 행렬 $R$ 은 다음과 같이 세 행렬의 곱으로 나타낼 수 있다. 이를 특이치 분해(Singular Value Decomposition) 라고 한다.

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

이 식에서

• $U $ : $m\times m$ 행렬. 역행렬이 대칭행렬
• $\Sigma$ : $m\times n$ 행렬. 비대각 성분이 0
• $V$ : $n\times n$ 행렬. 역행렬이 대칭행렬

$\Sigma$ 의 대각 성분을 특이치라고 하며, 전체 특이치 중에서 가장 값이 큰 $k$개의 특이치만을 사용해 다음과 같이 행렬 $\hat{U}, \hat{\Sigma}, \hat{V}$ 를 만들 수 있다.

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

이 행렬들을 다시 조합하면 원래 행렬과 같은 크기를 가지고 유사한 원소를 가지는 행렬을 만들 수 있다.

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

하지만 실제로 평점행렬은 빈 원소가 많은 sparse 행렬이기 때문에 SVD 를 바로 적용하기 어렵다. 따라서 행렬 $P, Q$ 는 다음과 같은 모형에 대해 오차함수를 최소화하여 구한다.

$$\hat{r}_{ui} = \mu + b_u + b_i + q_i^T p_u$$ $$\sum_{r_{ui}\in R_{train}}(r_{ui}-\hat{r}_{ui})^2 + \lambda (b_i^2+b_u^2 + ||q_i||^2 + ||p_u||^2)$$

%%time
algo = surprise.SVD(n_factors=20)
print(surprise.model_selection.cross_validate(algo, data))