ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
────────────
HỒ LONG VÂN
MÔ HÌNH VÀ THUẬT GIẢI CHO HỆ HỖ TRỢ
TÌM KIẾM THÔNG TIN THEO NGỮ NGHĨA
TRÊN CÁC BÁO ĐIỆN TỬ
LUẬN VĂN THẠC SĨ NGÀNH KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01
TP HỒ CHÍ MINH - NĂM 2014
2
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

HỒ LONG VÂN
MÔ HÌNH VÀ THUẬT GIẢI CHO HỆ HỖ TRỢ
TÌM KIẾM THÔNG TIN THEO NGỮ NGHĨA
TRÊN CÁC BÁO ĐIỆN TỬ
LUẬN VĂN THẠC SĨ NGÀNH KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS-TS ĐỖ VĂN NHƠN
3
TP HỒ CHÍ MINH - NĂM 2014
4
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các số liệu, kết quả
trình bày trong luận văn này là trung thực. Những tư liệu được sử dụng trong luận văn có
nguồn gốc và trích dẫn rõ ràng, đầy đủ.
TP. Hồ Chí Minh, ngày 01 tháng 12 năm 2014
Hồ Long Vân

8
DANH MỤC BẢNG
Bảng 3.1: Trọng số được gán cho mỗi quan hệ………………………………………….67
Bảng 4.1: Thống kê kết quả tìm kiếm theo từ khoá trên kho thử nghiệm 1000 tin bài 101
Bảng 4.2: Thống kê kết quả tìm kiếm ngữ nghĩa trên kho thử nghiệm 1000 tin bài.… 104
Bảng 4.3: Thống kê kết quả tìm kiếm theo chủ đề trên kho thử nghiệm 1000 tin bài….107
Bảng 4.4: Thống kê kết quả tìm kiếm tin bài gần giống nhau.…………………………108
Bảng 4.5: Thống kê chức năng điểm tin.……………………………………………….109
9
DANH MỤC HÌNH
Hình 2.1: Quy trình xử lý của Crawler……………………………………….………….12
Hình 2.2: Kiến trúc tổng quát của một RSS…………………………………………… 14
Hình 2.3: Ví dụ về một đồ thị keyphrase ………………………………………………37
Hình 2.4: Ví dụ về một đồ thị keyphrase mở rộng………………………………………38
Hình 3.1: Quy trình xây dựng đồ thị keyphrase cho câu truy vấn……………………….64
Hình 3.2: Quy trình xây dựng đồ thị keyphrase cho tin bài báo điện tử…………………65
Hình 4.1: Cấu trúc tổng quát của hệ thống …………………………………………….87
Hình 4.2: Menu các chức năng của hệ thống ………………………………………… 90
Hình 4.3: Giao diện trang chủ của hệ thống ………………………………………… 90
Hình 4.4: Giao diện danh sách các trang báo điện tử……………………………………91
Hình 4.5: Giao diện quản lý thông tin và cấu trúc của một trang báo điện tử………
Hình 4.6: Giao diện tập danh sách các chủ đề tin tức.………………………………… 93
Hình 4.7: Giao diện thông tin của một chủ đề tin tức……………………………………93
Hình 4.8: Giao diện cấu hình lựa chọn chế độ và chiến lược thu thập
Hình 4.9: Giao diện quản lý kho tin bài………………………………………………….95
Hình 4.10: Giao diện nâng cao cho “Tìm kiếm thông thường”………………………….96
Hình 4.11: Giao diện nâng cao cho “Tìm kiếm ngữ nghĩa”…………………………… 97
Hình 4.12: Giao diện kết quả tìm kiếm sắp xếp theo “Trang báo điện tử”………………98
Hình 4.13: Giao diện chức năng lọc tin kết quả tìm kiếm……………………………….99
Hình 4.14: Giao diện chức năng điểm tin.……………………………………………….99

