Recommendation System (Part 4)

R Machine Learning Series

Introduction

Về Recommendation System và xây dựng Recommender trong các tình huống thường phát sinh trong thực tế (có ratings, không có ratings cũng như đánh giá hiệu quả của Recommender) các bạn có thể tham khảo Part 1, Part 2 và Part 3. Trong phần này chúng ta sẽ xây dựng Recommender Engine dựa trên Jaccard Similarity áp dụng cho Binary Data - vốn là một tình huống phổ biến khi mà dữ liệu về items là không có ratings tương ứng.

About Jaccard Similarity

Xem xét một ví dụ giả định về 3 JAV Fants và 6 diễn viên yêu thích của họ như sau:

# Clear workspace: 

rm(list = ls())

#============================
#    Jaccard Similarity
#============================

# Create a fake data that describes movies viewed by 3 users: 

user1 <- rep(0:1, each = 1, time = 3)
user2 <- c(0, rep(1, 3), 0, 1)
user3 <- c(1, 0, 0, 0, 1, 1)

row_names <- c("Maria Ozawa", 
               "Eimi Fukada", 
               "Nozomi Sasaki", 
               "Sora Aoi", 
               "Minori Hatsune",
               "Ria Sakurai")

df_fake <- data.frame(user1 = user1, user2 = user2, user3 = user3)

row.names(df_fake) <- row_names

# Show data: 

df_fake

##                user1 user2 user3
## Maria Ozawa        0     0     1
## Eimi Fukada        1     1     0
## Nozomi Sasaki      0     1     0
## Sora Aoi           1     1     0
## Minori Hatsune     0     0     1
## Ria Sakurai        1     1     1

Với user1 thì Eimi Fukada, Sora Aoi, Ria Sakurai là ba diễn viên yêu thích của người này (đánh số 1). Các diễn viên khác đánh số 0 nghĩa là chưa thích. Chúng ta có thể tính mức độ tương đồng của user1 này với hai users còn lại theo thước đo Jaccard Similarity như sau:

# Jaccard Similarity between user1 and user2: 

3 / (3 + 0 + 1)

## [1] 0.75

# Jaccard Similarity between user1 and user3:

1 / (1 + 2 + 2)

## [1] 0.2

Diễn giải dưới đây sẽ giúp bạn hiểu một cách trực quan những gì được viết trong các tài liệu Toán về Jaccard Similarity. Ví dụ, với cặp user1 - user2 thì con số 0.75 được đếm bằng a / (a + b + c) trong đó:

• a lượng giá trị 1 mà cột user1 và user đều có. Trong tình huống của chúng ta thì a = 2.
• b là số lượng giá trị 1 xuất hiện ở cột user1 nhưng lại là 0 ở cột user2. Trong tình huống của chúng ta thì b = 0.
• c là số lượng giá trị 1 xuất hiện ở cột user2 nhưng lại là 0 ở cột user1.

Kết quả chỉ ra rằng giữa user1 - user2 là giống nhau hơn so với cặp user1 - user3. Điều này dẫn đến một suy luận là nên khuyến nghị những diễn viên yêu thích của user2 cho user1. Đây chính là cơ sở để xây dựng Recommender Engine dựa trên chỉ số tương đồng Jaccard.

A Real-world Application

Chúng ta sử dụng bộ dữ liệu MovieLens Data Set để xây dựng một Recommender dựa trên Jaccard Similarity. Trước hết chúng ta đọc bộ dữ liệu này và convert về Binary Data (lưu ý là chúng ta có ratings cho các movies nhưng bài toán sẽ được giải quyết trên giả định chúng ta không có ratings và do vậy tất các những movies có rating chúng ta sẽ phải convert về 1):

# Import data: 

library(tidyverse)

ratings <- read_csv("ratings.csv")

# Convert to real time: 

library(lubridate)

ratings %>% 
  mutate(timestamp = as_datetime(timestamp), timestamp = date(timestamp)) -> ratings

# All ratings: 

ratings$rating %>% unique() -> all_ratings

# Set all users and movies:  

all_users <- ratings$userId %>% unique() %>% as.character()

all_movies <- ratings$movieId %>% unique() %>% as.character()

# convert to binary matrix: 

ratings %>% 
  select(-timestamp) %>% 
  spread(key = movieId, value = rating, fill = 0) %>% 
  mutate_at(.vars = all_movies, function(x) {case_when(x %in% all_ratings ~ 1, TRUE ~ 0)}) %>% 
  mutate(userId = all_users) -> df_binary

# Show some observations: 

