Recommendation System (Part 3)

R Machine Learning Series

Different Types of Recommenders

Các hệ thống khuyến nghị (Recommendation System / Recommender) được xây dựng dựa trên ba hướng tiếp cận dưới đây:

• Collaborative Filtering
• Content-Based Filtering
• Hybrid Recommendation Systems

Collaborative Filtering (CF) là hướng tiếp cận mà chỉ dựa vào dữ liệu về hành vi tiêu dùng của người sử dụng trong khi Content-Based Filtering lại chỉ dựa vào các đặc điểm / đặc trưng của sản phầm. Cách tiếp cận thứ ba - Hybrid Recommendation Systems, thì lại dựa vào đồng thời cả dữ liệu về hành vi của người tiêu dùng và các đặc điểm của sản phẩm. Một ví dụ là hệ thống khuyến nghị của Netflix được sử dụng để khuyến nghị các bộ phim mà người dùng nên xem.

Collaborative Filtering lại có hai hướng tiếp cận riêng biệt là User-base Collaborative Filtering và Item-base Collaborative Filtering. Giải thích tương đối chi tiết về hai hướng tiếp cận này bạn đọc có thể tham khảo ở đây, ở đây và ở đây.

Trong Part 1 và Part 2 chúng ta đã train một Recommender tương ứng với hai tình huống: (1) có dữ liệu về ratings - tình huống lí tưởng, và (2) không có dữ liệu về ratings - một tình huống hay gặp trong thực tế. Cả hai Recommender này đều thuộc User-base Collaborative Filtering (thể hiện qua method = "IBCF" khi train Recommender).

Tất cả cách tiếp cận để xây dựng hệ thống khuyến nghị đều dựa trên một thước đo được gọi là Similarity Measure - mức độ tương đồng và việc lựa chọn Similarity Measure phù hợp sẽ ảnh hưởng đến chất lượng của hệ thống khuyến nghị.

Cosin Similarity

Trong số các Similarity Measures đã đề cập ở trên thì Cosin Similarity là thước đo có khả năng áp dụng trong nhiều tình huống: từ dữ liệu có ratings lẫn không có ratings và cũng có thể sử dụng cho Content-Based Filtering và Hybrid Recommendation Systems. Dưới đây chúng ta sẽ viết một hàm tính Cosin Similarity (với giả định rằng bạn đọc đã biết công thức toán học của thước đo này):

# Clear workspace: 

rm(list = ls())

# Function calculating cosine similarity beween two vectors: 

cosine_similiraty <- function(x, y) {
  cosine_sim <- crossprod(x, y) / sqrt(crossprod(x)*crossprod(y))
  return(cosine_sim)
}

Chúng ta áp dụng hàm đã viết để tính cosin similarity của hai vectors:

# An example of cosin similiraty: 

vec1 <- c( 1, 1, 1, 0, 0, 0) 

vec2 <- c( 0, 1, 1, 1, 0, 1)

cosine_similiraty(vec1, vec2)

##           [,1]
## [1,] 0.5773503

Như đã biết, chúng ta có thể sử dụng hàm similarity() của thư viện recommenderlab để tính ra kết quả 0.5773503 này:

# Compare with similarity() function: 

library(recommenderlab)

similarity(as(as.matrix(cbind(vec1, vec2)), "realRatingMatrix"), which = "items")

##           vec1
## vec2 0.5773503

Mục tiêu đặt ra là đưa ra 5 items có mức độ tương đầu cao nhất với một item bất kì cho trước trong bộ dữ liệu MovieLens Data Set đã từng được sử dụng ở Part 1. Trước hết cần load, transformation data về ma trận thưa (Sparse Matrix) từ dữ liệu thô (Raw Data) ban đầu:

# 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

# Convert to sparse matrix: 

ratings %>% 
  select(-timestamp) %>% 
  spread(key = movieId, value = rating, fill = 0) -> sparse_user_item

# Users: 

sparse_user_item$userId -> all_users

# Convert to sparse matrix: 

sparse_user_item %>% 
  select(-userId) %>% 
  as.matrix() -> sparse_matrix_user_item

# Set row names for sparse matrix: 

rownames(sparse_matrix_user_item) <- all_users

# Columns names (movieIds): 

col_names <- colnames(sparse_matrix_user_item)

# Some observations: 

sparse_matrix_user_item[1:5, 1:5]

##   1 2 3 4 5
## 1 4 0 4 0 0
## 2 0 0 0 0 0
## 3 0 0 0 0 0
## 4 0 0 0 0 0
## 5 4 0 0 0 0

