Neighborhood-Based Collaborative Filtering – Recommendation Systems – Phần 2

Xin chào mọi người, ở bài viết trước thì mình đã giới thiệu qua về Hệ thống gợi ý ( Recommendation Systems ) và trong bài biết lần này mình sẽ trình bày với các bạn 1 phương pháp của Lọc cộng tác ( Collaborative Filtering ) có tên là Neighborhood-based Collaborative Filtering (NBCF)

Nội dung trong phần này

• 1. Giới thiệu
• 2. User-user Collaborative Filtering
• 3. Item-item Collaborative Filtering
• 4. Tài liệu tham khảo

Giới thiệu

Trong Content-based Recommendation Systems, chúng ta đã biết đặc điểm của Content-based Recommendation Systems là việc xây dựng mô hình cho mỗi user không phụ thuộc vào các users khác mà phụ thuộc vào profile của mỗi items. Việc làm này có lợi thế là tiết kiệm bộ nhớ và thời gian tính toán. Đồng thời, hệ thống có khả năng tận dụng các thông tin đặc trưng của mỗi item như được mô tả trong bản mô tả (description) của mỗi item. Bản mô tả này có thể được xây dựng bởi nhà cung cấp hoặc được thu thập bằng cách yêu cầu users gắn tags cho items. Việc xây dựng feature vector cho mỗi item thường bao gồm các kỹ thuật Xử lý ngôn ngữ tự nhiên (Natural Language Processing – NLP).

Cách làm trên có hai nhược điểm cơ bản. Thứ nhất, khi xây dựng mô hình cho một user, các hệ thống Content-based không tận dụng được thông tin từ các users khác. Những thông tin này thường rất hữu ích vì hành vi mua hàng của các users thường được nhóm thành một vài nhóm đơn giản; nếu biết hành vi mua hàng của một vài users trong nhóm, hệ thống nên suy luận ra hành vi của những users còn lại. Thứ hai, không phải lúc nào chúng ta cũng có bản mô tả cho mỗi item. Việc yêu cầu users gắn tags còn khó khăn hơn vì không phải ai cũng sẵn sàng làm việc đó; hoặc có làm nhưng sẽ mang xu hướng cá nhân. Các thuật toán NLP cũng phức tạp hơn ở việc phải xử lý các từ gần nghĩa, viết tắt, sai chính tả, hoặc được viết ở các ngôn ngữ khác nhau.

Những nhược điểm phía trên có thể được giải quyết bằng Collaborative Filtering (CF). Trong bài viết này, tôi sẽ trình bày tới các bạn một phương pháp CF có tên là Neighborhood-based Collaborative Filtering (NBCF). Bài tiếp theo sẽ trình bày về một phương pháp CF khác có tên Matrix Factorization Collaborative Filtering. Khi chỉ nói Collaborative Filtering, chúng ta sẽ ngầm hiểu rằng phương pháp được sử dụng là Neighborhood-based.

Ý tưởng cơ bản của NBCF là xác định mức độ quan tâm của một user tới một item dựa trên các users khác gần giống với user này. Việc gần giống nhau giữa các users có thể được xác định thông qua mức độ quan tâm của các users này tới các items khác mà hệ thống đã biết. Ví dụ, A, B đều thích phim Cảnh sát hình sự, tức đều rate bộ phim này 5 sao. Ta đã biết A cũng thích Người phán xử, vậy nhiều khả năng B cũng thích bộ phim này.

Các bạn có thể đã hình dung ra, hai câu hỏi quan trọng nhất trong một hệ thống Neighborhood-based Collaborative Filtering là:

• Làm thế nào xác định được sự giống nhau giữa hai users?
• Khi đã xác định được các users gần giống nhau (similar users) rồi, làm thế nào dự đoán được mức độ quan tâm của một user lên một item?

Việc xác định mức độ quan tâm của mỗi user tới một item dựa trên mức độ quan tâm của similar users tới item đó còn được gọi là User-user collaborative filtering. Có một hướng tiếp cận khác được cho là làm việc hiệu quả hơn là Item-item collaborative filtering. Trong hướng tiếp cận này, thay vì xác định user similarities, hệ thống sẽ xác định item similarities. Từ đó, hệ thống gợi ý những items gần giống với những items mà user có mức độ quan tâm cao.

Phương pháp này được chia thành 2 hướng nhỏ, là User-User Collaborative Filtering (uuCF) và Item-Item Collaborative Filtering (iiCF).

