> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/data-mining/recommender-system.md).

# Recommender System

## Utility Matrix

$$R$$: utility matrix

<table><thead><tr><th width="149">Users \ Items</th><th>Avatar</th><th>LOTR</th><th>Matrix</th><th>Pirates</th></tr></thead><tbody><tr><td>Alice</td><td>5</td><td></td><td>2</td><td></td></tr><tr><td>Bob</td><td></td><td>4</td><td></td><td>3</td></tr><tr><td>Carol</td><td>1</td><td></td><td>5</td><td></td></tr><tr><td>David</td><td></td><td></td><td></td><td>2</td></tr></tbody></table>

* $$R=|U| \times |I|$$
* $$U$$: set of users
* $$I$$: set of items

### problem

* $$R$$ is sparse
* cold start problem
  * 새로운 item들에 대한 rating이 없음
  * 새로운 user들에 대한 기록이 없음

## Recommender Systems

### 1. Content Based

* 사용자가 이전에 높은 평가를 준 아이템과 **유사한 아이템**을 추천
* 아이템 간 유사성을 계산하기 위해 아이템의 특성(feature)을 활용
* 텍스트 기반의 데이터를 다룰 경우, 문서에서 중요한 단어를 추출해야 하며, 이를 위해 **TF-IDF** 사용

#### TF-IDF

$$\text{TF-IDF}=w\_{id}=TF\_{id} \times IDF\_i$$, 값이 클수록 해당 단어의 중요도가 높은 것

* TF(Term Frequency)
  * 특정 단어가 문서 내에서 얼마나 자주 등장하는지를 나타냄
  * $$TF\_{id}=\frac{f\_{id}}{max\_k f\_{kd}}$$, $$f\_{id}$$: document $$d$$에 있는 term $$i$$의 빈도수
* IDF(Inverse Document Frequency)
  * 특정 단어가 전체 문서에서 얼마나 드물게 나타나는지를 나타냄
  * 한 documnet에서만 나타나는 word가 중요하다는 것
  * inverse 하는 이유는 모든 document에서 발현되면 중요도를 줄이기 위함
  * $$IDF\_i=log(\frac{N}{n\_i})$$, term $$i$$가 총 document 개수 $$N$$의 $$n\_i$$에서의 빈도수

**e.g. Document A=\[b a b c a a], B=\[a b c], C=\[a d e f], D=\[a d e g]**

A: {a:3, b:2, c:1} -> 각 item이 document A에서 나타난 개수

* $$TF\_{aA}=\frac{a=3}{max(a=3, b= 2, c=1)}=\frac{3}{3}=1$$
* $$TF\_{bA}=\frac{b=2}{max(a=3,b=2,c=1)}=\frac{2}{3}$$

A, B, C, D: {a: 4, b: 2, c: 2, d: 2, e: 2, f: 1, g: 1} -> 각 item이 나타난 document의 개

* $$IDF\_a=log(\frac{N=4}{a=4})=log(\frac{4}{4})=0$$
* $$IDF\_g=log(\frac{N=4}{g=1})=log(\frac{4}{1})=log4$$

#### Heuristic

$$R\_{xi}=cos(x,i)=\frac{x^Ti}{||x|| \ ||i||}$$

* $$x$$: user profile, 사용자의 이전 활동으로부터 생성된 프로필 (e.g. 관심사, 과거 평점)
* $$i$$: item profile, 아이템의 특성을 나타내는 프로필 (e.g. 키워드, 장르, 카테고리)

#### 특징

* 장점
  * 다른 사용자의 데이터 필요 없음
  * 새롭고 인기 없는 아이템 추천 가능
* 단점
  * 적절한 특징(feature)를 찾기 어려움
  * 사용자의 컨텐츠 프로필을 벗어난 항목을 추천하지 않

### 2. Collaborative Filtering

* 나와 비슷한 선호도를 가진 user를 기반으로 추천
* user-user collaborative filtering
* item-item collaborative filtering

#### user-user collaborative filtering

나와 유사한 user가 rating한 것을 기반으로 rating

