# Neighborhood Collaborative Filtering (NCF)

Trong cách tiếp cận này thì ta gọi ma trận U (utility matrix) là ma trận gồm n hàng và m cột. Trong đó n là số lượng user và m là số lượng item. Mỗi ô trên ma trận sẽ là giá trị rating của user giành do item tương ứng. Đối với trường hợp user chưa đánh giá item thì giá trị sẽ là không (tương ứng với việc chưa được đánh giá).
Phương án NCF bao gồm 2 phương án chính:
- User based: Phương án này sẽ dựa trên sự tương đồng trong rating giữa các user để đưa ra dự đoán. Cụ thể để lấy các item gợi ý cho 1 user i nào đó thì chúng ta sẽ dựa vào các user khác tương đồng với user i và sử dụng đánh giá của những người này để lựa chọn những gợi ý cho user i.
- Item based: Phương án này sẽ dựa trên sự tương đồng trong rating đối với các item để đưa ra dự đoán. Nó cũng gần giống với phương án sử dụng user based, chỉ khác là ở đây chúng ta sẽ xét sự tương đồng cho các item.

Ở đây dù tiếp cận theo cách nào thì về mặt cơ bản, cách cài đặt 2 phương pháp này vẫn sẽ là như nhau nên ở đây sẽ chỉ trình bày cho phương án User based.

Đầu tiên mỗi hàng của ma trận $U$ sẽ là một vector biểu diễn cho mỗi user $u_i$. Khi đó ta thấy rằng, để tìm các user khác tương đồng với user $i$ nào đó thì ta chỉ cần dựa trên việc so sánh vector với một số thang đó cụ thể. Ở đây ta có khá nhiều các phương án khác nhau, có thể kể đến: cosin, khoảng cách Euler, hệ số tương quan... Ở trong đồ án này thì vì lý do thời gian nên sẽ sử dụng khoảng cách cosin. Ta gọi $sim(i, j)$ là mức độ tương đồng giữa user $i$ và user $j$, khi đó ta có:
$$sim(i, j) = \frac {u_i * u_j} {||u_i|| ||u_j||}$$

Thực tế thì ta sẽ có biểu thức trên tương đương với việc tính hệ số tương quan cho các vector $u_i$ đã được chuẩn hoá, ta sẽ nói thêm về phần này ở sau đó. Ở đây ta sẽ luôn có $-1 \leq sim(i, j) \leq 1$.
- Ở đây $sim(i, j)$ càng gần 1 thì giữa 2 user $i$ và $j$ có quan hệ tương hỗ, tức là những bộ phim mà user $i$ có xu hướng thích thì user $j$ cũng có xu hướng thích bộ phim đó (dựa trên rating).
- Trường hợp $sim(i, j)$ càng gần -1 thì giữa user $i$ và user $j$ có quan hệ đối kháng, nghĩa là những bộ phim mà user $i$ đánh giá cao thì user $j$ lại có xu hướng không thích các bộ phim này.
- Trường hợp khi $sim(i, j) \sim 0$ thì giữa user $i$ và user $j$ sẽ có rất ít sự liên hệ.

Khi đã tính được $sim(i, j)$ thì để tìm được các user có độ tương đồng cao nhất với 1 user $i$ cho trước, ta sẽ sắp xếp các giá trị này theo giá trị tăng dần trị tuyệt đối của $|sim(i, j)|$. Lúc này ta sẽ có nhiều phương án để chọn ra danh sách các user tương đồng với user $i$:
- Ta sẽ chọn top $k$ user có độ tương đồng cao nhất, việc thay đổi $k$ sẽ phần nào đó ảnh hưởng đến mô hình.
- Ta sẽ cho một mức tương đồng tối thiểu và chọn hết những user $j$ có mức độ tương đồng cao hơn mức này, tất nhiên, điều này trong thực tế sẽ có trường hợp mức này chọn quá cao và dẫn tới không có bất kỳ user nào nằm trong danh sách, hoặc mức này được sắp xếp quá thấp khiến cho danh sách này chứa gần như toàn bộ user.

