BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

ĐỖ ĐÌNH LÂN

NGHIÊN CỨU PHÁT HIỆN SỰ KIỆN
TỪ DỮ LIỆU VĂN BẢN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Bình Định, năm 2017


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

ĐỖ ĐÌNH LÂN

NGHIÊN CỨU PHÁT HIỆN SỰ KIỆN
TỪ DỮ LIỆU VĂN BẢN

Chuyên ngành
Mã số

: Khoa học máy tính
: 60 48 01 01


Người hướng dẫn: TS. Lê Quang Hùng





6

MỤC LỤC

DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt
ACE
IDF
k-NN
NER
NP
SVM
TDT
TF
VP

Cụm từ
Automatic Content Extraction
Inverse Document Frequency
k Nearest Neighbours
Name Entity Recognition
Noun Phrase
Support Vector Machine
Topic Detection and Tracking
Term Frequency
Verb Pharse

Ý nghĩa

thường được đăng tải trên các mạng xã hội ngay khi nó xảy ra. Trong khi đó
các trang tin tức khác trên mạng thường đăng tải các thông tin này chậm hơn.
Thậm chí, nhiều thông tin được đăng tải trên các trang mạng xã hội nhưng
không được đăng tải trên các trang tin tức khác.
Tin tức, thông tin, sự kiện sẽ có giá trị cao khi nó được truyền tải đến
người dùng nhanh và chính xác, đặc biệt các thông tin, sự kiện liên quan đến
an ninh - chính trị, kinh tế, đời sống, giáo dục, pháp luật, thể thao,… Vậy làm
thế nào để phát hiện, tập hợp nhanh các sự kiện đó từ các văn bản, các trang
tin tức và trả lời được các câu hỏi “sự kiện gì? xảy ra ở đâu? thời gian nào?
diễn biến sự kiện như thế nào...” cho người dùng?
Xuất phát từ nhu cầu thực tiễn đó, chúng tôi lựa chọn thực hiện đề tài
“Phát hiện sự kiện từ dữ liệu văn bản”.
1. Mục tiêu nghiên cứu
Trong luận văn này, chúng tôi đặt ra mục tiêu: tìm hiểu về bài toán phát
hiện sự kiện từ dữ liệu văn bản và lựa chọn cách tiếp cận phù hợp để cài đặt
thực nghiệm trên dữ liệu văn bản tiếng Việt.


10

1. Bố cục của luận văn

Ngoài phần mở đầu và kết luận, luận văn được tổ chức thành 3 chương
với bố cục như sau:
Chương 1. GIỚI THIỆU. Chương đầu tiên của luận văn, chúng tôi giới
thiệu tổng quan về lĩnh vực phát hiện và trích chọn sự kiện. Sau đó, chúng tôi
trình bày sơ lược về bài toán phát hiện sự kiện từ dữ liệu văn bản cùng sự cần
thiết của nó trong nghiên cứu khoa học cũng như trong thực tiễn.
Chương 2. MỘT SỐ KỸ THUẬT PHÁT HIỆN SỰ KIỆN. Trong chương
này, chúng tôi trình bày một số cách tiếp cận bài toán phát hiện sự kiện từ dữ

Chương trình Phát hiện và theo dõi chủ đề TDT (Topic Detection and
Tracking) được tổ chức từ năm 1997 thu hút nhiều nhóm nghiên cứu từ các
trường đại học tham gia. Chương trình này được phối hợp bởi Viện công nghệ
và chuẩn hoá quốc gia Hoa Kỳ (NIST) nhằm giải quyết bài toán phát hiện,
theo dõi và xâu chuỗi sự kiện. Một số nhóm nghiên cứu tham gia chương
trình như: nhóm CMU của Đại học Carnegie Mellon, nhóm BBN từ công ty


12