mối quan hệ ngữ nghĩa giữa chúng. Những cách tiếp cận theo hướng ngữ nghĩa hay theo
cấu trúc khái niệm này hướng tới việc mô phỏng một cách tự nhiên cách con người giao
tiếp, nghĩa là mô phỏng cấp độ hiểu về ý nghĩa của từ, cụm từ hay văn bản mà người
dùng cung cấp tương ứng với những gì người dùng nghĩ. Trong đó, cách tiếp cận dựa trên
các Ontology được xem là cách tiếp cận hiện đại và phù hợp nhất cho việc thiết kế biểu
diễn, xử lý nội dung và ý nghĩa thông tin của các trang báo điện tử.
Xuất phát từ nhu cầu thực tế và khả năng nghiên cứu phát triển giải pháp cũng như
ứng dụng, đề tài đã tìm hiểu và nghiên cứu các kỹ thuật để xây dựng hệ hỗ trợ tìm kiếm
tin bài theo ngữ nghĩa trên các báo điện tử bao gồm các mô hình, vấn đề, thuật giải, quy
trình xây dựng hệ thống trong đó cố gắng quản lý được các thông tin liên quan tới ngữ
nghĩa của tài liệu cũng như hỗ trợ biểu diễn và xử lý ngữ nghĩa trong tìm kiếm. Kết quả
thực nghiệm bước đầu cho thấy giải pháp đã đề xuất là khả quan và có khả năng ứng
dụng tốt.
Nội dung của luận văn được trình bày trong 5 chương, bao gồm:
Chương 1 giới thiệu tổng quan về đề tài gồm các khảo sát tìm hiểu thực trạng hiện
nay của các tờ báo điện tử và nhu cầu cần thiết để xây dựng hệ thống hỗ trợ cho việc tìm
kiếm thông tin trên internet, tìm hiểu các hệ thống thu thập và tìm kiếm thông tin, phát
hiện tin bài trùng lắp cũng như các kỹ thuật liên quan trong nước và quốc tế. Cuối cùng
trình bày mục tiêu của luận văn.
Chương 2 trình bày cơ sở lý thuyết của đề tài liên quan tới các phương pháp thu
thập thông tin, mô hình ontology CK_ONTO, mô hình tổng quát cho một trang báo điện
tử, cuối cùng giới thiệu một số phương pháp rút trích keyphrase, phương pháp biểu diễn
tài liệu và phương pháp tính khoảng cách ngữ nghĩa giữa các khái niệm.
12
Chương 3 giới thiệu mô hình của hệ thống tìm kiếm báo điện tử theo ngữ nghĩa và
các vấn đề liên quan để xây dựng hệ thống bao gồm: thu thập tin bài, rút trích tự động
keyphrase, tìm kiếm theo ngữ nghĩa các tin bài báo điện tử, tìm kiếm tin bài theo chủ đề,
bài toán điểm tin. Đi cùng với các vấn đề là các phương pháp tiếp cận để giải quyết và
các thuật giải tương ứng. Các phương pháp và thuật giải này là cơ sở để xây dựng các
động cơ suy diễn và tìm kiếm trong hệ thống hỗ trợ tìm kiếm ngữ nghĩa cho báo điện tử.

