ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Lê Mạnh Cường

XÂU CHUỖI VĂN BẢN THEO SỰ KIỆN

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: công nghệ thông tin

HÀ NỘI – 2013


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Lê Mạnh Cường

XÂU CHUỖI VĂN BẢN THEO SỰ KIỆN

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: công nghệ thông tin

Cán bộ hướng dẫn: TS. Phan Xuân Hiếu

Cán bộ đồng hướng dẫn: ThS. Trần Mai Vũ


VIETNAM NATIONNAL UNIVERSITY, HANOI
UNIVERSITY OF ENGINEERING AND TECHNOLOGY

Cuong Le Manh

EVENT – ORIENTED DOCUMENT GROUPING

Major: Information Technology

Supervisor: Dr. Hieu Phan Xuan
Co-Supervisor: M.s. Vu Tran Mai

HA NOI – 2013


Lời cảm ơn
Trước tiên, tôi xin gửi lời cảm ơn sâu sắc nhất đến PGS.TS. Hà Quang Thụy, TS.
Phan Xuân Hiếu, ThS. Trần Mai Vũ và cử nhân Nguyễn Minh Tiến, những người đã
tận tình hướng dẫn tôi trong quá trình thực hiện khóa luận tốt nghiệp.
Tôi cảm ơn các thầy, cô trường Đại học Công nghệ đã tạo điều kiện thuận lợi cho
tôi học tập và nghiên cứu tại đây.
Tôi xin cảm ơn các anh chị và các bạn trong phòng thí nghiệm Công nghệ Tri
thức KT-Lab đã hỗ trợ tôi về mặt kiến thức chuyên môn cũng như thực nghiệm để tôi
hoàn thành khóa luận tốt hơn.
Tôi cũng xin cảm ơn các bạn trong lớp K54CD và K54C–CLC đã ủng hộ, giúp
đỡ tôi trong thời gian tôi học tập ở trường.
Cuối cùng, tôi muốn gửi lời cảm ơn đến gia đình và bạn bè, những người đã
khích lệ, động viên tôi giúp tôi vượt qua những khó khăn.
Tôi xin chân thành cảm ơn.

Hà Nội, ngày 15 tháng 5 năm 2013

Lê Mạnh Cường



XÂU CHUỖI VĂN BẢN THEO SỰ KIỆN
Lê Mạnh Cường
Khóa QH-2009-I/CQ, ngành Công nghệ thông tin
Tóm tắt khóa luận tốt nghiệp
Dữ liệu đang bùng nổ một cách chóng mặt, nhu cầu trích chọn thông tin của con người
ngày một tăng. Bài toán xâu chuỗi văn bản là một trong những vấn đề lớn đang được quan
tâm hiện nay. Với mục tiêu giúp con người nắm được bức tranh toàn cảnh về các nguồn văn
bản trên mạng hay cụ thể ở đây là các văn bản dạng tin tức dựa trên chuỗi các sự kiện xảy ra
là sự ra đời của bài toán xâu chuỗi văn bản theo sự kiện. Trong phạm vi khóa luận tìm hiểu
về một số tiếp cận phát hiện sự kiện trong văn bản cũng như mốt số tiếp cận dùng để xâu
chuỗi các sự kiện trong văn bản. Với mục tiêu phát hiện sự kiện trong văn bản tìm hiểu về
hướng tiếp cận sử dụng độ đo TF – IDF, còn với mục tiêu là phát hiện chuỗi sự kiện dùng để
xâu chuỗi văn bản, tìm hiểu hai tiếp cận. Tiếp cận đầu tiên cũng sử dụng độ đo TF – IDF còn
tiếp cận thứ hai sử dụng độ tương đồng của các thông tin thời gian – địa điểm của sự kiện.
Về phần phương pháp đề xuất cho loại văn bản tin tức sử dụng phương pháp xâu chuỗi
dựa trên tiêu đề các trang tin tức vì thực tế là hầu hết tiêu đề của tin tức đã nêu rõ nội dung
của sự kiện. Tác giả xây dựng các từ điển danh từ, động từ, thực thể và các luật để bắt sự kiện
sau đó dùng độ tương đồng cô-sin giữa các từ/cụm từ để gom nhóm các sự kiện. Cuối cùng sử
dụng yếu tố thời gian để xâu chuỗi sự kiên. Từ chuỗi sự kiện phát hiện được trên các tiêu đề
ta tiến hành xâu chuỗi các văn bản tương ứng với các tiêu đề đó.
Từ khóa: xâu chuỗi văn bản, sự kiện, chuỗi sự kiện


EVENT – ORIENTED DOCUMENT GROUPING
Cuong Le Manh
QH-2009-I/CQ, Information Technology
Abstract
Nowadays data is booming, the development of information extraction is necessary.

Document grouping is the one of the major problems and it has become a hot trend of
academy community. To help people know clearly the background of on-line information is
motivation of event-oriented document grouping. It can divide into two stages: event
detection and event sequence detection. In this thesis the author have learned about three
approaches to deal with that problem. The first approach what uses TF – IDF measures aims
to detect events in a document. The second approach also uses TF – IDF measures but it aims
to group documents. The last approach uses time and place information to detect event
sequence.
In this thesis, the author proposes a method for on-line news documents. The method
uses title of these documents to group them. Firstly, the author builds a dictionary which
consists of noun phrases, verb phrases and entity names. Then author uses the dictionary and
rules to detect event. Afterwards the method uses cosine similar measure and time feature to
group documents by grouping their titles.
Keywords: document grouping, event, event sequence.


