Luận án Tiến sĩ Công nghệ thông tin: Nghiên cứu cải tiến phân lớp đa nhãn văn bản và ứng dụng tóm tắt

Chia sẻ: Yi Yi | Ngày: | Loại File: PDF | Số trang:152

Thêm vào BST

Báo xấu

37
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án cung cấp một khảo sát khái quát về phân lớp đa nhãn, đề xuất các phương pháp biểu diễn dữ liệu và lựa chọn đặc trưng phù hợp nhằm nâng cao hiệu quả của giải pháp phân lớp đa nhãn văn bản tiếng Việt. Nghiên cứu, đề xuất các thuật toán phân lớp đa nhãn dựa trên các thuật toán phân lớp hiện đại.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Công nghệ thông tin: Nghiên cứu cải tiến phân lớp đa nhãn văn bản và ứng dụng tóm tắt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ NGÂN NGHIÊN CỨU CẢI TIẾN PHÂN LỚP ĐA NHÃN VĂN BẢN VÀ ỨNG DỤNG LUẬN ÁN TIẾN SĨ CÔNG NGHÊ THÔNG TIN Hà Nội – 2017
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ NGÂN NGHIÊN CỨU CẢI TIẾN PHÂN LỚP ĐA NHÃN VĂN BẢN VÀ ỨNG DỤNG Chuyên ngành: Hệ thống thông tin Mã số: 62.48.01.04 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS HÀ QUANG THỤY 2. PGS.TS PHAN XUÂN HIẾU Hà Nội – 2017
LỜI CAM ĐOAN Tôi xin cam đoan luận án này là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong các công trình nào khác. Nghiên cứu sinh Phạm Thị Ngân i
LỜI CẢM ƠN Luận án được thực hiện tại Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin – Trường Đại học Công nghệ - Đại học quốc gia Hà Nội dưới sự hướng dẫn khoa học của PGS.TS. Hà Quang Thụy và PGS.TS. Phan Xuân Hiếu. Trước tiên tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Hà Quang Thụy và thầy Phan Xuân Hiếu, những người đã đưa tôi tiếp cận và đạt được những thành công trong lĩnh vực nghiên cứu của mình. Tôi đặc biệt gửi lời cảm ơn tới thầy Hà Quang Thụy đã luôn tận tâm, động viên, khuyến khích và chỉ dẫn tôi hoàn thành được bản luận án này. Tôi xin bày tỏ lòng biết ơn tới thầy Nguyễn Trí Thành đã nhiệt tình hướng dẫn và truyền đạt các kinh nghiệm nghiên cứu trong quá trình tôi thực hiện luận án. Tôi xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học thuộc Trường Đại học Công nghệ (đặc biệt là các thành viên của Phòng thí nghiệm khoa học dữ liệu và công nghệ tri thức – DS&KTlab) - Đại học Quốc gia Hà Nội đã giúp đỡ về chuyên môn và tạo điều kiện thuận lợi cho tôi trong suốt thời gian học tập và nghiên cứu. Tôi xin bày tỏ lòng cảm ơn chân thành tới các cộng sự đã cùng tôi thực hiện các công trình nghiên cứu và các bạn đồng nghiệp đã giúp đỡ, trao đổi và chia sẻ những kinh nghiệm về chuyên môn, đóng góp các ý kiến quý báu cho tôi trong quá trình nghiên cứu. Tôi xin trân trọng cảm ơn các thầy cô trong hội đồng chuyên môn đã đóng góp các ý kiến quý báu để tôi hoàn thiện luận án. Tôi cũng bày tỏ lòng lòng cảm ơn sâu sắc tới Ban giám đốc Học viện Cảnh sát nhân dân; Tập thể lãnh đạo Bộ môn Toán-Tin học, Học viện Cảnh sát nhân dân đã tạo kiện thuận lợi cho tôi trong quá trình nghiên cứu; cảm ơn các đồng chí trong Bộ môn Toán-Tin học đã luôn ủng hộ, quan tâm và động viên tôi. Tôi luôn biết ơn những người thân trong gia đình, bố mẹ nội, bố mẹ ngoại, các anh chị em đã luôn chia sẻ khó khăn, động viên và là chỗ dựa tinh thần vững chắc cho tôi trong suốt thời gian qua. ii
MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ii MỤC LỤC ................................................................................................................ iii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ...........................................vii DANH MỤC CÁC BẢNG ....................................................................................... ix DANH MỤC CÁC HÌNH VẼ................................................................................... x MỞ ĐẦU .................................................................................................................... 1 Chương 1. TỪ PHÂN LỚP ĐƠN NHÃN TỚI PHÂN LỚP ĐA NHÃN ...... 10 1.1. Từ phân lớp đơn nhãn đơn thể hiện tới phân lớp đa nhãn đa thể hiện .... 10 1.1.1. Phân lớp đơn nhãn ................................................................................. 10 1.1.2. Phân lớp đơn nhãn đa thể hiện .............................................................. 11 1.1.3. Phân lớp đa nhãn ................................................................................... 12 1.1.4. Phân lớp đa nhãn đa thể hiện ................................................................. 13 1.2. Giới thiệu chung về phân lớp đa nhãn ......................................................... 14 1.2.1. Kỹ thuật phân lớp đa nhãn ..................................................................... 15 1.2.1.1. Tiếp cận chuyển đổi bài toán .......................................................16 1.2.1.2. Tiếp cận thích nghi thuật toán......................................................22 1.2.1.3. Tóm tắt về các thuật toán được giới thiệu ...................................28 1.2.2. Dữ liệu đa nhãn ..................................................................................... 29 1.2.2.1. Các độ đo dữ liệu đa nhãn............................................................29 1.2.2.2. Phân bố nhãn ................................................................................30 1.2.2.3. Mối quan hệ giữa các nhãn ..........................................................30 1.2.3. Đánh giá phân lớp đa nhãn .................................................................... 31 1.2.3.1. Các độ đo dựa trên mẫu ...............................................................32 1.2.3.2. Các độ đo dựa trên nhãn ..............................................................34 1.3. Giảm chiều dữ liệu trong phân lớp đa nhãn ................................................ 36 iii
1.3.1. Tiếp cận giảm chiều không gian đặc trưng đầu vào .............................. 37 1.3.2. Tiếp cận giảm chiều không gian nhãn đầu ra ........................................ 41 1.4. Học bán giám sát cho phân lớp đa nhãn ...................................................... 43 1.5. Kết luận chương 1 .......................................................................................... 43 Chương 2. HAI MÔ HÌNH PHÂN LỚP ĐƠN NHÃN VĂN BẢN TIẾNG VIỆT ........................................................................................................... 45 2.1. Mô hình nhận diện thực thể có tên dựa trên trường ngẫu nhiên có điều kiện và tiêu chuẩn kỳ vọng tổng quát ........................................................... 45 2.1.1. Nhận diện thực thể có tên ...................................................................... 45 2.1.2. Mô hình đề xuất ..................................................................................... 46 2.1.2.1. Sử dụng tiêu chuẩn kỳ vọng tổng quát vào mô hình trường nhẫu nhiên có điều kiện CRFs ..............................................................................48 2.1.2.2. Xây dựng tập ràng buộc cho tiêu chuẩn kỳ vọng tổng quát ........51 2.1.2.3. Mô hình đề xuất cho bài toán nhận diện thực thể có tên .............52 2.1.3. Ứng dụng mô hình ................................................................................. 56 2.2. Một mô hình phân lớp đơn nhãn trong hệ tư vấn xã hội ........................... 59 2.2.1. Sơ bộ về tư vấn xã hội ........................................................................... 59 2.2.2. Mô hình đề xuất ..................................................................................... 62 2.2.3. Ứng dụng mô hình ................................................................................. 66 2.3. Kết luận chương ............................................................................................. 68 Chương 3. PHÂN LỚP ĐA NHÃN VĂN BẢN DỰA TRÊN BIỂU DIỄN DỮ LIỆU THEO CHỦ ĐỀ ẨN .................................................................................... 70 3.1. Phân lớp đa nhãn văn bản dựa trên biểu diễn dữ liệu theo chủ đề ẩn ...... 70 3.1.1. Biểu diễn dữ liệu theo chủ đề ẩn ........................................................... 70 3.1.2. Mô hình phân lớp đa nhãn văn bản dựa trên biểu diễn dữ liệu theo chủ đề ẩn ................................................................................................ 75 3.1.2.1. Pha 1 – Huấn luyện mô hình ........................................................77 3.1.2.2. Pha 2 – Đánh giá mô hình huấn luyện .........................................82 iv
3.1.3. Ứng dụng phân lớp đa nhãn đánh giá khách sạn ................................... 83 3.1.3.1. Xây dựng tập dữ liệu thực nghiệm ..............................................84 3.1.3.2. Thực nghiệm ................................................................................85 3.1.3.3. Kết quả thực nghiệm ....................................................................86 3.2. Phân lớp đa nhãn văn bản dựa trên biểu diễn dữ liệu theo đồ thị khoảng cách các chủ đề ẩn .......................................................................................... 87 3.2.1. Mô hình biểu diễn văn bản theo đồ thị khoảng cách ............................. 89 3.2.1.1. Biểu diễn dữ liệu theo đồ thị khoảng cách...................................89 3.2.1.2. Mô hình đồ thị khoảng cách và mô hình n-gram .........................92 3.2.2. Mô hình phân lớp đa nhãn văn bản dựa trên biểu diễn dữ liệu theo đồ thị khoảng cách chủ đề ẩn ..................................................................... 93 3.2.2.1. Pha huấn luyện mô hình...............................................................95 3.2.2.2. Pha phân lớp sử dụng mô hình huấn luyện ..................................97 3.2.3. Ứng dụng phân lớp đa nhãn đánh giá khách sạn ................................... 98 3.3. Kết luận chương 3 ........................................................................................ 100 Chương 4. KỸ THUẬT BÁN GIÁM SÁT PHÂN LỚP ĐA NHÃN VĂN BẢN TIẾNG VIỆT ................................................................................................ 102 4.1. Tiếp cận phân cụm bán giám sát ................................................................ 102 4.1.1. Tiếp cận dựa trên ràng buộc ................................................................ 102 4.1.2. Tiếp cận dựa trên khoảng cách ............................................................ 103 4.2. Mô hình phân lớp đa nhãn bán giám sát ................................................... 105 4.2.1. Phát biểu bài toán phân lớp đa nhãn bán giám sát .............................. 105 4.2.2. Thuật toán phân lớp đa nhãn dựa trên kỹ thuật phân cụm bán giám sát106 4.2.2.1. Thuật toán TESC và LIFT .........................................................107 4.2.2.2. Thuật toán phân lớp đa nhãn bán giám sát ................................109 4.2.3. Mô hình phân lớp đa nhãn bán giám sát đề xuất ................................. 116 4.3. Một mô hình ứng dụng phân lớp đa nhãn văn bản bán giám sát ............ 117 4.3.1. Mô hình đề xuất ................................................................................... 117 v
4.3.1.1. Pha 1. Huấn luyện mô hình ........................................................118 4.3.1.2. Pha 2. Phân lớp sử dụng mô hình huấn luyện ...........................120 4.3.2. Ứng dụng phân lớp đa nhãn sử dụng mô hình đề xuất ........................ 120 4.4. Kết luận chương 4 ........................................................................................ 123 KẾT LUẬN ............................................................................................................ 124 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN TỚI LUẬN ÁN ............................................................................................................... 128 TÀI LIỆU THAM KHẢO .................................................................................... 129 vi
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu Tiếng Anh Tiếng Việt ANN Artificial neural network Mạng Nơ-ron nhân tạo Backpropagation for Multilabel Phân lớp đa nhãn mạng Nơron BPMLL Learning lan truyền ngược BR Binary Relevance Phân lớp nhị phân CC Classifier Chains Chuỗi bộ phân lớp Phương pháp tích hợp phụ CDE ChiDep Ensemble thuộc Chi CLR Calibrated Label Ranking Xếp hạng nhãn xác định CML Collective Multi-Label Classifier Bộ phân lớp đa nhãn nhóm CRFs Conditional Random Fields Trường ngẫu nhiên có điều kiện CTM Corelated Topic Model Mô hình chủ đề tương quan DTM Dynamic Topic Model Mô hình chủ đề động ECC Ensemble of Classifier Chains Tích hợp chuỗi bộ phân lớp Ensemble of Probabilistic Tích hợp chuỗi bộ phân lớp xác EPCC Classiﬁer Chains suất EPS Ensemble of Pruned Sets Tích hợp các tập cắt tỉa FE Feature Extraction Trích chọn đặc trưng FS Feature Selection Lựa chọn đặc trưng Instance-Based Learning by Học dựa trên thực thể bằng hồi IBLR Logistic Regresion quy logic IG Information Gain Độ lợi thông tin kNN k Nearest Neighbour k láng giềng gần nhất LC Label Combination Kết hợp nhãn LP Label Powerset Tập lũy thừa nhãn LDA Latent Dirichlet Allocation Mô hình chủ đề ẩn Multi-Label Learning with Label Học đa nhãn với đặc trưng nhãn LIFT specIfic FeaTures riêng biệt LP Label Power set Tập lũy thừa nhãn LSA Latent Semantic Analysis Phân tích ngữ nghĩa ẩn MI Mutual Information Thông tin tương hỗ MIML Multi-Instance Multi-Label Đa nhãn đa thể hiện MLC Multi-Label Classiffication Phân lớp đa nhãn ML-DT Multi-Label Decision Tree Cây quyết định đa nhãn ML-kNN Multi-Label k Nearest Neighbour k Láng giềng gần nhất đa nhãn MLL Multi-Label Learning Học đa nhãn MLNB Multilabel Naive Bayes Naïve Bayes đa nhãn Multiclass Multilabel Associative MMAC Phân lớp kết hợp đa nhãn đa lớp Classiﬁcation Multilabel Multiclass Thuật toán Perceptron phân lớp MMP Perceptron đa lớp đa nhãn vii
Thuật toán tối ưu đàn kiến đa MuLAM Multilabel Ant - Miner nhãn NER Named Entity Recognition Nhận dạng thực thể có tên PCA Principal Component Analysis Phân tích thành phần chính PCC Probabilistic Classiﬁer Chains Chuỗi bộ phân lớp xác suất Thuật toán cây phân cụm dự PCT Predictive Clustering Trees đoán PMM1 Parametric Mixture Models Mô hình hòa trộn tham số PMM2 POS Part Of Speech Từ loại PS Pruned Sets Các tập bị cắt tỉa PW Pairwise Methods Phương pháp cặp đôi Ranking by Pairwise Phương pháp xếp hạng theo so RPC Comparision sánh cặp đôi Ranking via Single-label Xếp hạng thông qua học đơn RSL Learning nhãn SVM Support Vector Machine Máy vectơ hỗ trợ TExt classification using Semi- Phân lớp văn bản sử dụng phân TESC supervised Clustering cụm bán giám sát Term Frequency Inverse Trọng số về tần suất và độ quan TFIDF Document Frequency trọng của từ viii
DANH MỤC CÁC BẢNG Bảng 1.1 Ví dụ về dữ liệu đa nhãn ............................................................................16 Bảng 1.2 Tóm tắt các thuật toán phân lớp đa nhãn ...................................................29 Bảng 1.3 Bảng ký hiệu dữ liệu phân lớp thực và dự đoán ........................................34 Bảng 2.1 Mẫu ngữ cảnh từ vựng ...............................................................................55 Bảng 2.2 Mẫu ngữ cảnh phát hiện tên thực thể.........................................................55 Bảng 2.3 Kết quả thực nghiệm ..................................................................................57 Bảng 2.4 Bảng đặc trưng tiểu sử và đặc trưng xã hội của người dùng .....................67 Bảng 2.5 Kết quả thực nghiệm ..................................................................................67 Bảng 3.1 Ví dụ về kết quả của mô hình chủ đề ẩn cho tài liệu .................................81 Bảng 3.2 Ví dụ về dữ liệu đa nhãn ............................................................................82 Bảng 3.3 Tập dữ liệu thực nghiệm ............................................................................84 Bảng 3.4 Tập dữ liệu huấn luyện ..............................................................................84 Bảng 3.5 Tập dữ liệu cho mô hình chủ đề ẩn............................................................85 Bảng 3.6 Kết quả phân lớp ........................................................................................86 Bảng 3.7 Bảng phân phối tập từ trên mỗi chủ đề ẩn .................................................96 Bảng 3.8 Kết quả thực nghiệm của mô hình phân lớp đa nhãn dựa trên mô hình chủ đề ẩn và đồ thị khoảng cách ....................................................................................100 Bảng 4.1 Kết quả thực nghiệm 1 và thực nghiệm 2 ................................................121 Bảng 4.2 Kết quả thực nghiệm 3, thực nghiệm 4 và thực nghiệm 5 .......................122 ix
DANH MỤC CÁC HÌNH VẼ Hình 0.1 Phân bố bài báo và lượng trích dẫn về học máy đa nhãn trong ISI (trái) và Scopus (phải) tới năm 2013 [22] .................................................................................3 Hình 0.2 Phân bố các chủ đề trong các chương của luận án .......................................7 Hình 1.1 Phân lớp đơn nhãn truyền thống [128].......................................................10 Hình 1.2 Học đơn nhãn đa thể hiện [128] .................................................................11 Hình 1.3 Học đa nhãn [128] ......................................................................................13 Hình 1.4 Học đa nhãn đa thể hiện [128] ...................................................................14 Hình 1.5 Hai tiếp cận học đa nhãn [21] ....................................................................15 Hình 1.6 Các bộ phân lớp nhị phân tương ứng với 4 nhãn .......................................17 Hình 1.7 Thuật toán phân lớp BR [89] .....................................................................18 Hình 1.8 Thuật toán phân lớp CC [64] .....................................................................20 Hình 1.9 Thuật toán phân lớp CLR [84] ...................................................................21 Hình 1.10 Thuật toán phân lớp RakEL [43], [84] .....................................................22 Hình 1.11 Thuật toán ML-kNN [84] .........................................................................23 Hình 1.12 Thuật toán phân lớp ML-DT [84] ............................................................25 Hình 1.13 Thuật toán phân lớp Rank-SVM [84] ......................................................26 Hình 1.14 Thuật toán phân lớp CML [84] ................................................................27 Hình 1.15 Các độ đo đánh giá của hệ thống đa nhãn [84] ........................................31 Hình 1.16 Mô hình lựa chọn đặc trưng cho phân lớp dữ liệu [47] ...........................36 Hình 2.1 Đồ thị vô hướng mô tả CRFs .....................................................................49 Hình 2.2 Mô hình gán nhãn bán giám sát CRFs kết hợp tiêu chuẩn kỳ vọng tổng quát ............................................................................................................................53 Hình 2.3 Tập các ràng buộc (Constraint file)............................................................54 Hình 2.4 Kết quả mô hình gán nhãn bán giám sát CRFs kết hợp tiêu chuẩn kỳ vọng tổng quát trên các tập ràng buộc khác nhau ..............................................................58 Hình 2.5 Mô hình hệ thống tư vấn xã hội .................................................................64 Hình 3.1 Phân phối các chủ đề trong bài báo, tập các từ và xác suất các từ trong chủ đề [16] .......................................................................................................................72 Hình 3.2 Mô hình sinh trong LDA [15] ....................................................................73 Hình 3.3 Thuật toán sinh trong mô hình LDA ..........................................................73 Hình 3.4 Mô hình chủ đề ẩn cho bài toán phân lớp đa nhãn ....................................78 Hình 3.5 Phân tích nhận xét của người dùng về khách sạn Romana ........................87 x
Hình 3.6 Biểu diễn văn bản theo không gian vectơ, v1 và v2 là hai văn bản trong không gian vectơ ba chiều T1, T2, T3 trong đó Ti là từ .............................................88 Hình 3.7 Minh họa biểu diễn đồ thị khoảng cách .....................................................90 Hình 3.8 Mô hình phân lớp đa nhãn dựa trên biểu diễn dữ liệu theo đồ thị khoảng cách các chủ đề ẩn. ....................................................................................................94 Hình 3.9 Biểu diễn đồ thị khoảng cách trên câu chủ đề............................................96 Hình 4.1 Mô hình phân lớp bán giám sát đề xuất ...................................................117 Hình 4.2 Mô hình ứng dụng phân lớp đa nhãn bán giám sát cho văn bản tiếng Việt .................................................................................................................................119 xi
MỞ ĐẦU Tính cấp thiết của luận án Cùng với sự bùng nổ dữ liệu cả về dung lượng lẫn về chủng loại, phân lớp dữ liệu tự động là rất cần thiết và là một trong những chủ đề chính trong khai phá dữ liệu. Trong mười thuật toán khai phá dữ liệu điển hình nhất có tới bảy thuật toán liên quan tới bài toán phân lớp là thuật toán C4.5 và cải biên, thuật toán máy vectơ hỗ trợ SVM (Support Vector Machine, còn được gọi là máy vectơ tựa), thuật toán EM (Expectation–Maximization), thuật toán Adaboost, thuật toán k-láng giềng gần nhất k-NN, thuật toán Bayes “ngây thơ” (Naïve Bayes), thuật toán CART (Classification and Regression Trees) [121]. Bản chất của bài toán phân lớp dữ liệu là xây dựng một hàm (hoặc ánh xạ) toàn phần từ tập dữ liệu (gồm các dữ liệu đã tồn tại hoặc sẽ xuất hiện) thuộc một miền ứng dụng tới một tập hữu hạn nhãn cho trước dựa trên thông tin đã biết về hàm này trên một tập con các dữ liệu đã được gán nhãn (được gọi là tập ví dụ mẫu). Hàm kết quả được gọi là mô hình (bộ) phân lớp (classification model/classifier) hay mô hình dự báo (prediction model) lớp. Do bài toán phân lớp đòi hỏi cho trước một tập ví dụ mẫu cho nên nó cũng được gọi là bài toán học có giám sát. Một thuật toán phân lớp điển hình thường trải qua hai bước thực hiện. Bước thứ nhất, được gọi là bước học mô hình (learning step), thực hiện việc phân tích dữ liệu thuộc một tập con ví dụ mẫu, được gọi là tập dữ liệu huấn luyện (training dataset), để xây dựng một mô hình phân lớp phù hợp với tập dữ liệu huấn luyện. Về bản chất, ở bước học, thuật toán phân lớp “học” một hàm có khả năng gán nhãn cho mọi dữ liệu miền ứng dụng. Hàm phân lớp kết quả từ bước học được sử dụng để dự báo nhãn cho các dữ liệu mới. Tuy nhiên, trước khi đem mô hình phân lớp vào ứng dụng thực tế, thuật toán phân lớp cần tiến hành bước đánh giá mô hình (model evaluation, hay kiểm thử mô hình (model testing)). Ở bước đánh giá mô hình, một tập con ví dụ mẫu, được gọi là tập dữ liệu kiểm thử (testing data), được sử dụng để đo độ chính xác của thuật toán. Mô hình phân lớp được áp dụng trên các ví dụ trong tập dữ liệu kiểm thử để nhận được các nhãn dự báo và các nhãn này được so sánh 1
với nhãn thực sự đã có tương ứng của ví dụ. Nếu tỷ lệ nhãn dự báo trùng hợp với nhãn thực sự càng cao thì mô hình phân lớp càng chính xác. Nhằm đảm bảo việc đánh giá mô hình phân lớp là khách quan, tập dữ liệu kiểm thử và tập dữ liệu huấn luyện là rời nhau (hai tập dữ liệu không chứa chung một ví dụ bất kỳ). Khi chất lượng của mô hình phân lớp được khẳng định thì nó được sử dụng để “gán” nhãn cho mọi dữ liệu chưa có nhãn (hiện có và sẽ có) thuộc miền ứng dụng. Tính ứng dụng cao của phân lớp làm cho bài toán phân lớp được tiến hóa từ đơn giản tới ngày càng phức tạp hơn theo hướng từ phân lớp đơn nhãn tới phân lớp đa nhãn hoặc phân lớp đa thể hiện, và cho tới phân lớp đa nhãn đa thể hiện [128]. Phân lớp đơn nhãn (còn được gọi là phân lớp truyền thống) quy ước mỗi đối tượng dữ liệu có duy nhất một nhãn (hàm phân lớp đơn trị). Phân lớp đa nhãn quy ước mỗi đối tượng dữ liệu có thể có hơn một nhãn (hàm phân lớp đa trị), chẳng hạn, một tài liệu về chuyển nhượng cầu thủ bóng đá có thể vừa thuộc lớp kinh tế vừa thuộc lớp thể thao. Phân lớp đa thể hiện quy ước một đối tượng dữ liệu có thể tương ứng với nhiều thể hiện và mỗi đối tượng này tương ứng với một nhãn. Một ví dụ điển hình về đối tượng đơn nhãn đa thể hiện là coi mỗi đối tượng là một chùm chìa khóa chứa nhiều chìa khóa, mỗi khóa có thể mở được một phòng [124]. Giả sử có một phòng khóa cửa và có N chùm chìa khóa, nếu một chùm nào đó chứa chìa khóa mở được phòng này thì chùm đó được coi là hữu ích. Phân lớp đa nhãn - đa thể hiện quy ước một đối tượng dữ liệu tương ứng với nhiều thể hiện và các thể hiện này tương ứng với nhiều nhãn. Chương 1 của luận án sẽ đề cập chi tiết hơn về quá trình tiến hóa bài toán phân lớp. Luận án “Nghiên cứu cải tiến phân lớp đa nhãn văn bản và ứng dụng” tập trung vào bài toán phân lớp đa nhãn. Phân lớp đa nhãn (Multi-Label Classiffication: MLC) hay học đa nhãn (Multi-Label Learning: MLL) là một khung học máy (learning framwork) giám sát mới nổi trong thời gian gần đây [22], [40], [42], [84]. Khung học máy này đã thể hiện sự phù hợp với thực tế và tính ứng dụng rộng rãi trong các bài toán phân lớp, điển hình là trong phân lớp văn bản, phân tích dữ liệu đa phương tiện, sinh học, khai phá mạng xã hội, học điện tử và nhiều miền ứng 2
dụng khác [21], [40]. Tuy nhiên, học đa nhãn đòi hỏi những tiến hóa mới đối với các phương pháp học máy cho giải pháp thích hợp với dữ liệu đa nhãn như vấn đề về mối quan hệ giữa các nhãn, chi phí tính toán của thuật toán, vấn đề mất cân bằng nhãn, vấn đề đa chiều của dữ liệu... Đây là các vấn đề cần tiếp tục nghiên cứu, cải tiến và phát triển để nâng cao hiệu quả phân lớp đa nhãn. Hình 0.1 Phân bố bài báo và lượng trích dẫn về học máy đa nhãn trong ISI (trái) và Scopus (phải) tới năm 2013 [22] Chính vì lý do đó, học đa nhãn cuốn hút một cộng đồng nhiên cứu rộng rãi trên thế giới. Bằng các truy vấn phù hợp vào cơ sở dữ liệu ISI và Scopus [22], E. Gibaja và S. Ventura nhận được thông tin về số lượng hàng năm các công bố khoa học về học đa nhãn và trích dẫn tới các công bố đó trong các cơ sở dữ liệu ISI và Scopus. Kết quả số liệu thống kê của các tác giả được chỉ dẫn tại Hình 0.1. Các biểu đồ trong Hình 0.1 chứng tỏ rằng học đa nhãn là chủ đề nhận được sự quan tâm ngày càng tăng trong cộng đồng nghiên cứu. Tính tới năm 2013, theo các tác giả thì hội nghị ECML/PKDD 2009 và hai hội nghị MLD 2009 và MLD 2010 chứa một lượng đáng kể các công trình nghiên cứu về học đa nhãn. Các nhóm nghiên cứu của Zhi-Hua Zhou, Min-Ling Zhang và cộng sự1, Ioannis P. Vlahavas, Grigorios Tsoumakas và cộng sự2, Sebastián Ventura Soto3 và cộng sự với nhiều đóng góp nổi bật về học đa nhãn. 1 http://cs.nju.edu.cn/zhouzh/ và http://cse.seu.edu.cn/PersonalPage/zhangml/ 2 http://plase.csd.auth.gr/vlahavas/ và http://intelligence.csd.auth.gr/people/tsoumakas 3 http://www.uco.es/users/sventura/en/ 3
Học đa nhãn là chủ đề nghiên cứu của một số luận án Tiến sỹ trên thế giới, chẳng hạn như [51], [67], [92], [111], [113]. Luận án của J. Read [67] đề xuất giải pháp phân lớp đa nhãn trên quy mô lớn với hai mô hình phân lớp dựa trên phương pháp tập cắt tỉa và chuỗi bộ phân lớp; hai tiếp cận này nhận được đánh giá tốt từ cộng đồng nghiên cứu nhờ tính hiệu quả trên cả phương diện về sự đa dạng và quy mô của dữ liệu. Tác giả H.Q.Le [51] đề xuất một kỹ thuật lựa chọn đặc trưng đa lớp và một thuật toán phân lớp đa nhãn trên miền dữ liệu web có cấu trúc nhóm. Thuật toán phân lớp đa nhãn đa cặp (Multi-Pair) chuyển đổi bài toán phân lớp đa nhãn về nhiều bài toán phân lớp nhị phân (OVA One-Vs-All), sau đó, tiếp tục phân tách mỗi bộ phân lớp nhị phân thành các cặp so sánh nhỏ hơn và đơn giản hơn giữa một nhóm và một tập con của phần bù của nhóm. Phân tách như vậy giúp tận dụng được cấu trúc nhóm trong phần bù và giảm sự mất cân bằng dữ liệu trong phương pháp OVA. Trong một tiếp cận khác, S.S.Bucak [113] đề xuất một phương pháp biểu diễn ảnh dựa trên học đa nhân và thuật toán học đa nhãn dựa trên tiếp cận xếp hạng đa nhãn, trong đó thuật toán xếp hạng đa nhãn sẽ xếp hạng tất cả lớp ảnh sao cho các lớp liên quan sẽ có hạng cao hơn các lớp ít liên quan. Luận án của S.Jungjit [111] đề xuất một mô hình phân lớp đa nhãn kết hợp hai bộ phân lớp đa nhãn kinh điển là phân lớp đa nhãn k láng giềng gần nhất (MLkNN) và phân lớp đa nhãn mạng Nơron lan truyền ngược (BPMLL) với giải pháp lựa chọn đặc trưng thông qua tìm kiếm các tập con đặc trưng phù hợp. Theo M. L. Zhang và Z. H. Zhou [84], các công trình nghiên cứu sớm nhất về học đa nhãn là tập trung vào miền ứng dụng phân lớp văn bản [6], [106]. Theo thời gian, học đa nhãn được ứng dụng vào nhiều miền ứng dụng đa dạng (đặc biệt là miền ứng dụng phân lớp dữ liệu ảnh) và nhiều phương pháp học đa nhãn đã được đề xuất [1], [7], [23], [25], [42], [44], [63], [66], [73], [74], [76], [114], [117], [118], [127]. Các phương pháp ban đầu thường đi theo cách tiếp cận là cố gắng chia bài toán học đa nhãn thành nhiều bài toán phân lớp hai nhãn hoặc chuyển nó thành phương pháp học máy xếp hạng nhãn trong phân lớp đa nhãn [23], [42], [73], [74], những tiếp cận gần đây chú trọng hơn đến việc khai thác mối quan hệ giữa các nhãn [7], [76], [117], [118], tiếp 4
cận khai thác mối quan hệ đa nhãn và dự đoán chuỗi tuần tự [65]. Trong học đa nhãn, các giải pháp biểu diễn dữ liệu và lựa chọn đặc trưng dữ liệu tốt cho phép nâng cao tính hiệu quả của các giải pháp học đa nhãn [24], [82], [83], [87], [93], [94], [127] và nhiều giải pháp đã được đề xuất. M.L. Zhang và cộng sự sử dụng chiến thuật lựa chọn đặc trưng dựa trên phân tích thành phần chính PCA và các thuật toán di truyền để loại bỏ các đặc trưng dư thừa, không liên quan và chọn ra tập đặc trưng phù hợp nhất cho bài toán phân lớp [82] hoặc khai thác các đặc trưng cụ thể cho từng nhãn để sử dụng cho quá trình huấn luyện và kiểm thử [83], [87]. A.Elisseeff và J.Weston sử dụng các đặc trưng nhãn được sắp xếp để khai thác mối quan hệ giữa các nhãn trong bài toán phân lớp đa nhãn [1]. O.G.R. Pupo và cộng sự đánh trọng số đặc trưng dựa trên bộ lọc nhằm cải tiến các thuật toán lười (lazy algorithm) phân lớp đa nhãn [93] hoặc cải tiến thuật toán ReliefF đánh trọng số và lựa chọn đặc trưng cho phân lớp đa nhãn bao gồm việc sử dụng phương pháp chuyển đổi bài toán đa nhãn về bài toán phân lớp đơn nhãn và thích nghi thuật toán ReliefF trực tiếp giải quyết bài toán phân lớp đa nhãn [94]. Phân tích các đặc trưng dữ liệu cho phân lớp đa nhãn cũng là một trong các hướng nghiên cứu được quan tâm gần đây [44]. Tại Việt Nam, qua khảo sát các công trình khoa học được công bố, phân lớp đơn nhãn đã nhận được sự quan tâm rộng rãi của cộng đồng nghiên cứu4. Trong khi đó, phân lớp đa nhãn, đặc biệt là phân lớp đa nhãn văn bản tiếng Việt, còn khá ít5 và đa phần do các nhóm nghiên cứu tại Đại học Công nghệ, Đại học Quốc gia Hà Nội tiến hành và hiện chưa có luận án tiến sỹ nào về phân lớp đa nhãn. Các tiếp cận về phân lớp đa nhãn trước đây chủ yếu tập trung vào giải thuật theo phương pháp học giám sát, các mô hình phân lớp đa nhãn bán giám sát vẫn còn hiếm. Luận án này tiếp nối các nghiên cứu về phân lớp đa nhãn, tiếp tục phân tích, đánh giá và đề xuất cải tiến mô hình phân lớp về phương pháp biểu diễn dữ liệu, lựa 4 Google Scholar trả về tài liệu đối với truy vấn “classification” + “Vietnamese” ngày 26/9/2017 5 Google Scholar trả về 29 tài liệu đối với truy vấn ““multi-label classification” + “Vietnamese”” ngày 20/12/2016. 5
chọn đặc trưng và đề xuất mới thuật toán phân lớp đa nhãn theo phương pháp bán giám sát nhằm tận dụng nguồn tài nguyên dữ liệu chưa gán nhãn phong phú. Phân lớp văn bản có tính ứng dụng do sự xuất hiện rộng rãi của văn bản trong mọi lĩnh vực của đời sống, ở sách báo, thông điệp, diễn đàn,… Do đó, luận án tập trung vào bài toán phân lớp đa nhãn văn bản tiếng Việt. Nghiên cứu của luận án hướng tới một số mục tiêu sau đây. Thứ nhất, luận án cung cấp một khảo sát khái quát về phân lớp đa nhãn. Thứ hai, luận án đề xuất các phương pháp biểu diễn dữ liệu và lựa chọn đặc trưng phù hợp nhằm nâng cao hiệu quả của giải pháp phân lớp đa nhãn văn bản tiếng Việt. Nghiên cứu, đề xuất các thuật toán phân lớp đa nhãn dựa trên các thuật toán phân lớp hiện đại là mục tiêu thứ ba của luận án. Cuối cùng, luận án xây dựng một số phần mềm thử nghiệm thực thi các giải pháp biểu diễn dữ liệu và thuật toán phân lớp đa nhãn được luận án đề xuất để kiểm chứng tính hiệu quả của các đề xuất đó. Đối tượng nghiên cứu của luận án là phương pháp biểu diễn dữ liệu, lựa chọn đặc trưng và thuật toán phân lớp đa nhãn trong miền dữ liệu văn bản tiếng Việt. Phạm vi nghiên cứu của luận án được giới hạn ở phương pháp biểu diễn dữ liệu, lựa chọn đặc trưng và thuật toán phân lớp đa nhãn văn bản tiếng Việt, tập trung vào miền ứng dụng phân tích nhận xét đánh giá tiếng Việt. Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết đề xuất mô hình biểu diễn dữ liệu và thuật toán phân lớp đa nhãn cũng như nghiên cứu thực nghiệm để kiểm chứng đánh giá các đề xuất của luận án. Luận án tham gia vào dòng nghiên cứu về phân lớp đa nhãn trên thế giới và đạt được một số đóng góp được ghi nhận, tập trung vào các nghiên cứu về phân lớp đa nhãn văn bản tiếng Việt. Thứ nhất, luận án đề xuất hai mô hình biểu diễn dữ liệu cho phân lớp đa nhãn là mô hình biểu diễn dữ liệu chủ đề ẩn [PTNgan3] và mô hình biểu diễn dữ liệu theo đồ thị khoảng cách các chủ đề [PTNgan4]. Thứ hai, trên cơ sở phát triển thuật toán phân cụm bán giám sát đơn nhãn TESC [120], luận án đề xuất một thuật toán phân lớp đa nhãn bán giám sát (Thuật 6
toán MULTICS [PTNgan5], [PTNgan6]) sử dụng chiến thuật “tham lam” khai thác các đặc trưng riêng biệt của các nhãn. Thứ ba, luận án tham gia đóng góp vào dòng nghiên cứu về học phân lớp đơn nhãn văn bản tiếng Việt tương ứng với hai ứng dụng thực tiễn là đề xuất mô hình gán nhãn thực thể có tên [PTNgan1] và mô hình hệ tư vấn xã hội [PTNgan2]. Đồng thời, nhằm minh chứng cho tiềm năng ứng dụng thực tiễn của các mô hình đề xuất, luận án thực thi các thực nghiệm để kiểm chứng tính hữu dụng của các thuật toán và mô hình được luận án đề xuất. Kết quả thực nghiệm cho thấy tiềm năng ứng dụng cao các kết quả nghiên cứu từ luận án. Luận án cũng có đóng góp trong việc cung cấp một nghiên cứu tổng quan về học máy đa nhãn. Bố cục của luận án gồm phần mở đầu và bốn chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Hình 0.2 cung cấp một khung nhìn sơ bộ về phân bố các chủ đề trong bốn chương nội dung của luận án. Hình 0.2 Phân bố các chủ đề trong các chương của luận án Chương 1 của luận án cung cấp một nghiên cứu khái quát từ phân lớp đơn nhãn tới phân lớp đa nhãn. Phân lớp đơn nhãn tuy đơn giản, hiệu quả nhưng không phù hợp với không ít tình huống trong thực tế; khung học máy đa nhãn (đơn thể 7