Một giải pháp dự đoán sở thích người dùng theo thời gian

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018

DOI: 10.15625/vap.2018.00037

MỘT GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH NGƯỜI DÙNG THEO THỜI GIAN

Lê Ngọc Quyền, Nguyễn Hữu Hoà, Nguyễn Thái Nghe

Khoa Công nghệ thông tin và Truyền thông, Đại học Cần Thơ

lnquyen232@gmail.com, [email protected], ntnghe@cit.ctu.edu.vn

TÓM TẮT: Hệ thống gợi ý (Recommender Systems - RS) có thể hỗ trợ người dùng trong quá trình ra quyết định bằng cách dự đoán

sở thích dựa trên hành vi trong quá khứ của họ. Bài viết này đề xuất giải pháp kết hợp mô hình dự báo và kỹ thuật Tensor

Factorization để xem xét đến yếu tố sở thích của người dùng có thể thay đổi theo thời gian nhằm khai thác và tận dụng được các

thông tin về thời gian cũng như trình tự mà người dùng đã phản hồi trên hệ thống. Tiếp cận này đã được thực nghiệm trên các tập

dữ liệu ở các lĩnh vực khác nhau và được đánh giá bằng độ đo RMSE (Root Mean Squared Error). So sánh với các kỹ thuật

Baselines khác không quan tâm đến vấn đề ảnh hưởng của yếu tố thời gian cho thấy giải pháp này rất khả quan.

Từ khóa: Hệ thống gợi ý, kỹ thuật dự báo, phân rã ma trận, lọc cộng tác.

I. GIỚI THIỆU

Hệ thống gợi ý (Recommender Systems - RS) đã được nghiên cứu phát triển như một giải pháp hữu ích hỗ trợ

người dùng giải quyết vấn đề quá tải thông tin trong các hệ thống [4, 9]. Thông qua RS các hệ thống thông tin có thể

dự đoán được sở thích của người dùng, giúp đưa ra những gợi ý phù hợp thay vì bắt buộc người dùng phải tìm kiếm

thông tin. Để làm được điều đó RS dựa vào những hành vi hay phản hồi (feedbacks) mà người dùng đã thực hiện trong

quá khứ. Các tương tác của người dùng chủ yếu được phân loại thành phản hồi tường minh (explicit feedback) và phản

hồi tiềm ẩn (implicit feedbacks). Phản hồi tường minh được xác định thông qua việc đánh giá/xếp hạng (ví dụ, rating từ

1 đến 5; hay like (1) và dislike (0),…) mà người dùng đã đánh giá trên sản phẩm - trong trường hợp này gọi là dự đoán

xếp hạng (rating prediction). Ngược lại, phản hồi tiềm ẩn được suy ra từ các hành động của người dùng như số lần

click chuột, số lần chọn mua sản phẩm, thời gian mà người dùng đã duyệt/xem sản phẩm,…

Với tính năng dự đoán nhu cầu của người dùng và cung cấp các đề xuất, RS không chỉ làm tăng trải nghiệm

người dùng mà còn thúc đẩy tăng doanh thu của các nhà cung cấp dịch vụ. Vì thế, hiện nay đã có rất nhiều hệ thống

lớn thuộc nhiều lĩnh vực khác nhau đã ứng dụng RS để phát triển các dịch vụ phục vụ khách hàng như: Amazon,

Google News, Netflix,... Chính vì khả năng ứng dụng rộng rãi, nên việc tạo ra các RS mới và có độ chính xác cao luôn

là một chủ đề được các nhà khoa học quan tâm. Với sự thành công trong Giải thưởng của Netflix [8, 12], kỹ thuật phân

rã ma trận (Matrix factorization - MF) thuộc nhóm giải thuật lọc cộng tác đã trở thành một trong những phương pháp

phổ biến nhất hiện nay (state-of-the-art) trong lĩnh vực dự đoán xếp hạng của. Tuy nhiên, đa số các giải thuật thuộc

nhóm MF chỉ dựa vào sự tương quan giữa user và item để đưa ra dự đoán (User × Item → Rating) mà chưa quan tâm

đến yếu tố thời gian khi xây dựng mô hình gợi ý. Nói cách khác, các nhóm giải thuật MF đa số tập trung vào giới thiệu

các mục tin phù hợp với người dùng dựa vào tất cả các dữ liệu trong quá khứ của người dùng đó, mà chưa xem xét đến

yếu tố sở thích của người dùng có thể thay đổi theo thời gian. Khi đó một số đánh giá khá lâu trước đây sẽ không còn

