Recommendation System (Part 1)

R Machine Learning Series

Introduction to Collaborative Filtering Recommender

Hệ thống khuyến nghị (Recommendation System) là một Engine được sử dụng phổ biến ở nhiều công ti thương mại điện tử. Collaborative Filtering Recommender (CFR) là một cách tiếp cận (mô hình) dựa trên dữ liệu lịch sử về hành vi mua sắm của khách hàng với ý tưởng rằng nếu, ví dụ, hai khách hàng cùng mua một cuốn sách (hoặc xem cùng một bộ phim) thì rất có thể họ sẽ tái diễn pattern đó trong tương lai. Hoặc hai khách hàng A và B được cho là có hành vi mua sắm tương tự nhau thì nếu khách hàng A đã xem một bộ phim X nào đó nhưng B thì lại chưa xem bộ phim này thì nếu hệ thống gợi ý rằng nên giới thiệu phim X này cho khách hàng B. Cách tiếp cận này rõ ràng chỉ dựa trên sở thích của khách hàng (user preferences) chứ không dựa trên những đặc điểm hay nội dung (contents) của sách/phim để đưa ra khuyến nghị cho người dùng/khách hàng tiềm năng.

Bài viết này minh họa việc xây dựng CFR bằng ngôn ngữ R với bộ dữ liệu từ MovieLens (phiên bản small) bao gồm 105339 ratings của 10329 bộ phim từ 668 user trong khoảng thời gian từ April 03, 1996 đến January 09, 2016. Bộ dữ liệu này có thể download ở đây. Định hướng thực hành nên các lí thuyết và cơ sở toán học về Recommendation System sẽ không được trình bày ở đây. Bạn đọc được giả định là đã có những hiểu biết nhất định về Recommendation System.

Data pre-processing and Exploratory Data Analysis

Tiền xử lí số liệu (Data pre-processing) và phân tích khám phá dữ liệu EDA (Exploratory Data Analysis) là bước luôn phải được thực hiện đầu tiên của một data project. Trước hết đọc hai files dữ liệu movies.csv và ratings.csv:

# Clear workspace: 

rm(list = ls())

# Load data: 

library(tidyverse)

movies <- read_csv("C:/Users/Admin/Documents/ml-latest-small/movies.csv")

ratings <- read_csv("C:/Users/Admin/Documents/ml-latest-small/ratings.csv")

Bộ dữ liệu movies miêu tả về phim (tên phim + thể loại) và mã movieId tương ứng của phim. Còn bộ dữ liệu ratings là xếp hạng của người dùng đối với một bộ phim mà họ đã xem. Chúng ta có thể xem qua những dữ liệu này:

# Show some observations: 

library(knitr)

kable(movies %>% head(), caption = "Table 1: Movie data")

Table 1: Movie data

movieId	title	genres
1	Toy Story (1995)	Adventure|Animation|Children|Comedy|Fantasy
2	Jumanji (1995)	Adventure|Children|Fantasy
3	Grumpier Old Men (1995)	Comedy|Romance
4	Waiting to Exhale (1995)	Comedy|Drama|Romance
5	Father of the Bride Part II (1995)	Comedy
6	Heat (1995)	Action|Crime|Thriller

kable(ratings %>% head(), caption = "Table 2: Rating data")

Table 2: Rating data

userId	movieId	rating	timestamp
1	1	4	964982703
1	3	4	964981247
1	6	4	964982224
1	47	5	964983815
1	50	5	964982931
1	70	3	964982400

Riêng cột biến timestamp là ở dạng Epoch time và chúng ta có thể chuyển về date time để thực hiện những phân tích xa hơn nếu cần:

# Convert to real date time:

library(lubridate)

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

Cột biến genres mô tả thể loại của phim. Để thuận lợi cho các phân tích sau này thì no genres listed nên thay bằng Other và dấu - được thay bằng _ như sau:

# Relabel for some genres: 