nhiều thông tin mới ở những trang báo chưa biết. Hay khi các cá nhân hoặc một tổ chức
nào đó cần tổng hợp tin từ một lĩnh vực cụ thể, thống kê định kỳ các tin bài liên quan tới
một vấn đề, sự kiện quan tâm nào đó, họ thường loay hoay với một mớ hỗn độn tin bài
không thể kiểm soát; đặc biệt hơn các công việc ấy đòi hỏi tốn rất nhiều công sức và thời
gian bởi nó chủ yếu được làm thủ công bởi con người nhưng có thể mang lại kết quả
không như mong đợi.
14
Trước những khó khăn của sự bùng nổ báo mạng như trên, nhu cầu tất yếu của các
cơ quan chức năng, các tổ chức, cá nhân là cần có một hệ thống có khả năng giải quyết
những vấn đề liên quan tới họ một cách dễ dàng và nhanh chóng. Hệ thống này phải có
khả năng thu thập các tin bài từ nhiều trang báo điện tử khác nhau, quản lý được các tin
bài, cho phép thống kê theo những tiêu chí liên quan, tìm kiếm các tin bài theo những tiêu
chí cho trước, xử lý được nội dung liên quan tới một lĩnh vực hay chủ đề… Vì vậy, nhu
cầu để xây dựng một hệ thống hỗ trợ cho việc tìm kiếm thông tin là thật sự quan trọng và
có ý nghĩa.
1.2. Vấn đề thu thập thông tin
Đã có rất nhiều hệ thống thu thập, tổng hợp tin tức đã ra đời. Ở Việt Nam,
HueCIT-NewsFinder và Báo Mới là 2 hệ thống tổng hợp tin khá nổi tiếng. HueCIT-
NewsFinder là phần mềm tìm kiếm tin tự động trên internet. Phần mềm có các khả năng
sau: tải tin thủ công hoặc tự động theo lịch lập sẵn, xem tin đã tải về, lưu trữ tin định kỳ
hoặc theo nhu cầu giúp giảm thiểu khối lượng xử lý, chuyển tin sang các trang thông tin
điện tử khác, tìm kiếm tin theo từ khóa và một số tiêu chí liên quan. Báo Mới là một
website tổng hợp thông tin tiếng Việt được điểu khiển tự động bởi máy tính. Hằng ngày
các tin tức từ các trang báo điện tử được tự động tổng hợp, phân loại nội dung vào các
chuyên mục thích hợp, phát hiện các tin bài đăng lại, nhóm các tin bài liên quan về cùng
một chủ đề, tự động bóc tách từ khóa giúp người đọc dễ dàng tìm kiếm các thông tin liên
quan đa chiều, đưa ra những gợi ý những bài viết mà độc giả có thể quan tâm.
Trên thế giới có khá nhiều trang web tổng hợp tin nổi tiếng như: Google News,
News 360, Fark, Pulse, Feedly… Google News là một trang web tin tức thu thập các tiêu
đề từ hơn 50.000 nguồn tin tức trên toàn thế giới, nhóm các thông tin tương tự lại với

nội dung thay đổi và được cập nhật thường xuyên. Những chương trình nổi tiếng như
RSS Reader hay RSS Aggregator vừa quản lý thông tin đăng ký, vừa cho tải các tin bài.
Tuy nhiên, không phải tất cả những tin bài nhận được là phù hợp với người dùng, vì vậy
cần có những cơ chế thích hợp để người dùng có thể nhận được những thông tin quan
tâm. Trong [18] có đề cập về việc tăng cường khả năng tổng hợp tin dùng RSS dựa trên
Ontology. Dùng ontology, việc tổng hợp thông tin sẽ chính xác và đầy đủ hơn. [8] giới
16
thiệu một phương pháp tổng hợp tin RSS dựa trên thuật toán gom cụm. Với kỹ thuật này,
những trang thông tin liên quan nhau sẽ được gom cụm theo các chủ đề giúp người dùng
dễ dàng tìm kiếm những chủ đề mà họ quan tâm. Các kỹ thuật này thật sự hữu ích cho
việc thực hiện thu thập tin bài trên các báo mạng.
1.3. Vấn đề tìm kiếm thông tin theo ngữ nghĩa
Internet chứa hầu như tất cả những thông tin liên quan tới mọi lĩnh vực, mọi ngõ
ngách trong cuộc sống. Nhưng nó rất rộng, rộng đến mức gần như không ai có thể kiểm
soát được. Diện mạo của Internet lại thay đổi quá nhanh chóng và mạnh mẽ.
Có thể ví Internet như một biển dữ liệu khổng lồ, với muôn vàn những viên ngọc quý
nằm giữa các hạt sạn. Trong đời sống hằng ngày, nhu cầu tìm kiếm thông tin đóng vai trò
vô cùng to lớn, và một trong những vấn đề bức thiết nhất của công nghệ hiện nay là làm
sao "đãi cát tìm vàng", khai thác nguồn tài nguyên này một cách hợp lý, đem lại lợi ích
tốt nhất cho con người. Ngày nay, hầu hết mọi người đều sử dụng các bộ máy tìm kiếm
để tìm kiếm thông tin trên mạng Internet.
Trên thị trường hiện nay các công cụ tìm kiếm thông tin trên máy tính đã trở nên
đông đảo và gia tăng không ngừng. Thời gian gần đây, chúng ta nghe nhiều về “cuộc
chiến các bộ máy tìm kiếm trên Internet” với sự cạnh tranh giữa các hãng công nghệ hàng
đầu trên thế giới, đó là sự canh tranh giữa Google (google.com), Yahoo (yahoo.com),
Bing (bing.com), MSN (msn.com), Ask (ask.com), AOL (aol.com), Lycos (lycos.com),
Alta Vista (altavista.com). Các bộ máy tìm kiếm này rất nổi tiếng trên toàn thế giới với
ngôn ngữ được hỗ trợ chính là tiếng Anh nhưng cũng đã hỗ trợ cho các ngôn ngữ khác.
Với tham vọng là xây dựng các bộ máy tìm kiếm tận dụng những lợi thế địa phương của
quốc gia về ngôn ngữ và văn hóa, các quốc gia cũng xây dựng các bộ máy tìm kiếm riêng

