i
i
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

ii

MỤC LỤC

LỜI CẢM ƠN i
MỤC LỤC ii
DANH MỤC HÌNH ẢNH v
DANH MỤC CÁC TỪ VIẾT TẮT vii
PHẦN MỞ ĐẦU 8
1. Tính cấp thiết của đề tài 8
2. Mục tiêu, nhiệm vụ, đối tượng nghiên cứu 9
3. Phạm vi nghiên cứu 10
4. Phương pháp nghiên cứu 10
5. Kết cấu đề tài 11
Chương 1: TỔNG QUAN VỀ HỆ TƯ VẤN VÀ PHƯƠNG PHÁP
LỌC CỘNG TÁC 12
1.1. Tổng quan về hệ tư vấn 12
1.1.1. Giới thiệu về hệ tư vấn 12

3.1.1. Mô tả bài toán 43
3.1.2. Mô tả về bộ dữ liệu MovieLens 43
3.1.3. Ưu, nhược điểm của bộ dữ liệu MovieLens 45
3.2. Ngôn ngữ lập trình Objective-C và thư viện đồ hoạ OpenGL 46
3.2.1. Ngôn ngữ lập trình Objective-C 46
3.2.2. Thư viện đồ hoạ OpenGL 47
3.3. Cài đặt hệ thống 49
3.3.1. Các yếu tố đầu vào 49
3.3.2. Các yếu tố đầu ra 50
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

iv

3.3.3. Quy trình hoạt động 50
3.4. So sánh, đánh giá mô hình đa tác tử hút và đẩy với phương pháp lọc cộng tác 58
KẾT LUẬN 60
DANH MỤC TÀI LIỆU THAM KHẢO 61

Hình 2.6. Quản lý lực quán tính trong mô hình 36
Hình 2.7. Các cách chọn láng giềng 37
Hình 2.8. Tính chất lực và độ mạnh lực dựa trên độ tương tự và khoảng cách
(cách tiếp cận rời rạc) 39
Hình 2.9. Tính chất lực và độ mạnh lực dựa trên độ tương tự và khoảng cách
(cách tiếp cận liên tục) 39
Hình 2.10. Ví dụ về phản ứng của một tác tử với hai láng giềng 40
Hình 3.1. Ngôn ngữ lập trình Objective-C 46
Hình 3.2. Thư viện đồ họa OpenGL 48
Hình 3.3. Ảnh đại diện của phim / tác tử 49
Hình 3.4. Sơ đồ quy trình hoạt động 50
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

vi

Hình 3.5. Cách quản lý trên lưới của mô hình 52
Hình 3.6. Thuật toán chọn láng giềng lân cận. 53
Hình 3.7. Mô hình ở mức độ địa phương 54
Hình 3.8. Mô hình ở mức độ toàn cục 55
Hình 3.9. Thuật toán tính giá trị dự đoán. 57
Hình 3.10. Danh sách tư vấn phim 57
Hình 3.11. Biểu đồ biểu diễn kết quả MAE của 5 bộ dữ liệu kiểm tra 58
Hình 3.12. Biểu đồ biểu diễn kết quả MAE của hai phương pháp. 59 Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

8

PHẦN MỞ ĐẦU

