Collaborative Filtering (1)

Collaborative Filtering (1)

1. Collaborative Filtering (CF)

1.1 CF 문제 정의

협업 필터링 (Collaborative Filtering, CF)

“많은 유저들로부터 얻은 기호 정보”를 이용해 유저의 관심사를 자동으로 예측하는 방법

• Collaborative: 집단적 협업, 다수의 의견 활용
• 더 많은 유저/아이템 데이터가 축적될수록 협업의 효과는 커지고 추천은 정확해질 것이란 가정에서 출발
• 학습데이터가 많을 수록 좋다는 것과 같은 원리

CF 기반 추천 시스템

최종 목적

유저 $u$가 아이템 $i$에 부여할 평점을 예측하는 것

방법

1. 주어진 데이터를 활용해 유저-아이템 행렬을 생성한다
2. 유사도 기준을 정하고 유저 혹은 아이템 간의 유사도를 구한다
3. 주어진 평점과 유사도를 활용하여 행렬의 비어 있는 값(평점)을 예측한다

1.2 CF 원리

CF 기반 추천 시스템의 원리

유저 A와 비슷한 취향을 가진 유저들이 선호하는 아이템을 추천

• 아이템이 가진 속성을 사용하지 않으면서도 높은 추천 성능을 보임

1.3 CF 분류

Neighborhood-based CF (Memory-based CF)

• User-based
• Item-based

Model-based CF

• Non-parametric (KNN, SVD)
• Matrix Factorization
• Deep Learning

Hybrid CF

• Content-based Recommendation 과의 결합

2. Neighborhood-based CF

2.1 User-based CF (UBCF)

유저 기반 협업 필터링 (User-based CF, UBCF)

• 두 유저가 얼마나 유사한 아이템을 선호하는지

• 유저간의 유사도를 구한 뒤에 타겟 유저와 유사도가 높은 유저들이 선호하는 아이템을 추천

• 유사도가 높다 = 취향이 비슷하다 = correlation이 높다

2.2 Item-based CF (IBCF)

아이템 기반 협업 필터링 (Item-based CF, IBCF)

• 두 아이템이 유저들로부터 얼마나 유사한 평점을 받았는지

• 아이템간 유사도를 구한 뒤에 타겟 아이템과 유사도가 높은 아이템 중 선호도가 큰 아이템을 추천

2.3 Neighborhood-based CF (NBCF)

이웃 기반 협업 필터링 (Neighborhood-based CF, NBCF)

최종 목적

유저 $u$가 아이템 $i$에 부여할 평점을 예측하는 것

특징

• 구현이 간단하고 이해가 쉬움
• 아이템이나 유저가 계속 늘어날 경우 확장성이 떨어짐 (Scalability)
• 주어진 평점 / 선호도 데이터가 적을 경우, 성능이 저하됨 (Sparsity)

Sparsity

• 유저-아이템 숫자에 비해 평점, 선호도 데이터가 적은 경우를 말함

• 행렬 대부분의 원소가 비어있음 (sparse matrix, 희소 행렬)
• NBCF를 적용하려면 적어도 sparsity ratio가 99.5%를 넘지 않는 것이 좋음
  • 그렇지 않을 경우에는 모델기반 CF를 사용해야함 (ex Matrix Factorization)
  • sparsity ratio: 행렬 전체 원소 중 비어 있는 원소의 비율

3. K-Nearest Neighbors CF & Similarity Function

3.1 K-Nearest Neighbors (KNN) CF

NBCF의 한계

• 아이템 $i$에 대한 평점 예측을 하기 위해서는 $\Omega_i$에 속한 모든 유저와의 유사도를 구해야함
  • $\Omega_i:$ 아이템 $i$에 대해 평가를 한 유저 집합
• 유저가 많아질 경우 계속해서 연산은 늘어나고 오히려 성능이 떨어지기도 함

KNN 협업 필터링(k-nearest neighbors CF, KNN CF)의 아이디어

$\Omega_i$에 속한 유저 가운데 유저 $u$와 가장 유사한 $K$명의 유저(KNN)를 이용해 평점을 예측

• 유사하다 = 유사도 값이 크다
• 보통 $K$ = 25 ~ 50을 많이 사용 / 하이퍼파라미터

3.2 Similarity Measure

유사도 측정법(Similarity Measure)

두 개체 간의 유사성을 수량화하는 실수 값 함수 혹은 척도

• 유사성에 대한 여러 정의가 존재하지만 일반적으로는 거리의 역수 개념을 사용
• 따라서 두 개체 간 거리를 어떻게 측정하느냐에 따라 유사도 측정방법이 달라짐

Mean Squared Difference Similarity

• 주어진 유저-아이템 rating에 대하여

\[msd(u, v)=\frac{1}{|I_{uv}|}\cdot \sum_{i\in I_{uv}}(r_{ui}-r_{vi})^2 \ msd\_sim(u, v) = \frac{1}{msd(u, v)+1}\] \[msd(i, j)=\frac{1}{|U_{uv}|}\cdot \sum_{u\in U_{ij}}(r_{ui}-r_{uj})^2 \ msd\_sim(i, j) = \frac{1}{msd(i, j)+1}\]

• 추천시스템에서 주로 사용되는 유사도

  • 각 기준에 대한 점수의 차이를 계산, 유사도는 유클리드 거리에 반비례

  • 분모가 0이 되는 것을 방지하기 위해 분모에 1이 더해짐 (smoothing)

  • 평점이 비슷할수록 $msd$ 값은 작아지게 되고 $msd_sim$의 값은 커지게 됨
  • $msd$ 값이 0일 경우 $msd_sim$의 값은 1 이 된다