Kế tiếp viết hàm đưa ra 5 items có độ tương đồng cao nhất với một item cho trước:

# Function calculates the similarity between a chosen movie and the other movies
# and recommend 5 new songs with 5-highest similarities: 

return_5_highest_sim <- function(movie_id) {
  
  apply(sparse_matrix_user_item, 2, function(i) {cosine_similiraty(sparse_matrix_user_item[, colnames(sparse_matrix_user_item) == movie_id], i)}) -> sim
  
  tibble(movieId = names(sim), similiraty = sim) -> df_sim
  
  df_sim %>% 
    mutate(movieId = as.numeric(movieId)) %>% 
    top_n(6, wt = similiraty) %>% 
    arrange(-similiraty) %>% 
    ungroup() %>% 
    mutate(reference = case_when(movieId == movie_id ~ "Yes", TRUE ~ "No")) %>% 
    return()
}

Chúng ta có thể sử dụng hàm này để list ra danh sách 5 movies/items tương đồng nhất với, ví dụ, bộ phim thứ nhất:

# Find 5-highest similarities for the first movieId: 

return_5_highest_sim(movie_id = col_names[1]) -> df_1

# Show results: 

library(knitr)

kable(df_1)

movieId	similiraty	reference
1	1.0000000	Yes
3114	0.5726013	No
480	0.5656368	No
780	0.5642617	No
260	0.5573882	No
356	0.5470959	No

Phim có movieId là 1 thì đương nhiên đồng nhất với chính nó và do vậy similiraty = 1. Phim có movieId = 3114 và movieId = 1 có similarity = 0.5726. Chúng ta mapping với bộ dữ liệu mô tả về các bộ phim này để biết rõ hơn:

# Movie descriptions: 

descriptions <- read_csv("movies.csv")

# Map the two data sets: 

inner_join(df_1, descriptions, by = "movieId") -> df_1_des

# Show results: 

df_1_des %>% 
  select(-genres, -reference) %>% 
  kable()

movieId	similiraty	title
1	1.0000000	Toy Story (1995)
3114	0.5726013	Toy Story 2 (1999)
480	0.5656368	Jurassic Park (1993)
780	0.5642617	Independence Day (a.k.a. ID4) (1996)
260	0.5573882	Star Wars: Episode IV - A New Hope (1977)
356	0.5470959	Forrest Gump (1994)

Kết quả khá sát với kì vọng của chúng ta: Toy Story 2 (1999) sản xuất năm 1999 tương đồng cao nhất Toy Story (1995) - bộ phim được chọn làm reference. Còn Jurassic Park (1993) là bộ phim tương đồng thứ hai. Kết quả này ngụ ý rằng: trong danh các bộ phim mà một user nào đó đã xem mà có Toy Story (1995) thì hệ thống khuyến nghị nên trước hết đề xuất Toy Story 2 (1999) để người này xem cộng với 4 movies khác nữa. Phần dưới đây sẽ đưa ra một cách tiếp cận để đánh giá hiệu quả hoạt động của Recommender.

Item-base Recommender Engine using Cosin Similarity

Như đã trình bày trong Part 2 thì hiệu quả của Recommender Engine sẽ được đánh giá theo cách tiếp cận sau: các movies được khuyến nghị cho user sẽ dựa trên data quan sát thấy từ 2018-01-01 trở về trước còn data sau ngày 2018-01-01 sẽ được sử dụng để test:

# 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)

Không phải user hay item nào cũng sử dụng cho huấn luyện Recommender Engine. Chẳng hạn, với user thì chúng ta chỉ lấy những user nào xem ít nhất 5 bộ phim còn movie thì phải là những phim được xem ít nhất 5 lần. Để thuận lợi chúng ta sẽ viết một hàm convert dữ liệu thô ban đầu về Sparse Matrix với các inputs sau:

• Dữ liệu thô được chọn.
• Số bộ phim tối thiểu mà một user phải xem để user đó được chọn.
• Số lần tối thiểu mà một movie được xem để movie đó được chọn.

# Function convert to sparse matrix: 

