[논문] Item-based collaborative filtering recommendation algorithms

Recommender System

Collaborative Filtering

1. NBCF : Neighborhood-Based Collaborative Filtering
2. UBCF : User-Based Collaborative Filtering
3. IBCF : Item-Based Collaborative Filtering

 

1. Collaborative Filtering : Overview

• 특징
  • user-item에 대한 선호도(rating)에 대한 database를 사용
  • 특정한 user A와 가장 유사한 성향을 가진 다른 user B에게 A가 선호하는 item을 추천하는 방식
  • 최종목적 : 특정한 user가 특정한 item에 대해 가질 선호도(rating)을 예측
  • 예시)
    1. user A와 B가 선호도가 유사함을 보일때,
    2. user B가 "파란색 네모"를 선호한다면, user A에게 "파란색 네모"를 추천 O
    3. user B가 "노란색 동그라미"를 선호하지 않는다면, user A에게 "노란색 동그라미"를 추천 X

• 프로세스
  • Input 행렬은 user u_i와 item i_j에 대한 선호도(rating)를 행렬로 나타낸 것
  • 각 cell에 선호도가 있으나, user가 item에 대해 아직 평가하지 않았다면 0(또는 비어있음)일 수 있음
  • 목적에 따라 결과물은 CF 알고리즘을 예측 또는 추천으로 표현할 수 있음
    • 예측 : user u_i에 대한 item i_j 선호도를 예측
    • 추천 : user u_i가 가장 선호할 N개의 item 목록 -> Top N Recommendation

 

• 문제점
  
  1. 확장성 향상 : the scalability of the collaborative filtering algorithms
     • CF는 실시간으로 수만개의 잠재적 이웃을 검색해낼수 있지만, 실제 추천시스템에서는 실시간으로 수천만개의 잠재적 이웃을 검색해야함
     • 특정한 user가 한 사이트에서 활동한 기록 등이 많을 때 이것을 선호도의 지표로 사용하는 경우, 데이터의 길이가 길어지므로 소요시간을 증가시킬 수 있음
  2. 추천하는 항목에 대한 품질 개선 : the quality of the recommendations for the users
     • user는 자신이 좋아하는 item을 추천할 것이라고 믿고 있는데,
     • 일관되지 않고 부정확한 추천이 계속 될 경우 신뢰성이 하락
• 확장성 vs 품질 : trade-off 관계
  
  • 검색 시간 소요 단축 -> 확장성 증가 - 품질(정확도) 저하
  • 검색 시간 소요 연장 -> 확장성 감소 - 품질(정확도) 증가

 

 

2. IBCF : Item-based Collaborative Filtering

• 기존의 CF에서는 대량의 user 집단 데이터 안에서 잠재적인 이웃(potential neighbor)를 검색하므로 병목 현상 발
  • IBCF는 user간의 관계가 아니라 item간의 관계를 먼저 탐색
  • user에 대한 추천은 user가 선호하는 다른 item을 통해 계산됨
  • 적은 계산량으로 user-based CF와 같은 품질의 결과

 

2-1. UBCF(User-based CF)와의 비교

• UBCF의 한계
  • Sparsity (희소성)
    • saprse 데이터는 user-item 행렬에 rating이 굉장히 적음
    • 따라서 유사한 성향의 user간 관계를 찾기가 어려우므로 추천 정확도가 낮아질 수 있음
  • Scalabilty (확장성)
    • user와 item 수가 많아질수록 많은 계산이 필요함
    • 실시간으로 대용량의 데이터를 처리해야하는 일반적인 웹 기반 추천시스템의 문제

 

2-2) 유사도 계산 : Item Similarity Computation

• Cosine Similarity
  • item i와 j는 같은 m차원에서의 벡터
  • 두 벡터 사이의 각도의 유사성으로 user와 item의 유사성을 체크함

• Pearson Correlation Similarity
  • item i, j의 상관관계를 계산
  • 같은 user에 대한 item i, j 각각의 rating을 사용

• Adjusted Cosine Silmilarity
  • user-based CF의 경우, 유사도가 user-item 행렬의 행(user)를 따라 계산되지만, item-based CF에서는 유사도가 열(item)에 따라 계산
  • Cosine Similarity의 단점은 다른 user 간의 rating scale의 차이가 고려되지 않음 -> normalize 필요

 

2-3) Prediction Computation

1. CF에서 가장 중요한 단계는 Prediction에서 Output Interface를 생성하는 것
2. 계산한 유사도를 기반으로 가장 유사한 item 집합을 분리하고, 해당하는 user의 rating의 예측

• Weighted Sum
  • target이 되는 item i와 유사한 item에 대하 user들이 부여한 rting의 합계를 계산
  • item i와 다른 item들의 유사도 계산
  • 1과 2를 Weight Sum 하여 Prediction 값(target item i의 예측 평점) 계산
  • rating 합계가 아니라, 다른 item과 item i의 잔차(deviation)을 사용할 수도 있다.