BBN Technologies, nhóm DRAGON của công ty Dragon, nhóm UPENN của
Trường Đại học Pennsylvania (UPENN). Các bài toán quan trọng của TDT
gồm: theo dõi chủ đề, phát hiện chủ đề, phát hiện sự kiện khởi đầu và phát
hiện liên kết.
Chương trình Trích chọn nội dung tự động của Đại học Pennsylvania
cũng thu hút được nhiều quan tâm từ các cộng đồng nghiên cứu và trích chọn
thông tin cũng như trích chọn sự kiện. Chương trình này tập trung vào các
ngôn ngữ như tiếng Anh, Trung Quốc và Ả Rập. Các thông tin được trích
chọn gồm các thực thể, quan hệ giữa các thực thể và các sự kiện chúng tham
gia vào.
1.2 Định nghĩa sự kiện
Tùy theo từng lĩnh vực và dữ liệu, các nhà nghiên cứu có nhiều cách
định nghĩa sự kiện khác nhau. Trên miền tin tức, Allan và cộng sự (1998) định
nghĩa tin tức có chứa sự kiện nếu nó có bốn yếu tố sau: hành vi, chủ thể, thời
gian, địa điểm [7]. Hành vi là các hoạt động hay hành động gây ra sự kiện.
Chủ thể là con người, sự vật hoặc sự việc. Thời gian là thời gian xảy ra sự
kiện. Địa điểm là nơi diễn ra sự kiện.
Ví dụ: “Chiều ngày 20/06/2017 đã xảy ra một vụ tai nạn trên đường
Quốc lộ 19 làm cho 4 người chết và 3 người bị thương”.
Cũng theo nhóm nghiên cứu này, việc định nghĩa rõ ràng thế nào là một

nhau. Một sự kiện khi được đề cập đến không nhất thiết phải có đầy đủ các
thuộc tính như trong định nghĩa.


14

1.3 Bài toán phát hiện sự kiện từ dữ liệu văn bản
Phát hiện sự kiện là bài toán quan trọng trong lĩnh vực phát hiện và
trích chọn thông tin. Kết quả của bước phát hiện sự kiện là đầu vào cho quá
trình trích chọn sự kiện. Nếu kết quả của quá trình phát hiện sự kiện đạt kết
quả tốt sẽ nâng cao hiệu quả của quá trình trích chọn sự kiện.
Bài toán phát hiện sự kiện trả lời câu hỏi“làm thể nào để phát hiện
được một văn bản có chứa sự kiện?”.
Đầu vào: Văn bản T (ví dụ: bản tin trên các


trang báo điện tử).

Đầu ra: Văn bản T có chứa sự kiện hay


không?

Tức là, cho trước đầu vào là văn bản, làm thế nào để phát hiện văn bản
đó có chứa sự kiện? Theo Grishman và cộng sự [15], phát hiện sự kiện là quá
trình học không giám sát, tác giả sử dụng các từ, cụm từ để quyết định một
văn bản có chứa sự kiện dịch bệnh hay không. Hai cụm từ được
tác giả lớp
sử
Bộ phân

quá trình nghiên cứu và triển khai các cách tiếp cận phát hiện sự kiện, chi tiết
về các cách tiếp cận trong phát hiện sự kiện sẽ được chúng tôi đề cập trong
Chương 2.


16

