ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA -------------------------- PHẠM MINH LUÂN RÚT TRÍCH GIÁ TRỊ THUỘC TÍNH CHO WIKIPEDIA INFOBOX Chuyên ngành: Khoa Học Máy Tính Mã số: 60.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 12 năm 2014 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG - HCM Cán bộ hướng dẫn khoa học: GS. Cao Hoàng Trụ.
(Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1: TS. Hồ Bảo Quốc. (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2: TS. Nguyễn Thanh Hiên.
(Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM, ngày 05 tháng 01 năm 2015 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ) 1. Nguyễn Hứa Phùng (CT). Quản Thành Thơ (TK).
Hồ Bảo Quốc (PB1). Nguyễn Thanh Hiên (PB2). Võ Thị Ngọc Châu (UV). Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA………. ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập -Tự do -Hạnh phúc ___________________ ___________________ NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: PHẠM MINH LUÂN MSHV: 12070522 Ngày, tháng, năm sinh: 31/08/1988 Nơi sinh: TP. HỒ CHÍ MINH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 604801 I. TÊN ĐỀ TÀI: RÚT TRÍCH GIÁ TRỊ THUỘC TÍNH CHO WIKIPEDIA INFOBOX II.
NHIỆM VỤ VÀ NỘI DUNG:. NGÀY GIAO NHIỆM VỤ: 20/08/2013. NGÀY HOÀN THÀNH NHIỆM VỤ: 10/10/2014. CÁN BỘ HƯỚNG DẪN: GS.
CAO HOÀNG TRỤ TP. HCM, ngày …… tháng …… năm 20… CÁN BỘ HƯỚNG DẪN TRƯỞNG KHOA …………… (Họ tên và chữ ký) (Họ tên và chữ ký) GS. CAO HOÀNG TRỤ LỜI CẢM ƠN Trước hết, tôi xin gửi lời cảm ơn chân thành và sâu sắc đến thầy hướng dẫn của tôi, GS. Cao Hoàng Trụ.
Trong suốt quá trình làm luận văn này, thầy đã tận tình, kiên nhẫn chỉ dẫn tôi từng bước và thường xuyên khích lệ tôi. Sự hướng dẫn và lời khuyên quý báu từ thầy là một nhân tố và động lực không thể thiếu để tôi có thể hoàn thành được luận văn này. Tôi xin gửi lời cảm ơn đến gia đình và bạn bè tôi, những người luôn ủng hộ, động viên và tạo điều kiện tốt nhất cho việc học tập và nghiên cứu của tôi. Xin chân thành biết ơn sự tận tình giảng dạy và giúp đỡ của tất cả quý thầy cô tại trường Đại học Bách khoa, đặc biệt là các thầy cô trong khoa Khoa học và Kỹ thuật Máy tính trong suốt quá trình được đào tạo tại trường.
TÓM TẮT Infobox là một cấu trúc thông tin phổ biến trong các bài viết của Wikipedia. Đây là nơi tập trung các thông tin cô đọng, các tính chất đặc trưng nhất của chủ thể được đề cập đến trong bài viết. Tuy nhiên thực tế cho thấy lượng thông tin trong infobox thường không đầy đủ, vẫn còn thông tin khác trong bài viết chưa được khai thác hết. iPopular và WAVE là hai phương pháp tiêu biểu cho việc làm giàu infobox bằng cách tìm thông tin còn thiếu ngay trong nội dung bài viết trên Wikipedia.
Trọng tâm của luận án là tập trung tìm hiểu, hiện thực và đưa ra những đánh giá về hai phương pháp iPopular và WAVE. Bên cạnh kết quả so sánh chéo giữa các phương pháp này, chúng tôi cũng đề xuất việc kết hợp ưu điểm của các phương pháp nhằm tối ưu việc trích xuất giá trị thuộc tính từ văn bản bài viết. Kết quả đạt được từ việc kết hợp tương đối khả quan, có những cải tiến nhất định so với các phương pháp trước đây. ABSTRACT An infobox is a fixed-format table designed to be added to Wikipedia articles to consistently present a summary of some unifying aspect that the articles share.
Often, an infobox does not contain as much information as possible because of different reasons. iPopular [11] and WAVE [14] are two typical systems that automatically enriches infoboxes of Wikipedia articles by extracting informations from the article’s text. The goal of this thesis is to compare and analyze the advantages and disadvantages of iPopular and WAVE. Atfer that, we find the way to enhance the two baseline systems by combining various techniques of them.The results of our experiments show that our combination method achieves some improvement in performance than the baseline methods.
LỜI CAM ĐOAN Tôi xin cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các nội dung trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy bằng cấp ở một trường khác. Phạm Minh Luân MỤC LỤC 1. Bài toán và phạm vi. Infobox và Wikipedia.
Gom cụm dữ liệu với thuật toán k-means. Phân loại thuộc tính đơn thành phần và đa thành phần. Phân tách cấu trúc giá trị của thuộc tính trên infobox. Thuật toán entropy cực đại.
Các hướng tiếp cận. Phương pháp iPopular. Phương pháp WAVE. Tập thực nghiệm.
Phương pháp đánh giá. So sánh iPopular và WAVE. Phương pháp kết hợp. Hướng phát triển.
46 DANH MỤC HÌNH Hình 1-1: Khai thác tri thức từ nội dung văn bản của bài viết trên Wikipedia. 2 Hình 1-2: Ví dụ minh họa về việc bổ sung giá trị thuộc tính mới từ bài viết. Trích từ [11]. 3 Hình 2-1: Một ví dụ về bài viết có infobox về Elvis Presley.
6 Hình 2-2: Infobox template Musical Artist. 7 Hình 2-3: Phương pháp gọm cụm dữ liệu. Trích từ [17]. 7 Hình 2-4: Một ví dụ trong việc phân tích cấu trúc của thuộc tính number_of_employees từ infobox_company.
Trích từ [11]. 10 Hình 2-5: Giải thuật phân tích cấu trúc. Trích từ [11]. 11 Hình 3-1: Mô hình khai phá tri thức từ DBpedia.
19 Hình 3-2: Quy trình hoạt động của iPopular. Trích từ [11]. 23 Hình 3-3: Hàm so sánh độ tương đồng của giá trị thuộc tính trong infobox và trong nội dung bài viết. Trích từ [11].
24 Hình 3-4: Đặc trưng CRF áp dụng trên mỗi cụm trong văn bản.Danh sách các tính chất của các từ trong cửa sổ gồm 5 từ trước và sau từ đang được phân tích. Trích từ [11]. 25 Hình 3-5: Sơ đồ hoạt động của WAVE. Trích từ [14].
27 Hình 3-6: Các định dạng văn bản được chuyển hoá trong tiền xử lý văn bản của WAVE. Trích từ [14]. 28 Hình 4-1: Tập thực nghiệm phương pháp iPopular sử dụng. 33 Hình 4-2: Tập thực nghiệm phương pháp WAVE sử dụng.
33 Hình 4-3: Minh họa quá trình đánh giá dựa trên phương pháp k-fold cross- validation. Nguồn từ internet. 34 Hình 4-4: Sơ đồ các bước trong phương pháp đề xuất. 40 DANH MỤC BẢNG Bảng 4-1: Kết quả thực nghiệm của iPopular và Wave trên tập thực nghiệm WAVE.
36 Bảng 4-2: Kết quả thực nghiệm của iPopular và WAVE trên tập thực nghiệm iPopular. 37 Bảng 4-3: Kết quả phương pháp kết hợp so với kết quả từ hai phương pháp iPopular và WAVE trên tập thực nghiệm WAVE. 42 Bảng 4-4: Kết quả phương pháp kết hợp so với kết quả từ hai phương pháp iPopular và WAVE trên tập thực nghiệm iPopular. 43 Bảng 4-5: Kết quả thực nghiệm của Wave, iPopular và phương pháp kết hợp trên tập thực nghiệm iPopular chỉ xét thuộc tính có cấu trúc đa thành phần.
Giới thiệu Ngày nay, Internet đóng một vai trò quan trọng trong việc lưu trữ và truyền tải thông tin của nhân loại. Bên cạnh đó, với công nghệ thông tin ngày càng phát triển, con người dễ dàng hơn bao giờ hết trong việc tiếp nhận và truyền tải các nội dung mong muốn cho cộng đồng dưới dạng số. Việc này dẫn đến sự bùng nổ thông tin trên internet. Tuy nhiên, ngoài những lợi ích mà internet đem lại, con người lại dễ dàng bị nhầm lẫn và lạc lối trong quá trình tìm kiếm những thông tin cần thiết giữa nguồn tri thức khổng lồ như vậy.
Vì các trang web phần lớn đều thuộc dạng phi hoặc bán cấu trúc, chiếm hầu như 80% khối lượng lưu trữ trên internet, chúng chủ yếu xuất hiện dưới dạng thông tin văn bản hoặc hình ảnh để cho người xem có thể dễ dàng đọc và hiểu được. Trước nhu cầu khai thác tri thức ngày càng cần phải nhanh chóng và chính xác, các công cụ trợ giúp có thể tự động đọc hiểu và rút trích các thông tin quan trọng từ các tài liệu trên web là không thể thiếu. Điều này thúc đẩy nhiều kỹ thuật và ứng dụng ra đời trong đó các phương pháp xử lý ngôn ngữ tự nhiên (Nature Language Processing) giúp cho máy tính phần nào hiểu được ngôn ngữ con người. Trong phạm vi luận án, việc khai thác tri thức từ nguồn thông tin khổng lồ trên trang Wikipedia được chúng tôi chọn trọng tâm chính (xem thêm về Wikipedia và infobox ở phần 2.
Vì Wikipedia là một trong những hệ thống thông tin mở với nguồn dữ liệu phong phú, đang còn rất nhiều nguồn tri thức có giá trị chưa được khai thác hết từ đó. Hướng tiếp cận của luận án là tìm hiểu những 1 phương pháp và kỹ thuật để có thể rút trích thông tin cần thiết từ bài viết trên Wikipedia với rất nhiều các thông tin hỗn độn được trình bày trong văn bản đó. Để minh họa cho tiềm năng khai thác các nguổn tri thức từ những nguồn thông tin trên Wikipedia, lấy một ví dụ cụ thể về giá trị thông tin từ bài viết trên Wikipedia mà ta có thể tìm thấy được; trong bài viết về Albert Einstein1 trên Wikipedia, ta có thể tìm thấy một câu trong đó “His father was Hermann Einstein, a sales…”, dựa vào câu này có thể cho ta một thông tin quan trọng là cha của Albert Einstein là Hermann Einstein (theo như Hình 1-1). Ví dụ trên là một trong rất nhiều những dạng tri thức tiềm năng mà các kỹ thuật liên quan đến việc xử lý ngôn ngữ tự nhiên có thể giải quyết.
Hình 1-1: Khai thác tri thức từ nội dung văn bản của bài viết trên Wikipedia. Bài toán và phạm vi Từ những nghiên cứu liên quan đến việc khai thác rút trích thông tin có giá trị từ văn bản. Mục tiêu chính của đề tài tập trung vào việc nâng cao giá trị cho nguồn thông tin infobox, là một dạng dữ liệu có tính cấu trúc cao và đóng vai trò rất quan trọng trên Wikipedia (xem giới thiệu về Wikipedia và infobox ở phần 2. Dựa vào quá trình tìm hiểu các đề tài liên quan, nội dung của luận văn này 1 http://en.org/wiki/Albert_Einstein 2 xoay quanh việc bổ sung giá trị cho thuộc tính còn trống cho infobox.
