[RecSys] 추천 시스템 - 협업 필터링 (Collaborative Filtering) - NBCF

Collaborative Filtering (CF)

1. CF 문제 정의

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

 

더 많은 유저/아이템 데이터가 축적될수록 협업의 효과는 커지고, 추천은 정확해질 것이라는 가정에서 출발

→ DL에서 데이터가 많으면 좋다는 거랑 같은 의미로 봐도 됨

예시1) "노트북"을 본 유저에게 "다른 노트북 상품"들을 추천

예시2) "노트북"을 구매한 유저들이 구매한 "노트북 악세사리 상품"을 추천

 

CF의 최종 목적: 유저 u가 아이템 i에 부여할 평점을 예측하는 것

 

<방법>

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

 

일반적으로 행렬의 대부분 값이 비어있을 수 밖에 없음

→ 유저가 아직 소비하지 않은 아이템, ...

 

예시)

넷플릭스 이용자가 1억명이라고 할 때, 1명이 평균 100편에 영화를 본다고 가정

→ 한 영화에 (1억 - 100) 만큼 비어있다고 볼 수 있음

 

---

2. CF 원리

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

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

 

예시)

유저 A가 a, b라는 아이템을 선호하고, 유저 B도 a, b라는 아이템을 선호한다고 가정

→ 유저 A가 c라는 새로운 아이템을 선호하게 되면, 유저 B에게 c라는 아이템을 추천해주는 방식

→ 반대로 유저 A가 c라는 아이템을 선호하지 않으면, 유저 B에게도 c라는 아이템을 추천하지 않음

 

---

3. CF 분류

 

Neighborhood-based CF (Memory-based CF)

• User-based CF (UBCF)
• Item-based CF (IBCF)

 

Model-based CF

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

 

Hybrid CF

• Content-based Recmommendation과의 결합

---

Neighborhood-based CF

NBCF의 최종 목적: 유저 u가 아이템 i에 부여할 평점을 예측하는 것 (CF의 최종 목적)

 

특징

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

사실 Scalability나 Sparsity는 RecSys의 모든 모델이 짊어지고 있는 문제임

 

Sparsity: Sparse Matrix (희소 행렬) 문제

 

<참고>

NBCF를 적용하려면 Sparsity Ratio가 99.5%를 넘지 않는 것이 좋음

→ 그렇지 않으면, 모델 기반 CF를 사용해야 함

---

1. User-based CF

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

 

• 두 유저가 얼마나 유사한 아이템을 선호하는가?
• 유저 간 유사도를 구한 뒤, 타겟 유저와 유사도가 높은 유저들이 선호하는 아이템을 추천

	아이언맨	헐크	스타워즈	비포선라이즈	노팅힐
유저 A	5	4.5	5	2	1
유저 B	4	5	?	1	2
유저 C	2	1	1	4	5
유저 D	4	2	3	2	4

예시로 이해해보자

1. 딱 봤을 때, 유저 A와 유저 B의 각 영화에 대한 선호도가 유사함
2. 둘 다 아이언맨과 헐크는 높은 점수를 주었고, 비포선라이즈와 노팅힐은 낮은 점수를 주었음
3. 이때, 유저 A가 스타워즈에 높은 점수를 주었으므로, 유저 B도 비슷하게 높은 점수를 줄 것이라고 예측!

---

2. Item-based CF

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

 

• 두 아이템이 유저들로부터 얼마나 유사한 평점을 받았는가?
• 아이템간 유사도를 구한 뒤, 타겟 아이템과 유사도가 높은 아이템 중 선호도가 큰 아이템을 추천

	아이언맨	헐크	스타워즈	비포선라이즈	노팅힐
유저 A	5	4.5	5	2	1
유저 B	4	5	?	1	2
유저 C	2	1	1	4	5
유저 D	4	2	3	2	4

예시로 이해해보자

1. 딱 봤을 때, 스타워즈는 아이언맨과 헐크에 유사도가 높음

2. 유저 B는 아이언맨과 헐크에 높은 점수를 준 것과 유사하게 스타워즈에도 높은 점수를 줄 것라고 예측!

---

K-Nearest Neighbors CF

1. K-Nearest Neighbors CF

K-Nearest Neighbors CF (KNN CF)

 

예시)

1NN CF: 한 유저(B)에 대해 가장 유사한 다른 유저 1명(A)의 평점 데이터를 이용해서 평점을 예측한다.

	아이언맨	헐크	스타워즈	비포선라이즈	노팅힐
유저 A	5	4.5	5	2	1
유저 B	4	5	? → 5	1	2
유저 C	2	1	1	4	5
유저 D	4	2	3	2	4

 

얼마나 유사한지는 어떻게 알 수 있을까?

---

2. Similarity Measure

 

여러가지 Similarity Measure(유사도 측정법)을 사용하면 됨!

→ 일반적으로 거리의 역수 개념을 사용함

 

(1) Mean Squared Difference Similarity (MSD)

유저-아이템 rating에 대하여,

 

유저간

$$ msd(u, v) = \cfrac{1}{|I_{uv}|} \cdot \sigma_{i \in I_{uv}} (r_{ui} - r_{vi})^2 , msd\_sum(u, v) = \cfrac{1}{msd(u, v) + 1} $$

 

아이템간

