Bài giảng Khai phá dữ liệu Web - Chương 3+4 - Hà Quang Thụy

Nội dung text: Bài giảng Khai phá dữ liệu Web - Chương 3+4 - Hà Quang Thụy

1. BÀI GIẢNG KHAI PHÁ DỮ LIỆU WEB CHƯƠNG 3. MỘT SỐ KIẾN THỨC TỐN HỌC BỔ TRỢ CHƯƠNG 4. MỘT SỐ BÀI TỐN XỬ LÝ NGƠN NGỮ TỰ NHIÊN NỀN TẢNG PGS. TS. HÀ QUANG THỤY HÀ NỘI 10-2010 TRƯỜNG ĐẠI HỌC CƠNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI 1
2. Nội dung 1. Một số kiến thức Tốn học bổ trợ 2. Một số bài tốn xử lý ngơn ngữ tự nhiên nền tảng 2
3. C3. Một số kiến thức Tốn học bổ trợ ⚫ Tốn học Internet ➢ Ra đời một lĩnh vực mới: Internet Mathematics ➢ Cộng đồng Tốn học Internet: Internet Mathematics Community ⚫ Đối tượng và các chủ đề ➢ Đối tượng: Mạng phức tạp trên Internet và Web: đồ thị Web, đồ thị Internet, mạng xã hội trực tuyến (Facebook, LinkedIn, và Twitter ), mạng sinh học trên Web ➢ Các chủ đề thuộc khai phá và mơ hình hĩa web (cơ sở lý thuyết và ứng dụng thực tiễn) trong mơi trường mạng phức tạp. ⚫ Tạp chí Internet Mathematics ➢ (2/2011 - xem trang sau) ➢ Đồng Trưởng ban biên tập: ❑ Fan Chung Graham ( DBLP: 137 bài báo ❑ Anthony Bonato ( DBLP: 35 bài báo ➢ Cơng bố bài báo chất lượng cao về mạng phức 3
4. Tạp chí Internet Mathematics ⚫ Ban biên tập tạp chí: Bổ sung một số chuyên gia Jennifer Tour Chayes “She is the co-author of over 100 scientific papers and the co-inventor of more than 25 patents” Rick Durrett . Andrew Tomkins DBLP: 88 bài báo ⚫ Một số biên tập viên được lưu ý Ronald L. Graham ( DBLP:116 bài báo. Nhiều giải thưởng 4 Frank Kelly ( )
5. Một số nội dung Tốn học bổ trợ ⚫ Mơ hình đồ thị ➢ Một số kiến thức cơ sở ➢ Đồ thị ngẫu nhiên ➢ Mạng xã hội ⚫ Học máy xác suất Bayes ➢ Một số kiến thức cơ sở ➢ Học máy xác suất Bayes ➢ Ước lượng giá trị tham số ⚫ Thuật tốn Viterbi ➢ Lý thuyết quyết định hỗn hợp ➢ Nội dung thuật tốn 5
6. Đồ thị Web và đồ thị ngẫu nhiên ⚫ Đồ thị Web ➢ Web cĩ cấu trúc đồ thị ➢ Đồ thị Web: nút  trang Web, liên kết ngồi  cung (cĩ hướng, vơ hướng). ➢ Bản thân trang Web cũng cĩ tính cấu trúc cây (đồ thị) ➢ Một vài bài tốn đồ thị Web ➢ Biểu diễn nội dung, cấu trúc ➢ Tính hạng các đối tượng trong đồ thị Web: tính hạng trang, tính hạng cung Nghiên cứu về đồ thị Web (xem trang sau) ⚫ Đồ thị ngẫu nhiên ➢ Tính ngẫu nhiên trong khai phá Web ➢ WWW cĩ tính ngẫu nhiên: mới, chỉnh sửa, loại bỏ ➢ Hoạt động con người trên Web cũng cĩ tính ngẫu nhiên ➢ Là nội dung nghiên cứu thời sự 6
7. Bibliography Webgraph Papers Dragomir R. Radev, 03/4/2010 Tồn bộ 2007 2008 2009 To 04/10 2007-10 1542 127 61 36 13 237 ⚫ So many webgraph research papers. ⚫ Some previous versions of “Bibliography Webgraph Papers” by Dragomir R. Radev ⚫ 1601: 5/2005 5/2007 5/2008 1/2009 8/2009 4/2010 11/2010 496 1212 1361 1457 1471 1542 1601 7
8. Lý thuyết về đồ thị lớn Đồ thị lớn ⚫ Số đỉnh lên tới hàng tỷ ⚫ Biểu diễn cung chính xác khơng cịn là quan trọng Cơ sở lý thuyết trong nghiên cứu đồ thị lớn ⚫ Khả năng là lý thuyết sinh đồ thị ⚫ Bất biến tới một số thay đổi nhỏ trong định nghĩa ⚫ Phải cĩ năng lưc chứng minh các định lý cơ bản [Hop07] John E. Hopcroft (2007). Future Directions in Computer Science, 8
9. Đồ thị ngẫu nhiên: Mơ hình Erdưs-Renyi ⚫ Đồ thị ngẫu nhiên: cĩ thể mơ hình mạng thế giới thực. ⚫ Định nghĩa: cĩ hai định nghĩa ⚫ Chọn ngẫu nhiên: Gn, N được chọn ngẫu nhiên từ n, N = {mọi đồ thị cĩ n đỉnh và N cung}’ các phần tử trong n, N là đồng n khả năng được chọn với xác suất 1/(( 2)/N); ⚫ Quá trình hình thành các cung trong Gn, N là ngẫu nhiên: mỗi cạnh xuất hiện với xác suất p, sự xuất hiện hay vắng mặt hai cạnh là độp lập nhau. [ER61] P. Erdưs, A. Rényi (1961). On the evolution of random graphs, Théorie de L'Information: 343-347, 1961. 9
10. Đồ thị ngẫu nhiên: Mơ hình Erdưs-Renyi ⚫ Đặt tên: Paul Erdős và Alfréd Rényi ⚫ Là một trong hai mơ hình sinh các đồ thị ngẫu nhiên ⚫ Chứa tập các nút mà mỗi nút trong mỗi tập đĩ cĩ xác suất như nhau, độc lập với các cung khác ⚫ n nút: Mỗi bộ n2 cung tiềm năng được biểu diễn với xác xuất độc lập N pn (1-p)N-n Số lượng n các nút Độ nút Phân bố độ nhị thức 10
11. Đồ thị ngẫu nhiên [Hop07] John E. Hopcroft (2007). Future Directions in Computer Science, 11
12. Mơ hình sinh đồ thị ⚫ Các nút và cung được bổ sung sau mỗi đơn vị thời gian ⚫ Quy tắc xác định nơi cung xuất hiện (nơi đặt cung mới) ⚫ Xác suất đồng nhất ⚫ Đính kèm ưu đãi – đưa đến phân bố theo luật số lớn [Hop07] John E. Hopcroft (2007). Future Directions in Computer Science, 12
13. Mạng xã hội ⚫ Mạng xã hội ➢ Internet, Web là một xã hội ảo ➢ Nhiều hoạt động (đặc biệt là hoạt động thơng tin) trong thế giới thực được thi hành ➢ “Thế giới phẳng”, “tồn cầu hĩa” và “bản địa hĩa” ➢ Khái niệm ❖ Mạng xã hội là mạng của một nhĩm người cĩ hoạt động và các mối quan hệ gắn kết họ với nhau. ❖ Mạng xã hội là một kiểu của mạng phức tạp ➢ Một số ví dụ mạng xã hội trên Internet ❖ Diễn đàn, Blog, Mạng e-mail, mạng xã hội chuyên đề ❖ Một số ví dụ khác (trang bên) ➢ Nghiên cứu mạng xã hội ❖ Vấn đề nghiên cứu thời sự. ❖ Kết hợp nhiều lĩnh vực, chẳng hạn như CNTT + Xã hội học 13
14. Mạng xã hội: ví dụ 295/docs/2008-01UVM-295smallworldnetworks-slides-handout.pdf 14
15. Social Networks: Properties • The small-world property ❑ Almost any pair of people in the world can be connected together by a short chain of intermediate acquaintances, usually about six lengths. [TM69] Jeffrey Travers, Stanley Milgram (1969). An Experimental Study of the Small World Problem, Sociometry, 32(4): 425-443, Dec., 1969. • Power-law degree distributions / the scale – free property ❑ Social network’s nodes (also edges) are distributed under the power-law degree • Network transitivity ❑ Structure and dynamics of the network influenced by nodes with the large number of connectings (using to detect communities in a social network!) • Community structure ❑ Networks are divided into communities in which the nodes in the same community closed links, and links communities liquid ❑ A community in social networks as an “interest group” in the real world. as meaning of “nhĩm lợi ích” in Vietnamese. See also “Advocacy group”, “Lobby group”. 5P&5C marketing model: People  Customer approach (Product  Consumer desire; Price  Cost; Place  Convenience; Promotion  Communication) 15 ❑ Flexible community structure: one community structure for one case.
16. Social Networks: Properties Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 1(2): 173-180, 2006. 16
17. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 17 1(2): 173-180, 2006.
18. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 1(2): 173-180, 2006. 18
19. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 19 1(2): 173-180, 2006.
20. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 20 1(2): 173-180, 2006.
21. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 21 1(2): 173-180, 2006.
22. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 22 1(2): 173-180, 2006.
23. E-mail Networks Lan N. Bui, Anh Q. Tran, Thuy Q. Ha (2006). User authentic Rating based on Email Networks, ICMOCCA2006: 144-148, Seoul, Korea & International Journal of Natural Sciences and Technology, 23 1(2): 173-180, 2006.
24. Mạng XH và cộng đồng [For10] - Câu lạc bộ karate của Zachary (được quan sát trong 3 năm), một kiểm chứng chuẩn cho phát hiện cộng đồng. Các màu sắc tương ứng với phân hoạch tốt nhất tìm được bằng cách tối ưu các mơ đun của Newman và Girvan. - Đồ thị gồm 34 đỉnh thành viên của câu lạc bộ. Cạnh nối các cá nhân cĩ tương tác bên ngồi các hoạt động của câu lạc bộ. Theo quan sát, cĩ xung đột giữa chủ tịch câu lạc bộ và người hướng dẫn dẫn đến sự phân hoạch câu lạc bộ thành hai nhĩm riêng biệt, tương ứng ủng hộ người hướng dẫn và chủ tịch (chỉ dẫn hình vuơng và hình trịn). Câu hỏi đặt ra là liệu từ cấu trúc mạng ban đầu cĩ thể suy luận các thành phần của hai nhĩm. - Nhìn vào hình, cĩ thể phân biệt hai tập hợp, một tập quanh các đỉnh 33 và 34 (34 là chủ tịch), tập cịn lại quanh đỉnh 1 (người hướng dẫn). - Cũng cĩ một số đỉnh nằm giữa hai cấu trúc chính, chẳng hạn như 3, 9, 10; đỉnh như vậy thường khơng phân loại được theo phương thức phát hiện cộng đồng. [For10] Santo Fortunato (2010), Community detection in graphs, Technical Report, Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Torino, ITALY. 24
25. Mạng XH và cộng đồng [For10] - Mạng hợp tác giữa mạng các nhà khoa học làm việc tại học viện Santa Fe (SFI). Các màu chỉ dẫn cộng đồng ở mức độ cao thu được theo thuật tốn của Girvan và Newman (mục VA) và tương ứng khá chặt chẽ với các đơn vị nghiên cứu của học viện. Phân chia nhỏ hơn tương ứng với các nhĩm nghiên cứu nhỏ hơn, xoay quanh các lãnh đạo dự án. - Đồ thị hiện cĩ 118 đỉnh (các nhà khoa học đại diện cho cư dân tại SFI và cộng tác viên của họ). Các cạnh nối các nhà khoa học đã cùng cơng bố ít nhất một bài báo. Trực quan cho phép phân biệt được các nhĩm chuyên ngành. Trong mạng này, khi quan sát nhiều nhĩm, là tác giả của một bài báo thì tất cả cùng liên kết với nhau. Cĩ chỉ một số ít các kết nối giữa hầu hết các nhĩm. [For10] Santo Fortunato (2010), Community detection in graphs, Technical Report, Complex 25 Networks and Systems Lagrange Laboratory, ISI Foundation, Torino, ITALY.
26. Mạng XH và cộng đồng [For10] - Mạng Lusseau các cá heo mũi to. Những màu nhãn cộng đồng được xác định qua tối ưu hĩa một phiên bản mơ đun của Newman và Girvan, theo đề xuất của Arenas và cộng sự. Phân hoạch phù hợp với các lớp sinh học của cá heo được Lusseau đề xuất. - Hiện cĩ 62 cá heo, các cạnh nối các cá heo được nhìn thấy thường xuyên hơn so với dự kiến. Tập cá heo bị tách thành hai nhĩm sau khi cá heo một trái nơi dành cho một số thời gian (hình vuơng và hình trịn trong Hình vẽ). Các nhĩm như vậy là khá cố kết, với một vài cụm (clique) nội bộ, và dễ dàng định danh: chỉ cĩ sáu cạnh nối các đỉnh của nhĩm khác nhau. - Do mạng này phân lớp tự nhiên cá heo Lusseau, cũng như câu lạc bộ karate của Zachary, thường được dùng để kiểm tra thực nghiệm thuật tốn phát hiện cộng đồng [For10] Santo Fortunato (2010), Community detection in graphs, Technical Report, Complex26 Networks and Systems Lagrange Laboratory, ISI Foundation, Torino, ITALY.
27. Mạng XH và cộng đồng: tương tác protein - protein [For10] [For10] Santo Fortunato (2010), Community detection in graphs, Technical Report, Complex27 Networks and Systems Lagrange Laboratory, ISI Foundation, Torino, ITALY.
28. Học máy xác suất Bayes ⚫ Một số kiến thức cơ sở về lý thuyết xác suất ➢ Khơng gian đo được ➢ Khơng gian xác suất ➢ Sigma – trường ➢ Hệ thống động ➢ Quá trình ngẫu nhiên thời gian rời rạc ➢ Kỳ vọng ➢ Entropy ➢ Trong tài liệu ⚫ Nhắc thêm về học máy xác suất ➢ 28
29. Học máy xác suất Bayes ⚫ Mơ hình tần số ➢ Tiến hành thử nghiệm lặp đi lặp lại ➢ Tỷ số xuất hiện trên tồn bộ số lần thử ⚫ Mơ hình xác suất ➢ Xác suất cĩ điều kiện: sự kiện e với tri thức nền  là P(e|) ➢ Tri thức nền là sự xuất hiện của tài liệu (trái) hoặc sự xuất hiện của tài liệu mới. ➢ Xác suất tiên nghiệm và xác suất hậu nghiệm. P(D e)P(e) P(D2 e, D)P(e D) P(e D) = P(e D, D2 ) = P(D) P(D2 D) 29
30. Ước lượng giá trị tham số ⚫ Hai bài tốn ➢ Lựa chon mơ hình hay dạng hàm: Dựa trên tri thức miền đã cĩ ➢ Mỗi mơ hình/hàm cĩ bộ tham số tương ứng ➢ Cần xác định bộ tham số này ⚫ Xác định tham số ➢ Thường theo ước lượng ➢ Ước lượng tham số mơ hình ➢ Ước lượng tham số cho trường hợp cụ thể 30
31. Thuật tốn Viterbi ⚫ Thuật tốn Viterbi ➢ Mơ hình máy trạng thái hữu hạn ❖ xác định tham số mơ hình phù hợp tập ví dụ học ➢ Lý thuyết quyết định hỗn hợp ➢ Bài tốn giải mã ❖ Đã cĩ mơ hình máy trạng thái hữu hạn ❖ Tìm dãy trạng thái phù hợp nhất với trường hợp cụ thể ➢ Nội dung thuật tốn ❖ Xem trong giáo trình 31
32. C4. Một số bài tốn xử lý tiếng Việt ⚫ Lĩnh vực xử lý ngơn ngữ tự nhiên ➢ Xử lý ngơn ngữ tự nhiên (tự động hĩa) ➢ Ra đời khoảng nhứng năm 1950 ➢ Ngày càng phát triển ⚫ Phân loại ➢ Xử lý ❖ Cơ bản ❖ Ứng dụng ➢ Tài nguyên ➢ Cơ bản ➢ Mức cao 32
33. Bài tốn tách câu ⚫ Đây là bài tốn khá đơn giản ⚫ Khái niệm ➢ Chuỗi ký tự kết thúc bằng dấu chấm, chấm hỏi, chấm than ➢ Vẫn cĩ trường hợp ngoại lệ (khoảng 10%) ❖ Các dấu trên khơng kết thúc câu (trong nháy kép) ❖ Một số dấu khác kết thúc câu ⚫ Một số trường hợp ➢ Dựa theo kinh nghiệm ➢ Mơ hình ME (Le Hong Phuong & Ho Tuong Vinh) ➢ Xem giáo trình 33
34. Bài tốn tách từ ⚫ Đây là bài tốn rất cơ bản, luơn thời sự ⚫ Từ vẫn phát triển bổ sung, thay đổi ⚫ Ngăn cách hiển, nhập nhằng, mờ ⚫ “Ơng già đi nhanh quá” | “Học sinh học sinh học” ⚫ Khái niệm ➢ Cho một câu hãy xác định các từ trong câu ➢ “Phù hợp ngữ cảnh” ⚫ Một số phương pháp ➢ Khớp tơi đa ➢ Máy trạng thái hữu hạn cĩ trọng số (WSFT) ❖ Trường ngẫu nhiên cĩ điều kiện ➢ Xem giáo trình 34
35. Phát hiện quan hệ ngữ nghĩa ⚫ Là bài tốn cơ bản ⚫ Quan hệ ngữ nghĩa giữa các đối tượng ngữ pháp ⚫ Một số quan hệ ngữ nghĩa: theo cách tiếp cận ⚫ Khái niệm ➢ Cho một tập các văn bản ➢ Tìm ra các đối tượng ngữ pháp và các quan hệ giữa chúng ⚫ Một số phương pháp ➢ DIPRE ➢ SNOWBALL ➢ Xem giáo trình 35
36. Phương pháp Snowball Eugene Agichtein, Luis Gravano (2000). Snowball: extracting relations from large plain-text collections, ACM DL 2000: 85-94 36
37. Phát hiện quan hệ ngữ nghĩa Các mức: Hình vị, Cú pháp, Ngữ nghĩa, Diễn ngơn, Phát ngơn (?), Tri thức Roxana Girju (2008). Semantic Relations:Discovery and Applications 37
38. Quan hệ ngữ nghĩa: Ngơn ngữ học Roxana Girju (2008). Semantic Relations:Discovery and Applications 38
39. Quan hệ ngữ nghĩa: XLNNTN Roxana Girju (2008). Semantic Relations:Discovery and Applications 39
40. Quan hệ ngữ nghĩa: XLNNTN Roxana Girju (2008). Semantic Relations:Discovery and Applications 40
41. Phát hiện quan hệ ngữ nghĩa Vu Tran, Vinh Nguyen, Uyen Pham, Oanh Tran and Quang Thuy Ha (2009). An Experimental Study of Vietnamese Question Answering System, International Conference on Asian Language Processing (IALP 2009): 152-155, Dec 7-9, 2009, Singapore, 41
42. Một số cơng cụ nguồn mở ⚫ Chuyển từ trang Web sang văn bản ➢ Bộ phân tích HTML ( Tác giả: Jose Solorzano ➢ Một số cơng cụ tinh chế cho tiếng Việt (html2text.php, text2telex.php Tác giả: Nguyễn Việt Cường ⚫ Một số bộ cơng cụ xử lý ➢ Nhĩm KPLD phát triển (PXHiếu, NCTú, NTTrang) ❖ Bộ cơng cụ xử lý Text trên Java: JtextPro ( và JwebPro ❖ Phần mềm phân đoạn từ tiếng Việt: JvnSegmenter ( ➢ Sản phầm tài nguyên và cơng cụ của Đề tài “Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lý tiếng nĩi và văn bản tiếng Việt“ mã số KC.01.01/06-10 do PGS, TS. Lương Chi Mai chủ trì. ❖ ➢ Một số tiện ích liên quan: và 42
43. Project target products SP8.1 Speech analysis tools SP6.1 SP6.2 SP6.3 Corpora for Corpora for Corpora for speech recognition speech synthesis specific words SP1 Apllicationoriented SP3 systems based on English-Vietnamese SP7.4 Vietnamese speech SP7.3 translation system E-V corpora of aligned recognition & synthesis Vietnamese tree bank sentences SP7.2 Viet dictionary SP8.2 SP8.3 Vietnamese word Vietnamese POS tagger Segmentation SP8.5 SP8.4 Vietnamese syntax Vietnamese chunker analyser Chủ trì đề tài KC.01.01/06-10: Prof. Luong Chi Mai (IOIT), Prof. Ho Tu Bao (JAIST, IOIT)