i
LỜI CAM ĐOAN
Tôi xin cam đoan những kết quả được trình bày trong luận
văn này là của riêng tôi, không sao chép từ bất kỳ một công trình
nào khác. Nếu có điều gì không trung thực, tôi xin chịu hoàn
toàn trách nhiệm.
Học viên
Hoàng Thịnh
ii
Lời Cảm Ơn
Lời đầu tiên, cho phép tôi gửi lời cảm ơn đến TS Võ Viết Minh Nhật, mặc dù
rất bận rộn trong công việc nhưng thầy đã luôn quan tâm giúp đỡ, hướng dẫn, chỉ
bảo tận tình giúp tôi hoàn thành luận văn này.
Tôi xin chân thành cảm ơn Quý Thầy Cô trong Khoa Công nghệ thông tin
trường Đại Học Khoa học Huế vì những kiến thức mà quý Thầy Cô truyền đạt cho
tôi trong suốt quá trình học tập tại trường.
Xin chân thành cảm ơn các anh chị em lớp cao học Khoa học máy tính khoá
2011-2013 và các bạn đồng nghiệp đã luôn bên cạnh, động viên, khuyến khích tôi
trong suốt thời gian học tập và thực hiện đề tài.
Cuối cùng, tôi xin gửi đến gia đình, chính từ sự hỗ trợ và động viên từ phía
gia đình mà tôi yên tâm học tập tốt và hoàn thành luận văn.
Xin chân thành cảm ơn!
Người thực hiện
Hoàng Thịnh
iii
MỤC LỤC
Trang
LỜI CAM ĐOAN i
Lời Cảm Ơn ii
MỤC LỤC iii
DANH MỤC CÁC BẢNG v

2.4.2 Các yếu tố ảnh hưởng đến độ chính xác tư vấn 36
2.5 Kết luận chương 2 38
Chương 3 39
MÔ PHỎNG VÀ ĐÁNH GIÁ CÁC THUẬT TOÁN TƯ VẤN 39
3.1 Dữ liệu thử nghiệm và phương pháp đánh giá 39
3.1.1 Mô tả dữ liệu 39
3.1.2 Phương pháp đánh giá chất lượng của hệ thống tư vấn 39
3.1.3 Môi trường và công cụ 40
3.2. Cài đặt thuật toán 40
3.2.1 Cài đặt thuật toán tính độ tương tự 40
3.2.2 Cài đặt thuật toán dự đoán tư vấn 42
3.3 Kết quả thử nghiệm 46
3.3.1 Thử nghiệm tư vấn với số lượng lân cận khác nhau: 46
3.3.2 Thử nghiệm với tư vấn với các độ tương tự khác nhau 47
3.3.3 Thử nghiệm tư vấn với các công thức dự đoán: 49
3.4 Kết luận chương 3 50
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 51
TÀI LIỆU THAM KHẢO 52
v
CÁC THUẬT NGỮ SỬ DỤNG TRONG TÀI LIỆU
STT
Tên tiếng
anh
Tên tiếng việt Giải thích
1 User Người dùng,
người sử dụng
Chỉ những người dùng hệ thống để tìm
kiếm lựa chọn sản phẩm
2 Item Sản phẩm, mục Chỉ những sản phẩm trên hệ thống như:
sản phẩm, phim, ảnh, bản nhạc, trang

3.3 Độ sai số MAE với các thuật toán dự đoán 50
DANH MỤC CÁC HÌNH VẼ
vii
Số hiệu
hình vẽ
Tên hình vẽ Trang
1.1 Minh họa hệ thống tư vấn sách cho người đọc 5
1.2
Minh họa phương pháp tư vấn dựa trên lọc nội dung
8
1.3
Minh họa phương pháp tư vấn dựa trên lọc cộng tác
13
1.4
Quy trình của hệ thông tư vấn dựa trên lọc cộng tác
14
2.1 Tách các sản phẩm được đánh giá và tính toán độ tương tự 24
2.2 Giải thuật lọc cộng tác dựa trên sản phẩm 32
2.3 Mô hình hệ thống lọc cộng tác dựa trên sản phẩm
37
3.1
Biểu đồ sai số lỗi tuyệt đối của hệ thống tư vấn với các lân cận
48
3.2
Biểu đồ sai số tuyệt đối của hệ thống tư vấn với các thuật toán
tính độ tương tự
49
3.3
Biểu đồ độ chính xác của hệ thống tư vấn với các thuật toán dự
đoán