phù hợp với sở thích hiện tại của người dùng. Chẳng hạn, khách hàng có xu hướng thích những sản phẩm mới đưa ra

thị trường gần đây hơn là những sản phẩm cũ, mặc dù trong quá khứ sản phẩm đó có thể được nhiều người ưa chuộng

nhưng đối với thời điểm hiện tại nó không còn phù hợp.

Bài viết này đề xuất giải pháp dự đoán sở thích người theo thời gian, nhằm tích hợp yếu tố thời gian vào mô

hình MF để cải thiện độ chính xác của các mô hình gợi ý truyền thống.

II. HỆ THỐNG GỢI Ý VÀ CÁC NGHIÊN CỨU LIÊN QUAN

2.1. Hệ thống gợi ý

Hệ thống gợi ý bao gồm các kỹ thuật và công cụ hỗ trợ người dùng trong việc tìm kiếm thông tin bằng cách dự

đoán sở thích (preferences) hay xếp hạng (rating) mà người dùng (user) có thể dành cho một mục thông tin (item - sản

phẩm, dịch vụ, thông tin,…) nào đó mà họ chưa xem xét tới trong quá khứ nhằm đưa ra những gợi ý phù hợp với nhu

cầu và sở thích của người dùng. Các gợi ý là kết quả được tính toán dựa trên việc thu thập dữ liệu về người dùng như

khi mua hàng, khi đưa ra các đánh giá cá nhân gọi chung là phản hồi (feedbacks). Tùy theo hệ thống mà giá trị này sẽ

có ý nghĩa khác nhau, ví dụ phản hồi có thể dùng để đo độ “phù hợp” hay “mức độ thích” (thường là các đánh giá trên

các sản phẩm) trong các hệ thống thương mại điện tử hay “năng lực/kết quả thực hiện” của người dùng trong các hệ

thống elearning.

Phản hồi của người dùng có thể là tường minh (explicit) hay tìm ẩn (implicit). Hiện nay, có rất nhiều hệ thống

lớn thu thập thông tin phản hồi từ khách hàng một cách tường minh, như Ebay, Amazon, LastFM, NetFlix,.. ở đó người

sẽ trực tiếp đánh giá trên sản phẩm, như bình chọn từ « (không thích) đến ««««« (rất thích); hay Youtube thu thập

thông tin qua like()/ disklike(), và các hệ thống khác [12]. Thông qua việc thu thập phản hồi tường minh, hệ thống

274

MỘT GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH NGƯỜI DÙNG THEO THỜI GIAN

dễ dàng xác định mức độ yêu thích của người dùng trên sản phẩm, từ đó dự đoán các sản phẩm tiếp theo mà người

dùng có thể thích để gợi ý cho họ. Tuy nhiên, điều này có thể gây bất lợi do không phải người dùng lúc nào cũng sẳn

sàng/vui lòng để lại các phản hồi của họ, vì vậy hệ thống cần xác định người dùng cần gì thông qua phản hồi tiềm ẩn

dựa vào hành vi của người dùng như: số lần click chuột, số lần chọn mua sản phẩm, thời gian mà người dùng đã

duyệt/xem sản phẩm,…

Cấu trúc của một hệ thống gợi ý gồm ba thành phần chính: người dùng (user), mục tin (item, item có thể là sản

phẩm, bộ phim, bài hát, bài báo,... tùy vào mỗi hệ thống) và phản hồi (feedback) của người dùng trên mục tin đó

(thường là các xếp hạng/đánh giá - rating biểu diễn mức độ thích/quan tâm của họ). Các thông tin này được biểu diễn

thông qua một ma trận như Hình 1. Ở đó, mỗi dòng là một user, mỗi cột là một item, và mỗi ô là một giá trị phản hồi

(ví dụ, xếp hạng) biểu diễn “mức độ thích” của user trên item tương ứng. Các ô có giá trị là những item mà các user đã

xếp hạng trong quá khứ. Những ô trống là những item chưa được xếp hạng (điều đáng lưu ý là mỗi user chỉ xếp hạng

cho một vài item trong quá khứ, do vậy có rất nhiều ô trống trong ma trận này - còn gọi là ma trận thưa - sparse

matrix).

Items

Users

Hình 1. Ma trận biểu diễn dữ liệu trong RS

Nhiệm vụ chính của RS là dựa vào các “ô đã có giá trị” trong ma trận trên, thông qua mô hình đã được xây

dựng, RS dự đoán “các ô còn trống”, 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ự, từ đó gợi ý chúng cho người dùng. Bài toán gợi ý có thể được biểu diễn như sau:

