Neighborhood-Based Collaborative Filtering
Introduction
Neighborhood-based collaborative filtering algorithms 는 memory-based algorithms와 동일한 의미입니다.
이 Neighborhood-based collaborative filtering algorithms은 두개의 primary types로 나눠질 수 있습니다.
- User-based collaborative filtering : user의 이웃에 대한 rating 고려
- Item-based collaborative filtering : target user가 item 이웃에 대해 rating 한 것 고려
여기에서 predict 까지의 과정에서 formulate 방법에 따라 두가지로 나눠집니다.
- Predicting the rating value of a user-item combination : rating value를 predcit
- Determining the top-k items or top-k users : top-k items or users를 결정
보통 merchant 입장에서는 정확한 rating value가 필요 없는 경우가 많습니다. 그래서 top-k items or users만 뽑는 2번 방법을 자주 사용합니다.
여기에서 top-k items는 보통 user에게 web centric scenarios에서 추천을 주는데 이는 보편적으로 사용되는 방법입니다.
top-k users는 보통 마케팅에서의 타게팅할 최상의 사용자를 결정하는데 사용됩니다. (merchant에게 유용)
앞에서 언급한 두 방법은 밀접하게 연관 되어있습니다. top-k items를 추천하기 위해서는 Target user에 대한 각 items의 ratings를 predict 해야합니다. 이런 formulate에서 효율을 위해 보통 precompute 합니다.
Key Properties of Ratings Matrices
rating matrices에 대한 key properties를 알아보겠습니다.
앞에서도 계속 언급되던 내용인데, CF의 방법에서는 ratings matrices의 small subset 만이 특정 되어 있습니다. (Sparse) 여기에서 특정 되어있는 데이터를 training data로 보고 나머지 unspecified 인 것들은 test data로 볼 수 있기 때문에, 이를 분류 회귀 문제의 generalization으로 볼 수 있습니다.
Ratings의 종류로서는,
- Continuous ratings : 이는 사용자에게 선택에 대한 짐을 안겨주기 때문에 잘 사용되지 않습니다.
- Interval-based ratings : numerical values는 explicit한 ratings입니다. 이 ratings간의 사이에 거리를 정의하고 ratings value 사이는 등거리하다는 가정을 둡니다.
- Ordinal ratings : interval based ratings + ordered categorical value 사용. 이 경우에는 value 사이의 거리가 동일하다는 가정이 없습니다. 하지만 실제로 사용될 때는 등거리인 경우가 많습니다. forced choice method라 불리기도 합니다.
- Binary ratings : positive or negative 이 두가지의 responses만이 존재합니다. 이는 interval based 하면서 ordinal 합니다.
- Unary ratings : negative response 없이 positive preference만 특정할 수 있습니다. 이에 대한 예시로는 Facebook의 "Like"가 있습니다. implicit한 경우에는 user의 action, behavior 입니다. unary ratings는 specialized models의 개발을 단순화 시키고 data를 얻기 쉽습니다.
Unary의 경우 setting이 다른것들과 본질적으로 다릅니다. 이러한 ratings type은 실제 세계에서 long-tail property를 일으키곤 합니다. (Fig 2.1)
long-tail property는 items의 일부만 자주 평가 되는 현상을 말합니다. (popular items..) Fig 2.1 을 보시면 skewed distribution이 형성됨을 알 수 있습니다.
이러한 ratings distribution이 어떤 영향을 미치는지 알아보겠습니다.
High frequency items는 보통 merchant에게 이익이 되지 않는 경우가 많습니다. 그리고 long tail의 부분은 높은 수익의 item인 경우가 많습니다.
데이터의 부족 때문에 long tail에서 robust한 rating prediction이 어렵습니다. (diversity 부족)
long tail distribution을 보면 빈도 있는 items의 수가 적음을 알 수 있습니다. neighborhoods는 빈도 있는 rated items에 의해 종종 결정되기 대문에 위의 사실은 neighborhood based CF에 큰 영향을 줄 수 있습니다. 이러한 경우 prediction process는 results를 잘못 낼 수도 있습니다.
Predicting Ratings with Neighborhood-Based Methods
Neighborhood-Based Collaborative Filtering은 prediction을 위해 similar users 혹은 items를 지정 할 필요가 있습니다.
User-Based Neighborhood Models
User-based neighborhood models는 target user와 비슷한 users를 특정합니다. 그러면 target user와 모든 다른 users간의 유사도가 계산됩니다. 그리고 이때 Similarity function은 users에 의해 특정된 ratings 간에 설정 되어야합니다.
하지만 이 때 user간 ratings scale이 다를 수도 있고 서로 다른 item을 평가 했을 수도 있기 때문에 이를 고려해줘야 합니다.
Notation
\(R = [r_{u,j}]\) : (m users, n items) mxn rating matrix, u = user, j = item
\(I_u\) : user u에게 특정된 ratings가 있는 item set
Similarity를 계산하기 위해서는 user u와 user v에 대한 두개 Set의 교집합 \(I_u \cap I_v\)이 필요합니다.
그러면 대표적인 Similarity measure을 봐보겠습니다.
Pearson correlation coefficient
첫번째로 user u, v의 mean ratings를 구해줍니다.
두번째로 user를 고정 한 상태로 편차간의 곱을 이용하여 Pearson correlation coefficient를 구해줍니다.
traditional 한 경우에, \(\mu\)를 구할 때 user u,v 모두에게 rating 된 item만 고려했었습니다. 하지만 통상 각자가 rating 한걸로 사용합니다. (Equation 2.1 처럼)
target user에 대한 peer groups 지정은 target user에 대해 Pearson coefficient가 가장 높은 k명의 users로 이뤄집니다.
peer group의 user들은 각 items에 따라 observed ratings의 수가 다양합니다. 그래서 각 predicted item마다의 peer group 생각을 해야합니다. (교집합)
이러한 계산에서 가장 큰 문제점이 뭘까요?? 그건 바로 user 마다 다른 scale의 ratings를 할 수 있다는 것 입니다. 그래서 raw ratings를 열(user) 단위에서 mean을 기준으로 표현되도록 하는게 중요합니다.
이는 아래의 식(Equation 2.3)이며 mean-centered rating이라고 불립니다.
위의 mean-centered rating을 고려하여 최종적인 neighborhood-based prediction function은 아래와 같습니다.
Example of User-Based Algorithm
위 Table 2.1을 기준으로 예시를 들어 user 3에 대한 prediction을 하고싶다는 가정하에 봐보겠습니다.
우선 앞에서 공부했던 process 대로 하면,
- user 3과의 users의 유사도 계산
- top-k closest users에 대해 Pearson weighted average 사용합니다. 이를 통해 item ratings \(r_{31},r_{36}\)을 predict 합니다.
일단 계산과정은 생략하겠습니다.
이런식으로 계산을 하면,
$$
\hat r_{31} = 6.49\
\hat r_{36} = 4
$$
가 나오는데 이를 보면 뭔가 둘 다 추천해도 괜찮을거 같다는 생각이 듭니다.
이는 mean centered ratings를 사용하지 않은 경우입니다.
mean centered ratings를 사용한 결과는
$$
\hat r_{31} = 3.35\
\hat r_{36} = 0.86
$$
\(\hat r_{36}\)가 나머지 ratings \(r_{31}, r_{32}, ..\)보다 낮음을 알 수 있습니다.
이와 같이 mean centered ratings를 통하면 observed ratings를 고려해주기 때문에 훨씬 더 연관성 있는 prediction이 가능합니다.
단점이 있따면 rating의 범위를 넘어 갈 수도 있다는 것이지만 top-k 추천같은 경우에는 정확한 prediction이 크게 필요한게 아니니 이런 경우에는 사용할 수 있습니다.
Similarity Function Variants
Similarity를 측정하는데 여러가지 function이 존재합니다.
raw한 코사인 유사도 입니다.
하지만 여기에서 고려를 해줘야 할게 \(I_u\cap I_v\)의 수가 적다면 Similarity function의 중요도를 낮춰줘야 합니다. 이러한 역할을 하는 것을 Significance weighting이라 합니다.
Variants of the Prediction Function
Prediction function에서도 물론 여러가지 방법이 있습니다.
그 중 하나인 Z-score에 대해 알아보겠습니다. (정규분포사용)
Z-score는 centered value인 \(s_{uj}\)에서 더 나아가서 표준편차인 \(\sigma_u\)로 나눠줍니다. (Z-test에서의 z와 동일한 의미인 정규분포 인듯.)
prediction은 아래와 같습니다.
여기에서 \(P_u(j)\)는 target user u에 대한 item j의 top-k similar users를 의미합니다.
여기에서 \(\sigma_u\)를 나눠줬던 행위처럼 \(g(.)\) 함수를 적용하면 이의 역함수를 마지막에 적용을 해줘야합니다. \(\sigma_u\)가 곱해져있는 이유 입니다.
z-score의 단점은 허용되는 ratings 범위를 자주 넘어간다는 점 입니다. 앞에서 말했듯이 rank ver를 사용하면 됩니다. (범위가 넘어간다 하더라도 성능이 괜찮음.)
prediction에 있어서 두번째 issue는 similarity를 고려해주는 곱 (원서에서는 weighting이라고 합니다.)에서 Similarity를 얼마나 고려해줄거냐를 생각해야하는데, 이는
$$
Sim(u,v) = Pearson(u,v)^\alpha
$$
와 같이 \(\alpha\)의 크기를 조절해서 유사도의 importance를 조절해줍니다. (alpha가 1보다 크면 importance 강화)
앞에서 언급한 내용들은 최근접 이웃 회귀모델과 유사합니다. (연속된 숫자로 결과가 나옴)
분류의 형식으로 predict function을 만드는 것도 가능합니다.
target user u의 peer groups이 설정되면 each possible ratings value에 대한 votes 수가 정해집니다. 이를 통해 votes 수가 가장 많은 것을 predict 할 수 있습니다.
위와 같은 방법은 distinct ratings의 수가 적을 때 좋습니다. 하지만 등급의 세분성이 높아지면 less robust, ordering information을 lose 할 수 있습니다.
Variants in Filtering Peer Groups
Peer groups를 정하는 가장 간단한 방법은 top-k를 가장 비슷한 users로 정하는 것입니다.
하지만 단순히 이런 방법으로 하면 target user와 상관 관계가 약하거나 반대방향의 user를 포함할 수도 있습니다. 이는 prediction의 오류를 초래할 수 있습니다.
그래서 weak, negative correlations를 갖는 ratings를 종종 filter 하기도 합니다.
Impact of the Long Tail
앞에서 언급했던 long tail 현상에 대해 자세히 알아보겠습니다.
popular ratings는 추천에 있어서 diversity를 해칠 수 있습니다. (document retrieval application에서 'a', 'an', ...)
그래서 IDF 를 고려해주는 것 처럼 IUF(Inverse User Frequency)를 고려해주도록 하겠습니다.
IUF
IUF weight를 이용한 Pearson은 아래와 같습니다.
Item-Based Neighboorhood Models
Item-based neighborhood models는 user-based neighborhood models와는 다르게 peer groups가 item으로 구성됩니다. 이는 item 간의 유사도를 구할 것임을 의미합니다.
단, 앞과 똑같이 item간의 유사도를 구하기전 각 row의 mean을 0으로 만듭니다. (Equation 2.3)
Notation
\(U_i\)item i를 rating한 user group
item based neighborhood models에서 유사도를 측정하는 방법 중 하나인 adjusted cosine에 대해 알아보겠습니다.
이 경우 item을 고정하고 user를 바꿔가며 두 items의 유사도를 측정합니다. 둘 다 rating 한 user의 history를 사용한다고 생각하면 될 것 같습니다.
물론 여기에서도 Pearson correlation이 사용 될 수 있지만 보통 이 경우에 Pearson correlation보다 adjusted cosine이 더 우수한 성능을 보입니다.
한번 user u에 대한 target item t의 rating이 필요한 경우에 대해서 process를 생각해봅시다.
- item t에 top k similar items를 지정합니다.(adjusted cosine 유사도 기반)
- item j와 target item t의 유사도를 고려해서 prediction
\(Q_t(u)\) : target user u가 rating 한 것 중 top k similar items
위의 식과 같이 prediction이 이루어 집니다.
여기에 대한 basic idea는 마지막 단계인 prediction을 target user's own ratings로 이끌어 낸다는 것 입니다.
item-based algorithms과 user-based algorithms가 매우 비슷하기 때문에 similarity function, prediction function들도 비슷하게 디자인 될 수 있습니다.
Efficient Implemention and Computational Complexity
Neighborhood-based methods의 prediction process에서 중간의 값들이 재사용됩니다.
그래서 중간 계산을 저장 했다가 다음 필요할 때 재사용 하는 offline process가 필요합니다.
Neighborhood-based models는 offline, online 단계로 나눠집니다.
offline phase : user-user of item-item similarity와 peer groups가 계산됩니다.
online phase : 위의 정보들을 predict 하는데 사용합니다.
Notation
\(n^\prime\) : user 기준 specified ratings의 최대 수 \(n \gg n^\prime\)
\(m^\prime\) : item 기준 specified ratings의 최대 수 \(m \gg m^\prime\)
user-based methods에서 offline running time은 \(O(m^2 n^\prime)\)
item-based methods에서 offline running time은 \(O(n^2 m^\prime)\)
user-based methods에서 online running time은 \(O(m^2)\)
item-based methods에서 online running time은 \(O(n^2)\)
Online 이 offline보다 효율적입니다.
Comparing User-Based and Item-Based Methods
item-based methods가 user-based methods보다 더 좋은 결과를 내는 경향이 있습니다. 이 이유는 item-based method가 target user's own ratings를 사용해서 predict하기 때문입니다.
하지만 item based와 user based 사이의 relative accuracy는 data에 달려있습니다.
Item based methods
- shilling attacks에 robust
- recommendation에 대한 concerete reason을 제공 할 수 있음.(explanation)
- rating의 변화에 더 robust.
item의 수보다 user의 수가 훨씬 많아서 co-rated item보다 item based경우 data가 많음
new item 보다 new user의 경우 더 자주 추가 된다. 이는 item에 대한 change가 극적으로 일어나지 않음을 의미함.
User based methods
- diversity에 있어서는 user based 가 더 나음. (serendipity, novel..)
- Explanation이 어려움. 하지만 제공은 가능함.(개인 정보 문제 등으로 제한된 설명)
- recommendation model의 유지가 어려움.
Strengths and Weaknesses of Neighborhood-Based Methods
이제 Neighborhood-based methods의 장단점에 대해 이야기해보겠습니다.
neighborhood-based methods의 이점들은 simplicity와 intuitive와 관련이 깊습니다.
장점
- 시행 및 디버그가 쉬움
- model based 보다 explanation이 쉬움
- new items and user에 대해 stable
단점
- offline phase에서 large-scale settings의 경우 너무 느릴수도 있음.
- sparsity 때문에 수렴에 제한 있음. Sparsity는 robust한 유사도 계산에 어려움을 줌
A Unified View of User-Based and Item-Based Methods
item 간 혹은 user 간의 유사도를 무시하는 각각의 방법을 절충시키는게 좋을 것 같습니다.
이는 두 방법을 이용해서 similar entries를 구하는 것과 동일한 의미입니다. 이는 유사도 정보를 결합함으로써 해결 할 수 있습니다.
- target entry (u,j)에 대해 rows, columns 사이의 코사인 coefficient를 사용하여 similar rows/columns를 구합니다.(user-based의 경우 rows가 사용되고, item-based의 경우 columns가 사용됩니다.)
- 위의 정보를 활용해서 target entry (u,j)를 weighted combination을 사용하여 예측합니다.