1. Tính cấp thiết của đề tài
Trong kỷ nguyên của sự bùng nổ thông tin, internet với các tiện ích của nó đang
có ảnh hưởng lớn đối với cộng đồng sử dụng mạng. Với lượng thông tin khổng lồ, nhu
cầu người dùng ngày càng tăng thêm, người dùng cần có sự tư vấn chính xác và kịp thời
để có thể tìm kiếm thông tin một cách nhanh chóng và tiết kiệm thời gian một cách tối
đa. Có rất nhiều hệ tư vấn áp dụng đối với các website thuộc các lnh vực sách, âm nhạc,
phim ảnh,… Tuy nhiên, cuộc sống lại rất phong phú trong mọi lnh vực và một khi nhu
cầu đã quá lớn thì yêu cầu đặt ra cng s phải cao hơn rất nhiều.
Khi người dùng cần tìm kiếm thông tin về một sản phẩm nào đó, giải pháp được
sử dụng hầu hết là đưa câu hi vào máy tìm kiếm thay vì tìm đến những website/forum
chuyên ngành. Tuy nhiên, máy tìm kiếm không phải lúc nào cng hiệu quả. Máy tìm
kiếm ch có thể đưa ra một danh sách các lựa chọn (có thể lên đến hàng triệu) chứ không
thể nói được lựa chọn nào là tốt nhất.
Chẳng hạn, một khách hàng cần mua một đa phim hay, họ cần một vài cái tên
để tham khảo và lựa chọn, đa số họ s vào Google tìm kiếm thông tin nhưng với lượng
thông tin về các loại phim quá phong phú, lại không có nhiều thời gian để tìm hiểu tng

thông tin và cho phép người dùng có thể tương tác với nó. Trong đề tài này, tác giả s
vẫn giữ ý tưởng về việc sử dụng các tác tử với các lực hút và đẩy như trong nghiên cứu
nói trên nhằm tổ chức dữ liệu trong không gian 2 chiều và nghiên cứu để áp dụng mô
hình đa tác tử hút và đẩy thay thế cho hướng tiếp cận lọc cộng tác.
Xuất phát t tầm quan trọng của một hệ tư vấn hoàn chnh, những tồn tại cơ bản
của phương pháp lọc cộng tác là vấn đề cấp thiết và quan trọng nên tác giả quyết định
chọn: “Nghiên cứu mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác” làm
hướng nghiên cứu cho đề tài.
2. Mục tiêu, nhiệm vụ, đối tượng nghiên cứu
 Mục tiêu nghiên cứu
- Lý thuyết về hệ tư vấn và phương pháp lọc cộng tác.
- Lý thuyết về tác tử, hệ thống đa tác tử, mô hình đa tác tử hút và đẩy.
- Đề xuất mô hình đa tác tử hút và đẩy cho hướng tiếp cận lọc cộng tác.
- Nghiên cứu các công cụ, kỹ thuật, nền tảng lập trình được sử dụng để xây dựng
hệ thống.
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

10

- Xây dựng hệ thống thử nghiệm tư vấn phim sử dụng mô hình đa tác tử hút và đẩy
đã đề xuất.
- So sánh, đánh giá mô hình đa tác tử hút và đẩy với phương pháp lọc cộng tác.
 Nhiệm vụ nghiên cứu
Để đạt được mục đích nghiên cứu nêu ra ở trên, đề tài tập trung giải quyết các
nhiệm vụ chủ yếu sau:
Về mặt lí luận: 1) Phân tích, tổng hợp các kiến thức về hệ tư vấn bảo đảm tính

kiến thức cần thiết để bổ sung một cách chi tiết, cụ thể, t đó hoàn thiện khóa luận.
Phương pháp chủ động học hi: bản thân cần chủ động học hi những người xung
quanh nhằm thu thập thông tin và bổ sung kiến thức.
Phương pháp tổng hợp: hoàn thiện khóa luận dựa trên những kiến thức cơ bản đã
thu nhận được trong quá trình học tập ở trường, kiến thức thực tế trong chuyến đi thực
tập tại Trung tâm Công nghệ Thông tin Tha Thiên Huế và những tài liệu đã nhận được
ở Công ty cng như tài liệu chủ động tìm kiếm.
5. Kết cấu đề tài
Ngoài Phần mở đầu, Kết luận, Danh mục viết tắt, Danh mục bảng biểu, Danh
mục hình ảnh, Danh mục tài liệu tham khảo, nội dung của Báo cáo thực tế gồm 3 chương:
Chương 1: Tổng quan về hệ tư vấn và phương pháp lọc cộng tác. Chương
này s giới thiệu tổng quan về hệ tư vấn, các chức năng, thông tin, hướng tiếp cận và
phương pháp đánh giá hệ tư vấn.
Chương 2: Mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác.
Chương này đi sâu tìm hiểu lý thuyết về tác tử, hệ thống đa tác tử, mô hình đa tác tử sử
dụng lực hút và đẩy trong phân loại email và tìm kiềm ảnh; mô hình đa tác tử hút và đẩy
cho phương pháp lọc cộng tác.
Chương 3: Hệ thống thử nghiệm tư vấn phim sử dụng mô hình đa tác tử hút
và đẩy. Nội dung chương này đi vào phân tích hệ thống thử nghiệm được sử dụng trong
khóa luận, các bộ công cụ hỗ trợ lập trình, cách thức cài đặt hệ thống, so sánh, đánh giá
hệ thống với phương pháp lọc cộng tác.

Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