Gọi U là một tập hợp n người dùng (user), |U| = n, và u là một người dùng cụ thể nào đó (u ∈ U).

Gọi I là một tập hợp m mục thông tin (item), |I| = m, và i là một mục thông tin cụ thể nào đó (i ∈ I).

Gọi R là một tập hợp các giá trị phản hồi của người dùng (các phản hồi này thường là “sở thích” (preference)

của người dùng) và r_ui∈ R là xếp hạng của người dùng u trên mục thông tin i.

Gọi r(u, i) là hàm đo độ phù hợp (hay hạng) của sản phẩm i với người dùng u: (

̂: U I R)

Mục tiêu của RS là tìm một hàm dự đoán giá trị xếp hạng của người dùng sao cho hàm mục tiêu (objective

function) ) thỏa mãn một điều kiện nào đó. Ví dụ, nếu là một hàm ước lượng độ chính xác thì nó cần phải

được tối đa hóa, còn nếu là hàm để đo độ lỗi như Root Mean Squared Error thì nó cần phải được tối thiểu.

2.2. Dự báo dựa trên phân tích chuỗi thời gian

Dự báo (forecasting) là phương pháp tiên đoán những sự việc sẽ xảy ra trong tương lai, trên cơ sở phân tích

khoa học về các dữ liệu đã thu thập được. Hiện nay, có rất nhiều phương pháp dự báo từ phương pháp đơn giản đến

