HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN 1

-----------------  ----------------

ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
Đề tài: KẾT HỢP LỌC CỘNG TÁC VÀ MÔ HÌNH

ĐÁM MÂY CHO TƯ VẤN LỰA CHỌN

Giảng viên hướng dẫn
Sinh viên thực hiện
Lớp
Khóa
Hệ

:
:
:
:
:

PGS.TS TRẦN ĐÌNH QUẾ
PHẠM VĂN LINH
D07CNPM2
10 (2007-2012)
Đại học chính qui

Hà Nội, tháng 12/ 2011


Hà Nội, tháng 12/ 2011


LỜI CẢM ƠN
Trước tiên, em xin gửi lời biết ơn sâu sắc nhất tới Thầy giáo PGS.TS Trần Đình
Quế, người đã tận tình chỉ bảo, hướng dẫn, nhắc nhở em trong suốt quá trình học tập
và hoàn thành đồ án này.
Em xin gửi lời cảm ơn chân thành tới tất cả quý Thầy, Cô đang giảng dạy trong
khoa Công nghệ thông tin cùng toàn thể Thầy, Cô trong trường Học viện Công Nghệ
Bưu Chính Viễn Thông đã tận tình truyền đạt những kiến thức quý báu giúp em hoàn
thành nhiệm vụ học tập trong suốt thời gian là sinh viên của trường.
Cho con gửi lời cảm ơn chân thành đến bố mẹ, ông bà đã luôn động viên, ủng hộ,
cổ vũ và tạo mọi điều kiện cho con trong suốt những năm tháng con ngồi trên ghế nhà
trường.
Cho tôi gửi lời cảm ơn đến những người bạn của tôi, những người luôn chia sẻ,
động viên, giúp đỡ và luôn ở bên tôi mỗi khi tôi gặp khó khăn trọng học tập cũng như
trong đời sống.
Xin chân thành cảm ơn!

Hà Nội, tháng 12 năm 2011
Sinh viên thực hiện

Phạm Văn Linh

i


MỤC LỤC
CÁC THUẬT NGỮ VIẾT TẮT...........................................................................................v
CHƯƠNG 1: TỔNG QUAN HỆ TƯ VẤN..........................................................................3

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
ii


…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
…………………………………………………………………………………………....
Điểm: …………………….………(bằng chữ: …..…………… ….)
Hà nội, ngày tháng
năm 2011
Giáo viên hướng dẫn

Hà nội, ngày tháng
năm 2011
Giáo viên phản biện
(ký, họ tên)

iv


CÁC THUẬT NGỮ VIẾT TẮT

Từ viết tắt

Tiếng Anh

Tiếng Việt

User_CF

Collaborative Filtering Base
on User

Lọc cộng tác dựa trên người dùng

CM_CF

Cloud model Collaborative
Filtering

Lọc cộng tác dựa trên mô hình
đám mây


SVD

Singular Value
Decomposition

Phân tích giá trị đơn

v


DANH MỤC CÁC HÌNH
Hình 1.1: Hệ thống tư vấn MovieLens..................................................................................5
Hình 1.2: Website amazon.com............................................................................................6
Hình 1.3: Quá trình lọc cộng tác.........................................................................................14
Hình 1.4: Ma trận người dùng sản phẩm............................................................................15
Hình 2.1 Kiến trúc hệ thống kết hợp lọc cộng tác và mô hình đám mây............................26
Hình 3.1: biểu đồ so sánh các giá trị MAE của các thuật toán khi thay đổi kích thước tập
láng giềng..................................................................................................................................43
Hình 3.2: biểu đồ so sánh các giá trị MAE của thuật toán khi thay đổi kích thước tập láng
giềng và độ đo tương tự............................................................................................................44
Hình 3.3: Biểu đồ so sánh giá trị MAE của các thuật toán khi thay đổi mức độ thưa thớt
của tập dữ liệu...........................................................................................................................46

DANH MỤC CÁC BẢNG
vi