Nhưng nếu họ muốn các thông tin về loại trái cây tên là apple, kết quả chưa thật sự như
mong đợi.
- Thuật toán bị đánh lừa. Chẳng hạn tìm kiếm flowers, hầu hết các kết quả là
những của hàng online bán flowers. Google tạo ra một sự thiên lệch trong kết quả tìm
kiếm khi người ta đề cập tới môt sản phầm trong trang web của họ và liên kết tới một cửa
hàng bán sản phẩm đó. Những liên kết dịch vụ này sinh ra trọng số lớn tới những cửa
18
hàng vì thuật toán PageRank của Google tưởng rằng những trang với nhiều link trỏ tới là
quan trọng. Sự thiên lệch cũng xảy ra khi một chủ đề cụ thể được thảo luận bởi nhiều
người trên blog hoặc forum. Những thảo luận này có xu hướng đưa những chủ đề đó lên
đầu của danh sách kết quả tìm kiếm thay vì những trang thực sự chứa thông tin mô tả chủ
đề. Kết quả người dùng nhận được là những trang với những thảo luận về một chủ đề chứ
không phải những trang định nghĩa chủ đề này.
Các hệ thống tìm kiếm thông tin hiện nay phần lớn vẫn dựa trên từ khóa và mức
độ phổ biến của tài liệu. Một danh sách các từ khóa là dạng biểu diễn sơ lược nhất của
nội dung và cách biểu diễn này mang mức độ thông tin thấp. Vấn đề khó khăn đối với
người sử dụng là ở khả năng mô tả nhu cầu thông tin bằng một số từ khóa biểu diễn và
chuyển nhu cầu này thành dạng thức truy vấn phù hợp với hệ thống. Đặc biệt đối với
người sử dụng ít kinh nghiệm không thể đặc tả đúng từ khóa cho vấn đề cần tìm kiếm. Đó
chính là những lý do cơ bản khiến cho các hệ thống tìm kiếm hiện nay có kết quả trả về
không phải lúc nào cũng thỏa mãn yêu cầu của người sử dụng, như là độ chính xác không
cao hay không tìm thấy được những tài liệu liên quan khi chúng được mô tả với những từ
khóa khác đồng nghĩa hoặc gần nghĩa với từ khóa mà người dùng cung cấp. Từ những
mô hình tìm kiếm đơn giản ban đầu như Boolean, nhiều tác giả đã nỗ lực cải thiện hiệu
quả của việc tìm kiếm thông qua các mô hình phức tạp hơn như mô hình không gian
vector (Vector Space Model), các mô hình xác suất (Probabilitic Models), mô hình ngôn
ngữ (Language Model). Nhiều nghiên cứu khác nhằm nỗ lực thay đổi cách đánh trọng số,
đưa vào xử lý ngôn ngữ tự nhiên, khử nhập nhằng, mở rộng tài liệu, mở rộng câu truy vấn
… cũng góp phần làm tăng hiệu quả tìm kiếm. Mặc dù có nhiều cải tiến để cải thiện kết
quả, những hạn chế của việc sử dụng từ khóa vẫn chưa được khắc phục.

