[CS246] RecSys (3) - Collaborative Filtering (CF)

 

 

Collaborative Filtering

Content-based 방법은 다른 user의 정보를 이용하지 않고 item profile을 이용했다. (user profile도 사실상 item profile에서 만들었음). Collaborative Filtering(CF)은 다른 user의 정보를 이용하여 item을 추천해주는 방법이다.

 

이 방법은 item이나 user profile을 만들지 않는다. 대신에 utility matrix의 row/column을 이용한다.

 

user-user collaborative filtering과 item-item collaborative filtering 이렇게 2가지 방법이 존재한다.

User-User Collaborative Filtering

user X의 rating과 유사한 N 명의 다른 user를 찾는다. 이렇게 찾은 N명의 다른 user의 rating을 바탕으로 X의 rating을 추측하는 방법이다.

User-User Collaborative Filtering (Stanford CS246)

Finding Similar Users

The utility matrix (MMDS textbook)

Jaccard similarity

자카드 유사도에서 사용되는 rating은 item-집합이다. (벡터가 아니다.) 

예를 들어 A = {HP1, TW, SW1}, B = {HP1, HP2, HP3}, C={TW, SW1, SW2} 가 된다.

$A$와 $B$의 교집합과 합집합의 크기는 각각 1과 5이므로 자카드 유사도는 $J(A,B)=1/5$이고, 자카드 거리는 $d_J(A,B)=4/5$ 이다.

$A$와 $C$의 경우는 $J(A,C)=2/4=1/2$이고 자카드 거리는 $d_J(A,C)=1/2$ 이다.

 

자카드 유사도에 따르면, A는 B보다 C와 더 유사하다. 그러나 직관적으로는 잘못되어 보인다. A와 B는 HP1이라는 동일한 영화에 높은 평점을 주었지만, A와 C는 TW와 SW1에 대하여 서로 반대의 평점을 주었기 때문이다.

 

Cosine similarity

코사인 유사도에서 사용되는 rating은 점(point)이다. 이 경우 빈칸(no-rating)에 $0$으로 간주하여 코사인 유사도를 계산한다. 위 예시를 이용하면 $A = [4,0,0,5,1,0,0]$, $B=[5,5,4,0,0,0,0]$, $C = [0,0,0,2,4,5,0]$가 된다. 따라서 A와 B, A와 C의 코사인 유사도를 계산하면 다음과 같다.

\[ \cos(A,B) = \cfrac{4 \times 5}{\sqrt{4^2 + 5^2 + 1^2} \sqrt{5^2 + 5^2 + 4^2} } = 0.380 \]

\[ \cos(A,C) = \cfrac{5 \times 2 + 1 \times 4}{\sqrt{4^2 + 5^2 + 1^2} \sqrt{2^2 + 4^2 + 5^2} } = 0.322 \]

(내가 보이게 또이또이하지만) A는 C보다 B에 조금 더 유사하다고 할 수 있다.

 

그러나 코사인 유사도 역시 근본적 문제가 있는데, $0$은 dislike이고, 빈칸(no-rating)이 아니기 때문이다.

 

Pearson correlation coefficient

$S_{xy}$를 $x$와 $y$ 모두 rating 된 item 집합이고, $\overline{r_{x}}$를 X의 평균 rating이라 하자. 그러면 

\[ \text{sim}(x, y) = \cfrac{\sum_{s \in S_{xy}} (r_{xs} - \overline{r_{x}}) (r_{ys} - \overline{r_{y}}) }{ \sqrt{\sum_{s \in S_{xy}} (r_{xs} - \overline{r_{x}})^2} \sqrt{ \sum_{s \in S_{xy}} (r_{ys} - \overline{r_{y}})^2 } } \]

 

상관계수가 의미를 가지려면 $S$의 크기가 많이 커야한다는 문제가 있다.

Rounding the Data: Improving Jaccard similarity

평점이 높은 영화끼리, 낮은 영화끼리 유사도를 가져야 한다. (distinguish between hign and low ratings) (위의 자카드 유사도는 실패했다) 대표적인 방법으로 평점이 낮은 영화는 unrated로 하고(빈칸) 평점이 높은(3,4,5 점) 영화는 1로 표기하는 방법이다. 이렇게 처리한 utility matrix는 다음과 같다.

Rounded Utility Matrix (MMDS textbook)

이 경우에 $J(A,B) = 1/4$이고 $J(A,C)=0$ 이다. 이전 결과보다 나은 유사도를 보여준다.

Normalizing Ratings: Improving Cosine similarity

각 사람별로 평균 평점을 원래 평점에서 빼서 정규화한다. 이렇게 처리한 utility matrix는 다음과 같다.

Normalized Utility Matrix (MMDS textbook)

이 경우 $\cos(A,B) = 0.092$, $\cos(A,C)=-0.559$ 이다. A와 C는 공통 영화에서 반대 경향의 rating을, A와 B는 공통 영화에서 같은 경향의 rating을 주는 것을 잘 반영한다.

Rating Predictions

이제 user간 유사도(또는 거리)를 바탕으로 rating을 예측해보자.

$r_x$: $x$의 rating vector

$N$: $x$와 가장 유사한 $k$명을 포함한 user set. $|N|=k$ 라 하자.

$N'$: $N$의 부분집합이며, item $i$에 실제로 rating한 user set. $|N'| = k'$ 라 하자. 

 

prediction 식은 simple/complex 버전이 있다. 

\begin{align} r_{xi} &= \cfrac{1}{k'} \sum_{y \in N'} r_{yi} \quad \text{(simple version)} \\ r_{xi} &= \cfrac{\sum_{y \in N'} \text{sim}(x,y) \cdot r_{yi} }{\sum_{y \in N'} \text{sim}(x,y) } \quad \text{(complex version)} \end{align}

 

 

반응형

Item-Item Collaborative Filtering

item $i$에 대하여, similar item을 찾는 방법이다.

(user-user CF와 마찬가지로) item $i$의 rating을 유사한 item의 rating으로부터 예측하는 방법이다.

similarity metrix은 user-user와 같은 유사도를 이용하고, prediction function은 아래를 이용한다.

\[ r_{xi} = \cfrac{\sum_{j \in N(i:x)} \text{sim}(i,j) \cdot r_{xj} }{\sum_{j \in N(i:x)} \text{sim}(i,j)} \]

 

$r_{xi}$: user $x$가 item $i$에 rating한 값

$N(i;x)$: $x$가 rating한 item 중에서 $i$와 유사한 item 집합

$\text{sim}(i, j)$: 두 item $i$와 $j$의 유사도

 

Item-Item vs. User-User

일반적으로 item-item collaborative filtering이 user-user 방법보다 더 잘 동작한다.

Why? item은 user보다 단순하고, user는 다양한 취향(multiple taste)을 갖기 때문

item-item similarity가 더 reliable하다. item은 simple term을 갖기 때문이다. (e.g. one genre)

user는 다양한 취향을 갖기 때문에 similarity 계산(혹은 더 좋은 유사도)이 어렵다.

Pros and Cons: Collaborative Filtering

Pros

feature 또는 profile을 만들지 않고도 추천해줄 수 있다.

Cons

충분히 많은 user가 필요하다 (cold start)

새롭거나 인기없는(new or unpopular) item은 rating이 없기 때문에 절대 추천되지 않는다 (first rater)

특정 취향을 가진 유저에게는 절대 추전되지 않는 item이 존재한다. (popularity bias)