Basic Collaborative Filtering Models

추천 시스템의 기본적인 Collaborative Filtering 모델들을 살펴보고자 한다.

Collaborative Filtering

Collaborative Filtering (이하 CF)은 한국어로 협업 필터링이라 하는데, 여러 유저의 활동들을 이용한 추천 방법론이다.

가장 간단한 예를 들자면 나와 비슷하게 상품을 구매하거나 영화/드라마를 시청한 유저들을 골라서

해당 유저들이 사용한 아이템을 추천하는 방식이다. 

 

CF는 유저들끼리의 비슷하거나 유사한 정도인, 유사도를 활용한 User-based Collaborative Filtering와 아이템들의 유사도를 활용한 Item-based Collaborative Filtering이 있다. 위 두 모델은 Charu C. Aggarwal의 Recommender Systems: The Textbook에는 Neighborhood-Based Collaborative Filtering이라고 나와있다. 이외에도 Model-based CF가 있는데 Latent Factor Model이 가장 대표적이다. 이는 User와 Item을 latent vector로 표현하는 방법으로 SVD (Singular Value Decomposition)이나 PCA (Principal Component Analysis), Matrix Factorization 등으로 표현한다. 

 

여기서는 User-based Collaborativg Filtering, Item-based Collaborativg Filtering, Matrix Fatorization(MF)-based Rating Prediction, 그리고 implicit interactions에 대한 MF인 Bayesian Personalized Ranking (BPR)을 알아본다.

 

User-based Collaborative Filtering

User-based CF에서는 user-user similarity를 이용하여 해당 유저에게 유저가 좋아할만한 아이템을 추천한다.

Charu C. Aggarwal의 Recommender Systems: The Textbook에서 가져온 예시로 알아보고자 한다.

 

 

 

 

Table 2.1의 row는 user이고, column은 item이다.

별점이나 점수는 보통 5점, 10점, 7점, 100점 등 다양한 단위가 쓰인다. 

위 내용에서는 7점 만점에 최저점이 1점이라고 가정한다.

 

User 1과 3의 Cosine similarity는 0.956이다. 

?를 0으로 잡고 User 1의 vector를 (7, 6, 7, 4, 5, 4), User 3의 vector를 (0, 3, 3, 1, 1, 0)으로 두고

User 3가 사용하지 않은 Items 1, 6을 제외한 cosine similarity를 계산하면 다음과 같다.

 

Cosine similarity

 

Cosine(1,3) = $\frac{ 6  *  3 +  7  *  3 +  4  *  1 + 5  *  1}{ \sqrt{ 6^2  +  7^2  +  4^2  +  5^2 } \cdot \sqrt{ 3^2  +  3^2  +  1^2  +  1^2 } } = 0.956$

 

Cosine similarity 외에도 추천에서 많이 사용하는 유사도는 Pearson Correlation과 Jaccard Index =  Jaccard similarity coefficient가 있다. 

 

 

Pearson Correlation의 경우는 다음과 같다. 

 

Pearson(1,3) = $\frac{ (6 - 5.5)*(3 - 2) + (7 - 5.5)*(3 - 2) + (3 - 5.5)*(1 - 2) +(5 - 5.5)*(1 - 2) }{ \sqrt{ {1.5}^{2} + {1.5}^{2}  + {-1.5}^{2} + {-1.5}^{2}  }  \cdot   \sqrt{ 1^2 + 1^2 + {(-1)}^{2} + {(-1)}^{2} } } = 0.894$

 

Jaccard Index의 경우는 다음과 같다.

 

Jaccard(1, 3) =  $\frac{|\{ 2, 3, 4, 5 \}|}{| \{ 1, 2, 3, 4, 5, 6 \} |}$ = 0.8333

 

• Cosine sim은 가장 무난한 지표로 -1과 1사이의 값으로 정규화 된 값이다.
• Pearson Corr은 개별 유저의 별점 편향성을 제거할 수 있고, -1과 1사이로 정규화된 값이다. 별점 편향성이란, 영화를 예로 들었을 때 유저 A는 대부분의 영화를 재밌게 보기 때문에 대부분을 3.5점 이상 주어서 4.5점 이상은 되어야 좋은 영화지만, 유저 B는 시네필이나 평론가와 같은 스타일이고 점수가 낮든 높은 상관 없이 두루두루 보기 때문에 평균이 2.5점이며 3.5점만 되어도 좋은 영화다. 이렇듯 두 유저 사이의 별점 경향성은 다를 수 있는데 Pearson corr는 평균을 빼주기 때문에 이런 편향성을 제거할 수 있다. 하지만 아이템을 1개만 사용하는 등 Cold-Start에 가까운 user들은 계산할 수 없다는 단점이 있다.
• Jaccard index는 0과 1사이의 값으로, 두 유저의 사용 아이템 중 가장 많이 겹치는 경우를 리턴한다. 별점이나 점수 등의 구체적인 사항이 아닌 클릭이나 구매 등의 implicit feedbacks에 대해서도 적용할 수 있다.

