TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
──────── * ───────
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN
ĐỀ TÀI:
XÂY DỰNG ỨNG DỤNG PHÂN TÍCH NGỮ NGHĨA
TRONG TÌM KIẾM TÀI LIỆU TRỰC TUYẾN
Sinh viên thực hiện: Nguyễn Công Chính .
Lớp: HTTTA-K48 .
Giáo viên hướng dẫn: TS. Lê Thanh Hương .
Hà nội, tháng 6 năm 2008
1
LỜI CÁM ƠN
Lời đầu tiên, em muốn gửi lời cám ơn chân thành tới cô TS. Lê Thanh
Hương, là người trực tiếp hướng dẫn em hoàn thành đồ án này.
Em cũng muốn gửi lời cám ơn tới các thầy cô trong bộ môn Hệ thống
Thông Tin, trong khoa Công nghệ thông tin và các thầy cô trong trường đã tận
tình dạy dỗ trong suốt những năm học vừa qua.
Tôi cũng xin gửi lời cám ơn đặc biệt đến bạn Kiều Văn Cường, người
cùng chung đồ án với tôi, đã giúp tôi rất nhiều trong những lúc nghiên cứu, xây
dựng chương trình. Tôi cũng xin cám ơn các bạn cùng lớp Tin 3 và HTTT A đã
cung cấp các tài liệu, gợi ý các giải thuật để hoàn thành đồ án.
Con cũng xin cảm ơn Bố, Mẹ, những người thân đã luôn bên cạnh động
viên khích lệ về mặt tinh thần và cả vật chất để giúp con hoàn thành tốt những
năm học đại học và đồ án này.
Hà Nội Tháng 5 năm 2008
Sinh viên
Nguyễn Công Chính
2
……………………………………………………………………...
……………………………………………………………………...
……………………………………………………………………...
……………………………………………………………………...
……………………………………………………………………...
Ngày tháng 05 năm 2008
Ký tên
4
MỤC LỤC
PHẦN 0: LỜI NÓI ĐẦU............................................................................................10
PHẦN I: VẤN ĐỀ VÀ THỰC TRẠNG....................................................................18
PHẦN II: CƠ SỞ LÝ THUYẾT................................................................................34
PHẦN III: GIẢI PHÁP KỸ THUẬT........................................................................49
PHẦN IV: XÂY DỰNG CHƯƠNG TRÌNH, CÀI ĐẶT CHẠY DEMO................54
5
DANH MỤC HÌNH VÀ BẢNG
DANH MỤC HÌNH VÀ BẢNG...................................................................................6
Hình 1: Hình minh họa tập tách văn bản................................................................14
Hình 2: Cấu trúc giải thuật LSA..............................................................................15
5.3 Mô hình tư vấn dựa trên lịch sử phiên truy cập của người dùng.....................16
Hình 3: Quy trình truy vấn......................................................................................17
Hình 4: Giao diện chính trang chủ chương trình....................................................17
Hình 5: Tìm kiếm thông tin – So sánh gợi ý của người và máy.............................18
Hình 6: Mô hình sơ đồ hệ thống gợi ý cho người dùng...........................................20
Hình 7: Sơ đồ tổng quát hệ thống.............................................................................21
Hình 8: Giao diện tìm kiếm của Amazone.com.......................................................22
Hình 9: Giao diện kết quả trả lại..............................................................................23
Hình 10: Giao diện kết quả tìm kiếm của Amazone.com.......................................24
Hình 11: Sơ đồ cấu trúc từ của Nguyễn Tài Cẩn....................................................27
Hình 12: Giao diện tìm kiếm của Google.................................................................34
Hình 35: User-Case quản lý NXBLớp biên:............................................................61
Hình 36: Biểu đồ tiến trình thêm mới NXB.............................................................62
Hình 38: Biểu đồ tiến trình xóa thông tin NXB.......................................................63
Hình 39: Biểu đồ công tác quản lý NXB.................................................................63
Hình 40: Biểu đồ usercase quản lý thành viên.........................................................64
Lớp biên:.....................................................................................................................64
Chức năng chỉnh sửa thông tin:................................................................................65
Hình 42: Biểu đồ tiến trình chỉnh sửa user.............................................................65
Hình 43: Biểu đồ tiến trình xóa user........................................................................66
Hình 44: Biểu đồ cộng tác quản lý user...................................................................66
Hình 45: Biểu đồ cộng tác quản lý user...................................................................67
.Table 5: Bảng các thực thể chính............................................................................68
Table 6: Bảng quan hệ các thực thể........................................................................69
Table 7: Danh sách các bảng chính...........................................................................72
Mô tả chi tiết bảng......................................................................................................73
7
Table 8: Mô tả bảng tài liệu A01...............................................................................73
Table 9: Mô tả bảng Catalogue A02..........................................................................74
Table 10: Mô tả bảng tác giả A04..............................................................................74
Table 11: Mô tả bảng NXB A05................................................................................75
Table 12: Mô tả bảng User A06.................................................................................75
Table 13: Mô tả bảng subCatalogue A07.................................................................76
Table 14: Mô tả bảng Child A08...............................................................................76
Table 15: Mô tả bảng A11..........................................................................................77
Table 16: Mô tả bảng A12..........................................................................................77
8
9
PHẦN 0: LỜI NÓI ĐẦU
1 1. MỤC TIÊU VÀ Ý NGHĨA CỦA ĐỀ TÀI
phiên giao dịch của họ. Phiên giao dịch của người dùng được bắt đầu từ khi người dùng
đánh từ khóa và có tín hiệu search. Kết thúc phiên làm việc với một từ khóa mới được
nhập. Phương pháp lọc cộng tác ước lượng hàm đánh giá R(u,i) của item i với user u dựa
trên cơ sở đánh giá R(u’,i) của user u’ cho cùng item i mà trong đó u và u’ là tương tự
nhau.
Phương pháp lọc cộng tác có các vấn đề như:
5 Sự thưa thớt: thực tế thì vấn đề của người dùng quan tâm (từ khóa) nó chiếm phần rất
nhỏ và sự đánh giá sự tương đồng cho tài liệu là rất nhỏ so với rất nhiều tài liệu của hệ
10
thống. Với hệ thống gợi ý trong luận văn này, các đánh giá, các nhận định sẽ được lưu
lại dần dần, loại bỏ dần những kết quả không chính xác.
6 Vấn đề tài nguyên mới: Hệ thống không ngừng cập nhật các tài liệu mới cho kho dữ
liệu của mình. Mỗi lần thêm một tài liệu mới, hệ thống sẽ tính lại (off-line) là phân tích
độ tương đồng về ngữ nghĩa giữa các văn bản (kỹ thuật LSA) để tìm ra tập các láng
giềng gần của một cuốn sách.
7 Vấn đề người dùng mới: Như đã đề cập, hệ thống sẽ phân tích và lưu trữ lại lịch sử
của tất cả các phiên làm việc, kết hợp phân tích nội dung trong hệ thống để lọc ra sự
tương đồng, liên quan chính xác nhất của các tài liệu. Nên hệ thống hoàn toàn có thể gợi
ý tư vấn cho một người dùng mới. Khi người dùng cung cấp cho hệ thống các sở thích,
hệ thống sẽ lọc tiếp theo sở thích đó, để cung cấp kết quả chính xác hơn.
Phương pháp lọc dựa trên nội dung: là một giải thuật hướng về nghiên cứu lọc
thông tin, phương pháp lọc dựa trên nội dung ước lượng hàm đánh giá R(u,i) của item i
với user u được thiết lập dựa trên cơ sở đánh giá R(u,i’) của cùng user u cho item i’ mà
trong đó i và i’ là tương tự nhau về mặt nội dung.
Nhược điểm chính của phương pháp này là nó giả định các thuật ngữ là độc lập
nhau. Trong thực tế, các thuật ngữ thường có liên quan với nhau và hiểu được điều này
có thể dẫn đến việc tính độ liên quan tốt hơn.
Tính đồng nghĩa: có nhiều cách để chỉ đến một đối tượng, ví dụ: car và automobile
8 • Các sản phẩm tương tự được đối xử theo cách khác nhau
9 • Tăng sự thưa thớt, làm mất tính chất bắc cầu giữa các từ khóa
tài liệu làm hàng, các cell của ma trận được khởi tạo là tần suất xuất hiện của từ khóa-
thuật ngữ đó trong tài liệu. LSA dùng kỹ thuật phân tích giá trị riêng (SVD-singular
value decomposition) để giảm bớt để giảm bớt kích thước ma trận thuật ngữ-tài liệu,
không gian N-chiều sẽ được giảm bớt xuống một không gian K chiều, K<<N, không
gian mới này được gọi là không gian khái niệm.
5 Sử dụng kết quả bước này, ta thu được tập các tài liệu có sự tương đồng về ngữ
nghĩa nhất định với tài liệu xét. Là nguồn quan trọng trong việc đưa ra gợi ý những tài
liệu tương tự với tài liệu người dùng đang đọc.
3.3 Phân tích lịch sử truy cập của người dùng
6
Một phiên làm việc của người dùng được đánh dấu bằng việc nhập một từ khóa và
nhấn nút search. Các kết quả gợi ý được đưa ra, khi người dùng quyết định chọn một tài
liệu (A), hệ thống gợi thống gợi ý các tài liệu có liên quan (dựa vào phân tích LSA trước
và phân tích lịch sử phiên làm việc). Khi người dùng chọn một tài liệu (B) tiếp theo
trong phần của hệ thống gợi ý để đọc, hệ thống ghi nhận tài liệu B có liên quan nhất
trong phiên làm việc đó với tài liệu A. Và cứ thế, hệ thống sẽ cập nhật và đánh giá lại sự
liên quan nhất định của các tài liệu qua các phiên làm việc của người dùng.
Hệ thống còn đưa ra kỹ thuật khảo sát (survey) để thu thập ý kiến chính xác hơn của
người dùng về sự tương đồng của các tài liệu.
Hạn chế của phương pháp này, là khi có một tài liệu mới được cập nhật, chỉ số lịch
sử truy cập của nó là 0, hoặc một giá trị âm nào đó. Có thể về cơ bản thì nó rất tương
đồng với văn bản A trên chẳng hạn, nhưng phải qua nhiều lần, nhiều phiên làm việc thì
nó mới đứng đầu trong các văn bản liên quan của A.
12
4. CÁC ĐÓNG GÓP CHÍNH CỦA LUẬN VĂN
Cung cấp bộ phân tách văn bản thành các từ khóa với văn bản tiếng Việt
và văn bản tiếng Anh. Sử dụng bộ đọc văn bản đầu vào Ifilter để xử lý, kết hợp các file
từ điển, file từ stopword để tách dữ liệu được đọc vào thành các từ khóa, đặc trưng cho
tài liệu đó.
Kỹ thuật LSA, đánh giá độ tương đồng về mặt ngữ nghĩa giữa các tài liệu
15
Tập tài liệu
(từ khóa)
Xử lý LSA
(ma trận và
giải thuật
SVD)
Tập các tài liệu liên
quan tới 1 tài liệu
Cập nhật CSDL
(dữ liệu tài liệu
liên quan )
5.3 Mô hình tư vấn dựa trên lịch sử phiên truy cập của người dùng
Kế thừa từ các hệ thống học thông minh, từ các phiên làm việc của người dùng, hệ
thống sẽ tự động cập nhật để chính xác hơn những thông tin có trong cơ sở dữ liệu để
phục vụ cho những lần tư vấn sau đó. Có rất nhiều mô hình khai thác trên lĩnh vực người
dùng. Trong đồ án này, tôi chỉ khai thác trên khía cạnh sở thích và lịch sử các phiên làm
việc của người dùng. Khi người dùng đăng ký thông tin, hệ thống ghi nhận ở tài khoản
của họ, thông tin về các lĩnh vực người dùng quan tâm để lọc các kết quả tìm kiếm. Tại
phiên làm việc của người dùng, khi người dùng click vào một tài liệu mà hệ thống đưa ra
để gợi ý cho tài liệu đang đọc, hệ thống sẽ cập nhật hệ số tương quan giữa 2 tài liệu đó,
phục vụ cho các kết quả tư vấn ở lần tiếp theo.
16
Nhận và tiền
xử lý query
Câu truy vấn
Xử lý query,
tạo kết quả trả
Tài liệu chứa từ
khóa trong query
tài liệu có chứa từ khóa, nó còn gợi ý những tài liệu có độ tương đồng nhất định với nội
dung người dùng tra cứu, thể hiện ở các liên kết cuối mỗi trang. Với amazon.co.uk, hệ
thống recommender chỉ với những thành viên đăng ký tài khoản với hệ thống. Khi đăng
ký tài khoản, user đăng ký luôn các sở thích và các lĩnh vực họ quan tâm. Với hệ thống
mubu.com, họ gợi ý trong lĩnh vực âm nhạc. Người dùng cũng phải cung cấp thông tin
về sở thích như ca sỹ, nhạc sĩ, thể loại nhạc quan tâm. Từ đó, hệ thống gợi ý cho người
dùng không cần keyword…
Hình 5: Tìm kiếm thông tin – So sánh gợi ý của người và máy
18
Rất nhiều người không có thời gian để lọc ra trong một tệp các cuốn sách được
thông tin mình mong muốn. Thậm chí trong một cuốn sách dầy tới nghìn trang. Mục lục
ở mỗi cuốn sách cũng là các tóm tắt ý, các chủ đề viết về cho cuốn sách. Người dùng có
thể tìm trong các mục lục đó, cũng có thể tìm theo từ khóa (ứng với mỗi tài liệu, chúng
được tìm theo từ khóa dựa vào chương trình đọc tài liệu đó). Như hình trên, vấn đề là,
tìm được một cuốn sách chứa chủ đề của mình và có đủ lượng thông tin cần thiết cho
vấn đề mình quan tâm. Hoặc khi chưa đủ thông tin, người dùng được gợi ý những cuốn
sách viết về những chủ đề có liên quan mà người ta cần tra cứu thông tin về.
Bài toán đặt ra là, trong kho dữ liệu, bao gồm rất nhiều cuốn sách, rất nhiều các tài
liệu như bài báo, tạp chí. Người dùng cần tra cứu thông tin về một vấn đề nào đó. Hệ
thống sẽ phải cung cấp những cuốn sách viết về vấn đề đó và sắp xếp theo thứ tự ưu tiên
nhất định cho người đọc. Hơn nữa, hệ thống cũng cung cấp các tài liệu mà những người
dùng trước đó đã sử dụng khi cần tra cứu vấn đề đó.
Người dùng thiết lập một phiên giao dịch, bằng việc đăng nhập vào hệ thống hoặc
có thể không cần đăng nhập (Tất nhiên, khi đăng nhập vào hệ thống sẽ được hỗ trợ một
số tính năng tìm kiếm nâng cao). Bằng việc đánh một từ khóa người dùng quan tâm, hệ
thống sẽ cung cấp hai loại kết quả:
1. Kết quả do truy vấn SQL trong cơ sở dữ liệu của hệ thống
2. Kết quả do phân tích qua lịch sử truy cập của những người dùng trước.
Với loại kết quả đầu tiên, kết quả tìm được do việc truy vấn bằng các câu truy vấn
SQL trong cơ sở dữ liệu. CSDL phải được thiết kế sao cho quá trình tìm kiếm là thuận
– Content based approach, kỹ thuật này cho phép hệ thống đưa ra những gợi ý phù
hợp nhất với những tiêu chuẩn đã được xác định. Hệ thống phải nắm được tất cả những
đặc điểm chính được thể hiện trong đối tượng được quan tâm (Theo từ khoá của người
dùng) và sắp xếp chúng theo những tiêu chuẩn tương ứng.
Mặt khác , tiếp cận theo hướng lọc cộng tác – Collborative filtering CF lại làm
việc dựa trên cơ chế tìm kiếm những sự đồng nhất của một cá nhân với cộng đồng mà họ
tham gia để xác định gợi ý hơn là dựa trên việc xác thực nội dung của sự quan tâm. Tức
là CF dựa trên sự công tác giữa một nhóm cá thể có chung một quan điểm hay một sự
lựa chọn nào đó để đưa ra nhưng gợi ý cho người tìm kiếm.
Hình 7: Sơ đồ tổng quát hệ thống
Trong môt số hệ thống cũng thường áp dụng cả hai kỹ thuật này cách này gọi là hệ
thống lai (Hybrid).
21
Về căn bản mô hình bài toán được xây dựng như sau:
- Gọi C là số thành viên của hệ thống: ci là tường người dùng cụ thể.
- Gọi S là toàn bộ không gian đối tượng có thể đưa ra và si là một đối tượng cụ thể.
- Gọi u là giá trị phù hợp của đối tượng s với người dùng c.
Vậy bài toán là sự ánh xạ u: CxS R. Trong đó R chính là tập hợp các đối tượng
được đưa ra giới thiệu. Tập R sẽ được sắp xếp theo thứ tự giảm dần của u.Công việc
chính của giải thuật đơn giản chỉ là đi tìm giá trị hàm u=f(c, s) sao cho u (max) là giá trị
được ưa thích nhất.
Dễ thấy độ phức tạp của bài toán là rất cao bởi không gian S là rất lớn. Ví dụ như
cách ứng dụng về gợi ý sách, số lượng sách có thể lên tới hàng triệu quyển. Hoặc hệ
thống gợi ý về CDs…Đồng thời không gian C cũng rất lớn nếu như mạng phát triển
mang tính toàn cầu như Ebay, Google, Yahoo có thể lên đến hàng tỉ thành viên.
2.1.2 Các hệ thống recommender tiêu biểu
Hệ thống bán hàng trực tuyến m a z o n e .
Hình 8: Giao diện tìm kiếm của Amazone.com
22
Đầu vào: Tên thiết bị, tên công ty, tên danh mục hay bất cứ từ khóa nào
cao nhất.
• Bài hát liên quan: Dựa vào thể loại, mức độ được ưa thích của bài hát, hệ thống
tính toán độ liên quan giữa các bài hát khác nhau. Sau đó đưa ra danh sách bài hát
có độ liên quan cao nhất đối với bài hát hiện tại.
• Giới thiệu các bài hát mới: Dựa vào tiểu sử người dùng (các bài hát đã nghe qua,
đánh giá của người dùng về các bài hát đã nghe), hệ thống sẽ tiến hành dự đoán
mức độ ưa thích của người dùng đối với các bài hát chưa nghe. Thông qua đó, sắp
xếp các bài hát và đưa ra danh sách các bài hát có độ ưa thích cao nhất để tư vấn
cho người dùng .
Hệ thống này có ưu điểm nổi bật:
• Hệ thống giúp cho người dùng có thể tìm thấy các bài hát gần gũi với bài hát mà
mình yêu thích thông qua các bài hát liên quan.
• Hệ thống Recommender cũng là kênh kết nối bạn với những người dùng khác có
cùng sở thích âm nhạc. Bạn sẽ có nhiều cơ hội làm quen, khám phá những sở thích
mới lạ từ những người cùng “gu” âm nhạc.
• Với các mục hỗ trợ tìm kiếm hiện nay, người dùng muốn tìm một bài hát buộc
phải đưa thông tin nào đó về bài hát cần tìm (tên bài hát, một câu hát trong bài, tên
ca sĩ, nhạc sĩ sáng tác...). Vì thế rất khó để tìm thấy một bài hát mới hoặc một bài
hát hợp sở thích của mình, hoặc bạn sẽ gặp khó khăn nếu bạn không có thông tin
về bài hát đó. Với chức năng tư vấn âm nhạc, hệ thống Recommender cho phép
người dùng có thể khám phá các bài hát mới lạ, bất ngờ. Nhờ hệ thống
Recommender, bạn có thể nghe nhạc chọn lọc theo đúng sở thích mà không mất
nhiều thời gian tìm kiếm.
Kết luận:
Nhìn chúng các hệ thống truyền thống đều có mặt hạn chế nhưng chúng ta biết cách
kết hợp các kỹ thuật phù hợp với từng hệ thống riêng biết. Trong nhiều hệ thống thực tế
25
Copyright: Tài liệu đại học ©