BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH

Vy Vân

NÂNG CAO HIỆU NĂNG HỆ TƯ VẤN
DỰA TRÊN THỪA SỐ HÓA MA TRẬN

LUẬN VĂN THẠC SĨ MÁY TÍNH

Thành phố Hồ Chí Minh – 2018


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH

Vy Vân

NÂNG CAO HIỆU NĂNG HỆ TƯ VẤN
DỰA TRÊN THỪA SỐ HÓA MA TRẬN

Chuyên ngành : Khoa Học Máy Tính
Mã số

: 8480101

LUẬN VĂN THẠC SĨ MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. HỒ BẢO QUỐC

Thành phố Hồ Chí Minh - 2018


MỤC LỤC
Lời cam đoan
Lời cám ơn
Danh mục thuật ngữ viết tắt
Danh mục các bảng
Danh mục hình vẽ
Chương 1. GIỚI THIỆU ................................................................................. 1
1.1. Giới thiệu................................................................................................. 1
1.2. Mục tiêu của luận văn ............................................................................. 4
1.3. Nội dung thực hiện .................................................................................. 5
1.4. Giới hạn luận văn .................................................................................... 6
1.5. Tóm tắt những đóng góp của luận văn.................................................... 6
1.5.1. Đóng góp về mặt khoa học ............................................................... 6
1.5.2. Đóng góp về mặt thực tiễn ................................................................ 7
1.6. Tổ chức luận văn ..................................................................................... 7
Chương 2. CÁC HỆ THỐNG TƯ VẤN ........................................................ 9
2.1. Tổng quan về hệ thống tư vấn ................................................................. 9
2.2. Các hệ thống tư vấn lọc cộng tác .......................................................... 15
2.2.1. Phương pháp lân cận gần nhất ........................................................ 16
2.2.2. Các mơ hình thống kê ngẫu nhiên (Statistical Random
Effects Models) .............................................................................. 17
2.2.3. Phương pháp thừa số hóa ma trận................................................... 19
2.2.4. Bài tốn thừa số hóa ma trận khơng âm ......................................... 26
Chương 3. TƯ VẤN THÔNG TIN DỰA TRÊN THỪA SỐ HĨA
MA TRẬN KHƠNG ÂM ........................................................... 28
3.1. Cách tiếp cận ......................................................................................... 28
3.2. Các thuật toán đề xuất cho hệ thống ..................................................... 31

3.2.1. Khởi tạo giá trị ban đầu cho hai ma trận thành phần ...................... 31
3.2.2. Hàm chi phí cho bài tốn thừa số hóa ma trận khơng âm .............. 33
3.2.3. Thuật toán đề xuất nâng cao hiệu năng cho bài tốn thừa số hóa
ma trận khơng âm........................................................................... 40


Chương 4. KẾT QUẢ THỰC NGHIỆM..................................................... 43
4.1. Qui trình thực nghiệm ........................................................................... 43
4.1.1. Tập dữ liệu Dataset ......................................................................... 44
4.1.2. Các thước đo đánh giá .................................................................... 44
4.2. Kết quả thực nghiệm ............................................................................. 45
4.2.1. Độ chính xác ................................................................................... 46
4.2.2. Độ hội tụ ......................................................................................... 47
4.2.3. Thời gian thực thi ............................................................................ 48
Chương 5. TỔNG KẾT ................................................................................. 50
5.1. Kết quả đạt được ................................................................................... 50
5.1.1. Về mặt lý thuyết .............................................................................. 50
5.1.2. Về mặt thực nghiệm ........................................................................ 51
5.2. Ưu và nhược điểm của phương pháp đề xuất ....................................... 52
5.3. Hướng mở rộng trong tương lai ............................................................ 52
TÀI LIỆU THAM KHẢO ............................................................................ 54


LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này của tự bản thân tơi tìm hiểu, nghiên cứu
dưới sự hướng dẫn của PGS.TS. Hồ Bảo Quốc. Các số liệu sử dụng phân tích
có nguồn gốc rõ ràng. Các kết quả nghiên cứu trong luận văn hoàn toàn trung
thực, khách quan và chưa từng được cơng bố trong bất kì nghiên cứu nào khác.
Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.

Học viên thực hiện
Vy Vân


LỜI CÁM ƠN

Đầu tiên, tơi xin bày tỏ lịng biết ơn chân thành và sâu sắc nhất đến
PGS.TS. Hồ Bảo Quốc – giảng viên hướng dẫn luận văn. Trong quá trình làm
luận văn, Thầy đã ln hỗ trợ, động viên, hết lịng hướng dẫn tơi hồn thành
luận văn này.
Tơi xin gửi lời cảm ơn chân thành đến Quý Thầy Cô − Trường Đại học Sư
Phạm TP. HCM đã truyền đạt những kiến thức q báu cho tơi trong q trình
học tập. Đồng thời, tôi xin gửi lời cảm ơn chân thành đến các bạn đồng nghiệp
Trường THPT chuyên Lương Thế Vinh – Đồng Nai đã hỗ trợ và tạo điều kiện
cho tôi trong thời gian qua.
Cuối cùng, tôi xin bày tỏ lịng biết ơn sâu sắc đối với gia đình, những
người sát cánh cùng tơi trong suốt q trình học tập cũng như thực hiện luận
văn.
TP. HCM, tháng 09 năm 2018
Học viên thực hiện
Vy Vân


