[추천시스템] 추천시스템(2) - Neighborhood based collaborative filtering

추천시스템(2) - Neighborhood based collaborative filtering

본 포스팅은 Aggarwal의 recommender system을 참고했습니다.

1. 서론

Neighborhood based collaborative filtering 알고리즘은 다른 말로 memory-based algorithm이라고도 부릅니다. 이 알고리즘은 비슷한 유저는 특정 아이템에 비슷한 평점을 준다는 아이디어에 기반합니다. Neighborhood based collaborative filtering는 두가지 타입이 존재합니다.

1.1 User-based collaborative filtering

이 경우에는, 유저 A와 비슷한 유저들의 평점이 유저 A의 추천에 사용됩니다. 유저 A의 각 아이템의 예측 평점은 유저 A가 속하는 동료 집단(peer)의 평점으로 계산됩니다.

• 평점을 예측할 때 이웃 유저를 이용해서 예측함
• 여기서 이웃이란 비슷한 유저를 의미함(평점 행렬의 행)

1.2 Item-based collaborative filtering

타겟 아이템 B에 대해 추천을 하기위한 첫번째 단계는 아이템 B와 비슷한 집단 S를 설정하는 것입니다. 그리고 나서 유저 A에 대해 아이템 B의 평점을 예측하기 위해 집단 S에 속하는 아이템 중 유저 A가 매겻던 아이템의 평점을 이용하는 것입니다. 집단 S에 속하는 아이템 중 유저 A가 과거에 평점을 매겼던 아이템이 있다면 이 아이템들의 가중 평균을 구해서 유저 A의 아이템 B의 평점을 예측하는 것입니다.

• 해당 유저가 과거 평점을 매겼던 이웃 아이템을 대상으로 예측
• 여기서 이웃이란 비슷한 아이템을 의미함(평점 행렬의 열)

1.3 평점 행렬

이번엔 $m \times n$ 평점 행렬(rating matrix) R에 대해 이야기 해보겠습니다. 이 평점 행렬 R은 m명의 유저와 n개의 아이템을 포함합니다. Neighborhood based collaborative filtering은 다음 두 가지 방법 중하나로 표현됩니다.

(1) user-item 조합의 평점 예측

이는 추천시스템에서 간단하고 가장 기본적인 부분입니다. 이 경우 아직 평점이 매겨지지 않은 값을 예측합니다. 예를 들어, 유저 u의 아이템 j인 $r_{uj}$를 예측하는 것입니다.

(2) top k 아이템 혹은 top k 유저 결정

사실 물건을 파는 사람 입장에서는 user-item 조합의 평점 리스트를 보는게 필수는 아닙니다. 그보다는 특정 유저가 흥미 있어할 법한 top k 아이템을 보고 싶어할 것입니다. 혹은 특정 아이템에 대해 가장 관련 있을 법한 top k 유저를 보고 싶어할 것입니다. 둘 중 더 일반적인 것은 top k 아이템 선정입니다. 예전에는 top k 아이템이 더 일반적이었지만 시간이 지나면서 마케팅에 사용하기 위해 top k 유저도 유용해지고 있습니다.

2. 평점 행렬의 성질

앞서 언급했듯이, 우리는 앞으로 평점행렬 R을 다루겠습니다. 평점 행렬 R은 $m\times n$ 행렬이며 m명의 유저와 n개의 아이템을 포함합니다. 따라서 행렬 R의 구성요소는 유저 u가 아이템 j에 대해 평점을 매긴 $r_{uj}$로 구성됩니다. 평점행렬에서 평점이 매겨진 구성요소는 소수에 불과하고 대부분은 평점이 매겨지지 않아서 널값에 해당합니다. 이 때 평점이 매겨진 구성요소는 트레이닝 데이터가 되고, 평점이 매겨지지 않은 데이터는 테스트 데이터에 해당합니다. 이 경우 평점이 매겨지지 않은 값의 열은 타겟 변수가 되는 것입니다. 따라서 추천 문제는 분류나 예측 문제라고 볼 수있는 것입니다. 평점을 매기는 방법은 다음과 같이 나눌 수 있습니다.

• 연속형 평점
• 구간 평점
• 순서 평점
• 이진 평점
• 단일 평점

3. Neighborhood Based Method 로 예측하기

Neighborhood Based Method의 기본 아이디어는 평점 행렬로부터 유저 간 유사성을 사용하거나 아이템간 유사성을 사용하는 것입니다. 이 떄 이웃(neighborhood) 이라는 단어는 유저 또는 아이템의 유사성을 결정할 필요가 있다는 말을 암시합니다. 지금부터는 Neighborhood Based Method를 이용해 유저-아이템 조합에서 평점예측을 어떻게 하는지 알아보겠습니다. 이웃기반 모델은 다음과 같이 두 가지 모델이 있습니다.

(1) User based model

비슷한 유저는 동일한 아이템에 대해 비슷한 평점을 줍니다. 즉, 앨리스와 밥이 과거에 영화 평점을 비슷하게 주었다면, 앨리스가 영화 터미네이터에 준 평점을 이용해 밥의 터미네이터 평점 예측에 활용할 수 있다는 뜻입니다. (밥은 아직 터미네이터를 보지 않은 상태)

(2) Item based model

비슷한 아이템은 동일한 유저에게 비슷한 평점을 받습니다. 즉, 밥이 예전에 본 영화인 에일리언의 평점은 아직 보지 않은 터미네이터 평점 예측에 활용할 수 있다는 뜻입니다.