추가적으로 위 세 지표 모두 클수록 더 유사하며, 낮을수록 유사하지 않다는 의미를 지닌다.

 

 

위에서 별점 편향성에 대해서 이야기했는데 Table 2.2 처럼 mean을 빼주는 작업을 수행한 다음 유사도를 계산하는 작업을 수행할 수도 있다. 이런 방법을 적용할지 말지는 추천 시스템을 구축하는 사람이 판단해야 한다.

 

Recommendation by user-user similarity

 

위에서 구한 여러가지 user-user similarity들을 기반으로 추천을 수행하는 방법은 다양하다.

 

추천을 받을 유저 $u$에 대해서,

 

• 유사도가 가장 높은 다른 user의 items 중에서 $u$가 사용하지 않은 아이템을 추천
• 유사도가 가장 높은 $k$ users의 items 중에서 공통된 아이템을 추천
• 유사도를 기반으로 하여 $u$가 사용하지 않은 아이템에 대한 rating prediction을 수행 후 높은 순으로 추천

특히 별점 예측의 경우 5점 만점을 가정할 때, predicted ratings가 3점 이상인 경우만 추천하는 식으로 여러가지 제약조건을 둘 수도 있다.

 

유저 $u$가 item $i$의 매긴 점수를 $r_{u,i}$라고 표기하자.

Sim($u, v$)는 정의한 유사도 함수로 cos sim, Pearson corr, Jaccard index 등 여러가지 함수가 될 수 있다.

그리고 mean-centered rating인 $s_{u,i} = r_{u,i} - {\mu}_{u}$로 정의하고, 이때 ${\mu}_{u}$ 는 유저 $u$의 평균 별점이다.

 

$\mathcal{U}$는 users의 집합이고, $I_u$는 user $u$가 사용한 아이템들의 집합을 표기한다.

 

Neighborhood-based predicted rating of item $i$ for user $u$는 아래와 같이 정의된다.

 

$\hat{r_{u,i}} = {\mu}_{u} + \frac{{\sum}_{v \in {P}_{u}(j)} Sim(u, v) \cdot {s}_{v,j} }{ {\sum}_{v \in {P}_{u}(j)} |Sim(u, v)| } $

 

이때, ${P}_{u}(j)$는 유저 $u$와의 유사도가 낮은 유저들을 걸러낸, 유사도가 높은 유저들의 집합이다.

 

유사도가 0.5 이상인 유저들이라거나, 유사도가 0.5 이상이면서 상위 10명의 유저들이 등 다양한 조건을 둘 수 있다.

 

Table 2.1에서의 예시를 통해서 계산하면 다음과 같다.

 

$\hat{r_{3,1}}$ 은 (7*0.894 + 6*0.939) / (0.894 + 0.939) = 6.49

$\hat{r_{3,6}}$은 (4*0.894 + 4*0.939) / (0.894 + 0.939) = 4

 

아이템 $K$ 개를 추천하는 Top-$K$ 추천 중에서 만약 아이템을 1개만 추천하는 Top-1 케이스라면,

더 예측 점수가 높은 Item 1을, User 3에게 추천하게 된다.

 

 

Item-based Collaborative Filtering

이 방법은 앞서와는 다르게 Item을 기준으로 유사도를 측정하는 방법이다. 

Item을 기준으로 측정한 유사도를 활용하여 유저 $u$에 대한 item $i$의 예측 값인 $\hat{r_{u,i}}$를 구하고

높은 아이템들을 유저 $u$에게 추천하게 된다.

 

다만 차이점이 있다면 여기서는 아이템이 기준이므로, 

mean-centered rating이 $s_{u,j} = r_{u,j} - {\mu}_{j}$로 바뀌게 된다.

 

User가 아닌 Item $j$를 기준으로한 평균을 빼준다.

 

일반 rating을 사용하는 아래 식과,

 

$\hat{r_{u,i}} = \frac{{\sum}_{j \in {Q}_{t}(u)} Sim(j, t) \cdot {r}_{u,j} }{ {\sum}_{j \in {Q}_{t}(u)} |Sim(j, t)| }$

 

 Mean-centred rating을 사용하는 아래의 식 두 가지로 별점 예측이 가능하다.