Bảng 2.1: ví dụ xếp hạng các sản phẩm..............................................................................33
Bảng 3.1: bảng giá trị kích thước tập láng giềng K và giá trị MAE tương ứng..................43

dữ liệu xếp hạng bằng cách loại bỏ những người dùng hoặc những sản phẩm không
được quan tâm. Để đạt được hiệu quả tư vấn cao, yêu cầu thuật toán phải giải quyết
được các vấn đề cũng như các đặc trưng của hệ tư vấn.
Các hệ thống tư vấn dựa trên lọc cộng tác cũng phải đưa ra các tư vấn trong thời
gian thực. Tuy nhiên, thuật toán lọc cộng tác đòi hỏi tính toán rất tốn kém và phát triển
phi tuyến với cả số lượng người dùng và sản phẩm. Khả năng mở rộng kém của các
thuật toán lọc cộng tác làm cho nó không có hiểu quả cho việc thực thi thời gian thực.
đã có nhiều nỗ lực được thực hiện nhằm giải quyết vấn đề khả năng mở rộng
Những năm gần đây, nhiều nhà nghiên cứu đã khẳng định hiệu quả của việc kết hợp
mô hình đám mây vào quá trình lọc cộng tác [11]. Phương pháp tiếp cận lọc cộng tác
dựa trên mô hình đám mây nhằm giải quyết vấn đề thưa thớt dữ liệu và khả năng mở
rộng thông qua xây dựng sở thích toàn cục của người dùng thể hiện bởi vector đặc
trưng đám mây. Phương pháp này có thể làm giảm số chiều của dữ liệu và tránh sự kết
hợp chặt chẽ của các thuộc tính khi tính độ tương tự. Tuy nhiên, việc sử dụng sở thích
1


toàn cục đối với việc tính độ tương tự có thể mất một số thông tin về xếp hạng của mỗi
cá nhân. Những phương pháp đo độ tương tự truyền thống không thể tính được độ
tương tự giữa hai người dùng nếu họ không cùng xếp hạng bất kỳ sản phẩm nào.
Phương pháp tiếp cận lọc cộng tác dựa trên mô hình đám mây giải quyêt vấn đề bằng
cách đưa ra độ đo tương tự toàn cục. Mặc dù mô hình đám mây có thể nâng cao độ che
phủ dự đoán của thuật toán lọc cộng tác, nó có thể làm giảm độ chính xác dự đoán.
Mục đích đồ án là tìm hiểu kỹ thuật lọc cộng tác áp dụng cho hệ tư vấn lựa chọn.
Giới thiệu và đánh giá thử nghiệm thuật toán kết hợp lọc cộng tác và mô hình đám
mây cho hệ tư vấn, nhằm cải thiện chất lựợng tư vấn và khắc phục vấn đề thưa thớt dữ
liệu.
Nội dung của đồ án gồm có:
• Tìm hiểu hệ tư vấn và lọc cộng tác cho hệ tư vấn lựa chọn.
• Tìm hiểu thuật toán kết hợp lọc cộng tác và mô hình đám mây cho hệ tư vấn lựa

Nội dung chương này trình bày tổng quan về hệ tư vấn, các chức năng của hệ tư vấn
đối với người sử dụng và nhà cung cấp dịch vụ, các kỹ thuật lọc cộng tác áp dụng cho
hệ tư vấn hiện nay cùng với ưu nhược điểm của các kỹ thuật này.

3


Đồ án tốt nghiệp Đại học

1.1.

Chương 1: Tổng quan hệ tư vấn

GIỚI THIỆU TỔNG QUAN VỀ HỆ TƯ VẤN