* centered cosine similarity(=pearson correlation coefficient: 선형 관계 데이터만 설명 가능)

  1. normalize as rating - mean of row rating
  2. cosine similarity

  $$r\_{xi}=\frac{\sum\_{y \in N}S\_{xy}r\_{yi}}{\sum\_{y \in N}S\_{xy}}$$

  * $$x, y$$: user
  * $$S\_{xy}=sim(x,y)$$

#### e.g. N=2일때, user1의 item5에 대한 rate을 예측하여라

| users \ items | item1 | item2 | item3 | item4 | item5 |
| :-----------: | :---: | :---: | :---: | :---: | :---: |
|     user1     |   1   |   5   |   3   |   3   |   ?   |
|     user2     |   1   |   4   |       |       |   4   |
|     user3     |   4   |   4   |   3   |       |   5   |
|     user4     |   1   |   4   |       |       |   5   |

1. 각 user 별 평균 계산

* $$\overline{user1}=\frac{1+5+3+3}{4}=3$$
* $$\overline{user2}=\frac{1+4+4}{3}=3$$
* $$\overline{user3}=\frac{4+4+3+5}{4}=4$$
* $$\overline{user4}=\frac{1+4+5}{3}=3.3$$

2. null 값이 아닌 경우 평균을 빼주고 null 값인 경우 0으로 정규화

|       | item1 | item2 | item3 | item4 | item5 |
| :---: | :---: | :---: | :---: | :---: | :---: |
| user1 |   -2  |   2   |   0   |   0   |   0   |
| user2 |   -2  |   1   |   0   |   0   |   1   |
| user3 |   0   |   0   |   -1  |   0   |   1   |
| user4 |  -2.3 |  0.7  |   0   |   0   |  1.7  |

3. cosine similarity 계산(소숫점 둘째자리 반올림)

* $$sim(user1, user2)=\frac{-2\times-2+2\times1+0\times0+0\times0+0\times1}{\sqrt{(-2)^2+2^2+0^2+0^2+0^2}\sqrt{(-2)^2+1^2+0^2+0^2+1^2}}=0.87$$
* $$sim(user1, user3)=0$$
* $$sim(user1, user4)=0.72$$

4. rate 계산

* user1과 가장 유사한 2명의 user는 user2(sim=0.87)과 user4(sim=0.72)
* $$item5(user1)=\frac{0.87 \times 4 + 0.72 \times 5}{0.87+0.72}=4.45$$

#### item-item collaborative filtering

* 예측하고자 하는 item과 유사한 item에 대해 user가 rating한 것을 기반으로 rating
* user-user와 계산 방식 동일(user x item을 item x user로 바꿔 계산)
* user-user 보다 더 나은 성능을 보임(user는 다양한 취향이 고려되어야하는 반면 item은 단순함)

#### baseline predictor collaborative filtering

* $$r\_{xi}=b\_{xi}+\frac{\sum\_{j \in N(i:x)}S\_{ij}r\_{xj}}{\sum\_{j \in N(i:x)}S\_{ij}}$$
  * $$b\_{xi}=\mu+b\_x+b\_i$$: user
  * $$S\_{ij}=sim(i,j)$$
  * $$N(i:x)$$: user $$x$$가 item $$i$$와 유사하게 rating한 item의 집합
  * $$b\_x$$: user $$x$$의 rating 편차
  * $$b\_i$$: item $$i$$의 rating 편차

#### example

* $$\mu=3.7, b\_i=0.5, b\_x=-0.2$$
* $$b\_{xi}=3.7+0.5+(-0.2)=4.0$$

### 3. Latent Factor Models

* $$R$$을 $$P(items\times factors)$$와 $$Q(factors\times users)$$로 decomposition
* $$R\_{xi} = Q\_i \cdot P\_x$$
  * $$Q\_i$$: $$Q$$의 row $$i$$
  * $$P\_i$$: $$P^T$$의 col $$x$$

<figure><img src="/files/FlwEVLWnPeYxGQFURIjf" alt=""><figcaption></figcaption></figure>