DANH MỤC THUẬT NGỮ VIẾT TẮT
Thuật ngữ tiếng Anh

Viết tắt

Collaborative Filtering


CF

Content-based

CB

Frobenius - Kullback Leibler - Itakura Saito

FKI

Latent Semantic Indexing

LSI

Matrix Factorization

MF

Mean Absolute Error

MAE

Mean Measure of Divergence

MMD

Method of Moments

MM


Non-negative Matrix Factorization

NMF

Pearson Correlation Coefficient

PCC

Pearson-Jaccard
Principal Component Analysis
Recommender System
Root Mean Square Error

PJ
PCA
RS
RMSE

Singular Value Decomposition

SVD

Stochastic Gradient Descent

SGD


DANH MỤC CÁC BẢNG

Bảng 2.1. Minh họa một ma trận đánh giá thưa R cho bài toán tư vấn .......... 28

Bảng 4.1. So sánh chỉ số MAE và RMSE của thuật toán đề xuất với
một số thuật toán khác.................................................................... 46
Bảng 4.2. Bảng so sánh thời gian thực thi của một số thuật toán
khác nhau........................................................................................ 49


DANH MỤC HÌNH VẼ

Hình 2.1. Một số hướng nghiên cứu tiếp cận của hệ thống tư vấn ................ 10
Hình 2.2. Ma trận đánh giá được phân tích thành 2 ma trận low-rank
U và I .............................................................................................. 21
Hình 3.1. Kiến trúc NMF cho phương pháp đề xuất ...................................... 30
Hình 3.2. Đồ thị hàm phân kì beta biểu diễn các giá trị  = 2, 1, 0
tương ứng ....................................................................................... 35
Hình 4.1. Minh họa độ hội tụ của phương pháp đề xuất và một số
phương pháp khác .......................................................................... 48


1

Chương 1. GIỚI THIỆU
1.1. Giới thiệu
Đầu tiên, ý tưởng đơn giản về hệ thống tư vấn xuất hiện vào đầu những
năm 1990 nhằm khai thác ý kiến của hàng triệu người dùng (users) trực tuyến
với mong muốn giúp users dễ dàng tìm kiếm những nội dung hữu ích và thú vị
hơn [1]. Trải qua thực tế, ý tưởng đơn giản ban đầu này đã chứng minh tính
hiệu quả.
Hệ thống tư vấn thu thập thơng tin về sở thích của users cho tập hợp các
items (ví dụ: phim, bài hát, sách, truyện cười, tiện ích, ứng dụng, trang web,
điểm đến du lịch và tài liệu học trực tuyến). Thơng tin có thể được thể hiện một

cách rõ ràng (thường bằng cách thu thập các xếp hạng đánh giá của users) hoặc
ngầm định (thường là theo dõi hành vi của users, chẳng hạn như bài hát được
nghe, tải xuống ứng dụng, truy cập trang web và đọc sách).
Hệ thống tư vấn có thể sử dụng các thông tin trong hồ sơ người dùng (như
tuổi tác, quốc tịch, giới tính), thơng tin xã hội (như người theo dõi, theo dõi và
bài đăng) thường được sử dụng trong hệ thống website, mạng xã hội. Một xu
hướng khác cũng đang được quan tâm, đó là sử dụng thơng tin từ Internet (ví
dụ: vị trí GPS, RFID, tín hiệu sức khỏe theo thời gian thực).
Hiện nay, hệ thống tư vấn trên Internet đã trở nên khá phổ biến, điều này
đã tạo điều kiện cho việc áp dụng hệ thống tư vấn trong các lĩnh vực đa dạng
khác nhau. Các nghiên cứu thường tập trung vào tư vấn giới thiệu phim, tư vấn
âm nhạc, chương trình truyền hình, sách, tài liệu, e-learning, thương mại điện
tử và tìm kiếm thông tin [2].
Thông qua các nguồn thông tin khác nhau từ users, hệ thống tư vấn sử
dụng các thông tin đó để cung cấp các dự đốn và đưa ra đề xuất về hàng hóa


2

hay dịch vụ (items) tư vấn trở lại cho users. Mục tiêu của hệ thống tư vấn chính
là đảm bảo độ chính xác (tư vấn đúng những gì users cần hoặc mong muốn),
mới lạ (tư vấn những thứ users chưa từng có kinh nghiệm nhưng gây được sự
thích thú đối với users), phân tán (tư vấn phong phú nhiều lĩnh vực) và ổn định
trong các tư vấn. Các phương pháp lọc cộng tác đóng một vai trị quan trọng
trong tư vấn, mặc dù phương pháp này thường được sử dụng cùng với các kỹ
thuật khác như các kỹ thuật dựa trên nội dung, dựa trên tri thức hoặc xã hội.
Các loại lọc thông tin được sử dụng nhiều nhất vào thời kì đầu của hệ
thống tư vấn là cộng tác, dựa trên nội dung và hồ sơ người dùng [3]. Ngồi ra,
hệ thống tư vấn khơng chỉ dựa trên lọc cộng tác mà còn dựa trên cơ sở tri thức
về users và items như Burke và cộng sự năm 1996 đã xây dựng hệ thống

