4. Xây dựng Collaborative Filtering
Như bài viết đã trình bày ở trên, content-based chỉ đề xuất các bộ phim có tính chất tương tự mà không đề xuất đa dạng phim hay các bộ phim được cộng đồng xem phim đánh giá cao. Bên cạnh đó, contented-based Recommender System trên có hai nhược điểm:
- 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 sẽ 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. Để có thể xây dựng được một hệ thống Collapborative Filtering, chúng ta 2 hướng tiếp cận:
- Một là 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 users gần giống nhau (similar users) tới item đó còn được gọi là User-user collaborative filtering.
- Hai là 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. Sau đây chúng ta sẽ tiếp cận theo hướng user-user.
Thuật toán
Ý tưởng cơ bản của thuật toán này là dự đoán mức độ yêu thích của một user đối với một item dựa trên các users khác “gần giống” với user đang xét. Việc xác định độ “giống nhau” giữa các users có thể dựa vào mức độ quan tâm (rating) của các users này với các items khác mà hệ thống đã biết trong quá khứ
Ví dụ: Hai users A, B đều thích các phim về cảnh sát hình sự (tức là đều đánh giá các bộ phim thuộc thể loại này 4 -> 5 sao). Dựa vào lịch sử xem phim của B, ta thấy B thích bộ phim “Người phán xử”, vậy nhiều khả năng A cũng thích phim này, từ đó hệ thống sẽ đề xuất “Người phán xử” cho A.
Thiết kế
1. Khởi tạo ma trận dữ liệu user - item
Đối với Collaborative filtering, chúng tôi sử dụng 3 thành phần dữ liệu là user, movies và ratings (1), cụ thể:
- Users: là danh sách người dùng
- Movies: là danh sách các phim, mỗi phim có thể kèm theo thông tin mô tả.
- Ratings: là số điểm user đánh giá cho các bộ phim Để lưu trữ được 3 thành phần dữ liệu trên, chúng tôi tiếp tục sử dụng module read_csv của Pandas để lưu trữ, chúng tôi gọi là ma trận user – items. Cụ thể, ma trận user - items biểu diễn mức độ quan tâm (rating) của user với mỗi item. Ma trận này được xây dựng từ dữ liệu (1).
import pandas
from pandas import read_csv
def get_dataframe_ratings_base(text):
"""
đọc file base của movilens, lưu thành dataframe với 3 cột user id, item id, rating
"""
r_cols = ['user_id', 'item_id', 'rating']
ratings = pandas.read_csv(text, sep='\t', names=r_cols, encoding='latin-1')
Y_data = ratings.values
return Y_data
Ma trận này có rất nhiều các giá trị miss. Nhiệm vụ của hệ thống là dựa vào các ô đã có giá trị trong ma trận trên (dữ liệu thu được từ trong quá khứ), thông qua mô hình đã được xây dựng, dự đoán các ô còn trống (của user hiện hành), sau đó sắp xếp kết quả dự đoán (ví dụ, từ cao xuống thấp) và chọn ra Top-N items theo thứ tự rating giảm dần, từ đó gợi ý chúng cho người dùng.
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity
from scipy import sparse
class CF(object):
"""
class Collaborative Filtering, hệ thống đề xuất dựa trên sự tương đồng
giữa các users với nhau, giữa các items với nhau
"""
def __init__(self, data_matrix, k, dist_func=cosine_similarity, uuCF=1):
"""
Khởi tạo CF với các tham số đầu vào:
data_matrix: ma trận Utility, gồm 3 cột, mỗi cột gồm 3 số liệu: user_id, item_id, rating.
k: số lượng láng giềng lựa chọn để dự đoán rating.
uuCF: Nếu sử dụng uuCF thì uuCF = 1 , ngược lại uuCF = 0. Tham số nhận giá trị mặc định là 1.
dist_f: Hàm khoảng cách, ở đây sử dụng hàm cosine_similarity của klearn.
limit: Số lượng items gợi ý cho mỗi user. Mặc định bằng 10.
"""
self.uuCF = uuCF # user-user (1) or item-item (0) CF
self.Y_data = data_matrix if uuCF else data_matrix[:, [1, 0, 2]]
self.k = k
self.dist_func = dist_func
self.Ybar_data = None
# số lượng user và item, +1 vì mảng bắt đầu từ 0
self.n_users = int(np.max(self.Y_data[:, 0])) + 1
self.n_items = int(np.max(self.Y_data[:, 1])) + 1
2. Chuẩn hóa ma trận user - item
Để có thể sử dụng ma trận này vào việc tính toán, chúng tôi cần thay những dấu ‘?’ bởi một giá trị. Đơn giản nhất có thể thay giá trị ‘0’ hay một cách khác là ‘2.5’ – giá trị trung bình giữa 0 và 5. Tuy nhiên, cách tính này có độ chính xác thấp vì những giá trị này sẽ hạn chế với những users dễ hoặc khó tính. Thay vào đó, nhóm sử dụng giá trị trung bình cộng ratings của mỗi user bằng cách trừ ratings của mỗi user cho giá trị trung bình ratings tương ứng của user đó và thay dấu ‘?’ bằng giá trị 0.
Mục đích của cách xử lý này là:
- Phân loại ratings thành 2 loại: giá trị âm (user không thích item) và dương (user thích item). Các giá trị bằng 0 là những item chưa được đánh giá.
- Số chiều của Utility matrix thường rất lớn, trong khi lượng ratings biết trước thường rất nhỏ so với kích thước của ma trận. Nếu thay dấu ‘?’ bằng ‘0’ thì chúng ta có thể sử dụng sparce matrix, tức ma trận chỉ lưu các giá trị khác 0 và vị trí của giá trị đó. Như vậy, việc lưu trữ sẽ tối ưu hơn
def normalize_matrix(self):
"""
Tính similarity giữa các items bằng cách tính trung bình cộng ratings giữa các items.
Sau đó thực hiện chuẩn hóa bằng cách trừ các ratings đã biết của item cho trung bình cộng
ratings tương ứng của item đó, đồng thời thay các ratings chưa biết bằng 0.
"""
users = self.Y_data[:, 0]
self.Ybar_data = self.Y_data.copy()
self.mu = np.zeros((self.n_users,))
for n in range(self.n_users):
ids = np.where(users == n)[0].astype(np.int32)
item_ids = self.Y_data[ids, 1]
ratings = self.Y_data[ids, 2]
# take mean
m = np.mean(ratings)
if np.isnan(m):
m = 0 # để tránh mảng trống và nan value
self.mu[n] = m
# chuẩn hóa
self.Ybar_data[ids, 2] = ratings - self.mu[n]
self.Ybar = sparse.coo_matrix((self.Ybar_data[:, 2],
(self.Ybar_data[:, 1], self.Ybar_data[:, 0])), (self.n_items, self.n_users))
self.Ybar = self.Ybar.tocsr()
3. Tính độ tương đồng giữa các item
Sau khi chuẩn hóa ma trận Utility, ta tính toán độ tương đồng giữa các users, sử dụng công thức :
Công thức này được hỗ trợ bởi hàm cosine similarity (hàm có sẵn của thư viện sklearn của Python):
def similarity(self):
"""
Tính độ tương đồng giữa các user và các item
"""
self.S = self.dist_func(self.Ybar.T, self.Ybar.T)
4. Dự đoán ratings của user
Nhóm sẽ dự đoán ratings của một user với mỗi item dựa trên k users gần nhất (neighbor users), tương tự như phương pháp K-nearest neighbors (KNN).
Trong đó, N(u, i) là tập k users gần nhất (có độ tương đồng cao nhất) với user u và đã từng đánh giá item i. Ví dụ, chúng tôi dự đoán normalized rating của user u1 cho item i1 với k = 2 là số users gần nhất.
- Bước 1: Xác định các users đã rated cho i1, đó là u0, u3, u5
- Bước 2: Lấy similarities của u1 với u0, u3, u5. Kết quả lần lượt là: {u0, u3, u5: {0.83, -0.4, -0.23}. Với k = 2. Chọn 2 giá trị lớn nhất là 0.83 và -0.23, tương ứng với các users u0, u5. Hai users này có normalized ratings với i1 là: {u0, u5} {0.75, 0.5}
- Bước 3: Tính normalized ratings theo (2):
Thực hiện dự đoán cho các trường hợp missing ratings (chưa có dự đoán), ta sẽ thu được ma trận normalized ratings matrix như ví dụ:
Cuối cùng, cộng lại các giá trị ratings với ratings trung bình (ở bước chuẩn hóa) theo từng cột. Chúng ta sẽ thu được ma trận hoàn thiện.
def __pred(self, u, i, normalized=1):
"""
Dự đoán ra ratings của các users với mỗi items.
"""
# tìm tất cả user đã rate item i
ids = np.where(self.Y_data[:, 1] == i)[0].astype(np.int32)
users_rated_i = (self.Y_data[ids, 0]).astype(np.int32)
sim = self.S[u, users_rated_i]
a = np.argsort(sim)[-self.k:]
nearest_s = sim[a]
r = self.Ybar[i, users_rated_i[a]]
if normalized:
# cộng với 1e-8, để tránh chia cho 0
return (r * nearest_s)[0] / (np.abs(nearest_s).sum() + 1e-8)
return (r * nearest_s)[0] / (np.abs(nearest_s).sum() + 1e-8) + self.mu[u]
def pred(self, u, i, normalized=1):
"""
Xét xem phương pháp cần áp dùng là uuCF hay iiCF
"""
if self.uuCF: return self.__pred(u, i, normalized)
return self.__pred(i, u, normalized)
5. Kết quả
Sau khi chúng ta đã dự đoán được ratings của các bộ phim mà người dùng sẽ đánh giá, ta lấy ra được top bộ phim mà user sẽ thích theo các bước:
- Lấy id người dùng
- Nhận danh sách rating của người dùng đối với các bộ phim chưa xem
- Sắp xếp danh sách các bộ giá trị rating đó
- Trả về các tiêu đề tương ứng với chỉ số của các phần tử trên cùng
def recommend_top(self, u, top_x):
"""
Determine top 10 items should be recommended for user u.
. Suppose we are considering items which
have not been rated by u yet.
"""
ids = np.where(self.Y_data[:, 0] == u)[0]
items_rated_by_u = self.Y_data[ids, 1].tolist()
item = {'id': None, 'similar': None}
list_items = []
def take_similar(elem):
return elem['similar']
for i in range(self.n_items):
if i not in items_rated_by_u:
rating = self.__pred(u, i)
item['id'] = i
item['similar'] = rating
list_items.append(item.copy())
sorted_items = sorted(list_items, key=take_similar, reverse=True)
sorted_items.pop(top_x)
return sorted_items
Vậy là ta đã xây dựng thành công Collaborative Filtering với hướng tiếp cận user-user. Bạn đã có thể thử một hướng tiếp cận khác đó chính là item-item.Trong phương pháp này, thay vì tính similarity giữa các users như trong uuCF, chúng ta sẽ tính similarity giữa các items, rồi gợi ý cho users những items gần giống với item mà user đó đã thích. Lợi ích của phương pháp này là:
- Vì số lượng items thường rất nhỏ so với số lượng users nên kích thước ma trận Similarity sẽ nhỏ hơn rất nhiều, giúp tối ưu hơn cả về mặt lưu trữ và tốc độ tính toán.
- Thường thì mỗi item được đánh giá bởi rất nhiều users, và con số này thường lớn hơn nhiều so với số items mà mỗi user đánh giá. Vì vậy, số giá trị đã biết trong một vector biểu diễn item sẽ lớn hơn nhiều so với một vector biểu diễn user. Trong trường hợp có thêm một số dữ liệu về ratings, giá trị trung bình ratings của iiCF sẽ ít thay đổi hơn so với uuCF, vì vậy sẽ ít phải cập nhật Similarity Matrix hơn. Về mặt tính toán, iiCF có thể thực hiện theo uuCF bằng cách chuyển vị ma trận Utility, coi như items đánh giá users. Sau khi tính được kết quả, chúng ta lại thực hiện chuyển vị một lần nữa sẽ thu được kết quả cuối cùng.
TỔNG KẾT
Như vậy, sau 3 bài viết của series Recommender System cơ bản, chúng ta đã trình bày tổng quan về cách thức hoạt động của một hệ thống Recommender System, cách xây dựng một mô hình Recommender System cơ bản. Chúng ta đã ứng dụng được nó vào thực tế với bộ dữ liệu của Movilens, sử dụng các thư viện NumPy, Pandas, Scikit-Learn để xây dựng 2 ví dụ minh họa hệ thống đề xuất phim với hai hướng tiếp cận là Content-based Recommender và Collaborative filtering Recommender với cả 2 hướng tiếp cận là user – user và item - item. Vì bài viết có hạn, các bạn có thể tham khảo source code và các tài liệu liên quan dưới để hiểu rõ hơn về Recommender System Source code demo
TÀI LIỆU THAM KHẢO
- Ekstrand, Michael D., John T. Riedl, and Joseph A. Konstan. “Collaborative filtering recommender systems” 2011
- Jure Leskovec, Anand Rajaraman, Jeffrey David Ullman, Stanford University, California. “Recommendation Systems” 2014
- Recommender System Tutorial
- Recommendation Systems - Stanford InfoLab
- Content Based Recommendations | Stanford University
- Collaborative Filtering | Stanford University