convert_to_sparse_matrix <- function(df_selected, min_movie_viewed_by_user, min_freq_for_movie) {
  
  # Only select users and items that sastify satisfy min thresholds: 

  df_selected %>% 
    group_by(userId) %>% 
    count() %>% 
    ungroup() %>% 
    filter(n >= min_movie_viewed_by_user) %>% 
    pull(userId) -> users_selected
  
  df_selected %>% 
    group_by(movieId) %>% 
    count() %>% 
    ungroup() %>% 
    filter(n >= min_freq_for_movie) %>% 
    pull(movieId) -> movies_selected
  
  # Filter raw data: 
  
  df_selected %>% 
    filter(userId %in% users_selected) %>% 
    filter(movieId %in% movies_selected) -> df_final
  
  # Convert to sparse matrix: 
  
  df_final %>% 
    select(-timestamp) %>% 
    spread(key = movieId, value = rating, fill = 0) -> sparse_user_item

  # Convert to sparse matrix: 

  sparse_user_item %>% 
    select(-userId) %>% 
    as.matrix() -> sparse_matrix_user_item

  # Set row names for sparse matrix: 

  rownames(sparse_matrix_user_item) <- users_selected

  # Return result: 
  
  return(list(raw_data = df_final, train_matrix = sparse_matrix_user_item))
  
}

Sử dụng hàm đã có để convert về sparse matrix cho train_raw_data:

# Convert to sparse matrix: 

convert_to_sparse_matrix(df_selected = train_raw_data, 
                         min_movie_viewed_by_user = 5, 
                         min_freq_for_movie = 5) -> list_results


# Extract raw data and sparse matrix: 

train_matrix <- list_results$train_matrix

df_for_converting <- list_results$raw_data

# All movies and users from train data: 

all_movies <- colnames(train_matrix)

all_users <- row.names(train_matrix)

Viết hàm return_5_highest_sim2() tương tự như return_5_highest_sim() với một số hiệu chỉnh. Hàm này trả về 5 movies có tương đồng cao nhất với một movie cho trước:

return_5_highest_sim2 <- function(movie_id) {
  
  apply(train_matrix, 2, function(i) {cosine_similiraty(train_matrix[, colnames(train_matrix) == movie_id], i)}) -> sim
  
  tibble(movieId = names(sim), similiraty = sim) -> df_sim
  
  df_sim %>% 
    mutate(movieId = as.numeric(movieId)) %>% 
    top_n(6, wt = similiraty) %>% 
    arrange(-similiraty) %>% 
    ungroup() %>% 
    mutate(reference = case_when(movieId == movie_id ~ "Yes", TRUE ~ "No")) %>% 
    mutate(movieId_ref = movie_id) %>% 
    return()
}

Sử dụng hàm đã có để đưa ra 5 items tương đồng cao nhất cho, ví dụ, 3 movies bất kì:

lapply(sample(1:length(all_movies), 3, replace = FALSE), function(x) {return_5_highest_sim2(all_movies[x])}) -> list_movies_recom
lapply(list_movies_recom, function(df) {inner_join(df, descriptions %>% select(-genres), by = "movieId")})

## [[1]]
## # A tibble: 6 x 5
##   movieId similiraty reference movieId_ref title                           
##     <dbl>      <dbl> <chr>     <chr>       <chr>                           
## 1    1688      1     Yes       1688        Anastasia (1997)                
## 2    1566      0.540 No        1688        Hercules (1997)                 
## 3    1907      0.494 No        1688        Mulan (1998)                    
## 4    4016      0.467 No        1688        Emperor's New Groove, The (2000)
## 5    2096      0.466 No        1688        Sleeping Beauty (1959)          
## 6    1588      0.458 No        1688        George of the Jungle (1997)     
## 
## [[2]]
## # A tibble: 6 x 5
##   movieId similiraty reference movieId_ref title                   
##     <dbl>      <dbl> <chr>     <chr>       <chr>                   
## 1   45431      1     Yes       45431       Over the Hedge (2006)   
## 2   93326      0.610 No        45431       This Means War (2012)   
## 3    6595      0.556 No        45431       S.W.A.T. (2003)         
## 4    7004      0.526 No        45431       Kindergarten Cop (1990) 
## 5   60126      0.520 No        45431       Get Smart (2008)        
## 6    8972      0.512 No        45431       National Treasure (2004)
## 
## [[3]]
## # A tibble: 6 x 5
##   movieId similiraty reference movieId_ref title                   
##     <dbl>      <dbl> <chr>     <chr>       <chr>                   
## 1   48142      1     Yes       48142       Black Dahlia, The (2006)
## 2   41716      0.652 No        48142       Matador, The (2005)     
## 3    6755      0.645 No        48142       Bubba Ho-tep (2002)     
## 4    5009      0.596 No        48142       Ali (2001)              
## 5   39381      0.594 No        48142       Proposition, The (2005) 
## 6   30894      0.585 No        48142       White Noise (2005)

