ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phí Văn Thủy

TRÍCH CHỌN SỰ KIỆN Y SINH PHỨC HỢP
DỰA VÀO MÔ HÌNH PHÂN TÍCH CÂY PHỤ THUỘC
TRONG VĂN BẢN VỀ BỆNH UNG THƯ DI TRUYỀ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Ệ

UNIVERSITY OF ENGINEERING AND TECHNOLOGY
Phi Van Thuy
A COMPLEX EVENT EXTRACTION METHOD
BASED ON DEPENDENCY PARSING
FOR CANCER GENETICS DATASET
Major: Information Technology

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

HA NOI - 2013


Thuật ngữ trích chn s kiện y sinh hc được sử dụng đ đề cập đến bài toán trích
chọn sự mô tả về các hoạt động và quan hệ giữa một hoc nhiều thực th t tài liệu y sinh học.
Việc tự động nhận dạng bất kì đối tượng của một lớp sự kiện riêng, trích chọn các tham số
liên quan của chúng và biu diễn thông tin được trích chọn vào một dạng có cấu trúc t các
công trình khoa học giúp cộng đồng nghiên cứu y sinh học nhanh chóng thu nhận được các
kết quả nghiên cứu mới nhất trong lĩnh vực liên quan mật thiết tới việc đảm bảo sức khe con
người.
Các kết quả mới nhất cho thấy hiệu năng khi trích chọn các sự kiện phức hợp (sự kiện
có th nhận tham số là thực th hoc sự kiện khác) chỉ đạt khoảng 40-50% F1 tại BioNLP
Shared Task 2011. Khóa luận này đề xuất một mô hình học máy cho bài toán trích chn s
kiện y sinh phức hợp và áp dụng vào Cancer Genetics (CG) task – một bài toán trích chọn
thông tin trong BioNLP Shared Task (ST) 2013. Mục đích của CG task là trích chọn thông tin
tự động t các văn bản về quá trình sinh học, liên quan đến sự phát trin và tiến trin của bệnh
ung thư. Mô hình của chúng tôi gồm ba thành phần chính: (1) nhận diện trigger; (2) trích chọn
ứng viên sự kiện; (3) xếp hạng và đưa ra kết quả. Khi đánh giá trên tập dữ liệu phát trin được
cung cấp bi BioNLP-ST 2013, với khoảng 1000 câu lấy t PubMed, chúng tôi thu được kết
quả bước đầu khá khả quan: độ đo F1 khi trích chọn các sự kiện phức hợp đạt t 50% đến
70%. Mô hình mới phù hợp với miền dữ liệu về bệnh ung thư di truyền và cho hiệu năng tốt
hơn mô hình cơ s chúng tôi đưa ra.
Từ khóa: Event extraction, Dependency tree, Cancer Genetics Task.
ii

A COMPLEX EVENT EXTRACTION METHOD
BASED ON DEPENDENCY PARSING
FOR CANCER GENETICS DATASET
Phi Van Thuy
Course: QH-2009-I/CQ , major: Information technology

gốc một cách rõ ràng t danh mục tài liệu tham khảo trong 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.
Nếu phát hiện có bất kỳ sự gian lận nào, em xin hoàn toàn chịu trách nhiệm
trước hội đồng, cũng như kết quả khóa luận tốt nghiệp của mình.
Sinh viên

Phí Văn Thủy
iv

Mục lục


3.1. Cơ s lý thuyết 19
3.1.1. Chuyn đổi cấu trúc sự kiện sang dạng biu diễn cây phụ thuộc 19
3.1.2. Giải thuật Earley paresr 21
3.2. Mô hình đề xuất giải quyết bài toán 23
3.2.1. Thành phần nhận diện trigger 24
3.2.2. Thành phần trích chọn ứng viên sự kiện 25
3.2.3. Thành phần xếp hạng và đưa ra kết quả 26
Chương 4. Thực nghiệm và đánh giá 28
4.1. Môi trường và dữ liệu thực nghiệm 28
4.1.1. Môi trường thực nghiệm 28
4.1.2. Dữ liệu thực nghiệm 28
4.2. Giới thiệu phần mềm thực nghiệm 31
4.3. Thực nghiệm 32
4.3.1. Hướng tiếp cận thực nghiệm 32
4.3.2. Thực nghiệm nhận diện trigger 32
4.3.3. Thực nghiệm trích chọn sự kiện phức hợp 34
4.4. Nhận xét và thảo luận 36
Kết luận và định hướng 39
Tài liệu tham khảo 40
Tiếng Anh 40
vi

