Luận án: Tiếp cận Đồ thị Biểu diễn, Khai thác Văn bản và Ứng dụng - Nguyễn Hoàng Tú Anh

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN  NGUYỄN HOÀNG TÚ ANH TIẾP CẬN ĐỒ THỊ BIỂU DIỄN, KHAI THÁC VĂN BẢN VÀ ỨNG DỤNG Chuyên ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán Mã số chuyên ngành: 1.10 Phản biện 1: GS. Nguyễn Thanh Thủy Phản biện 2: PGS. Đinh Điền Phản biện 3: TS. Nguyễn Đức Cường Phản biện độc lập 1: PGS.

Nguyễn Xuân Huy Phản biện độc lập 2: TS. Quản Thành Thơ Phản biện độc lập 3: PGS. Nguyễn Kim Anh NGƯỜI HƯỚNG DẪN KHOA HỌC GS. HOÀNG VĂN KIẾM Tp.

Hồ Chí Minh – Năm 2011 Mục lục  Mở đầu. 1 Mục tiêu và đóng góp của luận án. 2 Nội dung luận án. 5 Chương 1 Tổng quan về khai thác dữ liệu văn bản .2 Các bài toán chính của khai thác văn bản .2 Mô hình biểu diễn văn bản .3 Bài toán phân loại văn bản.1 Phương pháp k-láng giềng gần nhất (k-NN) .2 Phương pháp Naïve Bayes .3 Phương pháp SVM .4 Bài toán gom cụm văn bản .1 Phương pháp k-Means.2 Phương pháp HAC .5 Bài toán tóm tắt văn bản .1 Phương pháp Heuristic .2 Các phương pháp khác.

26 Chương 2 Mô hình biểu diễn văn bản bằng đồ thị .2 Mô hình đồ thị khái niệm.3 Mô hình đồ thị hình sao .4 Mô hình đồ thị tần số vô hướng.5 Mô hình đồ thị đơn giản.6 Mô hình đồ thị khoảng cách n đơn giản .7 Mô hình đồ thị đỉnh là câu .8 Mô hình đồ thị lưỡng phần .9 Phân loại các mô hình đồ thị [CT4]. 40 i Chương 3 Phân loại văn bản dựa trên tiếp cận đồ thị .2 Các công trình nghiên cứu liên quan .1 Khai thác đồ thị con phổ biến .2 Phân loại văn bản dựa trên tiếp cận đồ thị .3 Phân loại văn bản tiếng Việt .3 Qui trình phân loại văn bản dựa trên kỹ thuật khai thác đồ thị .1 Tiền xử lý văn bản .2 Mô hình hóa văn bản thành đồ thị .3 Rút trích đặc trưng đồ thị .4 Xây dựng vectơ đại diện lớp .5 Bộ phân loại .4 Kết quả thử nghiệm .1 Thử nghiệm trên tập dữ liệu email tiếng Anh.1 Thử nghiệm trên tập dữ liệu tiếng Việt. 71 Chương 4 Gom cụm tập văn bản có biến động dựa trên biểu diễn đồ thị .2 Các công trình nghiên cứu liên quan .1 Gom cụm văn bản động .2 Gom cụm văn bản dựa trên tiếp cận đồ thị .3 Gom cụm văn bản tiếng Việt .3 Gom cụm tập văn bản có biến động dựa trên biểu diễn đồ thị .1 Tiền xử lý văn bản .2 Mô hình hóa văn bản thành đồ thị .3 Rút trích đặc trưng đồ thị .4 Xác định độ tương tự giữa các văn bản .5 Kỹ thuật chọn lựa động đặc trưng .6 Thuật toán gom cụm động Incremental DBSCAN cải tiến .4 Kết quả thử nghiệm. 103 Chương 5 Tóm tắt văn bản dựa trên biểu diễn đồ thị .2 Các công trình nghiên cứu liên quan .1 Tóm tắt văn bản dựa trên tiếp cận đồ thị .2 Tóm tắt văn bản tiếng Việt .3 Mô hình tóm tắt văn bản tiếng Việt dựa trên biểu diễn đồ thị và kỹ thuật xếp hạng .1 Tiền xử lý văn bản .2 Mô hình hóa văn bản thành đồ thị .3 Xếp hạng câu .4 Tạo bản tóm tắt .4 Kết quả thử nghiệm .1 Kết quả tóm tắt văn bản đơn .1 Kết quả tóm tắt tập văn bản.