FindMe, hệ thống này đã chứng minh tính khả thi và tính hiệu quả của các hệ
thống tư vấn và tạo ra sự khích lệ đáng kể cho nghiên cứu và thực hiện ở lĩnh
vực thương mại.
Sự phát triển của hệ thống tư vấn đã cho thấy tầm quan trọng của kỹ thuật
lai của hệ thống tư vấn, kết hợp các kỹ thuật khác nhau để có được những ưu
điểm của mỗi kỹ thuật. Thậm chí người ta còn mở các cuộc khảo sát tập trung
vào hệ thống tư vấn lai hóa. Bên cạnh đó thương mại hóa diễn ra với tốc độ
nhanh chóng đi cùng các hệ thống tư vấn nổi lên trong một môi trường kinh
doanh Internet mở rộng. Để thành công, các công ty tư vấn phải áp dụng lý
thuyết hệ thống tư vấn sang thực tiễn để chứng minh được những dự đốn chính
xác, có thể cung cấp các tư vấn có giá trị - thường dưới hình thức chọn một vài
items cụ thể để đề xuất tư vấn cho các giao dịch mua thêm (ví dụ như khi khách
hàng mua máy laptop, hệ thống sẽ tư vấn thêm các sản phẩm khác như chuột,
bàn phím rời, USB,...).
Trong thực tế, các hệ thống tư vấn phải làm việc ở quy mô lớn hơn quy
mơ nghiên cứu trong phịng thí nghiệm, tức là phải xử lý hàng triệu users và


3

items với hàng trăm hoặc hàng ngàn giao dịch mỗi giây. Thách thức mới cho
hệ thống tư vấn ngoài việc đảm bảo tính chính xác (tư vấn đúng items khách
hàng có nhu cầu hoặc u thích) thì cịn đảm bảo không làm chậm tốc độ truy
cập các trang web. Thực ra có thể nói khơng q là hệ thống tư vấn phát triển
không được nhắm vào nghiên cứu mà là nhắm vào vấn đề tiếp thị items.
Nghiên cứu về hệ tư vấn ở giai đoạn phát triển đã giải quyết nhiều thách
thức về vấn đề nêu trên. Thuật toán mới được phát triển để giảm thời gian tính
tốn trực tuyến, bao gồm các thuật toán tương quan dựa trên items và những
phương pháp tiếp cận nhằm giảm kích thước dữ liệu đều được sử dụng cho tới
hiện nay. Một loạt các nghiên cứu khám phá các vấn đề liên quan đến các xếp

hạng đánh giá của users dưới dạng ngầm định, vấn đề thiếu thông tin ở những
users mới và items mới (cold-start) cũng như các vấn đề liên quan đến trải
nghiệm users, chẳng hạn như độ tin cậy và tính minh bạch.
Các hệ thống tư vấn mới ra đời được áp dụng rộng rãi trong thương mại
điện tử. Đồng thời, với việc nghiên cứu về các hệ thống tư vấn bùng nổ là việc
tiếp cận tới các lĩnh vực khác như thu thập thông tin, khai phá dữ liệu (data
mining). Nghiên cứu kinh doanh tiếp thị sản phẩm đã xuất hiện các phân tích
và cách tiếp cận mới cho các hệ thống tư vấn. Nghiên cứu thuật toán mới được
thúc đẩy bởi sự xuất hiện các tập dữ liệu lớn, sẵn có trong thương mại điện tử
từ thực tiễn.
Đa số các hệ thống tư vấn hiện nay được xây dựng theo ba cách tiếp cận
chính: dựa trên nội dung (Content Based), dựa trên lọc cộng tác (Collaborative
Filtering) và dựa trên việc lai ghép các phương pháp với nhau (Hybrid
Approach). Chi tiết từng cách tiếp cận sẽ được trình bày tiếp ở chương 2 của
luận văn.


4

Phương pháp thừa số hóa ma trận (một nhánh nghiên cứu trong phương
pháp lọc cộng tác) [4] nhanh chóng trở thành một xu hướng nghiên cứu mới,
mang lại nhiều thành tựu vượt trội và cho đến nay vẫn được coi là một phương
pháp thế mạnh của hệ thống tư vấn. Y. Koren [4] đã chiến thắng giải Netflix cho
bài toán tư vấn dựa trên phương pháp thừa số hóa ma trận. Giải Netflix trị giá
một triệu đô la để cải thiện độ chính xác cho dự đốn tư vấn 10 phần trăm đã
mang lại sự phấn kích cho các nhà nghiên cứu, cùng nhau nỗ lực để đưa ra các
phương pháp dự đốn chính xác hơn.
Xuất phát từ những nhu cầu thực tiễn như đã nêu trên, cùng với việc áp
dụng thành quả nghiên cứu của phương pháp thừa số hóa ma trận đã đạt được
từ các nghiên cứu trước đó. Đặc biệt, việc học các nhân tố ẩn (latent factor) [5],