Danh sách bảng
Bảng 1: Các kiu thc th trong CG task 5
Bảng 2: Các kiu s kiện trong CG task 6
Bảng 3: Kt quả vi tp kim th theo các lp s kiện 12
Bảng 4: Phân loại các kiu s kiện trong CG task 17

Hình 8a: Câu gc vi các s kiện 20
Hình 8b: Sau khi chuyn đi sang s phụ thuộc s kiện 20
Hình 9: Mô hình giải quyt bài toán Trích chn s kiện y sinh phức hợp trong văn bản
về bệnh ung thư di truyền 25
Hình 10: Minh ha dạng biu diễn hai cây s kiện cho hai s kiện phức hợp 27
Hình 11: Các mô-đun chính trong phần mềm thc nghiệm 34
Hình 12: Ví dụ về một câu trong tp d liệu huấn luyện cho nhn diện trigger 35
Hình 13: So sánh kt quả gia mô hình cơ sở và mô hình mi đề xuất (dạng biều đồ)38

viii

Bảng các ký hiệu

Từ viết tắt
Thuật ngữ
BioNLP-ST
BioNLP Shared Task
CG Task
Cancer Genetics Task
SVM
Support Vector Machine

1

Mở đầu

Trích chọn sự kiện y sinh học là bài toán trích chọn sự mô tả về các hoạt động

giải quyết đin hình: dựa vào phân tích phụ thuộc cú pháp và dựa vào hệ thống đường
ống. Những công trình này mang tính ứng dụng cao, đang ngày càng được cải tiến cho
hiệu quả tốt hơn. 1
https://sites.google.com/site/bionlpst/home/protein-gene-coreference-task
2
https://sites.google.com/site/bionlpst/home/entity-relations

2

Dựa trên những hướng tiếp cận này cùng với một mô hình học máy đã đề xuất
trong đề tài nghiên cứu khoa học sinh viên, chúng tôi đề xuất một mô hình phân tích
cây phụ thuộc cho việc giải quyết bài toán trích chọn sự kiện y sinh phức hợp trong
văn bản về bệnh ung thư di truyền. Kết quả thực nghiệm bước đầu cho thấy mô hình
mới phù hợp với miền dữ liệu y sinh và cho hiệu năng tốt hơn mô hình cơ s đã đề
xuất: độ đo F1 khi trích chọn các sự kiện phức hợp đạt t 50% đến 70%. Các kết quả này khá
khả quan, th hiện được ưu đim của mô hình đề xuất.
Nội dung của khóa luận bao gồm có 4 chương:
Chương 1: Giới thiệu khái quát về bài toán trích chọn sự kiện liên quan đến
bệnh ung thư di truyền cũng như các khái niệm liên quan.
Chương 2: Giới thiệu một số hướng tiếp cận giải quyết bài toán trích chọn sự
kiện y sinh học, bao gồm hướng tiếp cận dựa vào phân tích phụ thuộc cú pháp và
hướng tiếp cận dựa vào hệ thống đường ống. Đây là cơ s lý thuyết, phương pháp luận
quan trọng đ khóa luận đưa ra mô hình trích chọn các sự kiện y sinh phức hợp 
chương 3.
Chương 3: Trên cơ s những hướng tiếp cận trình bày  chương 2 và thông qua
khảo sát miền dữ liệu văn bản y sinh học về bệnh ung thư di truyền, khóa luận đã lựa
chọn phương pháp dựa vào mô hình phân tích cây phụ thuộc là cơ s của việc giải