Sử dụng những kết quả này để khuyến nghị những movies nào cho user và đánh giá chất lượng của Recommender sẽ được giải thích ở phần dưới đây.

Evaluating Recommender Performance

Cách tiếp cận để đánh giá hệ thống khuyến nghị đã được trình bày trong Part 2. Để thực hiện thực hóa cách tiếp cận này trước hết chúng ta viết hàm mà khuyến nghị 5 movies cho một user bất kì được chọn căn cứ theo user ID:

show_5_movies_for_user <- function(user_id) {
  
  df_for_converting %>% 
    filter(userId == user_id) %>% 
    filter(!duplicated(movieId)) %>% 
    pull(movieId) %>% 
    as.character() -> movies_by_user
  
  lapply(movies_by_user, return_5_highest_sim2) -> list_movies_reco_for_user

  do.call("bind_rows", list_movies_reco_for_user) -> df_reco
  
  df_reco %>% 
    filter(reference != "Yes") %>% 
    top_n(n = 5, wt = similiraty) %>% 
    select(movieId) %>% 
    mutate(userId = user_id) %>% 
    return()
  
}

Sử dụng hàm này để đưa ra movies được khuyến nghị cho tất cả users (có thể mất thời gian để chạy):

# All users will viewed movies after 2018-01-01: 

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

base::intersect(all_user_future, all_users) -> all_user_future

# Movies recommended for those users: 

system.time(lapply(all_user_future, show_5_movies_for_user) -> list_movies_recom_for_all)

##    user  system elapsed 
## 2504.31   15.43 2545.22

Chúng ta có thể xem 5 items cho 2 userID đầu tiên:

list_movies_recom_for_all[1:2]

## [[1]]
## # A tibble: 6 x 2
##   movieId userId
##     <dbl> <chr> 
## 1    7153 18    
## 2    5952 18    
## 3    7153 18    
## 4    4993 18    
## 5    5952 18    
## 6    4993 18    
## 
## [[2]]
## # A tibble: 5 x 2
##   movieId userId
##     <dbl> <chr> 
## 1    1221 50    
## 2    7438 50    
## 3    6874 50    
## 4  102033 50    
## 5  174055 50

Với userId = 50 thì các movieId được khuyến nghị là 1221, 7438, 6874, 102033 và 174055. Chúng ta sẽ phải kiểm tra xem trong “giỏ hàng” mà khách hàng này mua sau khi có khuyến nghị (tức sau 2018-01-01) có những movies này hay không.

# Movies viewed after 2018-01-01: 

test_raw_data %>% 
  filter(userId == all_user_future[2]) %>% 
  pull(movieId) %>% 
  unique() -> movieId_for_this_user

# Number of recommended moveies that this user viewed: 
sum(list_movies_recom_for_all[[2]] %>% pull(movieId) %in% movieId_for_this_user)

## [1] 1

Kết quả này chỉ ra rằng user đó có xem 1 trong số những movies được khuyến nghị. Để đánh giá kết quả hoạt động của Recommender trước hết chúng ta viết hàm tính số lượng movies mà users xem:

number_movies_viewed_from_recommender <- function(user_i_th) {
  
  test_raw_data %>% 
  filter(userId == all_user_future[user_i_th]) %>% 
  pull(movieId) %>% 
  unique() -> movieId_for_this_user
  
  sum(list_movies_recom_for_all[[user_i_th]] %>% pull(movieId) %in% movieId_for_this_user) -> n
  
  return(n)
}

Sử dụng hàm này để tính, ví dụ, tỉ lệ users sẽ xem ít nhất một movie được khuyến nghị từ Recommender:

sum(sapply(1:length(all_user_future), number_movies_viewed_from_recommender) != 0) / length(all_user_future)

## [1] 0.15

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

Conclusions

• 15% là tỉ lệ cao hay thấp thì còn tùy thuộc vào mục tiêu ban đầu đặt ra khi xây dựng Recommender Engine. Mặt khác, tỉ lệ này sẽ cao hơn nếu, ví dụ, hệ thống đưa ra không chỉ 5 mà là 10 movies khuyến nghị cho users.

• Để có đánh giá toàn diện làm căn cứ lựa chọn Recommander thì cần phải so sánh các Recommanders dựa trên các thước đo khác nhau về Similarity - điều mà post này chưa giải quyết.

References

1. A Survey of Accuracy Evaluation Metrics of Recommendation Tasks.
2. Evaluating Recommendation Systems.
3. Evaluating Collaborative Filtering Recommender Systems.
4. Recommender Systems: An Introduction.