ÑI H≈C QU»C GIA HÀ NÀI
TR◊ÕNG
ÑI H≈C CÔNG NGHõ
NGUYôN MINH TIòN
TRÍCH CH≈N S‹ KIõN D¿CH BõNH
CHO Hõ TH»NG GIÁM SÁT
TR‹C TUYòN
LUäN VãN THÑC Sfl CÔNG NGHõ THÔNG TIN
HÀ NÀI - 2014
ÑI H≈C QU»C GIA HÀ NÀI
TR◊ÕNG
ÑI H≈C CÔNG NGHõ
NGUYôN MINH TIòN
TRÍCH CH≈N S‹ KIõN D¿CH BõNH
CHO Hõ TH»NG GIÁM SÁT
TR‹C TUYòN
Ngành:
Công nghª Thông tin
Chuyên ngành:
Mã sË:
Hª thËng Thông tin
60480104
LUäN VãN THÑC Sfl CÔNG NGHõ THÔNG TIN
NG◊ÕI H◊ŒNG DàN KHOA HOC: Ti∏n sˇ Nguyπn Trí Thành
HÀ NÀI - 2014
LÌi cam oan
Tôi xin cam oan lu™n v´n “Trích chÂn s¸ kiªn d‡ch bªnh cho hª thËng giám sát
tr¸c tuy∏n” là công trình nghiên c˘u cıa riêng tôi. Các sË liªu, k∏t qu£ ˜Òc trình
bày trong lu™n v´n là hoàn toàn trung th¸c và ch˜a t¯ng ˜Òc công bË trong bßt
k˝ mÎt công trình nào khác.
Tôi ã trích d®n ¶y ı các tài liªu tham kh£o, công trình nghiên c˘u liên quan
trong n˜Óc và quËc t∏. Ngo§i tr¯ các tài liªu tham kh£o này, lu™n v´n là công
viªc cıa riêng tôi.
Hà NÎi, ngày...tháng...n´m 2014
Tác gi£
Nguyπn Minh Ti∏n
3
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 tÓi TS. Nguyπn Trí Thành, nguÌi
ã t™n tình chø b£o và h˜Óng d®n tôi trong quá trình th¸c hiªn lu™n v´n tËt nghiªp.
Tôi xin g˚i lÌi c£m Ïn chân thành tÓi PGS.TS. Hà Quang Thˆy, ng˜Ìi ã t™n
tình giúp Ô, ‡nh h˜Óng và góp ˛ cho tôi trong suËt thÌi gian tôi nghiên c˘u và làm
viªc t§i phòng thí nghiªm Công nghª Tri th˘c (Knowledge Technology Laboratory
- KT-Lab).
Tôi xin g˚i lÌi c£m Ïn tÓi TS. Phan Xuân Hi∏u, nghiên c˘u sinh Tr¶n Mai VÙ,
nh˙ng ng˜Ìi ã cÍ vÙ, giúp Ô và óng góp ˛ ki∏n cho tôi trong suËt quá trình hÂc
t™p và nghiên c˘u t§i tr˜Ìng §i hÂc Công nghª - §i hÂc QuËc gia Hà NÎi.
Tôi chân thành c£m Ïn các th¶y, cô, và cán bÎ tr˜Ìng §i hÂc Công nghª §i hÂc QuËc gia Hà NÎi ã gi£ng d§y và t§o i∑u kiªn thu™n lÒi cho tôi hÂc t™p,
nghiên c˘u, và hoàn thành lu™n v´n. Bên c§nh ó, tôi xin c£m Ïn các anh, ch‡, và
các b§n sinh viên thuÎc phòng nghiên c˘u Công nghª Tri th˘c (KT-Lab) ã giúp
Ô tôi hoàn thành lu™n v´n.
Tôi xin g˚i lÌi c£m Ïn tÓi nh˙ng Áng nghiªp t§i BÎ môn Công nghª Ph¶n m∑m
- Khoa Công nghª Thông tin - Tr˜Ìng §i hÂc S˜ ph§m Kˇ Thu™t H˜ng Yên ã
ıng hÎ, cÍ vÙ tôi trong suËt thÌi gian hÂc t™p, nghiên c˘u và hoàn thành lu™n v´n.
CuËi cùng, tôi muËn g˚i lÌi c£m Ïn ∞c biªt tÓi gia ình, b§n bè, và nh˙ng ng˜Ìi
thân yêu luôn bên c§nh Îng viên tôi trong suËt quá trình hÂc t™p và th¸c hiªn
lu™n v´n tËt nghiªp.
Tôi xin chân thành c£m Ïn!
HÂc viên
Nguyπn Minh Ti∏n
4
Mˆc lˆc
1 TÍng quan v∑ bài toán trích xußt s¸ kiªn
1.1 Bài toán trích xußt thông tin t¯ d˙ liªu lÓn . . . . . . . . . . . . . .
1.1.1 Bài toán trích xußt thông tin . . . . . . . . . . . . . . . . . .
1.1.2 D˙ liªu lÓn - CÏ hÎi và thách th˘c cho lænh v¸c trích chÂn
thông tin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 TÍng quan v∑ s¸ kiªn . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1
‡nh nghæa s¸ kiªn . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Trích chÂn s¸ kiªn . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Bài toán trích chÂn s¸ kiªn d‡ch bªnh . . . . . . . . . . . . . . . . .
1.3.1 Trích chÂn s¸ kiªn d‡ch bªnh - fi nghæa và t¶m quan trÂng .
1.3.2 Phát hiªn s¸ kiªn . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3 Trích chÂn s¸ kiªn . . . . . . . . . . . . . . . . . . . . . . . .
1.4 fi nghæa bài toán trích chÂn s¸ kiªn d‡ch bªnh . . . . . . . . . . . . .
1.4.1 fi nghæa khoa hÂc . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2 fi nghæa th¸c t∏ . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Khó kh´n và thách th˘c . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 TÍng k∏t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
5
6
7
8
8
9
9
10
10
10
11
11
2 MÎt sË ph˜Ïng pháp ti∏p c™n
2.1 Ph˜Ïng pháp ti∏p c™n d¸a trên lu™t . .
2.1.1 Lu™t cú pháp . . . . . . . . . . .
2.1.2 Lu™t ng˙ nghæa . . . . . . . . . .
2.2 Ph˜Ïng pháp ti∏p c™n d¸a trên hÂc máy
2.3 Ph˜Ïng pháp k∏t hÒp lu™t và hÂc máy .
2.4 MÎt sË nh™n xét . . . . . . . . . . . . . .
2.5 TÍng k∏t . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
12
12
12
13
14
15
15
17
.
.
.
.
18
18
19
20
20
3 Mô
3.1
3.2
3.3
3.4
hình ∑ xußt
Các ∞c tính cıa s¸ kiªn d‡ch bªnh
Phát bi∫u bài toán . . . . . . . . .
Ph˜Ïng pháp ∑ xußt . . . . . . . .
Mô hình phát hiªn và trích chÂn s¸
5
. . .
. . .
. . .
kiªn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
6
M÷C L÷C
3.5
3.6
3.7
Bài toán phát hiªn s¸ kiªn . . . . .
3.5.1 Phát bi∫u bài toán . . . . .
3.5.2 Xây d¸ng t™p lu™t . . . . .
3.5.3 Xây d¸ng mô hình phân lÓp
Bài toán trích chÂn s¸ kiªn . . . . .
3.6.1 Phát bi∫u bài toán . . . . .
3.6.2 Trích chÂn thÌi gian . . . .
3.6.3 Trích chÂn tên bªnh . . . .
3.6.4 Trích chÂn ‡a i∫m . . . .
TÍng k∏t . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Th¸c nghiªm và ánh giá k∏t qu£
4.1 Môi tr˜Ìng và các công cˆ cài ∞t . . . . .
4.1.1 Cßu hình ph¶n c˘ng . . . . . . . . .
4.1.2 Công cˆ ph¶n m∑m . . . . . . . . . .
4.1.3 Các gói ch˜Ïng trình . . . . . . . . .
4.2 Xây d¸ng t™p d˙ liªu . . . . . . . . . . . . .
4.2.1 Thu th™p d˙ liªu . . . . . . . . . . .
4.2.2 Ti∑n x˚ l˛ d˙ liªu . . . . . . . . . . .
4.3
ánh gía quá trình phát hiªn s¸ kiªn . . . .
4.3.1
ánh giá bÎ lÂc d˙ liªu . . . . . . .
4.3.2
ánh giá quá trình phân lÓp . . . .
4.4
ánh gía quá trình trích chÂn s¸ kiªn . . .
4.5 Phân tích lÈi và bàn lu™n . . . . . . . . . . .
4.5.1 Phân tích lÈi bÎ lÂc d˙ liªu . . . . .
4.5.2 Phân tích lÈi quá trình trích chÂn s¸
4.6 TÍng k∏t . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
kiªn
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
22
24
25
25
26
27
27
29
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
30
30
30
30
32
32
33
33
33
34
35
37
37
37
41
Danh mˆc các t¯ vi∏t t≠t
STT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T¯ vi∏t t≠t
IE
IR
DM
DSSs
OMSs
RSs
MUC
ACE
NOAA
TDT
NLP
NER
TF-IDF
CRFs
Maxent
T¯ ¶y ı
Information Extraction
Information Retrieval
Data Mining
Decision Supporting Systems
Online Monitoring Systems
Recommendation Systems
Message Understanding Conference
Automatic Content Extraction
National Oceanic and Atmospheric Administration
Topic Detection and Tracking
Natural Language Processing
Named Entity Recognition
Term Frequency - Inverse Document Frequency
Conditional Random Fields
Maximum Entropy Model
7
Danh sách b£ng
1.1
ThËng kê trên d˙ liªu Twitter . . . . . . . . . . . . . . . . . . . . . .
3
3.1
Danh sách các t¯/cˆm t¯ th˜Ìng xuyên . . . . . . . . . . . . . . . .
23
4.1
4.2
4.3
4.4
4.5
4.6
4.7
Cßu hình ph¶n c˘ng ˜Òc s˚ dˆng trong th¸c nghiªm . . . . . . . .
Công cˆ ph¶n m∑m ˜Òc s˚ dˆng trong th¸c nghiªm . . . . . . . .
Danh sách các lÓp trong t¯ng gói ph¶n m∑m . . . . . . . . . . . . .
Các thành ph¶n cıa mÎt bài báo . . . . . . . . . . . . . . . . . . . .
T lª lÈi cıa ch˘c n´ng lÂc d˙ liªu . . . . . . . . . . . . . . . . . . .
So sánh kh£ n´ng phân lÓp gi˙a Thí nghiªm a and Thí nghiªm b .
So sánh Î chính xác quá trình trích chÂn gi˙a Thí nghiªm c and
Thí nghiªm d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
LÈi trong Thí nghiªm c (15 trên 25 lÈi) . . . . . . . . . . . . . . . .
LÈi trong Thí nghiªm d . . . . . . . . . . . . . . . . . . . . . . . . . .
30
31
32
33
34
35
4.8
4.9
8
36
38
39
Danh sách hình v≥
1.1
1.2
1.3
S¸ t´ng tr˜ng d˙ liªu t¯ n´m 2004 ∏n n´m 2020 . . . . . . . . . .
D˙ liªu trên Internet trong 60 giây . . . . . . . . . . . . . . . . . . .
Các b˜Óc trong quá trình khám phá tri th˘c trong cÏ s d˙ liªu [15]
3.1
3.2
3.3
3.4
Quá trình phát hiªn và trích chÂn s¸ kiªn
Thành ph¶n phát hiªn s¸ kiªn . . . . . . .
Thành ph¶n trích chÂn s¸ kiªn . . . . . .
Bi∫u diπn cıa cây phân cßp ‡a i∫m . . .
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
3
4
21
22
25
28
LÌi nói ¶u
Trích chÂn/trích xußt thông tin (Information Extraction - IE), ∞c biªt là trích
chÂn/trích xußt s¸ kiªn (Event Extraction - EE) là mÎt lænh v¸c con trong khai
phá d˙ liªu (Data Mining - DM). K∏t qu£ cıa quá trình trích chÂn có th∫ ˜Òc
dùng cho các hª thËng hÈ trÒ ra quy∏t ‡nh (Decision Supporting Systems - DSSs),
các hª thËng t˜ vßn (Recommendation Systems - RSs), ho∞c các hª thËng giám
sát tr¸c tuy∏n (Online Monitoring Systems - OMSs) [20].
Nh˙ng n´m g¶n ây, trích chÂn s¸ kiªn ã thu hút nhi∑u s¸ quan tâm t¯ các
nhà khoa hÂc trong lænh v¸c khai phá d˙ liªu nói chung và trích chÂn thông tin
nói riêng. Trích chÂn s¸ kiªn ˜Òc ∑ xußt l¶n ¶u tiên t§i hÎi th£o Message
Understanding Conference n´m 1987 [19]. Trong hÎi ngh‡ này, mÎt s¸ kiªn ˜Òc
‡nh nghæa nh˜ sau: mÎt s¸ kiªn b≠t buÎc ph£i có tác nhân (actor), thÌi gian
x£y ra s¸ kiªn (time), ‡a i∫m (place) và tác Îng tÓi môi tr˜Ìng xung quanh
(impact on the surrounding environment). Bênh c§nh ó, ch˜Ïng trình Automatic
Content Extraction (ACE) ˜a ra ‡nh nghæa: s¸ kiªn là mÎt hành Îng ˜Òc t§o
ra bi ng˜Ìi tham gia và ˜Òc chia thành tám lo§i: cuÎc sËng (life), s¸ di chuy∫n
(movement), s¸ chuy∫n (transection), kinh doanh (business), xung Ît (conflict),
liên hª (contact), con ng˜Ìi (personnel) và lu™t phát (justice). Theo inh nghæa cıa
Allen và cÎng s¸ [1], mÎt s¸ kiªn bao gÁm bËn thuÎc tính: ph˜Ïng th˘c (modality),
s¸ phân c¸c (Positive, Negative), m˘c Î (Specific, Generic) và thÌi i∫m (Past,
Present, Future, Unspecified).
Lu™n v´n "Trích chÂn s¸ kiªn d‡ch bªnh cho hª thËng giám sát tr¸c tuy∏n" t™p
trung vào nghiên c˘u các cách th˘c và ph˜Ïng pháp gi£i quy∏t bài toán trích chÂn
s¸ kiªn d‡ch bªnh. Qua ó, ˜a ra mô hình, gi£i pháp cho vßn ∑ trích chÂn s¸
kiªn d‡ch bªnh trên mi∑n d˙ liªu ti∏ng Viªt. Lu™n v´n s˚ dˆng ph˜Ïng pháp k∏t
hÒp gi˙a lu™t (rule-based) và hÂc máy ∫ gi£i quy∏t hai bài toán lÓn trong nghiên
c˘u, ó là: bài toán phát hiªn s¸ kiªn và bài toán trích chÂn s¸ kiªn. K∏t qu£ cıa
nghiên c˘u là danh sách các s¸ kiªn d‡ch bªnh ˜Òc tr¸c quan hóa trên hª thËng
giám sát tr¸c tuy∏n, nÏi mà ng˜Ìi dùng có th∫ theo dõi tình hình diπn bi∏n d‡ch
bªnh trên lãnh thÍ Viªt Nam.
Cßu trúc lu™n v´n ˜Òc chia làm bËn ch˜Ïng, nÎi dung ˜Òc mô t£ nh˜ sau:
Ch˜Ïng 1: TÍng quan v∑ bài toán trích chÂn s¸ kiªn
Ch˜Ïng này trình bày cÏ b£n v∑ bài toán trích chÂn s¸ kiªn trong bËi c£nh bùng
10
DANH SÁCH HÌNH Vì
11
nÍ thông tin trên Internet. HÏn n˙a, lu™n v´n cÙng ∑ c™p tÓi mÎt sË nghiên c˘u
liên quan v∑ trích chÂn s¸ kiªn, ‡nh nghæa s¸ kiªn. Quan trÂng hÏn, ch˜Ïng này
chø ra ˛ nghæa cıa bài toán trích chÂn s¸ kiªn d‡ch bªnh trên mi∑n d˙ liªu ti∏ng
Viªt. CuËi cùng, tác gi£ trình bày nh˙ng thách th˘c trong bài toán trích chÂn s¸
kiªn d‡ch bªnh và ˘ng dˆng cıa bài toán.
Ch˜Ïng 2: MÎt sË ph˜Ïng pháp ti∏p c™n
Ch˜Ïng này t™p trung trình bày ba ph˜Ïng pháp gi£i quy∏t bài toán phát hiªn và
trích chÂn s¸ kiªn, ó là: ph˜Ïng pháp s˚ dˆng lu™t, ph˜Ïng ti∏p c™n hÂc máy, và
ph˜Ïng pháp k∏t hÒp gi˙a lu™t và hÂc máy. Bên c§nh ó, lu™n v´n cÙng ˜a ra
mÎt sË nh™n xét gi˙a các ph˜Ïng pháp. CuËi cùng, lu™n v´n chø ra ph˜Ïng pháp
phù hÒp vÓi bài toán trích chÂn s¸ kiªn d‡ch bªnh.
Ch˜Ïng 3: Mô hình ∑ xußt
Ch˜Ïng này mô t£ mô hình ∑ xußt cho bài toán phát hiªn và trích chÂn s¸ kiªn
d‡ch bªnh, bên c§nh ó mô t£ chi ti∏t hai bài toán lÓn trong lu™n v´n ó là: bài
toán phát hiªn s¸ kiªn và trích chÂn s¸ kiªn.
Ch˜Ïng 4: Th¸c nghiªm và ánh giá k∏t qu£
Ch˜Ïng này mô t£ quá trình th¸c nghiªm và ánh giá k∏t qu£ cıa ph˜Ïng pháp ∑
xußt d¸a trên hai bài toán lÓn, ó là: bài toán phát hiªn s¸ kiªn và trích chÂn s¸
kiªn. Ba Î o ˜Òc s˚ dˆng trong pha phát hiªn s¸ kiªn là Î chính xác (precision),
Î hÁi t˜ng (recall) và Î o F1 (F1-score), trong khi ó ph˜Ïng pháp ánh giá
thı công ˜Òc áp dˆng trong pha trích chÂn s¸ kiªn.
Ph¶n k∏t lu™n: mô t£ nh˙ng k∏t qu£ §t ˜Òc cıa lu™n v´n, nh˙ng h§n ch∏
và ph˜Ïng h˜Óng phát tri∫n cıa lu™n v´n trong t˜Ïng lai.
Ch˜Ïng 1
TÍng quan v∑ bài toán trích xußt s¸
kiªn
Trích xußt/trích chÂn thông tin óng vai trò quan trÂng giúp con ng˜Ìi gi£i
quy∏t vßn ∑ bùng nÍ d˙ liªu. Ch˜Ïng này s≥ ∑ c™p tÓi bài toán trích chÂn thông
tin trong ng˙ c£nh bùng nÍ d˙ liªu; sÏ l˜Òc v∑ s¸ kiªn, trích chÂn s¸ kiªn, và trích
chÂn s¸ kiªn d‡ch bªnh; nêu rõ ˛ nghæa cıa bài toán trích chÂn s¸ kiªn d‡ch bªnh
và nh˙ng thách th˘c mà bài toán trích chÂn s¸ kiªn d‡ch bªnh c¶n gi£i quy∏t.
1.1
1.1.1
Bài toán trích xußt thông tin t¯ d˙ liªu lÓn
Bài toán trích xußt thông tin
Trích xußt thông tin (IE) có th∫ ˜Òc coi n¨m gi˙a thu hÁi thông tin (Information
Retrieval - IR) và hi∫u v´n b£n (Text Understanding) [3]. Không giËng vÓi thu hÁi
thông tin chø t™p trung vào các m©u thông tin có liên quan trong v´n b£n, trích
xußt thông tin còn quan tâm tÓi các s¸ kiªn có liên quan trong v´n b£n và bi∫u
diπn chúng d˜Ói d§ng các khuôn m®u (template). Bên c§nh ó, khác vÓi hi∫u v´n
b£n chø t™p trung trên mÎt ph¶n nh‰ cıa v´n b£n (câu, o§n v´n), trích xußt thông
tin quan tâm tÓi toàn bÎ nÎi dung v´n b£n.
Theo Peshkin và Pfeffer [29], trích xußt thông tin có th∫ ˜Òc ‡nh nghæa: nh˜
là mÎt công viªc i∑n thông tin vào các m®u t¯ các d˙ liªu không bi∏t tr˜Óc trong
mi∑n ˜Òc ‡nh nghæa tr˜Óc. Mˆc tiêu cıa trích xußt thông tin là lßy t¯ các v´n
b£n các thông tin nÍi b™t cıa các s¸ kiªn, th¸c th∫, ho∞c các mËi quan hª. Nh˜
v™y, có th∫ coi trích xußt thông tin là mÎt kˇ nghª lßy và bi∫u diπn tri th˘c thành
các thông tin có ‡nh d§ng và h˙u ích t¯ nguÁn d˙ liªu vô t™n trên Internet.
V™y bài toán trích chÂn thông tin có th∫ ˜Òc phát bi∫u nh˜ sau:
•
¶u vào: d˙ liªu bßt k˝.
•
¶u ra: thông tin h˙u ích (tri th˘c) có cßu trúc.
1
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
2
D˙ liªu ¶u vào cho bài toán trích chÂn thông tin rßt phong phú và a d§ng. D˙
liªu có th∫ là có cßu trúc (structured), bán cßu trúc (semi-structured), không có
cßu trúc (unstructured), ho∞c có th∫ là d˙ liªu không gian (partial), d˙ liªu thÌi
gian (temporal). VÓi bßt k˝ d§ng d˙ liªu nào, nhiªm vˆ cıa trích chÂn thông tin
cÙng ph£i ˜a ra các k∏t qu£ có cßu trúc ng≠n và ˛ nghæa.
1.1.2
D˙ liªu lÓn - CÏ hÎi và thách th˘c cho lænh v¸c trích chÂn thông tin
“We are drowning in data, but starving for knowledge!" [26] 1 . John chø ra r¨ng
chúng ta ang d˜ th¯a d˙ liªu tuy nhiên l§i nghèo nàn v∑ tri th˘c.
Theo thËng kê cıa NOAA (National Oceanic and Atmospheric Administration,
USA) tính tÓi thÌi i∫m tháng 04-2012, d˙ liªu ng˜Ìi dùng t§o ra trên Internet
kho£ng g¶n 60.000 Terabytes và s≥ t´ng lên kho£ng 160.000 Terabytes trong vòng
8 n´m tÓi. S¸ t´ng tr˜ng ˜Òc minh ho§ trong hình 1.1 2 .
Hình 1.1: S¸ t´ng tr˜ng d˙ liªu t¯ n´m 2004 ∏n n´m 2020
Theo thËng kê t¯ statisticbrain.com 3 ngày 01-01-2014 trên d˙ liªu Twitter, mÈi
ngày có kho£ng 135.000 ng˜Ìi ´ng nh™p vào Twitter; sË l˜Òng các thông iªp mÎt
ngày trên Twitter là kho£ng 58 triªu tweet; trung bình mÈi giây có kho£ng 9.100
thông iªp ˜Òc ng˜Ìi dùng ˜a lên Twitter. SË liªu chi ti∏t ˜Òc minh ho§ trong
b£ng 1.1.
Theo thËng k∏ cıa Qmee 4 5 , d˙ liªu trên Internet trong 60 giây có th∫ ˜Òc
1 John
Naisbitt (www.naisbitt.com/)
http://celebrating200years.noaa.gov/visions/data_mgmt/
3 http://www.statisticbrain.com/twitterstatistics/
4 http://blog.qmee.com/qmee-online-in-60-seconds/
5 http://www.independent.co.uk/life-style/gadgets-and-tech/news/what-happens-in-60-seconds-on-the-internet8738267.html
2
3
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
B£ng 1.1: ThËng kê trên d˙ liªu Twitter
ThËng kê t¯ Twitter
SË l˜Òng các ng˜Ìi dùng ´ng k˛ tích c¸c
SË l˜Òng các ng˜Ìi dùng ´ng nh™p mÎt ngày
SË l˜Òng các trang ∞c biªt ˜Òc th´m hàng tháng
SË l˜Òng thông iªp mÎt ngày
SË l˜Òng các truy vßn thông quan ch˘c n´ng tìm ki∏m mÎt ngày
SË l˜Òng các ng˜Ìi dùng tích c¸c hàng tháng
SË ngày mà tÍng sË thông iªp §t tÓi 1 t
SË l˜Òng các thông iªp mÎt giây
D˙ liªu
645.750.000
135.000
190 triªu
58 triªu
2.1 t
115 triªu
5 ngày
9.100
tr¸c quan hoá nh˜ hình 1.2.
Hình 1.2: D˙ liªu trên Internet trong 60 giây
Thông qua hình 1.2, mÈi giây ng˜Ìi dùng t£i lên 72 giÌ video, có kho£ng 2 triªu
câu truy vßn trên Google, kho£ng 41.000 thông iªp ˜Òc ng˜Ìi dùng Facebook
t£i lên mÈi giây, kho£ng 20 triªu b˘c £nh ˜Òc t£i lên Flick, 204 triªu email ˜Òc
g˚i. Nh˙ng con sË thËng kê trên cho thßy d˙ liªu ˜Òc ˜a lên Internet có sË l˜Òng
lÓn và phong phú v∑ chıng lo§i.
T¯ các thËng kê trên, chúng ta có th∫ thßy r¨ng d˙ liªu có xu h˜Óng bùng nÍ
trên Internet. Tuy nhiên, nhi∑u d˙ liªu không £m b£o r¨ng ng˜Ìi dùng có nhi∑u
thông tin và càng không th∫ nói r¨ng ng˜Ìi dùng có th∫ n≠m b≠t ˜Òc tri th˘c
mÎt cách hi∫n nhiên và dπ dàng. Trong th¸c t∏, quá trình bi∏n Íi t¯ d˙ liªu sang
thông tin và cuËi cùng sang tri th˘c là mÎt quá trình lâu dài, òi h‰i nhi∑u ph˜Ïng
pháp x˚ l˛ ph˘c t§p. Quá trình bi∏n Íi này có th∫ ˜Òc minh ho§ trong hình 1.3.
Theo Fayyad và cÎng s¸ [15], quá trình bi∏n Íi t¯ d˙ liªu thành tri th˘c là
mÎt quá trình bi∏n Íi lâu dài, c¶n nhi∑u b˜Óc x˚ l˛ ph˘c t§p. Trong suËt quá
trình này, d˙ liªu ˜Òc th∫ hiªn ba m˘c: d˙ liªu, thông tin (m®u), và tri th˘c.
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
Articles
4
Interpretation /
Evaluation
Data Mining
Transformation
Knowledge
Preprocessing
Selection
Patterns
--- --- ----- --- ----- --- --Preprocessed Data
Data
Transformed
Data
Target Date
Figure 1. An Overview of the Steps That Compose the KDD Process.
Hình 1.3: Các b˜Óc trong quá trình khám phá tri th˘c trong cÏ s d˙ liªu [15]
ly understandable patterns in data (Fayyad,
Piatetsky-Shapiro, and Smyth 1996).
Here, data are a set of facts (for example,
cases in a database), and pattern is an expression in some language describing a subset of
the data or a model applicable to the subset.
Hence, in our usage here, extracting a pattern
also designates fitting a model to data; finding structure from data; or, in general, making any high-level description of a set of data.
The term process implies that KDD comprises
many steps, which involve data preparation,
search for patterns, knowledge evaluation,
and refinement, all repeated in multiple iterations. By nontrivial, we mean that some
search or inference is involved; that is, it is
not a straightforward computation of
predefined quantities like computing the average value of a set of numbers.
The discovered patterns should be valid on
new data with some degree of certainty. We
also want patterns to be novel (at least to the
system and preferably to the user) and potentially useful, that is, lead to some benefit to
the user or task. Finally, the patterns should
be understandable, if not immediately then
after some postprocessing.
The previous discussion implies that we can
define quantitative measures for evaluating
extracted patterns. In many cases, it is possible to define measures of certainty (for example, estimated prediction accuracy on new
data) or utility (for example, gain, perhaps in
dollars saved because of better predictions or
speedup in response time of a system). Notions such as novelty and understandability
are much more subjective. In certain contexts,
understandability can be estimated by simplicity (for example, the number of bits to describe a pattern). An important notion, called
interestingness (for example, see Silberschatz
and Tuzhilin [1995] and Piatetsky-Shapiro and
Matheus [1994]), is usually taken as an overall
measure of pattern value, combining validity,
novelty, usefulness, and simplicity. Interestingness functions can be defined explicitly or
can be manifested implicitly through an ordering placed by the KDD system on the discovered patterns or models.
Given these notions, we can consider a
pattern to be knowledge if it exceeds some interestingness threshold, which is by no
means an attempt to define knowledge in the
philosophical or even the popular view. As a
matter of fact, knowledge in this definition is
purely user oriented and domain specific and
is determined by whatever functions and
thresholds the user chooses.
Data mining is a step in the KDD process
that consists of applying data analysis and
discovery algorithms that, under acceptable
computational efficiency limitations, produce a particular enumeration of patterns (or
models) over the data. Note that the space of
– ây, d˙ liªu có th∫ coi là mÎt t™p hÒp các s¸ kiªn (các b£n ghi trong cÏ s d˙
liªu). Thông tin (m®u) là mÎt s¸ bi∫u diπn trong mÎt ngôn ng˙ mô t£ cıa mÎt
t™p con d˙ liªu. CuËi cùng, thông tin s≥ là tri th˘c n∏u nó v˜Òt qua mÎt ng˜Ông
(threshold). Trong khuôn khÍ lu™n v´n, tác gi£ Áng quan i∫m v∑ d˙ liªu, thông
tin, và tri th˘c vÓi Fayyad và cÎng s¸.
MÎt i∑u rõ ràng, s¸ bùng nÍ d˙ liªu trên Internet t§o ra nh˙ng thu™n lÒi và
thách th˘c cho các nhà khoa hÂc khi muËn thu hÁi thông tin. ¶u tiên, s¸ phát
tri∫n cıa Internet và s¸ bùng nÍ thông tin t§o ra nhi∑u nguÁn thông tin. N∏u nh˜
tr˜Óc ây, nguÁn d˙ liªu chı y∏u là v´n b£n (text) thì hiªn nay d˙ liªu rßt phong
phú, bao gÁm các d˙ liªu v´n b£n, hình £nh, âm thanh, các d˙ liªu thÌi gian, không
gian...Nh˙ng nguÁn d˙ liªu t§o i∑u kiªn thu™n lÒi cho nh˙ng nghiên c˘u v∑ trích
chÂn thông tin. Bên c§nh ó, d˙ liªu hiªn nay không Ïn thu¶n là tin t˘c, nó còn
bao gÁm thông tin cá nhân (c£m xúc, ˛ ki∏n). T¯ nh˙ng d˙ liªu
mÓi này, trích
FALL 1996 41
chÂn thông tin có th∫ thu hÁi nh˙ng thông tin mÓi phˆc vˆ cho quá trình tích hÒp
thông tin.
Tuy nhiên, bên c§nh nh˙ng thu™n lÒi, s¸ bùng nÍ v∑ d˙ liªu t§o ra nh˙ng thách
th˘c không nh‰ trong lænh v¸c trích chÂn thông tin. ¶u tiên, vÓi s¸ ra Ìi cıa
các d˙ liªu mÓi òi h‰i c¶n ph£i có nh˙ng kˇ thu™t phù hÒp. ôi khi trong mÎt sË
tr˜Ìng hÒp, trích chÂn thông tin ph£i ˜Ïng ¶u vÓi nh˙ng d˙ liªu ph˘c t§p nh˜
hình £nh, âm thanh, d˙ liªu không gian, ho∞c thÌi gian. Th˘ hai, s¸ ang d§ng v∑
nguÁn d˙ liªu òi h‰i quá trình tích hÒp d˙ liªu ph˘c t§p. i∑u này xußt phát do
mˆc ích cıa trích chÂn thông tin là lßy ra mÎt l˜Òng nh‰ thông tin có ˛ nghæa,
do ó, sau quá trình trích chÂn, d˙ liªu c¶n ˜Òc tÍng hÒp t¯ nhi∑u nguÁn khác
nhau ∫ cuËi cùng ˜a ra d˙ liªu có ˛ nghæa vÓi ng˜Ìi dùng. CuËi cùng, bài toán
v∑ tËc Î x˚ l˛ và tính toán c¶n ˜Òc gi£i quy∏t. VÓi s¸ bùng nÍ v∑ sË l˜Òng và
ph˘c t§p v∑ nÎi dung yêu c¶u các ph˜Ïng pháp trích chÂn thông tin ph£i có thÌi
gian x˚ l˛ hÒp l˛.
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
5
Nh˜ ã ∑ c™p trên, chúng ta có th∫ thßy rõ t¶m £nh h˜ng cıa d˙ liªu lÓn
(Big Data) tÓi quá trình thu hÁi thông tin cıa con ng˜Ìi và vai trò cıa trích chÂn
thông tin trong bËi c£nh thông tin bùng nÍ và gây khó kh´n cho ng˜Ìi dùng trong
quá trình ti∏p c™n tri th˘c.
1.2
TÍng quan v∑ s¸ kiªn
VÓi vai trò trích chÂn ra các thông tin có ˛ nghæa t¯ t™p lÓn các d˙ liªu, trích
chÂn s¸ kiªn ˜Òc cÎng Áng khoa hÂc rßt quan tâm và ¶u t˜ nghiên c˘u. N´m
1987, Message Understanding Conferences (MUC) 6 ˜Òc tÍ ch˘c vÓi s¸ hÈ trÒ
cıa Quˇ nghiên c˘u BÎ quËc phòng Hoa K˝ 7 và l¶n ¶u tiên khái niªm s¸ kiªn
event ˜Òc ∑ c™p. Sau ó, rßt nhi∑u hÎi ngh‡ ˜Òc tÍ ch˘c t§o thành dãy hÎi ngh‡
MUC. VÓi mÈi hÎi ngh‡, thông tin ˜Òc quan tâm khác nhau nh˜ng ∑u có ∞c
i∫m chung là chúng ˜Òc trích xußt t¯ d˙ liªu nói v∑ khıng ho£ng (crisis). Các
chı ∑ trong d˙ liªu th˜Ìng là tÎi ph§m, khıng bË, ánh bom...MÎt trong nh˙ng
óng góp lÓn cıa MUC là ˜a ra viªc trích xußt thông tin d¸a trên m®u (scenario
template). Các m®u ˜Òc ban tÍ ch˘c quy ‡nh và các Îi tham gia c¶n i∑n thông
tin vào các m®u này mÎt cách t¸ Îng. CuËi cùng, các s¸ kiªn ˜Òc trích chÂn gÁm
các thông tin: tÍ ch˘c, Ëi t˜Òng tham gia (ng˜Ìi, s¸ v™t, s¸ viªc), thÌi gian, ‡a
i∫m, sË l˜Òng... Î chính xác (precision) và hÁi t˜ng (recall) cıa các nghiên c˘u
tham d¸ MUC n¨m trong kho£ng 50% ∏n 60% [19].
Ch˜Ïng trình Phát hiªn và theo dõi chı ∑ (Topic Detection and Tracking,
TDT) 8 ˜Ò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 tÍ ch˘c bi Viªn Công nghª
và Chu©n hoá quËc gia Hoa K˝ (NIST) và DAPRA 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 này nh˜: nhóm CMU cıa §i hÂc Carnegie Mellon, nhóm BBN t¯ công ty
BBN Technologies, nhóm DRAGON cıa công ty Dragon Systems, 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: Story Segmentation, Topic Tracking, Topic Detection, First Story Detection,
and Link Detection 9 .
Ch˜Ïng trình Trích xußt nÎi dung t¸ Îng (Automatic Content Extraction,
ACE) 10 11 cıa §i hÂc Pennsylvania cÙng thu hút ˜Òc nhi∑u s¸ quan tâm t¯
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à A r™p
(Arabic). 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
6 http://www-nlpir.nist.gov/related_projects/muc
7 http://en.wikipedia.org/wiki/DARPA
8 http://projects.ldc.upenn.edu/TDT/
9 http://www.itl.nist.gov/iad/mig//tests/tdt/
10 http://projects.ldc.upenn.edu/ace
11 http://www.itl.nist.gov/iad/mig/tests/ace/
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
6
th∫, và các s¸ kiªn chúng tham gia vào. ACE có mˆc ích giËng vÓi MUC, tuy
nhiên ch˜Ïng trình này t™p trung vào các Ëi t˜Òng (th¸c th∫, mËi quan hª th¸c
th∫ và các s¸ kiªn) hÏn là t™p trung vào các t¯ (term of words) trong v´n b£n 12 .
Nh˜ v™y, có th∫ thßy r¨ng trích chÂn thông tin nói chung và trích chÂn s¸ kiªn
nói riêng là mÎt vßn ∑ quan trÂng và thÌi s¸, nh™n ˜Òc rßt nhi∑u quan tâm t¯
cÎng Áng khoa hÂc. Trong ph¶n ti∏p theo, lu™n v´n s≥ làm sáng t‰ ‡nh nghæa v∑
s¸ kiªn cÙng nh˜ bài toán trích chÂn s¸ kiªn.
1.2.1
‡nh nghæa s¸ kiªn
Trích chÂn s¸ kiªn l¶n ¶u tiên ˜Òc giÓi thiªu nh˜ mÎt chı ∑ quan trÂng trong
Message Understanding Conference (MUC) n´m 1987 [19]. Trong MUC, mÎt s¸
kiªn ˜Òc ‡nh nghæa nh˜ sau: “mÎt s¸ kiªn ph£i có tác nhân (actor), thÌi gian
(time), ‡a i∫m (place), và tác Îng tÓi môi tr˜Ìng xung quanh". Khi tham gia
MUC, các nhóm nghiên c˘u ph£i ∑ xußt ph˜Ïng pháp ∑ i∑n các thông tin
vào các m®u cho tr˜Óc (scenario template). Các m®u này gÁm nhi∑u thành ph¶n
(slots/elements) khác nhau t˜Ïng ˘ng vÓi các thành ph¶n ˜Òc ‡nh nghæa bên
trên. ThÌi gian ban ¶u, MUC chø t™p trung nghiên c˘u các s¸ kiªn quân s¸. Tuy
nhiên, các l¶n tÍ ch˘c sau, các lo§i s¸ kiªn mÓi ˜Òc bÍ sung nh˜ khıng bË, ¶u
t˜ m§o hi∫m, tai n§n máy bay...
Trong ch˜Ïng trình ACE, Dodington George R. và cÎng s¸ ˜a ra ‡nh nghæa
s¸ kiªn nh˜ sau: “mÎt s¸ kiªn là mÎt hành Îng ˜Òc t§o bi nh˙ng ng˜Ìi tham
gia" [13]. ACE chia s¸ kiªn thành 8 lo§i khác nhau gÁm: LIFE (s¸ sËng–ch∏t),
MOVEMENT (s¸ di chuy∫n), TRANSACTION (giao d‡ch), BUSINESS (kinh t∏),
CONFLICT (xung Ît), CONTACT (giao thiªp, g∞p gÔ), PERSONNEL (nh™nuÍi viªc), JUSTICE (pháp l˛). MÈi d§ng s¸ kiªn l§i phân biªt t¯ng d§ng con. Ví
dˆ, LIFE có các d§ng s¸ kiªn con nh˜ BE-BORN (chào Ìi), INJURE (b‡ th˜Ïng),
DIE (ch∏t), hay PERSONAL có START-POSITION (v‡ trí khi nh™n viªc), ENDPOSITION (v‡ trí khi thôi viªc), NOMINATE (bÍ nhiªm), ELECT (b¶u chÂn),...
Trong nghiên c˘u cıa mình, Allen và cÎng s¸ cho r¨ng mÎt s¸ kiªn ˜Òc ph£n
ánh qua tin t˘c khi nó có 4 y∏u tË: ph˜Ïng th˘c (modality), tính Ëi c¸c (polarity), s¸ tÍng quát (genericity), và thÌi i∫m (tense) [1]. Trong ó, ph˜Ïng th˘c là
hành vi gây ra s¸ kiªn; tính Ëi c¸c là s¸ kiªn ó gây tác Îng tËt hay xßu (possitive/negative); s¸ tÍng quát là s¸ kiªn ó có tính chung hay riêng (specific/generic);
và thÌi i∫m là thÌi gian s£y ra s¸ kiªn (past, present, future, ho∞c unspecified).
Trong mi∑n d˙ liªu liên quan tÓi d‡ch bênh, Gishman R. và cÎng s¸ ˜a ra ‡nh
nghæa v∑ mÎt s¸ kiªn nh˜ là mÎt m®u (template) gÁm các thuÎc tính: tên bªnh
(disease name), thÌi gian (date), ‡a i∫m (location), sË l˜Òng n§n nhân (victime
number), mô t£ v∑ n§n nhân (victim descriptor), tình tr§ng (victim status), lo§i
12 http://en.wikipedia.org/wiki/Automatic_Content_Extraction
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
7
n§n nhân (victim type), và s¸ kiªn cha (parent event) [17]. S¸ khác biªt trong
‡nh nghæa cıa Grishman vÓi các ‡nh nghæa khác chÈ ông ∑ c™p thêm tÓi s¸
kiªn cha. Trong th¸c t∏, mÎt s¸ kiªn có th∫ là s¸ kiªn b≠t ¶u ho∞c ˜Òc b≠t ¶u
t¯ mÎt s¸ kiªn khác (parent event). Nh˜ v™y, quá trình trích chÂn s¸ kiªn không
Ïn gi£n chø lßy ra các thông tin t˜Ïng ˘ng vÓi m®u ˜Òc ‡nh nghæa mà c¶n phát
hiªn thêm s¸ kiªn ban ¶u cıa s¸ kiªn hiªn t§i.
Trong công bË cıa Nguyen và cÎng s¸ [27], các tác gi£ quan niªm mÎt s¸ kiªn
d‡ch bªnh là mÎt m®u (template) gÁm các thuÎc tính tên bªnh (disease name), thÌi
i∫m bùng phát (time), và ‡a i∫m bùng phát (location). Khác vÓi quan niªm cıa
Grishman và cÎng s¸, các tác gi£ chø quan tâm tÓi 3 thuÎc tính cho mˆc ích tr¸c
quan hoá hÏn là trích chÂn các thông tin chi ti∏t cıa s¸ kiªn và phát hiªn chuÈi s¸
kiªn. Trong mi∑n d˙ liªu ti∏ng Viªt, Tran và các cÎng s¸ [38] quan tâm tÓi ba lo§i
s¸ kiªn chính gÁm: cháy nÍ, tÎi ph§m, và t§i n§n giao thông. Mˆc tiêu cıa tác gi£
là trích chÂn ra các thông tin cÏ b£n cıa ba lo§i s¸ kiªn và tr¸c quan hoá chúng
trên mÎt b£n Á theo dõi s¸ kiªn.
Có th∫ thßy r¨ng các nghiên c˘u liªt kê trên ∑u Áng ˛ r¨ng s¸ kiªn có th∫
coi nh˜ mÎt m®u (template) gÁm nhi∑u các thuÎc tính (elements). Quá trình trích
chÂn s¸ kiªn quan tâm tÓi viªc làm th∏ nào có th∫ i∑n các thông tin phù hÒp t¯
v´n b£n gËc t˜Ïng ˘ng vÓi t¯ng thuÎc tính.
1.2.2
Trích chÂn s¸ kiªn
Trích xußt s¸ kiªn có th∫ coi là mÎt lænh v¸c con cıa trích chÂn thông tin. Tuy
nhiên, trích chÂn s¸ kiªn có s¸ khác biªt vÓi lænh v¸c cha cıa nó. N∏u nh˜ trích
chÂn thông tin chø quan tâm vÓi các d˙ liªu rÌi r§c (tên ng˜Ìi, ‡a i∫m, các con
sË,...) thì trích chÂn s¸ kiªn quan tâm nhi∑u hÏn tÓi tính cßu trúc và m˘c Î liên
quan cıa thông tin trong mÎt s¸ kiªn. Qua ó, ng˜Ìi Âc có th∫ dπ dàng suy lu™n
ra các thông tin có ˛ nghæa. Ví dˆ, vÓi câu “Thêm mÎt tr¥ t˚ vong do bªnh tay chân
miªng t§i Qu£ng Nam vào ngày 12/06/2012". Trong ví dˆ này, trích chÂn thông
tin ˜a ra các k∏t qu£ rÌi r§c nh˜: mÎt, Qu£ng Nam, ho∞c 12/06/2012 ; trong khi
trích chÂn s¸ kiªn s≥ ˜a ra mÎt bÎ các thuÎc tính bi∫u diπn cho s¸ kiªn gÁm {tay
chân miªng, Qu£ng Nam, 12/06/2012}. Rõ ràng, vÓi t™p d˙ liªu trên, thông tin
s≥ h˙u ích và ¶y ı hÏn các thông tin rÌi r§c.
MÎt cách tÍng quát, có th∫ coi trích chÂn s¸ kiªn nh™n ¶u vào là các v´n b£n
không có cßu trúc và ¶u ra là tri th˘c ˜Òc bi∫u diπn d˜Ói d§ng thông tin có
cßu trúc. Nh˙ng thông tin này có th∫ làm ¶u vào cho nh˙ng hª thËng giám sát
(monitoring systems) ho∞c các hª thËng hÈ trÒ ra quy∏t ‡nh (supported decision
systems). Trích chÂn s¸ kiªn có th∫ ˜Òc áp dˆng cho mÎt mi∑n d˙ liªu cˆ th∫
(close domain) nh˜ d‡ch bªnh, cháy nÍ,... ho∞c mi∑n d˙ liªu m (open domain),
Áng thÌi ˜a ra các thông tin xung quang s¸ kiªn ó, thông th˜Ìng bao gÁm: tác
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
8
nhân, thÌi gian, ‡a i∫m, sË l˜Òng,...
Theo Grishman và cÎng s¸, trích chÂn s¸ kiªn là mÎt bài toán khó do vßn ∑
x˚ l˛ ngôn ng˙ t¸ nhiên (Natural Language Processing - NLP) và ∞c tr˜ng d˙
liªu [19]. Dπ dàng nh™n thßy trích chÂn s¸ kiªn phˆ thuÎc nhi∑u vào NLP, cˆ th∫
là bài toán nh™n d§ng th¸c th∫ (Named Entity Recognition - NER). M∞c dù NER
ã thu ˜Òc nh˙ng k∏t qua kh£ quan, tuy nhiên v®n còn mÎt sË thách th˘c lÓn,
∞c biªt vÓi các ngôn ng˙ không ph£i ti∏ng Anh. Bên c§nh ó, d˙ liªu ¶u vào cıa
trích chÂn s¸ kiªn rßt a d§ng nên s≥ £nh h˜ng tÓi tính hiªu qu£ cıa quá trình
trích chÂn.
1.3
1.3.1
Bài toán trích chÂn s¸ kiªn d‡ch bªnh
Trích chÂn s¸ kiªn d‡ch bªnh - fi nghæa và t¶m quan trÂng
Trích chÂn s¸ kiªn d‡ch bªnh có th∫ coi là mÎt lænh v¸c con trong trích chÂn s¸
kiªn. N∏u nh˜ trích chÂn s¸ kiªn có th∫ áp dˆng cho c£ mi∑n d˙ liªu óng (close
domain) ho∞c mi∑n d˙ liªu m (open domain) thì trích chÂn s¸ kiªn d‡ch bªnh chø
quan tâm tÓi nh˙ng v´n b£n liên quan tÓi d‡ch bªnh. Ví dˆ, khi ng˜Ìi dùng Âc
các bài báo liên quan tÓi mÎt d‡ch bªnh (tay chân miªng), h muËn lßy ra các
thông tin cÏ b£n, dπ nhÓ cıa toàn bÎ bài báo gÁm: tên bªnh, ‡a i∫m bùng phát,
và thÌi gian bùng phát. Nh˜ v™y, yêu c¶u là c¶n ph£i trích chÂn ˜Òc các thông
tin cÏ b£n cıa mÎt s¸ kiªn d‡ch bªnh t¯ mÎt v´n b£n ¶u vào.
Bài toán trích chÂn d‡ch bªnh có ˛ nghæa quan trÂng không chø trong nghiên
c˘u mà còn trong Ìi sËng, ∞c biªt trong tr˜Ìng hÒp các d‡ch bªnh nguy hi∫m
bùng phát và lây lan trên diªn rÎng. Do mÎt d‡ch bªnh th˜Ìng bùng phát trong
mÎt thÌi gian ng≠n và lân lan rßt nhanh trên mÎt ph§m vi rÎng, do v™y nó có th∫
t§o ra các tình huËng xßu £nh h˜ng tÓi ng˜Ìi dân và n∑n kinh t∏. Do ó, trích
chÂn và giám sát s¸ lây lan cıa các d‡ch bªnh có ˛ nghæa rßt quan trÂng trong viªc
Ëi phó vÓi s¸ lây lan cıa chúng.
Bài toán phát hiªn và trích chÂn s¸ kiªn d‡ch bªnh ˜Òc ∑ c™p t¯ khá sÓm
và nh™n ˜Òc nhi∑u s¸ quan tâm t¯ phía các nhà khoa hÂc. Grishman và cÎng s¸
[17] s˚ dˆng các m®u s¸ kiªn (event patterns) ∫ phân tích các câu ¶u vào và
trích chÂn ra các s¸ kiªn d‡ch bªnh. Các m®u s¸ kiªn này ˜Òc xây d¸ng d¸a trên
mËi quan hª gi˙a các t¯. Ví dˆ, m®u “np (DISEASE) vg (KILL) np (VICTIM)"
s≥ ˜Òc s˚ dˆng ∫ Ëi sánh vÓi câu “Cholera killed 23 inhabitants". MÎt s¸ kiªn
˜Òc phát hiªn d¸a trên ràng buÎc cıa hai cˆm danh t¯ gÁm: outbreak of... và
died from.... Trong nghiên c˘u cıa mình, hiªu qu£ cıa quá trình trích chÂn kho£ng
53.98% (F-score).
Volkova và cÎng s¸ [39] quan tâm tÓi trích chÂn s¸ kiªn d‡ch bªnh trên Îng
v™t. Quá trình nh™n d§ng s¸ kiªn gÁm ba b˜Óc: ¶u tiên là nh™n d§ng th¸c th∫ t¯
CH◊ÃNG 1. T NG QUAN Vó BÀI TOÁN TRÍCH XUáT S‹ KIõN
9
các b´n b£n không có cßu trúc, th˘ hai là phân lÓp các câu d¸a trên các th¸c th∫,
và cuËi cùng là các th¸c th∫ trong mÎt câu ˜Òc k∏t hÒp ∫ t§o thành s¸ kiªn. Î
chính xác trong pha nh™n d§ng s¸ kiªn và phân lÓp l¶n l˜Òt là 75% và 65% trên
hai t™p d˙ liªu là WordNet và GoogleSet.
Doan và các cÎng s¸ [12] xây d¸ng hª thËng Global Health Monitor cho phép
hi∫n th‡ các s¸ kiªn d‡ch bªnh trên toàn th∏ giÓi. Hª thËng gÁm ba thành ph¶n
chính: (1) phân lÓp chı ∑, (2) nh™n d§ng th¸c th∫ (NER), và (3) phát hiªn các
thành ph¶n cıa s¸ kiªn (disease/location detection). Các tác gi£ s˜ dˆng Naive
Bayes cho bài toán phân lÓp chı ∑ và §t Î chính xác kho£ng 88.10%. Trong
thành ph¶n nh™n d§ng th¸c th∫, các tác gi£ s˚ dˆng Support Vector Machine và
§t Î chính xác vào kho£n 76.97% (F-score). Trong b˜Óc cuËi cùng, tác gi£ s˚
dˆng mÎt Ontology [9] vÓi Î chính xác kho£ng 93.49%.
Nh˜ v™y, cÙng giËng nh˜ ‡nh nghæa v∑ s¸ kiªn, mÎt s¸ kiªn d‡ch bªnh có th∫
coi nh˜ mÎt m®u (template) ch˘a các thuÎc tính cıa s¸ kiªn. Trích chÂn s¸ kiªn
d‡ch bªnh chø quan tâm tÓi nh˙ng d˙ liªu liên quan tÓi d‡ch bªnh (con ng˜Ìi ho∞c
Îng v™t).
1.3.2
Phát hiªn s¸ kiªn
Bài toán trích chÂn s¸ kiªn d‡ch bªnh có th∫ phát bi∫u thành hai bài toán nh‰,
ó là: bài toán phát hiªn s¸ kiªn và bài toán 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
d‡ch bªnh?". T˘c là cho tr˜Óc ¶u vào là mÎt v´n b£n, quá trình phát hiªn s¸ kiªn
ph£i quy∏t ‡nh v´n b£n ó có ch˘a s¸ kiªn d‡ch bªnh hay không? Theo Grishman
và cÎng s¸ [17], 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¯ khoá ∫ quy∏t ‡nh mÎt v´n b£n có ch˘a s¸ kiªn d‡ch bªnh hay không. Hai
t¯ khoá ˜Òc tác gi£ s˚ dˆng là “outbreak of..." và “died from...".
Theo Doan và cÎng s¸ [12], bài toán phát hiªn s¸ kiªn có th∫ coi nh˜ quá trình
hÂc có giám sát. Trong nghiên c˘u cıa mình, tác gi£ s˜ dˆng ph˜Ïng pháp phân
lÓp Naive Bayes ∫ phân lÓp các tài liªu. BÎ phân lÓp này d¸a trên mÎt t™p các
d˙ liªu ã ˜Òc gán nhãn. Qua quá trình hußn luyªn, bÎ phân lÓp s≥ quy∏t ‡nh
mÎt v´n b£n ¶u vào có ch˘a s¸ kiªn d‡ch bªnh hay không.
1.3.3
Trích chÂn s¸ kiªn
N∏u nh˜ bài toán phát hiªn s¸ kiªn tr£ lÌi câu h‰i “mÎt v´n b£n có ch˘a s¸ kiªn
hay không?", thì bài toán trích chÂn s¸ kiªn tr£ lÌi câu h‰i “làm th∏ nào trích chÂn
các thuÎc tính cıa mÎt s¸ kiªn?". Ph˜Ïng pháp s˚ dˆng lu™t (hÂc không giám sát)
˜Òc s˚ dˆng t¯ rßt sÓm ∫ gi£i quy∏t bài toán này [17]. Quá trình trích chÂn b¨ng
ph˜Ïng pháp này th˜Ìng s˚ dˆng các lu™t d¸a trên quá trình kh£o sát d˙ liªu ∫
trích chÂn ra các thuÎc tính cıa mÎt s¸ kiªn.
- Xem thêm -