128 Các kết quả đạt được. 128 Hướng phát triển. 130 Danh mục công trình của tác giả. 131 Tài liệu tham khảo.

133 Phụ lục A Các độ đo đánh giá .1 Đánh giá phương pháp phân loại .2 Đánh giá chất lượng gom cụm.3 Đánh giá bản tóm tắt. 147 Phụ lục B Ví dụ biểu diễn văn bản bằng đồ thị. 149 Phụ lục C Kiểm định giả thiết thống kê. Kiểm định giả thiết về số trung bình của tổng thể.

Kiểm định giả thiết về tỷ lệ của tổng thể. Kiểm định giả thiết về sự khác biệt giữa hai trung bình của tổng thể. Kiểm định giả thiết về sự bằng nhau giữa hai tỷ lệ của tổng thể. 156 Phụ lục D Ví dụ kết quả tóm tắt văn bản .1 Ví dụ tóm tắt văn bản đơn .2 Ví dụ tóm tắt tập văn bản.

162 iii Danh mục các thuật ngữ, ký hiệu, chữ viết tắt  Average link : liên kết trung bình Bag of words model : mô hình túi từ Clustering : gom cụm Complete link : liên kết đầy đủ Cue : ngữ chỉ thị Cross-validation : đánh giá chéo Data mining : khai thác dữ liệu Dendrograms : sơ đồ nhánh Document : tài liệu Graph-based model : mô hình biểu diễn bằng đồ thị Heading : tiêu đề Hyperplane : siêu phẳng Information extraction : trích chọn thông tin Information retrieval : truy vấn thông tin Single link : liên kết đơn Title : nhan đề Text mining : khai thác dữ liệu văn bản (khai thác văn bản) CGs : mô hình đồ thị khái niệm - Conceptual Graphs CSDL : cơ sở dữ liệu DC-Tree : cây gom cụm tài liệu – Document Clustering Tree DF : tần suất xuất hiện của tài liệu – Document frequency DIG : đồ thị chỉ mục tài liệu - Document Index Graph DUC : Document Understanding Conference HAC : gom cụm phân cấp tích tụ - Hierachical Agglomerative Clustering ICG : gom cụm động dựa trên đồ thị - Incremental Clustering based on Graph iv IDF : nghịch đảo tần suất xuất hiện của tài liệu - Inverse Document Frequency IG : độ lợi thông tin – Information gain KDD : khám phá tri thức trong cơ sở dữ liệu - Knowledge discovery in databases k-NN : k - láng giềng gần nhất - k- Nearest Neighbor KTTL : kích thước của văn bản/email KTLop : kích thước thư mục /lớp MCS : đồ thị con chung cực đại - Maximal Common Subgraph MDL : độ dài mô tả cực tiểu - Minimum description length MMR : mức độ cực đại tương ứng - Maximal Marginal Relevance NB : Naïve Bayes ROUGE : Recall Oriented Understudy for Gisting Evaluation SOM : bản đồ tự tổ chức - Self Organizing Map SVM : máy vectơ hỗ trợ - Support Vector Machine STC : gom cụm dựa trên cây tiền tố - Suffix Tree Clustering TF : tần suất xuất hiện của thuật ngữ - Term Frequency VSM : mô hình không gian vectơ - Vector Space Model log : logarit cơ số 10 v Danh mục các hình  Hình 1. Ví dụ văn bản cho mô hình không gian vectơ. Siêu phẳng (đường nét liền) với lề cực đại. Các vectơ hỗ trợ – các điểm trên các đường đứt nét.

Thuật toán HAC. Sơ đồ nhánh đơn giản. Ví dụ mô hình đồ thị khái niệm. Ví dụ mô hình đồ thị hình sao biểu diễn văn bản [CT4].

Ví dụ mô hình đồ thị hình sao biểu diễn email [CT10]. Ví dụ mô hình đồ thị tần số vô hướng [89]. Ví dụ mô hình đồ thị đơn giản [CT4]. Ví dụ mô hình đồ thị khoảng cách n đơn giản [CT4].