- Trong những hệ thống quản lý tài liệu: có hàng triệu tài liệu trong những hệ
thống này và chúng cần được kiểm soát, vì vậy việc nhận dạng những tài liệu
trùng lắp là vô cùng cần thiết.
- Phát hiện sự ăn cắp ý tưởng: những công nghệ điện tử hiện đại ngày nay có thể
sao chép ý tưởng một cách hết sức dễ dàng. Để xử lý vấn đề này, cơ chế phát
hiện sự trùng lắp cần được sử dụng.
20
- Thu thập trang web (web crawling): sự tăng trưởng mạnh mẽ của world wide
web đòi hỏi những bộ thu thập hiện đại phải trở nên hiệu quả hơn, những trang
web trùng lắp sẽ không được thu thập về.
- Trong thư viện kỹ thuật số: những thư viện kỹ thuật số thường lưu trữ một
lượng lớn các bộ sưu tập xuất bản điện tử, vì vậy cần có những hệ thống giúp
phát hiện sự chồng chéo, trùng lắp thông tin.
- Làm sạch dữ liệu: trong các hệ thống cơ sở dữ liệu, một bước cần thiết để làm
sạch dữ liệu và tích hợp dữ liệu là xác định những dữ liệu trùng lắp.
- Trong những hệ thống quản lý email: xác định những thư rác trùng lắp.
Đã có rất nhiều nghiên cứu liên quan tới việc phát hiện sự trùng lắp thông tin và
nhiều thuật toán đã được đưa ra để nhận dạng sự trùng lắp. Một trong những thuật toán
đầu tiên được giới thiệu bởi Broder [5]. Kỹ thuật này tính toán độ tương tự giữa 2 tài liệu,
mỗi tài liệu được chia ra thành những mảnh gọi là shingles. Nếu 2 tài liệu chứa cùng tập
shingles thì chúng được xem là tương đương và có thể được cho là gần giống nhau. [24]
đề xuất phương pháp chỉ số đảo ngược phân bố để tính toán độ tương tự và nhận dạng dữ
liệu dư thừa. [13] so sánh độ tương tự của từng cặp câu để tìm ra những tài liệu gần giống
nhau. SpotSigs đã được đề xuất trong [14] kết hợp những từ đứng trước stopword với
những chuỗi ngắn của những thuật ngữ có nội dung liền kề. [10] trình bày một phương
pháp phát hiện sự trùng lắp thích nghi, có thể đạt được độ chính xác cao trên các lĩnh vực
khác nhau. Một cách tiếp cận khác dựa trên ngữ nghĩa cũng được sử dùng để phát hiện
tin bài gần giống nhau. [6] giới thiệu một phương pháp phát hiện sự ăn cắp ý tưởng dùng
tiếp cận tương tự chuỗi dựa trên ngữ nghĩa và [12] cũng đưa ra một số độ đo tương tự
dựa trên text mà đặc trưng cho quan hệ giữa những đồ thị web ngữ nghĩa.