12

Sinh viên thực hiện: Nguyễn Minh Đức

13 Hình 1.1. Hệ tư vấn của trang web www.amazon.com.
Hiểu một cách đơn giản thì các tư vấn được cung cấp dưới dạng các danh sách
xếp hạng các mặt hàng. Trong việc thực hiện bảng xếp hạng này, hệ tư vấn cố gắng dự
đoán những 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 sử dụng.
Để hoàn thành một nhiệm vụ tính toán như vậy, hệ tư vấn thu thập t người sử dụng sở
thích của họ, ví dụ như đánh giá của người dùng cho các mặt hàng, sản phẩm.
Hệ tư vấn bắt đầu được chú ý t những quan sát sau: một người thường dựa trên
những lời khuyên, tư vấn t những người khác trong việc đưa ra các quyết định. Ví dụ,
người ta thường dựa vào lời giới thiệu của bạn b khi chọn mua sách để đọc, người sử
dụng lao động dựa trên thư giới thiệu để tuyển dụng và người xem dựa vào các đánh giá
phê bình phim của nhà phê bình phim trong các tạp chí để chọn phim xem.
Để bắt chước các hành vi này, các hệ tư vấn đầu tiên s áp dụng các thuật toán
để tận dụng các đánh giá được đưa ra bởi một cộng đồng người sử dụng nhằm cung cấp
các tư vấn cho một người dùng cần tư vấn. Hệ thống s tư vấn các mặt hàng mà người
dùng tương tự (những người có sở thích tương tự) đã thích. Cách tiếp cận này gọi là lọc
cộng tác, tức là khi người dùng cần tư vấn có những tương đồng trước đó trong quá khứ
với một số người dùng khác, khi đó các tư vấn khác s đến t những người sử dụng
tương tự.
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

s nhận diện người dùng c và tương tác với người dùng đó như một người truy
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

15

cập có giá trị. Hệ tư vấn s sử dụng lịch sử của người dùng c này để đưa ra các
lời tư vấn chính xác.
 Hiu r hơn về nhng gì ngưi dng mun: Đây là một chức năng quan
trọng của một hệ tư vấn, hệ thống s mô tả sở thích của người sử dụng thành một
dữ liệu có tổ chức. Sau đó, nhà cung cấp dịch vụ có thể quyết định tái sử dụng
dữ liệu này cho một số mục tiêu khác như cải thiện việc quản lý kinh doanh hoặc
đề ra các ý tưởng mới.
Bên cạnh đó, các chức năng quan trọng của hệ tư vấn đối với người sử dụng hệ
thống đó là:
 Tìm một s nhm hàng tt: Tư vấn cho người dùng một số mặt hàng dưới
dạng một danh sách xếp hạng cùng với dự đoán bao nhiêu người dùng muốn sử
dụng chúng.
 Tìm tt c các mặt hàng tt: Tư vấn tất cả các mặt hàng có thể đáp ứng
một số nhu cầu của người sử dụng.
 Chú thch trong ng cnh: Tùy vào ngữ cảnh nhất định s có một danh
sách nhấn mạnh các mặt hàng cụ thể nào đó tùy thuộc vào nhu cầu và sở thích
của số đông người dùng.
 Tư vn một chui các mặt hàng: Thay vì tập trung vào một tư vấn duy
