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

MAI THỊ NHƯ

ĐỀ TÀI: LỌC CỘNG TÁC DỰA TRÊN MÔ HÌNH
ĐỒ THỊ HAI PHÍA

CHUYÊN NGÀNH: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
MÃ SỐ: 60.48.15
TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012
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:

dung khai thác những khía cạnh liên quan đến nội dung thông tin sản phẩm hoặc người
dùng đã từng sử dụng hay truy nhập trong quá khứ để tạo nên tư vấn. Trái lại, 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.
Lọc cộng tác được tiếp cận theo hai xu hướng 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 trên mô hình (Model Based
Collborative Filtering). So với lọc cộng tác dựa vào bộ nhớ, lọc cộng tác dựa trên mô hình
cho lại kết quả tốt hơn. Chính vì vậy, em đã lựa chọn đề tài “Lọc cộng tác dựa trên mô
hình đồ thị hai phía” để thực hiện trong khuôn khổ luận văn thạc sĩ chuyên ngành truyền
số liệu và mạng máy tính.
2. Mục tiêu của luận văn
Mục tiêu của luận án là nghiên cứu áp dụng, cải tiến phương pháp lọc cộng tác dựa
trên mô hình, cụ thể là mô hình đồ thị hai phía nhằm cải thiện độ chính xác của lọc thông
tin trong các hệ tư vấn. Đặc biệt, nghiên cứu tập trung vào việc nâng cao kết quả dự đoán
nhu cầu người dùng trong trường hợp dữ liệu thưa.
3. Các kết quả đạt được của luận văn
Luận văn đã thực hiện đầy đủ những nội dung theo đề cương đã được phê duyệt.
Những kết quả đạt được của luận văn bao gồm:
Nghiên cứu và tổng hợp được những vấn đề tổng quan về lọc cộng tác, bao gồm:
- Kiến trúc tổng quát của các hệ thống lọc thông tin, phân biệt hệ thống lọc thông
tinh với các hệ thống khác như hệ thống truy vấn thông tin (Information Retrieval)
hệ thống tách thông tin (Information Extraction);
- Phát biểu bài toán lọc cộng tác tổng quát và những vấn đề liên quan.
- Nghiên cứu và tổng hợp lại các phương pháp lọc cộng tác tổng quát: Lọc cộng tác
dựa trên bộ nhớ (MBCF), lọc cộng tác dựa trên mô hình (MDBCF). Phân tích rõ
lợi thể và hạn chế của mỗi phương pháp để xác định mục tiêu nghiên cứu cụ thể
của đề tài.
Nghiên cứu và mở rộng mô hình đồ thị hai phía cho lọc cộng tác, bao gồm:
- Nghiên cứu và mở rộng phương pháp biểu diễn đồ thị hai phía cho lọc cộng tác.
Trong đó, phương pháp biểu diễn mở rộng trực tiếp mô hình của Huang.

Component).