Lời cam đoan
Tôi xin cam đoan phương pháp tôi sử dụng để Xâu chuỗi văn bản theo sự kiện là
công trình nghiên cứu của tôi, có sự giúp đỡ từ hai người thầy hướng dẫn của tôi là TS.
Phan Xuân Hiếu và Th.S. Trần Mai Vũ. Các nội dung và kết quả trong đề tài này là do
tác giả thực hiện, không sao chép từ bất cứ nguồn nào có sẵn.
Tất cả những tham khảo từ các nghiên cứu liên quan đều được trích dẫn một các
rõ ràng từ danh mục tài liệu tham khảo của khóa luận. Trong khóa luận, không có việc
sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu
tham khảo.

Hà Nội, ngày 15 tháng 5 năm 2013

Lê Mạnh Cường



Mục lục
Lời nói đầu .......................................................................................................................... 1
Chương 1: Tổng quan bài toán xâu chuỗi văn bản theo sự kiện ..................................... 3
1.1. Trích chọn thông tin ............................................................................................. 3
1.1.1. Bùng nổ dữ liệu ...................................................................................... 3
1.1.2. Trích chọn thông tin ............................................................................... 3
1.2. Sự kiện và trích chọn sự kiện................................................................................ 4
1.2.1. Định nghĩa sự kiện ................................................................................. 5
1.2.2. Trích chọn sự kiện .................................................................................. 5
1.3. Bài toán xâu chuỗi văn bản theo sự kiện ............................................................. 6
1.3.1. Tổng quan .............................................................................................. 6
1.3.2. Định nghĩa chuỗi sự kiện ........................................................................ 6
1.3.3. Bài toán xâu chuỗi văn bản theo sự kiện ................................................. 7
1.3.4. Phát hiện sự kiện khởi đầu và quyết định chuỗi ...................................... 8
1.4. Ý nghĩa của bài toán xâu chuỗi văn bản theo sự kiện ......................................... 8
1.5. Khó khăn và thách thức......................................................................................... 9
1.6. Tóm tắt chương.................................................................................................... 10
Chương 2: Một số cách tiếp cận xâu chuỗi văn bản theo sự kiện ................................. 11
2.1. Hướng tiếp cận độ đo TF – IDF để phát hiện sự kiện ....................................... 11
2.2. Hướng tiếp cận độ đo TF – IDF để xâu chuỗi sự kiện ...................................... 12
2.3. Hướng tiếp cận sử dụng độ tương đồng các thông tin và địa điểm để xâu chuỗi
sự kiện ........................................................................................................................... 13
2.3.1. Thông tin về thời gian của sự kiện ........................................................ 13
2.3.2. Thông tin về địa điểm của sự kiện ........................................................ 13
2.4. Nhận xét và đánh giá ........................................................................................... 15
2.5. Tóm tắt chương.................................................................................................... 15


Chương 3: Phương pháp xâu chuỗi văn bản dựa trên độ tương đồng của cụm trên ngôn

ngữ tiếng Việt ................................................................................................................... 16
3.1. Mô tả bài toán ...................................................................................................... 16
3.2. Phương pháp đề xuất ........................................................................................... 16
3.2.1. Giai đoạn phát hiện sự kiện ................................................................. 16
3.2.2. Giai đoạn xâu chuỗi sự kiện ................................................................. 17
3.3. Mô hình đề xuất để giải quyết bài toán .............................................................. 19
3.4. Một số đánh giá về phương pháp giải quyết ...................................................... 21
3.5. Tóm tắt chương.................................................................................................... 22
Chương 4. Thực nghiệm và đánh giá .............................................................................. 23
4.1. Môi trường thực nghiệm ..................................................................................... 23
4.1.1. Cấu hình phần cứng.............................................................................. 23
4.1.2. Môi trường phần mềm .......................................................................... 23
4.2. Xây dựng từ điển và các luật nhận biết sự kiện ................................................. 24
4.2.1. Xây dựng từ điển .................................................................................. 24
4.2.2. Xây dựng các luật ................................................................................. 25
4.3. Thực nghiệm ........................................................................................................ 25
4.3.1. Dữ liệu thực nghiệm ............................................................................. 25
4.3.2. Quá trình thực nghiệm .......................................................................... 26
4.4. Kết quả và nhận xét kết quả ................................................................................ 27
4.4.1. Phần phát hiện sự kiện .......................................................................... 27
4.4.2. Phần xâu chuỗi sự kiện ......................................................................... 28
4.5. Đánh giá ............................................................................................................... 32
4.5.1. Phương pháp đánh giá .......................................................................... 32
4.5.2. Đánh giá ............................................................................................... 33
4.6. Tóm tắt chương.................................................................................................... 35
Tổng kết ............................................................................................................................ 36


Định hướng tương lai ....................................................................................................... 37
Tài liệu tham khảo ............................................................................................................ 38