[6] trong phương pháp thừa số hóa ma trận khơng âm nhằm mang lại độ chính
xác cao hơn cho hệ thống tư vấn. Luận văn sẽ sử dụng, tiếp thu những kiến thức
nghiên cứu trước, đi vào tập trung nghiên cứu và đề xuất nâng cao hiệu quả
việc áp dụng thừa số hóa ma trận khơng âm trong các hệ thống tư vấn với mong
muốn cải tiến một số nhược điểm cho hệ thống tư vấn.
1.2. Mục tiêu của luận văn
Trong luận văn, tác giả tập trung vào nghiên cứu việc nâng cao hiệu năng
hệ tư vấn dựa trên thừa số hóa ma trận. Mục tiêu cụ thể:
Nghiên cứu các phương pháp tiếp cận nhằm nâng cao chất lượng hệ

i.

thống tư vấn theo hướng thừa số hóa ma trận.
Nghiên cứu hệ thống tư vấn theo hướng thừa số hóa ma trận không âm

ii.

dựa trên việc học các nhân tố ẩn, đặc biệt:


Các phương pháp cải thiện các hệ số tốt hơn cho ma trận khởi tạo ban
đầu.


5



Các phương pháp cập nhật ma trận thành phần cho bài toán lặp để
đạt được hội tụ nhanh hơn.


Việc kiểm tra hiệu quả cụ thể của thuật toán sẽ sử dụng một một số tập
dữ liệu phổ biến trong hệ thống tư vấn như MovieLens, Book-Crossing. Việc
đánh giá chất lượng cho phương pháp, luận văn sẽ sử dụng các độ đo thông
dụng như Mean Absolute Error (MAE) và Root Mean Square Error (RMSE).
1.3. Nội dung thực hiện
Nhằm đạt được những mục tiêu đã nêu, luận văn sẽ thực hiện các cơng
việc sau đây:
i.

Tiến hành nghiên cứu những cơng trình nghiên cứu có liên quan đến
phương pháp thừa số hóa ma trận.

ii.

Tìm hiểu hiện trạng về các hệ thống tư vấn, phân tích ưu và khuyết điểm
của những phương pháp được áp dụng phổ biến.

iii.

Tìm hiểu về các phương pháp thừa số hóa ma trận cùng với các thuật
tốn tư vấn: Phương pháp lân cận gần nhất, Các mơ hình thống kê, Matrix
factorization, Non-negative matrix factorization, …

iv.

Nghiên cứu các thuật toán của Machine learning.

v.


Xây dựng thuật toán cho tư vấn theo thừa số hóa ma trận khơng âm dựa
trên các thuật toán Machine learning đang áp dụng, kết hợp với các kiến
thức tốn học khác để tối ưu hóa cho bài toán ma trận khởi tạo lẫn bài
toán lặp, đặc biệt chú trọng đến vấn đề dữ liệu thưa.
Về mặt thực nghiệm, những thuật giải tư vấn do luận văn đề xuất sẽ được

thử nghiệm và đánh giá trên một bộ dữ liệu mẫu trong lĩnh vực hệ thống tư vấn,
ví dụ như MovieLens [7] được xem là một bộ dữ liệu “chuẩn” để tiến hành
những thực nghiệm trong lĩnh vực của luận văn. Quá trình thử nghiệm của luận
văn sẽ được tiến hành theo những bước chính như sau:


6



Chuẩn bị dữ liệu



Thu thập các chỉ số đánh giá và xây dựng quy trình thực nghiệm



Tiến hành thử nghiệm để phân tích và đánh giá các độ đo về tính chính
xác, tính hội tụ và thời gian thực thi

1.4. Giới hạn luận văn
Trong phạm vi nghiên cứu, luận văn chỉ tập trung nghiên cứu bài toán theo
hướng thừa số hóa ma trận khơng âm.

Việc cập nhật trong q trình huấn luyện, luận văn chỉ sử dụng một
phương pháp cập nhật duy nhất là Stochastic gradient descent, chưa tiến hành
thử nghiệm các phương pháp cập nhật khác của machine learning như
Conjugate gradient.
Thời gian thực thi của phương pháp đề xuất trong luận văn nhiều hơn
phương pháp thừa số hóa ma trận khơng âm thơng thường.
1.5. Tóm tắt những đóng góp của luận văn
Luận văn có những đóng góp về mặt khoa học và thực tiễn, chi tiết được
trình bày ở phần 1.5.1 và 1.5.2.
1.5.1. Đóng góp về mặt khoa học
Luận văn đã đề xuất được hai cải tiến cho bài tốn thừa số hóa ma trận
khơng âm, cụ thể:


Luận văn đề xuất độ đo PJ để đánh hệ số khởi tạo cho hai ma trận thành
phần U, I ban đầu.



Luận văn cải tiến thuật toán cập nhật hệ số cho hai ma trận U, I bằng
cách đề xuất tính hàm chi phí FKI và sử dụng hàm chi phí này làm cơ
sở để cập nhật cho hai ma trận thành phần U, I trong q trình huấn
luyện (tối ưu hóa) bằng vòng lặp.


7