Ví dụ mô hình đồ thị với đỉnh là câu. Minh họa mô hình đồ thị lưỡng phần với đỉnh là câu và từ. Sơ đồ giai đoạn huấn luyện. Sơ đồ giai đoạn phân loại.

Mã giả thuật toán gSpan nguyên thủy [100]. Ví dụ mã DFS cho đồ thị có hướng s. Ví dụ đồ thị con phổ biến của chủ đề Khoa học, Văn hóa. Kết quả phân loại email theo kích thước thư mục [CT10].

Kết quả phân loại theo thư mục của eClass và eMailSift [CT10]. Kết quả phân loại theo thư mục của eTCG và eClass. Độ chính xác phân loại theo người dùng [CT10]. So sánh kết quả phân loại dùng độ đo Dice và Manhattan [CT3].

So sánh kết quả phân loại theo chủ đề [CT3]. Qui trình gom cụm văn bản động [CT2]. Qui trình xây dựng đồ thị [CT7]. Thuật toán DIG [35].

Quá trình chọn lựa động đặc trưng [CT7]. Ví dụ trường hợp 4, trộn “bắc cầu” giữa các cụm A, B, C. Mã giả cho kỹ thuật trộn cụm của Incremental DBSCAN cải tiến. So sánh thời gian gom cụm giữa các mô hình biểu diễn văn bản.

Đánh giá chất lượng gom cụm giữa mô hình không gian vectơ truyền thống và mô hình đồ thị theo độ đo F (a) và Entropy (b)[CT2]. So sánh kết quả giữa các hệ thống gom cụm theo độ đo F. So sánh kết quả gom cụm theo độ đo F khi sử dụng và không sử dụng kỹ thuật chọn lựa động đặc trưng. Đánh giá thuật toán Incremental DBSCAN cải tiến theo độ đo F và Entropy [CT7].

Mô hình tóm tắt văn bản tiếng Việt [CT1]. Qui trình bộ tóm tắt văn bản đơn [CT8]. Đồ thị biểu diễn văn bản [CT8]. Thuật toán xếp hạng câu.

Kết quả đánh giá bản tóm tắt văn bản đơn theo ROUGE-1 [CT8]. Kết quả đánh giá bản tóm tắt văn bản đơn theo ROUGE-2. So sánh theo ROUGE-1 trên các chủ đề. So sánh theo ROUGE-2 trên các chủ đề.

Ví dụ biểu diễn văn bản bằng đồ thị. 152 vii Danh mục các bảng  Bảng 2. So sánh các mô hình biểu diễn văn bản bằng đồ thị [CT4]. Thống kê trên tập dữ liệu ENRON [CT10].

Mô tả các hệ thống thử nghiệm. Tập dữ liệu thử nghiệm TC1 cho bài toán phân loại văn bản [CT9]. Kết quả thử nghiệm phân loại [CT3]. So sánh kết quả phân loại theo giá trị F1 trung bình [CT6].

So sánh thời gian huấn luyện và phân loại văn bản. Thống kê trên tập dữ liệu TC2. Thống kê tập dữ liệu thử nghiệm [CT2]. So sánh chất lượng gom cụm theo độ đo F [CT5].

So sánh chất lượng gom cụm theo độ đo Entropy [CT5]. Sự cải thiện chất lượng gom cụm của ICG [CT2]. So sánh số lượng cụm thu được giữa ICG và SHC [CT2]. Kết quả cập nhật dữ liệu động [CT2].

Các từ khóa đặc trưng đại diện cho cụm [CT2]. Ma trận biểu diễn đồ thị văn bản [CT8]. Tập dữ liệu thử nghiệm T1 cho bài toán tóm tắt văn bản đơn [CT8]. Tập dữ liệu thử nghiệm T2 cho bài toán tóm tắt tập văn bản [CT1].

Kết quả đánh giá bản tóm tắt văn bản đơn [CT8]. So sánh các hệ thống tóm tắt trên tập T2 [CT1]. So sánh kết quả tóm tắt theo độ đo ROUGE trên từng chủ đề [CT1] .