người dùng và có thể đưa ra được những gợi ý cho người dùng.
Đầu những năm 90 của thế kỷ XX, một hướng nghiên cứu mới cho các hệ
thống tư vấn lựa chọn, đó là lọc cộng tác. Ngay từ khi ra đời, các hệ thống tư vấn
dựa trên lọc cộng tác đã thể hiện được những ưu điểm cùng tính kinh tế của mình.
Nó nhanh chóng thu hút được sự quan tâm nghiên cứu và đã được ứng dụng thành
công trong khá nhiều hệ thống thương mại như www.amazon.com,
www.ebay.com, Do nhu cầu cao như vậy nên các phương pháp xây dựng giải
thuật tư vấn nhận được nhiều sự quan tâm trong giới nghiên cứu.
2
Trong phạm vi luận văn cao học, tôi chọn đề tài “Tìm hiểu phương pháp lọc
cộng tác dựa trên Item”.
• Mục đích nghiên cứu
Mục tiêu đặt ra của luận văn trong đề tài này là: Tìm hiểu tổng quan về hệ
thống tư vấn, các phương pháp được sử dụng trong hệ thống tư vấn, quy trình thực
hiện tư vấn, ứnng dụng của hệ thống tư vấn trong thực tiễn.
Mục tiêu cụ thể là tìm hiểu phương pháp lọc cộng tác dựa trên sản phẩm, tìm
hiểu các thuật toán tính độ tương tự và dự đoán, đánh giá và so sánh chất lượng tư
vấn của các thuật toán.
• Đối tượng và phạm vi nghiên cứu
Nghiên cứu các phương pháp tính độ tương tự, và dự đoán trong hệ thống tư
vấn lọc cộng tác dựa trên sản phẩm (item) với các tập dữ liệu phim trên hệ thống
Group Lens
• Phương pháp nghiên cứu
Nghiên cứu lý thuyết, phân tích quá trình thực hiện, mô phỏng, cài đặt thuật
toán, so sánh đánh giá và rút ra kết luận từ các kết quả thu được.
• Ý nghĩa khoa học và thực tiễn của đề tài
Hệ thống tư vấn là những công cụ cung cấp các gợi ý về các sản phẩm cho
người dùng. Một vấn đề quan trọng và phổ biến trong kỹ thuật tư vấn là sử dụng các
phương pháp tư vấn nhằm tăng chất lượng tư vấn và thời gian tính toán để áp dụng
trong các lĩnh vực: kinh doanh thương mại, dịch vụ … Phương pháp lọc cộng tác

Vào giữa thập niên 1990, hệ thống tư vấn được xem như là một lĩnh vực
nghiên cứu độc lập khi bắt đầu tập trung vào những vấn đề liên quan đến tư vấn mà
phụ thuộc rõ ràng những cấu trúc trọng số. Trong hầu hết các trường hợp, tư vấn
được đưa về việc đánh giá trọng số cho những sản phẩm mà người dùng chưa chọn
lựa (sử dụng)
Trong hình thức đơn giản nhất, các tư vấn mang tính cá nhân hóa cung cấp
một danh sách các sản phẩm đã được xếp hạng. Để thực hiện việc xếp hạng này, hệ
thống tư vấn cố gắng dự đoán các sản phẩm hoặc dịch vụ phù hợp nhất dựa trên sở
thích của người dùng. Để hoàn thành một công việc như thế, hệ thống tư vấn thu
thập sở thích của các người dùng, bằng cách dựa trên các xếp hạng của họ về các
sản phẩm hoặc được suy diễn từ các hành động của người dùng. Ví dụ, một hệ
thống tư vấn có thể xem xét việc một người dùng xem thông tin trên website của
một trang sản phẩm như là một dấu hiệu ngầm định về sở thích của người đó đối
với sản phẩm trên trang đó.
5
Ví dụ minh họa hoạt động của 1 hệ thống tư vấn: Một người dùng đăng nhập
vào một hệ thống website đọc sách, người này cần xem 1 quyển sách về văn học
nhưng không biết là nên xem quyển sách nào, hệ thống website cần tư vấn cho
người đó xem một hoặc vài quyển sách mà dự đoán rằng người này sẽ thích quyển
sách mà được hệ thống tư vấn. Để tư vấn được cho người dùng, hệ thống cần thu
thập các thông tin về người dùng và các người dùng khác, thông tin các quyển sách.
Có một vài cách tư vấn truyền thống đơn giản nhất như, chọn những quyển sách
được nhiều người ưa thích nhất, hoặc chọn những quyển mới nhất để tư vấn. Tuy
nhiên để nâng cao chất lượng của tư vấn cho người dùng, hệ thống tư vấn cần sử
dụng các thông tin của tất cả những người dùng và thông tin của tất cả các sản
phẩm, sử dụng các thuật toán để đưa ra tư vấn phù hợp nhất cho người dùng.
Hình 1.1: Minh họa hệ thống tư vấn sách cho người đọc
1.1.2 Ứng dụng của hệ thống tư vấn
Phạm vi ứng dụng của hệ thống tư vấn lựa chọn là rất rộng. Trong thương mại
điện tử, hầu hết các hệ thống này là các hệ thống bán sách, giới thiệu phim, tin tức,