1.5.2. Đóng góp về mặt thực tiễn
Bên cạnh những đóng góp về mặt khoa học, luận văn cịn có những đóng
góp về mặt thực tiễn:



Luận văn đánh giá những phương pháp đề xuất bằng cách thực nghiệm
trên bộ dữ liệu chuẩn Movielens.



Độ hội tụ và độ chính xác khi áp dụng trên bộ dữ liệu Movielens cho
kết quả đáng khích lệ.

1.6. Tổ chức luận văn
Để đạt được mục tiêu trên, luận văn được trình bày thành năm chương có
cấu trúc như sau:


Chương 1: Giới thiệu. Trong chương này, tác giả trình bày về đề tài
nghiên cứu của luận văn như mục tiêu, nội dung nghiên cứu, giới hạn
luận văn cũng như những đóng góp của luận văn.



Chương 2: Các hệ thống tư vấn. Trong chương này, tác giả trình bày
về hiện trạng của các hệ thống tư vấn truyền thống, những cách tiếp
cận lọc cộng tác cũng như trình bày mơ hình thường được áp dụng trong
Matrix Factorization gồm: Matrix Factorization và Non-negative
Matrix Factorization.



Chương 3: Tư vấn thông tin dựa trên thừa số hóa ma trận khơng âm.

Trong chương này, tác giả trình bày về thuật tốn đề xuất, được xây
dựng từ việc lai hóa cơng thức tính độ tương đồng PJ cho ma trận khởi
tạo và hàm chi phí FKI cũng như công thức cập nhật cho các ma trận
thành phần khi thực hiện phân tích nhân tử ma trận không âm.



Chương 4: Kết quả thực nghiệm. Trong chương này, tác giả trình bày
quá trình tiến hành cũng như kết quả thử nghiệm của các thuật toán đề
xuất trên bộ dữ liệu MovieLens. Những đánh giá và phân tích cũng được


8

trình bày nhằm giúp làm rõ kết quả thực nghiệm cho các thuật toán đề
xuất.


Chương 5: Tổng kết. Trong chương này, tác giả trình bày phần kết luận
và nêu lên một số hướng phát triển trong tương lai của luận văn.


9

Chương 2. CÁC HỆ THỐNG TƯ VẤN
2.1. Tổng quan về hệ thống tư vấn
Các hệ thống tư vấn (Recommender Systems - RS) được quan tâm nghiên
cứu xuất phát từ mục đích thương mại, các cơng ty bán hàng mong muốn có
những hệ thống tư vấn tự động, nhằm cung cấp thơng tin hữu ích cho users về
các loại hàng hóa hay dịch vụ (items) đáp ứng chính xác, phù hợp hơn nhu cầu

riêng của từng cá nhân [2], [8]. Ví dụ các hệ thống như Ebay, Amazon,
MovieLens… có chức năng tư vấn những thông tin về một số items đáp ứng
theo nhu cầu hay sở thích của từng user. Nhìn chung các hệ thống tư vấn hiện
có dựa trên hai cách tiếp cận chính: tiếp cận dựa trên nội dung (Content-Based
- CB ) và tiếp cận dựa trên lọc cộng tác (Collaborative Filtering – CF). Ngoài
ra, cách tiếp cận “lai hóa” giữa 2 cách trên cịn sử dụng, nhằm mang lại hiệu
quả và sự phong phú cho các hệ thống tư vấn. Hình 2.1 thể hiện một số hướng
nghiên cứu trong hệ thống tư vấn hiện nay.
Theo cách tiếp cận dựa trên nội dung (CB) [9], [10] người ta chủ yếu dựa
vào nội dung và đặc trưng của các items. Từ đó người ta tính được mức độ
tương đồng của các items dựa vào các vector đặc trưng của items. Khi một user
u đánh giá item ij, hệ thống sẽ tìm các items ik, ih,... có vector đặc trưng tương
đồng với item ij để tư vấn cho user u đó. Cách tiếp cận này có ưu điểm là khả
năng cao users sẽ nhận được các tư vấn về items phù hợp với sở thích của mình
thơng qua việc tính mức độ tương đồng của các items với nhau chứ không phải
cùng đánh đồng sở thích của mọi users là như nhau. Khuyết điểm là nội dung
mà user được tư vấn bị giới hạn, nghĩa là user chỉ nhận được các tư vấn về
những items có độ tương đồng với items mà mình đã đánh giá, điều này vơ tình
làm cho user khơng có cơ hội nhận được những tư vấn về các items ở lĩnh vực
khác mà có thể user cũng quan tâm.


10

Hình 2.1. Một số hướng nghiên cứu tiếp cận của hệ thống tư vấn

Cách tiếp cận dựa trên lọc cộng tác (CF) [11], [12] chủ yếu dựa vào tính
tương đồng của các users với nhau, theo cách này khi một user ui cung cấp
đánh giá của mình cho một item i trong một ma trận đánh giá R (ratings matrix),
với mỗi ui hệ thống sẽ xác định một cộng đồng các users uj, uk,... có tính tương

