Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015
MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI
1
Đỗ Thị Liên, 1Nguyễn Xuân Anh, 1Nguyễn Duy Phương, 1Từ Minh Phương
1
Học viện Công nghệ Bưu chính Viễn thông
liendt@ptit.edu.vn, anhnx@ptit.edu.vn,phuongnd@ptit.edu.vn, phuongtm@ptit.edu.vn
Tóm tắt - Hệ tư vấn (recommender systems) là hệ thống có khả năng cung cấp thông tin phù hợp và gỡ bỏ thông tin không
phù hợp cho mỗi người dùng sử dụng các dịch vụ Internet. Hệ tư vấn được xây dựng dựa trên hai kỹ thuật lọc thông tin chính: Lọc
cộng tác (collaborative filtering) và lọc nội dung (content-based filtering). Mỗi phương pháp khai thác những khía cạnh riêng liên
quan đến đặc trưng nội dung hay thói quen sử dụng sản phẩm của người dùng trong quá khứ để dự đoán một danh sách ngắn gọn
các sản phẩm phù hợp nhất đối với mỗi người dùng. Trong bài báo này, chúng tôi đề xuất một phương pháp hợp nhất giữa tư vấn
cộng tác và tư vấn nội dung bằng mô hình đồ thị. Mô hình cho phép ta dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng
tác, sau đó xây dựng một độ tương tự mới trên đồ thị để xác định mức độ tương tự giữa các cặp người dùng và sản phẩm để sinh ra
kết quả dự đoán. Kết quả thử nghiệm trên các bộ dữ liệu thực về phim cho thấy các phương pháp đề xuất cải thiện đáng kể chất
lượng tư vấn.
Từ khóa - Tư vấn cộng tác, tư vấn theo nội dung, hệ tư vấn lai, tư vấn dựa vào sản phẩm, tư vấn dựa vào người dùng.
I. GIỚI THIỆU HỆ TƯ VẤN
Người dùng sử dụng các dịch vụ Internet trực tuyến hiện nay luôn trong tình trạng quá tải thông tin. Để tiếp cận
được thông tin hữu ích, người dùng thường phải xử lý, loại bỏ phần lớn thông tin không cần thiết. Hệ tư vấn
(recommender systems) cung cấp một giải pháp nhằm giảm tải thông tin bằng cách dự đoán và cung cấp một danh sách
ngắn các sản phẩm (trang web, bản tin, phim, video…) phù hợp cho mỗi người dùng. Trên thực tế, hệ tư vấn không chỉ
hướng đến vấn đề giảm tải thông tin cho mỗi người dùng mà nó còn là yếu tố quyết định đến thành công của các hệ
thống thương mại điện tử [4]. Bài toán tư vấn tổng quát có thể được phát biểu như sau.
Cho tập hợp hữu hạn gồm N người dùng U = {u1, u2,…, uN}, P = {p1, p2,.., pM} là tập hữu hạn gồm M sản phẩm.
Mỗi sản phẩm px∈P có thể là hàng hóa, phim, ảnh, tạp chí, tài liệu, sách, báo, dịch vụ hoặc bất kỳ dạng thông tin nào
mà người dùng cần đến. Mối quan hệ giữa tập người dùng U và tập sản phẩm P được biểu diễn thông qua ma trận đánh
giá R={ rix: i = 1, 2, ..N; x = 1, 2,..M }. Giá trị rix thể hiện đánh giá của người dùng ui∈U cho một số sản phẩm px∈P.
Thông thường giá trị rix nhận một giá trị thuộc miền F = { 1, 2,.., g} được thu thập trực tiếp bằng cách hỏi ý kiến người
dùng hoặc thu thập gián tiếp thông qua cơ chế phản hồi của người dùng. Giá trị rix = φ được hiểu người dùng ui chưa
đánh giá hoặc chưa bao giờ biết đến sản phẩm px. Ma trận đánh giá của các hệ thống tư vấn thực tế thường rất thưa.
Mật độ các giá trị rix≠0 nhỏ hơn 1%, hầu hết các giá trị rix còn lại là φ [4]. Ma trận R chính là đầu vào của các hệ thống
tư vấn cộng tác [1, 2, 3]. Để thuận tiện trong trình bày, ta viết px∈P ngắn gọn là x∈P; và ui∈U là i∈U. Các ký tự i, j
luôn được dùng để chỉ tập người dùng trong các mục tiếp theo của bài báo.
Mỗi sản phẩm x∈P được biểu diễn thông qua |C| đặc trưng nội dung C = { c1, c2,.., c|C|}. Các đặc trưng cs∈C
nhận được từ các phương pháp trích chọn đặc trưng (feature selection) trong lĩnh vực truy vấn thông tin. Ví dụ x∈P là
một phim thì các đặc trưng nội dung biểu diễn một phim có thể là C={thể loại phim, nước sản xuất, hãng phim, diễn
viên, đạo diễn…}. Gọi wx = {wx1, wx2,.., wx|C| } là vector trọng số các giá trị đặc trưng nội dung sản phẩm x∈P . Khi đó,
ma trận trọng số W ={wxs: x =1, 2, .., M; s =1, 2, .., |C|} chính là đầu vào của các hệ thống tư vấn theo nội dung sản
phẩm [2, 3, 17]. Để thuận tiện trong trình bày, ta viết cs∈C ngắn gọn là s∈C.Ký tự s luôn được dùng để chỉ tập đặc
trưng nội dung sản phẩm trong các mục tiếp theo của bài báo.
Mỗi người dùng x∈P được biểu diễn thông qua |T| đặc trưng nội dung T = {t1, t2,.., t|T|}. Các đặc trưng tq∈T
thông thường là thông tin cá nhân của mỗi người dùng (Demographic Information). Ví dụ i∈U là một người dùng thì
các đặc trưng nội dung biểu diễn người dùng i có thể là T={giới tính, độ tuổi, nghề nghiệp, trình độ,…}. Gọi vi = {vi1,
vi2,.., vi|T|} là vector trọng số biểu diễn các giá trị đặc trưng nội dung người dùng i∈U. Khi đó, ma trận trọng số V ={viq
: i = 1, 2, .., N;q = 1, 2, .., |T| } chính là đầu vào của các hệ thống tư vấn theo nội dung thông tin người dùng [3, 13]. Để
thuận tiện trong trình bày, ta viết tq∈T ngắn gọn là q∈T. Ký tự q luôn được dùng để chỉ tập đặc trưng nội dung người
dùng trong các mục tiếp theo của bài báo.
Tiếp đến ta ký hiệu, Pi⊆P là tập các sản phẩm x∈P được đánh giá bởi người dùng i∈U và Ux⊆U là tập các
người dùng i∈U đã đánh giá sản phẩm x∈P. Với một người dùng cần được tư vấn i∈U (được gọi là người dùng hiện
thời, người dùng cần được tư vấn, hay người dùng tích cực), nhiệm vụ của các phương pháp tư vấn là gợi ý K sản phẩm
x∈(P\Pi) phù hợp nhất đối với người dùng i.
Có nhiều đề xuất khác nhau để giải quyết bài toán tư vấn. Hệ tư vấn theo nội dung xây dựng phương pháp dự
đoán dựa trên ma trận trọng số các đặc trưng nội dung sản phẩm W={wxs} hoặc ma trận trọng số các đặc trưng nội dung
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
431
người dùng V ={viq} [3, 13, 17]. Hệ tư vấn cộng tác đưa ra phương pháp dự đoán dựa trên ma trận đánh giá R={rix} [1,
2, 4]. Hệ tư vấn lai đưa ra phương pháp dự đoán dựa trên cả 3 ma trận R, W và V[3, 9].
II. MỘT SỐ NGHIÊN CỨU LIÊN QUAN
Hiệu quả của phương pháp tư vấn lai đã được khẳng định trong nhiều nghiên cứu khác nhau [2, 8]. Hướng tiếp cận
phổ biến nhất thường được sử dụng là phương pháp tổ hợp tuyến tính giữa lọc cộng tác và lọc nội dung. Trong hướng
tiếp cận này, các tác giả tiến hành xây dựng hai phương pháp lọc cộng tác và lọc nội dung độc lập nhau, sau đó tổ hợp
tuyến tính kết quả dự đoán của cả hai hoặc lựa chọn ứng viên tốt nhất từ một trong hai phương pháp [17]. Hướng tiếp
cận thứ hai xem xét vấn đề tư vấn lai bằng cách thêm các đặc trưng của lọc nội dung vào lọc cộng tác. Phương pháp
được thực hiện bằng cách xây dựng một thủ tục kết hợp dữ liệu để tạo nên dữ liệu đầu vào tổng hợp giữa các giá trị
đánh giá của lọc cộng tác và các đặc trưng nội dung. Pazzani [13] đề xuất phương pháp biểu diễn hồ sơ sản phẩm bằng
một vector trọng số các đặc trưng nội dung người dùng. Dựa trên biểu diễn này, phương pháp dự đoán được Pazzani
thực hiện bằng các kỹ thuật lọc cộng tác thuần túy. Hướng tiếp cận thứ ba xem xét bài toán tư vấn lai bằng cách thêm
các đặc trưng của lọc cộng tác vào lọc nội dung. Theo phương pháp này, các đặc trưng nội dung sản phẩm đóng vai trò
trung tâm và xem xét đánh giá người dùng của lọc cộng tác như các giá trị đặc trưng giả định để thêm vào quá trình dự
đoán [17, 18].
Hướng tiếp cận cuối cùng được cộng đồng quan tâm nghiên cứu là hợp nhất giữa lọc cộng tác và lọc nội dung dựa
trên các kỹ thuật học máy. Basu [19] đề xuất việc xây dựng tập các giá trị đặc trưng đại diện cho cả lọc cộng tác và lọc
nội dung. Phương pháp dự đoán được tiến hành dựa trên việc xây dựng tập luật suy diễn các giá trị đặc trưng. Popescul
[20] đề xuất mô hình phân tích ngữ nghĩa ẩn để hợp nhất giữa lọc cộng tác và lọc nội dung. Balisico và Hofman [21] sử
dụng hàm nhân để kết hợp mức độ tương tự từ người dùng đến người dùng, sản phẩm đến sản phẩm, sau đó áp dụng
máy vector hỗ trợ để sinh ra dự đoán. Crammer và Singer [22] xem xét bài toán tư vấn lai như việc xếp hạng các sản
phẩm bằng việc bổ sung các đặc trưng nội dung sản phẩm.
Liên quan đến mô hình đồ thị, nhiều đề xuất khác nhau đã được đưa ra giải quyết bài toán tư vấn. Aggarwal [23]
biểu diễn mối quan hệ giữa các cặp người dùng như một đồ thị có hướng, trong đó mỗi cạnh được thiết lập phản ánh
mức độ tương tự giữa hai người dùng. Phương pháp dự đoán được thực hiện bằng cách tính toán trọng số đường đi
ngắn nhất giữa các cặp người dùng. Lien [7] đề xuất xây dựng độ đo tương tự giữa các cặp người dùng hoặc sản phẩm
bằng mô hình đồ thị hai phía có trọng số. Mức độ tương tự giữa các cặp người dùng được thực hiện bằng cách ước
lượng tổng trọng số của tất cả các đường đi từ đỉnh người dùng đến đỉnh người dùng, mức độ tương tự giữa các cặp sản
phẩm được thực hiện bằng cách ước lượng tổng trọng số của tất cả các đường đi từ sản phẩm dùng đến đỉnh sản phẩm.
Phuong [6] đề xuất phương pháp kết hợp giữa lọc cộng tác và lọc nội dung bằng cách xây dựng mối liên hệ giữa người
dùng và tập đặc trưng nội dung sản phẩm. Phương pháp dự đoán được thực hiện bằng cách tổ hợp tuyến tính trọng số
các đường đi từ đỉnh người dùng đến đỉnh sản phẩm. Sản phẩm nào có tổng trọng số các đường đi lớn nhất đến nó
chính là đích của quá trình dự đoán.
Trong bài báo này, chúng tôi đề xuất một mô hình hợp nhất giữa lọc cộng tác và lọc nội dung dựa trên biểu diễn đồ
thị. Mô hình được xây dựng bằng cách lấy lọc cộng tác làm trung tâm, xây dựng hồ sơ người dùng dựa trên ma trận
đánh giá để thiết lập nên mối quan hệ trực tiếp giữa tập người dùng với tập đặc trưng nội dung sản phẩm. Tiếp đến,
chúng tôi tiến hành xây dựng hồ sơ sản phẩm cũng dựa trên ma trận đánh giá để thiết lập nên mối quan hệ trực tiếp
giữa tập sản phẩm và tập đặc trưng nội dung người dùng. Dựa trên mối quan hệ giữa tập người dùng với tập đặc trưng
nội dung sản phẩm và mối quan hệ giữa tập sản phẩm với tập đặc trưng nội dung người dùng, chúng tôi tìm cách xác
định được mối quan hệ tiềm ẩn giữa tập đặc trưng sản phẩm và tập đặc trưng người dùng. Bằng cách này, chúng tôi thu
gọn mô hình tư vấn kết hợp tổng quát thành mô hình tư vấn cộng tác chuẩn.
Về nguyên tắc, sau khi thu được mô hình tư vấn cộng tác chuẩn ta có thể triển khai bất kỳ một phương pháp lọc
cộng tác nào đã được đề xuất trước đây. Tuy nhiên để khai thác được thế mạnh của đồ thị, chúng tôi xây dựng một độ
tương tự dựa trên đồ thị bằng cách ước lượng mức độ tương tự giữa các cặp người dùng dựa trên tổng trọng số các
đường đi từ đỉnh người dùng đến đỉnh người dùng, mức độ tương tự giữa các cặp sản phẩm dựa trên tổng trọng số các
đường đi từ đỉnh sản phẩm đến đỉnh sản phẩm. Bằng cách này ta tận dụng được các thuật toán tìm kiếm hiệu quả đã
được triển khai trên đồ thị. Để tập trung trình bày phương pháp đề xuất, mục tiếp theo chúng tôi trình bày bày phương
pháp dịch chuyển bài toán tư vấn kết hợp về bài toán lọc cộng tác. Mục 4 trình bày về các phương pháp tư vấn lai dựa
trên đồ thị. Mục 5 trình bày phương pháp thử nghiệm và so sánh. Mục cuối cùng là kết luận và hướng phát triển tiếp
theo của bài báo.
III. DỊCH CHUYỂN BÀI TOÁN TƯ VẤN KẾT HỢP VỀ BÀI TOÁN LỌC CỘNG TÁC
Như đã giới thiệu ở trên, bài toán tư vấn kết hợp thực hiện dự đoán dựa trên tập đánh giá của người dùng cho các
sản phẩm, cùng với tập đặc trưng nội dung sản phẩm và đặc trưng người dùng. Trong mục này, chúng tôi đề xuất
phương pháp dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng tác thuần túy bằng cách xây dựng hồ sơ
người dùng và hồ sơ sản phẩm của dựa vào đánh giá tự nhiên của người dùng đối với các sản phẩm trong quá khứ.
Trên cơ sở hồ sơ người dùng và hồ sơ sản phẩm đã được xây dựng, chúng tôi tìm cách xác định mối quan hệ tiềm ẩm
giữa tập đặc trưng nội dung người dùng và tập đặc trưng nội dung sản phẩm để thu được mô hình giống với mô hình
MỘ
ỘT MÔ HÌNH ĐỒ
Ồ THỊ CHO HỆ TƯ
T VẤN LAI
432
4
bài
b toán tư vấnn cộng tác. Đểể diễn giải tínnh đúng đắn củ
ủa phương ph
háp đề xuất, chhúng tôi sử dụụng mô hình đồ
đ thị thực
hiện
h cho bài tooán tư vấn kết hợp.
3.1.
3 Biểu diễn
n đồ thị cho lọọc kết hợp
Không hạạn chế tính tổnng quát của bàài toán phát biểu trong Mục 1, ta giả thiếtt giá trị đánh ggiá của người dùng i∈U
đối
đ với sản phhẩm x∈P đượcc xác định theeo công thức (1).
( Mỗi sản phẩm
p
x∈P đượ
ược biểu diễn tthông qua |C | đặc trưng
nội
n dung C = {c1, c2,..,c|C|} được xác địnnh theo công thức (2). Mỗi người dùng i∈ U được biểuu diễn thông qua
q |T| đặc
trrưng nội dungg T = {t1, t2,..,, t|T|} được xácc định theo công thức (3).
ế
ườ ù
ẩ
ở ứ độ
∈
đá
á ả
(1)
ế
ườ ù
ư đá
á ặ
ư
ế đế ả
ẩ
1
0
ế
1
0 ế
ả
ế
ườ
ế
ù
ẩ
ườ
ả
ù
ô
ẩ
ô
ó đặ
ó đặ
ư
ư
ó đặ
ó đặ
ư
ư
ế
ế
ế
0 ∶
0∶
0∶
(2)
(3)
Hệ tư vấnn với ma trận đđánh giá R = {{rix:i=1, 2,..,N
N; x=1, 2,..,M}}, ma trận đặc trưng nội dunng sản phẩmC
C={cxs:x=1,
2,
2 .., M; s =1, 2, ..,|C|}, maa trận đặc trưnng nội dung người
n
dùng T = {tiq:i=1, 2, .., N; q =1, 22, ..,|T|}có thể
ể biểu diễn
dưới
d
dạng đồ thị
t trọng số G =(Ω, E), tronng đó Ω là tập đỉnh và E là tập cạnh. Tập đỉnh Ω của đđồ thị được xác
c định theo
công
c
thức (4) chính
c
là hợp ccủa tập người dùng U, tập sản
s phẩm P, tậập đặc trưng nnội dung sản pphẩm C và tập
p đặc trưng
nội
n dung ngườ
ời dùng T. Tậpp cạnh E của đđồ thị bao gồm
m 3 loại cạnh: cạnh (i, x) nnối giữa đỉnh nngười dùng vớ
ới đỉnh sản
phẩm,
p
cạnh (xx, s) nối đỉnh ssản phẩm với đặc trưng nội dung sản ph
hẩm, cạnh (i, qq) nối giữa đỉỉnh người dùn
ng với đỉnh
đặc
đ trưng nội dung
d
của ngườ
ời dùng.
,
,
,
Bảng 1. Ma trrận đánh giá R
u1
u2
u3
p1
5
0
0
p2
0
4
5
p3
4
0
4
,
,
,
.
.
.
(5)
p4
0
3
0
Bảngg 2. Ma trận đặcc trưng sản phẩẩm C
c1
1
1
1
0
p1
p2
p3
p4
c2
0
1
0
1
c3
1
0
1
1
Bảng 3. Ma trận đặc trưng người dùùng T
u1
u2
u3
t1
1
1
0
t2
0
0
1
t3
0
1
0
t4
1
0
1
Hìn
nh 1. Đồ thị biểểu diễn cho hệ ttư vấn
Ví dụ vớii hệ gồm 3 nggười dùng U = {u1, u2, u3},, 4 sản phẩm P = {p1, p2, p 3, p4}. Trongg đó, ma trận đánh
đ
giá R
được
đ
cho trongg Bảng 1; Maa trận đặc trưnng nội dung sản phẩm C đư
ược cho trongg Bảng 2; Ma trận đặc trưng
g nội dung
người
n
dùng T được cho tronng Bảng 3. Khhi đó, đồ thị biểu
b diễn cho bài
b toán tư vấấn tổng quát đđược biểu diễn
n như Hình
1.
1 Đồ thị đượcc biểu diễn thàành ba đồ thị con hai phía (bipartie
(
praph
h). Đồ thị conn hai phía ở giiữa biểu diễn quan điểm
của
c người dùnng đối với các sản phẩm thôông qua ma trậận đánh giá R =(rix). Các cạạnh nối giữa đđỉnh người dùn
ng i∈U với
đỉnh
đ
sản phẩm
m x∈P được đáánh trọng số llà rix. Đồ thị con
c hai phía trrên cùng biểuu diễn mối quaan hệ giữa sản
n phẩm với
tập đặc trưng nội
n dung sản pphẩm thông qqua ma trận C=
=(cxs). Các cạn
nh nối giữa đỉỉnh sản phẩm x∈P với đỉnh
h đặc trưng
nội
n dung sản phẩm
p
s∈C đượ
ợc đánh trọng số là 1. Đồ th
hị con hai phíaa dưới cùng biiểu diễn mối qquan hệ giữa người
n
dùng
với
v tập đặc trư
ưng nội dung nngười dùng thhông qua ma trrận T=(tiq). Cáác cạnh nối giữ
ữa đỉnh ngườii dùng i∈U vớ
ới đỉnh đặc
trrưng nội dungg người dùng q∈T cũng đượ
ợc đánh trọng số là 1.
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
433
Dựa trên biểu diễn đồ thị, phương pháp tư vấn cộng tác được thực hiện dựa trên các cạnh nối giữa đỉnh người dùng
i∈U và đỉnh sản phẩm x∈P với trọng số rix [5]. Phương pháp tư vấn theo nội dung sản phẩm được thực hiện trên các
cạnh nối giữa đỉnh sản phẩm x∈P và đỉnh đặc trưng nội dung sản phẩm s∈C [7]. Phương pháp tư vấn theo nội dung
người dùng được thực hiện trên các cạnh nối giữa đỉnh người dùng i∈U và đỉnh đặc trưng nội dung người dùng t∈T
[17]. Phương pháp tư vấn kết hợp được thực hiện dựa trên cả ba loại cạnh (i , x), (x, s), và (i, q) [9, 10].
3.2. Xây dựng hồ sơ người dùng dựa trên ma trận đánh giá
Phương pháp tư vấn theo nội dung thực hiện dự đoán các sản phẩm có nội dung thông tin hay mô tả hàng hóa
tương tự với những sản phẩm mà người dùng đã từng sử dụng hoặc truy nhập trong quá khứ. Chất lượng của các
phương pháp tư vấn theo nội dung phụ thuộc vào phương pháp trích chọn đặc trưng để biểu diễn vector đặc trưng nội
dung sản phẩm và vector hồ sơ sử dụng sản phẩm của người dùng. Hạn chế lớn nhất của phương pháp trích chọn đặc
trưng hiện nay là nhiều đặc trưng nội dung không đóng góp vào việc xác định mức độ tương tự giữa vector hồ sơ người
dùng và vector đặc trưng sản phẩm vẫn được tham gia quá trình tính toán [3, 5]. Để hạn chế điều này, chúng tôi đề xuất
phương pháp xây dựng hồ sơ sử dụng sản phẩm của người dùng thông qua các giá trị đánh giá của hệ tư vấn cộng tác,
sau đó thiết lập mối quan hệ trực tiếp giữa người dùng và từng đặc trưng sản phẩm để nâng cao hiệu quả tư vấn.
Phương pháp được tiến hành như sau.
Để xây dựng được hồ sơ sử dụng sản phẩm của người dùng ta cần thực hiện hai nhiệm vụ: xác định được tập các
sản phẩm người dùng đã từng truy cập hay sử dụng trong quá khứ và ước lượng trọng số mỗi đặc trưng nội dung sản
phẩm trong hồ sơ người dùng [2, 17]. Gọi Pi⊆P được xác định theo công thức (6) là tập sản phẩm người dùng i∈U đã
đánh giá các sản phẩm x∈P. Khi đó, Pi chính là tập sản phẩm người dùng đã từng truy cập trong quá khứ được các
phương pháp tư vấn theo nội dung sử dụng trong khi xây dựng hồ sơ người dùng. Vấn đề còn lại là làm thế nào ta ước
lượng được trọng số mỗi đặc trưng s∈C đối với mỗi hồ sơ người dùng i∈U.
∈
|
0
∈ ,
∈
(6)
Gọi ListItem(i, s) là tập các sản phẩm x∈Pi chứa đựng đặc trưng s∈C được xác định theo công thức (7). Khi đó,
|ListItem(i , s)| chính là số lần người dùng i∈U sử dụng các sản phẩm x∈P chứa đựng đặc trưng s∈C trong quá khứ.
,
∈
|
0
∈ ,
∈ , ∈
(7)
Dựa trên Pi và ListItem( i, s) các phương pháp tư vấn theo nội dung ước lượng được trọng số wis phản ánh mức độ
quan trọng của đặc trưng nội dung s đối với người dùng i. Phương pháp phổ dụng nhất thường được sử dụng trong xây
dựng hồ sơ người dùng là kỹ thuật tf-idf [17]. Giá trị wis là một số thực trải đều trong khoảng [0,1]. Tuy nhiên, trong
khi quan sát bài toán tư vấn cộng tác chúng tôi nhận thấy bản thân nó đã tồn tại một phép đánh giá tự nhiên của người
dùng đối với sản phẩm thông qua giá trị đánh giá rix. Giá trị rix phản ánh mức độ ưa thích của người dùng sau khi đã sử
dụng sản phẩm và đưa ra quan điểm của mình đối với sản phẩm. Ví dụ với hệ tư vấn phim [18], giá trị rix = 1, 2, 3, 4, 5
được hiểu theo các mức quan điểm “rất tồi”, “tồi”, “bình thường”, “hay”, “rất hay”. Chính vì lý do đó, chúng tôi mong
muốn có được một phương pháp trích chọn đặc trưng có cùng mức độ đánh giá tự nhiên của rix.
Để thực hiện ý tưởng nêu trên, chúng tôi thực hiện quan sát trên tập ListItem(i, s). Nếu giá trị |ListItem(i, s)| vượt
quá một ngưỡng θ nào đó thì trọng số đặc trưng nội dung sản phẩm s∈C đối với người dùng i∈U là wis được tính bằng
trung bình cộng của tất cả các giá trị đánh giá. Trường hợp |ListItem(i, s)| có giá trị bé hơn θ, giá trị wis được tính bằng
tổng của tất cả các giá trị đánh giá chia cho θ. Trong thử nghiệm, chúng tôi tính toán được số lượng trung bình của tất
cả người dùng i∈U đã đánh giá các sản phẩm x∈P, sau đó chọn θ tương đương với 2/3 số lượng trung bình các đánh
giá của tập người dùng i∈U đã đánh giá sản phẩm x∈P chứa đựng đặc trưng s∈C. Bằng cách này ta có thể hạn chế
được một số đặc trưng nội dung ít được người dùng quan tâm nhưng vẫn được đánh giá với trọng số cao.
|
∑
∈
, |
∑
,
∈
ế
,
ế
|
|
,
|
,
|
(8)
Giá trị wis được ước lượng theo (8) phản ánh quan điểm của người dùng i∈U đối với các đặc trưng nội dung sản
phẩm s∈C cũng chính là hồ sơ người dùng i∈U đã sử dụng các đặc trưng nội dung s∈C trong quá khứ. Dễ dàng nhận
thấy wis∈F, trong đó F = { 1, 2, .., g}. Chính vì vậy, ta có thể xem mỗi đặc trưng nội dung sản phẩm đóng vai trò như
một sản phẩm phụ bổ sung vào tập sản phẩm. Dựa trên nhận xét này, chúng tôi mở rộng đồ thị hai phía của bài toán tư
vấn cộng tác nguyên thủy (đồ thị con ở giữa) bằng cách giữ nguyên tập đỉnh ở phía người dùng U, tập đỉnh phía sản
phẩm được mở rộng là P∪C. Liên kết giữa đỉnh người dùng i∈U và đỉnh sản phẩm x∈P được thiết lập nếu rix≠ 0. Liên
kết giữa đỉnh người dùng i∈U và đỉnh đặc trưng sản phẩm s∈C được thiết lập nếu wis≠ 0. Ma trận đánh giá mở rộng
được xác định theo công thức (9).
ế
∈
ế
à
∈
à
0
0
(9)
MỘ
ỘT MÔ HÌNH ĐỒ
Ồ THỊ CHO HỆ TƯ
T VẤN LAI
434
4
Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn
nh 1, chọn θ = 2 ta sẽ tính toán được ma
a trận đánh
giá
g mở rộng trrong Bảng 4 vvà đồ thị tư vvấn cộng tác mở
m rộng đượcc thể hiện như
ư Hình 2. Cácc cạnh màu đỏ
ỏ là những
cạnh
c
mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng
g tác.
B
Bảng
4. Ma trậận đánh giá mở rộng R
u1
u2
u3
p1
5
0
0
p2
0
4
5
p3
4
0
4
p4
0
3
0
c1
4
2
4
c2
0
3
2
c3
4
1
2
Hình 2. M
Mở rộng theo pphía sản phẩm
3.3.
3 Xây dựngg hồ sơ sản ph
hẩm dựa trên
n ma trận đán
nh giá
Tương tự như hồ sơ ngư
ười dùng, hồ sơ sản phẩm lưu
l trữ lại vết tích các đặc ttrưng nội dungg người dùng đã từng sử
dụng
d
sản phẩm
m. Để xây dựnng được hồ sơ
ơ sản phẩm taa cần thực hiệện hai nhiệm vvụ: xác định đđược tập ngườ
ời dùng đã
từ
ừng sử dụng sản phẩm quáá khứ và ước lượng trọng số mỗi đặc trư
ưng nội dung nngười dùng trrong hồ sơ sản
n phẩm [3,
13].
1 Gọi Ux⊆U được xác đinnh theo công thức (10) là tậập người dùng
g i∈U đã sử ddụng sản phẩm
m x∈P. Khi đó
ó, Ux chính
là tập người dùùng cần được lưu lại các giáá trị đặc trưng
g nội dung tron
ng hồ sơ sản pphẩm. Vấn đề còn lại là làm
m thế nào ta
ước
ư lượng đượ
ợc trọng số mỗỗi đặc trưng q∈T đối với mỗ
ỗi hồ sơ sản phẩm x∈P.
∈
|
0
∈ ,
∈
0
∈ ,
(10)
Gọi ListU
User (x, q) làà tập người ddùng i∈Uxcó đặc trưng q∈T được xác định theo côông thức (11). Khi đó,
|L
ListUser(x , q)|
q chính là sốố lần sản phẩm
m x∈P được tập
t người dùn
ng i∈U có đặặc trưng nội ddung q∈T sử dụng
d
trong
quá
q khứ.
,
∈
|
∈ ,
∈
,
|
(11)
ư vấn theo nội dung người ddùng ước lượnng được trọng số txq phản
Dựa trên Ux và ListUserr( x, q) các phhương pháp tư
ánh
á mức độ quuan trọng củaa đặc trưng nộội dung q đối với sản phẩm
m x. Giống như
ư người dùng,, bản thân các
c sản phẩm
cũng
c
đã tồn tạii một phép đáánh giá tự nhiêên của tập ngư
ười dùng đối với
v sản phẩm tthông qua giáá trị đánh giá rix. Do vậy,
chúng
c
tôi đề xuất
x phương phháp trích chọnn đặc trưng nộ
ội dung người dùng có cùngg mức độ đánhh giá với giá trị đánh giá
rix. Để thực hiiện điều này, cchúng tôi tiếnn hành quan sáát trên tập ListtUser(x, q). N
Nếu giá trị |ListtItem(i, s)| vượt quá một
ngưỡng
n
θ nào đó thì trọng số đặc trưng nnội dung người dùng q∈T đối với sản pphẩm x∈P là vxq được tính bằng
b
trung
bình
b
cộng của tất cả các giáá trị đánh giá. Trường hợp |L
ListUser(x, q)| có giá trị bé hơn θ, giá trịị vxq được tính
h bằng tổng
của
c tất cả các giá trị đánh ggiá chia cho θ. Trong thử nghiệm,
n
chúng
g tôi tính toánn được số lượợng trung bình
h của tất cả
sản
s phẩm x∈P được đánh ggiá bởi người ddùng i∈U, sau
u đó chọn θ tư
ương đương vớới 2/3 số lượnng người dùng
g i∈U chứa
đựng
đ
đặc trưngg q∈T đã sử ddụng sản phẩm
m x∈P. Bằng cách
c
này ta có thể hạn chế đđược một số đđặc trưng nội người
n
dùng
ítt quan tâm đếnn sản phẩm nhhưng vẫn đượ
ợc đánh giá với trọng số cao.
|
,
∑∈
|
∑∈
,
ế
,
ế
|
|
,
|
(12)
ợng theo (12) biểu diễn hồ sơ sản phẩm x∈P đã được ttập những ngư
ười dùng i∈U chứa đựng
Giá trị vxq được ước lượ
đặc
đ trưng q∈T sử dụng. Dễ dàng nhận thấấy vxq∈F, tron
ng đó F = { 1, 2, .., g}. Chínnh vì lý do nàyy, ta có thể xe
em mỗi đặc
trưng nội dunng người dùngg đóng vai tròò như một người dùng phụ
ụ bổ sung vàoo tập người dù
dùng. Dựa trên
n nhận xét
này,
n
chúng tôii mở rộng đồ thị hai phía ccủa bài toán tư
t vấn cộng táác đã được m
mở rộng trong Mục 2.2 bằng cách giữ
nguyên
n
tập đỉỉnh ở phía sảnn phẩm là P∪ C và mở rộn
ng phía ngườ
ời dùng thành U∪T. Liên kkết giữa đỉnh sản phẩm
x∈P và đỉnh người
n
dùng i∈U được thiếết lập nếu rix≠ 0. Liên kết giữa
g
đỉnh sảnn phẩm x∈P vvà đỉnh đặc trưng người
dùng
d
q∈T đượ
ợc thiết lập nnếu vxq≠ 0. M a trận đánh giá
g mở rộng ghi
g lại trọng ssố các cạnh (xx, i) và (x, q)) được xác
định
đ
theo công thức (13).
ế
ế
ế ∈ , ∈
∈ , ∈
à
à
∈ , ∈
à
0
0
0
(13)
Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn
nh 1, chọn θ = 2 ta sẽ tính toán được ma
a trận đánh
giá
g mở rộng trrong Bảng 5 vvà đồ thị tư vấấn cộng tác mở
m rộng được thể
t hiện như H
Hình 3. Các ccạnh màu xanh là những
cạnh
c
mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng
g tác.
Đỗ
Đ Thị Liên, Nguuyễn Xuân Anh, N
Nguyễn Duy Phươ
ơng, Từ Minh Phư
ương
435
Bảng 5. Ma trậận đánh giá mở rộng R
u1
u2
u3
t1
t2
t3
t4
p1
5
0
0
2
0
0
2
p2
0
4
5
2
0
2
2
p3
4
0
4
2
2
0
4
p4
0
3
0
1
0
1
0
c1
4
2
4
c2
0
3
2
c3
4
1
2
Hình 3. Mở rộng theo phíaa người dùng
3.4.
3 Xây dựngg mối liên hệ giữa đặc trưn
ng người dùn
ng và đặc trưn
ng sản phẩm
Hồ sơ ngư
ười dùng đượcc xác định theeo (8), hồ sơ sản
s phẩm đượ
ợc xác định theeo (12) được thực hiện dựa
a trên đánh
giá
g tự nhiên củủa người dùngg đối với sản phẩm và thói quen sử dụng
g sản phẩm củủa người dùngg. Rõ ràng, bả
ản thân tập
đặc
đ trưng nội dung
d
người dùùng và tập đặcc trưng nội du
ung sản phẩm cũng tồn tại m
một mối quan hệ tự nhiên nào
n đó giữa
hồ
h sơ người dùùng và hồ sơ ssản phẩm. Ví dụ tại sao trẻ em thích xem
m phim hoạt hhình, nữ tuổi teeen thích xem
m phim tình
cảm,
c
nam tuổii teen thích xeem phim hànhh động…? Chúng tôi cho rằằng khai thác được mối quaan hệ tiềm ẩn
n kể trên sẽ
cải
c thiện đáng kể chất lượngg dự đoán các sản phẩm phù
ù hợp với mỗi người dùng.
Để xác địnnh mối liên hệệ tiềm ẩn giữaa đặc trưng q∈T với đặc trư
ưng s∈C, chúnng tôi xây dựnng hai kiểu qua
an sát khác
nhau.
n
Kiểu quan sát thứ nhấất được tiến hàành từ hồ sơ người
n
dùng đếến các đặc trư
ưng nội dung ssản phẩm. Kiể
ểu quan sát
th
hứ hai được thực
t
hiện ngư
ược lại từ hồ ssơ sản phẩm đến
đ các đặc trư
ưng người dùùng. Vì cả hai kiểu quan sát chỉ nhằm
mục
m đính xác định mối quan
an hệ tiềm ẩn ggiữa cặp đặc trưng
t
q∈T vớ
ới đặc trưng s∈ C nên chúngg tôi tổ hợp kế
ết quả giữa
hai
h kiểu quán sát
s để thu đượ
ợc kết quả cuốối cùng. Phươn
ng pháp cụ thểể được tiến hànnh như sau.
Quan sát từ hồ sơ ngư
ười dùng đến các đặc trưng
g nội dung sả
ản phẩm
ung q∈T đượcc xác định the o công thức ( 14). Gọi UserrAttr(i,s) là
Gọi Uq là tập người dùnng i∈U có đặcc trưng nội du
tập người dùng i∈U có đặcc trưng q∈T đđã đánh giá cáác sản phẩm x∈P chứa đựnng đặc trưng s ∈C được xác
c định theo
công
c
thức (15)). Khi đó, mốii liên hệ giữa đặc trưng q∈T và đặc trưn
ng s∈C được ư
ước lượng theeo công thức (16). Trong
đó,
đ wis là hồ sơ
ơ người dùng i∈U được xácc định theo (8)).
∈
|
∑∈
, |
∑∈
,
|
,
0
,
(14)
∈
|
ế |
0
ế |
(15)
,
,
|
(16)
ượng theo (166) phản ánh mức
m độ ảnh hư
ường của đặc ttrưng s∈C lênn tập người dù
ùng có đặc
Giá trị aqss được ước lư
g đặc trưng
trrưng q∈T. Nếếu số lượng tậập người dùngg i∈U có đặc trưng q∈T đãã đánh giá cácc sản phẩm x∈P chứa đựng
s∈C vượt quá ngưỡng θ thìì aqs được tínhh bằng giá trị trung bình củaa trọng số cácc đặc trưng s ttrong hồ sơ ng
gười dùng.
Trong
T
trường hợp khác, aqss được tính tổnng trọng số cáác đặc trưng s trong hồ sơ người dùng nnhân với 1/θ. Bằng cách
này
n chúng ta có
c thể hạn chhế được các đặc trưng của người dùng hoặc
h
sản phẩm
m ít được ngư
ười dùng sử dụ
ụng nhưng
được
đ
đánh giá với trọng số ccao.
n
dùng
Quan sát từ hồ sơ sản phẩm đến cáác đặc trưng người
m x∈P có đặc trưng nội dun
ng s∈C được xác
x định theo công thức (17). Gọi ItemA
Attr(q, s) là
Gọi Ps là tập sản phẩm
tập sản phẩm có đặc trưng s∈C đã đượcc đánh giá bởii tập người dù
ùng i∈U chứaa đựng đặc trư
ưng q∈T đượ
ợc xác định
th
heo công thứcc (18). Khi đóó, mức độ phùù hợp của tập sản phẩm có đặc
đ trưng s đốối với tập ngư
ười dùng i∈U chứa đựng
đặc
đ trưng q theeo công thức ((18). Trong đóó, vxq là hồ sơ sản phẩm x∈P được xác địnnh theo (12).
∈
|
,
0
(17)
∈
|
0
(18)
MỘ
ỘT MÔ HÌNH ĐỒ
Ồ THỊ CHO HỆ TƯ
T VẤN LAI
436
4
|
∑
∈
, |
∑
,
∈
ế |
,
,
ế |
,
|
(19)
Giá trị bqss được ước lư
ượng theo (199) phản ánh mức
m độ ảnh hư
ưởng của đặcc trưng q∈T lêên tập sản ph
hẩm có đặc
trrưng s∈C. Nếếu số lượng sảản phẩm x∈P có đặc trưng
g s∈C đã đánh
h giá các sản pphẩm i∈U chhứa đựng đặc trưng q∈T
vượt
v
quá ngưỡ
ỡng θ thì bqs đđược tính bằngg giá trị trung bình của trọn
ng số các đặc trưng q trongg hồ sơ sản ph
hẩm. Trong
trrường hợp khhác, bqs được tính tổng trọnng số các đặcc trưng q trong hồ sơ ngườời dùng nhân với 1/θ. Bằng
g cách này
chúng
c
ta có thhể hạn chế được các đặc trư
ưng của ngườ
ời dùng hoặc sản
s phẩm ít đư
ược người dùn
ùng sử dụng nh
hưng được
đánh
đ
giá với trrọng số cao.
Tổng hợp
p giữa các kiểểu quan sát
Như đã trìình bày ở trênn, giá trị aqs đư
ược xác định theo (16) và bqs được xác đđịnh theo (19) đều phản ánh
h thói quen
tự
ự nhiên sử dụụng sản phẩm ccủa tập người dùng có đặc trưng
t
q đối vớ
ới tập sản phẩm
m có đặc trưngg s. Điểm khá
ác biệt duy
nhất
n giữa aqs và
v bqs là kiểu qquan sát dựa vvào hồ sơ ngườ
ời dùng hay hồ
ồ sơ sản phẩm
m. Để dung hòòa giữa hai kiểu quan sát,
chúng
c
tôi chọnn giá trị trungg bình giữa aqss và bqs theo công
c
thức (20)). Trong đó, ggiá trị dqs chỉ đđược thiết lập khi và chỉ
khi
k aqs và bqs có
c giá trị khác 0. Điều này ccó nghĩa, mối quan hệ giữa đặc trưng s∈C và đặc trưngg q∈T được th
hiết lập khi
và
v chỉ khi các sản phẩm có đặc trưng s thhực sự được nh
hiều người dù
ùng quan tâm vvà ngược lại nnhiều người dù
ùng có đặc
trrưng q thực sự
ự quan tâm đếến các sản phẩẩm có đặc trưn
ng s. Điều này
y là hoàn toànn phù hợp với tâm lý chung của người
sử
s dụng sản phhẩm.
ế
0
á
ườ
ư
0 à
0
ợ
á
(20)
mối liên hệ giiữa tập đặc trư
ưng người dùn
ng và tập đặc ttrưng sản phẩm
m, chúng tôi mở
m rộng đồ
Sau khi xáác định được m
th
hị hai phía củủa bài toán tư vvấn cộng tác đđã được trình bày trong Mụ
ục 2.3 bằng cáách bổ sung ccác liên kết giữ
ữa mỗi đặc
trrưng s∈C vớii đặc trưng q∈T. Đồ thị cuốối cùng ta nhận
n được có tập đỉnh là tập nggười dùng U, tập sản phẩm P, tập đặc
trrưng người dùùng T và tập đđặc trưng sản phẩm P. Tập đỉnh của đồ th
hị được chia tthành hai phíaa, một phía là U∪T, phía
còn
c lại là P∪C.
C Tập cạnh của đồ thị bao gồm 4 loại cạạnh: cạnh (i , x)
x nối giữa đỉnnh người dùngg và đỉnh sản phẩm
p
được
đánh
đ
trọng số là rix, cạnh (i , s) nối giữa đỉnh người dù
ùng và đỉnh đặc
đ trưng sản pphẩm được đáánh trọng số là wis, cạnh
(q , x) nối giữaa đỉnh đặc trư
ưng người dùnng và đỉnh sản
n phẩm được đánh trọng sốố là vqx, cạnh ((q , s) nối giữ
ữa đỉnh đặc
trrưng người dùùng và đỉnh đặặc trưng sản pphẩm được đán
nh trọng số là dqs.
ế
ế
ế
ế
0
0
0
0
∈
∈
∈
à
∈
à
à
à
∈
∈
∈
∈
(21)
nh 1, chọn θ = 2 ta sẽ tính toán được ma
a trận đánh
Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn
giá
g mở rộng trrong Bảng 6 vvà đồ thị tư vấấn cộng tác mở
m rộng được thể
t hiện như H
Hình 4. Các ccạnh màu vàng là những
cạnh
c
mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng
g tác.
Bảng 6. Maa trận đánh giá m
mở rộng R
u1
u2
u3
t1
t2
t3
t4
p1
5
0
0
2
0
0
2
p2
0
4
5
2
0
2
2
p3
4
0
4
2
2
0
4
p4
0
3
0
1
0
1
0
c1
4
2
4
2
1
1
4
c2
0
3
2
1
1
1
1
c3
4
1
2
1
1
0
3
Hình 4. Đồồ thị biểu diễn bbài toán tư vấn lai
Ma trận đánh
đ
giá mở rộộng được đề xxuất theo (21)) đã tích hợp đầy
đ đủ các gi á trị đánh giáá của lọc cộng
g tác, hồ sơ
người
n
dùng, hồồ sơ sản phẩm
m, mối liên hệệ giữa hồ sơ người
n
dùng và hồ sơ nội dunng sản phẩm của lọc nội du
ung. Trọng
số
s các đặc trưnng nội dung trrong hồ sơ ngư
ười dùng, hồ sơ sản phẩm và
v mối liên hệệ giữa các đặcc trưng nội dun
ng có cùng
metric
m
với giá trị đánh giá. Chính vì vậy,, các phương pháp tư vấn cộng
c
tác dựa vvào bộ nhớ [115, 16] hoặc các phương
pháp
p
tư vấn cộộng tác dựa trêên mô hình [6, 11, 12] đều có
c thể triển kh
hai trên ma trậận đánh giá mởở rộng. Đây là
à đóng góp
chính
c
của bài báo
b trong xây dựng mô hìnhh hợp nhất giữ
ữa tư vấn cộng
g tác và tư vấnn theo nội dunng.
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
437
IV. CÁC PHƯƠNG PHÁP DỰ ĐOÁN TRÊN ĐỒ THỊ KẾT HỢP
Sau khi dịch chuyển bài toán tư vấn kết hợp về bài toán lọc cộng tác chuẩn, về nguyên tắc ta có thể triển khai bất kỳ
một phương pháp tư vấn cộng tác nào trên ma trận đánh giá mở rộng. Trong khuôn khổ của bài báo này, chúng tôi đề xuất
mở rộng các phương pháp tư vấn cộng tác dựa vào bộ nhớ bằng cách mở rộng các độ tương quan trên trên ma trận đánh
giá mở rộng. Sau đó, chúng tôi xây dựng một độ đo tương tự mới dựa vào các kỹ thuật tìm kiếm trên đồ thị. Kết quả thử
nghiệm trên các bộ dữ liệu thực về phim cho thấy các phương pháp đề xuất cải thiện đáng kể kết quả tư vấn.
4.1. Phương pháp tư vấn kết hợp dựa vào người dùng
Phương pháp tư vấn cộng tác dựa vào người dùng (UserBased) thực hiện ước lượng mức độ tương tự giữa các cặp
người dùng dựa vào các độ đo tương tự để từ đó sinh ra dự đoán các sản phẩm mới phù hợp với người dùng cần được
tư vấn [12, 15]. Hiệu quả của phương pháp UserBased phụ thuộc vào tập giá trị đánh giá R = (rix) được xác định theo
(1). Do tính chất thưa thớt của ma trận đánh giá nên việc xác định mức độ tương tự giữa các cặp người dùng gặp nhiều
hạn chế [14]. Để khắc phục nhược điểm này, chúng tôi tiến hành mở rộng phương pháp tư vấn kết hợp trên ma trận
đánh giá mở rộng R được xác định theo (21). Trong đó, việc ước lượng mức độ tương tự giữa các cặp người dùng
không chỉ thực hiện trên ma trận đánh giá mà được mở rộng cho toàn bộ hồ sơ người dùng. Phương pháp được ký hiệu
là Hybrid-UserBased và tiến hành thông qua bốn bước như dưới đây.
Bước 1. Tính toán mức độ tương tự giữa các cặp người dùng. Tại bước này ta có thể sử dụng các độ đo tương
quan hoặc các độ đo tương tự để tính toán mức độ giống nhau giữa các cặp người dùng [15]. Gọi uij là mức độ tương tự
giữa người dùng i∈U và người dùng j∈U. Khi đó, độ tương quan Pearson giữa người dùng i∈U và người dùng j∈U
được mở rộng trên tập đánh giá người dùng và hồ sơ người dùng theo công thức (22).
∑ ∈ ∩
∑ ∈ ∩
∑ ∈ ∩
∑ ∈ ∩
∑ ∈ ∩
(22)
∑ ∈ ∩
Trong đó,
|
∩
|
∩
|
| ∩
|
|
| ∩
∑
∑
∈ |
∑
|
∑
∈
∈
(23)
∩
∩
∈ ∩
(24)
0
(25)
(26)
(27)
∈ ∩
Bước 2. Xác định tập láng giềng cho người dùng cần tư vấn. Tại bước này ta chỉ cần sắp xếp các giá trị uij theo
thứ tự giảm dần, trong đó i∈U là người dùng cần được tư vấn các sản phẩm x∈P. Sau đó chọn tập K người dùng đầu
tiên làm tập láng giềng của người dùng i [15]. Ký hiệu tập láng giềng của người dùng i∈U là Ki.
Bước 3. Dự đoán quan điểm của người dùng đối với các sản phẩm mới. Phương pháp phổ biến nhất để sinh ra dự
đoán quan điểm của người dùng i∈U cho sản phẩm mới x∈P theo công thức (28)[15].
∑ ∈
∑ ∈
|
(28)
|
Bước 4. Chọn K sản phẩm mới có rix cao nhất tư vấn cho người dùng i.
4.2. Phương pháp tư vấn kết hợp dựa vào sản phẩm
Phương pháp tư vấn cộng tác dựa vào sản phẩm (ItemBased) thực hiện ước lượng mức độ tương tự giữa các cặp
sản phẩm dựa vào các độ đo tương tự để từ đó sinh ra dự đoán các sản phẩm mới phù hợp với người dùng cần được tư
vấn [1, 2, 16]. Hiệu quả của phương pháp ItemBased phụ thuộc vào tập giá trị đánh giá người dùng R = (rix) được xác
định theo (1). Do tính chất thưa thớt của ma trận đánh giá nên việc xác định mức độ tương tự giữa các cặp sản phẩm
gặp nhiều hạn chế. Để khắc phục nhược điểm này, chúng tôi tiến hành mở rộng phương pháp tư vấn kết hợp trên ma
trận đánh giá mở rộng R được xác định theo (21). Trong đó, việc ước lượng mức độ tương tự giữa các cặp sản phẩm
không chỉ thực trên ma trận đánh giá mà được mở rộng cho toàn bộ hồ sơ sản phẩm. Phương pháp được viết tắt là
Hybrid-ItemBased và tiến hành thông qua bốn bước như dưới đây.
Bước 1. Tính toán mức độ tương tự giữa các cặp sản phẩm. Tại bước này ta có thể sử dụng các độ đo tương quan
hoặc các độ đo tương tự để tính toán mức độ giống nhau giữa các cặp sản phẩm [16]. Gọi pxy là mức độ tương tự giữa
sản phẩm x∈P và sản phẩm y∈P. Khi đó, độ tương quan Pearson giữa sản phẩm x∈P và sản phẩm y∈P được mở rộng
trên tập đánh giá người dùng và hồ sơ sản phẩm theo công thức (29).
∑∈
∑∈
∩
∩
∑∈
∩
∑ ∈
∑ ∈
∩
∩
∑ ∈
(29)
∩
MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI
438
Trong đó,
|
|
|
|
∩
|
∩
|
∑∈
∑∈
∈ |
∑
∩
∩
|
|
∑
(30)
∩
∩
∈
∩
∈
(31)
0
(32)
(33)
(34)
∩
Bước 2. Xác định tập láng giềng cho sản phẩm cần tư vấn. Tại bước này ta chỉ cần sắp xếp các giá trị pxy theo thứ
tự giảm dần. Sau đó chọn tập K sản phẩm đầu tiên làm tập láng giềng của sản phẩm x [16]. Ký hiệu tập láng giềng của
sản phẩm x∈P là Kx.
Bước 3. Dự đoán quan điểm của người dùng đối với các sản phẩm mới. Phương pháp phổ biến để sinh ra dự đoán
quan điểm của người dùng i∈U cho sản phẩm mới x∈P theo công thức (35)[16].
∑ ∈
∑ ∈
|
(35)
|
Bước 4. Chọn K sản phẩm mới có rix cao nhất tư vấn cho người dùng i.
4.3. Độ tương tự giữa các cặp người dùng dựa trên đồ thị
Phương pháp Hybrid-UserBased được đề xuất trong Mục 3.1 có thể thực hiện dễ dàng trên đồ thị bằng cách xem
xét tất cả các đường đi độ dài 2 từ đỉnh người dùng đến đỉnh người dùng trên đồ thị [5, 7]. Ví dụ để xác định mức độ
tương tự giữa người dùng u1 và u2 trên đồ thị trong Hình 4 ta dựa vào các đường đi : u1-p1-u2, u1-c1-u2, u1-c3-u2. Trọng
số của mỗi đường đi được tính bằng tích của trọng số các cạnh. Tổng trọng số tất cả các đường đi từ đỉnh i∈U đến đỉnh
j∈U chính là độ tương tự giữa hai người dùng này. K người dùng có tổng trọng số các đường đi từ đỉnh i∈U đến đỉnh
j∈U có trọng số lớn nhất chính là tập láng giềng của người dùng i. Sau đó sử dụng tập láng giềng để sinh ra dự đoán
cho người dùng i.
Một trong những thách thức lớn nhất của hệ tư vấn là vấn đề dữ liệu thưa [1, 3]. Vấn đề dữ liệu thưa xảy ra khi các
giá trị đánh giá rix≠0 rất ít (dưới 1%). Số lượng các cạnh (i, x) thấp làm cho việc xác định các cạnh (i, s) cũng thấp.
Điều này làm cho kết quả dự đoán của các phương pháp trên đạt kết quả không cao. Để hạn chế điều này, chúng tôi
tiến hành mở rộng độ dài đường đi từ đỉnh người dùng đến đỉnh người dùng để tận dụng mối liên hệ gián tiếp giữa các
cặp người dùng và các cặp đặc trưng nội dung khác nhau. Các đường đi có thể là các cạnh đánh giá (i, x), cạnh (i, s),
cạnh (q, x) hoặc cạnh (q, s). Ví dụ để xác định mức độ tương tự giữa u2 và u3 với đồ thị biểu diễn bài toán tư vấn kết
hợp trong Hình 4, ta có thể sử dụng các đường đi u2-p1-u1-p3-u3, u2-p4-t3-p2-u3, u2-c1-t4-p3-u3. Điều này là hoàn toàn hợp
lý vì u2 thích p1, p1 được u1 thích, u1 thích p3 , p3 được u3 thích nên gián tiếp u2 tương tự với u3 ở một mức độ nào đó.
Hoặc u2 thích p4, p4 được người dùng có đặc trưng t3 thích, người dùng có đặc trưng t3 thích p2, u3 thích t2 nên gián tiếp
u2 tương tự với u3 ở một mức độ nào đó. Hoặc u2 thích đặc trưng c1, c1 phù hợp với tập người dùng có đặc trưng t4, t4
phù hợp với sản phẩm p3, u3 thích p3 nên cũng gián tiếp u2 tương tự với u3 ở một mức độ nào đó.
Vì đồ thị tư vấn kết hợp là đồ thị hai phía nên các đường đi từ đỉnh người dùng đến đỉnh người dùng luôn có độ
dài chẵn (2, 4, 6, 8) [7]. Trọng số của mỗi đường đi được tính bằng tích các trọng số các cạnh nên đường đi qua các
cạnh có trọng số cao vẫn được đánh giá cao, đường đi qua các cạnh có trọng số thập vẫn được đánh giá thấp. Để ưu
tiên cho các đường đi ngắn (độ dài 2) chúng tôi sử dụng tham số α (0<α<1) để đánh thấp trọng số các đường đi có độ
dài cao. Cụ thể, phương pháp ước lượng tổng trọng số các đường đi độ dài L từ đỉnh người dùng đến đỉnh người dùng
được xác định theo công thức (36) [7].
.
. .
.
ế
ế
2
4, 6, 8, …
(36)
Trong đó, L là độ dài đường đi, R là ma trận đánh giá mở rộng được xác định theo (21), RT là ma trận chuyển vị
của R. Giá trị L chẵn được xác định khi tất cả ≠0 [7]. Tổng trọng số các đường đi độ dài L từ đỉnh i∈U đến đỉnh j∈U
là mức độ tương tự giữa hai người dùng này. K người dùng j∈U có
lớn nhất chính là tập láng giềng của người dùng
i∈U. Dựa trên nhận xét này, chúng tôi điều chỉnh Bước 1 của thuật toán Hybrid-UserBased trong Mục 3.1 thành thuật
toán Hybrid-UserBased-Graph trong Hình 5.
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
439
Thuật toán Hybrid-UserBased-Graph:
Đầu vào:
- Ma trận đánh giá mở rộng R= (rix) biểu diễn đồ thị kết hợp được xác định theo (21).
- i∈U là người dùng cần được tư vấn.
- K là số lượng người dùng của tập láng giềng.
Đầu ra:
- Dự đoán x: rix| x∈P\Pi( quan điểm của người dùng i đối với các sản phẩm mới x∈P).
Các bước tiến hành:
Bước 1. Tính toán mức độ tương tự giữa các cặp người dùng trên đồ thị kết hợp:
L ⇐2;//Thiết lập độ dài đường đi ban đầu L=2
Repeat
ế
2
.
ế
4, 6, 8, …
. . .
L⇐L + 2; //Tăng độ dài đường đi.
Until ( ≠0với mọi j∈(U \ i));
Bước 2. Xác định tập láng giềng cho người dùng i∈U.
• Sắp xếp ≠0 theo thứ tự giảm dần (i≠j).
• Chọn K người dùng j∈U đầu tiên làm tập láng giềng của người dùng i (Ký hiệu
tập láng giềng của người dùng i∈U là Ki).
Bước 3. Dự đoán quan điểm của người dùng i đối với các sản phẩmx∈P\Pi.
∑∈
;
|
|
Bước 4. Chọn K sản phẩm có rixcao nhất tư vấn cho người dùng i.
Hình 5. Thuật toán Hybrid-UserBased-Graph
4.4. Độ tương tự giữa các cặp sản phẩm dựa trên đồ thị
Phương pháp Hybrid-ItemBased được đề xuất trong Mục 3.2 cũng có thể thực hiện dễ dàng trên đồ thị bằng cách
xem xét tất cả các đường đi độ dài 2 từ đỉnh sản phẩm đến đỉnh sản phẩm trên đồ thị [7]. Ví dụ để xác định mức độ
tương tự giữa sản phẩm p1 và p3 trên đồ thị trong Hình 4 ta dựa vào các đường đi: p1-u1-p3, p1-t1-p3, p1-t2-p3. Trọng số
của mỗi đường đi được tính bằng tích của trọng số các cạnh. Tổng trọng số tất cả các đường đi từ đỉnh x∈P đến đỉnh
y∈P chính là độ tương tự giữa hai sản phẩm. K sản phẩm có tổng trọng số các đường đi từ đỉnh x∈P đến đỉnh y∈P có
trọng số lớn nhất chính là tập láng giềng của sản phẩm x. Sau đó sử dụng tập láng giềng của sản phẩm để dự đoán các
sản phẩm phù hợp nhất đối với người dùng i [7].
Để hạn chế ảnh hưởng của vấn đề dữ liệu thưa, chúng tôi tiến hành mở rộng độ dài đường đi từ sản phẩm đến đỉnh
sản phẩm để tận dụng mối liên hệ gián tiếp giữa các cặp sản phẩm và các cặp đặc trưng nội dung. Các đường đi có thể
là các cạnh đánh giá (i, x), cạnh (i, s), cạnh (q, x) hoặc cạnh (q, s). Ví dụ để xác định mức độ tương tự giữa p1 và p2 với
đồ thị biểu diễn bài toán tư vấn kết hợp trong Hình 4, ta có thể sử dụng các đường đi p1-u1-p3-u2-p2, p1-u2-p4-t1-p2, p1t2-c3-u3-p2. Tính hợp lý của phép suy diễn này cũng được lý giải tương tự như trường hợp tính toán mức độ tương tự
giữa các cặp người dùng.
Vì đồ thị tư vấn kết hợp là đồ thị hai phía nên các đường đi từ đỉnh sản phẩm đến đỉnh sản phẩm luôn có độ dài
chẵn (2, 4, 6, 8) [5, 7]. Trọng số của mỗi đường đi được tính bằng tích các trọng số các cạnh nên đường đi qua các cạnh
có trọng số cao vẫn được đánh giá cao, đường đi qua các cạnh có trọng số thấp vẫn được đánh giá thấp. Để ưu tiên cho
các đường đi ngắn (độ dài 2) chúng tôi sử dụng tham số α (0<α<1) để đánh thấp trọng số các đường đi có độ dài cao.
Cụ thể, phương pháp ước lượng tổng trọng số các đường đi độ dài L từ đỉnh sản phẩm đến đến đỉnh sản phẩm được xác
định theo công thức (37) [7].
.
.
.
.
ế
ế
2
4, 6, 8, …
(37)
Trong đó, L là độ dài đường đi, R là ma trận đánh giá mở rộng được xác định theo (20), RT là ma trận chuyển vị
của R. Giá trị L chẵn được xác định khi tất cả
≠0 [7]. Tổng trọng số các đường đi độ dài L từ đỉnh x∈P đến đỉnh
y∈P là mức độ tương tự giữa hai người dùng này. K sản phẩm y∈P có
lớn nhất chính là tập láng giềng của sản
phẩm x∈P. Dựa trên nhận xét này, chúng tôi điều chính Bước 1 của thuật toán Hybrid-ItemBased trong Mục 3.2 thành
thuật toán Hybrid-ItemBased-Graph trong Hình 6.
MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI
440
Thuật toán Hybrid-ItemBased-Graph:
Đầu vào:
- Ma trận đánh giá mở rộng R= (rix) biểu diễn đồ thị kết hợp được xác định theo (21).
- i∈U là người dùng cần được tư vấn.
- K là số lượng sản phẩm của tập láng giềng.
Đầu ra:
- Dự đoán x: rix| x∈P\Pi (quan điểm của người dùng i đối với các sản phẩm mới x∈P).
Các bước tiến hành:
Bước 1. Tính toán mức độ tương tự giữa các cặp sản phẩm trên đồ thị kết hợp:
L ⇐2;//Thiết lập độ dài đường đi ban đầu L=2
Repeat
.
ế
2
ế
4, 6, 8, …
. . .
L⇐L + 2; //Tăng độ dài đường đi.
Until ( ≠0với mọi y∈(P \ x));
Bước 2. Xác định tập láng giềng cho sản phẩm x∈P.
• Sắp xếp ≠0 theo thứ tự giảm dần (x≠y).
• Chọn K sản phẩm y∈P đầu tiên làm tập láng giềng của sản phẩm x (Ký hiệu tập
láng giềng của sản phẩm x∈P là Kx).
Bước 3. Dự đoán mức độ phù hợp của người dùng i đối với các sản phẩm x∈P\Pi.
∑ ∈
;
|
|
Bước 4. Chọn K sản phẩm có rix cao nhất tư vấn cho người dùng i.
Hình 6. Thuật toán Hybrid-ItemBased-Graph
V. THỬ NGHIỆM VÀ GIÁ
Để đánh giá hiệu quả của các phương pháp tư vấn kết hợp đề xuất, chúng tôi tiến hành thử nghiệm trên bộ dữ
liệu thực về phim [24]. Phương pháp trình bày ở trên được đánh giá và so sánh với các phương pháp khác theo thủ tục
mô tả dưới đây.
5.1. Dữ liệu thử nghiệm
Thuật toán lọc kết hợp được thử nghiệm trên bộ dữ liệu MovieLens của nhóm nghiên cứu GroupLens thuộc
Trường Đại học Minnesota [24]. Bộ dữ liệu gồm 100.000 đánh giá của 943 người dùng cho 1682 phim. Giá trị đánh
giá được thực hiện từ 1 đến 5. Mức độ thưa thớt dữ liệu đánh giá là 99.1%. Tập đặc trưng nội dung sản phẩm được
chọn là 18 thể loại phim khác nhau [18]. Tập đặc trưng nội dung người dùng cũng được cung cấp kèm theo tập đặc
trưng nội dung phim [24]. Chọn giá trị θ = 15 theo phương pháp được mô tả ở trên để xác định wis, vqx, dqs theo công
thức (8), (12), và (16) theo thứ tự. Chọn α=0.8 để xác định trọng số đường đi cho các công thức (36), (37).
5.2. Phương pháp thử nghiệm
Trước tiên, toàn bộ dữ liệu thử nghiệm được chia thành hai phần, một phần Utr được sử dụng làm dữ liệu huấn
luyện, phần còn lại Ute được sử dụng để kiểm tra. Tập Utr chứa 75% đánh giá và tập Ute chứa 25% đánh giá. Dữ liệu
huấn luyện được sử dụng để xây dựng mô hình theo thuật toán mô tả ở trên. Với mỗi người dùng i thuộc tập dữ liệu
kiểm tra, các đánh giá (đã có) của người dùng được chia làm hai phần Oi và Pi. Oi được coi là đã biết, trong khi đó Pi là
đánh giá cần dự đoán từ dữ liệu huấn luyện và Oi[8, 14].
Sai số dự đoán MAEu với mỗi khách hàng u thuộc tập dữ liệu kiểm tra được tính bằng trung cộng sai số tuyệt đối
giữa giá trị dự đoán và giá trị thực đối với tất cả mặt hàng thuộc tập Pu.
|
|
∑
∈
| ̂
|
(38)
Sai số dự đoán trên toàn tập dữ liệu kiểm tra được tính bằng trung bình cộng sai số dự đoán cho mỗi khách hàng
thuộc Ute.Giá trị MAE nhỏ thì phương pháp dự đoán có độ chính xác cao [8, 14].
∑ ∈
5.3. So sánh và đánh giá
|
|
(39)
Các phương pháp tư vấn kết hợp Hybrid-UserBased, Hybrid-ItemBased, Hybrid-UserBased-Graph, HybridItemBased-Graph được trình bày trong mục 3.1, 3.2, 3.3 và 3.4 được so sánh với những phương pháp lọc cộng tác sau:
-
Phương pháp CF-UserBased sử dụng độ tương quan Pearson. Đây là phương pháp tư vấn cộng tác chuẩn dựa
vào người dùng chỉ thực hiện dự đoán dựa trên tập giá trị đánh người dùng[15].
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
-
441
Phương pháp CF-ItemBased sử dụng độ tương quan Pearson. Đây là phương pháp lọc cộng tác chuẩn dựa vào
sản phẩm chỉ thực hiện dự đoán dựa trên tập giá trị đánh người dùng[16].
Phương pháp thử nghiệm được thực hiện chọn ngẫu nhiên 300, 600, 900 người dùng trong tập MovieLens làm dữ
liệu huấn luyện. Chọn ngẫu nhiên 100, 200, 300 người dùng trong số còn lại để làm tập kiểm tra. Giá trị MAE trong
Bảng 7 và Bảng 8 được ước lượng từ trung bình của 10 lần thử nghiệm ngẫu nhiên.
Kết quả trong Bảng 7 cho thấy phương pháp lọc dựa vào người dùng thuần túy CF-UserBased cho lại giá trị MAE
lớn nhất so với các phương pháp còn lại. Điều này có thể lý giải hạn chế của phương pháp lọc cộng tác khi quá trình
huấn luyện chỉ dựa vào tập rất nhỏ các giá trị rix≠0. Khi kích thước tập dữ liệu huấn luyện lớn kết quả dự đoán phương
pháp dần được cải thiện. Cụ thể giá trị MAE trên tập dữ liệu gồm 300, 600, 900 người dùng lần lượt là (0.856, 0.834,
0.838), (0.794, 0.775, 0.764), (0.778, 0.745, 0.748) theo thứ tự. Kích cỡ tập láng giềng lớn thực hiện thiếu ổn định. Tập láng
giềng lớn không tỉ lệ thuận với kết quả dự đoán. Kết quả này hoàn toàn phù hợp với những nghiên cứu trước đây.
Phương pháp Hybrid-UserBased cho lại giá trị MAE thấp hơn nhiều so với phương pháp CF-UserBased. Cụ thể
với tập láng giềng K=10 và kích thước tập dữ liệu huấn luyện gồm 300, 600, 900 người dùng thì phương pháp cho lại
giá trị MAE lần lượt là 0.642, 0.611, 0.607 so với 0.856, 0.794, 0.788 của phương pháp CF-UserBased; với K=20 giá
trị MAE lần lượt là 0.586, 0.597, 0.611 so với 0.834, 0.775, 0.745 của phương pháp CF-UserBased;; với K=30 giá trị
MAE lần lượt là 0.513, 0.553, 0.609 so với 0.838, 0.764, 0.748 của phương pháp CF-UserBased. Số lượng người dùng
trong tập láng giềng lớn kết quả dự đoán cũng thực hiện ổn định hơn. Điều này có thể giải thích phương pháp HybridUserBased tính toán được mức độ tương tự giữa các cặp người dùng chính xác hơn vì phương pháp được thực hiện trên
toàn bộ tập dữ liệu đánh giá và hồ sơ người dùng. Chính vì lý do đó phương pháp xác định được tập láng giềng của
người dùng hiện thời tốt hơn để đưa ra kết quả dự đoán.
Phương pháp Hybrid-UserBased-Graph cho lại giá trị MAE thấp nhất so với tất cả các phương pháp còn lại. Giá trị
MAE trên các tập dữ liệu huấn luyện và tập láng giềng dao động trong khoảng 0.515≤MAE≤0.548. Phương pháp cho lại
kết quả khá ổn định trên các tập tập dữ liệu và tập láng giềng có kích cỡ khác nhau. Điều này có thể khẳng định phương
pháp xác định độ tương tự dựa trên tập các đường đi từ đỉnh người dùng đến đỉnh người dùng là hoàn toàn tin cậy. Độ
tương tự giữa các cặp người dùng trên đồ thị đã tích hợp được tất cả các mối quan hệ giữa người dùng và sản phẩm, người
dùng và đặc trưng nội dung sản phẩm, sản phẩm và đặc trưng người dùng, đặc trưng sản phẩm và đặc trưng người dùng.
Bảng 7. Giá trị MAE của các phương pháp tư vấn dựa vào người dùng
Kích thước tập dữ liệu huấn luyện
300 người dùng
600 người dùng
900 người dùng
Phương pháp
CF-UserBased
Hybrid-UserBased
Hybrid-UserBased-Graph
Hybrid-CF-UserBased
Hybrid-UserBased
Hybrid-UserBased-Graph
CF-UserBased
Hybrid-UserBased
Hybrid-UserBased-Graph
Kích thước của tập láng giềng
10
20
30
0.856
0.834
0.838
0.642
0.586
0.513
0.521
0.518
0.512
0.794
0.775
0.764
0.611
0.597
0.553
0.515
0.515
0.537
0.788
0.745
0.748
0.607
0.611
0.609
0.548
0.519
0.517
Giá trị MAE trong Bảng 8 của các phương pháp lọc dựa vào sản phẩm cũng có diễn biến tương tự như phương
pháp lọc dựa vào người dùng. Giá trị MAE của phương pháp lọc kết hợp Hybrid-ItemBased nhỏ hơn nhiều so với
phương pháp CF-ItemBased. Lý do để điều này xảy ra chỉ có thể lý giải phương pháp tính toán mức độtương tựgiữa
các cặp sản phẩm được thực hiện trên tập giá trị đánh giá và hồ sơ sản phẩm thực hiện chính xác hơn các phép đo chỉ
dựa vào tập giá trị đánh giá. Giá trị MAE của phương pháp Hybrid-ItemBased-Graph thấp hơn đáng kể so với phương
pháp Hybrid-ItemBased. Điều này cũng chỉ có thể giải thích độ tương tự giữa các sản phẩm dựa trên đồ thị đã kết hợp
được tất cả các mối quan hệ gián tiếp giữa người dùng, sản phẩm, hồ sơ người dùng và hồ sơ sản phẩm.
Bảng 8. Giá trị MAE của các phương pháp tư vấn dựa vào sản phẩm
Kích thước tập dữ liệu huấn luyện
300 người dùng
600 người dùng
900 người dùng
Phương pháp
CF-ItemBased
Hybrid-ItemBased
Hybrid-ItemBased -Graph
CF-ItemBased
Hybrid-ItemBased
Hibrid-ItemBased -Graph
CF-ItemBased
Hybrid-ItemBased
Hybrid-ItemBased -Graph
Kích thước của tập láng giềng
5
10
20
0.843
0.837
0.835
0.622
0.622
0.607
0.612
0.589
0.571
0.814
0.816
0.844
0.651
0.637
0.613
0.537
0.525
0.517
0.793
0.786
0.743
0.568
0.587
0.543
0.548
0.519
0.511
MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI
442
VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Bài báo đã đề xuất một mô hình hợp nhất giữa phương pháp tư vấn cộng tác và tư vấn the nội dung. Mô hình được
xây dựng bằng cách dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng tác thuần túy để tận dụng những ưu
điểm của phương pháp này. Phương pháp dịch chuyển được tiến hành bằng cách xây dựng hồ sơ người dùng của lọc
nội dung dựa trên đánh giá tự nhiên của người dùng đối với các sản phẩm. Sau đó, thiết lập mối quan hệ trực tiếp giữa
người dùng và từng đặc trưng nội dung sản phẩm. Bằng cách này ta mở rộng được ma trận đánh giá của lọc cộng tác về
phía các sản phẩm. Tiếp đến, quá trình xây dựng hồ sơ sản phẩm cũng được thực hiện trên thói quen sử dụng sản phẩm
một cách tự nhiên của người dùng đối với các sản phẩm. Dựa trên hồ sơ sản phẩm, chúng tôi thiết lập mối quan hệ trực
tiếp giữa sản phẩm và mỗi đặc trưng nội dung người dùng. Bằng cách này ta mở rộng được ma trận đánh giá của lọc
cộng tác về phía người dùng. Cuối cùng, chúng tôi tìm cách xác định mối quan hệ tiềm ẩn giữa mỗi đặc trưng người
dùng với các đặc trưng sản phẩm dựa trên hồ sơ người dùng và hồ sơ sản phẩm. Mô hình cuối cùng nhận được là mở
rộng của mô hình tư vấn cộng tác cơ bản.
Sau khi thu gọn về bài toán lọc cộng tác, ma trận đánh giá mở rộng được đề xuất trong bài báo đã tích hợp đầy đủ
các giá trị đánh giá của lọc cộng tác, hồ sơ người dùng, hồ sơ sản phẩm, mối liên hệ giữa hồ sơ người dùng và hồ sơ
nội dung sản phẩm của lọc nội dung. Trọng số các đặc trưng nội dung trong hồ sơ người dùng, hồ sơ sản phẩm và mối
liên hệ giữa các đặc trưng nội dung có cùng metric với giá trị đánh giá. Chính vì vậy, các phương pháp tư vấn cộng tác
dựa vào bộ nhớ hoặc các phương pháp tư vấn cộng tác dựa trên mô hình đều có thể triển khai trên ma trận đánh giá mở
rộng. Để tận dụng ưu thế của mô hình đồ thị, chúng tôi đề xuất xây dựng một độ tương quan khai thác gián tiếp các
mối quan hệ giữa người dùng, sản phẩm, đặc trưng người dùng, đặc trưng sản phẩm để nâng cao kết quả dự đoán. Kết
quả thử nghiệm các phương pháp tư vấn kết hợp đề xuất cho thấy chất lượng tư vấn được cải thiện đáng kể so với các
phương pháp tư vấn cơ bản. Chúng tôi tin tưởng rằng, mô hình cũng sẽ cho lại kết quả tốt đối với các phương pháp tư
vấn dựa trên mô hình. Những kết quả này sẽ được trình bày trong những nghiên cứu tiếp theo của bài báo.
VII. TÀI LIỆU THAM KHẢO
1.
2.
3.
4.
5.
6.
7.
8.
9.
Su X., Khoshgoftaar T. M., “A Survey of Collaborative Filtering Techniques.,”. Advances in Artificial
Intelligence ,2009, pp.1-20.
Adomavicius G., Tuzhilin A., “Toward the Next Generation of Recommender Systems: A Survey of the State-ofthe-Art and Possible Extensions”, IEEE Transactions On Knowledge And Data Engineering, vol. 17, No. 6, 2005.
Robin D. Burke, “Hybrid Recommender Systems: Survey and Experiments”. User Model. User-Adapt.
Interact. 12(4): 331-370 (2002).
M. D. Ekstrand, J. T. Riedl and J. A. Konstan, “Collaborative Filtering Recommender System”. Foundations and
Trends in Human–Computer Interaction, Vol 4, No2, 2010, pp 81:173.
Nguyen Duy Phuong, Le Quang Thang, Tu Minh Phuong, “A Graph-Based Method for Combining Collaborative
and Content-Based Filtering. PRICAI 2008: 859-869.
Nguyen Duy Phuong, Tu Minh Phuong, “Collaborative Filtering by Multi-task Learning”, RIVF 2008, pp: 227232.
Do Thi Lien, Nguyen Duy Phuong, “Collaborative Filtering with a Graph-based Similarity Measure”.
ComManTel, 2014, pp. 251-256.
Asela Gunawardana, Guy Shani, “A Survey of Accuracy Evaluation Metrics of Recommendation Tasks. Journal of
Machine Learning Research 10: 2935-2962 (2009).
Asela Gunawardana, Christopher Meek, “ A unified approach to building hybrid recommender systems”. RecSys
2009: 117-124.
10. Robin D. Burke, Fatemeh Vahedian, Bamshad Mobasher, “Hybrid Recommendation in Heterogeneous
Networks”. UMAP 2014: 49-60.
11. J. Wang, A. P. de Vries, and M. J. T. Reinders., “Unifying user-based and item-based collaborative filtering
approaches by similarity fusion.,”. In Proceedings of the 29th annual international ACM SIGIR conference on
Research and development in information retrieval (SIGIR '06). ACM, New York, NY, USA, 501-508.
12. Raghavan, S., Gunasekar, S., Ghosh, J. “Review quality aware collaborative filtering”. In Proceedings of the sixth
ACM conference on Recommender systems, pp. 123–130. ACM(2012).
13. Pazzani, M. J. “A framework for collaborative, content-based and demographic filtering”, Artificial Intelligence
Review 13(5-6), 393–408 (1999).
14. Herlocker J. L., Konstan J. A., Terveen L. G., and Riedl J. T., “Evaluating Collaborative Filtering Recommender
Systems”, ACM Trans. Information Systems, vol. 22, No. 1 (2004), pp. 5-53.
15. Breese J. S., Heckerman D., and Kadie C., “Empirical analysis of Predictive Algorithms for Collaborative
Filtering”, In Proc. of 14th Conf. on Uncertainty in Artificial (1998).
16. Sarwar B., Karypis G., Konstan J., and Riedl J., “Item-Based Collaborative Filtering Recommendation
Algorithms”, Proc. 10th Int’l WWW Conf (2001).
Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương
443
17. Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., Sartin, M. “Combining content-based and
collaborative filters in an online newspaper”. In: Proceedings of ACM SIGIR workshop on recommender systems,
vol. 60. Citeseer (1999).
18. Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., & Sartin, M. : Combining contentbased and
collaborative fillters in an online newspaper. Proceedings of ACM SIGIR Workshop on Recommender
Systems.(1999).
19. Basu, C., Hirsh, H., And Cohen, W.: Recommendation as classification: Using social and content-based
information in recommendation. In Proceedings of the 15th National Conference on Artificial Intelligence, 714–
720. (1998).
20. Popescul A., Ungar L.H., Pennock D.M., and Lawrence S.: Probabilistic Models for Unified Collaborative and
Content-Based Eecommendation in Sparse-Data Environments, Proc. 17th Conf. Uncertainty in Artificial
Intelligence, (2001).
21. Balisico J., Hofman T.: Unifying collaborative and content-based filtering. In Proceedings. of Int. Conf. on
Machine learning (ICML-04) (2004).
22. Crammer, K., and Singer, Y: Pranking with ranking. Advances in Neural Information Processing Systems 14 pp.
641-647. (2002).
23. Aggarwal C.C., Wolf J.L., Wu K.L., and Yu P.S.: Horting Hatches an Egg: A New Graph-Theoretic Approach
to Collaborative Filtering, Proc. Fifth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining,
Aug. (1999).
24. http://www.grouplens.org/.
A GRAPH-BASED MODEL FOR HIBRID RECOMMENDER SYSTEM
Do Thi Lien, Nguyen Xuan Anh, Nguyen Duy Phuong, Tu Minh Phuong
Abstract - Recommender systems are the capable systems of providing essentialinformation and removing unessentialinformation
for Internet users. The recommender systems are built based on two main information filtering techniques: Collaborative filtering
and content-based filtering. Each method exploits particular aspects related to content features or product usage habit of users in
the past to predict a brief list of the most suitable products with each user. In this paper, we propose a new unify method between
collaborative filtering recommendation and content-based filtering recommendation based on graph model. The model allows us to
shift hybrid filtering recommender problem to collaborative filtering recommender problem, then build new similar measures based
on graph to determine similarities between two users or two items, these similar measures are used to predict suitable products for
users in the system. The experimental results on real data sets show that the proposed methods achieve superior performance
compared to baseline methods.
Keywords - Collaborative Filtering Recommendation, Content-based Filtering
Recommendation System, Item-Based Recommendation, User-Based Recommendation.
Recommendation,
Hybrid
Filtering