Collaborative Filtering - The most popular techniques for building recommender systems
Nguyen Minh Thanh (thanhleo92@gmail.com)
30 October 2017
1 Giới thiệu
Có những hiện tượng mà chúng ta đã gặp rất nhiều lần như :
Youtube gợi ý những video mà bạn có thể sẽ thích
Facebook gợi ý kết bạn
Sau khi mua hàng trên Amazon, hệ thống sẽ tự động gợi ý ra các món hàng “Frequently bought together”
Netflix gợi ý phim cho người dùng
Bằng cách quảng cáo sản phẩm hướng vào từng đối tượng như vậy, hiệu quả của việc Marketing sẽ tăng lên cũng như tăng hiệu quả kinh doanh. Thuật toán đứng đằng sau những ứng dụng này là những thuật toán Machine Learning có tên gọi là Recommendation Systems hoặc Recommender Systems
Recommendation Systems có tuổi đời khá trẻ so với các thuật toán Machine Learning khác vì nó xuất hiện từ nhu cầu bùng nổ của Internet cách đây 10-15 năm trước.
2 Hai nhóm chính của Recommendation Systems
Có 2 thực thể chính của Recommendation Systems là \(Items\) và \(Users\). Trong đó \(Users\) là người dùng, còn \(Items\) là sản phẩm: bộ phim, bài hát, sách … Mục đích chính của các Recommendation Systems là dự báo mức độ quan tâm của một User tới Item nào đó để đưa ra chiến lược Recommend phù hợp
Các Recommendation Systems thường được chia thành 2 nhóm lớn:
Content-based systems: hệ thống sẽ recommend dựa trên đặc tính của Item. VD: một User xem rất nhiều video trên Youtube thể loại nhạc trẻ Việt của Sơn Tùng thì hệ thống Recommendation Systems sẽ gợi ý cho Users này một số video cùng thể loại như Lạc Trôi. Cách tiếp cận này yêu cầu việc sắp xếp các Item vào các nhóm rõ ràng, tuy nhiên nếu Item không có nhóm cụ thể hoặc khó xác định nhóm thì việc sử dụng Content-based Systems là không thể
Collaborative Filtering: là hệ thống gợi ý item dựa trên sự tương quan giữa các Users và Items. Có thể hiểu rằng một Item được recommend cho một User sẽ dựa trên những Users có hành động tương tự. VD: A,T,N đều thích xem clip AOE của GAMETV, ngoài ra T và A thích xem clip của Chim Sẻ Đi Nắng. Dựa trên thông tin của T và A, hệ thống có thể dự đoán rằng N sẽ thích xem clip của Chim Sẻ Đi Nắng và gợi ý cho người dùng này
\(Bài viết này chúng ta sẽ đi vào nghiên cứu Collaborative Filtering do có tính ứng dụng cao trong thực tế\)
3 Collaborative Filtering
3.1 Hai nhóm của Collaborative Filtering
Collaborative Filtering được chia thành 2 nhóm :
User-based CF: CF gợi ý User A sử dụng Item dựa trên những Users có hành động tương tự như A (như VD đã nêu ở trên)
Item-based CF: CF gợi ý User A sử dụng Item dựa trên những Item mà User khác đã từng sử dụng. VD: User vừa xem xong phần I tập phim Game of Thrones, Netfix sẽ gợi ý người dùng xem tiếp phần II của bộ phim này
3.2 Các bước tính toán Items Based Collaborative Filtering
VD: Xây dựng CF cho khách hàng dựa trên dữ liệu lịch sử vote cho các bộ phim
Các bộ phim sẽ được khách hàng đánh giá trên thang điểm từ 1 đến 5
- Bước 1: Xây dựng ma trận rating matrix dựa trên mức độ đánh giá các bộ phim của các khách hàng này
library(recommenderlab)
library(dplyr)
data("MovieLense")
data_matrix <- as(MovieLense, "matrix")
data_matrix[1:6,1:5] %>% as.data.frame() %>% head## Toy Story (1995) GoldenEye (1995) Four Rooms (1995) Get Shorty (1995)
## 1 5 3 4 3
## 2 4 NA NA NA
## 3 NA NA NA NA
## 4 NA NA NA NA
## 5 4 3 NA NA
## 6 4 NA NA NA
## Copycat (1995)
## 1 3
## 2 NA
## 3 NA
## 4 NA
## 5 NA
## 6 NA
Bước 2: Normalise dữ liệu rating: Việc đầu tiên CF sẽ tính trung bình các rating của từng User, sau đó sẽ tính giá trị giữa các các rating đến các giá trị trung bình này. Bản chất của việc normalise dữ liệu đến từ việc tính cách của khách hàng luôn khác nhau (có những người khi xem bộ phim thấy rất hay sẽ đánh giá 5đ, tuy nhiên có những người khó tính hơn chỉ đánh giá 4). Do vậy, khi tính toán trung bình sẽ mang lại mức đánh giá là tốt nhất khi những giá trị lớn hơn trung bình là bộ phim khách hàng thích còn dưới trung bình là không thích.
Bước 3: Tính toán Similarities giữa các Users và Items : Phương pháp thường được sử dụng là Cosine Similarity giữa các Users với nhau. Giá trị của Cosin Similarity giữa các Users sẽ trong khoảng [-1,1]. Giá trị 1 thể hiện 2 vector hoàn toàn Similarity với nhau, với - 1 sẽ thể hiện ngược lại qua đó sẽ tạo ra ma trận Similarity. Từ ma trận Similarity ta sẽ biết những Users nào có hành vi giống với Users nào.
Bước 4: Sử dụng phương pháp K-nearest neighbor để dự báo giá trị rating bị missing. CF sẽ lựa chọn k Users có mức độ similarity cao nhất (tức các khách hàng có hành vi giống nhất)
Bước 5: Tính giá trị dự báo rating items dựa trên trung bình điều hòa giá trị similarity và rating của các k users giống nó nhất
4 Sự khác nhau giữa CF và Association Rule
Data
– Data của thuật toán Association rule lịch sử giao dịch của khách hàng, tức khách hàng có giao dịch trên sản phẩm đó hay không.
– Data của CF sẽ dựa trên lịch sử giao dịch khách hàng tuy nhiên có phân chia thuộc tính thích hay không thích sản phẩm đó
Số lượng recommend
– Association rule sẽ recommend dựa trên rule có lift lớn hơn 1 do vậy không phải khách hàng nào cũng có recommend sử dụng sản phẩm
– CF sẽ recommend cho tất cả các khách hàng vì thuật toán đã cố gắng điền đầy đủ chỉ số recommend cho các sản phẩm của từng khách hàng
5 Thực hành:
- R cung cấp package Recommenderlab phục vụ cho việc xử lý Collaborative Filtering, tuy nhiên package này có một vài nhược điểm như:
– Sử dụng matrix dạng \(Realratingmatrix\) rất tốn dung lượng RAM
– Việc tính toán rất phức tạp và nặng. Giả sử có 500.000 khách hàng, việc tính toán Cosine Similarity giữa từng cặp khách hàng với nhau sẽ tạo ra 120 triệu giá trị. Việc này khiến cho máy tính không thể tính toán nổi
Do vậy chung ta sẽ sử dụng phương pháp khác trong R bằng việc sử dụng Sparse Matrix - Cách lưu trữ dữ liệu giúp giảm nhẹ việc tính toán.
Bài viết này sẽ sử dụng data lịch sử sử dụng thẻ tín dụng của khách hàng trên các Category qua đó sẽ recommend các Category phù hợp với khách hành để phục vụ việc upsell campaign. Collaborative Filtering sẽ được xây dựng dựa trên lịch sử giao dịch thẻ tín dụng từ 30/7/2017 trở về trước và sẽ được test trên khoảng thời gian tương lai đến thời điểm 31/10/2017 để đánh giá xem với việc ta chưa có những tác động đến khách hàng thì hành vi của khách hàng có thay đổi giống với dự báo là chính xác bao nhiêu
5.1 Chạy các Function phục vụ việc tính toán:
library(RODBC)
library(dplyr)
library(stringr)
library(lubridate)
library(reshape2)
library(recommenderlab)
library(factoextra)
library(purrr)
load(file = "./Data/score_credit_card_long.Rda")
load(file = "./Function/add_predictions_to_prediction_matrix.Rda")
load(file = "./Function/cal_cor.Rda")
load(file = "./Function/cal_cos.Rda")
load(file = "./Function/calculate_predictions.Rda")
load(file = "./Function/evaluate_cf.Rda")
load(file = "./Function/find_similarities.Rda")
load(file = "./Function/predict_cf.Rda")
load(file = "./Function/rmse_function.Rda")5.2 Tính recommendation cho khách hàng sử dụng sản phẩm
ratings_matrix <- Matrix(as.matrix(score_credit_card_long %>% select(-1)), sparse = TRUE)
items_to_predict <- 1:ncol(ratings_matrix)
users <- 1:nrow(ratings_matrix)
prediction_indices <- as.matrix(expand.grid(users,items_to_predict))
recommender_result <- predict_cf(ratings_matrix,
prediction_indices,
alg_method = "ibcf",
normalization = TRUE,
similarity_metric = cal_cos,
k = 300,
make_positive_similarities = FALSE,
rowchunk_size = 2000,
columnchunk_size = 1000)
recommender_result_final <- as.data.frame(as.matrix(recommender_result))
recommender_result_final$target_id <- score_credit_card_long$target_id
recommender_result_final <- recommender_result_final %>%
melt(id.vars = "target_id")
recommend_data <- left_join(recommender_result_final,
score_credit_card_long %>% melt(id.vars = "target_id"),
by = c("target_id", "variable"))
recommend <- recommend_data %>%
filter(value.y == 0) %>%
group_by(target_id) %>%
arrange(desc(value.x)) %>%
slice(1:3) %>%
as.data.frame()Kết quả của CF sẽ là 3 sản phẩm có chỉ số recommendation cao nhất sẽ được lựa chọn thể recommend cho khách hàng
recommend_fix %>%
select(5,2) %>%
head(12)## customer_id variable
## 1 1 Dutyfreetouristattraction
## 2 1 Insurance
## 3 1 Fuel
## 4 2 Cash
## 5 2 Advertisingservices
## 6 2 Insurance
## 7 3 Travelline
## 8 3 Others
## 9 3 Cash
## 10 4 Cash
## 11 4 Education
## 12 4 Advertisingservices5.3 Test kết quả của CF
rm(list = ls())
load(file = "./Data/recommend.Rda")
load(file = "./Data/card_status.Rda")
load(file = "./Data/rfm_data.Rda")
load(file = "./Data/test_data.Rda")
card_status$target_id <- card_status$target_id %>% as.factor
recommend_fix <- left_join(recommend, card_status) %>%
filter(value == 1)
recommend_fix_1 <- left_join(recommend_fix, rfm_data %>% select(target_id, group)) %>%
filter(group %in% c(3,4))
names(test_data)[2] <- "variable"
calculate_cf <- left_join(recommend_fix_1, test_data)Số khách hàng mà CF đưa ra recommend về hành vi chi tiêu:
recommend_fix_1 %>% distinct(target_id) %>% count()## # A tibble: 1 x 1
## n
## <int>
## 1 132038Số khách hàng mà CF đã recommend đúng:
calculate_cf %>%
filter(status == "Yes") %>%
distinct(target_id) %>% count## # A tibble: 1 x 1
## n
## <int>
## 1 13558Như vậy, CF đã recommend chính xác đến 10.27% số khách hàng. Tuy nhiên, đây là kết quả mà chúng ta không có bất kỳ sự tác động nào. Với việc áp dụng CF vào marketing campaign con số này sẽ tăng lên đáng kể.