đồng với user ui đó, dựa trên độ tương đồng vector đặc trưng của các users với
nhau. Sau khi xác định cộng đồng những người tương đồng với user ui, hệ thống
tư vấn sẽ đưa ra tư vấn những items mà cộng đồng này cho điểm cao. Ưu điểm
của CF chính là sự chia sẻ thông tin trong cộng đồng các users, nghĩa là khi có
một user u đánh giá thích một item i nào đó, thì hệ thống tư vấn có thể sử dụng
thông tin này để tư vấn cho các users khác trong cùng cộng đồng. Việc này sẽ
làm cho nội dung tư vấn được phong phú, khác với trường hợp CB chỉ tư vấn
xung quanh các items cùng độ tương đồng nhất định dựa vào vector đặc trưng
của items. Khuyết điểm của CF, có khả năng sẽ có một số users cá biệt trong
cộng đồng, nghĩa là sở thích của họ về một số items nào đó có thể trái ngược


11

hoặc khác hồn tồn với cộng đồng mà users đó đang thuộc về, dẫn đến tư vấn
khơng cịn chính xác. Cũng theo cách tiếp cận dựa trên lọc cộng tác, có hai
hướng đi chính là dựa trên Memory based và hướng còn lại dựa trên Model
based, cụ thể như sau:
Hướng tiếp cận Memory based (Neighborhood base) [13] thu thập dữ liệu
ratings trong hệ thống và dùng nó để tính tốn ratings cho items mới. Memory
based có thể được thực hiện theo hai cách, tư vấn dựa trên users hoặc dựa trên
items. Tuy nhiên hướng tiếp cận Memory based bị hạn chế bởi các nhược điểm,
đầu tiên là độ thưa thớt dữ liệu (sparsity), Memory based đưa ra tư vấn các
items đa phần dựa vào sở thích của users đã có trong quá khứ, nếu xuất hiện
users mới thì hệ thống sẽ cần thông tin đánh giá đủ số lượng items cho phép để
hệ thống nắm bắt được sở thích của những users mới này một cách chính xác,
như vậy khả năng đưa ra các tư vấn tin cậy càng lớn. Tương tự, các items mới
cũng có chung một vấn đề. Khi các items mới được thêm vào hệ thống, chúng
cần được đánh giá bởi số lượng users đáng kể trước khi các items có thể được
tư vấn cho những users có cùng sở thích trong cộng đồng. Thứ hai về khả năng

mở rộng (scalability) hay cịn có thể hiểu là tốc độ xử lí sẽ giảm khi số lượng
users-items lớn lên. Các thuật toán CF truyền thống gặp phải các vấn đề nghiêm
trọng, với hàng chục triệu users và hàng triệu items thì độ phức tạp của bài tốn
là cả vấn đề.
Theo hướng tiếp cận Model based [14], người ta sẽ thiết lập mơ hình để
huấn luyện và đánh giá những ratings chưa biết của users. Các nghiên cứu trước
đây tập trung áp dụng nhiều phương pháp như: Phân tích ngữ nghĩa tiềm ẩn
(Latent Semantic Analysis) [15], Cực đại entropy (Maximum Entropy) [16],
Cấp phát Dirichlet ẩn (Latent Dirichlet Allocation) [17], Gom cụm Bayes
(Bayesian Clustering) [18], Support Vector Machine và phân rã các giá trị đơn
(Singular Value Decomposition) [8]. Mặt khác, phương pháp thừa số hóa ma


12

trận thông qua việc phân rã ma trận và xét tính tương đồng [19] cũng được sử
dụng.
Dùng phương pháp thừa số hóa ma trận (Matrix Factorization –MF) [4]
là một hướng tiếp cận trong Model based và thu hút các nhà nghiên cứu.
Phương pháp thừa số hóa ma trận có ưu điểm là độ chính xác cao, ngồi ra
phương pháp này cịn có ưu điểm về tốc độ xử lí khi dữ liệu users và items
trong thế giới thực lớn lên. Phương pháp thừa số hóa ma trận (đặc biệt việc thừa
số hóa ma trận khơng âm) được thực hiện bằng cách chuyển đổi cả users và
items sang cùng một không gian đặc trưng ẩn (latent feature) [20], xác định
mỗi thực thể với một vector đặc trưng được suy ra từ những ratings có sẵn, sau
đó phát sinh dự đốn cho những ratings chưa biết bằng cách tính tích trong
(inner product) của các cặp vector tương ứng. Tuy phương pháp thừa số hóa
ma trận khơng âm cho kết quả tốt hơn các phương pháp khác, nhưng việc phân
rã ma trận không âm hiện nay vẫn còn một vài hạn chế, như kết quả thường phụ
thuộc vào sự khởi tạo ban đầu của ma trận users và items. Điều này đòi hỏi các

