ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM THỊ MY
NGHIÊN CỨU HỆ THỐNG KHUYẾN NGHỊ
NGƯỜI DÙNG DỰA VÀO LỌC CỘNG TÁC
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM THỊ MY
NGHIÊN CỨU HỆ THỐNG KHUYẾN NGHỊ
NGƯỜI DÙNG DỰA VÀO LỌC CỘNG TÁC
Ngành:
Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số:
60480103
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN VĂN VINH
HÀ NỘI – 2014
1
Lời cam đoan
Tôi xin cam đoan luận văn này là công trình nghiên cứu hoàn toàn của bản thân.
Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân tôi
hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất
xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho
lời cam đoan của mình.
Nam Định, ngày 28 tháng 09 năm 2014
Người cam đoan
Phạm Thị My
2
Lời cảm ơn
Đầu tiên, tôi xin chân thành cảm ơn thầy giáo Nguyễn Văn Vinh là cán bộ hướng
dẫn khoa học, thầy đã tận tình giúp đỡ và hướng dẫn tôi về cả chuyên môn, nghiên cứu
và định hướng phát triển trong suốt quá trình làm luận văn.
Để hoàn thành luận văn tốt nghiệp là cả một quá trình đầy khó khăn và thử thách
trong học tập và nghiên cứu tại trường Đại học Công Nghệ. Và để có được những thành
quả như ngày hôm nay, ngoài những nỗ lực của bản thân, không thể không nhắc tới là
sự động viên, giúp đỡ của các Thầy, Cô giáo, bạn bè, đồng nghiệp và người thân trong
gia đình.
Tôi cũng xin gửi lời cám ơn tới các Thầy, Cô giáo của Khoa Công Nghệ Thông
Tin, vì đã tận tình giảng dạy những kiến thức bổ ích, hiện đại về lĩnh vực Kỹ thuật phần
mềm tôi học tập và tạo mọi điều kiện cho tôi học tập nghiên cứu và hoàn thành luận văn
này.
Với gia đình, tôi xin bày tỏ lòng biết ơn sâu sắc vì gia đình đã luôn ở bên và ủng
hộ tôi trên con đường học tập và nghiên cứu.
Cuối cùng, tôi cũng xin gửi lời càm ơn đến đồng nghiệp và bạn bè tôi là những
người đã động viên, tạo mọi điều kiện cho tôi lao động và học tập trong suốt thời gian
qua.
Nam Định, ngày 28 tháng 09 năm 2014
Học viên
Phạm Thị My
3
Bảng các ký hiệu và chữ viết tắt
STT
Ký hiệu
1
U
User
Người dùng
2
I
Item
Sản phẩm
3
R
Rating
Đánh giá
4
IR
Information Retrieval
Thu thập thông tin
5
IF
Information Filtering
Lọc thông tin
6
RS
Recommender Systems
Hệ thống khuyến nghị
7
CF
Collaborative Filtering
Lọc cộng tác
8
KNN
K-nearest neighbor
K-hàng xóm gần nhất
9
RMSE
Root Mean Square Error
Hàm sai số bình phương trung bình
10
MAE
Mean absolute error
Sai số tuyệt đối trung bình
11
MF
Matrix Factorization
Ma trận thừa số
12
GD
Gradient descent
Giảm độ lệch
13
SGD
Stochastic gradient descent Giảm độ lệch ngẫu nhiên
Diễn giải
Tiếng Việt
4
Danh mục bảng và biểu đồ
Bảng 2.1: Ví dụ 1 về người dùng đánh giá sản phẩm ................................................................ 17
Bảng 2.2: Ví dụ 2 về người dùng đánh giá sản phẩm ................................................................ 20
Bảng 2.3: Ví dụ 3 về người dùng đánh giá sản phẩm ................................................................ 23
Bảng 2.4: Ma trận đánh giá dày đặc ........................................................................................... 32
Bảng 2.5: Ma trận đánh giá thưa thớt ......................................................................................... 32
Bảng 2.6: So sánh giữa GD và SGD .......................................................................................... 43
Bảng 3.1: Định dạng các bộ dữ liệu huấn luyện và kiểm tra của Movielens ............................. 48
Bảng 3.2: Giá trị RMSE và RMSEtb thực nghiệm trên tập dữ liệu Movielens .......................... 50
Danh mục hình ảnh
Hình 1.1: Mô hình hệ thống lọc thông tin .................................................................................... 9
Hình 1.2: Một ví dụ về mô hình khuyến nghị sản phẩm ............................................................ 10
Hình 1.3: Mô hình kỹ thuật lọc dựa theo nội dung .................................................................... 12
Hình 2.1: Mô hình đồ thị tính khoảng cách Manhattan .............................................................. 18
Hình 2.2: Mô hình đồ thị tính khoảng cách Euclidean ............................................................... 19
Hình 2.3: Mô hình đồ thị tính hệ số tương quan Pearson ........................................................... 22
Hình 2.4: Mô hình đồ thị tính hệ số tương tự Cosine ................................................................. 24
Hình 2.5: Phương pháp tiếp cận vùng lân cận ............................................................................ 30
Hình 2.6: Định hướng người dùng đối với phim ảnh ................................................................. 31
Hình 2.7: Phương pháp ma trận thừa số ..................................................................................... 35
Hình 2.8: Mô hình phương pháp Gradient descent .................................................................... 36
Hình 2.9: Đồ thị biểu thị thuật toán SGD thử nghiệm trên tập dữ liệu của Netflix ................... 42
5
MỤC LỤC
Lời cam đoan .............................................................................................................................. 1
Lời cảm ơn .................................................................................................................................. 2
Bảng các ký hiệu và chữ viết tắt ................................................................................................ 3
Danh mục bảng và biểu đồ ........................................................................................................ 4
Danh mục hình ảnh .................................................................................................................... 4
Mở đầu ......................................................................................................................................... 7
CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ HỆ THỐNG KHUYẾN NGHỊ .................. 9
1.1. Khái niệm chung: ............................................................................................................ 9
1.1.1. Lọc thông tin (Information Filtering _IF)............................................................... 9
1.1.2. Hệ thống khuyến nghị (Recommender System) .................................................... 10
1.1.3. Giới thiệu bài toán về hệ thống khuyến nghị: ...................................................... 11
1.2. Các kỹ thuật lọc cho hệ thống khuyến nghị [4] ............................................................ 11
1.2.1. Kỹ thuật lọc dựa theo nội dung: ........................................................................... 12
1.2.2. Kỹ thuật lọc cộng tác (Collaborative Filtering) ................................................... 12
1.2.3, Kỹ thuật Hybrid ..................................................................................................... 13
1.3. Các phương pháp lọc cộng tác ..................................................................................... 13
1.3.1, Lọc cộng tác dựa vào bộ nhớ ................................................................................. 14
1.3.2, Lọc cộng tác dựa vào mô hình (Model-Based Collaborative Filtering) .............. 14
CHƯƠNG 2: KỸ THUẬT LỌC CỘNG TÁC ....................................................................... 16
2.1. Giới thiệu bài toán lọc cộng tác ............................................................................... 16
2.2. Các phương pháp tính độ tương tự giữa các người dùng ..................................... 16
2.2.1.
Khoảng cách Manhattan.................................................................................. 16
2.2.2.
Khoảng cách Euclidean. ................................................................................... 18
2.2.3.
Hệ số tương quan Pearson. .............................................................................. 20
2.2.4.
Hệ số tương tự Cosine. ..................................................................................... 22
2.3. Phương pháp cải tiến K-hàng xóm gần nhất (k-nearest neighbor) ..................... 24
2.3.1
Thuật toán KNN dựa trên người dùng. ............................................................ 25
2.3.2
Thuật toán KNN dựa trên sản phẩm: ............................................................... 27
2.4. Mô hình nhân tố ẩn. ................................................................................................. 29
2.4.1
Phương pháp tiếp cận vùng lân cận (the neighborhood approach) .............. 29
2.4.2
Mô hình nhân tố ẩn (latent factor models) [3] .................................................. 30
2.4.2.1. Cơ sở lý thuyết ................................................................................................. 30
2.4.2.2. Bài toán: ........................................................................................................... 31
2.4.3. Phương pháp ma trận thừa số (Matrix Factorization Methods) [6] ................... 32
2.4.4. Thuật toán gradient descent ngẫu nhiên. ............................................................. 35
2.4.4.1. Thuật toán Gradient descent (GD) ................................................................ 35
2.4.4.2. Thuật toán gradient descent ngẫu nhiên ....................................................... 37
2.4.4.3. Thuật toán SGD dùng cho phân tích ma trận (ma trận thừa số) ............... 41
6
2.4.4.4. So sánh giữa thuật toán GD và SGD ............................................................. 43
2.5. Tiêu chuẩn đánh giá ...................................................................................................... 44
2.5.1. Mean absolute error (MAE) .................................................................................. 44
2.5.2. Root mean square error (RMSE) .......................................................................... 44
CHƯƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ VỚI DỮ LIỆU PHIM ẢNH .................. 46
3.1. Dữ liệu thực nghiệm. ..................................................................................................... 46
3.1.1. Tập dữ liệu thực nghiệm. ....................................................................................... 46
3.1.2. Thông tin chi tiết về định dạng của bộ dữ liệu của Movielens[15] ....................... 47
3.2. Phương pháp thực nghiệm ...................................................................................... 49
3.2.1. Môi trường thực nghiệm ........................................................................................ 49
3.2.2. Phương pháp tiến hành thực nghiệm ................................................................... 49
3.3. So sánh và đánh giá kết quả thực nghiệm ................................................................... 50
3.3.1. Kết quả thực nghiệm .............................................................................................. 50
3.3.2. So sánh và đánh giá ................................................................................................ 52
3.3.2.1. Các phương pháp cơ sở ................................................................................... 52
3.3.2.2. Thuật toán SGD ............................................................................................... 52
KẾT LUẬN ............................................................................................................................... 54
TÀI LIỆU THAM KHẢO ....................................................................................................... 55
7
Mở đầu
Tương tác cá nhân là hoạt động/ sự việc diễn ra trên toàn thế giới, thậm chí có từ
hàng trăm năm trước cho đến ngày nay. Những năm 1990, tương tác cá nhân ít nhiều
cũng đã có mặt. Theo thường lệ, khi đi vào một cửa hàng sách quen thuộc, chủ hàng sẽ
chào đón như: “Có báo mới ngày hôm nay đấy!”, chủ hàng biết rằng khách hàng của
mình muốn điều gì khi đến đây. Hoặc chủ hàng có thể giới thiệu cho một vài quyển
sách mà khách hàng của mình có thể quan tâm dựa trên những sở thích của khách. Hoặc
khi đi vào quán nước quen, người phục vụ sẽ hỏi: “Như thường lệ chứ?”
Khoảng 30 năm về trước, khi bạn muốn mua chiếc tivi ở cửa hàng điện máy thì
có vài sự lựa chọn phổ biến cho bạn: Panasonic và Samsung hay LG. Những năm sau
đó, bạn có nhiều sự lựa chọn phong phú hơn, bạn chọn hãng Samsung thì trong đó còn
nhiều lựa chọn như: LED hay LCD, bao nhiêu inch?…
Hàng ngày có hàng trăm bài hát được thu âm, hàng trăm đầu sách được xuất bản
trên thế giới, trong khi đó các cửa hàng chỉ có giới hạn các đầu sách hoặc các bài hát,
các bộ phim… Từ đó, các dịch vụ trực tuyến được ra đời và đáp ứng nhu cầu ngày càng
cao của người dùng.
Cho đến ngày nay, sự tương tác cá nhân vẫn luôn tồn tại, thậm chí bạn có hàng
triệu sự lựa chọn. Mỗi giây các phương tiện truyền thông được thêm vào mạng. Mỗi
phút 100 tập tin mới có sẵn trên usenet. 24/24 giờ video được tải lên YouTube. Mỗi giờ
180 cuốn sách mới được xuất bản. Mỗi ngày càng có thêm nhiều lựa chọn các sản phẩm
để mua trong thế giới thực.
Bạn muốn mua một số bài nhạc? iTunes có khoảng 11 triệu bài hát để lựa chọn
và họ đã bán được 16 tỷ bài hát vào tháng 10 năm 2011. Nếu bạn muốn nhiều hơn sự
lựa chọn thì có thể đi đến Spotify với 15 triệu bài hát. Bạn muốn mua một cuốn sách,
Amazon cung cấp hơn 2 triệu cuốn sách để bạn lựa chọn.
Trong cuộc sống của chúng ta ngày nay, với sự phát triển không ngừng của công
nghệ thông tin, nguồn thông tin quá phong phú làm cho bạn không có đủ thời gian để
xem xét lựa chọn tất cả các cuốn sách, phim, tạp chí hay bài hát… bạn không biết mình
nên xem phim gì, đọc cuốn sách nào phù hợp với sở thích, nhu cầu của bản thân.
Vấn đề cấp thiết đặt ra là cần một hệ thống hỗ trợ người dùng chọn lựa những
sản phẩm phù hợp với nhu cầu của người dùng, từ đó hệ thống khuyến nghị được
8
nghiên cứu và phát triển không ngừng nhằm đạt hiệu quả nhất trong việc tương tác với
người dùng. Hệ thống khuyến nghị (Recommender Systems - RS) là giải pháp hiệu quả
nhất giải quyết vấn đề trên.
Chính vì vậy trong luận văn này, chúng tôi xin được trình bày về hệ thống
khuyến nghị. Trong phạm vi luận văn, chúng tôi tập trung nghiên cứu về kỹ thuật lọc
cộng tác và phân tích các phương pháp cơ bản để tìm một người hoặc một nhóm người
gần nhất với người dùng hiện tại cần khuyến nghị. Để giảm thiểu sai số trong dự đoán
chúng tôi trình bày nghiên cứu của mình về phương pháp ma trận thừa số cụ thể hơn là
thuật toán gradient descent ngẫu nhiên. Nội dung chính của luận văn này được chia làm
3 chương:
Chương 1: Giới thiệu tổng quan về hệ thống khuyến nghị
Chương 2: Kỹ thuật lọc cộng tác
Chương 3: Thực nghiệm và đánh giá với dữ liệu phim ảnh
Trong chương 1, chúng tôi đi tìm hiểu chung về hệ thống khuyến nghị, các kỹ
thuật lọc thông tin trong hệ thống khuyến nghị: lọc dựa vào nội dung, lọc cộng tác và kỹ
thuật kết hợp Hybrid, các phương pháp lọc cộng tác như: Lọc dựa vào bộ nhớ và lọc
dựa vào mô hình. Trong chương 2, chúng tôi trình bày chi tiết hơn về kỹ thuật lọc cộng
tác, các phương pháp tính độ tương tự giữa các người dùng, phương pháp ma trận thừa
số, thuật toán gradient descent ngẫu nhiên và các tiêu chuẩn đánh giá dự đoán. Chương
3, chúng tôi tiến hành thực nghiệm trên bộ dữ liệu của Movielens với 100.000 đánh giá,
sau đó dựa vào kết quả thực nghiệm để đánh giá, phân tích và so sánh tính hiệu quả của
từng phương pháp và thuật toán đã nêu trong chương 2.
9
CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ
HỆ THỐNG KHUYẾN NGHỊ
1.1. Khái niệm chung:
1.1.1. Lọc thông tin (Information Filtering _IF)
Hình 1.1: Mô hình hệ thống lọc thông tin
Giảm quá tải thông tin là mục tiêu chính của lọc thông tin (Information Filtering
_IF) và nó đã được công nhận là một trong những ưu tiên trong việc phát triển hệ thống
thông tin dựa trên web hiện nay. Cung cấp các tài liệu có liên quan dựa trên sở thích
khách hàng. Công nghệ khuyến nghị được trình bày như là một mô hình mới của sự tìm
kiếm nơi mà các mặt hàng có liên quan tìm ra người sử dụng thay vì người sử dụng tìm
kiếm chúng. Xu hướng mới trong công nghệ thông tin như mạng xã hội và thiết bị di
10
động đang thực hiện nghiên cứu cá nhân được ưu tiên hàng đầu. Nghiên cứu khách
hàng và tiếp thị có một truyền thống lâu đời. Với những tiến bộ trong công nghệ thông
tin, nó đã phát triển và ngày càng tinh vi mang lại hiệu quả cho các hệ thống trực
tuyến. Lọc cộng tác, hệ thống khuyến nghị, hệ thống trợ giúp cá nhân, lọc xã hội, hệ
thống khai thác dữ liệu xã hội, và các hệ thống thích nghi người dùng có thể được gọi
chung là hệ thống lọc thông tin (IF ). Ngày nay, hệ thống lọc thông tin ở khắp mọi nơi,
trong mọi ngành công nghiệp và dịch vụ, từ tiếp thị cho sức khỏe, du lịch, giáo dục, giải
trí,...
Vậy, hệ thống lọc thông tin là một hệ thống loại bỏ thông tin dư thừa hoặc không
mong muốn từ một luồng thông tin sử dụng tự động trên máy vi tính
Mục tiêu chính của nó là quản lý của tình trạng quá tải thông tin và tăng tỷ lệ ngữ
nghĩa của tín hiệu trên nhiễu. Để thực hiện các hồ sơ này được so sánh với một số đặc
tính tham khảo.
1.1.2. Hệ thống khuyến nghị (Recommender System)
Hệ thống khuyến nghị (Recommender System)[7] là một loại hình cụ thể của kỹ
thuật lọc thông tin (như phim ảnh, âm nhạc, trang web, tin tức) mà người dùng quan
tâm. Nó rất quan trọng cho sự thành công của thương mại điện tử và ngành công nghiệp
CNTT hiện nay, và dần dần trở nên phổ cập trong các ứng dụng khác nhau (ví dụ như
dự án Netflix, Google tin tức, Amazon). Là một hệ thống khuyến nghị chuyên nghiệp
xây dựng dựa trên hồ sơ quá khứ của người dùng, hệ thống so sánh hồ sơ của người
dùng với một số đặc điểm tài liệu tham khảo, và tìm cách để dự đoán “đánh giá” mà
người dùng sẽ cung cấp cho một mục mà người dùng đó vẫn chưa đánh giá . Trong hầu
hết các trường hợp, hệ thống khuyến nghị tương ứng với một vấn đề khai thác dữ liệu
quy mô lớn. Là hệ thống có khả năng tự động phân tích, phân loại, lựa chọn và cung cấp
cho người dùng những thông tin, hàng hóa hay dịch vụ mà họ quan tâm.
Hình 1.2: Một ví dụ về mô hình khuyến nghị sản phẩm
11
1.1.3. Giới thiệu bài toán về hệ thống khuyến nghị:
Cho U là tập tất cả người dùng; P là tập tất cả các sản phẩm(sách, bài hát,
phim…) có thể tư vấn. Tập P có thể rất lớn, từ hàng trăm ngàn đến hàng triệu sản phẩm.
Tập U trong một số trường hợp cũng có thể lên tới hàng triệu người dùng. Hàm r(u,p) là
những đánh giá mức độ phù hợp (xếp hạng) của sản phẩm p với người dùng u, r: UxP
R. Với mỗi người dùng u ∈ U cần tìm sản phẩm p’ ∈ P sao cho hàm r(u,p’) đạt giá trị
lớn nhất: ∀u ∈U,p’=arg maxp∈ P r(u,p)
Trong hệ thống khuyến nghị, những đánh giá được thể hiện bằng các hình thức
thông thường như: thích và không thích (hình bàn tay với ngón trỏ: youtube.com), số
sao (thường từ 1- 5 sao)…
1.2. Các kỹ thuật lọc cho hệ thống khuyến nghị [4]
Trong việc lựa chọn sản phẩm hoặc dịch vụ (gọi chung là Item), người dùng thường gặp
phải những khó khăn là:
Lượng Item: Mỗi ngày, có hàng triệu thông tin được đăng tải lên internet mỗi
ngày, người dùng không biết mình nên và không nên sử dụng Item nào?
Thông tin về Item: do lượng Item là vô cùng lớn, nên User không thể tìm hiểu
được tất cả các Item về nội dung, chức năng cũng như Item có phù hợp với nhu
cầu của user không?...
Gợi ý đặt ra để giải quyết các vấn đề khó khăn trên là:
Khai thác những khía cạnh cạnh liên quan đến nội dung thông tin sản phẩm hoặc
người dùng đã từng sử dụng hay truy nhập trong quá khứ để khuyến nghị. Đây là
kỹ thuật lọc dựa theo nội dung (Content-Based Filtering)
Lựa chọn dựa trên ý kiến hay lời khuyên của những người dùng khác về các
Item. Hệ thống khuyến nghị áp dụng các thuật toán tận dụng các gợi ý được cung
cấp bởi một cộng đồng người dùng tương tự sau đó cung cấp cho người dùng
đang hoạt động (người đang tìm kiếm các đề xuất). Phương pháp này được gọi là
lọc cộng tác (Collaborative Filtering _CF)
So với lọc theo nội dung, lọc cộng tác có một số ưu điểm như đơn giản trong cài đặt và
có thể lọc được mọi loại thông tin hay hàng hoá mà không cần phải biểu diễn dưới dạng
văn bản.
12
1.2.1. Kỹ thuật lọc dựa theo nội dung:
Với kỹ thuật khuyến nghị dựa trên nội dung[10], mức độ phù hợp r(u,p) của sản phẩm
phẩm p với người dùng u được đánh giá dựa trên mức độ phù hợp r(u,pj), trong đó pj
P và tương tự như p. Ví dụ, để gợi ý một bộ phim cho người dùng u, hệ thống tư vấn sẽ
tìm các đặc điểm của những bộ phim từng được u đánh giá cao (như diễn viên, đạo
diễn…); sau đó chỉ những bộ phim tương đồng với sở thích của c mới được giới thiệu.
Hướng tiếp cận dựa trên nội dung bắt nguồn từ những nghiên cứu về thu thập thông
tin (IR - information retrieval) và lọc thông tin (IF - information filtering). Do đó, rất
nhiều hệ thống dựa trên nội dung hiện nay tập trung vào tư vấn các đối tượng chứa dữ
liệu text như văn bản, tin tức, website… Những tiến bộ so với hướng tiếp cận cũ của IR
là do việc sử dụng hồ sơ về người dùng (chứa thông tin về sở thích, nhu cầu…). Hồ sơ
này được xây dựng dựa trên những thông tin được người dùng cung cấp trực tiếp (khi
trả lời khảo sát) hoặc gián tiếp (do khai phá thông tin từ các giao dịch của người dùng).
Hình 1.3: Mô hình kỹ thuật lọc dựa theo nội dung
1.2.2. Kỹ thuật lọc cộng tác (Collaborative Filtering)
Kỹ thuật lọc cộng tác (Collaborative Filtering) dựa trên nguyên tắc hoạt động là
các khuyến nghị dựa trên ảnh hưởng của nhiều người khác nhau, các cộng tác của nhiều
người này sẽ trở thành khuyến nghị. Khác so với kỹ thuật lọc cộng tác dựa trên nội
dụng, hệ thống cộng tác dự đoán mức độ phù hợp r(u,p) của một sản phẩm p với người
dùng u dựa trên mức độ phù hợp r(ui, p) giữa người dùng ui và p, trong đó ui là người có
cùng sở thích với u. Ví dụ, để gợi ý một bộ phim cho người dùng u, đầu tiên hệ thống
13
cộng tác tìm những người dùng khác có cùng sở thích phim ảnh với u. Sau đó, những bộ
phim được họ đánh giá cao sẽ được dùng để tư vấn cho u. Chi tiết cụ thể về kỹ thuật này
sẽ được tôi trình bày trong chương 2.
1.2.3, Kỹ thuật Hybrid
Kỹ thuật Hybrid[9] là phương pháp kết hợp của cả hai kỹ thuật trên. Một số ứng
dụng kết hợp cả hai kỹ thuật lọc cho hệ thống khuyến nghị dựa theo nội dung và lọc
cộng tác. Mỗi kỹ thuật đều có những ưu điểm và nhược điểm riêng, do đó khi kết hợp
có thể khắc phục những hạn chế của từng kỹ thuật. Nó cải thiện hiệu suất dự đoán, quan
trọng hơn, từ đó vượt qua những vấn đề lọc thông tin như thưa thớt và mất thông
tin. Tuy nhiên, sự kết hợp của hai kỹ thuật để thực hiện sẽ gia tăng phức tạp và giá
thành cao. Thông thường hầu hết các hệ thống khuyến nghị thương mại là Hybrid, ví
dụ: hệ thống khuyến nghị tin tức của Google
Thông thường có 4 cách để kết hợp như sau:
Cài đặt hai phương pháp riêng rẽ rồi kết hợp dự đoán của chúng với nhau: Có hai
kịch bản cho trường hợp này là:
+ Cách 1: Kết hợp kết quả của cả hai phương pháp thành một kết quả chung
duy nhất.
+ Cách 2: Tại mỗi thời điểm chọn một phương pháp cho kết quả tốt hơn (ví dụ:
Hệ thống Dailylearner)
Tích hợp các đặc trưng của phương pháp dựa trên nội dung vào hệ thống cộng
tác.
Tích hợp các đặc trưng của phương pháp cộng tác vào hệ thống dựa trên nội
dung.
Xây dựng mô hình hợp nhất, bao gồm các đặc trưng của cả hai phương pháp.
1.3. Các phương pháp lọc cộng tác
Với số lượng quá lớn các sản phẩm có trên internet thì thông thường một người
dùng chỉ đánh giá hữu hạn m sản phẩm (với m sản phẩm được đánh giá nhỏ hơn rất
nhiều so với tập M sản phẩm). Khó khăn đặt ra là dự đoán đánh giá một người dùng cho
tập M sản phẩm là điều rất khó khăn, hơn nữa tập M sản phẩm luôn luôn thay đổi và
theo thời gian thì ngày càng tăng lên. Ngoài ra để dự đoán đánh giá của N người dùng
với M sản phẩm sẽ gây ra tốc độ xử lý chậm => mất nhiều thời gian, lãng phí tài
14
nguyên… Một trong những giải pháp đặt ra để giải quyết vấn đề trên là: kỹ thuật lọc
cộng tác (Collaborative Filtering)
Lọc cộng tác cho hệ thống khuyến nghị được tiếp cận theo hai phương pháp
chính: Lọc cộng tác dựa vào bộ nhớ (Memory-Based Collaborative Filtering) và lọc
cộng tác dựa vào mô hình (Model-Based Collaborative Filtering) . Điểm khác biệt quan
trọng trong hai phương pháp tiếp cận là: Lọc dựa vào bộ nhớ tiến hành xây dựng đồng
thời mô hình huấn luyện và mô hình dự đoán. Ngược lại, lọc dựa vào mô hình xây dựng
mô hình huấn luyện và mô hình dự đoán độc lập nhau. So với lọc cộng tác dựa vào mô
hình, lọc cộng tác dựa vào bộ nhớ được áp dụng rộng rãi hơn do tính hiệu quả, đơn giản
và có độ chính xác khá cao.
1.3.1, Lọc cộng tác dựa vào bộ nhớ
Phương pháp lọc cộng tác dựa vào bộ nhớ [11] thường sử dụng toàn bộ dữ liệu đã
có của người dùng để dự đoán đánh giá của người đó về một sản phẩm mới. Là phương
pháp có khả năng đưa trực tiếp dữ liệu mới vào bảng dữ liệu nên nó đạt khá nhiều thành
công khi được áp dụng vào các ứng dụng thực tế. Đặc biệt, kỹ thuật này phát huy tính
hiệu quả cao trong các hệ thống trực tuyến (là nơi luôn có dữ liệu mới được cập nhật)
thường đưa ra các dự đoán chính xác hơn.
Lọc cộng tác dựa vào bộ nhớ (Memory-Based Collaborative Filtering) được thực
hiện theo hai phương pháp chính: Lọc dựa vào người dùng (User-Based Collaborative
Filtering) và lọc dựa vào sản phẩm (Item-Based Collaborative Filtering) . Hiệu quả của
các phương pháp lọc dựa vào bộ nhớ phụ thuộc vào độ đo tương tự giữa các cặp người
dùng hoặc sản phẩm. Phương pháp lọc cộng tác dựa vào bộ nhớ, tôi sẽ trình bày cụ thể
hơn trong chương 2.
1.3.2, Lọc cộng tác dựa vào mô hình (Model-Based Collaborative Filtering)
Phương pháp tiếp cận dựa trên mô hình [17] không sử dụng tất cả dữ liệu đã có để
đưa ra dự đoán, thay vào đó chúng nắm bắt thông tin trong từng bước giống như một sự
thỏa thuận về mô hình các sở thích người dùng. Các mô hình được phát triển bằng cách
sử dụng phương thức khai thác dữ liệu, thuật toán học máy để tìm mô hình dựa trên dữ
liệu huấn luyện. Chúng được sử dụng để đưa ra dự đoán cho dữ liệu thực tế. Có rất
nhiều thuật toán CF dựa trên mô hình như: mạng Bayes , mô hình phân nhóm , mô hình
ngữ nghĩa tiềm ẩn.
15
Ưu điểm của mô hình này là xử lý dữ liệu thưa thớt tốt hơn so với lọc dựa trên bộ
nhớ. Điều này giúp với khả năng mở rộng với các tập dữ liệu lớn, nó cải thiện hiệu suất
dự đoán. Những nhược điểm của phương pháp này là giá thành cao trong việc xây dựng
mô hình, cần phải có một sự cân bằng giữa hiệu suất và khả năng mở rộng dự đoán, có
thể bị mất thông tin hữu ích do mô hình giảm và một số mô hình có khó khăn trong việc
giải nghĩa các dự đoán.
16
CHƯƠNG 2: KỸ THUẬT LỌC CỘNG TÁC
Phương pháp khuyến nghị tôi đang xem xét trong chương này được gọi là lọc
cộng tác. Nó được gọi là cộng tác bởi vì nó đưa ra các khuyến nghị dựa trên những
người dùng khác trong thực tế, mọi người cộng tác để đưa ra khuyến nghị. Nguyên lý
hoạt động của hệ thống khuyến nghị là: giả sử để giới thiệu một cuốn sách cho bạn. Tôi
tìm kiếm những người sử dụng khác của trang web để tìm một trong số đó là người
tương tự như bạn dựa trên những cuốn sách mà bạn và người sử dụng đó thích.
2.1.
Giới thiệu bài toán lọc cộng tác
Cho một tập hữu hạn gồm có N người dùng U = { u1,u2,…,uN }, một tập
gồm M sản phẩm P = { p1,p2,…,pM }. Mỗi sản phẩm pj ∈ P có thể là phim, ảnh, tạp
chí, tài liệu, sách, báo,hàng hóa, dịch vụ hoặc bất kỳ dạng thông tin nào mà người dùng
cần đến. Một ma trận R = ( rij ) với i = 1,…N ; j = 1,…,M thể hiện mối quan hệ giữa tập
người dùng U và tập sản phẩm P. Trong đó rij là đánh giá của người dùng ui cho sản
phẩm pj.
Các giá trị rij nhận giá trị theo các hình thức: thu thập trực tiếp ý kiến đánh giá
của người dùng ui về sản phầm pj hoặc thu thập gián tiếp thông qua cơ chế phản hồi của
người dùng.
Gọi ux là người dùng hiện thời cần được khuyến nghị sản phẩm py, với rxy=Ø
(nghĩa là người dùng ux chưa đánh giá hoặc chưa từng biết đến sản phẩm py). Bài toán
lọc cộng tác có nhiệm vụ dự đoán đánh giá rxy của người dùng ux với sản phẩm py. Từ
đó, giới thiệu cho người dùng ux những sản phẩm phù hợp nhất dựa trên giá trị rxy,
những sản phẩm được khuyến nghị cho người dùng ux là những sản phẩm có đánh giá
cao.
2.2.
Các phương pháp tính độ tương tự giữa các người dùng
Cho ui là người dùng hiện thời, ua là người dùng cần tính độ tương tự với người
dùng ui, rip là đánh giá của người dùng ui cho sản phẩm p và rap là đánh giá của người
dùng ua cho sản phẩm p. Với tập m sản phẩm là những sản phẩm mà người dùng ui và
người dùng ua cùng đánh giá.
2.2.1. Khoảng cách Manhattan
17
Một trong những cách đơn giản nhất để đo khoảng cách giữa hai điểm dữ liệu là
khoảng cách Manhattan[1].
Tính độ tương tự giữa người dùng ua và ui sử dụng phương pháp khoảng cách
Manhattan được tính bằng công thức sau:
m
d Manhattan ua , ui rip rap
p 1
Trong không gian 2 chiều, mỗi người dùng được đại diện bởi một điểm (x,y), tôi
sẽ bổ sung thêm subscript cho x và y để tham khảo những người dùng khác nhau. Vì
vậy, ta có (x1,y1) và (x2,y2) lần lượt là các điểm dữ liệu thể hiện đánh giá của ua và ui
cho 2 sản phẩm khác nhau x và y. Khi đó khoảng cách Manhattan được tính bằng công
thức sau:
| x1 - x2| + | y1 - y2 |
Cho bảng ví dụ 1 sau:
The Hobbit
Harry Potter
John
2
2
Peter
4
4
Bảng 2.1: Ví dụ 1 về người dùng đánh giá sản phẩm
Khi đó, khoảng cách Manhattan được định nghĩa lại và biểu diễn trong không gian 2
chiều như sau:
18
Hình 2.1: Mô hình đồ thị tính khoảng cách Manhattan
dManhattan(Peter, John)=|2-4|+|2-4|=2+2=4
Giá trị khoảng cách giữa Peter và John khi áp dụng phương pháp tính khoảng
cách Manhattan là: dManhattan=4. Áp dụng tương tự phương pháp này để tính khoảng cách
với người dùng khác, sau đó sẽ chọn người dùng có giá trị khoảng cách nhỏ nhất với
người dùng hiện tại.
2.2.2. Khoảng cách Euclidean.
Ưu điểm rất rõ ràng khi sử dụng công thức tính khoảng cách Manhattan là tính
toán đơn giản và rất nhanh. Tuy nhiên, khoảng cách Euclidean[1] thay vì đi xung quanh
các khối thì bạn chỉ cần vẽ một đường thẳng giữa hai điểm dữ liệu và đo khoảng cách
giữa hai điểm bằng cách sử dụng định lý Pythagorean.
Công thức tính khoảng cách Euclidean tổng quát:
m
d Euclidean ua , ui
r
p 1
ip rap
2
- Xem thêm -