1. Collaborative Filtering
Collaborative Filtering : behavior-based(user interation) recommendation
- 아이템의 속성을 무시
- user-item interaction에 주목 : 어떤 사람이 유저가 구매한 아이템을 좋아하는지
장점
1. 추천되는 특정 아이템의 내용과 무관하게 작동하는 알고리즘
2. "두산 베어스 굿즈를 전부 산 유저들이 마라탕을 좋아한다" 같은 흥미로운 패턴들도 찾을 수 있음
2. Neighborhood-based Collaborative Filtering
- 유저의 성향과 아이템의 유사도로 선호도를 예측
- 비슷한 성향을 가진 유저가 소비한 아이템을 추천해줌
3. User-based Collaborative Filtering
> Scoring Functions
유저 집합 U와 아이템 집합 I에 대해 sparse한 평점 행렬 \( R \in \mathbb{R}^{|\mathcal{U}|\times|\mathcal{I}|} \) 이 주어졌을 때
아이템 i에 대한 유저 u의 점수를 예측 :
> 가중치(혹은 simialrity 행렬) \( w_{uv}\)
얼마나 강한 상관관계를 가지고 있는지... 모델링하는 방법
- Pearson 상관관계
- 두 벡터 \( r_u - \bar{r}_u \)와 \( r_v - \bar{r}_v \) 사이의 코사인 유사도
높은 \( w_{uv}\)를 가진 이웃 유저들은 다음과 같은 \( \mathcal{V}\)로 선택할 수 있다.
- top-k neighbors
- \( w_{uv} > w_{threshold}\) 인 이웃
- \( w_{uv} > 0\) 인 이웃
- 아이템 i를 평가한 유저
> Z-normalization score prediction
> Implementation Issue : Bottleneck
\( m = |\mathcal{U}|\) 유저와 \( n = |\mathcal{I}|\) 아이템일 때
- 두 유저 간의 상관 관계 : O(n)
- 유저에 대한 모든 상관관계 : O(mn)
- 모든 pairwise 상관관계 : O(m^2n)
- 추천에 드는 최소 시간 : O(mn)
=> Too heavy!
> 좀 더 practical 하게 하는 방법
1. Top-k 이웃으로 제한 (\( m \rightarrow k\))
2. Cached 또는 Incremental correlations
> 한계
1. Issues of Sparsity
아이템의 수는 많은데 유저에게 평가 되는 경우는 매우 적음
평가가 없는 경우가 많음
2. Computational Performance
수 만 명의 유저의 pairs correlations를 계산하는 비용은 매우 비쌈
Incremental approach를 해도 비쌈
User profile은 계속 바뀜 - 유저를 만족시키기 위해서 real-time 계산을 해야함. 미리 계산 불가.
4. Item-based Collaborative Filtering
* Item-Item 유사도는 stable하다.
- # of items : 일반적으로 아이템의 수 < 유저의 수
- Rating sparsity : 평균적으로 아이템의 평가 수 > 유저의 평가 수
- Profile of item : 아이템의 프로필은 급하게 변하지 않는다.
* 아이템의 유사도는 아이템에 대한 유저의 선호도를 계산하는데 이용할 수 있다.
> 방법
1단계 : 아이템 쌍 사이의 유사도를 계산
- Item rating vector 간의 상관관계
- Co-rated 인 경우만 (multi-level ratings)
- Item rating vector의 코사인
- multi-level & unary rating 둘 다에 사용 가능.
- 또는 조정된 ratings (코사인을 계산하기 전 정규화 등)
- 조건부 확률 (unary ratings)
2단계 : User-item rating scores 예측
- 평가된 "item-neighbors" 의 가중치 적용된 합(weighted sum)
- rating을 추정하기 위한 Linear regression
> Scoring function
아이템에 이웃하는 아이템에 기반하여 점수를 매김
1. 유저가 평가한, 비슷한 아이템을 찾는다. (유저 u가 평가한 아이템의 집합 \(N(i;u)\))
2. 가준치가 적용된 유저의 평균 ratings를 계산 (\(\bar{r}_i\))
3. 정규화 된 ratings를 평균낸 후, 역정규화 한다.
linear regression 같은 다른 방법을 고려할 수도 있음
> Item correlations or similarity
보통 item rating vector 간의 코사인 유사도를 사용한다.
우선 유저의 ratings를 정규화 한다.
- 평균 빼기 ( \(\hat{r}_{ui} = r_{ui} - \bar{r}_i \) , \(\hat{r}_{uj} = r_{uj} - \bar{r}_j \) )
- 없는 값은 0으로 취급
- 피어슨 상관계수
score 계산하는 거 해보기!
> 이웃 선택 방법
이웃들은 보통 유저가 평가한 아이템 등으로 유사한 아이템들이다. 유사한 아이템 이웃들 중에서 k 개로 수를 한정할 수 있는데 적당한 크기의 k를 사용하는 것이 중요하다.
- 너무 작은 k : 정확하지 않은 점수
- 너무 큰 k : 노이즈가 심함
- k=20 정도가 보통 잘 작동함
> 모델 만들기
모든 아이템 쌍 사이의 유사도를 미리 계산
- 아이템은 유저에 비해서 정적이기 때문에 미리 유사도를 계산해도 유효하다.
Naively : \( O(n^2) = O(|\mathcal{I}|^2)\)
- 만약 대칭(symmetric)인 경우, 한 방향만 계산하면 됨
- 대부분의 similarity 함수들은 쌍을 건너 뛰어도 됨
Initialize W(item pairwise) to empty weight matrix
for i ∈ ℐ
for j ∈ ℐ s.t. i ≠ j
if sim(i,j) > 0
w_ij ← sim(i,j)
Clear all but M largest values of row w_i
Truncating model
\(n^2 \) 모델을 꼭 유지하지 않아도 된다.
유저가 모든 아이템들을 rating 하지 않았기 때문에 모델의 각 아이템은 k개의 이웃만으로 score를 계산해도 충분하다.
Non-positive 이웃을 제거하는 방법도 있다.
이 방법을 통해 accuracy, covage와 메모리 사용을 균형 맞출 수 있다.
> Unary Data (Implicit feedback)
Unary Data 예시) 클릭, 조회, 구매, 시청 ...
데이터는 logical user-item interaction 행렬로 표현할 수 있다.
이 행렬은 item-item similarity 행렬처럼 코사인 유사도를 적용할 수 있다.
Score aggregating
Weighted average는 이진 데이터(0 또는 1)에서 유효하지 않다.
그래서 이진데이터에서는 이웃과의 유사도를 합한다.
$$ S(u,i) = \displaystyle \sum_{j \in \mathcal{I}_u} w_{ij}$$
> Item-based CF의 확장
User Trust 어플리케이션에 쉽게 확장할 수 있다. User trustwortiness는 아이템 관련성 계산에 통합할 수 있기 때문이다. 유저의 전역적인(global) 명성을 사용한다.
신뢰도가 높은 유저는 더 큰 영향을 가지고 있다고 고려한다.
아이템의 유사도가 계산 되었을 때, 유저의 신뢰도에 따라 유저에게 가중치를 부여할 수 있다.
- \(p_u \) : 유저 u의 신뢰성(trustworthiness)
> Item-based CF의 장단점
장점
1. 잘 작동한다
- prediction accuarcy, top-n predictions
2. 효율적이고 직관적인 implemenation
- 유저의 수보다 아이템의 수가 적은 경우에서 pre-computability 의 장점을 갖는다.
3. 적용가능성(applicability)와 유연성
- 쇼핑 차트나 유저 프로필 같은 곳에 적용하기 용이하다.
4. 유저의 수가 훨씬 많은 도메인에서 Item-Item이 더 빠르고 안정적이다
- 안정성 덕분에 pre-compute을 할 수 있고, item-item 상관관계를 저장할 수 있음
단점
1. Item-Item은 User-User만큼 같지 않다
- 서로 많이 다른 아이템들이 추천되는 것을 item-item을 통해서 발견하기 어렵다
- 하지만 User-User의 경우, 많은 근거 없이도 가까운 유저가 선호하는 아이템을 추천할 수 있다. (동적)
- Item-Item 예측은 더 많은 데이터에 근거를 두기 때문에 less extreme(보수적, stable) 한 경향을 갖는다.
2. 추천과 예측에서 보수적(conservative)이다.
- 쇼핑이나 소비 태스크에서는 좋을 수 있다
- 하지만 검색이나 오락처럼 새롭고 최신 아이템이 선호되는 영역에서는 지치는 일 일 수 있다