nhìn chung độ phù hợp có thể là một hàm bất kì tùy thuộc vào ứng dụng cụ thể. Giá
trị của r có thể được xác định bởi người dùng hoặc được tính toán bởi công thức nào
đó. Mỗi người dùng trong không gian U được xác định bởi một hồ sơ (profile). Hồ
7
sơ này có thể gồm rất nhiều loại thông tin: tuổi, giới tính, thu nhập, … hoặc có thể
chỉ gồm một mã người dùng (user id) duy nhất. Tương tự, mỗi sản phẩm trong
không gian I cũng được xác định bởi một tập các đặc trưng. Ví dụ, trong hệ thống
tư vấn phim, đặc trưng của mỗi bộ phim có thể là : tên phim, thể loại, đạo diễn, năm
sản xuất, diễn viên chính … Vấn đề chính của hệ thống tư vấn là r không được xác
định trên toàn không gian U × I mà chỉ trên một miền nhỏ của không gian đó. Điều
này dẫn tới việc hàm r phải được ngoại suy trong không gian U × I. Thông thường,
độ phù hợp được thể hiện bằng điểm và chỉ xác định trên tập các sản phẩm đã từng
được người dùng đánh giá từ trước. Ví dụ, bảng 1 mô tả đánh giá của một số người
dùng với các phim mà họ đã xem (thang điểm từ 1-5, kí hiệu Ø nghĩa là bộ phim
chưa được người dùng đánh giá). Từ những thông tin đó, hệ thống tư vấn phải dự
đoán điểm cho các bộ phim chưa được người dùng đánh giá, từ đó đưa ra những gợi
ý phù hợp nhất.
Bảng 1.1: Minh họa đánh giá của người dùng về 1 số bộ phim đã xem
Harry Potter X-Men Iron Man Spider Man
User A 3 Ø 5 Ø
User B 2 1 Ø Ø
User C Ø 5 2 4
1.3. Phân loại hệ thống tư vấn
Có rất nhiều cách để dự đoán, ước lượng hạng/điểm cho các sản phẩm như sử
dụng học máy, lí thuyết xấp sỉ, các thuật toán dựa trên kinh nghiệm … Theo [6], các
hệ thống tư vấn thường được phân thành ba loại:
• Tư vấn dựa trên nội dung: Người dùng sẽ được tư vấn những sản
phẩm tương tự với những sản phẩm đã được người dùng đó ưa thích trước đây.
• Tư vấn dựa trên cộng tác: Người dùng sẽ được tư vấn những sản
phẩm được ưa chuộng xuất phát từ những người dùng có cùng thị hiếu và sở