movies %>% 
  mutate(genres = genres %>% 
           str_replace_all("\\(no genres listed\\)", "Other") %>% 
           str_replace_all("-", "_")) -> movies

Chúng ta kì vọng rằng số lượng các movieId ở hai bộ số liệu là trùng nhau nhưng thực tế không phải vậy:

ratings$movieId %>% n_distinct()

## [1] 9724

movies$movieId %>% n_distinct()

## [1] 9742

Do vậy chúng ta sẽ chỉ lấy ra những bộ phim mà thuộc về cả hai bộ dữ liệu ratings và movies:

# Common movieId: 

base::intersect(ratings$movieId %>% unique(), movies$movieId %>% unique()) -> common_movies

# Filter data by common_movies: 

movies %>% filter(movieId %in% common_movies) -> movies_common

ratings %>% filter(movieId %in% common_movies) -> ratings_common

# Combine data: 

full_join(movies_common, ratings_common, by = "movieId") -> movie_data

# Some observations: 

movie_data %>% head()

## # A tibble: 6 x 8
##   movieId title  genres   userId rating timestamp real_time           date_ymd  
##     <dbl> <chr>  <chr>     <dbl>  <dbl>     <dbl> <dttm>              <date>    
## 1       1 Toy S~ Adventu~      1    4      9.65e8 2000-07-30 18:45:03 2000-07-30
## 2       1 Toy S~ Adventu~      5    4      8.47e8 1996-11-08 06:36:02 1996-11-08
## 3       1 Toy S~ Adventu~      7    4.5    1.11e9 2005-01-25 06:52:26 2005-01-25
## 4       1 Toy S~ Adventu~     15    2.5    1.51e9 2017-11-13 12:59:30 2017-11-13
## 5       1 Toy S~ Adventu~     17    4.5    1.31e9 2011-05-18 05:28:03 2011-05-18
## 6       1 Toy S~ Adventu~     18    3.5    1.46e9 2016-02-11 16:56:56 2016-02-11

Như đã đề cập CFR là cách tiếp cận mà chỉ căn cứ hành vi của user chứ không sử dụng thông tin về content của phim (hay sách). Điều này có nghĩa là cột biến genres về thể loại phim (có thể xem như đây là một dạng content đơn giản) sẽ không sử dụng khi xây dựng CFR. Tuy nhiên chúng ta có thể sử dụng genres sau này. Vậy nên tiện thể chúng ta viết một hàm có tên convert_to_01_content để covert về ma trận nhị phân (binary matrix)

convert_to_01_content <- function(genres) {
  
  genres %>% 
    str_split(pattern = "\\|", simplify = TRUE) %>% 
    data.frame() -> df_ith
  
  names(df_ith) <- df_ith %>% slice(1) 
  
  return(df_ith %>% mutate(genres = genres))
}

Sử dụng hàm này cho cột biến genres đồng thời tạo binary matrix/data frame:

lapply(movie_data$genres, convert_to_01_content) -> df_genres

do.call("bind_rows", df_genres) -> df_genres

# Convert to binary matrix/data frame: 

df_genres %>% 
  select(-genres) %>% 
  mutate_all(function(x) {case_when(is.na(x) ~ 0, TRUE ~ 1)}) -> df_genres01

# Combine data sets: 

movie_data %>% bind_cols(df_genres01) -> movie_data_01 

# Show some observations: 

movie_data_01 %>% head()