Phụ lục ............................................................................................................................... 41


Danh sách hình vẽ

Hình 1. Sự tăng trưởng dung lượng dữ liệu giai đoạn 2004-2020........................... 4
Hình 2. Minh họa một chuỗi sự kiện ..................................................................... 7
Hình 3. Minh họa sự kiện khởi đầu ....................................................................... 8
Hình 4. Mô hình giải quyết bài toán .................................................................... 20
Hình 5. Mô tả một phần của dữ liệu..................................................................... 26
Hình 6. Thống kê số sự kiện phát hiện được trên các chủ đề từ 6/3 đến 7/5 ......... 28
Hình 7. Thống kê các sự kiện được phát hiện từ 8/4 đến 7/5 ................................ 29
Hình 8. Số cụm phát hiện được khi sử dụng ba độ đo tương đồng ....................... 29
Hình 9. Số cụm và số sự kiện lớn nhất trong các cụm từ 8/4 đến 7/5 ................... 31
Hình 10. Thống kê trên bộ luật thứ hai ................................................................ 32
Hình 11. Tỉ lệ lỗi trên các chủ đề (theo tập luật thứ nhất) .................................... 34


Danh sách bảng biểu
Bảng 1. Cấu hình phần cứng ............................................................................. 23
Bảng 2. Môi trường phần mềm ......................................................................... 23
Bảng 3. So sánh giữa sự kiện nóng nhất giữa hệ thống với thực tế .................... 31
Bảng 4. Kết quả xâu chuỗi sự kiện .................................................................... 35


Các ký hiệu và từ viết tắt
Kí hiệu
ACE
LOC
k-NN

MUC
NER
NOAA
NP
OBN
ORG
TDT
TF–IDF
TREC
VP

Ý nghĩa
Automatic Content Extraction
Location
k Nearest Neighbours
Message Understanding Conference
Name Entity
National Oceanic and Atmospheric Administration
Noun Phrase
Object name
Organization
Topic Detection and Tracking
Term Frequency–Inverse Document Frequency
Text REtrieval Conference
Verb Pharse


Lời nói đầu
Xâu chuỗi văn bản theo sự kiện thực chất là bài toán phát hiện và theo dõi sự kiện
– một bài toán đã được cộng đồng khoa học quan tâm từ khá lâu. Bài toán được phát