Sau khi đã có mức độ tương đồng và danh sách các user tương đồng, gọi $score(i, j)$ là rating dự đoán của user $i$ dành cho item $j$, ta có thể dự đoán rating của user $i$ cho một item $j$ nào đó như sau:
$$score(i, j) = \bar{r_i} + \frac {\sum_{k} sim(i, k) (r_{kj} - \bar{r_k})} {\sum_{k} |sim(i, j)|}$$
Trong đó:
- $\bar{r_i}$ là giá trị rating trung bình của user $i$.
- $r_{kj}$ là đánh giá của user $k$ giành cho item $j$.

Ở đây ta sẽ tách phần rating trung bình của user ra riêng bởi vì các user khác nhau thì có mức độ đánh giá khác nhau. Một số user họ dễ tính thì rating của họ sẽ thường cho cao. Với một số user khác đòi hỏi khắt khe hơn thì sẽ yêu cầu nhiều yếu tố để đánh giá một bộ phim, do đó phần đánh giá của họ sẽ có phần khác biệt. Để hạn chế những điều này thì ta sẽ đưa toàn bộ đánh giá về cùng một thang đó, như vậy ta sẽ giảm mức độ ảnh hưởng của điều này. Một vấn đề khác nảy sinh đó là giá trị $score(i, j)$ sẽ có thể nằm ngoài thang đo hiện có, chẳng hạn nếu ta có đánh giá từ 1-5 thì $score(i, j)$ hoàn toàn có thể bé hơn 1 hoặc lớn hơn 5. Trong những trường hợp này thì ta sẽ chỉ cần làm tròn $score(i, j)$ về giá trị gần nhất với nó nằm trong khoảng đánh giá 1-5.

Ở đây thông thường để hệ thống hoạt động hiệu quả với một lượng truy cập lớn thì ta sẽ tính sẵn hệ số tương quan giữa từng cặp $(i, j)$. Và giữ các giá trị này trong 1 khoảng thời gian, (điều này nghĩa là khi user $i$ có 1 lượt đánh giá mới cho một item nào đó thì ta sẽ không cập nhật lại ngay việc này), chẳng hạn 1 tuần hay hơn, vì nhìn chung số lượng rating của user đánh giá là không quá nhiều, ngoài ra nếu chỉ mỗi user có thêm vài lượt đánh giá thì nhìn chung dự đoán rating sẽ không thay đổi quá nhiều. Tuy nhiên ở đây chúng ta sẽ gặp phải 1 vấn đề tương đối lớn, đó là khi số lượng user quá nhiều thì sẽ có đến $O(n^2)$ cặp $(i, j)$ cần phải tính, tuy nhiên ta cũng sẽ nhận ra rằng việc tính hết các cặp này trong thực tế lại không quá cần thiết vì chúng ta sẽ chỉ sử dụng 1 lượng nhỏ các user tương đồng để dự đoán mà thôi. Khi đó ta sẽ có ý tưởng đó là chia các user đã cho thành các cụm, và việc tìm các user tương đồng thay vì tìm trên toàn bộ các user thì lúc này ta sẽ chỉ cần tìm trong cụm. Hiệu quả của việc này sẽ phụ thuộc nhiều vào quá sự phân bố của cụm, các user phân bố càng đều vào cụm thì quá trình tính toán sẽ càng nhanh và ngược lại.

Một vấn đề nữa của phương pháp tiếp cận kiểu NCF đó là chúng ta sẽ cần phải lưu 1 ma trận có kích thước lớn tuy nhiên phần lớn các giá trị trong ma trận lại nhận giá trị 0. Do đó khi số lượng user nhân với số lượng item lớn thì lượng bộ nhớ sử dụng cho phương pháp này sẽ rất lớn. Trong đồ án này, vì giới hạn bộ nhớ và tốc độ tính toán của Colab nên dataset sử dụng sẽ chỉ là dataset movie lens 100k. Để giảm lượng bộ nhớ cần dùng thì ta có thể sử dụng phương pháp Matrix Factorization, tuy nhiên do thời gian có hạn nên phương pháp này sẽ xem như là một hướng mở.