tư vấn trang Web cho người dùng, trình bày nội dung trang Web đó với 100 từ quan
trọng nhất “Tầm quan trọng” (việc cung cấp nhiều thông tin) của từ k
j
trong tài liệu
d
j
được xác định bằng độ đo trọng số wij định nghĩa qua một vài phương pháp khác
nhau.
Một trong những thước đo phổ biến để xác định mức độ quan trọng của từ
khóa trong việc truy vấn thông tin là đo tần suất xuất hiện của mục từ trong tài liệu
(Term Frequency ) và tần số nghịch đảo của tần suất xuất hiện các tài liệu (Inverse
Document Frequency) được định nghĩa như sau: Giả sử N là tổng số tài liệu được tư
vấn cho người dùng và từ khóa kj xuất hiện trong ni của chúng (ni là tổng số tài liệu
có từ khóa k). Giả sử fi,j là số lần từ khóa ki xuất hiện trong tài liệu dj. TFi,j là tần
số xuất hiện từ khóa ki trong tài liệu dj:
jzz
ji
ji
f
f
TF
,
,
,
max
=
Trong đó:
jzz
f
,

Chẳng hạn, ContentBasedProfile(u) có thể được định nghĩa như là một véc-tơ của
những mức độ quan trọng (w
u1
, …., w
uk
) , mỗi mức này sẽ biểu diễn tầm quan trọng
của từ khóa k
i
với người dùng u và nó có thể được tính toán từ các véc-tơ nội dung
đã được đánh trọng số cụ thể thông qua các kỹ thuật khác nhau. Ví dụ một vài
phương pháp tính trung bình cộng, tính toán ContentBasedProfile (u) như là một
véc-tơ “trung bình” từ những véc-tơ nội dung cụ thể. Mặt khác, sử dụng phân loại
Bayes để đánh giá khả năng giống nhau của tài liệu.
Trong những hệ thống dựa trên nội dung, hàm tiện ích r(u,i) thường được định
nghĩa như sau:
))(),(Pr(),( icontentuofileeContentBasscoreiur
=
Dựa trên việc truy vấn thông tin để tư vấn các trang Web, Web sites URLs
hoặc các thông điệp tin tức Usenet, thì cả ContentBasedProfile (u) của người dùng u
và Content (i) của tài liệu i đều có thể được trình bày như các TF-IDF véc-tơ
w
u

và
w
i

của các từ khóa quan trọng. Hàm r(u,i) được biểu diễn trong việc truy vấn thông
tin thường được xác định theo véc-tơ
w

K
j
uj
iu
iu
ww
ww
ww
ww
1
2
,
1
2
,
,
1
,
22
.


11
Trong đó K là tổng số các từ khóa trong hệ thống.
Ví dụ, nếu user u đọc nhiều bài báo trực tuyến về chủ để Tin Sinh Học thì kỹ
thuật tư vấn dựa trên nội dung sẽ có khả năng tư vấn những bài báo khác về tin sinh
học cho user u nếu nó có nhiều thuật ngữ liên quan đến tin sinh học hơn vì vậy
ContentBasedProfile (u) sẽ được xác định bằng véc-tơ
w
u

,
……
,k
n,j
trong trang đó:
)& &|(
,,1 jnji
kkCP
Ngoài ra, giả thuyết rằng các khóa này độc lập với nhau vì vậy xác suất ở trên
tương ứng với:
∏
x
ijxi
CKPCP )|()(
,
Mặc dù giả thuyết các từ khóa độc lập với nhau không nhất thiết phải áp dụng
ở nhiều ứng dụng nhưng kết quả thực nghiệm đã chứng minh kỹ thuật phân loại
Naïve Bayes vẫn đưa ra độ chính xác cao về mức độ phân loại. Hơn nữa cả P (k
x,j
|
12
C
i
) và P (C
i
) có thể được đánh giá từ dữ liệu hướng dẫn phía dưới. Với mỗi trang p
j
,
xác suất P (C
i

các món ăn của người Huế thì ngay cả những cửa hàng lớn nhất kiểu Huế trong
thành phố cũng không bao giờ được tư vấn. Đây là một vấn đề đã được nghiên cứu
trong nhiều lĩnh vực, nó thường được ấn định bằng việc giới thiệu một cách ngẫu
nhiên. Chẳng hạn, việc sử dụng những thuật toán di truyền được đề xuất như là khả
năng giải quyết các vấn đề về ngữ cảnh của việc lọc thông tin. Thêm vào đó, vấn đề
liên quan đến việc quá chuyên môn hóa còn là những hệ thống dựa trên nội dung
không thể tư vấn những sản phẩm mà khác với những gì mà người dùng đã biết
trước đó. Trong trường hợp nào đó, những sản phẩm không nên được tư vấn nếu
13
chúng có quá nhiều điểm tương đồng với những gì mà người dùng đã gặp, như một
bài báo tin tức tuy là khác nhau nhưng đưa về cùng một sự kiện. Vì vậy, một vài hệ
thống tư vấn dựa trên nội dung không chỉ lọc ra những sản phẩm có quá nhiều
điểm khác với sở thích của người dùng mà còn lọc cả chính những sản phẩm có quá
nhiều điểm giống của người dùng trước đó. Nói tóm lại, tính đa dạng của việc tư
vấn thường là những đặc điểm mô tả trong hệ thống tư vấn. Lý tưởng nhất là người
dùng sẽ tự đưa ra trọng số của những lựa chọn thay cho việc đưa ra một tập các khả
năng lựa chọn. Chẳng hạn, không phải là một ý kiến tuyệt vời nếu ta tư vấn tất cả
các bộ phim của Woody Allen tới người dùng mà chỉ ưa thích một trong số những
bộ phim đó.
- Vấn đề người dung mới: Người dùng phải đánh giá đầy đủ cho những sản
phẩm trước khi hệ thống tư vấn dựa trên nội dung có thể hiểu những sở thích của
người dùng và từ đó đưa ra cho người dùng những tư vấn tin cậy. Vì vậy, với người
dùng mới, thông tin về việc đánh trọng số rất ít nên khó có thể đảm bảo việc tư vấn
sẽ tốt.
- Vấn đề thông tin sản phẩm mới: Lọc nội dung phân tích các đặc điểm của
sản phẩm để so sánh với những sản phẩm mà người dùng đã đánh giá trước đó, với
những sản phẩm có thông tin không đầy đủ hoặc quá đặc biệt, rất khó để đưa ra 1 tư
vấn chính xác với các sản phẩm như vậy.
1.3.2. Phương pháp tư vấn dự trên lọc cộng tác
Mục đích của giải thuật lọc cộng tác là gợi ý những sản phẩm mới hoặc dự

aj
thể hiện đánh giá của người dùng a lên tài
nguyên j.
- Tư vấn: cho ra danh sách N tài nguyên {T
iN
} mà người dùng a thích nhất.
Giải thuật lọc cộng tác được mô tả thông qua một ma trận đánh giá R m x n
người dùng và sản phẩm. Mỗi phần tử a
i,j
trong mảng R biểu diễn đánh giá của
người dùng thứ i đối với sản phẩm thứ j. Mỗi đánh giá cá nhân là một số và nó có
thể nhận giá trị 0 khi người dùng chưa đánh giá sản phẩm đó. Các nhà nghiên cứu
đã xây dựng một số các giải thuật lọc cộng tác mà có thể chia thành 2 loại chính:
dựa trên bộ nhớ (Memory-based) và dựa trên mô hình (Model-based).
Giải thuật lọc công tác dựa trên bộ nhớ (Memory-based): Giải thuật lọc cộng
tác dựa trên bộ nhớ sử dụng các cơ sở dữ liệu người dùng – sản phẩm để dự đoán.
Những hệ thống triển khai kỹ thuật thống kê để tìm những lựa chọn của người dùng,
15
như biết người lân cận, có lịch sử phù hợp với người dùng đích (ví dụ, người dùng
đánh giá tương tự các sản phẩm khác nhau hoặc có khuynh hướng mua những sản
phẩm tương tự nhau). Một khi lân cận của người dùng được hình thành, hệ thống sử
dụng những giải thuật khác nhau để kết hợp những sở thích của người dùng lân cận
để đề xuất một dự đoán hoặc một tư vấn top-N cho người dùng.
Theo [6], Thuật toán dựa trên bộ nhớ về căn bản sử dụng các độ do kinh
nghiệm (heuristics) để sinh ra dự đoán dựa trên tập các sản phẩm của người dùng.
Cụ thể là, đánh giá trị r
u,i
của người dùng u đối với sản phẩm i thường được tính
toán như là một sự kết hợp trọng số của nhiều người dùng khác nhau với cùng một
sản phẩm i (thường là N sản phẩm giống nhau nhất):

(a)
∑
∈
×=
Uu
iuiu
ruusimkr
'
,',
)',(
(b)
∑
∈
−×+=
Uu
uiuuiu
rruusimkrr
'
',',
)()',(
(c)
Trong đó :
k: hệ số chuẩn hóa và thường được lựa chọn là k=
∑
∈Uu
uusim
ˆ
'
)',(/1