biểu tường minh là xác định sự kiện trong các văn bản rồi từ những sự kiện đã phát
hiện quay trở lại xâu chuỗi văn bản. Hội nghị Message Understanding Conferences
MUC1 hay các chương trình phát hiện và theo dõi chủ đề TDT2, trích xuất các nội
dung tự động ACE3 đã dày công nghiên cứu vấn đề này. Có nhiều hướng tiếp cận về
học máy (k – NN, cây quyết định…) cũng như thống kê (TF – IDF) được đưa ra trong
quá trình tìm hiểu và giải quyết bài toán. Hiện nay, trên thế giới có nhiều hệ thống xác
định sự kiện cũng như chuỗi sự kiện từ các văn bản dạng tin tức được cập nhập hàng
ngày, ví dụ như BioCaster ( HealthMap ( />hay hệ thống VnLoc của Việt Nam ( Việc dữ liệu đang tăng trưởng
với một tốc độ chóng mặt trở thành động lực cũng như thách thức không nhỏ cho bài
toán.
Khóa luận Xâu chuỗi văn bản theo sự kiện khảo sát một số phương pháp phát
hiện sự kiện và chuỗi sự kiện. Dựa trên cơ sở đó, tác giả nghiên cứu và đề xuất phương
pháp xâu chuỗi văn bản hướng sự kiện thực hiện trên miền văn bản tin tức tiếng Việt.
Phương pháp được đề xuất bao gồm hai giai đoạn chính là phát hiện sự kiện và xâu
chuỗi các sự kiện đó. Ở giai đoạn thứ nhất, tác giả sử dụng hệ thống luật và từ điển do
tác giả nghiên cứu và xây dựng để phát hiện sự kiện. Ở giai đoạn thứ hai, các sự kiện
được đánh giá dưới ba độ đo tương đồng thử nghiệm với ngưỡng là 0.2 và dùng đặc
trưng thời gian để xâu chuỗi sự kiện. Quá trình thực nghiệm thu được kết quả tương
đối khả quan. Điều này chứng tỏ tính đúng đắn của phương pháp tác giả sử dụng cũng
như tính thực tiễn với miền tin tức tiếng Việt. Sử dụng tiêu đề để phát hiện và xâu
chuỗi sự kiện có thể không chính xác bằng việc xử lý cả đoạn văn nhưng lại rút ngắn
được nhiều thời gian. Bên cạnh đó nếu xây dựng các từ điển và bộ luật tốt hướng tới
từng chủ đề riêng thì phương pháp này sẽ có độ chính xác cao.
Khóa luận bao gồm bốn chương được mô tả như dưới đây.
Chương 1. Tổng quan bài toán xâu chuỗi văn bản theo sự kiện giới thiệu về trích
chọn thông tin trong giai đoạn dữ liệu bùng nổ mạnh mẽ, sau đó giới thiệu khái quát

1

/>

2

/>
3

/>
1


bài toán xâu chuỗi văn bản, ý nghĩa bài toán cũng như một số khó khăn thách thức mà
bài toán đối mặt.
Chương 2. Một số cách tiếp cận xâu chuỗi văn bản theo sự kiện trình bày một
phương pháp để phát hiện sự kiện và hai phương pháp phát hiện chuỗi sự kiện dùng để
hỗ trợ cho bài toán mà tác giả hướng đến.
Chương 3. Phương pháp xâu chuỗi văn bản dựa trên độ tương đồng của cụm từ
trên ngôn ngữ tiếng Việt mô tả rõ ràng bài toán xâu chuỗi văn bản trên miền tin tức
tiếng Việt. Chương này cũng trình bày phương pháp giải quyết bài toán dựa trên hai
giai đoạn chính là phát hiện sự kiện và xâu chuỗi các sự kiện đã được phát hiện. Giai
đoạn phát hiện sự kiện dựa trên tập luật và tập dữ liệu mà tác giả đã xây dựng. Giai
đoạn sau sử dụng độ đo tương đồng giữa các cụm từ để xâu chuỗi sự kiện.
Chương 4. Thực nghiệm và đánh giá thể hiện quá trình thực hiện phương pháp đã
được nêu trong chương 3, sau đó đánh giá kết quả thực nghiệm.
Tiếp theo là phần tổng kết khóa luận cùng với định hướng tương lai. Phần này
khái quát lại toàn bộ công trình và đưa ra một số định hướng mới trong thời gian tiếp
theo.
Cuối cùng là danh mục Tài liệu tham khảo chỉ ra các tài liệu mà tác giả đã tham
khảo trong suốt quá trình thực hiện khóa luận. Việc sử dụng các tài liệu này trong khóa
luận được trích dẫn một cách rõ ràng.

2



Chương 1: Tổng quan bài toán xâu chuỗi văn bản theo sự kiện
1.1. Trích chọn thông tin
1.1.1. Bùng nổ dữ liệu
Dữ liệu do con người tạo ra đang tăng lên với một tốc độ chóng mặt. Theo thống
kê gần đây của tổ chức NOAA (National Oceanic and Atmospheric Administration),
dung lượng dữ liệu dữ liệu đạt gần 80,000 Terabytes tính đến tháng 4 năm 2013. Cũng
theo tổ chức này, dự báo đến năm 2020 sẽ tăng lên đến 160,000 Terabytes (chi tiết tại
hình 14).
Trong một cuốn sách mang tên Megatrends: Ten New Directions Transforming
Our Lives, tác giả John Naisbitt nhận định.
We are drowning in information, and starved for knowledge [11].
(Chúng ta đang chìm ngập trong thông tin nhưng lại thiếu thốn tri thức).
Điều đó có nghĩa có nhiều thông tin chưa chắc đã có nhiều tri thức. Quá trình
biến đổi từ dữ liệu thành tri thức là một quá trình mang tính bản chất và lâu dài. Bên
cạnh đó tri thức thường mang tính chất đặc riêng của từng miền, để thu thập và biến
đổi dữ liệu thành tri thức cần có những nghiên cứu và công cụ hỗ trợ cho quá trình
này.
1.1.2. Trích chọn thông tin
Như đã đề cập ở trên, thông tin không phải ngẫu nhiên mà nắm bắt được. Yêu
cầu đặt ra cho lĩnh vực trích chọn thông tin là có thể trích xuất các thông tin có ích từ
một tập dữ liệu lớn.
Với phạm vi văn bản, theo phân loại của Sunita Sarawagi, có nhiều mức trích
chọn thông tin chẳng hạn như nhận dạng thực thể, xác định thuộc tính thực thể, xác
định quan hệ giữa các thực thể, nhận dạng đồng tham chiếu… [15]. Tùy theo từng lĩnh
vực cụ thể, người ta xây dựng và áp dụng một số phương pháp để tăng hiệu quả trích
xuất. Có hai phương pháp điển hình đó là dựa trên luật hoặc dựa trên thống kê. Với
phương pháp dựa trên luật có thể kể đến như là luật nhận dạng đơn thực thể, luật nhận
dạng đa thực thể, luật đánh dấu biên thực thể, …) còn với phương pháp thống kê người


4

/>
3


Hình 1. Sự tăng trưởng dung lượng dữ liệu giai đoạn 2004-2020
ta hay sử dụng Mô hình Markov ẩn, mô hình Markov cực đại Entropy hay độ tương
đồng TF – IDF.
Bùng nổ dữ liệu vừa là thách thức vừa là động lực cho lĩnh vực trích chọn thông tin.
Việc xử lý lượng một dữ liệu lớn đòi hỏi ngoài một hiệu năng phần cứng lớn cần có
những phương pháp trích chọn thích hợp.
1.2. Sự kiện và trích chọn sự kiện
Trích chọn sự kiện được cộng đồng khoa học quốc tế đầu tư nghiên cứu từ khá
sớm. Hội nghị MUC5 được tổ chức lần đầu tiên năm 1987 dưới sự hỗ trợ của Quỹ
nghiên cứu bộ quốc phòng Hoa Kỳ là một trong những hội nghị tiêu biểu trong trích
chọn sự kiện. Hội nghị đã đưa ra phương pháp trích chọn sự kiện theo khung mẫu với
mục đích là trích chọn bằng cách lấy các thông tin liên quan đến sự kiện. Bên cạnh đó,
các chương trình TDT6 (Phát hiện và theo dõi chủ đề) được tổ chức hàng năm từ năm
1997 đã bước đầu giải quyết được bài toán phát hiện sự kiện mới, theo dõi và xâu
chuỗi sự kiện. Có nhiều nhóm nghiên cứu tham gia chương trình như nhóm BBN từ
công ty BBN Technologies, nhóm CMU của trường đại học Carnegie Mellon, nhóm
DRAGON của công ty Dragon Systems … Mỗi nhóm đều đưa ra những tiếp cận riêng
và góm phần nâng cao kết quả của lĩnh vực trích chọn sự kiện.

5

/>
6


/>
4


1.2.1. Định nghĩa sự kiện
Tùy theo từng lĩnh vực và dữ liệu người ta có nhiều cách định nghĩa sự kiện. Trên
miền tin tức, Allan và cộng sự định nghĩa tin tức chứa sự kiện nếu nó có bốn yếu tố:
hành vi, chủ thể, thời gian và địa điểm [3]. Hội nghị MUC quan tâm đến các sự kiện về
khủng bố, quân sự, đầu tư mạo hiểm, tai nạn máy bay… Định nghĩa sự kiện mà hội
nghị đưa ra phải có đủ các yếu tố: tác nhân, thời gian, địa điểm và các tác động của nó.
Còn trong chương trình ACE 7 (Automatic Content Extraction), sự kiện đơn giản là
một sự thay đổi trạng thái. Loại sự kiện và các thuộc tính sự kiện được quy định chặt
chẽ hơn. Có tám loại sự kiện được sử dụng bao gồm business (kinh tế), conflict (xung
đột), contact (liên lạc), justice (pháp lý), life (cuộc sống), movement (sự di chuyển),
personnel (nhân sự) và transaction (giao dịch). Mỗi loại sự kiện sau đó lại được chia
thành từng dạng con. Ví dụ như trong justice bao gồm một số dạng như arrest – jail
(bắt giữ – bỏ tù ), convict (kết án), fine (phạt)…[1] Hay như trong hệ thống VnLoc sự
kiện được định nghĩa là bộ bảy đặc trưng bao gồm tên sự kiên, loại sự kiện, thời gian
xảy ra sự kiện, nơi xảy ra sự kiện, nguồn đưa tin, liên kết và tóm tắt của sự kiện đó.
Cũng theo VnLoc thì sự kiện họ quan tâm thuộc một trong ba loại: tai nạn giao thông,
hình sự, cháy nổ.
Thông thường các nghiên cứu thường chỉ giải quyết vấn đề trong một lĩnh vực cụ
thể. Yoko Nishihara quan tâm sự kiện trong lĩnh vực mạng xã hội [13] trong khi Hongwoo Chun hay K. Bretonnel Cohen lại tập trung vào sự kiện y sinh [5] [6]. Bên canh
đó người ta cũng quan tâm đến các mối nguy hiểm đe dọa [17], …
Trong phạm vi khóa luận, tác giả quan tâm đến sự kiện thuộc một trong mười chủ
đề thuộc mục thế giới trên một số trang tin tức tiếng Việt. Cụ thể là các chủ đề: bầu cử,
chiến tranh – quân sự, hàng không – vũ trụ, hạt nhân, khủng bố, khủng hoảng kinh tế,
ngoại giao, tham nhũng, tin tặc và tranh chấp chủ quyền. Sự kiện ở đây là sự thay đổi
trạng thái ứng với tác động của các cụm danh từ và cụm động từ.

1.2.2. Trích chọn sự kiện
Trích chọn sự kiện là lĩnh vực con của trích chọn thông tin. Nhiệm vụ của trích
chọn sự kiện là nhận biết và trích chọn được các thông tin về sự kiện từ tập dữ liệu. Cụ
thể hơn trích chọn sự kiện tập trung phát hiện sự kiện với miền lĩnh vực cho trước, sau
đó trích được ra các đặc trưng của sự kiện như thời gian, địa điểm…

7

/>
5


Trích chọn sự kiện thực sự là một bài toán khó. Ngoài vấn đề về việc xây dựng
các bộ nhận dạng sự kiện thì nó còn phải đối mặt với các khó khăn chung về xử lý
ngôn ngữ tự nhiên, hay tính nhập nhằng ngữ cảnh.
1.3. Bài toán xâu chuỗi văn bản theo sự kiện
1.3.1. Tổng quan
Dưới góc nhìn sự kiện, bài toán xâu chuỗi văn bản chính là bài toán phát hiện
chuỗi sự kiện. Giám sát một tập dữ liệu để tìm ra các văn bản cùng nói về một sự kiện
và xâu chuỗi theo thứ tự thời gian chính là định nghĩa của chuỗi sự kiện. Chẳng hạn về
sự kiện “Khủng bố ở cuộc đua ma-ra-tông Boston”, chúng ta muốn theo dõi diễn biến
cũng như kết quả cho đến khi sự kiện kết thúc. Yêu cầu đặt ra là cần xâu chuỗi các văn
bản theo diễn biến của sự kiện từ nguồn thông tin trên các trang báo được cập nhật liên
tục.
Các trang báo mạng rất quan tâm đến vấn đề xâu chuỗi các văn bản cụ thể ở đây
là tin tức. Cách tiếp cận hiện nay của các trang báo mạng là cách làm thủ công, tức là
gắn văn bản với các sự kiện liên quan đã có bằng cách trỏ liên kết bằng tay. Cách làm
này không những bị động mà còn mang tính cục bộ, tức là trang báo mạng nào cũng
thực hiện nhưng lại không có liên kết với nhau. Một yêu cầu đặt ra cho miền Tiếng
Việt là cần có một hệ thống phát hiện và theo dõi sự kiện của văn bản, hay có thể nói

gọn là xâu chuỗi văn bản theo sự kiện.
1.3.2. Định nghĩa chuỗi sự kiện
Bài toán chuỗi sự kiện được cộng đồng khoa học quốc tế quan tâm từ khá sớm.
Như đã đề cập ở phần đầu, đây là một trong những nội dung chính của chương trình
TDT. Ở TDT–1, người ta chỉ tập trung vào hai dạng dữ liệu, đó là tin tức dưới dạng
văn bản và tin tức từ phát thanh, truyền hình. Bên cạnh đó, hội nghị TREC–68 (Text
REtrieval Conference) cũng quan tâm đến bài toán chuỗi sự kiện nhưng có đôi chút
khác biệt so với TDT–1. Trong khi TDT–1 quan tâm đến sự kiện và hướng phát hiện
chuỗi sự kiện thì TREC–6 xâu chuỗi văn bản theo cùng chủ đề.
Theo Heikki Mannila, một sự kiện được mô tả là cặp (A,t) với A là các thông tin
liên quan đến sự kiện, t là thời gian xảy ra sự kiện [10]. Tập sự kiện E cho trước và A
E.

8

/>
6


Chuỗi sự kiện S là bộ ba giá trị (s, Ts, Te) với s =< (A1, t1), (A2, t2), …, (An, tn) >
Trong đó:
Ai

E với i = 1, 2, …, n

Ai

Ai+1 với i = 1, 2, …, n-1

ti


ti+1 với i = 1, 2, …, n-1

Ts là thời gian bắt đầu chuỗi sự kiện
Te là thời gian kết thúc chuỗi sự kiện
Ts

ti

Te

Hình 2 [10] minh họa một ví dụ về chuỗi sự kiện S = (s, 29,67)
với s = < (E, 31), (D, 32), (F, 33), …, (D, 67)>

Hình 2. Minh họa một chuỗi sự kiện [10]
1.3.3. Bài toán xâu chuỗi văn bản theo sự kiện
Thực chất bài toán xâu chuỗi văn bản theo sự kiện chính là bài toán phát hiện
chuỗi sự kiện. Đầu vào yêu cầu là một tập văn bản còn đầu ra chính là tập văn bản đó
nhưng đã được xâu chuỗi theo sự kiện. Mỗi văn bản có một ứng viên sự kiện, đầu tiên
người ta tiến hành xâu chuỗi các sự kiện ứng viên, sau đó quay trở lại xâu chuỗi văn
bản. Như vậy theo hướng sự kiện, bài toán xâu chuỗi văn bản phụ thuộc vào bài toán
phát hiện chuỗi sự kiện.
Theo Yang Yiming, bài toán phát hiện chuỗi sự kiện là một bài toán học có giám
sát [19]. Đầu tiên người ta xây dựng dữ liệu học dựa vào các sự kiện đã xảy ra sau đó
sử dụng mô hình học máy dựa trên bộ dữ liệu này để phát hiện văn bản được thêm vào
có chứa sự kiện thuộc những sự kiện đã được xây dựng hay không. Có nhiều cách tiếp
cận được sử dụng để giải quyết bài toán này. Chẳng hạn các phương pháp học máy
như k người láng giềng gần nhất k–NN [2], cây quyết định [18], [19]. Các phương
pháp thống kê như sử dụng trọng số TF–IDF được đề cập ở [3] hay thống kê tần suất
xuất hiện của các cụm từ của nhóm Heikki Mannila [10]. Ngoài ra còn có một số cách

dựa trên mô hình ngôn ngữ như sử dụng mô hinh ngữ nghĩa của Ramesh Nallapati
[12], hay như của công ty Dragon Systems [2].
7


Bài toán xâu chuỗi văn bản theo sự kiện bao gồm hai giai đoạn. Giai đoạn thứ
nhất là phát hiện sự kiện trong các văn bản. Giai đoạn thứ hai là theo dõi và xâu chuỗi
các sự kiện. Một số vấn đề được quan tâm trong bài toán là phát hiện sự kiện khởi đầu,
đánh giá sự kiện tương đồng và quyết định chuỗi.
1.3.4. Phát hiện sự kiện khởi đầu và quyết định chuỗi
Chương trình TDT định nghĩa sự kiện khởi đầu là sự kiện chưa từng xảy ra và
được nhắc đến trong quá khứ. Hình 3 [4]dưới đây minh họa hai dạng sự kiện (hình thoi
và hình tròn) theo thứ tự tăng dần của thời gian. Với luồng tin tức thu được từ các
trang báo mạng chúng ta thu được rất nhiều sự kiện, nhiệm vụ của chúng ta là phải
gom nhóm các tin tức cùng nói về một sự kiện. Trong ví dụ này chúng ta cần đưa các
sự kiện hình thoi về một cụm và các sự kiện hình tròn về một cụm. Để đưa các văn bản
về được một cụm cần dựa trên độ tương đồng giữa hai văn bản hay cụ thể hơn là phải
dựa vào độ tương đồng giữa hai sự kiện. Bên cạnh đó cần phải xem xét và đánh giá
các sự kiện trùng lặp. Sau khi đưa được các sự kiện về các cụm chúng ta sử dụng yếu
tố thời gian để quyết định chuỗi sự kiện. Trong khóa luận tác giả quan tâm đến vấn đề
các sự kiện tương đồng phục vụ cho công việc xâu chuỗi.

Hình 3. Minh họa sự kiện khởi đầu [4]
1.4. Ý nghĩa của bài toán xâu chuỗi văn bản theo sự kiện
Về mặt khoa học, bài toán xâu chuỗi văn bản có ý nghĩa rất lớn. Đầu tiên, việc có
thể tập trung các văn bản có liên quan lại với nhau giúp con người có thể dễ dàng tìm
thông tin cần thiết một cách nhanh chóng. Bên cạnh đó, khi các văn bản được xâu
chuỗi theo sự kiện, bài toán có thể giúp chúng ta dự đoán xu hướng sự kiện, theo dõi
các xu hướng mà cộng đồng quan tâm. Việc nắm được diễn biến của sự kiện giúp con


8


người chủ động hơn trong tình hình cuộc sống hiện nay. Cuối cùng bài toán là một lĩnh
vực con của bài toán trích chọn thông tin. Giải quyết tốt bài toán là cơ sở để giải quyết
những bài toán liên quan, chẳng hạn như giám sát thông tin trong các bài toán quản lý
xã hội.
Bài toán xâu chuỗi văn bản theo sự kiện cũng có ý nghĩa rất lớn trong thực tiễn.
Với bối cảnh bùng nổ dữ liệu cụ thể trong mảng tin tức chúng ta có thể thấy thông tin
xuất hiện rất nhiều nhưng lại rất rời rạc. Người dùng không thể nắm được bước tranh
toàn cảnh về những gì đang diễn ra trong cuộc sống. Chẳng hạn một người quan tâm
đến sự kiện “Khủng bố ở Boston” vừa diễn ra trong tháng tư vừa qua thì với lượng tin
tức cập nhật liên tục nhưng lại không theo quy luật cụ thể nào có thể khiến người đó
gặp rất nhiều rắc rối trong việc nắm thông tin. Đơn giản người ta chỉ muốn xem diễn
biến của sự kiện trên nhưng họ buộc phải tìm kiếm tuần tự để thực hiện điều đó. Yêu
cầu đặt ra cho bài toán xâu chuỗi văn bản là cố gắng đưa các văn bản nói về một sự
kiện về cùng một nhóm sau đó trình bày theo thứ tự thời gian để người dùng có thể
nắm được rõ ràng diễn biến sự kiện. Trên thế giới hiện nay có rất nhiều hệ thống theo
dõi các sự kiện từ luồng tin tức. Điển hình có thể kể đến như HealthMap của Hoa Kỳ
hay BioCaster của Nhật Bản. Ở Việt Nam cũng có hệ thống VnLoc9 theo dõi các sự
kiện đời sống như tai nạn, hỏa hoạn, dịch bênh… Không những vậy các hệ thống
thường được thể hiện trực quan trên bản đồ giúp người dùng dễ dàng theo dõi.
1.5. Khó khăn và thách thức
Được nhận định là một bài toán khó vì phải trải qua bài toán xâu chuỗi sự kiện
nên dễ hiểu là bài toán phải đối mặt với nhiều khó khăn. Bài toán gặp một số khó khăn
trong cả giai đoạn phát hiện sự kiện trong văn bản cũng như là xâu chuỗi các sự kiện.
Về giai đoạn phát hiện sự kiện, bài toán gặp những khó khăn chung của lĩnh vực
xử lý ngôn ngữ tự nhiên trên Tiếng Việt. Bên cạnh đó, bài toán đối mặt với các khó
khăn về nhập nhăng ngữ cảnh, tính đa tham chiếu cũng như tính đa hình cấu trúc ngữ
pháp của văn bản. Chẳng hạn như “Tổng thống Mỹ sang thăm Nhật Bản”, “Ông

Barrack Obama trò chuyện với thủ tướng Nhật Bản”, … Vấn đề đồng tham chiếu cũng
như sự biến đổi của thông tin trở thành thách thức lớn. Trong khóa luận tác giả chưa
giải quyết được vấn đề đồng tham chiếu.

9

/>
9


Về giai đoạn xâu chuỗi sự kiện, bài toán gặp khó khăn trong việc xác định sự
kiện khởi đầu cũng như đánh giá độ tương đồng giữa các sự kiện. Bên cạnh đó bài
toán phải đảm bảo tính đúng đắn của chuỗi sự kiện, tức là phải xác định được sự kiện
nào đi trước sự kiện nào theo sau.
Ngoài ra việc xây dựng được bộ phát hiện sự kiện gặp nhiều khó khăn. Tác giả
phải tìm hiểu rất nhiều bài báo và xây dựng được từ điển cũng như luật phục vụ cho
công việc phát hiện sự kiện. Việc này đòi hỏi tác giả phải can thiệp sâu vào dữ liệu, có
những phân tích đúng đắn và tỉ mỉ trên miền ứng dụng thực hiện. Trong khóa luận, tác
giả thực hiện xây dựng mười chủ đề thuộc chuyên mục Thế giới trên các trang báo
mạng. Việc xử lý với một lượng lớn dữ liệu đòi hỏi nhiều thời gian cũng như công sức.
1.6. Tóm tắt chương
Chương một đã nêu lên được một số vấn đề. Đầu tiên là việc bùng nổ dữ liệu
cũng như nhu cầu trích chọn thông tin. Nhiều phương pháp được đưa ra cho lĩnh vực
này. Tiếp đó là nêu được tổng quan về sự kiện, chuỗi sự kiện và bài toán xâu chuỗi văn
bản hướng sự kiện. Đồng thời chương một cũng nêu được ý nghĩa thực tiễn của bài
toán. Cuối cùng là khó khăn thách thức chung của bài toán cũng như một số khó khăn
của tác giả khi thực hiện trong một lĩnh vực cụ thể.

10



Chương 2: Một số cách tiếp cận xâu chuỗi văn bản theo sự kiện
Trong chương một đã giới thiệu tổng quan về bài toán xâu chuỗi văn bản theo sự
kiên. Bài toán này phải trải qua hai giai đoạn là phát hiện sự kiện và xâu chuỗi sự kiên.
Ở chương này giới thiệu một phương pháp phát hiện sự kiện sử dụng độ đo TF – IDF
ở mục 2.1. Mục 2.2 và 2.3 sẽ trình bày hai phương pháp được sử dụng để xâu chuỗi sự
kiện. Phương pháp đầu tiên là hướng tiếp cận sử dụng độ đo TF – IDF còn phương
pháp thứ hai dựa trên độ tương đồng các thông tin về thời gian cũng như địa điểm.
2.1. Hướng tiếp cận độ đo TF – IDF để phát hiện sự kiện
Hướng tiếp cận sử dụng các độ đo TF – IDF là một trong những phương pháp
được sử dụng trong thời kỳ mở đầu của bài toán phát hiện sự kiện.
Để đánh giá khi so sánh văn bản d với tập đặc trưng q, Allan và cộng sự sử dụng
hàm đánh giá sau [14]

Trong đó:
wi là độ liên quan của đặc trưng qi
di là độ tin cậy được thể hiện ở công thức 2.2
Độ tin cậy

được tính bởi công thức sau:

Trong đó:
được thể hiện ở công thức 2.3
được thể hiện ở công thức 2.4
là hằng số làm trơn, ở đây = 0.4
Độ đo TF được tính bởi công thức 2.3

Trong đó:
t là số lần xuất hiện của đặc trưng trong tin tức.
dl là độ dài của tin tức tính theo đơn vị từ.

avg_dl là số lượng trung bình đặc trưng trong một tin tức
Độ đo IDF được tính bởi công thức 2.4
11


Trong đó:
C là số tin tức trong bộ ngữ liệu đã được chuẩn hóa
df là số lượng tin tức có ít nhất một đặc trưng xuất hiện
2.2. Hướng tiếp cận độ đo TF – IDF để xâu chuỗi sự kiện
Ngoài việc sử dụng trọng số TF – IDF để phát hiện sự kiện, người ta cũng sử
dụng trọng số này để phát hiện chuỗi sự kiện. Tiếp cận này dựa trên quan điểm các sự
kiện trong cũng chuỗi thường có một số thuộc tính tương đồng hoặc trùng nhau. Các
sự kiện được vec-tơ hóa để có thể tính độ tương đồng giữa chúng [16].
Gọi K = { k1, k2, …, kn,} là tập đặc trưng.
Đối với mỗi tài liệu chứa sự kiện, độ đo TF và IDF được tính toán theo các công
thức

Trong đó:
là số lần xuất hiện của từ khóa ki trong văn bản
là số lần xuất hiện cực đại của tất cả các từ khóa trong văn
bản.

Trong đó:
là số văn bản chứa đặc trưng ki.
N là tổng số văn bản được xét tới.
Tuy nhiên có một số trường hợp df(i) = 0 nên trong một số bài báo người ta có
thể lấy mẫu số là 1+df(i).
Cuối cùng độ tương đồng giữa hai văn bản được tính bởi công thức

Bên cạnh đó có một số cải tiến nhằm nâng cao tính đúng đắn của chuỗi sự kiện,

chẳng hạn có thể áp dụng các độ đọ TF – IDF ở phần 2.1 vào các công thức 2.3 và 2.4.

12