head(df_binary[1:5, 1:5])

## # A tibble: 5 x 5
##   userId   `1`   `2`   `3`   `4`
##   <chr>  <dbl> <dbl> <dbl> <dbl>
## 1 1          1     0     1     0
## 2 2          0     0     0     0
## 3 3          0     0     0     0
## 4 4          0     0     0     0
## 5 5          1     0     0     0

COnvert df_binary về binary matrix (cho tiện tính toán trên matrix, nếu không thích tính toán với matrix có thể bỏ qua bước này):

# Convert to transpose of df_binary: 

df_binary %>% 
  select(-userId) %>% 
  t() %>% 
  as.matrix() %>% 
  as.data.frame() -> my_mat

# Set col and row names for the transpose: 

colnames(my_mat) <- all_users
rownames(my_mat) <- all_movies

Viết hàm có tên jaccard_sim() tính Jaccard Similarity giữa hai users (không loại trừ hai users này là một):

# Function calculates Jaccard Similarity: 

jaccard_sim <- function(two_users) {
  
  sums <- rowSums(my_mat[, two_users])
  
  a <- length(sums[sums == 2])
  
  a_b_c <- length(sums[sums == 1]) + a
  
  jaccard_sim <- a/a_b_c
  
  return(jaccard_sim)

}

Dưới đây là tương đồng giữa user thứ nhất và thứ hai:

# Test the function: 

jaccard_sim(all_users[c(1, 2)])

## [1] 0.007722008

Đương nhiên user1 và chính nó sẽ có tương đồng là 1:

jaccard_sim(all_users[c(1, 1)])

## [1] 1

Chúng ta sẽ sử dụng hàm này cho các bước xây dựng Recommender Engine sau này. Sử dụng cách tiếp cận đã trình bày trong Part 3 chúng ta sẽ chọn mốc thời gian 2018-01-01 để chia dữ liệu thành bộ train và test:

#==================================================
#    Recommender Engine using Jaccard Similarity
#==================================================

# Set time point: 

time_selected <- ymd("2018-01-01")

# Split data for train and test engine: 

train_raw_data <- ratings %>% filter(timestamp <= time_selected)

test_raw_data <- ratings %>% filter(timestamp > time_selected)

# All ratings in train data: 

all_ratings_train <- train_raw_data$rating %>% unique()

# Set all users and movies:  

all_users_train <- train_raw_data$userId %>% unique() %>% as.character()

all_movies_train <- train_raw_data$movieId %>% unique() %>% as.character()

all_users_test <- test_raw_data$userId %>% unique() %>% as.character()

# convert to binary matrix for train data: 

train_raw_data %>% 
  select(-timestamp) %>% 
  spread(key = movieId, value = rating, fill = 0) %>% 
  mutate_at(.vars = all_movies_train, function(x) {case_when(x %in% all_ratings_train ~ 1, TRUE ~ 0)}) -> df_binary_train

# Convert to transpose: 

df_binary_train %>% 
  select(-userId) %>% 
  t() %>% 
  as.matrix() %>% 
  as.data.frame() -> my_mat_train

# Set col and row names for the transpose of df_binary_train: 

colnames(my_mat_train) <- all_users_train
rownames(my_mat_train) <- all_movies_train

Viết hàm top_5_jaccard() đưa ra 5 users có Jaccard Similarity (JS) cao nhất với một user chọn trước:

# Function returns 5 users with highest Jaccard similarities: 

top_5_jaccard <- function(user_selected) {
  
  m_users <- length(all_users_train)
  
  jaccard_sim_i_th <- NULL
  
  for (j in 1:m_users) {
    
    sums <- rowSums(my_mat_train[, c(user_selected, all_users_train[j])])
    
    a <- length(sums[sums == 2])
    
    a_b_c <- length(sums[sums == 1]) + a
    
    jaccard_sim <- a/a_b_c
    
    jaccard_sim_i_th <- c(jaccard_sim_i_th, jaccard_sim)
    
  }
  
  df_results <- data.frame(userId = all_users_train, similarity = jaccard_sim_i_th)
  
  df_results %>% 
    mutate(reference = case_when(similarity == 1 ~ "yes", TRUE ~ "no")) %>% 
    top_n(n = 6, wt = similarity) %>% 
    arrange(-similarity) -> df_top5
  
  return(df_top5)
  
}

JS cho tất cả các users mà sẽ có mặt cả trước và sau thời điểm 2018-01-01:

# Common users: 

base::intersect(all_users_train, all_users_test) -> common_users

# For all users: 

lapply(common_users, top_5_jaccard) -> jaccard_for_all