$$ msd(i, j) = \cfrac{1}{|I_{ij}|} \cdot \sigma_{i \in I_{ij}} (r_{ui} - r_{uj})^2 , msd\_sum(i, j) = \cfrac{1}{msd(i, j) + 1} $$

 

• 유사도는 유클리드 거리에 반비례
• 분모에 1 더한 건 Inf 방지

 

(2) Cosine Similarity

 

$$ \cos (\theta ) =   \dfrac {X \cdot Y} {\left\| X\right\| _{2}\left\| Y\right\| _{2}}  $$

 

• 두 벡터가 가리키는 방향이 얼마나 유사한지
• 방향이 같으면 1, 정반대이면 -1

(3) Pearson Similarity

$$ pearson\_sim(X, Y) = \cfrac{\sum_{i=1}^N (X_i - \overline{Y})}{\sqrt{\sum_{i=1}^N (X_i - \overline{X})^2} \sqrt{\sum_{i=1}^N (Y_i - \overline{Y})^2}} $$

 

각 벡터를 표본 평균으로 정규화한 뒤에 코사인 유사도를 구한 값

→ 크기 차이 (scale)을 고려하기 때문에 좀 더 Robust하게 평가 성능이 나옴

→ 1에 가까울수록 양의 상관관계, 0일 때 서로 독립, -1에 가까울수록 음의 상관관계

 

(4) Jaccard Similarity

$$ J(A, B) = \cfrac{|A \cap B|}{|A \cup B|} = \cfrac{|A \cap B|}{|A| + |B| - |A \cap B|} $$

 

• Cosine이나 Pearson 유사도와 달리 길이(차원)이 달라도 유사도 계산 가능
• 두 집합이 같은 아이템을 얼마나 공유하고 있는가!
• 두 집합의 아이템이 모두 같으면 1, 같은 게 없으면 0

---

Rating Prediction

최종적으로 CF로 평점(Rating)을 어떻게 예측할까?

 

1. Absolute Rating

(아래 내용은 User-Based CF인데, Item-Based CF도 같은 방식으로 적용하면 됨)

 

해당 유저(B)와 다른 유저들(A, C, D)의 유사도 값을 Weight로 사용해서 Weighted Average를 구하자

 

	아이언맨	헐크	스타워즈	비포선라이즈	노팅힐
유저 A	5	4.5	5	2	1
유저 B	4	5	?	1	2
유저 C	2	1	1	4	5
유저 D	4	2	3	2	4

$$ \text{?} = \frac{\sum_{u} sim(u_{B} , u) \cdot r_{u, i}}{\sum_{u} (u_{B} , u)} $$

 

 

전체 유저 $ U $, 아이템 $ I $에 대한 평점 데이터가 존재하고,

아이템 $ i $ 에 대한 평점이 있으면서 유저 $ u $와 유사한 유저들의 집합을 $ \Omega_{i} $라고 할 때,

 

유저 $ u $의 아이템 $ i $에 대한 평점 $ \hat{r} (u, i) $를 예측해보자

 

$$ \text{Average}: \hat{r}(u, i) = \cfrac{\sum_{u' \in \Omega_i} r(u', i)}{|\Omega_i|} $$

 

$$ \text{Weighted Average}: \hat{r}(u, i) = \cfrac{\sum_{u' \in \Omega_i} sim(u, u') r(u', i)}{\sum_{u' \in \Omega_i} sim(u, u')} $$

 

---

 

2. Relative Rating

 

Absolute Rating의 한계: 유저마다 평점을 주는 기준이 다름 (scale이 다름)

→ Relative Rating(상대점 평점)을 도입하자

→ 유저의 평점 평균보다 얼마나 높거나 낮은지 편차(Deviation)을 사용하면 됨

→ 모든 평점 데이터를 $ dev $로 바꾼 뒤에 $ r $ 대신  $ dev $를 사용하여 예측하자

 

predicted rating = 유저 평균 rating + predicted deviation

 

$$ dev(u, i) = r(u, i) - \overline{r_u} $$

 

$$ \hat{dev}(u, i) = \cfrac{\sum_{u' \in \Omega_i} dev(u', i)}{|\Omega_i|} = \cfrac{\sum_{u' \in \Omega_i} r(u', i) - \overline{r_{u'}}}{|\Omega_i|} $$

 

$$ \hat{r}(u, i) = \overline{r_u} + \cfrac{\sum_{u' \in \Omega_i} r(u', i) - \overline{r_{u'}}}{|\Omega_i|} = \overline{r_u} + \hat{dev}(u, i) $$

 

 

Weighted Average Prediction

 

1) Absolute Rating

$$ \hat{r}(u, i) = \cfrac{\sum_{u' \in \Omega_i} sim(u, u') r(u', i)}{\sum_{u' \in \Omega_i} sim(u, u')} $$

 

2) Relative Rating

$$ \hat{r}(u, i) = \overline{r_u} + \cfrac{\sum_{u' \in \Omega_i} sim(u, u') \{r(u', i)- \overline{r_{u'}}\}}{\sum_{u' \in \Omega_i} sim(u, u')} $$

 

이렇게 CF의 최종 목적인 유저 u가 아이템 i에 부여할 평점 예측이 끝남!

→ 이 이후에는 RecSys의 최종 목적이 예측 평점이 높은 아이템을 유저에게 추천하는 것

→ Top-N Recommendation