앞서 추천 문제는 분류나 예측 문제로 볼 수있다고 했습니다. 따라서 Neighborhood Based Method는 머신러닝에서 kNN 방법에 비유할 수 있습니다. 이 때 행렬의 행을 기준으로 이웃을 결정하는 kNN과는 달리 Neighborhood Based Method는 평점 행렬의 행을 기준으로 이웃을 정할 수도 있고, 열을 기준으로 이웃을 정할수 있다는 점에서 kNN과 다릅니다.

3.1. User based neighborhood model

이 방법에서 우리의 타겟 유저의 평점을 계산하기 위해 타겟 유저와 비슷한 유저들을 정의하기 위해 이웃(neighborhood)라는 개념이 사용됩니다. 타겟 유저 $i$의 이웃을 결정하기 위해 다른 유저들의 유사성이 계산됩니다. 이를 위해 우선 각 유저들의 평점간 유사성을 결정하는 함수가 정의 되어야 합니다. 그러나 이 유사성을 계산하는 것은 꽤 까다로운 일입니다. 왜냐하면 평점을 매길때 각 유저별로 서로 다른 스케일을 사용하기 때문입니다. 이를 테면 어떤 유저는 자신이 가장 좋아하는 아이템에 편향되어 있는 사람도 있고, 다른 유저는 가장 싫어하는 아이템에 편향되어 있는 경우도 있기 때문입니다. 게다가 서로 다른 사람들이 서로 다른 아이템에 평점을 부여한다는 점도 어려운 점입니다. 따라서 이러한 이슈들을 다룰 메커니즘이 필요합니다.

m명의 유저들과 n개의 아이템을 다루는 $m\times n$ 평점 행렬 R에 대해 $I_{u}$를 유저 $u$에 의해 마킹된 평점의 아이템 셋이라고 하겠습니다. 이때 $I_{u}$는 $u$번째 행(row)을 의미합니다. 예를 들어, 유저(행) u의 첫번째, 세번째, 다섯번째 아이템의 평점이 표시되어 있고 나머지 아이템은 마킹되어 있지 않을때, $I_{u}$는 다음과 같습니다.

$ I_{u} = \{ 1, 3, 5 \} $

그러므로 유저 u와 유저 v가 동시에 평점을 매긴 아이템 목록은 $I_{u} \cap I_{v}$에 해당합니다. 만약 유저 v가 1, 2, 3, 4 아이템에 평점을 매겼다면 $I_{v} = \{ 1, 2, 3, 4 \}$가 되므로 다음과 같이 표현할 수 있습니다.

$I_{u} \cap I_{v} = \{ 1, 3, 5 \} \cap \{ 1, 2, 3, 4 \} = \{ 1, 3\}$

만약 두 유저간 공통 평점 아이템이 없다면 비어있는 셋이 됩니다. 위와 같이 두 유저간 공통 구매 아이템 셋을 구한 후 두 유저간 이웃과 관련된 계산을 할 수 있습니다.

유저 u 와 유저 v의 유사도를 Sim(u, v)라고 표현할 때, 이를 측정하기 위해서 피어슨 상관계수(Pearson correlation coefficient)를 측정할 수 있습니다. 이를 구하기 위한 첫 단계로 유저 u의 평균 평점을 구합니다.

$\mu = \frac{\sum_{k \in I_{u}} r_{uk} }{| I_{u} |}, u \in \{ 1, \cdots , m \}$

위 식에서 각 유저의 평균 평점을 구할 때는 두 유저의 공통 평점 아이템만을 대상으로 평균 평점을 구해야합니다. 그러나 조금 간단한 가정을 통해 위와 같이 구하기도 합니다. 그리고나서 유저 u와 유저 v의 피어슨 상관계수는 다음과 같이 구할 수 있습니다.

$ Sim(u, v) = Pearson(u, v) = \frac{\sum_{k\in I_u \cap I_v }(r_{uk}-\mu_u)(r_{vk}-\mu_v)}{\sqrt{\sum_{k\in I_u \cap I_v}(r_{uk}-\mu_u)^2} \sqrt{\sum_{k\in I_u \cap I_v}(r_{vk}-\mu_v)^2} } $

위와 같은 피어슨 상관계수는 해당 타겟 유저와 다른 모든 유저들 간의 피어슨 상관계수를 계산합니다. 그리고 동료집단을 선정할 수 있는 한가지 방법은 피어슨 상관계수가 가장 높은 상위 k명의 유저를 선택하는 것입니다. 그러나 동료집단에서도 특정 아이템에 대한 평점은 다양하게 나타날 수 있으므로, 각 아이템 별로 서로 다른 k명의 유저를 선택할 수도 있습니다. 이런 경우에는 k명의 유저의 각 평점의 가중 평균을 이용해 특정 아이템의 평점을 예측합니다.

피어슨 상관계수를 이용한 유사도 측정의 단점은 각 유저들마다 스케일이 다르다는 것입니다. 어떤 유저는 아이템의 평점을 대체로 높게 주고, 어떤 사람은 아이템의 평점을 대체로 낮게 주는 것입니다. 따라서 사전에 mean-centered 되도록 표준화를 해주는 것이 좋습니다. mean-centered 평점 $s_uj$는 유저 u의 아이템 j에 대한 평점을 의미하며 다음과 같이 구합니다.

$ s_{uj} = r_{uj} - \mu_u $

36