Hinh 1.1. Kiến trúc tổng quát của hệ thống lọc thông tin
1.1.2. Lọc thông tin và truy vấn thông tin
1.1.3. Lọc thông tin và các hệ tư vấn
1.2. Phát biểu bài toán lọc cộng tác
Cho tập hợp hữu hạn U = {u
1
, u
2
,…, u
N
} là tập gồm N người dùng, P = {p
1
, p
2
, ,
p
M
} là tập gồm M sản phẩm. Mỗi sản phẩm p
x
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. Để
thuận tiện trong trình bày, ta viết p
x
P ngắn gọn thành xP; và u
i
U là iU.
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={ r

trên ma trận đầu vào, các phương pháp lọc cộng tác thực hiện như được mô tả trong Hình
1.2.

Hinh 1.2. Các thành phần của hệ thống lọc cộng tác
Có nhiều phương pháp đề xuất khác nhau để giải quyết bài toán lọc cộng tác. Tuy
vậy ta có thể phân loại các phương pháp thành hai cách tiếp 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. Nội dung cụ thể của hai phương pháp này
được trình bày trong những mục tiếp theo.
1.3. Phương pháp lọc cộng tác dựa trên bộ nhớ
Lọc cộng tác dựa trên độ bộ nhớ được tiếp cận theo hai phương pháp 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 phẩm (ItemBased).
Mỗi phương pháp đều có những ưu điểm riêng khai thác những khía cạnh liên quan đến
người dùng hoặc sản phẩm. Đặc điểm chung của cả hai phương pháp này là sử dụng toàn
bộ tập dữ liệu đánh giá để dự đoán quan điểm của người dùng cần được tư vấn về các sản
phẩm mà họ chưa hề biết đến.
1.3.1. Phương pháp UserBased và ItemBased
1.3.2. Ví dụ minh họa
1.3.3. Hạn chế của phương pháp User-Based và Item-Based
1.4. Phương pháp dựa trên mô hình
Việc thiết kế và phát triển các mô hình (như các thuật toán học máy, khai phá dữ
liệu) có thể cho phép hệ thống học cách nhận biết các mẫu phức tạp dựa trên dữ liệu
huấn luyện, và sau đó đưa ra các dự đoán thông minh cho nhiệm vụ lọc cộng tác cho dữ
liệu kiểm thử hay dữ liệu thực, dựa trên các mô hình đã học được. Các thuật toán CF dựa
trên mô hình, như là các mô hình Bayesian, các mô hình phân cụm và các mạng phụ
thuộc đã được nghiên cứu để giải quyết những hạn chế của các thuật toán CF dựa trên bộ
nhớ
1.4.1. Các thuật toán CF mạng bayes tin cậy
1.4.2. Các thuật toán CF phân cụm
1.4.3. Những vấn đề còn hạn chế


Hinh 2.1. Ví dụ về đồ thị hai phía.

2.2 Một số nghiên cứu liên quan
2.3 Mở rộng mô hình đồ thị hai phía
2.3.1. Phương pháp biểu diễn đồ thị
Không hạn chế tính tổng quát của bài toán, ta có thể giả sử r
ix
= +v nếu người
dùng i “thích” sản phẩm x ở mức độ v, r
ix
= -v nếu người dùng i “không thích” sản phẩm
x ở mức độ -v, trong đó v[-1,1].












v
v
r
ix

(2.3)


Nếu người dùng i chưa biết đến sản phẩm x.
N
ế
u ngư
ờ
i dùng i không thích s
ả
n ph
ẩ
m x
ở

m
ứ
c đ
ộ

-
v.

Bang 2.1. Kết quả kiểm nghiệm trên tập MovieLens
Phương pháp

Độ đo
S
ố

đánh giá bi
ế

0.279

Đ
ộ

chính xác

0.174

0.186

0.198

0.218

F
-
Measure

0.158

0.170

0.178

0.245

ItemBased
Đ
ộ


0.134

0.151

0.157

0.185

Huang-Graph
Đ
ộ

nh
ạ
y

0.142

0.165

0.234

0.381

Đ
ộ

chính xác


0.215

0.312

0.397

Đ
ộ

chính xác

0.211

0.284

0.325

0.377

F
-
Measure

0.204

0.245

0.318

0.387

nh
ạ
y

0.102

0.121

0.142

0.149

Đ
ộ

chính xác

0.174

0.194

0.214

0.265

F
-
Measure

0.129

0.163

0.211

0.259

F
-
Measure

0.113

0.134

0.156

0.192

Huang-Graph
Đ
ộ

nh
ạ
y

0.113

0.129


Đ
ộ

nh
ạ
y

0.125

0.138

0.157

0.185

Đ
ộ

chính xác

0.287

0.256

0.234

0.473

F
-

người dùng xem phim, tra cứu nội dung phim, đánh giá phim, tìm kiếm nội dung phim, tư
vấn phim và một số chức năng cập nhật thông tin về phim và thông tin người dùng. Toàn
bộ hệ thống được xây dựng dựa trên công nghệ JSP với giao diện Web thân thiện, đẹp và
dễ sử dụng.
3.1. Kiến trúc tổng quát của hệ thống
3.1.1. Tầng trình bày
3.1.2. Tầng Logic

3.1.3. Tầng dữ liệu
3.2. Mô hình các lớp cơ sở
3.3. Các chức năng chính của hệ thống
3.3.1. Giao diện trang chủ của FRS

3.3.2. Mô tả chi tiết phim
3.3.3. Giao diện tìm kiếm thông tin về phim
3.3.4. Hiển thị phim theo thể loại
3.3.5. Tư vấn phim cho người dùng
3.4. Kết luận
Hệ thống tư vấn lựa chọn phim được xây dựng dựa vào mô hình đồ thị hai phía đã
mô tả đầy đủ các chức năng chính của một hệ thống lọc thông tin, bao gồm: chức năng
học, chức năng lọc, chức năng phân tích dữ liệu, chức năng người dùng. Ứng dụng cho
lại kết quả tư vấn tốt ngay cả trong trường hợp người dùng có ít dữ liệu đánh giá.
hợp cho mỗi người dùng.
Để phân bổ thông tin phù hợp và loại bỏ thông tin không phù hợp cho mỗi người
dùng, đồ thị tổng quát được thực hiện tách thành hai đồ thị con: Đồ thị con G
+
biểu diễn
các đánh giá thích hợp và đồ thị con G
-
biểu diễn các đánh giá không thích hợp. Quá trình
suy diễn trên đồ thị G+ phản ánh mức độ phù hợp của sản phẩm tương ứng cho mỗi
người dùng. Quá trình suy diễn trên đồ thị G- phản ánh mức độ không phù hợp của sản
phẩm tương ứng cho mỗi người dùng. Cuối cùng, kết quả dự đoán được tổ hợp lại làm
kết quả dự đoán chung cho cả mô hình. Trong trường hợp dữ liệu thưa, mô hình cho phép
mở rộng độ là đường đi từ đỉnh người dùng đến đỉnh sản phẩm để tận dụng thông tin gián
tiếp giữa người dùng và sản phẩm.
Cuối cùng, phương pháp lọc trên mô hình đồ thị hai phía được sử dụng để xây
dựng hệ tư vấn lựa chọn phim. Hệ thống phản ánh đầy đủ các chức năng cơ bản của một
hệ thống lọc thông tin, bao gồm thành phần phân tích thông tin, thành phần mô hình
người dùng, thành phần học và thành phần lọc. Hệ thống cho lại kết quả tư vấn tốt trên bộ
dữ liệu MovieLens gồm 3900 phim và 6040 người dùng.
Hướng nghiên cứu tiếp theo của đề tài sẽ tập trung vào việc kết hợp giữa lọc cộng
tác và lọc nội dung. Đây cũng là chủ đề mang tính thời sự cao của cộng đồng nghiên cứu
về lọc thông tin.