# For the first 3 users: 

jaccard_for_all[1:3]

## [[1]]
##   userId similarity reference
## 1     18  1.0000000       yes
## 2    305  0.2541296        no
## 3    561  0.2509458        no
## 4    573  0.2496025        no
## 5    249  0.2405583        no
## 6     63  0.2385621        no
## 
## [[2]]
##   userId similarity reference
## 1     50  1.0000000       yes
## 2    247  0.1311475        no
## 3    328  0.1194030        no
## 4     18  0.1035599        no
## 5    525  0.1031746        no
## 6    339  0.1011673        no
## 
## [[3]]
##   userId similarity reference
## 1     68  1.0000000       yes
## 2    274  0.3473463        no
## 3    608  0.3436066        no
## 4    480  0.3416068        no
## 5    414  0.3130316        no
## 6    177  0.3066502        no

Viết hàm movies_recommended_for_specific_user() trả về movieId của những bộ phim được khuyến nghị cho một user cho trước:

# Function recommends movies for a specific user: 

movies_recommended_for_specific_user <- function(userID) {
  
  top_5_jaccard(userID) -> df_sim_user
  
  df_sim_user %>% 
    filter(similarity != 1) %>% 
    top_n(n = 1, wt = similarity) %>% 
    pull(userId) %>% 
    as.character() -> user_that_most_sim
  
  test_raw_data %>% 
    mutate(userId = as.character(userId)) %>% 
    filter(userId %in% user_that_most_sim) %>% 
    pull(movieId) %>% 
    unique() %>% 
    as.character() -> movies_recom
  
  return(tibble(userId = userID, movies_recom = movies_recom))
  
}

Chúng ta có thể, ví dụ, sử dụng hàm đã có list ra danh sách các bộ phim mà user thứ nhất nên xem. Lưu ý rằng danh sách các bộ phim đó đến từ các bộ phim đã từng được xem bởi user có JS cao nhất - hay tương đồng cao nhất với user thứ nhất:

movies_recommended_for_specific_user(common_users[1]) %>% head()

## # A tibble: 6 x 2
##   userId movies_recom
##   <chr>  <chr>       
## 1 18     25          
## 2 18     288         
## 3 18     300         
## 4 18     316         
## 5 18     357         
## 6 18     474

Viết hàm return_number_Recommendedmovies_viewed() đếm số bộ phim mà Engine khuyến nghị thực tế sẽ được xem bởi một user cho trước:

# Function test

return_number_Recommendedmovies_viewed <- function(user_i_th) {
  
  test_raw_data %>% 
    filter(userId == user_i_th) %>% 
    pull(movieId) %>%
    unique() -> movies_actual
  
  movies_recommended_for_specific_user(user_i_th) -> df_recom
  
  df_recom %>% 
    pull(movies_recom) -> movies_recom
  
  return(sum(movies_recom %in% movies_actual))
}

Với user, ví dụ, thứ 10 chẳng hạn thì số bộ phim mà người này sẽ xem trong số các bộ phim được Engine khuyến nghị là:

return_number_Recommendedmovies_viewed(common_users[10])

## [1] 3

Chúng ta có thể đo lường hiệu quả vận hành của Recommender Engine bằng các so sánh những movies được hệ thống khuyến nghị với những bộ phim mà users sẽ xem sau thời điểm 2018-01-01:

sum(sapply(common_users, return_number_Recommendedmovies_viewed) != 0) / length(common_users)

## [1] 0.35

Kết quả này nghĩa là 35% số users sau ngày 2018-01-01 sẽ xem ít nhất một movie mà hệ thống khuyến nghị cho họ.

Summary

Recommender Engine được xây dựng dựa trên dữ liệu có trước ngày 2018-01-01 để đưa ra các bộ phim được khuyến nghị cho các users dựa trên độ tương đồng JS. Chất lượng của Engine được tính toán bằng cách so sánh các bộ phim khuyến nghị bởi Engine và các bộ phim thực tế sẽ được xem bởi các users. Các cách tiếp cận khác cho việc đánh giá Engine các bạn có thể sử dụng các hàm sẵn có của thư viện recommenderlab của Michael Hahsler vốn được trình bày trong nhiều textbook và sẽ không được trình bày ở đây.

References

1. Mining of Massive Datasets, Chapter 3
2. A Survey of Accuracy Evaluation Metrics of Recommendation Tasks.
3. Evaluating Recommendation Systems.
4. Evaluating Collaborative Filtering Recommender Systems.
5. Recommender Systems: An Introduction.