nhất, ý tưởng của hệ tư vấn là để giới thiệu một chuỗi các mặt hàng s thu hút
hơn. Ví dụ điển hình như giới thiệu một loạt phim truyền hình, một cuốn sách về
hệ tư vấn sau khi đã giới thiệu một cuốn sách về khai thác dữ liệu.

tin, ví dụ như: đánh giá cho các mặt hàng (Ratings), bởi vì họ tin rằng đóng góp
của họ s có ích. Điều này có thể là một động lực lớn để nhập thông tin thành
một hệ thống tư vấn. Ví dụ: với một hệ tư vấn về xe, một người dùng đã mua một
chiếc xe mới thì họ nhận thức được rằng ý kiến đánh giá của mình về chiếc xe đó
có thể s hữu ích cho người khác.
 nh hưng nhng ngưi khác: Đối với hệ tư vấn trên website, người dùng
có mục tiêu r ràng chính là người ảnh hưởng đến những người dùng khác vào
mua các sản phẩm. Cng có một số người sử dụng có thể sử dụng hệ thống ch
để thúc đẩy hoặc hạ thấp một số mặt hàng theo ý riêng của họ.
Như những điểm khác nhau trong chức năng của hệ tư vấn, ta thấy vai trò của
một hệ tư vấn trong một hệ thống thông tin là khá đa dạng. Sự đa dạng này s là khởi
đầu cho việc khai thác một loạt các nguồn kiến thức và các kỹ thuật khác nhau.
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

17

1.1.3. Các thông tin được sử dụng trong hệ tư vấn
Hệ tư vấn là hệ thống xử lý thông tin thu thập t các loại dữ liệu khác nhau để
xây dựng các tư vấn. Dữ liệu chủ yếu là về các mặt hàng cần tư vấn và người dùng s
nhận được các tư vấn này. Tuy nhiên, dữ liệu và các nguồn tri thức sn có cho các hệ
thống tư vấn có thể rất đa dạng. Trong bất k trường hợp nào, dữ liệu được sử dụng bởi
hệ tư vấn thuộc ba loại: Sn phẩm (Item), ngưi sử dng (User), và các giao dch
(Transactions) - đó chính là quan hệ giữa người sử dụng và các mặt hàng.
Sn phẩm (Item): Sản phẩm là các đối tượng được tư vấn. Các sản phẩm này đặc
trưng bởi tiện ích và giá trị của nó. Giá trị của một mặt hàng có thể là tích cực nếu hữu
ích cho người sử dụng, hoặc tiêu cực nếu chúng không phù hợp với người sử dụng.

người sử dụng đã cung cấp, chẳng hạn như đánh giá cho các sản phẩm được chọn.
Trong thực tế, xếp hạng là hình thức phổ biến nhất của các dữ liệu giao dịch trong
hệ tư vấn. Những đánh giá này có thể được thu thập một cách r ràng hoặc ngầm định.
Người dùng s được yêu cầu cung cấp ý kiến của mình về một mặt hàng theo một thang
đánh giá. Ví dụ như: Xếp hạng số t 1-5 sao; Xếp hạng theo thứ tự, chẳng hạn: "hoàn
toàn đồng ý, đồng ý,…”,
Một kịch bản tư vấn điển hình được thể hiện trong hình 1.2. Ta có tập n người
dùng U = {u
1
, u
2
, , u
n
} và tập m sản phẩm I = {i
1
, i
2
, , i
m
}. Mỗi người dùng u
i
có thể
có dữ liệu nhân khẩu học và một danh sách các sản phẩm 


