NamDev
Guest
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ế
Có 2 hướng tiếp cận Collaorative Filtering:
1. Khởi tạo ma trận dữ liệu
Đối với Collaborative filtering, chúng ta sử dụng 3 thành phần dữ liệu là user, movies và ratings (1), cụ thể:
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.
2. Chuẩn hóa ma trận dữ liệu
Để có thể sử dụng ma trận này vào việc tính toán, chúng ta 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 đó, ta 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.
import pandas as pd
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
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()
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.
3. Tính toán độ tương đồng
Sau khi chuẩn hóa ma trận Utility, ta tính toán độ tương đồng giữa các users. Chúng ta sử dụng hàm cosine similarity (hàm có sẵn của thư viện sklearn của Python). Dưới đây là công thức và hàm cosine similarity
# ở phần khởi tạo class, ta đã gái: dist_func=cosine_similarity
def similarity(self):
"""
Tính độ tương đồng giữa các user và các item
"""
eps = 1e-6
self.S = self.dist_func(self.Ybar.T, self.Ybar.T)
Kết quả sau khi tính toán độ tương đồng (độ tương đồng là 1 con số trong khoảng -1 đến 1. Càng gần 1 thì càng tương đồng, càng gần -1 thì càng đối lập)
4. Dự đoán ratings
Ta 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.
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.
Ý 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ế
Có 2 hướng tiếp cận Collaorative Filtering:
- 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.
1. Khởi tạo ma trận dữ liệu
Đối với Collaborative filtering, chúng ta 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 ta tiếp tục sử dụng module read_csv của Pandas để lưu trữ, chúng ta 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).
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.
2. Chuẩn hóa ma trận dữ liệu
Để có thể sử dụng ma trận này vào việc tính toán, chúng ta 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 đó, ta 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.
import pandas as pd
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
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()
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.
3. Tính toán độ tương đồng
Sau khi chuẩn hóa ma trận Utility, ta tính toán độ tương đồng giữa các users. Chúng ta sử dụng hàm cosine similarity (hàm có sẵn của thư viện sklearn của Python). Dưới đây là công thức và hàm cosine similarity
# ở phần khởi tạo class, ta đã gái: dist_func=cosine_similarity
def similarity(self):
"""
Tính độ tương đồng giữa các user và các item
"""
eps = 1e-6
self.S = self.dist_func(self.Ybar.T, self.Ybar.T)
Kết quả sau khi tính toán độ tương đồng (độ tương đồng là 1 con số trong khoảng -1 đến 1. Càng gần 1 thì càng tương đồng, càng gần -1 thì càng đối lập)
4. Dự đoán ratings
Ta 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 công thức:
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.