만약, item1에 대한 user5의 rate을 예측한다면 → $$R\_{5,1}=\[0.1, -0.4, 0.2]\cdot\[-2,0.3,2.4]=3.4$$

#### Stochastic Gradient Descent

**concept**

* gradient descent: $$f(x)$$ 값이 최소가 되는 $$x$$를 찾는 과정
  1. graidnet($$\triangledown f(x)$$) 계산
  2. $$x'=x-\eta \triangledown f(x), \ \eta: \text{learning rate}$$
  3. $$x=x'$$
  4. until convergence: $$|x'-x|<\epsilon \ or \ \text{set number of iterations}$$
* stochastic gradient descent
  * gradient descent는 전체 학습 데이터셋을 이용해 에폭 한번 당 gradient를 업데이트(비효율적)
  * stochastic gradient descent는 batch size로 학습 데이터 안에 subset 데이터를 만들고 이를 이용해 gradient를 업데이트(효율적)

**loss**

* $$J(P,Q)=min\_{P,Q} \ \sum\_{(x,i)\in R}(r\_{xi}-q\_ip\_x)^2+\[\lambda\_1 \sum\_x ||p\_x||^2 + \lambda\_2 \sum\_i ||q\_i||^2]$$
* $$J(P,Q,b)=min\_{P,Q,b} \ \sum\_{(x,i)\in R}(R\_{xi}-\hat{R}\_{xi})^2+\lambda\[\sum\_x ||p\_x||^2\_2 + \sum\_i ||q\_i||^2\_2 + \sum\_x ||b\_x||^2\_2 + \sum\_i ||b\_i||^2\_2]$$
  * $$\hat{R}\_{xi}=\mu+b\_x+b\_i+q\_ip\_x$$

### Correlation

**e.g. study times과 exam score 사이의 상관관계**

| student | study times | exam score |
| :-----: | :---------: | :--------: |
|    A    |      10     |     75     |
|    B    |      8      |     60     |
|    C    |      12     |     85     |
|    D    |      6      |     55     |
|    E    |      7      |     90     |

* Pearson Correlation: 선형 관계 측정, 이상치에 민감(크기 정보 활용하기 때문)
  1. calculate mean of data
     * study times: $$\frac{10+8+12+6+7}{5}=8.6$$
     * exam score: $$\frac{75+60+85+55+90}{5}=73$$
  2. substract

     | student | study times | exam score |
     | :-----: | :---------: | :--------: |
     |    A    |     1.4     |      2     |
     |    B    |     -0.6    |     -13    |
     |    C    |     3.4     |     12     |
     |    D    |     -2.6    |     -18    |
     |    E    |     -1.6    |     17     |
  3. cosine similarity
     * $$r=\frac{1.4\times 2+(-0.6)\times(-13)+3.4\times12+(-2.6)\times(-18)+(-1.6)\times17}{\sqrt{1.4^2+(-0.6)^2+3.4^2+(-2.6)^2+(-1.6)^2}\sqrt{2^2+(-13)^2+12^2+(-18)^2+17^2}}$$
     * $$r=0.4$$
* Spearman’s Rank Correlation: 단조 관계 측정, 이상치에 덜 민감(순위 정보 활용하기 때문)
  1. rank data

     | student | Rank(study times) | Rank(exam score) |
     | :-----: | :---------------: | :--------------: |
     |    A    |         2         |         3        |
     |    B    |         3         |         4        |
     |    C    |         1         |         2        |
     |    D    |         5         |         5        |
     |    E    |         4         |         1        |
  2. calculate
     * $$D\_i=\text{Rank of study times}\_i-\text{Rank of exam score}\_i$$

       | student | $$D\_i$$ |
       | :-----: | :------: |
       |    A    |    -1    |
       |    B    |    -1    |
       |    C    |    -1    |
       |    D    |     0    |
       |    E    |     3    |
  3. calculate
     * $$\rho=1-\frac{6 \sum\_i (D\_i)^2}{n(n^2-1)}=1-\frac{6\[(-1)^2+(-1)^2+(-1)^2+0^2+3^2]}{5(5^2-1)}$$
     * $$\rho=1-0.6=0.4$$