(vớI 


 và 


gọi là người dùng cần tư vấn (active user), được lấy t các sản phẩm chưa được bình
chọn tường minh bởi người dùng đó. Mặt khác, hệ thống có thể đề xuất một sản phẩm
mới, 

, cho những người dùng có thể quan tâm.
1.1.4. Các hướng tiếp cận của hệ tư vấn
Để thực hiện chức năng tư vấn, một hệ tư vấn phải dự đoán được một mặt hàng
để tư vấn. Muốn làm được điều này, hệ thống phải dự đoán sở thích của một số người
hoặc so sánh công dụng, chức năng của một số mặt hàng sau đó đưa ra các mặt hàng tư
vấn cho người dùng dựa trên sự so sánh này. Sử dụng các thuật toán tư vấn có thể đưa
ra các mặt hàng tư vấn không hoàn toàn chính xác, tuy nhiên chúng ta vẫn có thể áp
dụng nó để mô tả vai trò chung của một hệ tư vấn.
Dựa vào loại dữ liệu và kỹ thuật được sử dụng để đi đến quyết định tư vấn, hệ
thống tư vấn có thể được phân loại thành các hướng tiếp cận sau đây:
1) Lọc cộng tác
Tiếp cận tư vấn lọc cộng tác còn được gọi là lọc xã hội hoặc tiếp cận dựa trên sự
tương đồng giữa người dùng với người dùng. Hệ thống lọc cộng tác xác định những
người dùng có sở thích tương tự với người dùng cần tư vấn và các sản phẩm mà họ đã
thích được chọn để tư vấn. Với phương pháp này, sở thích của người dùng s là đầu vào
cho các quyết định tư vấn.
Các hệ thống lọc cộng tác hoạt động bằng cách tập hợp các đánh giá của người
dùng cho các sản phẩm trong một miền xác định và đo lường sự tương tự trong hành vi
đánh giá giữa một số người dùng nhằm xác định cách tư vấn cho một sản phẩm.
Các phương pháp lọc cộng tác có thể được phân thành những tiếp cận nh hơn
như các hướng tiếp cận dựa trên láng giềng (neigborhood-based) và dựa trên mô hình
(model-based).
Khoá luận tốt nghiệp


21

3) Phương pháp lai
Mặc dù đã đạt được một số hiệu quả nhất định, nhưng phương pháp lọc cộng tác
vẫn tồn tại nhiều hạn chế như vấn đề thưa thớt dữ liệu, sự thay đổi của dữ liệu, cng như
độ phức tạp tính toán và thời gian. Bên cạnh đó, vấn đề bộ nhớ luôn là nhược điểm của
phương pháp tư vấn dựa trên nội dung. Để có thể tận dụng những điểm mạnh của các
kỹ thuật này, đồng thời hạn chế các khuyết điểm của chúng, phương pháp lai sử dụng
đồng thời cả hai phương pháp trên để có kết quả tư vấn tốt hơn.
1.1.5. Phương pháp đánh giá hệ tư vấn
Chất lượng của một hệ tư vấn có thể được đánh giá bằng việc so sánh các tư vấn
với một tập mẫu kiểm tra, với các giá trị bình chọn của người dùng là đã biết, bằng cách
sử dụng các phép đo độ chính xác dự đoán. Phương pháp đo lường được sử dụng phổ
biến nhất là sai số tuyệt đối trung bình (Mean Absolute Error - MAE) được định ngha
như là sự sai khác trung bình giữa các giá trị bình chọn đã dự đoán được với các giá trị
bình chọn thực sự theo công thức:










Trong đó 

là giá trị bình chọn được dự đoán cho người dùng u cho sản phẩm i, 

1.2. Phương pháp lọc cộng tác
1.2.1. Tổng quan
Lọc cộng tác (Collaborative Filtering) là kỹ thuật được áp dụng khá thành công
trong các hệ tư vấn, nó được dùng để đánh giá độ quan tâm của người dùng tới một mặt
hàng mới. Trong các hệ thống lọc cộng tác, các dự đoán được đưa ra dựa trên tập dữ liệu
về sở thích người dùng – mặt hàng có liên quan tới người dùng hoặc mặt hàng. Tuy nhiên,
trong trường hợp dữ liệu ít, độ tương tự trực tiếp giữa hai người dùng hoặc hai mặt hàng
ch cung cấp rất ít thông tin cho ta dự đoán.