## # A tibble: 6 x 28
##   movieId title genres userId rating timestamp real_time           date_ymd  
##     <dbl> <chr> <chr>   <dbl>  <dbl>     <dbl> <dttm>              <date>    
## 1       1 Toy ~ Adven~      1    4      9.65e8 2000-07-30 18:45:03 2000-07-30
## 2       1 Toy ~ Adven~      5    4      8.47e8 1996-11-08 06:36:02 1996-11-08
## 3       1 Toy ~ Adven~      7    4.5    1.11e9 2005-01-25 06:52:26 2005-01-25
## 4       1 Toy ~ Adven~     15    2.5    1.51e9 2017-11-13 12:59:30 2017-11-13
## 5       1 Toy ~ Adven~     17    4.5    1.31e9 2011-05-18 05:28:03 2011-05-18
## 6       1 Toy ~ Adven~     18    3.5    1.46e9 2016-02-11 16:56:56 2016-02-11
## # ... with 20 more variables: Adventure <dbl>, Animation <dbl>, Children <dbl>,
## #   Comedy <dbl>, Fantasy <dbl>, Romance <dbl>, Drama <dbl>, Action <dbl>,
## #   Crime <dbl>, Thriller <dbl>, Horror <dbl>, Mystery <dbl>, Sci_Fi <dbl>,
## #   War <dbl>, Musical <dbl>, Documentary <dbl>, IMAX <dbl>, Western <dbl>,
## #   Film_Noir <dbl>, Other <dbl>

Chúng ta có thể rút ra, ví dụ, một số insights về hành vi tiêu dùng/xem phim của các users:

# Most popular genres: 

df_genres01 %>% 
  gather(Genre, n) %>% 
  group_by(Genre) %>% 
  summarise(Freq = sum(n)) %>% 
  arrange(Freq) %>% 
  mutate(Genre = factor(Genre, levels = Genre)) %>% 
  ggplot(aes(Genre, Freq)) + 
  geom_col() + 
  coord_flip() + 
  labs(x = NULL, y = NULL, title = "Figure 1: Most Viewed Movies")

# Genre trend: 

movie_data_01 %>% 
  select(-c(1:7)) %>% 
  gather(genres, count, -date_ymd) %>% 
  group_by(date_ymd, genres) %>% 
  summarise(total = sum(count)) %>% 
  ggplot(aes(date_ymd, total, color = genres)) + 
  geom_line(show.legend = FALSE) + 
  facet_wrap(~ genres, scales = "free_x") + 
  labs(x = NULL, y = NULL, title = "Figure 2: Trend of Viewed Movies")

# Most watched movies (top 10): 

movie_data_01 %>% 
  group_by(title) %>% 
  count() %>% 
  arrange(-n) %>% 
  head(10) %>% 
  kable(caption = "Table 3: Top-10 Movies")

Table 3: Top-10 Movies

title	n
Forrest Gump (1994)	329
Shawshank Redemption, The (1994)	317
Pulp Fiction (1994)	307
Silence of the Lambs, The (1991)	279
Matrix, The (1999)	278
Star Wars: Episode IV - A New Hope (1977)	251
Jurassic Park (1993)	238
Braveheart (1995)	237
Terminator 2: Judgment Day (1991)	224
Schindler’s List (1993)	220

Không nằm ngoài dự đoán, Shawshank Redemption (bộ phim ưa thích của người viết bài này) có số lượt xem xếp thứ hai chỉ sau phim dành giải Oscar năm 1994 Forrest Gump. Chúng ta tìm hiểu thêm về một số thông tin có thể là hữu ích thu được từ bộ dữ liệu. Ví dụ: tổng số lượt người xem phim là 100836 cho tất cả 9724 bộ phim, như vậy bình quân một bộ phim được xem chừng 10.37 lần nhưng phân bố rất lệch. Thực vậy, chỉ có 450 bộ phim có số lượt xem nhiều hơn 50:

movie_data_01 %>% 
  group_by(title) %>% 
  count() %>% 
  filter(n >= 50) %>% 
  arrange(-n) -> movies_over50_viewed


kable(movies_over50_viewed %>% head(), caption = "Table 4: Top 450 Movies")

Table 4: Top 450 Movies

title	n
Forrest Gump (1994)	329
Shawshank Redemption, The (1994)	317
Pulp Fiction (1994)	307
Silence of the Lambs, The (1991)	279
Matrix, The (1999)	278
Star Wars: Episode IV - A New Hope (1977)	251