tương ứng với tên thực th y sinh, những thực th được quan tâm đến nhiều nhất là
Protein, Gen, Tế bào, Bệnh Trước khi có th xác định được mối quan hệ giữa các
thực th chúng ta phải xác định được đâu là các thực th tham gia vào mối quan hệ đó.
Vì vậy, bài toán nhận diện thực th (BioNER) là bài toán cơ bản và đơn giản nhất
trước khi giải quyết các bài toán phức tạp hơn trong lĩnh vực này. Đến nay đã có rất
nhiều công trình nghiên cứu về BioNER được công bố, cùng với đó là hàng loạt kho
ngữ liệu và ontology được xây dựng nhằm tổ chức và lưu trữ thông tin về nhiều kiu
thực th khác nhau (Gene Ontology (gen), CHEBI (hóa chất), Cell type, CARO (cơ th
chung), PRO (protein) ).
Các bài toán trong khai phá dữ liệu miền y sinh học gần đây tập trung vào trích
chọn sự kiện – chứa quan hệ giữa các thực th trong văn bản. Mc dù những nghiên
cứu gần đây trong khai phá văn bản y sinh đã đạt được một sự tiến bộ đáng k, nhưng
hiệu suất của các hệ thống trích chọn sự kiện hiện tại vẫn còn cần được cải thiện. Ý
thức được tầm quan trọng cũng như tiềm năng của hướng nghiên cứu này, nhóm chúng
tôi tập trung giải quyết bài toán trích chọn sự kiện liên quan đến bệnh ung thư di
truyền trong văn bản y sinh học – một trong những bài toán mới nhất cần được nghiên
cứu giải quyết tại BioNLP Shared Task 2013. 3
http://www.ncbi.nlm.nih.gov/pubmed/

4

Các hội thảo BioNLP Shared Task
4
(BioNLP-ST) đại diện cho một xu hướng
toàn cộng đồng trong khai phá văn bản y sinh học nhằm mục đích trích chọn thông tin
(IE) miền y sinh học. Hai sự kiện trước, BioNLP-ST 2009 và 2011 đã thu hút sự chú ý
rộng lớn, với hơn 30 đội (team) xác nhận kết quả cuối cùng. Tại BioNLP-ST 2011, kết
Hình 2: Ví dụ về trích chn s kiện liên quan đn bệnh ung thư di truyền
Số lượng tài liệu khoa học về bệnh ung thư vô cùng lớn, và sự hiu biết của
chúng ta về cơ chế phân tử của bệnh ung thư đang phát trin nhanh chóng: một truy
vấn PubMed về “cancer” trả về khoảng 2.7 triệu chỉ dẫn bài báo khoa học
5
, với khoảng
140,000 chỉ dẫn liên quan đến ung thư (cancer). Đ xây dựng và lưu trữ các tri thức
cập nhật mới nhất về bệnh ung thư di truyền, việc tự động trích chọn thông tin t các
tài liệu y sinh học là rất cần thiết.
1.2. Các khái niệm liên quan đến bài toán
Phần này trình bày số khái niệm cơ bản liên quan đến bài toán trích chọn sự kiện
liên quan đến bệnh ung thư di truyền trong văn bản y sinh học:
 Thực thể: các thực th (entity) trong miền y sinh học như protein, tế bào, mô
Trong CG task, có 18 kiu thực th được định nghĩa với tham chiếu đến những
ontology và cơ s dữ liệu (CSDL) miền chuẩn, đc biệt là Gene Ontology
(GO), Cell Ontology (CL) và Common Anatomy Reference Ontology (CARO).
Bảng 1: Các kiu thc th trong CG task
STT
Kiểu thực thể
STT
Kiểu thực thể
1
Organism
10
Organism subdivision
2
Anatomical system
11


5
http://www.ncbi.nlm.nih.gov/pubmed?term=cancer

6

 Sự kiện: sự kiện (event) y sinh học được mô tả là một thay đổi về trạng thái của
một hoc nhiều phân tử sinh học
6
. Nó được định nghĩa như một quan hệ giữa
một hoc nhiều thực th thực hiện các vai trò khác nhau. Trong CG task, có 40
kiu sự kiện được định nghĩa với tham chiếu đến Gene Ontology (GO),
Biological process subontology.
Bảng 2: Các kiu s kiện trong CG task
STT
Kiểu sự kiện
STT
Kiểu sự kiện
1
Development
21
Phosphorylation
2
Blood vessel development
22
Dephosphorylation
3
Growth
23
DNA methylation