Hình 1.4. Hệ thống tư vấn lọc cộng tác trên trang web www.amazon.com
Phương pháp tư vấn lọc cộng tác hoàn toàn khác so với phương pháp tư vấn dựa
trên nội dung. Thay vì giới thiệu các mặt hàng, vì chúng tương tự như các mặt hàng người
dùng đã thích trong quá khứ, cách tiếp cận lọc cộng tác tư vấn các mặt hàng dựa vào ý
kiến của những người dùng khác. Thông thường, bằng cách tính toán sự giống nhau của
những người sử dụng, một tập hợp láng giềng gần nhất (nearest neighbor) các người dùng
có sở thích tương quan đáng kể với một người dùng nhất định s được tìm thấy. Như vậy,
trong phương pháp này, người dùng chia s sở thích của họ về tng mặt hàng mà họ đã
tng tiêu dùng để những người dùng khác của hệ thống có những quyết định tốt hơn đối
với những mặt hàng đó.
Lọc cộng tác có thể được phân thành những tiếp cận nh hơn như hướng tiếp cận
dựa trên láng giềng (neigborhood-based) và dựa trên mô hình (model-based).
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

23

1.2.2. Lọc cộng tác dựa trên láng giềng





















Trong đó, I là tập các sản phẩm được bình chọn bởi cả hai người dùng, 

là bình chọn
được gán cho sản phẩm i bởi người dùng u, và 

 là giá trị bình chọn trung bình được
cho bởi người dùng u.
Một số cách đo độ tương tự khác cng đã được nghiên cứu, như: H s tương
quan Spearman, H s tương quan ca Kendall, Sai phn bình phương trung bình,
Entropy, Độ tương tự cosin, Độ tương tự cosin điều chnh. Về bản chất, những độ đo

Trong đó 

là giá trị dự đoán cho người dùng cần tư vấn a đối với sản phẩm i, 

là
độ tương tự giữa hai người dùng a và u, và K là láng giềng hoặc tập những người dùng
có độ tương tự cao nhất.
Lọc cộng tác dựa trên sn phẩm: Khi được áp dụng cho hàng triệu người dùng
và sản phẩm, các giải thuật lọc cộng tác dựa trên láng giềng gặp phải một số hạn chế về
độ phức tạp trong việc tính toán độ tương tự giữa những người dùng. Trong một hướng
nghiên cứu khác, thay vì lựa chọn ra những người dùng tương tự thì chuyển sang tìm
kiếm các sản phẩm được bình chọn tương tự. Tiếp cận này giúp cho các hệ thống trực
tuyến hoạt động nhanh hơn, và thường cải tiến được chất lượng của các lời tư vấn.
Trong tiếp cận này, độ tương tự giữa các cặp sản phẩm i và j được tính toán nội
tuyến (offline) sử dụng độ tương quan Pearson như sau:























Trong đó K là tập các láng giềng của k sản phẩm được bình chọn bởi người dùng a mà
chúng tương tự với sản phẩm i nhất.
Khoá luận tốt nghiệp
Sinh viên thực hiện: Nguyễn Minh Đức

25 Hình 1.5. Lọc cộng tác dựa trên người dùng và dựa trên sản phẩm.
Không giống như lọc theo nội dung, lọc cộng tác khai thác những khía cạnh liên
quan đến thói quen sở thích của người sử dụng sản phẩm để đưa ra dự đoán các sản
phẩm mới cho người dùng này. Cho nên lọc cộng tác không phải phân tích, bóc tách,
hiểu, đánh ch mục cho các đặc trưng nội dung sản phẩm. Chính vì vậy, lọc cộng tác có
thể lọc hiệu quả trên nhiều dạng sản phẩm khác nhau như hàng hóa, phim, ảnh, tài liệu,
Cùng trên một hệ tư vấn, người dùng s được tư vấn nhiều loại mặt hàng khác nhau cho
dù các mặt hàng này có thể biểu diễn trên không gian các đặc trưng nội dung khác nhau.