Đăng ký Đăng nhập
Trang chủ Trích chọn sự kiện dịch bệnh cho hệ thống giám sát trực tuyến...

Tài liệu Trích chọn sự kiện dịch bệnh cho hệ thống giám sát trực tuyến

.PDF
61
107
122

Mô tả:

Ñ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 bi 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 bi 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 bi 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 -

Tài liệu liên quan