$\hat{r_{u,i}} = {\mu}_{j} + \frac{{\sum}_{j \in {Q}_{t}(u)} Sim(j, t) \cdot {s}_{u,j} }{ {\sum}_{j \in {Q}_{t}(u)} |Sim(j, t)| }$

 

이때, $ {{Q}_{t}(u)} $는 target item $t$에 대해 별점을 매긴 user $u$들의 집합이다.

 

 

Matrix Factorization Rating Prediction (Latent Factor Model)

 

Figure 1. Matrix Factorization

 

 

Matrix Factorization은 맨 오른쪽의 Users-Items가 있는 User-Item Rating Matrix (or User-Item Interaction Matrix)를 User Factor Matrix와 Item Factor Matrix의 곱으로 분해하는 작업이다.

 

NLP에서 token을 d차원 벡터로 나타내듯이 유저와 아이템도 d차원 벡터로 나타낸다.

그리고 두 벡터, user $i$의 vector ${u}_{i}$와 item $j$ vector ${v}_{j}$ 의 dot product로,

user $i$가 item $j$에 매긴 별점인 ${r}_{ij}$을 $\hat{{r}_{ij}}$로 예측하게 된다.

 

만약 원본 ratings matrix $R$이 $N \times M$이라면 User factor matrix $U$는 $N \times d$가 되고

Item factor matrix $V$는 $M \times d$이 된다. 따라서 $R = U \times V^T$이 된다. 

 

위 기본 모델에다가 전체에 대한 경향성인 $m$, user $i$의 경향성인 $m_i$, item $j$의 경향성인 $m_j$를 도입하여, 

$\hat{{r}_{ij}} = m + m_i  + m_j + {{u}_{i}}^{T} \cdot {v}_{j} $의 형식으로 추론할 수도 있다.

 

 

Bayesian Personalized Ranking (BPR)

BPR은 추천 시스템 분야에서 가장 유명한 논문 중 하나일텐데, implicit feedback에 matrix factorization을 도입한 방법론이다. 기존에는 별점 등의 explicit feedback을 활용한 matrix factorization의 형식이었는데, 여기서는 user를 기준으로 한 positive items과 negative items 개념을 도입한 pair-wise ranking을 통해 user와 item factor matrices를 최적화를 했다.

 

Positive items란 유저가 샀거나, 봤거나, 카트에 담았거나, 클릭하거나 했던 아이템이며 negative items는 유저와 상호작용(interaction)이 없는 아이템이다. Implicit feedback은 positive feedbacks보다 그 종류가 많으며, explicit feedbacks도 binarize해서 1과 0과 같은 implicit feedbacks로 변형할 수 있기에 보다 포괄적이다. 

 

BPR의 가정 중 하나는 positive items가 negative items보다 유저가 더 높은 평가를 주거나, 더 선호하거나 한다는 점이다. 하지만 단순한 0과 1대신 실수 전체의 범위의 값을 지니는 임의의 score를 도입하여 이런 문제를 해결했다.

 

 

Figure 2. BPR

 

Figure 2에서 $ \hat{{x}_{ui}} $는 user $u$가 positive item $i$에 대한 잠재적 score다. Rating이나 확률이 아니다.

$ \hat{{x}_{uj}} $는 user $u$가 negative item $j$에 대한 잠재적 score다.

 

 $\hat{{x}_{uij}} = \hat{{x}_{ui}}  - \hat{{x}_{uj}}$는 pairwise score다.

이 값에 sigmoid 함수를 취해서 확률 값으로 만든다.

이 확률값을 최대로 하도록 loss 함수를 설정하고 SGD로 최적화한다.

 

 

 

 

 

 

References:

Recommender Systems: The Textbook, Charu C. Aggarwal.

Recommender Systems Handbook, Francesco Ricci, Lior Rokach, and Barcha Shapira.

https://developers.google.com/machine-learning/recommendation/collaborative/basics?hl=ko

https://ko.wikipedia.org/wiki/%ED%98%91%EC%97%85_%ED%95%84%ED%84%B0%EB%A7%81

https://tech.kakao.com/2021/10/18/collaborative-filtering/

https://www.blossominkyung.com/recommendersystem/collaborative-filtering

[업스테이지] AI 실전 학습 - Recommender Systems Basic

https://towardsdatascience.com/recsys-series-part-4-the-7-variants-of-matrix-factorization-for-collaborative-filtering-368754e4fab5

https://towardsdatascience.com/recommender-system-bayesian-personalized-ranking-from-implicit-feedback-78684bfcddf6