uuCF : Về cơ bản,anh em có thể hiểu là tìm ra những nhóm User tương tự nhau từ đó sẽ đưa ra dự đoán mực độ quan tâm của User trên các User khác cũng nhóm . Về chi tiết mình sẽ nói ỏ phần 2

iiCF : Tương tự như User-User, phương pháp này sẽ tìm ra những nhóm item tương tự nhau. Sau đó, dự đoán mức độ yêu thích của user với item dựa trên độ yêu thích của user đó với các item khác cùng loại. Về chi tiết mình sẽ nói ở phần 3

User-user Collaborative Filtering

Đầu vào của bài toán là Utility matrix và công việc quan trọng nhất trong uuCF là phải xác định được sự giống nhau giữa hai User và cách xác định sự giống nhau này dựa trên độ quan tâm với các item giữa các User. Ví dụ nhé:

Hình trên là 1 ví dụ về đầu vào là utility matrix dựa trên số sao rating của các user với item. Nhìn phát thấy luôn là User 1 và 0 cho rating về các item khá giống nhau ít ra còn giống hơn mấy các User còn lại vậy nên ta có thể đoàn rằng user 0 cũng quan tâm tới item 2 như user 1

Vậy để thuận tiện tính toán similarity giữa các User ta phải điền giá trị vào các ô ‘?’. Vậy mỗi ô ‘?’ cần được điền giá trị như thế nào để thích hợp, có thể nhiều người sẽ nghĩ đến là 0 nhưng điều này mình đánh giá sẽ ảnh hưởng khá lớn trong việc đưa ra gợi ý vì mức 0 có nghĩa đây là 1 mức khá tiêu cực đối với item. Một giá trị mình thấy rất khả quan hơn trong trường hợp này chính là giá trị trung bình cộng của các ratings mà User đã đánh giá cho các item còn lại. Ví dụ như ở user đầu ta có thể tính được giá trị trung bình này là 3.25 được tính từ trung bình cộng của 5-3-2-2. Ta sẽ tính được utility matrix

Tiếp theo chúng ta sẽ xây dựng normalized utility matrix bằng cách trừ mỗi rating đi với giá trị trung bình. Vậy tại sao lại cần bước chuẩn hóa này lại cần thiết và quan trọng như vâỵ thì rất dễ hiểu thôi:

• Việc trừ đi trung bình cộng của mỗi cột khiến trong trong mỗi cột có những giá trị dương và âm và 0 ( là giá trị chưa xác định ) . Những giá trị âm và dương này đại diện cho sự quan tâm của User đến Item là thích hoặc không thích còn 0 là đại diện cho những User không có chứng kiến =)) hiểu nôm na là chưa xác định được có thích hay không.
• Về mặt kỹ thuật, số chiều của utility matrix là rất lớn với hàng triệu users và items, nếu lưu toàn bộ các giá trị này trong một ma trận thì khả năng cao là sẽ không đủ bộ nhớ. Quan sát thấy rằng vì số lượng ratings biết trước thường là một số rất nhỏ so với kích thước của utility matrix, sẽ tốt hơn nếu chúng ta lưu ma trận này dưới dạng sparse matrix, tức chỉ lưu các giá trị khác không và vị trí của chúng. Vì vậy, tốt hơn hết, các dấu ‘?’ nên được thay bằng giá trị ‘0’, tức chưa xác định liệu user có thích item hay không. Việc này không những tối ưu bộ nhớ mà việc tính toán similarity matrix sau này cũng hiệu quả hơn.

Ma trận sau khi được chuẩn hóa còn được gọi là normalized utility matrix như hình dưới:

Tính toán Similarity

vậy sau khi xây dựng xong normalized utility matrix , bước quan trọng tiếp theo chúng cần cần làm là tính toán độ tương đồng giữa các User.

Ta gọi mực độ tương đồng của 2 User là Sim(Ui,Uj). Để xây dựng 1 hàm Similarity thì chúng ta cần đảm bảo yếu tố sau :

Ở đây mình sẽ đề cập đến 2 similarity function đó là

• Cosine Similarity : Đây là hàm được sử dụng nhiều nhất, và cũng quen thuộc với các bạn nhất. Nếu các bạn không nhớ công thức tính cos của góc giữa hai vector u1 , u2 trong chương trình phổ thông, thì dưới đây là công thức:

Trong bài này mình sẽ sử dụng công thức này nhé.

