- 논문 링크 (11700회 인용)
Item-based collaborative filtering recommendation algorithms | Proceedings of the 10th international conference on World Wide We
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
dl.acm.org
Summary
- 기존의 방식이 비슷한 유저를 먼저 탐색하고자 한다면, item-based CF는 아이템간의 관계를 먼저 탐색함으로써 bottleneck을 해결하고자 한다.
- 아이템간의 관계를 유사도 계산을 통해 파악하고, 이를 이용하여 target item에 대한 점수를 예측한다.
- 유사도 방법은 adjusted cosine similarity가, 예측 방법은 item-item 방법이 좋았다.
- target item과 유사한 아이템의 개수는 늘어날수록 성능이 좋아졌다.
Motivation
- 기존의 user-based CF의 단점을 극복하고자 개발된 것이 item-based CF이다.
- user-based CF는 유저와 가까운 이웃들의 거리를 계산할 때, $O(n^2)$의 시간 복잡도가 걸려서 유저의 수가 매우 많아진다면 scalability의 문제가 발생한다.
- 정확도의 문제도 있다.
- 정확도를 늘리고자 한다면 시간이 오래 걸리고, 시간을 줄이면 정확도가 줄어들기 때문에 이 둘은 trade-off 관계에 있다.
- item-based CF는 유사한 아이템을 먼저 탐색함으로써 위 문제를 해결하고자 한다.
Approach
notation
- $\mathcal{U} = \{ u_1, u_2, \cdots, u_m \}$: m명의 유저
- $\mathcal{I} = \{ i_1, i_2, \cdots, i_n \}$: n개의 아이템
- $\mathcal{I}_{u_i}$: 각 유저가 가지는 아이템
- $u_a$: active user. cf 알고리즘을 수행할 대상
- $P_{a,j}$: active user의 $i_j \notin I_{u_a}$인 아이템에 대한 predicted likeness. 예측해야할 대상이다. 이를 Prediction이라고 한다.
- $I_r$: active user가 좋아할만한 r개의 아이템이다. CF에서는 top-n 추천이라고도 불린다.
Item similarity computation
item-based CF는 active user의 사용하지 않은 아이템에 대한 unknown likeness을 예측하고자 하는데 이를 위해 사용하지 않은 아이템과 유사한 k개의 아이템을 뽑는다. 이때 사용하지 않은 아이템과 그 외의 아이템 간의 유사도를 계산해야 한다.
Cosin based similarity
두 아이템 i,j간의 코사인 유사도는 위와 같이 정의된다. 이때 각 아이템 벡터는 m차원이다.
Correlation based similarity
여기서 $U$는 아이템 i,j에 대해 모두 likeness을 표현한 유저이다. $R_{u,i}$는 유저 u가 아이템 i에 대해 표현한 likeness을, $\bar{R}_i, \bar{R}_j$는 아이템 i,j에 대한 평균 likeness이다.
Adjsted cosine similarity
cosine based similarity는 유저들간의 스케일을 보정하지 않는다는 단점이 있다. 이를 보완하기 위해 $\bar{R}_u$을 빼준다. 이는 유저 u의 평균 likeness이다.
Prediction computation
CF에서 가장 중요한 부분이다. active user의 unknown predicted likeness을 예측하는 부분이다.
Weighted sum
아이템 i와 유사한 k개의 아이템은 앞서 item similarity computation 파트에서 완료했다. 여기서 $s_{i,j}$는 아이템 i,j간에 미리 계산한 유사도이다. 또한 $R_{u,i}$는 유저 u가 아이템 i에 대해 남긴 likeness이다. 이 prediction 값은 active user가 아이템 i와 유사한 아이템들을 어떻게 평가하는지 나타낸다.
Regression
weighted sum에서 $R_{u,N}$을 사용하는 대신 regression 모형을 이용한 추정값을 사용한다.
이는 cosine similarity나 correlation similarity가 euclidean 상으로는 멀 수 있지만 실제로는 가까운 경우 좋지 못한 예측 결과를 내기 때문에 raw likeness가 아닌, 근사값을 사용하는 것이다.
Results
Effect of similarity algorithm
adjusted cosine similarity의 MAE가 가장 낮았다.
Sensitivity of training size & neighborhood size
여기서 training이란, 미리 떼어둔 데이터를 사용하여 아이템 i와 유사한 k개의 아이템 간의 similarity score 값을 미리 계산해두는 과정이다. 훈련 데이터 비율이 높을 수록 MAE가 줄어들고, 유사한 아이템을 처음 늘릴 때 MAE가 많이 줄어들었다 (item-item)
Conclusion
- user based CF의 한계를 극복하고자 연구된 item based CF이지만 여전히 아이템간의 similarity을 계산하고자할 때 $O(n^2)$의 시간이 걸리는게 아닌가 싶다. ($n$은 아이템의 개수)
- 그럼에도 active user의 unknown likeness을 예측하고자 다른 아이템간의 유사도를 반영했다는 점에서 의미가 있다고 생각된다.
댓글