HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
ĐỖ THỊ LIÊN
NGHIÊN CỨU, PHÁT TRIỂN PHƯƠNG PHÁP
LỌC CỘNG TÁC DỰA VÀO BỘ NHỚ
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.01.04
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: TS. Nguyễn Duy Phương
Phản biện 1: ……………………………………………………………………………
Phản biện 2: …………………………………………………………………………..
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ
Bưu chính Viễn thông
Vào lúc:
....... giờ ....... ngày ....... tháng ....... .. năm ...............
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1
MỞ ĐẦU
1. Đặt vấn đề
Lọc thông tin (Information Filtering là lĩnh v c nghi n c u các uá trình lọc b
nh ng thông tin không thích hợ và cung cấ thông tin thích hợ đ n với m i người d ng.
Lọc thông tin được xem là hương há hiệu uả hạn ch tình trạng uá tải thông tin được
quan tâm nhiều nhất hiện nay. Các hương há lọc thông tin đóng vai trò uan trọng đối
với các thống thương mại điện tử, đặc biệt là hệ tư vấn (Recommender System .
Hệ tư vấn (Recommender System là hệ thống có khả năng t động hân tích, hân
loại, l a chọn và cung cấ cho người d ng nh ng thông tin, hàng hóa hay dịch vụ mà họ
uan tâm. Hệ tư vấn được xem như một bi n thể điển hình có vai trò uan trọng trong lọc
thông tin. Nhiều hệ tư vấn đã được thương mại hóa và triển khai thành công, ti u biểu là hệ
tư vấn của các hãng Amazon.com, Netflix.com, Procter & Gamble.
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 theo nội
dung (Content-Based Filtering và lọc cộng tác (Collaborative Filtering . Lọc theo nội
dung khai thác nh ng khía cạnh li n uan đ n các đặc trưng nội dung thông tin sản hẩm
người d ng đã từng sử dụng hay truy nhậ trong uá kh để tạo n n tư vấn. Lọc theo nội
dung cho lại k t uả khá tốt tr n các dạng thông tin được biểu diễn bằng các đặc trưng nội
dung, nhưng gặ
hải khó khăn tr n các dạng thông tin đa hương tiện (hình ảnh, âm
thanh, dịch vụ . Trái lại, lọc cộng tác khai thác nh ng khía cạnh li n uan đ n thói uen sử
dụng sản hẩm của cộng đồng người d ng có c ng sở thích để tạo n n tư vấn. 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 hải biểu diễn dưới dạng văn bản.
Lọc cộng tác cho hệ tư vấn được ti
cận theo hai hương há 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 uan trọng trong hai hương há
ti
cận là hương há xây d ng mô hình huấn luyện và mô hình d đoán. 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ậ 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 á dụng rộng rãi hơn
do tính hiệu uả, đơn giản và có độ chính xác khá cao.
2
Lọc cộng tác d a vào bộ nhớ được th c hiện theo hai hương há 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 hẩm (ItemBased Collaborative Filtering . Hiệu uả của các hương há lọc d a vào bộ nhớ hụ
thuộc vào độ đo tương t gi a các cặ người d ng hoặc sản hẩm. Trong uá trình nghi n
c u và ng dụng, nhiều nghi n c u đã được đề xuất để cải thiện các độ đo tương t , đặc
biệt trong trường hợ d liệu thưa. Mặc d đã có nhiều nghi n c u nhắm tới nội dung này,
nhưng đây vẫn là nh ng vấn đề nghi n c u mở, có tính thời s và thu hút s
ua tâm của
cộng đồng nghi n c u.
Đề tài “Nghiên cứu, phát triển phương pháp lọc cộng tác dựa vào bộ nhớ” được
th c hiện trong khuôn khổ luận văn thạc sĩ chuy n ngành “Truyền d liệu và mạng máy
tính” nhằm gó
hần giải uy t một số vấn đề còn tồn tại của lọc cộng tác d a vào bộ
nhớ.
2. Mục tiêu của luận văn
Mục ti u của luận văn là nghi n c u á dụng, cải ti n hương há lọc cộng tác
d a tr n bộ nhớ nhằm cải thiện độ chính xác k t uả d đoán cho các hệ tư vấn. Đặc biệt,
nghi n c u tậ trung vào việc nâng cao k t uả d đoán nhu cầu người d ng trong
trường hợ d liệu thưa.
3. Các đóng góp của luận văn
Đóng gó của luận văn là đề xuất một hương há tính toán m c độ tương t
gi a các cặ người d ng hoặc sản hẩm d a vào đồ thị để nâng cao chất lượng d đoán
cho các hệ tư vấn. Nh ng đóng gó cụ thể của luận văn bao gồm bao gồm:
-
Mở rộng biểu diễn đồ thị của Huang [23] cho các hệ thống lọc cộng tác. Phương
há biểu diễn h hợ với tất cả các bộ d liệu cho lọc cộng tác hiện tại.
-
Đề xuất hương há tính toán m c độ tương t gi a các cặ người d ng d a vào
hương há ước lượng trọng số các đường đi từ đỉnh người d ng đ n đỉnh người
d ng. Đề xuất được á dụng cho hương há UserBased đạt k t uả tốt tr n các
bộ d liệu thử nghiệm khác nhau.
-
Đề xuất hương há tính toán m c độ tương t gi a các cặ sản hẩm d a vào
hương há ước lượng trọng số các đường đi từ đỉnh sản hẩm đ n đỉnh sản
hẩm. Đề xuất được á dụng cho hương há ItemBased đạt k t uả tốt tr n các
bộ d liệu thử nghiệm khác nhau.
3
-
Xây d ng được bộ d liệu thử nghiệm cho lọc cộng tác với 7682 người d ng và
3000 sản hẩm di động khác nhau.
-
Xây d ng hệ tư vấn sản hẩm điện thoại di động. Hệ thống cho hé xem, đánh
giá, gợi ý nh ng sản hẩm hợ với sở thích của m i người d ng.
4. Bố cục của luận văn
Luận văn được tổ ch c thành ba chương, trong đó :
Chương 1 : Giới thiệu tổng uan về lọc cộng tác d a vào bộ nhớ.
Nội dung chính của chương trình bày nh ng nghi n c u cơ bản về lọc cộng tác, các
hương há lọc cộng tác, đi sâu trình bày về các hương há lọc cộng tác d a tr n bộ
nhớ. Tr n cơ sở nh ng nghi n c u cơ bản, xác định rõ hướng nghi n c u của đề tài.
Chương 2 : Trình bày hương há lọc cộng tác d a tr n mô hình đồ thị, bao gồm :
Phương há lọc d a tr n người d ng, hương há lọc d a tr n sản hẩm. Nội dung
trình bày trong chương này được tổng hợ từ k t uả nghi n c u đã được trình bày tại
hội nghị Quốc Gia lần th 6 về “Nghi n c u cơ bản và ng dụng công nghệ thông tin” tổ
tr c tại Hu ngày 20-21/6/2013 [1].
Chương 3 : Trình bày thi t k và xây d ng hệ tư vấn sản hẩm điện thoại di động sử
dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề xuất trong chương 2.
4
CHƯƠNG 1: LỌC CỘNG TÁC DỰA VÀO BỘ NHỚ
Mục ti u chính của chương này trình bày nh ng vấn đề tổng uan về lọc cộng tác,
các hương há lọc cộng tác,
hân tích rõ nh ng hạn ch tồn tại của m i hương há
để từ đó xác định rõ hướng nghi n c u cụ thể của đề tài. Nh ng k t uả nghi n c u của
đề tài sẽ được trình bày trong các chương ti
1.1.
theo của luận văn.
Phát biểu bài toán lọc cộng tác
Cho tậ hợ h u hạn U = {u1, u2,…, uN} là tậ gồm N người d ng, P = {p1, p2,..,
pM} là tậ gồm M sản hẩm. M i sản hẩm pxP có thể là hàng hóa, him, ảnh, tạ 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. Để
thuận tiện trong trình bày, ta vi t pxP ngắn gọn thành xP, uiU là iU.
Mối uan hệ gi a tậ người d ng U và tậ sản hẩm P được biểu diễn thông ua
ma trận đánh giá R ={ rix , i = 1..N, x = 1..M}. M i giá trị rix thể hiện đánh giá của người
dùng uiU đối với sản hẩm pxP. Giá trị rix có thể được thu thậ tr c ti
h i ý ki n người d ng hoặc thu thậ gián ti
thông ua cơ ch
bằng cách
hả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
hẩm px. Nhiệm vụ của lọc cộng tác là d đoán uan điểm của người d ng uaU đối với
nh ng mặt hàng mới px P, tr n cơ sở đó tư vấn cho người d ng ua nh ng sản hẩm
được đánh giá cao [7].
Bảng 1 là một ví dụ về ma trận đánh giá cho hệ lọc cộng tác gồm 3 người d ng U
={ u1, u2, u3} và 4 sản hẩm P = {p1, p2, p3, p4}. Các giá trị đánh giá được biểu diễn có
giá trị rix {, 1, 2, 3, 4, 5}. Nh ng giá trị rix= được hiểu là người d ng iU chưa bi t
đ n sản hẩm xP. Ô điền ký t “?” là giá trị cần điền vào của các hương há lọc cộng
tác.
Bảng 1-1. Ma trận đánh giá của lọc cộng tác.
p1
p2
p3
p4
u1
5
4
u2
3
4
u3
?
3
?
2
5
Ma trận đánh giá R = (rix) là thông tin đầu vào duy nhất của các hương há lọc
cộng tác. D a tr n ma trận đầu vào, các hương há lọc cộng tác th c hiện như được
mô tả trong Hình 1.1.
Hình 1-1. Các thành phần của hệ thống lọc cộng tác
D a tr n ma trận đánh giá, các hương há
lọc cộng tác th c hiện hai tác vụ:
D đoán uan điểm của người d ng hiện thời (Active User về các sản hẩm mà họ chưa
đánh giá, đồng thời đưa ra một danh sách các sản hẩm có đánh giá cao nhất hân bổ
cho người d ng hiện thời.
Có nhiều hương há đề xuất khác nhau để giải uy t bài toán lọc cộng tác. Tuy
vậy ta có thể hân loại các hương há thành hai cách ti
cận chính: Lọc cộng tác d a
vào bộ nhớ và lọc cộng tác d a vào mô hình. Trong hai hương há này, hương há
lọc cộng tác d a vào bộ nhớ được sử dụng rộng dãi hơn cho các hệ thống lọc thông tin
th c t do cài đặt đơn giản, độ chính xác cao, chi hí tính toán thấ . Chính vì vậy, hướng
ti
cận của luận văn tậ trung nghi n c u hát triển hương há lọc cộng tác d a vào
bộ nhớ.
Lọc cộng tác d a tr n bộ nhớ được ti
cận theo hai hương há chính: Phương
pháp lọc d a vào người d ng (UserBased và lọc d a vào sản hẩm (ItemBased . Nội
dung cụ thể của hai hương há này được trình bày trong nh ng mục ti
theo.
6
1.2.
Phương pháp lọc cộng tác dựa trên sản phẩm
1.2.1. Thuật toán lọc cộng tác dựa trên sản phẩm
Thuật toán lọc cộng tác d a vào sản hẩm xây d ng cho sản hẩm một tậ láng
giềng có các đánh giá tương t nhất trong ma trận người d ng – sản hẩm. Các đánh giá
của nh ng sản hẩm láng giềng này sau đó được sử dụng để đưa ra d đoán. Thuật toán
lọc cộng tác d a tr n sản hẩm (Item-Based) được th c hiện thông ua 3 bước:
Bước 1: Tính toán độ tương t sản hẩm
Bước 2: Xác định tậ láng giềng cho sản hẩm cần tư vấn
Bước 3: Tính toán đưa ra lời d đoán
1.2.2. Ví dụ lọc cộng tác dựa trên sản phẩm
1.2.3. Hạn chế của phương pháp lọc cộng tác dựa trên sản phẩm
Vấn đề d liệu thưa (S arsity Data Problem
Vấn đề người d ng mới (New User Problem
Vấn đề sản hẩm mới (New Item Problem
1.3.
Phương pháp lọc cộng tác dựa trên người dùng
1.3.1. Thuật toán lọc cộng tác dựa trên người dùng
Thuật toán lọc cộng tác d a vào người d ng xây d ng cho m i người d ng một
tậ các láng giềng có các đánh giá tương t trong ma trận người d ng – sản hẩm. Các
đánh giá từ nh ng người d ng này sau đó được sử dụng để đưa ra d đoán. Kĩ thuật lọc
cộng tác d a trên người d ng (User-Based) được th c hiện thông ua 3 bước:
Bước 1. Tính toán m c độ tương t gi a các cặ người d ng
Bước 2: Xác định tậ láng giềng cho người d ng cần tư vấn
Bước 3: Tính toán đưa ra d đoán
1.3.2. Ví dụ lọc cộng tác dựa trên người dùng
1.3.3. Hạn chế của phương pháp lọc cộng tác dựa trên người dùng
Vấn đề d liệu thưa (S arsity Data Problem
Vấn đề người d ng mới (New User Problem
Vấn đề sản hẩm mới (New Item Problem
7
1.4.
Mục tiêu nghiên cứu của luận văn
Như đã trình bày ở trên lọc cộng tác được hân chia thành hai hướng ti
cận: lọc
cộng tác d a vào bộ nhớ và lọc cộng tác d a vào mô hình. Trong hai hương há này,
hương há lọc cộng tác d a vào bộ nhớ được sử dụng rộng dãi hơn cho các hệ thống
lọc thông tin th c t do cài đặt đơn giản, độ chính xác cao, chi hí tính toán thấ . Tuy
nhi n với việc sử dụng các dộ đo tương uan, độ đo tương t hiện tại thì các hệ thống lọc
thông tin chỉ khai thác được mối uan hệ tr c ti
nhiều mối uan hệ gián ti
gi a các đối tượng, như vậy b
ua rất
gi a các đối tượng trong hệ thống.
Chính vì vậy, hướng ti
cận của luận văn tậ trung nghi n c u hát triển hương
pháp lọc cộng tác d a vào bộ nhớ với mục ti u cụ thể như sau:
Nghi n c u và đề xuất hương há hạn ch ảnh hưởng tình trạng d liệu thưa của
lọc cộng tác d a tr n mô hình đồ thị. Phương há đề xuất được trình bày trong
Chương 2.
Xây d ng một ng dụng d a tr n hương há đề xuất. K t uả hân tích thi t k và
xây d ng ng dụng được trình bày trong Chương 3.
1.5.
Kết luận chương 1
Nội dung chương 1 đã trình bày tổng uan về lọc cộng tác, các hương há lọc
cộng tác d a vào bộ nhớ. Qua đó hân tích rõ nh ng hạn ch tồn tại của m i hương
há để xác định rõ hướng cụ thể của đề tài về nghi n c u và hát triển hương há lọc
cộng tác d a vào bộ nhớ.
8
CHƯƠNG 2: PHƯƠNG PHÁP USER-BASED VÀ
ITEM-BASED DỰA TRÊN MÔ HÌNH ĐỒ THỊ
Mục ti u chính của chương này trình bày k t uả nghi n c u của luận văn về hát
triển hương há lọc cộng tác d a vào bộ nhớ tr n mô hình đồ thị. Sử dụng biểu diễn đồ
thị cho hé tận dụng được mối uan hệ gián ti
gi a các đối tượng người d ng và sản
hẩm vào uá trình d đoán và tư vấn. Khác với cách ti
cận trong [23, 29], hương
há d đoán của luận văn được th hiện d a tr n việc xây d ng một độ đo tương t
gi a các cặ người d ng hoặc sản hẩm. D a tr n độ đo tương t này, ta xác định được
tậ láng giềng tốt hơn so với các hương há lọc d a vào bộ nhớ sử dụng các độ đo
tương uan.
Để thuận tiện cho việc trình bày: Mục (2.1 trình bày hương há biểu diễn đồ
thị hai hía cho lọc cộng tác. Mục (2.2 trình bày hương há lọc d a tr n người d ng
tr n mô hình đồ thị. Mục (2.3 trình bày hương há lọc d a tr n sản hẩm tr n mô
hình đồ thị. Mục (2.4 trình bày điều kiện cần và đủ để các hệ thống lọc cộng tác á dụng
tất cả các hương há tr n mô hình đồ thị. Mục (2.5 trình bày về k t uả thử nghiệm,
so sánh và đánh giá với các hương há lọc khác. Mục cuối c ng (2.6) là k t luận và
hướng nghi n c u ti
theo. Nội dung trình bày trong chương này được tổng hợ từ k t
uả nghi n c u trong [1].
2.1.
Biểu diễn đồ thị hai phía cho lọc cộng tác
Giả sử ta có hệ lọc cộng tác gồm N người d ng U và M sản hẩm P với ma trận
đánh giá là R=(rij: i=1, 2, ..N; j =1, 2, ..,M . Không hạn ch tính tổng uát của bài toán,
ta giả sử rix= +v n u người d ng iU đánh giá sản hẩm xP ở m c độ v, trong đó
v[0, 1].
v
rix
Nếu người dùng i thích sản phẩm x ở mức độ v.
Nếu người dùng i chưa biết đến sản phẩm x.
(2.1)
Biểu diễn ma trận đánh giá theo (2.1 sẽ không ảnh hưởng đ n các hệ thống lọc
cộng tác sử dụng đánh giá nhị hân (0,1 hoặc có nhiều m c đánh giá trong khoảng [0,1].
Đối với các bộ d liệu có giá trị đánh giá rix{1, 2, .., V}, ta chỉ cần th c hiện hé bi n
đổi đơn giản chuyển rix
rix
. Phé bi n đổi này vẫn bảo toàn được m c độ đánh giá theo
V
th t khác nhau của các hệ lọc cộng tác. Đây là một biểu diễn mở rộng của Huang đã
9
th c hiện trong [22]. Ví dụ với hệ lọc cộng tác được cho trong Bảng 1, sẽ được chuyển
đổi biểu diễn theo (2.1 thành Bảng 2.1. Muc đích của việc chuyển đổi rix[0,1] để sử
dụng trong hương há tính toán m c độ tương t gi a các cặ người d ng và sản
hẩm. Nội dung này sẽ được trình bày chi ti t trong các mục ti
theo.
Bảng 2-1. Ma trận đánh giá được chuyển đổi
p1
p2
p3
p4
u1
1.0
0.8
u2
0.6
0.8
u3
?
0.6
?
0.4
Hệ lọc cộng tác với ma trận đánh giá xác định theo (2.1 hình thành n n một đồ thị
hai hía, một hía là tậ người d ng, hía còn lại là tậ sản hẩm, ký hiệu là đồ thị G
=. Tậ đỉnh V của đồ thị được chia thành hai tậ : tậ người d ng và tậ sản hẩm
(V=UP . Tậ cạnh E của đồ thị được xác định theo công th c (2.2 . M i cạnh eE đều
có dạng e = (i, x , trong đó iU và xP. Không tồn tại các cạnh của nối gi a hai đỉnh
người d ng hoặc cạnh nối gi a hai đỉnh sản hẩm. Trọng số của m i cạnh được xác định
theo (2.3).
E e (i, x) : i U x P | rix
(2.2)
rix if (i, x) E
wix
0 otherwise
(2.3)
Gọi C=(cij là ma trận trọng số biểu diễn đồ thị G (i =1, 2,.., N+M; j = 1, 2, ..,
N+M . Khi đó, ma trận vuông C sẽ được chia thành bốn hần theo công th c (2.4).
Trong đó, ma trận vuông U(NN biểu diễn mối uan hệ gi a người d ng và người d ng,
P(MM biểu diễn mối uan hệ gi a sản hẩm với sản hẩm, W(NM được xác định
theo (2.3 biểu diễn mối uan hệ gi a người d ng và sản hẩm, WT(MN là chuyển vị
của W(NM biểu diễn mối uan hệ gi a sản hẩm và người d ng. Các hần tử của ma
trận U(NN), P(MM ban đầu đều có giá trị 0.
U N N
C T
W M N
W N M
PM M
(2.4)
10
Ví dụ, với hệ lọc cộng tác được cho trong Bảng 2.1, khi đó đồ thị hai hía biểu
diễn cho lọc cộng tác được thể hiện trong Hình 2.1, thành hần của ma trận trọng số
được thể hiện trong Hình 2.2.
p1
p2
1.0
0.8
p3
0.6
u1
0.8
p4
0.6
u2
0.4
u3
Hình 2-1. Đồ thị hai phía biểu diễn cho lọc cộng tác.
U(NN)
C=
W(NM)
0.0
0.0
0.0
1.0
0.0
0.8
0.0
0.0
0.0
0.0
0.0
0.6
0.8
0.0
0.0
0.0
0.0
0.0
0.6
0.0
0.4
1.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.6
0.6
0.0
0.0
0.0
0.0
0.8
0.8
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.4
0.0
0.0
0.0
0.0
WT(MN)
P(MM)
Hình 2-2. Ma trận trọng số biểu diễn đồ thị hai phía.
Cho đồ thị G = biểu diễn dưới dạng ma trận trọng số C xác định theo (2.4).
Khi đó, lọc cộng tác có thể được xem xét như bài toán tìm ki m tr n đồ thị. Trong đó,
mức độ tương tự giữa các cặp người dùng được tính toán dựa vào 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 được
tính toán dựa vào trọng số các đường đi từ đỉnh sản phẩm đến đến đỉnh sản phẩm, mức
độ phù hợp của người dùng đối với sản phẩm được tính toán dựa vào trọng số các đường
đi từ đỉnh người dùng đến đỉnh sản phẩm. M c độ tương t gi a các cặ người d ng sẽ
được điền giá trị vào ma trận U(NN , m c độ tương t gi a các cặ sản hẩm sẽ được
điền giá trị vào ma trận P(MM , m c độ h hợ của người d ng đối với sản hẩm
được điền giá trị vào ma trận W(NM) và WT(MN . Trong đó,U(NN), P(MM),
W(NM), WT(MN được xác định theo (2.4). Nội dung cụ thể m i hương há ti
sẽ được trình bày trong các mục ti
theo.
cận
11
2.2.
Phương pháp user-based dựa trên mô hình đồ thị hai phía
Thuật toán UserBased-Graph:
Đầu vào:
Ma trận trọng số C là biểu diễn đồ thị G = cho lọc cộng tác .
iU 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 | xP\Pi.( quan điểm của người dùng i đối với các sản phẩm
mới xP).
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:
L 2;//Thi t lậ độ dài đường đi ban đầu
Repeat
W N M *W T M N
U L N N
W N M *W T M N *U L 2 N N
if
L2
if
L 4,6,8,..
(2.5)
L L + 2; //Tăng độ dài đường đi.
Until ( u ijL 0 với mọi j(U \ i) );
Bước 2. Xác định tậ láng giềng cho người d ng iU.
Sắ x
u ijL 0
theo th t giảm dần (ij).
Chọn K người d ng jU đầu ti n làm tậ láng giềng của người d ng i
(Ký hiệu tậ láng giềng của người d ng iU là Ki).
Bước 3. D đoán uan điểm của người d ng i đối với các sản hẩm xP\Pi.
rix
1
Ki
r
jx
;
jK i
Bước4. Chọn K sản hẩm có m c độ tương t cao nhất tư vấn cho người d ng i.
Hình 2-3. Thuật toán UserBased-Graph.
M c độ tương t gi a các cặ người d ng được xác định theo (2.5) hụ thuộc vào
độ dài đường đi L từ đỉnh người d ng đ n đỉnh người d ng tr n đồ thị. Do vậy, một vấn
đề đặt ra là với m i người d ng iU giá trị của L được lấy bằng bao nhi u cho tốt.
Ngược lại đồ thị G= hải có tính chất gì để ta có thể xác định được L sao cho m c
độ tương t gi a các cặ người d ng uij0. Định lý 1 dưới đây sẽ cho ta một cách xác
định L trong trường hợ đồ thị biểu diễn của lọc cộng tác G = liên thông.
12
Định lý 1. N u đồ thị biểu diễn cho các hệ lọc cộng tác G= liên thông thì luôn
luôn tồn tại số t nhi n chẵn L để u ijL 0 với mọi i, jU . Trong đó, u ijL được xác định
theo công th c ở bước 1.
Phương pháp item-based dựa trên mô hình đồ thị hai phía
2.3.
Thuật toán ItemBased-Graph:
Đầu vào:
Ma trận trọng số C là biểu diễn đồ thị G = cho lọc cộng tác .
xP là sản phẩm cần dự đoá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 | iU\Ux.( quan điểm của người dùng i đối với phẩm mới xP).
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
L 2;//Thi t lậ độ dài đường đi ban đầu
Repeat
W T M N *W N M
P L M M
W T M N *W N M * P L 2 M M
if
L2
if
L 4,6,8,..
(2.6)
L L + 2; //Tăng độ dài đường đi.
Until ( p xyL 0 với mọi y(P \ x) );
Bước 2. Xác định tậ láng giềng cho sản hẩm xP.
Sắ x
L
p xy
theo th t giảm dần (xy).
Chọn K sản hẩm yP đầu ti n làm tậ láng giềng của sản hẩm x (Ký
hiệu tậ láng giềng của sản hẩm xP là Kx).
Bước 3. D đoán uan điểm của người d ng i đối với các sản hẩm xP\Pi.
rix
1
Kx
r
ix
;
xKx
Bước4. Chọn K sản hẩm có m c độ tương t cao nhất tư vấn cho người d ng i.
Hình 2-4. Thuật toán ItemBased-Graph.
M c độ tương t gi a các cặ sản hẩm xác định theo (2.6) hụ thuộc vào độ dài
đường đi L từ đỉnh sản hẩm đ n đỉnh sản hẩm tr n đồ thị. Do vậy, với m i sản hẩm
xP ta cũng cần xác định giá trị của L để th c hiện tính toán. Định lý 2 dưới đây sẽ cho
ta một cách xác định L trong trường hợ đồ thị biểu diễn của lọc cộng tác G = liên
thông.
13
Định lý 2. N u đồ thị biểu diễn cho các hệ lọc cộng tác G= liên thông thì luôn
luôn tồn tại số t nhi n chẵn L để p xyL 0 với mọi x, yP . Trong đó, PxyL được xác định
theo công th c trong bước 1.
2.4.
Điều kiện cần và đủ để các hệ thống lọc cộng tác áp dụng tất cả các
phương pháp trên mô hình đồ thị
Định lý 3. Điều kiện cần và đủ để U L N N được xác định theo (2.5), P L M M xác định
theo (2.6) được điền đầy đủ giá trị khác 0 khi và chỉ khi đồ thị biểu diễn cho các hệ lọc
cộng tác G= li n thông.
2.5.
Kiểm nghiệm và đánh giá
2.5.1. Dữ liệu thử nghiệm
Ti n hành kiểm thử tr n 2 tậ d liệu : MovieLens, vật giá.
(1) Bộ d liệu MovieLens [24] gồm 1682 người d ng, 943 him với tr n 100000 đánh
giá, các m c đánh giá được thi t lậ từ 1 đ n 5, m c độ thưa thớt d liệu đánh giá là
98,7%. Các m c đánh giá 1, 2, 3, 4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0.
Chọn ngẫu nhi n : (80% 754 người d ng làm tậ huấn luyện (Training , (20% 189
người d ng còn lại làm tậ kiểm tra (Test như hình 2.6.
Hình 2-5. Mô phỏng tập dữ liệu Movilens
(2) Bộ d liệu vật giá [28] gồm 402 người d ng tr n 10 đánh giá, 3441 sản hẩm với
8885 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5. Các m c đánh giá 1, 2, 3,
4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0.
14
Chọn ngẫu nhi n (80% 322 người d ng trong tậ huấn luyện, (20%) 80 người d ng
trong tậ kiểm tra.
(3) Bộ d liệu vật giá [28] gồm 1114 người dùng tr n 5 đánh giá, 4418 sản hẩm với
13476 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5. Các m c đánh giá 1, 2,
3, 4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0.
Chọn ngẫu nhi n (80% 892 người d ng trong tậ huấn luyện, (20%) 222 người dùng
trong tậ kiểm tra.
2.5.2. Phương pháp thử nghiệm
Trước ti n, toàn bộ tậ người d ng được chia thành hai hần, một hần Utr được sử
dụng làm d liệu huấn luyện, hần còn lại Ute được sử dụng để kiểm tra. Tậ d liệu huấn
luyện d ng để xây d ng mô hình theo các thuật toán lọc được sử dụng. Với m i người
dùng u Ute, các đánh giá ru,p≠ được chia thành hai hần Ou và Pu. Ou được coi là đã bi t,
trong khi đó Pu là đánh giá cần d đoán từ d liệu huấn luyện và Ou (hình 2.6). Giả sử
hương há lọc đưa ra d đoán cho người d ng trong tậ Pu là P’u . Khi đó, sai số d
đoán được th c hiện bằng cách so sánh các đánh giá trong hai tậ Pu là P’u .
Có nhiều hương há đánh giá sai số hân loại khác nhau đã được đề xuất. Một
trong số hương há
hổ bi n nhất được sử dụng trong lọc cộng tác là đánh giá sai số
hân loại thông ua độ đo trung bình giá trị tuyệt đối l i MAE.
Sai số d đoán
với m i khách hàng u thuộc tậ d liệu kiểm tra được tính
bằng trung bình cộng của sai số tuyệt đối gi a hai giá trị được d đoán và giá trị th c của
tất cả các sản hẩm thuộc tậ
.
|
|
∑
| ̂
|
(2.7)
Sai số d đoán tr n toàn tậ 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
.
∑
|
Giá trị MAE càng nh ch ng t
hơn.
2.5.3. Kết quả thử nghiệm
2.5.3.1.
Với bộ dữ liệu Movielens
|
(2.8)
hương há đề xuất cho k t uả càng chính xác
15
Bảng 2-2. Độ đo MAE với các đánh giá biết trước của tập dữ liệu Movielens
Số đánh giá bi t trước trong tậ kiểm tra
Phương há
1
2
5
10
15
20
Top-N-ItemBased
0.4347
0.38
0.4536
0.4576
0.4128
0.3869
KNN-UserBased
0.7171
0.5519
0.4894
0.5554
0.6
0.6334
ItemBased-Graph
0.3819
0.3021
0.3269
0.2253
0.2024
0.1755
UserBased-Graph
0.3657
0.3584
0.3486
0.3475
0.3465
0.3336
2.5.3.2.
Với bộ dữ liệu vật giá 402 người dùng
Bảng 2-3. Độ đo MAE với các đánh giá biết trước của tập dữ liệu vật giá 402 người dùng
Phương há
2.5.3.3.
Số đánh giá bi t trước trong tậ kiểm tra
1
2
5
Top-N-ItemBased
0.7877
0.77215
0.7412
KNN-UserBased
0.8046
0.7978
0.7804
ItemBased-Graph
0.7503
0.7576
0.5788
UserBased-Graph
0.6549
0.6428
0.6596
Với bộ dữ liệu vật giá 1114 người dùng
Bảng 2-4. Độ đo MAE với các đánh giá biết trước của tập dữ liệu vật giá 1114 người dùng
Phương há
Số đánh giá bi t trước trong tậ kiểm tra
1
2
5
Top-N-ItemBased
0.7804
0.7638
0.7327
KNN-UserBased
0.8042
0.798
0.7722
ItemBased-Graph
0.7444
0.7032
0.3248
UserBased-Graph
0.6593
0.6574
0.4891
K t uả kiểm nghiệm cho thấy, các hương há đề xuất d a tr n đồ thị cho lại sai số
trung bình tuyệt đối l i MAE nh hơn với hương hương há lọc ItemBased và
UserBased d a tr n độ tương uan Pearson. Điều đó có thể khẳng định, hương há d
đoán d a tr n mô hình đồ thị có thể tích hợ được nhiều thông tin gián ti
gi a người
16
d ng và sản hẩm vào uá trình huấn luyện. Lý do khi n hai hương há đề xuất cho lại
k t uả tốt hơn là hương há đã d đoán d a vào tậ láng giềng của cộng đồng người
d ng có chung sở thích. Nói cách khác hương há đề xuất xác định được tậ láng
giềng chính xác hơn so với các hương há hiện tại.
2.6.
Kết luận chương 2
Nội dung chương 2 đã trình bày k t uả nghi n c u của luận văn về hát triển
hương há lọc cộng tác d a vào bộ nhớ tr n mô hình đồ thị.
Phương há biểu diễn đồ thị cho hé tận dụng được mối uan hệ gián ti
gi a
các đối tượng người d ng và sản hẩm vào uá trình d đoán và tư vấn.
Phương há d đoán được đưa về bài toán tìm ki m tr n đồ thị cho hé ta sử
dụng biểu diễn đồ thị bằng ma trận thưa để giảm thiểu không gian biểu diễn d liệu,
đồng thời có thể sử dụng các thuật toán hiệu uả tr n đồ thị. Phương
há d đoán tr n
tất cả các đánh giá, cho hé ta giảm thiểu các l i có thể xảy ra trong
uá trình d đoán
và hân bổ thông tin (Một sản hẩm người d ng “không thích” có thể có mặt trong danh
sách các sản hẩm cần tư vấn. Một sản hẩm người d ng “thích” có thể có mặt trong
danh sách các sản hẩm cần loại b .
M c độ tương t gi a các cặ người d ng được tính toán d a vào 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ặ sản
hẩm được tính toán d a vào trọng số các đường đi từ đỉnh sản hẩm đ n đ n đỉnh sản
hẩm. Đây chính là điểm khác biệt uan trọng của mô hình đề xuất so với các mô hình
trước đây.
K t uả kiểm nghiệm tr n bộ d liệu MovieLens, vật giá cho thấy, mô hình đề
xuất cho lại k t uả tốt hơn các hương há lọc cộng tác d a tr n độ tương uan thuần
túy.
17
CHƯƠNG 3: XÂY DỰNG HỆ TƯ VẤN SẢN PHẨM
ĐIỆN THOẠI DI ĐỘNG
Mục ti u chính của chương này trình bày thi t k và xây d ng hệ tư vấn sản hẩm
điện thoại di động sử dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề
xuất trong chương 2. Hệ thống cho hé người d ng xem sản hẩm, đánh giá sản hẩm,
tìm ki m sản hẩm, tư vấn sản hẩm đ n người d ng. Song song đó là xây d ng thành
công một ng dụng tr n điện thoại thông minh chạy hệ điều hành Windows Phone sử
dụng dịch vụ cung cấ bởi hệ tư vấn đã xây d ng.
3.1.
Yêu cầu hoạt động của hệ thống
Người d ng ng dụng tr n điện thoại thông minh chạy hệ điều hành Windows
Phone đăng nhậ vào hệ thống bằng tài khoản của mình, ti n hành đánh giá nh ng sản
hẩm. Hệ thống sẽ ghi nhận nh ng đánh giá đó để làm cơ sở khuy n nghị. Hệ thống sẽ
d a vào nh ng đánh giá đó của người d ng để gợi ý cho người d ng nh ng sản hẩm
h hợ , trả về điện thoại của người d ng.
3.2.
Mô hình tổng quát của hệ thống
Ki n trúc của hệ thống mô tả trong Hình 3.1 được thi t k gồm 2 hần chính như sau:
1. Phần 1: ng dụng máy khách được vi t tr n nền tảng hệ điều hành Windows Phone
h trợ người sử dụng các ch c năng như: xem / tìm ki m thông tin các sản hẩm điện
thoại di động, xem gợi ý về các sản hẩm di động h hợ với người d ng, đánh giá
m c độ thích của người d ng với sản hẩm được xem.
2. Phần 2: ng dụng máy chủ bao gồm:
-
Dịch vụ web hụ trách việc truyền nhận thông tin gi a máy khách và máy chủ.
-
Hệ thống khuy n nghị người d ng. Hệ thống này có 2 ch c năng : ch c năng
huấn luyện và ch c năng tư vấn.
Ch c năng huấn luyện (th c hiện học offline hía Back-end : có nhiệm vụ
xây d ng mô hình d a tr n d liệu đánh giá sản hẩm của người d ng được
xây d ng theo mô hình đồ thị đã trình bày trong chương 2.
Ch c năng tư vấn (th c hiện online được cung cấ
thông
ua dịch vụ
webservice : Khi có y u cầu tư vấn từ một người d ng được gửi từ ng dụng
máy khách thông ua webservice tới hệ thống tư vấn, ch c năng sẽ sử dụng
18
d liệu được xây d ng từ ha học offline để lấy về To -N sản hẩm có đánh
giá d đoán cao nhất để tư vấn cho khách hàng.
3.3.
Phân tích thiết kế hệ thống
3.3.1. Phân tích hệ thống
3.3.1.1.
Xây dựng biểu đồ use case và scenario của các use case
3.3.1.2.
Xây dựng biểu đồ lớp phân tích
3.3.2. Thiết kế hệ thống
3.3.2.1.
Xây dựng biểu đồ tuần tự
3.3.2.2.
Xây dựng biểu đồ lớp thiết kế
3.4.
Mô hình dữ liệu hệ thống
3.4.1. Mô tả dữ liệu
Nguồn thông tin về các sản hẩm điện thoại tr n thị trường được trích xuất từ
trang web vật giá [28], gồm : 7682 người d ng, 3000 sản hẩm với 16110 đánh giá, các
m c đánh giá được thi t lậ từ 1 đ n 5.
3.4.2. Mô hình dữ liệu hệ thống
Hình 3-1. Mô hình dữ liệu hệ thống tư vấn sản phẩm điện thoại
3.5.
Kết luận chương 3
Nội dung chương 3 đã trình bày thi t k và xây d ng hệ tư vấn sản hẩm điện
thoại di động sử dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề xuất
trong chương 2. Song song đó là xây d ng thành công một ng dụng tr n điện thoại
thông minh chạy hệ điều hành Windows Phone sử dụng dịch vụ cung cấ bởi hệ tư vấn
đã xây d ng.
- Xem thêm -