• Pearson Corelation : Mình thường k hay sử dụng công thức này , anh em có thể tham khảo thêm ở đây

Sau khi sử dụng Cosine Similarity thì chúng ta sẽ thu được ma trận Similarity như sau:

Rating Prediction

Sau khi xây dựng được ma trận Similarity thì chúng ta phải đưa ra dự đoán đúng không nào? Ở đây chúng ta sẽ dự đoán theo K- User gần nhất . K càng nhiều thì dự đoán sẽ càng chính xác nghe khá giống với K-NN nhỉ.

Công thức được đưa ra ở đây là:

Để mình lấy ví dụ minh họa dự đoán user 5 rating cho item 3 với K = 3 luôn cho anh em dễ hiểu nhé:

• Xác định các User đã rated cho item 3 là User 0,1,2,3,4,6
• Xác định similarities của User 5 với các User còn lại lần lượt là : 0.2 , -0.23 , 0.47 , -0.29 , 0 , 0.56 với K = 3 thì ta chọn 0,2,6
• Xác định Normalized ratings của User 0,2,6 lần lượt là -1.25 , 0.5 , 0.67
• Đưa ra dự đoán theo công thức :

Thực hiện tương tự là ta có thể hoàn thiện normalized ratings matrix :

Đến bước này là gần như đã xong việc cuối cùng của ae là cộng lại với gái trị trung bình ban đầu tính được là ta có thể đưa ra dự đoán của 1 User với 1 Item rồi

Item-item Collaborative Filtering

Một số hạn chês của User-user CF:

• Trên thực tế, số lượng users luôn lớn hơn số lượng items rất nhiều. Kéo theo đó là Similarity matrix là rất lớn với số phần tử phải lưu giữ là hơn 1 nửa của bình phương số lượng users (chú ý rằng ma trận này là đối xứng). Việc này, như đã đề cập ở trên, khiến cho việc lưu trữ ma trận này trong nhiều trường hợp là không khả thi.
• Ma trận Utility Y thường là rất sparse. Với số lượng users rất lớn so với số lượng items, rất nhiều cột của ma trận này sẽ rất sparse, tức chỉ có một vài phần tử khác 0. Lý do là users thường lười rating. Cũng chính vì việc này, một khi user đó thay đổi rating hoặc rate thêm items, trung bình cộng các ratings cũng như vector chuẩn hoá tương ứng với user này thay đổi nhiều. Kéo theo đó, việc tính toán ma trận Similarity, vốn tốn nhiều bộ nhớ và thời gian, cũng cần được thực hiện lại.

Ngược lại, nếu chúng ta tính toán similarity giữa các items rồi recommend những items gần giống với item yêu thích của một user thì sẽ có những lợi ích sau:

• Vì số lượng items thường nhỏ hơn số lượng users, Similarity matrix trong trường hợp này cũng nhỏ hơn nhiều, thuận lợi cho việc lưu trữ và tính toán ở các bước sau.
• Vì số lượng phần tử đã biết trong Utility matrix là như nhau nhưng số hàng (items) ít hơn số cột (users), nên trung bình, mỗi hàng của ma trận này sẽ có nhiều phần tử đã biết hơn số phần tử đã biết trong mỗi cột. Việc này cũng dễ hiểu vì mỗi item có thể được rated bởi nhiều users. Kéo theo đó, giá trị trung bình của mỗi hàng ít bị thay đổi hơn khi có thêm một vài ratings. Như vậy, việc cập nhật ma trận Similarity Matrix có thể được thực hiện ít thường xuyên hơn.

Cách tiếp cận thứ hai này được gọi là Item-item Collaborative Filtering. Mình thấy hướng tiếp cận này được sử dụng nhiều trong thực tế hơn.

Quy trình dự đoán missing ratings cũng tương tự như trong User-user CF

Đầu tiên tính giá trị trung bình của rating theo item:

Xây dựng normalized utility matrix :

Xây dựng Item similarity matrix :

Đưa ra dự đoán còn thiếu:

Trên đây là lý thuyết về NBCF. Mình xin kết thúc bài viết này ở đây , ở phần sau mình sẽ đi vào code Python và kiểm thử dữ liệu cho anh em nhé . Hẹn ae ở bài viết tới

Tài liệu mình hay tham khảo

1. Khá hay và nhiều kiến thức của các pháp sư US-UK AWS Machine Learning Blog

2. Kho Dataset cho anh em GroupLens

3. Mình cũng hay tham khảo ở đây TensorFlowBlog