Trong cuộc sống thường ngày, mọi người thường dựa vào ý kiến hay lời khuyên
người khác để đưa ra quyết định về hành động hoặc lựa chọn, ví dụ như để lựa chọn bộ
phim mọi người có thể đọc giới thiệu tổng quát, bài đánh giá của các nhà phê bình điện
ảnh hoặc nhận xét của những người khác về bộ phim trên các tạp chí, Internet hoặc khi
muốn mua một cuốn sách, mọi người có thể tham khảo ý kiến của người quen, chủ cửa
hàng bán sách hoặc những người mua khác, bằng cách đưa ra sở thích, mối quan tâm
của mình với họ để nhận được góp ý.
Với sự phát triển của Internet và thương mại điện tử hiện nay, lượng thông tin có
sẵn là vô cùng lớn, điều đó gây khó khăn và rất tốn thời gian để người dùng tìm kiếm
thông tin và lựa chọn sản phẩm. Yêu cầu cần có phương pháp thu thập thông tin và đưa
ra lời khuyên để hỗ trợ người dùng trong vấn đề tìm kiếm và lựa chọn sản phẩm họ
quan tâm. Hệ tư vấn là một giải pháp được đưa ra cho vấn đề này
Hệ tư vấn là các kỹ thuật (lọc thông tin) và các công cụ phần mềm cung cấp các
đề xuất sản phẩm có thể được quan tâm tới người dùng. Các đề xuất này có thể giúp
ích cho quá trình đưa ra quyết định lựa chọn sản phẩm của người dùng, như lựa chọn

xếp hạng các sản phẩm. để có thể tạo ra được danh sách đó, các hệ 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 với người dùng dựa trên sở thích và các
điều kiện rằng buộc của người dùng , để làm được điều này, các hệ tư vấn thu thập
thông tin liên quan tới người dùng : sở thích, các lần đánh giá về các sản phẩm , hoặc
được suy luận từ các hành vi của người dùng đối với hệ thống hoặc tận dụng các tư vấn
đã được tạo bởi cộng đồng người dùng để tư vấn cho người dùng đang hoạt động
(active user), người mà cần được tư vấn. Kết quả tư vấn là các sản phẩm mà những

6


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn

người dùng tương tự đã thích, các sản phẩm này có thể hoàn toàn mới đối với người
dùng được tư vấn. Phương pháp tiếp cận này được gọi là kỹ thuật lọc cộng tác.
Nghiên cứu các hệ tư vấn liên quan tới các kỹ thuật và các công cụ hệ thống phân
lớp thông tin. Tuy nhiên các hệ tư vấn được nghiên cứu độc lập từ những năm 1990.
Những năm gần đây sự quan tâm về các hệ tư vấn đã gia tăng nhanh chóng, được thể
hiện [1]:
•

Các hệ tư vấn đóng vai trò quan trọng trong các website đã được đánh giá
cao như: amazon.com, youtube.com, yahoo . . . Hơn nữa nhiều công ty đa
phương tiện hiện nay đang phát triển và triển khai các hệ tư vấn như một
phần dịch vụ mà học cung cấp tới khách hàng của họ. Ví dụ Netflix, dịch vụ
cho thuê phim trực tuyến, họ đưa ra giải thưởng 1 triệu dollar cho nhóm đầu
tiên cải thiện đáng kể hiệu năng hệ tư vấn của họ (cải thiện 10% hiệu năng ).


7


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn

1.1.1.1 Đối với nhà cung cấp
Trên thực tế, có nhiều lý do để nhà cung cấp dịch vụ muốn khai thác công nghệ
này. FrancescoRicci và cộng sự [1] đã đưa ra một số lí do như sau:
• Tăng số lượng sản phẩm bán được: đây có lẽ là chức năng quan trọng nhất đối với
các hệ tư vấn thương mại điện tử, mục đích này đạt được do các sản phẩm được tư
vấn phù hợp với các sản phẩm mà người dùng cần và người dùng mong muốn, có
thể người dùng sẽ chấp nhận mua sau khi xem tư vấn từ hệ thống. Nói chung, ta có
thể nói nhìn từ quan điểm của các nhà cung cấp dịch vụ, mục đích chính của việc
đưa ra một hệ tư vấn là làm tăng tỷ lệ giữa giữa lượng khách hàng mua sản phẩm và
lượng khách hàng truy cập chỉ để duyệt tìm thông tin.
• Bán được các sản phẩm đa dạng hơn: chức năng này của hệ tư vấn cho phép người
dùng lựa chọn các lựa chọn các sản phẩm mà có thể rất khó để tìm thấy nếu như
không có tư vấn chính xác. Ví dụ, trong hệ tư vấn phim của Netflix, nhà cung cấp
quan tấm tới cho thuê tất cả DVD của họ , chứ không chỉ những DVD nổi tiếng,
điều này có thể rất khó nếu như không có hệ tư vấn, họ có thể gặp rủi ro trong việc
quảng cáo các bộ phim không phù hợp với thị hiếu của người dùng. Như vậy, một
hệ tư vấn đề xuất hoặc quảng cáo được những DVD không nổi tiếng nhưng phù hợp
với người dùng.
• Nâng cao sự hài lòng của người dùng: Một hệ thống tư vấn được thiết kế tốt có thể
hoàn thiện kinh nghiệm sử dụng web hoặc ứng dụng của người dùng. Với tương tác
người máy hợp lý, người dùng có thể thấy được các tư vấn một cách dễ ràng, phù
hợp với thị hiếu của họ. Như vậy họ sẽ thích sử dụng hệ thống. Sự kết hợp hiệu quả
giữa các tư vấn và giao diện sử dụng sẽ làng tăng lượng đánh giá chủ quan của

• Tìm ra tất cả sản phẩm tốt: tư vấn tất cả sản phẩm mà có thể làm hài lòng nhu cầu
của khách hàng. Trong nhiều trường hợp không đủ cơ sở để đưa ra các sản phẩm tốt
nhất. Điều này chỉ đúng khi số lượng sản phẩm liên quan tương đối nhỏ hoặc khi hệ
tư vấn là chức năng quan trọng trong ứng dụng tài chính và y tế.
• Tư vấn liên tục: thay vì tập trung vào tạo tư vấn đơn, các hệ thống tư vấn tạo các tư
vấn liên tục tới người dùng cho tới khi họ tìm được sản phẩm mong muốn.
• Tư vấn một nhóm sản phẩm: đề xuất một nhóm các sản phẩm mà tương đương
nhau. Ví dụ như kế hoạch du lịch có thể là gồm nhiều điểm đến, các dịch vụ nơi ở ,
các sự kiện hấp dẫn. Từ quan điểm của người dùng những lựa chọn khác nhau có
thể được xem xét và được lựa chọn một điểm đến du lịch hợp lý.
• Chỉ duyệt tìm: trong tác vụ này, người dùng duyệt các danh mục mà không có ý
định mua sản phẩm nào, tác vụ này đưa ra tư vấn giúp người dùng duyệt tìm các
sản phẩm có nhiều khả năng thuộc vào phạm vi sở thích của người dùng với phiêm
truy cập xác định. Đây là tác vụ được hỗ trợ bởi các kỹ thuật đa phương tiện.
• Tìm kiếm các tư vấn tin tưởng: một số người dùng không tin tưởng vào các hệ
thống tư vấn, họ tham gia vào hệ thống để thấy được các hệ thống này đưa ra tư vấn
tốt tới mức nào. Do đó, một số hệ thống có thể đưa ra các chức năng chính xác để
cho phép họ thử nghiệm hành vi của họ, ngoài các yêu cầu tư vấn.
• Cải thiện hồ sơ cá nhân người dùng: người dùng có khả năng cung cấp thông tin,
những gì họ thích, không thích với hệ thống tư vấn. Điều này là hết sức cần thiết để
đưa ra các tư vấn mang tính chất cá nhân hóa. Nếu như hệ thống không xác định tri
thức về người dùng đang hoạt động thì nó chỉ có thể đưa ra các tư vấn giống nhau.

9


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn


chưa thể liệt kê hết tất cả miền ứng dụng mà được giải quyết bằng các kỹ thuật tư vấn,
nó đưa ra miêu tả ban đầu về các kiểu miền ứng dụng.

10


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn

Nhà phát triển hệ tư vấn có hiểu biết về miền ứng dụng, các yêu cầu của nó cũng
như những thách thức và các hạn chế của nó. Chỉ sau khi phân tích những yếu tố họ
mới có thể lựa chọn được thuật toán tư vấn tối ưu và thiết kế tương tác người máy hiệu
quả.
1.1.3. Các vấn đề cơ bản của hệ tư vấn
1.1.3.1.

Vấn đề điểm khởi đầu yếu

Vấn đề này liên quan đặt biệt với các vấn đề mà hệ thống không thể thực hiện bất
kỳ kết luận cho người dùng hoặc sản phẩm do hệ thống chưa thu thập đủ thông tin.
Vấn đề này chủ yếu gặp phải trong các hệ tư vấn. Thông thường, một hệ tư vấn so sánh
hồ sơ của các người dùng để tham khảo một số đặc điểm mà có thể thu được từ các
phương pháp lọc cộng tác hoặc phương pháp lọc nội dung. Hệ thống không thể tạo các
tư vấn hữu ích khi mà nó chưa có đủ thông tin về người dùng hoặc sản phẩm.
Ba kiểu vấn đề điểm bắt đầu yếu gồm: sản phẩm mới, người dùng mới, hệ thống
mới đưa vào sử dụng. Rõ ràng, vấn đề người dùng mới xảy ra khi một người dùng mới
sử dụng hệ thống và hệ thống không có đủ thông tin về sở thích của người dùng.
Tương tự, khi một sản phẩm mới được thêm vào hệ thống và chưa có người dùng nào
trong hệ thống cung cấp thông tin phản hồi về sản phẩm này. Vấn đề hệ thống mới đưa

xây dựng ma trận người dùng – sản phẩm chứa các xếp hạng sản phẩm được người
dùng đưa ra. Khi số lượng người dùng và sản phẩm tăng lên, ma trận này cũng lớn hơn
và gặp phải vấn đề thưa thớt dữ liệu. Có nhiều phương pháp được đề xuất để giải quyết
vấn đề thưa thớt dữ liệu. Hầu hết chúng đề thành công trong việc cung cấp các tư vấn
tốt hơn nhưng vẫn chưa có một mô hình chung để giải quyết vấn đề thưa thớt dữ liệu
[5].
1.1.3.3. Vấn đề về khả năng mở rộng
Khả năng mở rộng là một tính chất mong đợi của các hệ thống mà chỉ ra khả năng
xử lý lượng công việc này càng lớn và mở rộng dễ dàng.
Đối với nhiều hệ thống tư vấn có nhiều người sử dụng và nhiều sản phẩm, duy trì
khả năng mở rộng là một vấn đề thánh thức. Các thuật toán láng giềng gần nhất được
sử dụng rộng rãi cho các hệ tư vấn và những thuật toán này yêu cầu tính toán một
lượng lớn cả người dùng và sản phẩm. Với một triệu người dùng và sản phẩm, một hệ
tư vấn trên web sẽ bị ảnh hưởng nghiêm trọng bởi vấn đề khả năng mở rộng.
Hầu hết các hệ tư vấn sử dụng các kiểu lọc cộng tác khác nhau để xây dựng các đề
xuất các sản phẩm liên quan đến mối quan tâm của người dùng. Tuy nhiên, các kỹ
thuật lọc cộng tác yêu cầu tính toán nhiều tùy theo số lượng người dùng và sản phẩm
trong có sở dữ liệu. Các phương pháp đề xuất để xử lý vấn đề khả năng mở rộng và
thúc đẩy xây dựng các tư vấn dựa trên cơ chế xấp xỉ. Ngay cả khi chúng ta cải tiến hiệu
năng, hầu hết kết quả đưa ra giảm tính chính xác.
1.2.