chiến lược thích hợp và hiệu quả cho ma trận khởi tạo ban đầu U và I. Hiện
nay, người ta chủ yếu dùng phương pháp random ngẫu nhiên cho hai ma trận
ban đầu này, điều này dẫn đến trường hợp nếu một khởi tạo ngẫu nhiên khơng
có lợi sẽ dẫn tới hội tụ chậm, hoặc cho kết quả khơng chính xác. Hạn chế thứ
hai của bài tốn thừa số hóa ma trận không âm là sự hội tụ sau quá trình lặp.
Cứ sau mỗi bước lặp, thuật tốn sẽ cập nhật các giá trị cho hai ma trận thành
phần U và I. Đối với những ma trận lớn, độ thưa dữ liệu cao, câu hỏi đặt ra là
cần phải qua bao nhiêu bước lặp để cho ra kết quả tốt mà chi phí về thời gian
có thể chấp nhận được? Nếu cải tiến được một thuật toán tốt hơn các thuật tốn
hiện có, hi vọng rằng q trình hội tụ kết quả sẽ diễn ra nhanh hơn và cho kết
quả chính xác hơn.


13

Bài tốn tư vấn hiện nay có rất nhiều ứng dụng ngồi thực tế đồng thời
cũng có nhiều thách thức lớn, chẳng hạn:
Thiếu dữ liệu: Thiếu dữ liệu ở đây có nghĩa là thiếu thơng tin về users.
Vấn đề lớn nhất đối với các hệ thống tư vấn là cần rất nhiều dữ liệu để đưa ra
các tư vấn một cách hiệu quả. Không phải ngẫu nhiên mà các công ty được xác
định có các tư vấn xuất sắc là những cơng ty có nhiều dữ liệu về users như:
Google, Amazon, Netflix, Last.fm. Một hệ thống tư vấn tốt trước hết cần có dữ
liệu đầy đủ về các items tư vấn, sau đó phải nắm bắt và phân tích dữ liệu users
(các sự kiện, hành vi), và cuối cùng là thuật toán tư vấn. Mối quan hệ giữa dữ
liệu (users-items) và chất lượng tư vấn là một mối quan hệ biện chứng. Hệ
thống tư vấn càng có nhiều dữ liệu về items và users, cơ hội đưa ra các tư vấn
càng chính xác. Ngược lại, để có được các tư vấn tốt, hệ thống cần rất nhiều
users cũng như thông tin về các users đó.
Thay đổi dữ liệu: Thay đổi dữ liệu ở đây có nghĩa là users có những thay
đổi thơng tin cá nhân hay items có xu hướng lỗi thời. Đối với vấn đề thay đổi

dữ liệu các hệ thống thường có xu hướng thiên vị đối với items cũ và gặp khó
khăn khi tư vấn items mới. Một ví dụ về điều này đã được viết bởi David Reinke
của StyleHop, thuộc cộng đồng nguồn nhân lực dành cho những người đam mê
thời trang. David cho rằng hành vi quá khứ của users không phải là một công
cụ tốt bởi vì “các xu hướng ln ln thay đổi”. Rõ ràng một cách tiếp cận thuật
toán sẽ gặp phải khó khăn nếu khơng thể theo kịp xu hướng thời trang. Hầu hết
những người không am hiểu nhiều về thời trang thường dựa vào những người
bạn và gia đình có kiến thức về thời trang tư vấn quần áo mới cho họ. David
Reinke tiếp tục nói rằng các tư vấn sản phẩm khơng hoạt động hiệu quả vì có
q nhiều thuộc tính sản phẩm trong thời trang và mỗi thuộc tính (sự phù hợp,
giá cả, màu sắc, phong cách, vải, thương hiệu…) có tầm quan trọng khác nhau,
thời gian khác nhau cho cùng một người tiêu dùng nếu áp dụng hệ thống tư vấn


14

tự động. Tuy nhiên các tư vấn xã hội (tư vấn từ người thân, đồng nghiệp, bạn
bè) có lẽ sẽ giải quyết được vấn đề này.
Thay đổi sở thích users: Việc user thay đổi sở thích ở đây là trong khi
hôm nay user chú ý item này nhưng ngày mai user có thể sẽ chú ý tới một item
khác. Một ví dụ điển hình là một hơm nào đó user sẽ lướt trên trang Amazon
tìm những cuốn sách mới, nhưng ngày hơm sau, user sẽ tìm trên Amazon một
món q sinh nhật cho người thân chẳng hạn. Về chủ đề sở thích user, hệ thống
tư vấn cũng có thể gắn nhãn khơng chính xác cho user.
Những items khơng thể dự đốn: Trong giải thưởng Netflix, trị giá một
triệu đơ do Netflix thưởng cho các nhóm nghiên cứu cung cấp thuật toán lọc
cộng tác để cải thiện thuật toán tư vấn của Netflix 10%, người ta lưu ý rằng có
vấn đề xảy ra với phim kinh dị. Loại phim mà mọi người hoặc u thích hoặc
ghét, như Napoleon Dynamite, rất khó đưa ra các tư vấn, bởi vì phản ứng của
users đối với loại phim này có xu hướng đa dạng và khơng thể đốn trước.