phức tạp. Về cơ bản có thể chia làm 2 nhóm: định tính (qualitative) và định lượng (quantitative [2, 3].

Dự báo định tính (qualitative): Được sử dụng điển hình khi không có thông tin cho các mô hình toán học. Khi

đó dự báo được đưa ra bằng cách phân tích định tính dựa vào suy đoán, cảm nhận. Các phương pháp này phụ

thuộc nhiều vào trực giác, kinh nghiệm và sự nhạy cảm của nhà quản trị trong quá trình dự báo, chỉ mang tính

phỏng đoán, không định lượng. Tuy nhiên chúng có ưu điểm là đơn giản, dễ thực hiện thời gian nghiên cứu dự

báo nhanh, chi phí dự báo thấp và kết quả dự báo trong nhiều trường hợp cũng rất tốt.

Dự báo định lượng (quantitative): Các phương pháp dự báo định lượng dựa vào các số liệu thống kê và thông

qua các công thức toán học được thiết lập để dự báo nhu cầu cho tương lai. Khi dự báo nhu cầu tương lai, nếu

không xét đến các nhân tố ảnh hưởng khác có thể dùng các phương pháp dự báo theo chuỗi thời gian. Nếu cần

ảnh hưởng của các nhân tố khác đến nhu cầu có thể dùng các mô hình hồi quy tương quan,...

Bài viết này chỉ tập trung đến phương pháp dự báo định lượng, trong đó phương pháp dựa báo chuỗi thời gian (time

series forcasting) là một phương pháp được sử dụng rất phổ biến. Trong phương pháp này đại lượng cần dự báo được xác

định trên cơ sở phân tích chuỗi các số liệu thu được trong quá khứ. Các yếu tố đặc trưng của chuỗi thời gian gồm:

Tính xu hướng (Trend): Thể hiện sự thay đổi của các dữ liệu theo thời gian (tăng, giảm,...);

Tính mùa vụ (Season): Thể hiện sự dao động hay biến đổi dữ liệu theo thời gian được lặp đi lặp lại theo những

chu kỳ đều đặn do sự tác động của một hay nhiều nhân tố môi trường xung quanh như tập quán sinh hoạt, hoạt

động kinh tế - xã hội;

Biến đổi có chu kỳ (Cycle): Là yếu tố lặp đi lặp lại sau một giai đoạn thời gian, như chu kỳ sinh học, chu kỳ

Lê Ngọc Quyền, Nguyễn Hữu Hoà và Nguyễn Thái Nghe

275

phục hồi kinh tế,...

Biến đổi ngẫu nhiên (Randomness): Dao động dữ liệu do các yếu tố ngẫu nhiên gây ra, không có quy luật.

Có nhiều kỹ thuật dùng để dự báo dựa trên việc phân tích chuỗi thời gian, về cơ bản chúng được chia thành 2

nhóm: mô hình hóa chuỗi thời gian động (open/dynamic model time series) và các kỹ thuật phân tích chuỗi thời gian cố

định (fixed model time series) [2, 3]. Ở đây, chúng tôi tập trung trên một số phương pháp dự đoán dựa trên phân tích

chuỗi thời gian điển hình như: Phương pháp trung bình có trọng số (Weighted Moving Average): Tương tự như

phương pháp trung bình đơn nhưng có gán trọng số cho dữ liệu. Phương pháp san bằng hàm số mũ (Exponential

Smoothing - ES): Đây là phương pháp dự đoán dựa trên dữ liệu gần nhất cộng với phần trăm chênh lệch giữa số dự

đoán và số thực tế ở thời điểm dự đoán. Từ đó đề xuất cách tích hợp chúng vào mô hình Tensor Factorization trong hệ

thống gợi ý.

III. GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH CỦA NGƯỜI DÙNG THEO THỜI GIAN

3.1. Kỹ thuật phân rã ma trận

Kỹ thuật phân rã ma trận (Matrix factorization - MF) được thực hiện thông qua việc chia một ma trận lớn X

thành 2 ma trận có kích thước nhỏ hơn rất nhiều so với ma trận ban đầu là W và H, sao cho X có thể được xây dựng lại

từ hai ma trận này càng chính xác càng tốt [8], nghĩa là như minh hoạ trong Hình 2.

Hình 2. Minh họa kỹ thuật phân rã ma trận

Trong đó:

| |

K là số nhân tố tiềm ẩn nhỏ hơn rất nhiều so với số người dùng và số mục dữ liệu (K << và K << ).

∈

là một ma trận mà mỗi dòng là một véctơ bao gồm K nhân tố tiềm ẩn (latent factors) mô tả user u.

là một ma trận mà mỗi dòng là một véctơ bao gồm K nhân tố tiềm ẩn mô tả cho item i.

| |

∈

Ý tưởng chính của MF là tồn tại các tính chất ẩn (latent features) mô tả sự liên quan giữa các items và users.

Mỗi item sẽ mang tính chất ẩn ở một mức độ nào đó tương ứng với các hệ số trong véctơ h_i, hệ số càng cao tương ứng

với việc mang tính chất đó càng cao. Tương tự, mỗi user cũng sẽ có những tính chất ẩn nào đó và được mô tả bởi các

hệ số trong véctơ w_u. Gọi và là các phần tử tương ứng của hai ma trận W và H, khi đó xếp hạng của người

dùng u trên mục dữ liệu i được dự đoán bởi công thức:

∑

3.2. Tích hợp kỹ thuật dự báo vào Tensor Factorization

Trong mô hình MF, gợi ý sở thích của người dùng được đưa ra dựa vào thông tin từ các ma trận user và item

(user × item → rating) mà không quan tâm đến thông tin thời gian khi cung cấp các gợi ý. Nói cách khác MF tập trung

vào giới thiệu các item phù hợp nhất với người dùng dựa vào tất cả các dữ liệu trong quá khứ mà không xem xét đến

yếu tố sở thích của khách hàng có thể thay đổi dưới sự tác động của yếu tố thời gian. Chẳng hạn 3 năm trước người

dùng thích chiếc xe máy Honda Airblade thì 3 năm sau họ có thể thích chiếc ô tô Honda City (do điều kiện kinh tế,

công việc, gia đình,... thay đổi theo thời gian). Trong RS yếu tố thời gian có thể được khai thác theo các cách [1, 7, 10,

13]:

- Thời gian tuyệt đối (Concrete time): đại diện cho các điểm thời gian cụ thể. Dạng thời gian này thường được

sử dụng trong các hệ thống gợi ý theo ngữ cảnh. Ví dụ: khoảng thời gian trong ngày, ngày trong tuần, tháng

hoặc mùa trong năm.

- Thời gian tương đối (Relative time): mô tả chuỗi dữ liệu có thứ tự (order). Ví dụ trình tự giải quyết một bài

tập trong hệ thống giảng dạy, danh sách các sản phẩm được sắp xếp theo độ yêu thích tăng dần của người

dùng,... Loại thời gian này thường được sử dụng trong kỹ thuật dự báo hoặc trong mô phỏng dữ liệu tuần tự.

Có nhiều bài viết nghiên cứu về hệ thống gợi ý có tác động của yếu tố thời gian và các kỹ thuật để xây dựng

chúng như: Mô hình lọc cộng tác với yếu tố thời gian động (Collaborative Filtering with Temporal Dynamics) [8], theo

đó Koren đã đề xuất nhiều mô hình dự đoán với yếu tố thời gian và đặc biệt mô hình nổi bật là TimeSVD++. Ngoài ra,

nhằm tận dụng và khai thác triệt để dữ liệu quá khứ của người dùng, [14] đã khai thác yếu tố thời gian với tiếp cận sử

276

MỘT GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH NGƯỜI DÙNG THEO THỜI GIAN

dụng thời gian tương đối để xây dựng mô hình dự đoán. Theo đó mô hình này tích hợp hàm dự báo trung bình động

(Moving Average) vào giải thuật lọc cộng tác để xây dựng hàm dự đoán. Ở một nghiên cứu khác, [13] cũng đã sử dụng

hàm trung bình có trọng số (Weighting Average) để xử lý yếu tố thời gian trong gợi ý kết quả học tập sinh viên. Các

nghiên cứu trên điều cho kết quả rất khả quan nhưng chỉ mới dừng lại ở việc thực nghiệm trên các tập dữ liệu thuộc

lĩnh vực giáo dục. Để phát triển và làm đa dạng các thuật toán xử lý thời gian tương đối trong lĩnh vực gợi ý, bài viết

này đề xuất tích hợp phương pháp dự báo làm trơn hàm mũ ES vào mô hình MF thông qua kỹ thuật phân tích nhân tố

tiềm ẩn Tensor Factorization và được thực nghiệm không chỉ trên các tập dữ liệu thuộc lĩnh vực giáo dục mà còn trên

nhiều lĩnh vực khác.

Để tích hợp phương pháp dự báo làm trơn hàm mũ (Exponential Smoothing - ES) vào mô hình MF, thay vì chỉ

sử dụng thông tin từ các ma trận user và item để xây dựng mô hình dự đoán, mô hình sẽ tích hợp thêm thông tin từ các

ma trận có liên quan đến yếu tố thời gian khi người dùng đưa ra dự đoán được mô tả ở Hình 3.

Hình 3. Biểu diễn mô hình dự đoán với yếu tố thời gian

Ý tưởng của mô hình đề xuất là khi đưa ra dự đoán của u trên i tại thời điểm T, trước hết sắp xếp trình tự dự

đoán của một người dùng theo thời gian, sau đó từ thời điểm T hiện tại lấy lùi về sau L giao dịch trong quá khứ của

người dùng đó để lấy dữ liệu rating theo thời gian của người dùng (dữ liệu thời gian tuần tự). Khi đó ta áp dụng

phương pháo dự báo làm trơn hàm mũ ES để tìm giá trị dự báo tại T và tích hợp kết quả dự báo vào MF như trình bày

trong Hình 4.

Hình 4. Mô tả ý tưởng mô hình đề xuất

Ma trận W, H lần lượt là các ma trận nhân tố tiềm ẩn của user và item. Ma trận Q trong Hình 3 là ma trận biểu

diễn các nhân tố tiềm ẩn đại diện cho yếu tố thời gian. Khi đó mô hình dự đoán được định nghĩa theo công thức:

∑

Trong đó K là số nhân tố tiềm ẩn, T là thời điểm hiện tại (current time) trong chuỗi thời gian dự đoán và

được mô tả bởi công thức:

∑

Trong đó:

- : là véctơ tiềm ẩn đại diện cho thời gian;

: là véctơ đại diện cho yếu tố tiềm ẩn của các item trước đó của user hiện tại;

- L: là độ dài số giao dịch trong quá khứ của user hiện tại được sử dụng cho hàm dự báo thời gian;

- : là giá trị làm trơn mũ tại thời điểm t của user hiện tại;

Với α là hằng số làm trơn mũ (0 < α < 1).

Lê Ngọc Quyền, Nguyễn Hữu Hoà và Nguyễn Thái Nghe

277

Giá trị là giá trị dự đoán trước đó của user hiện tại. Tham số

thể hiện cho sự liên quan của item hiện

tại với các item đã đánh giá trước đó. Ví dụ, người dùng đã mua điện thoại và hiện tại mua thêm các phụ kiện khác như

ốp lưng, kính cường lực thì các sản phẩm này sẽ có sự liên quan với nhau.

Ở đây cũng sử dụng các giá trị thiên vị (biases) cho mô hình dự đoán để tránh tình trạng thiên vị trong quá trình

đưa ra đánh giá [8]. Khi đó công thức dự đoán sẽ trở thành:

∑

Trong đó µ là giá trị trung bình toàn cục, được xác định từ tập dữ liệu huấn luyện qua công thức:

∑

)