CÁC KỸ THUẬT LỌC CỘNG TÁC

Các hệ tư vấn được giới thiệu như một kỹ thuật thông minh dựa trên máy tính để
giải quyết các vấn đề quá tải thông tin và sản phẩm. Chúng có thể được sử dụng cung
cấp các dịch vụ hiệu quả trong các miền nghiệp vụ điện tử, có lợi cả với khách hàng và
nhà buôn. Các hệ tư vấn đối với khách hàng bằng cách đưa ra cho họ các đề xuất về

12



Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn

Hình 1.3: Quá trình lọc cộng tác
Mục tiêu của các hệ tư vấn là tạo ra các đề xuất về các sản phẩm mới hoặc để dự
đoán sử dụng một sản phẩm xác định cho một người dùng cụ thể. Trong cả hai trường
hợp quá trình đều dựa trên đầu vào được cung cấp liên quan tới sở thích của người
dùng.
Với m là số lượng người dùng tập người dùng U = {u1 , u2 ,..., um } và n à số sản phẩm
I ={i1 , i2 ,..., in } , với mỗi người dùng ui với i=1,2,…,m đều có một danh sách các sản

phẩm

I ui

, thể hiện các ý kiến đánh giá của người dùng u i về các sản phẩm. Lưu ý

quan trọng đó là

I ui ⊆ I

,

I ui

có thể là tập null, điều đó có nghĩa không bắt


cung cấp bởi người dùng đang hoạt động ua . Dạng hệ thống tư vấn này đầu ra
cũng được biết như Individual Scoring.
• Tư vấn: được thể hiện như một danh sách N sản phẩm, với N ≤ n, mà được dự tính
rằng người dùng đang hoạt động thích nhất. Các hệ thống tư vấn đầu ra dạng này
còn được biết đến với tên Tư vấn N sản phẩm xếp hạng đầu hoặc Ranked Scoring.
Các thuật toán lọc cộng tác có thể được chia thành 2 loại chính: lọc cộng tác dựa
trên bộ nhớ và dựa trên mô hình.
• Các thuật toán lọc cộng tác dựa trên bộ nhớ: các thuật toán dựa trên bộ nhớ sử
dụng toàn bộ cơ sở dữ liệu người dùng – sản phẩm để tạo một dự đoán. Những hệ
thống này sử dụng các kỹ thuật thống kê để tìm một tập các người dùng, được biết
như các láng giềng, mà có lịch sử phù hợp với người dùng đích. Những hệ thống
này sử dụng các thuật toán khác nhau để kết hợp các sở thích của các láng giềng để
tạo một dự đoán hoặc tư vấn N sản phẩm cho active user. Các kỹ thuật, được biết
như lọc cộng tác dựa trên người dùng hoặc láng giềng gần nhất được sử dụng rộng
rãi và phổ biến trong thực tế.
• Các thuật toán lọc cộng tác dựa trên mô hình: các thuật toán lọc cộng tác dựa
trên mô hình hỗ trợ tư vấn sản phẩm bằng cách, trước tiên phát triển một mô hình
các đánh giá của người dùng. Các thuật toán thuộc loại này đưa ra một phương
pháp tiếp cận xác suất và hình dung quá trình lọc cộng tác như tính toán giá trị được
dự đoán của một dự đoán của người dùng, đưa ra các đánh giá của họ trên những
15


Đồ án tốt nghiệp Đại học

Chương 1: Tổng quan hệ tư vấn

sản phẩm khác. Quá trình xây dựng mô hình được thực hiện bằng các thuật toán
học máy khác nhau như Bayesian network, clustering và các phương pháp tiếp cận
dựa trên luật. Mô hình mạng Bayesian xây dựng một mô hình xác suất cho vấn đề

được tính là {si1 , si 2 ,..., sik } . Những sản phẩm tương nhất được tìm ra, sau đó tính dự
đoán bằng cách trung bình theo trọng số các đánh giá của target user trên những sản
phẩm tương tự đó.

16