Figure 3 cho thấy rating = 4 là xếp hạng phổ biến nhất của người dùng dành cho các bộ phim:

movie_data_01 %>% 
  group_by(rating) %>% 
  count() %>% 
  ungroup() %>% 
  mutate(rating = as.factor(rating)) %>% 
  ggplot(aes(rating, n)) + 
  geom_col() + 
  labs(x = NULL, y = NULL, title = "Figure 3: Distribution of Rating")

Recommender based on Ratings: Item-based CFR

CFR có thể được xây dựng dựa vào xếp hạng (ratings) mà user bình bầu cho bộ phim họ đã xem. Nhưng trước hết chúng ta cần convert xếp hạng của những bộ phim bởi user (người xem) về ma trận thưa (sparse matrix):

# Convert to sparse matrix for ratings: 

ratings %>% 
  select(movieId, userId, rating) %>% 
  spread(value = rating, key = movieId) -> sparse_df

Vì có 610 users và 9724 bộ phim nên sparse matrix sẽ nên là một ma trận có 610 dòng và 9724 cột. Kết quả sau đây cho thấy sparse data frame dư ra một cột là userId (các cột biến khác chính là movieId - hay là các items):

head(sparse_df[1:6, 1:6])

## # A tibble: 6 x 6
##   userId   `1`   `2`   `3`   `4`   `5`
##    <dbl> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1      1     4    NA     4    NA    NA
## 2      2    NA    NA    NA    NA    NA
## 3      3    NA    NA    NA    NA    NA
## 4      4    NA    NA    NA    NA    NA
## 5      5     4    NA    NA    NA    NA
## 6      6    NA     4     5     3     5

Do vậy chúng ta cần loại bỏ cột biến userId này trước khi convert về sparse matrix bằng hàm as() như sau:

# Remove userId and convert to matrix: 

sparse_df %>% 
  select(-userId) %>% 
  as.matrix() -> ratingmat

# Convert to realRatingMatrix class for modeling Recommendation System: 

library(recommenderlab)

as(ratingmat, "realRatingMatrix") -> ratingmat

CFR vận hành dựa trên thước đo gọi là sự tương tự (similarity) hay “khoảng cách” giữa các: (1) users, (2) hoặc items và được tính toán theo ba cách khác nhau: (1) cosine similarity, (2) Pearson similarity, và (3) Jaccard similarity. Thước đo này được tính toán bằng cách sử dụng hàm similarity() của thư viện recommenderlab như sau:

# Calculate cosine similarity for 10 observation by user: 

similarity_users <- similarity(ratingmat[1:10, ], method = "cosine", which = "users")

# Plot cosine similarity heatmap: 

image(as.matrix(similarity_users), main = "Figure 4: Similarity by User")

Hoặc them items:

# Calculate cosine similarity for 10 observation by item: 

similarity_items <- similarity(ratingmat[, 1:10], method = "cosine", which = "items")

image(as.matrix(similarity_items), main = "Figure 5: Similarity by Item")

Tương tự như vậy là heatmap cho rating mà ở đó mỗi một dòng là một user còn mỗi một cột là movie. Ví dụ, 20 users + 20 movies đầu tiên:

image(ratingmat[1:20, 1:20], main = "Figure 6: Heatmap of the first 20 rows and 20 columns")

Sử dụng 80% data để train CFR và phần dữ liệu còn lại để test CFR:

set.seed(1)
id <- sample(x = 1:nrow(ratingmat), size = 0.8*nrow(ratingmat), replace = FALSE)
data_train <- ratingmat[id, ]
data_test <- ratingmat[-id, ]

Huấn luyện CFR Engine:

# Define some parameters for CFR Engine: 

my_params <- list(k = 30, method = "Cosine")

# Train CFR recommender: 

cfr_recommender <- Recommender(data = data_train, 
                               method = "IBCF",
                               parameter = my_params)