Chương 2. MỘT SỐ KỸ THUẬT PHÁT HIỆN SỰ KIỆN
Trong chương này, chúng tôi trình bày một số cách tiếp cận bài toán
phát hiện sự kiện từ dữ liệu văn bản, bao gồm: (i) cách tiếp cận dựa trên luật,
(ii) cách tiếp cận dựa trên học máy và (iii) cách tiếp cận kết hợp luật và học
máy.
2.1 Cách tiếp cận dựa trên luật
1.1.1 Luật cú pháp
Luật cú pháp, đôi khi còn được gọi là mẫu cú pháp (lexico-syntactic
patterns) có thể coi là phương pháp được sử dụng sớm nhất để giải quyết bài
toán phát hiện và trích chọn sự kiện. Các mẫu này được xây dựng bởi chuyên
gia dưới dạng tập luật. Điển hình cho phương pháp này là các luật được biểu
diễn dưới dạng biểu thức chính quy.
Các luật cú pháp là sự kết hợp biểu diễn của các ký tự và các thông tin
cú pháp với các biểu thức chính quy. Sau khi các biểu thức chính quy đã được
xây dựng, các biểu thức này sẽ được so khớp với dữ liệu trong văn bản đầu
vào để phát hiện và trích chọn ra các thông tin tương ứng của các thuộc tính.
Đôi khi, luật cú pháp được biểu diễn ở dạng đơn giản hơn, đó là các từ khoá.
Tập luật cú pháp được sử dụng trong phát hiện và trích chọn sự kiện,
[9], [10]. Trong nghiên cứu của mình, Nishihara và cộng sự sử dụng các mẫu
về: địa điểm (place), đối tượng (object) và hành vi (action) để biểu diễn một
sự kiện được phát hiện và trích chọn từ blogs [3]. Trong lĩnh vực y sinh,
Yakushiji và cộng sự sử dụng một bộ phân tích kết hợp với ngữ pháp để xác
định mối quan hệ và các sự kiện [23]. Còn trong lĩnh vực tiền và chính trị


đề phát hiện sự kiện cho hệ thống cảnh báo sớm [17]; còn Vargas -Vera và
Celjuska đề xuất một bộ khung cho việc phát hiện các sự kiện tập trung trên
báo Knowledge Media Institute (KMI) [18]. Phát hiện và trích chọn sự kiện
trong văn bản phi cấu trúc có thể được ứng dụng trong nhiều lĩnh vực như:
giáo dục, tài chính, chứng khoán, y sinh, hình sự, cháy nổ, pháp luật,…
2.1.3 Biểu diễn tập luật
Theo Sunita Sarawagi [16], một luật cơ bản có dạng:
"mẫu theo ngữ cảnh → hành động".
Ví dụ: Mẫu biểu diễn cho sự kiện {thời gian, địa điểm, tác nhân,
hành động}.
“Vào ngày 20/8/2015 một vụ tai nạn xảy ra trên Quốc lộ 1A đã làm 3
người đi xe máy bị thương, nguyên nhân ban đầu là do xe máy chở 3 đi
ngược chiều”.
Một mẫu theo ngữ cảnh bao gồm một hoặc nhiều mẫu nhãn ghi lại
thuộc tính của một hoặc nhiều thực thể và bối cảnh xuất hiện trong văn bản.
Một mẫu được gán nhãn là so khớp một biểu thức chính quy được xác định
qua các tính năng của thẻ trong văn bản và một nhãn tùy chọn. Các thuộc tính
có thể được chỉ ra là thuộc tính của thẻ hoặc ngữ cảnh hoặc các văn bản trong
các thẻ xuất hiện.
Hầu hết các hệ thống dựa trên luật được liên tầng, luật được áp dụng
trong nhiều giai đoạn mà mỗi giai đoạn liên kết một dữ liệu đầu vào với một
chú thích như là tính năng đầu vào cho các giai đoạn tiếp theo.


19

Ví dụ, phát hiện các địa chỉ liên lạc của người được tạo ra trong hai giai
đoạn của luật: giai đoạn thứ nhất, nhãn thẻ cùng với nhãn thực thể như: tên
người, vị trí địa lý như tên đường, tên thành phố và địa chỉ thư điện tử. Giai

({Dictionary - Lookup = Titles}
{String = “.”}
{Orthography type =capitalized word}{2})
→Person Names.
Mỗi điều kiện trong dấu ngoặc nhọn là một điều kiện của một thẻ được
theo sau cùng với số tùy chọn và chỉ ra số lần lặp lại của thẻ. Ví dụ về một luật
để đánh dấu tất cả số đi sau các giới từ "by" và "in" là thực thể năm:
(String=“by”|String=“in”})
({Orthography type = Number}):y
→Year=:y.
Có hai mẫu trong luật này: mẫu đầu tiên để ghi lại ngữ cảnh xuất hiện
của các thực thể năm và mẫu thứ hai ghi lại các tính chất của thẻ tạo thành
"year".