Những thách thức kể trên của hệ thống tư vấn được các nhà khoa học tập
trung nghiên cứu nhằm cải thiện chất lượng hệ tư vấn, đặc biệt đối với thách
thức đầu tiên, tức bài toán cold-start, đã có rất nhiều cố gắng giải quyết vấn đề
thưa dữ liệu. Một phương pháp được đưa ra với một số thành cơng đó là phương
pháp nhằm làm giảm số chiều của ma trận đánh giá. Chiến lược đơn giản để
giảm số chiều là hình thành tập hợp các cụm items hoặc users, sau đó sử dụng
các cụm này như một thành phần cơ bản trong dự đoán. Để phương pháp gom
cụm này tốt hơn thì người ta sử dụng kỹ thuật thống kê như nguyên lý phân tích
thành phần PCA và kỹ thuật truy vấn thông tin như chỉ mục ngữ nghĩa tiềm
tàng LSI. Về bản chất, những phương pháp giảm số chiều giải quyết vấn đề
thưa dữ liệu bằng cách sinh ra nhiều ma trận tương tác user – item được xem là
gần gũi nhất với users và items. Tuy nhiên, trong một vài trường hợp, thông tin


15

hữu ích có thể bị mất trong suốt tiến trình giảm chiều ma trận, làm cho các dự
đốn khơng cịn đáng tin cậy nữa.
Giải quyết vấn đề thưa dữ liệu chính là sự kết hợp giữa phương pháp lọc
cộng tác với những phương pháp tiếp cận dựa trên nội dung. Thêm vào đó là
những tương tác giữa user – item, vì vậy các kỹ thuật này cũng xem độ tương
đồng items xuất phát từ nội dung của chính các items đó, điều này tạo ra dự
đốn chính xác hơn. Tuy nhiên, khuyết điểm chính của những kỹ thuật này là
chỉ có thể được sử dụng khi nội dung thơng tin có sẵn trong hệ thống, điều này
có thể gây khó khăn trong một số trường hợp.
2.2. Các hệ thống tư vấn lọc cộng tác
Lọc cộng tác là một kỹ thuật mạnh và nó đã được áp dụng khá thành cơng
trong nhiều hệ tư vấn. Về thực chất, lọc cộng tác là một hình thức tư vấn tự
động bằng cách dựa trên sự tương đồng giữa những users hoặc giữa những
items trong hệ thống và đưa ra tư vấn cho user một hoặc một vài items, hoặc

gợi ý một item mới cho user nào đó.
Có rất nhiều phương pháp tiếp cận trên hình thức này được trình bày,
nhưng các kỹ thuật này hầu chỉ xét đến sự tương đồng trực tiếp giữa hai users
hoặc hai items. Trong phương pháp lọc cộng tác, hai users được coi là tương
đồng nếu họ thể hiện mối quan tâm giống nhau về cùng các items thông qua
việc mua hoặc đưa ra đánh giá về items đó. Tuy nhiên, trên thực tế hai người
có thể mua những items hồn tồn khác nhau nhưng lại có những sở thích giống
nhau. Tương tự vậy, hai items có thể khơng được mua bởi cùng một user nhưng
hồn tồn có thể tương tự nhau. Một điểm khác của cách tiếp cận này là sự nhạy
cảm của nó khi có quá ít dữ liệu, điều này xảy ra khi có nhiều users nhưng mỗi
người lại chỉ mua hoặc đánh giá ở một hoặc một vài items hoặc khi có nhiều
items nhưng mỗi item lại chỉ được mua bởi một hoặc một vài users. Tuy nhiên,


16

trong rất nhiều trường hợp thực tế, việc dữ liệu thưa là điều khơng thể tránh. Ví
dụ như khi user mới đăng ký vào hệ thống nên khơng có hoặc có ít thơng tin về
sở thích, hoặc khi một item mới được thêm vào hệ thống nên có thể chưa hoặc
mới được mua hay đánh giá bởi rất ít users. Vấn đề này còn được gọi là coldstart.
Hạn chế của phương pháp lọc cộng tác, có nghĩa là các dự đoán giá trị Rij
đã cho sẽ được tư vấn cho cộng đồng những users có độ tương đồng với user u
nào đó, trong khi có thể xảy ra trường hợp trong cộng đồng của user u này có
một vài users cá biệt, có sở thích khác các users cịn lại trong cộng đồng. Sau
đây là phần trình bày ba phương pháp chính trong số các phương pháp lọc cộng
tác.
2.2.1. Phương pháp lân cận gần nhất
Để dự đoán rating Rij được đánh giá bởi user i cho item j, người ta tìm
những users khác trong tập dữ liệu đã được đánh giá cho item j và những users
có các mẫu ratings tương tự với user i về các items khác (tìm lân cận cho user

i). Lấy 𝑅̅𝑖𝑗 là mức trung bình ratings của item j trong số những láng giềng lân
cận với user i, sau đó đưa ra dự đốn ratings cho user i dựa trên 𝑅̅𝑖𝑗 . Đây gọi
đây là phương pháp k-lân cận gần nhất (k-Nearest Neighbor hay kNN).
Ban đầu trong lĩnh vực hệ thống tư vấn có xu hướng sử dụng phương pháp
này. Tất nhiên, một trong những vấn đề nảy sinh đó là định nghĩa của gần nhất,
rất khó để đánh giá định nghĩa gần nhất và tìm lân cận gần cho một user khi mà
trong thực tế là hầu hết các dữ liệu đánh giá bị thiếu. Vấn đề thưa dữ liệu này
tiếp tục được trình bày ở các phương pháp dưới đây.