- Điểm tin: liệt kê các tin tức không trùng lắp tại một thời điểm của tất cả các trang báo
điện tử có trong hệ thống. Các tin tức được nhiều trang báo đăng nhiều nhất sẽ là những
tin chính và nằm ở các vị trí đầu tiên trên trang điểm tin.
Trong thế giới internet, có rất nhiều loại website: báo điện tử (E-newspaper), cổng
thông tin (Portal), sàn giao dịch (Marketplace), cửa hàng và siêu thị trực tuyến (E-store),
mạng xã hội (Social Network), Web Blog… Trong phạm vi của luận văn, đề tài chỉ tập
22
trung vào việc thu thập các trang báo điện tử chính thống (E-newspaper) như: báo “Tuổi
Trẻ Online”, báo “VNEXPRESS”, báo “Dân Trí”…
Việc xây dựng hệ thống hỗ trợ tìm kiếm các tin bài trên báo điện tử theo ngữ nghĩa
hiện vẫn còn khá mới và các phương pháp xử lý vẫn chưa cho lời giải tối ưu. Các phương
pháp và kỹ thuật hiện có thường chỉ hỗ trợ cho một số miền tri thức nhất định trong
những ứng dụng cụ thể và tỏ ra không hiệu quả trong việc áp dụng giải quyết nhiều dạng
bài toán khác nhau. Ngoài ra, việc xây dựng một cơ sở tri thức cho một lĩnh vực cũng gặp
nhiều khó khăn vì đòi hỏi kiến thức của chuyên gia về lĩnh vực và tốn khá nhiều thời gian
công sức. Trong bối cảnh đó, luận văn chỉ nghiên cứu xây dựng thử nghiệm một hệ hỗ trợ
tìm kiếm tin bài về một lĩnh vực, cụ thể là lĩnh vực Lao động-Việc làm. Kho dữ liệu tin
bài chứa các tin bài có nội dung là ngôn ngữ Tiếng Việt.
CHƯƠNG 2
CƠ SỞ LÝ THUYẾT
Chương 2 trình bày các phương pháp thu thập thông tin, mô hình ontology
CK_ONTO và mô hình tổng quát cho một trang báo điện tử. Tiếp theo là một số phương
pháp rút trích keyphrase và cuối cùng là các phương pháp biểu diễn tài liệu và phương
pháp tính khoảng cách ngữ nghĩa giữa các khái niệm.
2.1. Các phương pháp thu thập thông tin
2.1.1. Web Crawler
Web crawler là chương trình khai thác sơ đồ cấu trúc của các website. Chức năng
chủ yếu của một Web Crawler là lấy dữ liệu và nội dung từ các trang web, sau đó thực
hiện tái tổ chức và lưu trữ những dữ liệu đó vào các kho chứa cục bộ. Những dữ liệu
được Web Crawler thu thập sau đó sẽ được xử lý để nhằm đáp ứng các mục đích của

ra URL cần được index tiếp theo từ frontier, nạp trang web tương ứng với URL
đó
bằng
giao thức HTTP, duyệt trang web vừa tải về để lấy ra các URL và các thông tin
mà ứng
dụng
cần, và cuối cùng là thêm các URL chưa được thăm vào frontier. Trước
khi các URL được thêm vào frontier chúng sẽ được gán một độ đo thể hiện đánh giá
hiệu quả khi thăm trang web
tương
ứng với URL đó. Quá trình crawling có thể kết
thúc khi một số lượng nhất định các trang web đã
được
tải. Nếu chương trình crawler
đã sẵn sàng để duyệt một trang web khác và trạng thái của frontier
là

rỗng,
một tín hiệu
trạng thái kết thúc (dead-end) sẽ được gửi cho crawler. Chương trình crawler
sẽ

không
có trang web mới để tải và dừng
lại.
24
Hình 2.1: Quy trình xử lý của Crawler.
Công việc crawling có thể được xem như một bài toán duyệt đồ thị. Toàn bộ thế
giới web được xem như một đồ thị lớn với các đỉnh là các trang web và các liên kết là các
cung (cạnh). Một crawler bắt đầu tại một vài đỉnh và sau đó đi theo các cung để tới các