21

Một ví dụ khác cho việc tìm kiếm tên công ty dạng “The ABC Corp.” or
“XYZ Ltd.” được tạo bởi:

({String=“The”}?
{Orthography type = All capitalized}
{Orthography type = Capitalized word, DictionaryType =Company end})

→Company name.
2.1.3.2 Các luật đánh dấu ranh giới thực thể
Đối với một số loại thực thể, đặc biệt như tiêu đề cuốn sách hay tiêu đề
các bài báo có số đơn vị từ quá dài, các luật đánh dấu ranh giới thực thể sẽ rất
hiệu quả để xác định sự bắt đầu và kết thúc một ranh giới thực thể. Đó là loại
bỏ một cách độc lập và tất cả các thẻ ở trong giữa hai thẻ đánh dấu đầu và

2.2 Cách tiếp cận dựa trên học máy


23

Cách tiếp cận dựa trên học máy đôi khi còn được gọi với tên là tiếp cận
dựa trên dữ liệu. Cách tiếp cận này thường được sử dụng cho các ứng dụng xử
lý ngôn ngữ tự nhiên và tập dữ liệu đủ lớn để huấn luyện cho phù hợp với các
hiện tượng ngôn ngữ [11]. Cách này thường dựa trên mô hình xác suất, lý
thuyết thông tin và đại số tuyến tính. Một số phương pháp cơ bản thường
được sử dụng là tần số xuất hiện của một từ trong văn bản và tần số nghịch
đảo của một từ trong tập văn bản (TF-IDF), n-grams hay phân cụm.
Có nhiều nghiên cứu áp dụng cách tiếp cận dựa trên dữ liệu để phát
hiện và trích chọn thông tin các sự kiện. Năm 2009, Okamoto và cộng sự [11]
dựng một khung để phát hiện các sự kiện cục bộ. Trong nghiên cứu tác giả sử
dụng các kỹ thuật phân cụm phân cấp. Trong khi đó, phân cụm có thể sinh ra
các kết quả tốt cho việc phát hiện và trích chọn sự kiện, Liu và cộng sự [8] kết
hợp các đồ thị có trọng số vô hướng chia đôi (weighted undirected bipartite
graphs) và phân cụm để phát hiện, trích chọn các thực thể chính cùng các sự
kiện có ý nghĩa từ các thông tin hàng ngày. Các kỹ thuật phân cụm cũng được
sử dụng bởi Tanev và cộng sự [5] để phát hiện và trích chọn các sự kiện: bạo
lực, thảm họa cho hệ thống giám sát.
Cách tiếp cận học máy không đòi hỏi người xây dựng cần đến các kiến
thức về ngôn ngữ và chuyên gia. Nhưng cách tiếp cận này lại đòi hỏi một
lượng dữ liệu lớn để làm tập huấn luyện. Cách tiếp cận dựa trên dữ liệu cần
xây dựng xác suất để xấp xỉ mô hình huấn luyện với dữ liệu.
2.2.1 Phương pháp k láng giềng gần nhất
Có nhiều phương pháp học máy được áp dụng vào bài toán phát hiện và
trích chọn sự kiện, trong đó k-NN là một trong những thuật toán được sử


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 di được tính bởi công thức sau:
(2.2)
Trong đó:
• tf được thể hiện ở công thức (2.3).
• idf đượ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):
(2.3)
Trong đó:
• t là số lần xuất hiện của đặc trưng trong văn bản.
• dl là độ dài của văn bản tính theo đơn vị từ.
• avg_dl là số lượng trung bình đặc trưng trong một văn bản.
Độ đo idf được tính bởi công thức (2.4):
(2.4)
Trong đó:
• C là số văn bản trong bộ ngữ liệu đã được chuẩn hóa.
• df là số lượng văn bản có ít nhất một đặc trưng xuất hiện.