• Regression
  • rating의 근사치를 사용
  • 유클리드 관점에서 Cosine Similarity로 계산된 유사도는 거리자체가 떨어져 있을 수 있음 (방향으로 유사도를 체크하는 방식이기 때문에)
  • 이를 그대로 사용하면 예측이 원활하지 않을 수 있음
  • Weight Sum 방식을 사용하되, 유사 item의 rating의 합 R_u,N을 사용하는 대신에 linear regression을 사용한 근사값 R`_u,N을 사용 
  • target item i와 유사한 item N을 각각 R_i, R_N으로 표현하면 다음과 같은 식

 

2-4) Performance Implicications

• Neighbor-based CF
  • Neighborhood를 형성하는 프로세스 특히, user-user 유사도를 계산하는 단계에서 bottle-neck 현상이 있음
  • 실시간 추천시스템에 적합하지 않음
• 확장성을 보장하려면 model-based recommendation을 사용해야함
• 주 아이디어 : (1) Neighborhood Generation (2) Prediction -> 두 단계를 분리하는 것

본 논문에서는,

• model-based 접근방법을 통해 item-item 유사도를 미리 계산
• 유사도 계산은 여전히 correlation 기반이지만 계산은 item 공간에서 수행됨
• E-commerce -> user 수는 자주 변경 / item 수는 자주 변경되지 않음
  • 그래서 item 유사도를 미리 계산
  • 시간은 절약할 수 있지만 item의 개수에 따라 O(n^2)의 공간이 필요함
• 각 item j에 대해 가장 유사한 k개(k<n)의 유사 item만 계산함
  • k는 모델의 크기(?)
• 모델 생성 단계에서 Prediction Generation 알고리즘이 수행됨
  • user u에 대한 item i을 예측
  •  target item i에 대해 precomputed k개의 유사 item들을 검색
  • user u가 precomputed k개의 유사 item들 중에 실제로 구매한 것이 몇개인지 찾게됨
    • basic item-based CF 사용하여 예측
• 추천 품질(Quality)과 성능(Performance)에 대한 trade-off 발생함을 확인
  • 극단적으로 볼때 원래 모델의 크기 n만큼 커지면 예상된 추천 품질을 가지지만, 시간복잡도 또는 공간복잡도 등의 성능적인 문제가 발생
  • 적절한 k를 찾는 것이 관건
    • 저장해야하는 유사 item의 개수 k는 예측 점수를 형성하는데 가장 큰 영향을 끼침
    • 가설 : model-based 접근방식은 작은 크기의 모델로도 좋은 성능을 낼 수 있을 것

 

 

3. Experimental Procedure

결과

3-1) Effect of Similarity Algorithms

• 위의 이미지는 유사도를 계산하는 방식에 따라서 loss(MAE)값을 비교한 것
• 각 유사도 계산 방식을 Neighborhood 계산과 Weighted Sum 계산을 사용하여 Prediction
  • Adjusted Cosine Similarity가 loss가 가장 작음

 

3-2) Sensitivity of Training/Test Ratio

• Sensitivity of Density를 결정하기 위한 실험
  • x의 값을 0.2~0.9까지 0.1단위로 계산
  • itm-itm : basic Weighted Sum
  • itm-reg : Regression
  • x가 증가될 수록 loss는 줄어듬
  • x가 0.8정도에서 itm-reg가 itm-itm보다 성능이 떨어지는 것을 확인
  • train/test 비율은 0.8에서 결정
• Neighborhood size
  • Neighborhood의 크기를 줄일수록 itm-itm은 줄어들다 수렴하는 경향
  • Neighborhood의 크기를 줄일수록 itm-reg는오히려 점점 커지는 경향
  • Neighborhood = 30에서 itm-itm이 최저이고, itm-reg이 3번째로 작으므로 최적의 크기는 30

 

3-3) Quality Experiments

• 왼쪽 이미지는 Neighborhood가 커짐에 따라 각 접근방식의 성능을 보여줌
  • Neighborhood가 20 이상일때, 가장 최적의 loss값을 가지는 접근방식은 item-item
  • 최적의 Neighborhood = 30이므로 item-item이 가장 최적의 접근방식
• 오른쪽 이미지는 x의 크기에 따라 각 접근 방식의 성능을 보여줌
  • x가 0.8이상일때, 가장 최적의 loss값을 가지는 접근 방식은 item-item
  • 최적의 x = 0.8이므로 item-item이 가장 최적의 접근방식

 

3-4) Sensitivity of the Model size

• 모델의 크기에 따른 최적의 x를 나타낸 이미지
• item의 일부만 사용해도 높은 정확도를 얻을 수 있다는 것을 보여줌
• 모델의 사이즈와 상관없이 x의 값이 0.8일때, 최적의 loss값을 가짐
  • 적은 사이즈의 모델에서도 최적의 성능을 보일 수 있다는 의미

 

 

4. Conclusion

• 추천시스템은 user database에서 비즈니스를 위한 부가가치를 창출할 수 있는 기술
• 사용자, 기업 모두에게 도움이 되는 기술이므로 E-commerce에서 특히 중요한 도구가 되고 있음
• 웹 기반 시스템은 많은 양의 데이터가 계속해서 증가함에 따라 획기적으로 성능향상할 필요가 생김

 

 

 

 

 

출처 및 참고 자료 : 네이버커넥트 부스트캠프 AI_Tech 강의 자료, 구글링