31
Negative regulation
12
Carcinogenesis
32
Planned process
13
Metastasis
33
Acetylation
14
Metabolism
34
Glycolysis
15
Synthesis
35
Glycosylation
16
Catabolism
36
Cell transformation
17
Gene expression
37
Cell differentiation
18
Transcription
38
Ubiquitination

vai trò ngữ nghĩa.
 Các vai tr tham số: trong CG task, các vai trò của tham số được định nghĩa:
o Theme: thực th/sự kiện bị tác động bi sự kiện hiện tại
o Cause: thực th/sự kiện gây ra sự kiện hiện tại
o AtLoc, FromLoc, ToLoc: vị trí, nguồn hoc đích xảy ra sự kiện
o Site, CSite: miền/vùng tương ứng với Theme/Cause
o Instrument: thực th được sử dụng đ thực hiện sự kiện Planned process
o Participant: kiu vai trò chung xác định một entity tham gia vào quá
trình mức khái quát (chỉ áp dụng cho sự kiện Pathway và Infection)
1.3. Phát biểu bài toán
Bài toán trích chọn sự kiện liên quan đến bệnh ung thư di truyền sử dụng dữ
liệu được cung cấp bi BioNLP-ST 2013 cho quá trình huấn luyện và kim thử. CG
task là một bài toán trích chọn sự kiện nối tiếp dạng biu diễn và các giả thiết t
BioNLP-ST 2009 và BioNLP-ST 2011. Dạng biu diễn liên quan đến hai loại gán
nhãn chính: nhãn thực th và nhãn sự kiện. Các đội tham gia CG task sẽ được cung
cấp nhãn chuẩn cho các thực th, k cả dữ liệu kim thử. Vì vậy bài toán tập trung vào
nhiệm vụ chính trích chọn sự kiện.
Đầu vào:
 Tập văn bản về bệnh ung thư di truyền.
 Các thực th y sinh học được gán nhãn chuẩn bằng tay, liên kết tới văn bản
thông qua vị trí các kí tự (character offset).
Đầu ra:
 Các sự kiện y sinh học được trích chọn và biu diễn theo cấu trúc được định
nghĩa trước.

8 Hình 3: Minh ha đầu vào và đầu ra của bài toán trích chn s kiện liên quan đn
bệnh ung thư di truyền

kiện cũng có th chứa nhiều vai trò tham số giống nhau.
 Các vai trò tham số của mỗi kiu sự kiện khác nhau (Theme, Cause, Site,
Csite, ), một số vai trò tham số mới được định nghĩa trong CG task
(Instrument, Participant).
 Một sự kiện có th có nhiều tham số, và thứ tự của các tham số này hầu hết
không tuân theo một nguyên tắc cố định.
1.5. Phương pháp đánh giá
Theo BioNLP-ST 2009, sự đánh giá dựa vào sự khớp nhau của các sự kiện
được định nghĩa bên dưới
7
. Kết quả đánh giá được báo cáo bằng cách sử dụng các độ
đo chuẩn: độ chính xác, độ hồi tưng và độ đo F1.
Một số khía cạnh cho sự khớp nhau của các sự kiện bao gồm kiu sự kiện,
nhận dạng những t biu diễn sự kiện (trigger), các tham số của sự kiện và tính chính
xác của các thực th và sự kiện chúng tham chiếu tới.
Một số khía cạnh cho sự khớp nhau của các sự kiện bao gồm kiu sự kiện,
nhận dạng những t biu diễn sự kiện (trigger), các thành phần và tham số của sự kiện
và tính chính xác của các thực th và sự kiện chúng tham chiếu tới. Một số tiêu chí
chính xác khác nhau được áp dụng:
 strict equality (khớp nhau hoàn toàn): một sự kiện là chính xác phải khớp