Sử dụng CFR Engine đã có để đưa ra recommendations cho các users:

# Use CFR recommender for test data. 

n_recommended <- 3

items_predicted <- predict(object = cfr_recommender, 
                           newdata = data_test, 
                           n = n_recommended)

Chúng ta cũng có thể list danh sách 20 bộ phim được đề xuất nhiều nhất bởi CFR Engine (Nixon (1995) là bộ phim được khuyến nghị nhiều lần nhất bởi CFR Engine với 10 lần):

data.frame(movieId = unlist(items_predicted@items)) %>% 
  group_by(movieId) %>% 
  count() %>% 
  ungroup() %>% 
  top_n(n = 20, wt = n) %>% 
  arrange(n) %>% 
  inner_join(movies_common %>% select(1:2)) %>% 
  mutate(title = factor(title, levels = title)) -> top_20_recommended

top_20_recommended %>% 
  ggplot(aes(title, n)) + 
  geom_col() + 
  geom_text(aes(label = n), hjust = 1.3, color = "white") + 
  coord_flip() + 
  labs(x = NULL, y = NULL, title = "Figure 7: Top-recommended Movies by CFR")

Xem 3 bộ phim mà Engine khuyến nghị cho, ví dụ, user thứ nhất (trong test data):

movies_recommended_user1 <- items_predicted@items[[1]]

movies_common %>% 
  filter(movieId %in% movies_recommended_user1) %>% 
  select(movieId, title)

## # A tibble: 3 x 2
##   movieId title                                
##     <dbl> <chr>                                
## 1       9 Sudden Death (1995)                  
## 2      71 Fair Game (1995)                     
## 3     105 Bridges of Madison County, The (1995)

Final Notes

Post này trình tập trung vào việc thực hiện tiền xử lí số liệu - chuẩn bị số liệu cho đến việc xây dựng một hệ thống khuyến nghị bằng ngôn ngữ R mà cụ thể là Collaborative Filtering Recommender. Một số vấn đề quan trọng vẫn chưa được đề cập/giải quyết là:

1. Đánh giá chất lượng của Recommender Engine. Ví dụ, sử dụng CFR Engine đã có chúng ta đưa ra khuyến cáo cụ thể ba bộ phim mà user thứ nhất nên xem. Nhưng làm thế nào để đánh giá khuyến nghị này có khớp với nhu cầu và sở thích của người này hay không?

2. Một số cách tiếp cận khác cho xây dựng Recommender Engine cũng như tinh chỉnh tham số.

3. Chất lượng của Engine còn phụ thuộc rất nhiều lựa chọn các observations phù hợp. Ví dụ: một mô hình dựa trên hành vi của user thì quan sát về user phải đủ nhiều để engine có thể “trích xuất” ra insights/pattern đại diện cho hành vi tiêu dùng (trong tình huống này là xem phim). CFR Engine được xây dựng trong post này sử dụng cả những user mà họ chỉ xem một vài phim. Những user này quá ít tương tác và do vậy hành vi của họ không rõ ràng (hoặc không có) vì thế sử dụng cả những user này khi xây dựng Recommender có thể không phù hợp.

4. Nếu có sẵn dữ liệu về ratings (là tình huống của bộ dữ liệu sử dụng trong post này) thì việc xây dựng Recommender Engine là thuận tiện. Tuy nhiên trong thực tế thì không phải lúc nào cũng có dữ liệu về rating và xây dựng một Recommender Engine lúc này trở nên khó khăn hơn.

References

1. Building Recommender Systems with Machine Learning and AI.

2. Building a Recommendation System with R.

3. Practical Recommender Systems.

4. Hands-On Recommendation Systems with Python: Start building powerful and personalized, recommendation engines with Python.

5. Evaluation Metrics for Recommender Systems.

6. Evaluating Recommendation Systems.

7. A Survey of Accuracy Evaluation Metrics of Recommendation Tasks.