Cosine Similarity

• 주어진 두 벡터 X, Y에 대하여

\[cos(\theta)=cos(X,Y)=\frac{X\cdot Y}{|X||Y|}=\frac{\sum_{i=1}^{n}X_iY_i}{\sqrt{\sum_{i=1}^{N}X_{i}^2}{\sqrt{\sum_{i=1}^{N}Y_{i}^2}}}\]

• 두 벡터의 각도를 이용하여 구할 수 있는 유사도
  • 두 벡터의 차원이 같아야 함
• 직관적으로 두 벡터가 가리키는 방향이 얼마나 유사한지를 의미함
  • 두 벡터의 방향이 비슷할수록 1에 가깝고 반대일 경우 -1에 가까워짐

Pearson Similarity (Pearson Correlation

• 주어진 두 벡터 X, Y에 대하여

\[pearson\_sim(X,Y)=\frac{\sum_{i=1}^N(X_i-\bar{X})(Y_i-\bar{Y})}{\sqrt{\sum_{i=1}^N(X_i-\bar{X})^2} \sqrt{\sum_{i=1}^N(Y_i-\bar{Y})^2}}\]

• 각 벡터를 표본평균으로 정규화한 뒤에 코사인 유사도를 구한 값
  • (X와 Y가 함께 변하는 정도) / (X와 Y가 따로 변하는 정도)
  • 1에 가까우면 양의 상관관계, 0일 경우 서로 독립, -1에 가까울 수록 음의 상관관계

Jaccard Similarity

• 주어진 두 집합 A, B에 대하여

\[J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|}\]

• 집합의 개념을 사용한 유사도
  • Cosine, Pearson 유사도와 달리 길이(차원)이 달라도 이론적으로 유사도 계산이 가능
  • 두 집합이 같은 아이템을 얼마나 공유하고 있는지를 나타냄
    • 두 집합이 가진 아이템이 모두 같으면 1
    • 두 집합에 겹치는 아이템이 하나도 없으면 0

데이터와 서비스의 특징에 따라 유사도를 선택하는 것이 중요!!

4. Rating Prediction

4.1 UBCF - Absolute/Relative Rating

Weighted Average

다른 유저들의 아이템에 대한 rating의 가중 평균을 냄

유저들마다 유사도가 다를 수 있으므로 유저간의 유사도값을 각각의 가중치로 적용 \(\hat{r}(u,i)=\frac{\sum_{u^{'}\in \Omega_i}sim(u, u^{'})r(u^{'},i)}{\sum_{u^{'}\in \Omega_{i}}sim(u,u^{'})}\) Absolute Rating의 한계

• 유저가 평점을 주는 기준이 제각기 다름
• 긍정적 유저: 대부분 5점을 주고 부정적인 평가로는 3점을 줌
• 부정적 유저: 대부분 1~2점을 주고 많이 줘봐야 4점을 줌

상대적 평점(Relative Rating)의 개념

유저의 평균 평점에서 얼마나 높고 낮은지, 그 편차(Deviation)를 사용 \(dev(u,i)=r(u,i)-\overline{r_u} \ for\ known\ rating\)

Relative Rating Formula

모든 평점 데이터를 deviation 값으로 바꾼 뒤 원래의 rating이 아닌 deviation을 예측한다

predicted rating = 유저 평균 rating + predicted deviation \(dev(u, i)=r(u,i)-\overline{r_u}\ for\ known\ rating\)

\[\widehat{dev}(u,i)=\frac{\sum_{u^{'}\in \Omega_i}dev(u^{'},i)}{|\Omega_i|}=\frac{\sum_{u^{'}\in \Omega_i}r(u^{'},i)-\overline{r_{u^{'}}}}{|\Omega_i|}\] \[\hat{r}(u,i)=\bar{r}_u+\frac{\sum_{u^{i}\in \Omega_i}r(u^{'},i)-\overline{r_{u^{'}}}}{|\Omega_i|}=\overline{r_u}+\widehat{dev}(u,i)\] \[\hat{r}(u,i)=\overline{r_u}+\frac{\sum_{u^{'}\in \Omega_i}sim(u, u^{'})\{r(u^{'},i)-\overline{r_{u^{'}}}\}}{\sum_{u^{'}\in \Omega_{i}}sim(u,u^{'})}\]

4.2 IBCF - Absolute/Relative Rating

아이템의 집합을 사용한다는 점이 UBCF와 다르다

Absolute Rating \(\hat{r}(u,i)=\frac{\sum_{i^{'}\in \phi_u}sim(i, i^{'})r(u,i^{'})}{\sum_{i^{'}\in \phi_{u}}sim(i,i^{'})}\) Relative Rating \(\hat{r}(u,i)=\overline{r_i}+\frac{\sum_{i^{'}\in \phi_u}sim(i, i^{'})\{r(u,i^{'})-\overline{r_{i^{'}}}\}}{\sum_{i^{'}\in \phi_{u}}sim(i,i^{'})}\)

4.3 Top-N Recommendation

CF in Recommendation System

• Collaborative Filtering의 최종 목적
  • 유저 $u$가 아이템 $i$에 부여할 평점을 예측하는 것
• Recommendation System의 최종 목적
  • 예측 평점이 높은 아이템을 유저에게 추천하는 것
  • Top-N recommendation

Top-N Recommendation

타겟 유저에 대한 아이템의 예측 평점 계산이 완료되면 높은 순으로 정렬하여 상위 N개만 뽑아 추천