u,i
. Chú ý rằng sim(x,y) như 1 hàm heuristics, được được giới thiệu
để đánh giá mức khác nhau giữa các người dùng giống nhau, nhằm làm đơn giản
hóa việc sử dụng thừa số k như biểu diễn ở trên.
Những phương pháp tiếp cận khác nhau thường được tính toán hàm tương
quan sim(u,u’) giữa những người dùng trong hệ thống tư vấn cộng tác. Trong hầu
hết các phương pháp tiếp cận này, sự tương đồng giữa hai người dùng dựa trên
những đánh giá về sản phẩm được cả u và u’ quan tâm. Một trong những phương
pháp phổ biến nhất là dựa trên sự tương quan và cosine. Cụ thể, đầu tiên, xem S
xy
là
tập tất cả các sản pẩm của người dùng x và y; nghĩa là S
xy
={i
∈
S|r
x
,
i
∅≠
& r
y,i
∅≠
}.
Trong hệ thống tư vấn cộng tác, S
xy
thường được sử dụng để đưa ra kết quả tức thì
cho việc tính toán “người hàng xóm gần nhất” của người dùng x và thường được
tính toán để đưa ra xếp hạng rõ ràng, nghĩa là tính toán tìm ra điểm giao nhau giữa
tập S

∑
=
Giá trị trọng số (đánh giá) là những số nguyên nằm giữa 0 và n. Biểu thức xác
suất là xác suất mà người dùng u sẽ đưa ra trọng số cụ thể cho sản phẩm i, dựa trên
những trọng số của người dùng về những sản phẩm trước đó đã được đánh giá. Để
ước lượng xác suất này, sử dụng 2 mô hình xác suất tương đối sau: mô hình phân
cụm (cluster) và mạng Bayes. Trong mô hình đầu tiên, người dùng có sở thích
giống nhau được tập hợp lại thành một lớp. Trong lớp người dùng, sự đánh giá được
xem là độc lập với nhau, nghĩa là cấu trúc mô hình giống như mô hình Bayes thô sơ
ban đầu. Số lượng của các lớp và các thông số của mô hình được biết từ dữ liệu. Mô
hình thứ hai biểu diễn mỗi sản phẩm như là một nút trong mạng Bayes, ở đó mỗi
trạng thái của nút tương ứng với giá trị trọng số của mỗi sản phẩm có thể nhận biết
được. Cả cấu trúc của mạng và xác suất điều kiện được nhận biết từ dữ liệu. Vì vậy
giới hạn của phương pháp này là mỗi người dùng có thể được tập hợp lại thành một
nhóm (cluster) đơn lẻ, trong khi một vài ứng dụng tư vấn có thể được lợi từ khả
năng hợp các người dùng thành một vài nhóm cùng một lúc. Chẳng hạn, trong tư
vấn về sách, người dùng quan tâm đến một chủ đề (ví dụ: lập trình) với mục đích
công việc nhưng hoàn toàn có thể quan tâm đến chủ đề khác (ví dụ như cá) vào
những thời gian rảnh rỗi.
Phương pháp lọc cộng tác có thể được giải quyết bằng phương pháp học máy
khác nhau (như mạng nơ-ron nhân tạo) kết hợp với kỹ thuật phân tách đặc trưng
(như sự phân tích giá trị đơn lẻ - một kỹ thuật đại số làm giảm chiều của những ma
trận) có thể được sử dụng. Các tác giả đã đi so sánh phương pháp dựa trên mô hình
tương ứng của chúng với phương pháp dựa trên bộ nhớ chuẩn và sau đó ghi lại
chúng và thấy rằng trong một vài ứng dụng, phương pháp dựa trên mô hình thực
hiện tốt hơn phương pháp dựa trên bộ nhớ tính theo mức độ chính xác của những tư
18
vấn. Tuy nhiên, việc so sánh cả hai trường hợp này hoàn toàn đều do kinh nghiệm
mà không có học thuyết nào chứng minh khẳng định này.
Sự khác biệt chính giữa kỹ thuật dựa trên mô hình cộng tác và những phương