DAI HOC QUOC GIA TP. HO CHi MINH TRUONG DAI HOC BACH KHOA TONG VAN HAI XÂY DỰNG MÔ HÌNH XÁC ĐỊNH CHỦ ĐÈ CHO CÂU TRUY VẤN CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SÓ CHUYÊN NGÀNH: 60.01 LUẬN VĂN THẠC SĨ TP. Hồ Chí Minh, tháng 6 năm 2012 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRUONG ĐẠI HỌC BÁCH KHOA -ĐHQG -HCM Cán bộ hướng dẫn khoa học: PGS.TS Phan Thị Tươi Cán bộ chấm nhận xét 1: TS Nguyễn Chánh Thành Cán bộ chấm nhận xét 2: TS Huỳnh Tường Nguyên Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHÁM BẢO VỆ LUẬN VĂN THẠC SĨ TRUONG DAI HOC BACH KHOA, ngay 18 thang 7 nim 2012 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1.TS Cao Hoàng Trụ (CT) 2. TS Nguyễn Chánh Thành (PBI) 3.
TS Huỳnh Tường Nguyên (PB2) 4.TS Phan Thị Tươi (UV) 5. TS Nguyễn Hứa Phùng (TK) Xác nhận của Chủ tịch Hội đồng đánh giá luận văn và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã sửa chữa. CHỦ TỊCH HỘI ĐÒNG TRƯỞNG/PHÓ KHOA (Họ tên và chữ ký) (Họ tên và chữ ký) PGS.TS Cao Hoàng Trụ TRUONG DH BACH KHOA TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHONG DAO TAO SDH Độc lập - Tự do - Hạnh phúc Tp.
HCM, ngày tháng năm 2012 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Tống Văn Hải Phái: Nam Ngày, tháng, năm sinh: 15/09/1986 Noi sinh: Ninh Binh Chuyén nganh: Khoa hoc may tinh MSHV: 10070477 1. TEN DE TAT: XÂY DỰNG MÔ HÌNH XÁC ĐỊNH CHỦ ĐỀ CHO CÂU TRUY VÁN. NHIỆM VỤ LUẬN VĂN: — _ Tìm hiểu các phương pháp phân lớp dữ liệu. o_ Xây dựng bộ phân lớp chủ đề cho câu truy van.
— Tim hiéu cach x4y dung ontology. o Xay dung ontology chủ dé với mục đích xác định cụm danh từ đặc trưng thuộc lớp chủ đề xác định. NGÀY GIAO NHIỆM VỤ: 4. NGÀY HOÀN THÀNH NHIỆM VỤ: 5.
HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: PGS.TS Phan Thị Tươi CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) (Họ tên và chữ ký) PGS.TS Phan Thị Tươi LỜI CÁM ƠN Đầu tiên, tôi muốn gửi lời cảm ơn sâu sắc nhất đến PGS.TS Phan Thị Tươi. Cô đã tận tình hướng dẫn và chỉ bảo tôi trong suốt quá trình hoàn thành luận văn. Tôi xin cảm ơn TS Nguyễn Chánh Thành đã cung cấp cho tôi những tài liệu tham khảo có liên quan đến đề tài luận văn này. Tôi cũng xin chân thành cảm ơn đến tất cả các thầy cô trong Khoa Khoa Học & Kỹ Thuật Máy Tính, Trường Đại Học Bách Khoa TP.
Hồ Chí Minh đã truyền đạt những kiến thức quý báu trong quãng thời gian tôi học tập tại đây. TOM TAT Cùng với sự phát triển mạnh mẽ của World Wide Web, nguồn thông tin chia sẻ trên Internet ngày càng trở nên phong phú và đa dạng hơn. Đối với các hệ thống tìm kiếm thông tin theo từ khóa ngày nay thường trả về gồm cả những tài liệu có nội dung không liên quan đến thông tin cần tìm kiếm. Chính vì điều này, luận văn đã đi nghiên cứu và xây dựng một mô hình xác định chủ đề cho câu truy vấn.
Ở đây, chủ đề của câu truy vấn được hiểu là câu truy vấn đang nói đến thuộc lĩnh vực nảo. Tuy nhiên, luận văn sẽ không chỉ dừng lại ở bước xác định chủ đề. Vì nếu dừng lại ở bước này và coi toàn bộ câu truy vấn như là một từ khóa để tìm kiếm tài liệu trên cơ sở dữ liệu cục bộ thì hiệu quả không cao bởi vì câu truy vấn là một chuỗi các ký tự thường có độ dài lớn. Vì vậy, bước tiếp theo chúng ta cần phải xác định xem những cụm từ đặc trưng nào xuất hiện trong câu truy vấn và sử dụng những cụm từ đặc trưng này như là từ khóa (thay vì toàn bộ cá câu truy vấn) để tìm kiếm tài liệu trên cơ sở dữ liệu cục bộ sẽ đem lại hiệu quả cao hơn.
1H ABSTRACT Along with the strong development of Word Wide Web, flows of information shared on the Internet are getting more and more in its variety. Today’s Information Retrieval Systems by key words give out lots of results including unexpected and unrelated ones. Therefore, this research studies and builds a model defining topics for queries. In this research, topic for a query is understood as the query is about what kind of topic or field.
However, defining the topics is just a partial step but the destination of the research. If the research stops at this step and the whole query is considered key words to retrieve information based on local data, it might not work with high effectiveness as a query is a chain of letters of length. Thus, the next step we need to define which distinct phrases should be included in the query and be used as key words (instead of as the whole query) to retrieve local database; then the effectiveness of searching information would be high. 1H MỤC LỤC LỜI CẢM ƠN "y1 ~.,ÔỎ ii ca mẽ.2 Đề tài nghiên cứu .-- << s©s° se ©+sEE4 32A4 E39Ex3EEAEEAEAEE4 13 751912413737scxe 1 1.3 Các nghiên cứu liên quan.1 Những vấn đề nghiên cứu trong nước.2 Các nghiên cứu ngoài TưỚCC .-- << 5= 24 s91 S54 498588 4880848508808 056 4 CHƯƠNG 2 CƠ SỞ LÝ THUYÉT PHÂN LỚP VĂN BẢN.1 Mô hình biểu diễn văn bán.--- --cs-se©se+vsEEse+xeerterkeerserrserrserrserssrre 5 2.1 Mô hình không gian veetor.
Một số phương pháp tính trọng số của một từ khóa.2 Một số phương pháp phân lớp,.---- se 2< s©s£ se £s£xseEseEse+xeexzerserserssee 7 2.1 Phân lớp Naive Biay€S .---- <5 sọ HH ch cọ Hư g0 8 2.2 Phân lớp dựa trên cây quyết định.-- -<- << se ss+sessexserserssrssesseree 10 2.3 Phan lớp dựa vào mạng TN€urFaÌ.4 Phương pháp Support Vector Machines .--c «5< 5c ss se se sssssesseesee 17 pc: 8Š .1 Định nghĩa Onnf0ÌOY.2 Cac thanh phan cita Ontology .----2-s°se+cse+vseEvserxeereerrserrserrserrsrrsserssrr 38 3.3 Ngôn ngữ biểu diễn Ontology .4 Phương thức xây dựng Onf0ÌOgV.5 Ontology va bai toán xác định cụm từ đặc frưng. ---- 5-5 << =esc<s=eseseese 43 CHƯƠNG 4 XÂY DỰNG MÔ HÌNH VÀ HIỆN THỰC.1 Xây dựng mô hình xác định chủ đề cho câu truy vấn.2 Hiện thực bộ phân lớp chủ đề.--s-s° se < s£Es£+se©ssSxsersexserseeeersserserl 48 4.1 Tạo mô hình bằng giải thuật SÌMO.----s-scss+vsseresrxesrrsrrssrrsee 48 IV 4.2 Xây dựng tập ngữ liệu huấn luyện. Mã hóa tập ngữ liệu theo định dạng LIBSVM .4 Lựa chọn đặc frưTiE .-- 5 5 5 5 HH HH TH TH Ti 0 00 53 4.6 Gắn nhãn từ ÏOạÌ .7 Công thức để đánh giá hiệu quả của bộ phân lớp chủ đề.3 Xây dựng onfology chủ đỀ.---- << se s<+ssSEs£xseEseEseExsExsersersersereersserser 55 4.1 XAy dung ontology chit dé may tinh .2 Xây dựng bộ từ điển từ vựng.--s-s-s<©s<cserse se vae+eeesserserseresrssesseree 58 4.3 Xác định cụm danh từ đặc trưng ngữ nghĩa dựa trên Onfology.4 Công thức đánh giá độ hiệu quả của Ontology chú đề máy tính .4 Xây dựng mô đun xác định cụm danh từ dự tuyễn .5 Xây dựng mô đun mã hóa định dạng LIBSVM.6 Xây dựng cơ sở dữ liệu cục bộ cho chú đề máy tính.7 Xây dựng mô đun tìm kiếm tài liệu .8 Phân rã cụm danh từ đặc (FWTIg. Ví dụ về toàn bộ quá trình hoạt động của hệ thống.---s- 52s ssseel 67 CHƯƠNG 5 ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN.1 Đánh giá hiệu quả của bộ phân lớp chú đề .2 Đánh giá hiệu quả xây dựng Ontology chú đề.-------sscssessscsssrssersee 74 kh cC) hố .,ÔỎ 76 NI an.
78 DANH MỤC HÌNH Hình 2.1 Mô hình vector 2 chiỄu.2 Vi du vé cliy quyét Ginl.3 EnfFoDy CA tập) €.- Ăn n1 KH HH 0000001080081 008 0050006 12 Hình 2.4 Mô HÌHH HỘI DCFCGJDẨTOHH.5 Mô Hình HẠHg ÏÝ€IHFAÏ,.6 Mô hình lan truyỀH ng .-oe-cecce<cc<ceSEseEeEEkeEeeExeEreereetkerkeersereerseressrsrre 16 Hình 2. 7 Siéu phẳng ƒphân chia dữ liệu thành 2 lớp + và — với khoảng cách biên lớn nhất. các điêm gân ƒ nhất là Các 'ŠHDĐOF( W€CfOF.8 Siêu phẳng ƒ phân chia tập dữ liệu thành 2 lóp + và —.---cee-ceecexeeces 21 Hình 2.9 Siêu phẳng phân chia tập dữ liệu có nhiễu thành 2 lớp + và —.10 Ảnh xạ từ không gian R“ sang không gian Ñ”(m > đ) .11 Rằng buộc giữa hai nhân LABFAHB€.co< ceccece<ceereereeteetseersereerseresersrre 27 Hình 2.12 Giới hạn của giá trị Œ; trường Hợp Ý\ # Ý¿ .13 Giới hạn của giá trị Œ; (FƯỜng HỢP Ý\ — Ý; ‹-c-.eceece<ceecĂSSee san ga nga nga ngan 28 Hình 2.14 Giá ngưỡng b khi cá hai nhân Lagrange cùng nằm trên đường biên.1 Thể hiện mối quan hệ cha con trong QHf0ÏOBV.2 Mô tả lép trong Ontology (bao gồm cá thực thổ).3 Mỗi quan hệ giữa các thực thể.4 Các thực thỂ trong Qnf0ÏOBV .5 Hệ phân cấp các đối tượng trong thế giới fÏUC.1 Cấu trúc mô hình xác định chú đề cho câu tFM VẤN .2 Dữ liệu được định dạng theo LLI BS WMỸ .- << 5< se «se =sEssessesse 51 Hình 4.3 Ontology chú đỀ máy tÍnh.-eecce©cescceecxeertesrkeersesreertsertsrrksrksrserrssrrerree 5T Hình 4.4 Mỗi quan hệ giữa các lóp đối tượng máy tính trong Qnfology.5 Các mỗi quan hệ được sứ dụng để suy luận trong trường hợp l.6 Các mỗi quan hệ được sứ dụng để suy luận trong trường hợp 2.7 Các mỗi quan hệ được sứ dụng để suy luận trong trường hợp 3.8 Các mỗi quan hệ được sứ dụng để suy luận trong trường hợp 4. 62 VI DANH MỤC BẢNG Bang 4.1 Tập nhãn từ loại của bộ gán HÌHẫH VH ÏS€F'.- «5< 5 =Ă se se se se essesse 54 Bang 5.1 30 câu truy vẫn được sứ dụng để thứ ngÌhiỆHH.2 Két quả thử nghiệm với hàm nhân tuyén tÍnhh .---e--ecccse©csecesecessrssex 73 Bang 5.3 Kết quả thử nghiệm với hàm nhân RBF.4 Két quả thử nghiệm với hàm nhân đa thức.5 Két quả thử nghiệm với hàm nhân sigimoid .6 Két quả thử nghiệm độ chính xác của onf0Ì08V.--eecceecceccseresereseressrsser 75 CHUONG 1 TONG QUAN 1.1 Phat biéu van dé Cùng với sự phát triển mạnh mẽ của World Wide Web, nguồn thông tin chia sẻ trên Internet ngày càng trở nên phong phú và đa dang hon.
Tuy nhiên, một thách thức đặt ra đối với con người là làm thế nào đề có thể sử dụng nguồn thông tin này một cách hiệu quả nhất. Khi tìm kiếm tài liệu, yêu cầu thông tin nhập từ phía người sử dụng hầu hết được biểu diễn dưới dạng các từ khóa. Cách biểu diễn này rõ ràng không có khả năng thể hiện trọn vẹn nội dung của thông tin. Do đó, khi truy hồi thông tin trên các hệ thống ngày nay, người sử dung đều nhận thêm những tài liệu có nội dung không liên quan đến thông tin mà mình mong muốn vì tìm kiếm dựa trên từ khóa thường không đạt được độ chính xác cao.
Nhằm tăng hiệu suất cũng như độ chính xác của các mô hình truy hồi thông tin theo từ khóa, nhiều công trình nghiên cứu đã khai thác tiềm năng ngữ nghĩa của cụm từ đặc trưng.