( ∈

Giá trị b_ulà độ thiên vị (bias) của người dùng u, xác định bởi:

∑

( ∈

)| |

{

}

| ∈

| | |

Giá trị bi là độ thiên vị (bias) của item i, xác định bởi:

∑

( ∈

)| |

{

}

| ∈

| | |

Đối với mô hình đề xuất, số lượng tham số của mô hình dự đoán sẽ khác với MF, chúng tôi gọi hướng tiếp cận

mới này là TFES (Tensor factoriztion - Exponential Smoothing). Khi đó, hàm mục tiêu của mô hình dự đoán trở thành:

‖ ‖

∑

∈

Trong đó W, H , Q lần lượt là các ma trận nhân tố tiềm ẩn đại diện cho user, item và time. P là ma trận đại điện

cho các yếu tố tiềm ẩn của các item mà người dùng đánh giá trước đó. λ là hệ số chính tắc hóa (0 ≤ λ <1) tương tự như

MF. Hàm mục tiêu

vẫn được tối ưu bằng phương pháp SGD, tức là các tham số w, h, p, q tương ứng sẽ được cập

nhật theo công thức:

(

)

(

);

(

)

(

);

Với

β là tốc độ học (learning rate, 0 < β < 1);

và

Giá trị của

được xác định bởi công thức:

;

∑

;

∑

(

) ;

Sau quá trình tối ưu, ta nhận được các tham số W, H, P, Q. Khi đó, chúng ta có thể dự đoán kết quả xếp hạng

cho user u trên item i dễ dàng. Giải thuật TFES được mô tả như dưới đây, trong đó đầu vào: Một bộ dữ liệu huấn luyện

D^train, giá trị khởi tạo bạn đầu W, H, P, Q; Đầu ra: Các ma trận W, H, P, Q sau khi được tối ưu.

278

MỘT GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH NGƯỜI DÙNG THEO THỜI GIAN

1: procedure LearnTFES(D^train,K,β,λ,L,α,stop_condition)

//Khởi tạo giá trị theo phân phối chuẩn ϭ = 0.01

2: {W,H,H^’,Q}  Ɲ(0, ϭ²)

∑

( ∈

)

for each user u do

∑

end for

for each item i do

∑

end for

while (Not stop_condition) do

Chọn dòng ngẫu nhiên từ tập D^train

∑

( (

))

10:

11:

12:

13:

14:

15:

//với

for k ←1 … K do

16:

(

)

17:

18:

19:

(

)

for do

(

)

20:

(

)

21:

22:

23:

24:

end for

end while

return {W, H, H^’, Q, b_u, b_i, }

25: end procedure

IV. KẾT QUẢ

Dữ liệu dùng để thực nghiệm mô hình đề xuất là các bộ dữ liệu được thu thập từ các hệ thống thông tin thuộc

hai lĩnh vực giáo dục và giải trí. Đây là các bộ dữ liệu chuẩn thường được sử dụng để đánh giá giải thuật trong lĩnh vực

gợi ý. Đối với lĩnh vực giáo dục, bài viết này sử dụng tập dữ liệu Assistments (2008-2009) từ Assistments Platform.

Tập dữ liệu này có nguồn gốc từ hệ thống trợ giảng thông minh (intelligent tutoring systems - ITS), được thu thập bằng

cách ghi lại nhật ký tương tác của sinh viên và hệ thống. Trong khi sinh viên làm các bài tập trên hệ thống ITS, các

hoạt động và kết quả của họ được ghi lại theo từng hàng trong bộ dữ liệu. Phản hồi của người dùng trong trường hợp

này là kết quả sinh viên giải quyết các bài tập (0: sai, 1: đúng). Các phản hồi sẽ được dùng để dự đoán bài tập kế tiếp

sinh viên có khả năng thực hiện đúng hay sai để đưa ra những gợi ý thích hợp. Đối với lĩnh vực giải trí, tập dữ liệu

Movielens được thu thập từ hệ thống gợi ý phim GroupLens, tập MovieLens 1M được dùng để thực nghiệm mô hình

đề xuất. Thông tin của các tập dữ liệu được mô tả ở Bảng 1.

Bảng 1. Mô tả tập dữ liệu thực nghiệm

Dataset

Users

8,519

6,040

Items

35,978

3,900

Rating

1,011,079

1,000,209

Assistments

MovieLens 1M

Đặc trưng của TFES là yếu tố thời gian trong hệ thống gợi ý, đặc biệt là chuỗi thời gian, vì thế trước khi thực thi

TFES cần phải tiền xử lý dữ liệu bằng sắp xếp các đánh giá của người dùng theo thời gian người dùng đưa ra dự đoán.

Việc phân chia tập dữ liệu để huấn luyện và kiểm tra phụ thuộc vào đặc điểm của mỗi tập dữ liệu và mục đích gợi ý.

Đối với tập dữ liệu thuộc lĩnh vực giáo dục, cụ thể là Assistments thì dữ liệu thực nghiệm sẽ được phân chia theo đề

xuất của KDD cup 2010 trong Hình 5.

Lê Ngọc Quyền, Nguyễn Hữu Hoà và Nguyễn Thái Nghe

279

Hình 5. Mô tả định dạng dữ liệu ITS (Nguồn: pslcdatashop.web.cmu.edu/KDDCup)

Trong hình trên, mỗi đường ngang là 1 dòng biểu diễn 1 bước (step) của sinh viên khi thực hiện một yêu cầu

hoặc một bài tập gọi chung là nhiệm vụ (task). Mỗi một nhiệm vụ bao gồm nhiều vấn đề (problem) và để giải quyết

được mỗi vấn đề trong nhiệm vụ đó sinh viên cần phải trải qua nhiều bước. Tập dữ liệu kiểm tra thu được bằng cách

lấy ngẫu nhiên các bước thuộc một vấn đề (steps for one problem) trong một nhiệm vụ của sinh viên. Phần còn lại sẽ

được sử dụng làm dữ liệu huấn luyện. Đối với tập dữ liệu thuộc lĩnh vực giải trí, Movielens 1M sẽ được phân chia bằng

cách lấy các giao dịch cuối cùng của một user làm tập kiểm tra, phần còn lại sẽ sử dụng làm dữ liệu huấn luyện như

trong Hình 6. Số lượng giao dịch được lấy được tính toán sao cho số tập kiểm tra (test) chiếm 30 % của tập dữ liệu, còn

lại 70 % dùng làm tập huấn luyện (train).

Hình 6. Mô tả cách chia dữ liệu Movielens

Kết quả thực nghiệm được so sánh bằng độ lỗi Root Mean Squared Error (RMSE) của mô hình TFES với MF,

Global Average, User Average và Item Average. Thực nghiệm cho thấy TFES cho kết quả cao trên tập dữ liệu thuộc

lĩnh vực giáo dục Assistments. Tuy nhiên, với tập dữ liệu lĩnh vực giải trí Movielens thì TFES cho kết quả chưa như

mong đợi. Điều đó cho thấy việc tích hợp phương pháp làm trơn hàm mũ đơn (ES) vào mô hình gợi ý sẽ đạt kết quả

cao trên tập dữ liệu có tính chất tuần tự, tích lũy dần theo thời gian và không có tính xu hướng. Ví dụ, đối với hệ thống

giáo dục, kết quả học tập hiện tại của sinh viên phụ thuộc rất nhiều vào quá trình học tập trước đó (dữ liệu có tính tích

lũy dần theo thời gian) nên mô hình TFES cho kết quả rất khả quan. Mặc khác, đối với lĩnh vực giải trí, sở thích của

người dùng có thể còn phụ thuộc vào nhiều yếu tố khác như: xu hướng, ngữ cảnh,… mà mô hình TFES chưa khai thác

hết được các yếu tố này. Do số lượng tham số mô hình cần tìm của TFES nhiều hơn MF dẫn đến quá trình huấn luyện

mô hình của TFES sẽ mất nhiều thời gian hơn. Tuy nhiên, trong thực tế việc cập nhật mô hình dự đoán được thực hiện

định kỳ theo một khoảng thời gian chứ không cập nhật liên tục nên vấn đề này có thể chấp nhận được.

280

MỘT GIẢI PHÁP DỰ ĐOÁN SỞ THÍCH NGƯỜI DÙNG THEO THỜI GIAN

Assistments

M O V I E L E N S 1 M

Global Average

User Average

Item Average

Global Average

User Average

Item Average

0.483

1.174

0.485

1.2

1.15

1.1

0.477

0.48

0.475

0.47

0.465

0.46

0.475

1.095

1.077

TFES

1.05

0.95

0.9

0.465

0.985

0.981

TFES

0.461

0.455

0.45

0.85

Root Mean Squared Error - RMSE

Hình 7. Kết quả so sánh RMSE

V. KẾT LUẬN

Bài viết này đề xuất giải pháp kết hợp mô hình dự báo và kỹ thuật Tensor Factorization để xem xét đến yếu tố

sở thích của người dùng có thể thay đổi theo thời gian nhằm khai thác và tận dụng được các thông tin về thời gian cũng

như trình tự mà người dùng đã phản hồi trên hệ thống. Tiếp cận này đã được thực nghiệm trên các tập dữ liệu ở các

lĩnh vực khác nhau và được đánh giá bằng độ đo RMSE (Root Mean Squared Error). So sánh với các kỹ thuật

Baselines khác không quan tâm đến vấn đề ảnh hưởng của yếu tố thời gian cho thấy giải pháp này rất khả quan.

VI. TÀI LIỆU THAM KHẢO

[1] Adomavicius G., Mobasher B., Ricci F., Tuzhilin A., 2011. Context-Aware Recommender Systems. AI Mag. 32, 67-80.

doi:10.1609/aimag.v32i3.2364.

[2] Bengio Y., 1996. Markovian Models for Sequential Data, in: Neural Computing Surveys, Vol. 2, Pp. 129- 162, 1999.

[3] Box G. E. P., Jenkins G. M., Reinsel G. C., Ljung G. M., 2015. Time Series Analysis: Forecasting and Control. John Wiley & Sons.

[4] Charu C. Aggarwal. 2016. Recommender Systems: The Textbook (1st ed.). Springer Publishing Company, Incorporated.

[5] Herlocker, J. L., Konstan, J. A., Terveen, L. G., Riedl, J. T., 2004. Evaluating collaborative filtering recommender systems.

ACM Trans. Inf. Syst. 22, 5-53. doi:10.1145/963770.963772.

[6] Hu Y., Koren Y., Volinsky C., 2008. Collaborative Filtering for Implicit Feedback Datasets. Presented at the 2008 Eighth

IEEE International Conference on Data Mining, pp. 263-272. doi:10.1109/ICDM.2008.22.

[7] Kolda T., Bader B., 2009. Tensor Decompositions and Applications. SIAM Rev. 51, 455-500. doi:10.1137/07070111X.

[8] Koren Y., Bell R., 2011. Advances in Collaborative Filtering, in: Recommender Systems Handbook. Springer, Boston, MA,

pp. 145-186. doi:10.1007/978-0-387-85820-3_5.

[9] Nguyen Dang Thanh, Mumtaz Ali, Le Hoang Son. 2017. A Novel Clustering Algorithm in a Neutrosophic Recommender

System for Medical Diagnosis. Cognitive Computation 9(4): 526-544.

[10] Nicholas D. Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E. Papalexakis, and Christos Faloutsos.

2017. Tensor Decomposition for Signal Processing and Machine Learning. Trans. Sig. Proc. 65, 13 (July 2017), 3551-3582.

[11] Rendle S., Freudenthaler C., Schmidt-Thieme, L., 2010. Factorizing Personalized Markov Chains for Next-basket

Recommendation, in: Proceedings of the 19th International Conference on World Wide Web, WWW ’10. ACM, New York,

NY, USA, pp. 811-820. doi:10.1145/1772690.1772773.

[12] Ricci F., Rokach L., Shapira B., Kantor P. B. (Eds.), 2011. Recommender Systems Handbook. Springer US, Boston, MA.

doi:10.1007/978-0-387-85820-3.

[13] Thai-Nghe N., Schmidt-Thieme L.. 2015. Factorization Forecasting Approach for User Modeling. Journal of Computer

Science and Cybernetics. 133-148. Vol 31, No 2. ISSN: 1813-9663. DOI: 10.15625/1813-9663/31/2/5860.

[14] Thai-Nghe N., Drumond L., Krohn-grimberghe A., Nanopoulos, R., Schmidt-thieme, L., 2011. Factorization techniques for

predicting student performance, in: In Educational Recommender Systems and Technologies: Practices and Challenges.

[15] Yorucu, V., 2003. The Analysis of Forecasting Performance by Using Time Series Data for Two Mediterranean Islands. Rev.

Soc. Econ. Bus. Stud. 2.

AN APPROACH FOR TEMPORAL PREDICTION IN RECOMMENDER SYSTEMS

Le Ngoc Quyen, Nguyen Huu Hoa, Nguyen Thai Nghe

ABSTRACT: Recommender Systems (RS) can be used to support users in decision making. User preferences may change over the

time since environments are changed. For example, economic, promotion, and family conditions are changed thus user needs may

also be changed. This work proposes an approach for integrating time series forecasting to collaborative filtering methods in RS to

take into account the times/sequences in the prediction models. Results show that this approach could be promissing for sequential

data in RS.

8 trang Thùy Anh 17280 Free

Download

Bạn đang xem tài liệu "Một giải pháp dự đoán sở thích người dùng theo thời gian", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

mot_giai_phap_du_doan_so_thich_nguoi_dung_theo_thoi_gian.pdf