với sự kiện đã được gán nhãn theo tất cả khía cạnh được đề cập  trên.
 approximate boundary matching (khớp biên xp x): cụm tên thực th và
trigger cho phép khác so với cụm tên chính xác. 7
http://www.nactem.ac.uk/tsujii/GENIA/SharedTask/evaluation.shtml

10


.
1.5.2. Khớp biên xp x
Khác với tiêu chí khớp nhau hoàn toàn ở phần in đậm:
 Kiu sự kiện như nhau
 Trigger được dự đoán tương đương với kết quả gán nhn chun
 Với mỗi tham số sự kiện, có một tham số khớp trong đó các thực th/sự kiện
được tham chiếu khớp:
o Các kiu như nhau (cả thực th và sự kiện)
o Cụm tên thực thể/trigger tương đương với kết quả gán nhn chun
o Các tham số của sự kiện như nhau
Với khớp xấp xỉ, sự tương đương được định nghĩa: một cụm dự đoán là tương
đương với cụm gán nhãn chuẩn nếu nó nằm hoàn toàn trong phần m rộng của cụm
gán nhãn chuẩn bi một t  cả hai phía trái và phải.
Ví dụ, cụm dự đoán (gạch chân) A plays role in [ ] là tương đương với (giả
định) cụm gán nhãn chuẩn A plays role in [ ] vì nó nằm trong cụm m rộng A plays
role in [ ].

11

Chương 2. Các hướng tiếp cận giải quyết bài toán
trích chọn sự kiện trong văn bản y sinh học
Phần này trình bày hai hướng tiếp cận được được sử dụng khá phổ biến trong
các hệ thống trích chọn sự kiện y sinh học gần đây. Chúng tôi cũng phân tích một số
thuận lợi và khó khăn đối với hai hướng tiếp cận này. Cuối cùng chúng tôi giới thiệu
một mô hình học máy đã được đề xuất đ giải quyết cho bài toán trích chọn sự kiện
liên quan đến bệnh ung thư di truyền.
2.1. Trích chọn sự kiện dựa vào phân tích phụ thuộc c
pháp
Trong công trình của David McClosky và cộng sự [5], họ đề xuất một hướng tiếp
cận mới cho bài toán trích chọn sự kiện. Họ tạo ra cây các chứa các quan hệ và tham

trigger có th bị loại b trong quá trình xử lý khi đi qua bộ tái xếp hạng. Hướng tiếp
cận này có tiềm năng cho kết quả khá tốt, tuy nhiên việc cài đt theo nó tương đối
phức tạp.
2.2. Trích chọn sự kiện dựa vào hệ thống đường ống
EventMine
9
[14] là một hệ thống đường ống dựa vào học máy, trích chọn sự kiện
t những tài liệu đã được gán nhãn tên thực th (chẳng hạn gen, protein…). Đưa vào
dữ liệu thích hợp, nó có th được huấn luyện đ trích chọn nhiều kiu và cấu trúc sự
kiện khác nhau. Hệ thống gồm 4 mô-đun phát hiện chính, hoạt động dựa trên đầu ra
của bộ phân tích cú pháp, được minh họa trong hình 6.
Các mô-đun hoạt động như sau:
 Trigger/Entity Detection: Mô-đun này xác định những t và cụm t nào trong
câu có khả năng tham gia cấu thành sự kiện, và gán kiu cho chúng. Những t
và cụm t có th là thực th hoc trigger. Trong câu ví dụ  hình 5, các t 9
http://nactem.ac.uk/EventMine/

13

phospholylation, inhibits và binding được xác định có khả năng là trigger cho
các sự kiện Phosphorylation, Negative regulation và Binding.
 Argument Detection: Mô-đun này tìm ra tng cp quan hệ giữa trigger và
tham số, và gán kiu ngữ nghĩa thích hợp cho quan hệ. Trong câu ví dụ  hình
5, sáu quan hệ như vậy được tìm ra.
 Multi-argument Event Detection: Mô-đun này kết hợp các cp quan hệ độc
lập thành các cấu trúc sự kiện hoàn chỉnh.
 Modification Detection: Mô-đun này gán thông tin modification (chẳng hạn