Luận án Tiến sĩ Khoa học máy tính: Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử.pdf (Luận án tiến sĩ Khoa học máy tính)

ĐẠI HỌC HUẾ TRƢỜNG ĐẠI HỌC KHOA HỌC LÊ VĂN TƢỜNG LÂN PHÂN LỚP DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH MỜ DỰA TRÊN ĐẠI SỐ GIA TỬ CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.48.01.01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: 1. PGS.TS. Nguyễn Mậu Hân 2. TS. Nguyễn Công Hào HUẾ - NĂM 2018 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Mậu Hân và TS. Nguyễn Công Hào. Các số liệu và kết quả trình bày trong luận án là trung thực, chưa được công bố bởi bất kỳ tác giả nào hay ở bất kỳ công trình nào khác. ii Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử LỜI CẢM ƠN Trong quá trình thực hiện đề tài “Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử”, tôi đã nhận được rất nhiều sự giúp đỡ, tạo điều kiện của tập thể Ban giám hiệu, Phòng Đào tạo Sau đại học, Khoa Công nghệ thông tin và các phòng chức năng của Trường Đại học Khoa học, Đại học Huế. Tôi xin bày tỏ lòng cảm ơn chân thành về sự giúp đỡ quý báu đó. Tôi xin được bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Nguyễn Mậu Hân và TS. Nguyễn Công Hào là những thầy giáo trực tiếp hướng dẫn và chỉ bảo cho tôi hoàn thành luận án. Tôi xin chân thành cảm ơn gia đình, bạn bè và đồng nghiệp đã động viên, khích lệ, tạo điều kiện và giúp đỡ tôi trong suốt quá trình thực hiện và hoàn thành luận án này. TÁC GIẢ LUẬN ÁN Nghiên cứu sinh Lê Văn Tƣờng Lân iii Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử MỤC LỤC Lời cam đoan ...............................................................................................................ii Lời cảm ơn ............................................................................................................... iii Danh mục các từ viết tắt ............................................................................................vii Danh mục các ký hiệu ............................................................................................. viii Danh mục các bảng biểu ............................................................................................ ix Danh mục các hình vẽ ................................................................................................. x Mở đầu ....................................................................................................................... 1 Chƣơng 1. Cơ sở lý thuyết về đại số gia tử và tổng quan phân lớp dữ liệu bằng cây quyết định ................................................................................................. 10 1.1. Lý thuyết tập mờ ...................................................................................... 10 1.1.1.Tập mờ và thông tin không chắc chắn ............................................ 10 1.1.2. Biến ngôn ngữ................................................................................ 12 1.2. Đại số gia tử............................................................................................... 14 1.2.1. Khái niệm đại số gia tử .................................................................. 14 1.2.2. Các hàm đo của đại số gia tử ......................................................... 16 1.2.3. Một số tính chất của các hàm đo ................................................... 17 1.2.4. Khoảng mờ và các mối tương quan của khoảng mờ ..................... 20 1.3. Phân lớp dữ liệu bằng cây quyết định ...................................................... 21 1.3.1. Bài toán phân lớp trong khai phá dữ liệu ...................................... 21 1.3.2. Cây quyết định ............................................................................... 23 1.3.3. Lợi ích thông tin và tỷ lệ lợi ích thông tin ..................................... 24 1.3.4. Vấn đề quá khớp trong mô hình cây quyết định .......................... 26 1.4. Phân lớp dữ liệu bằng cây quyết định mờ ................................................. 28 1.4.1. Các hạn chế của phân lớp dữ liệu bằng cây quyết định rõ ............ 28 1.4.2. Bài toán phân lớp dữ liệu bằng cây quyết định mờ ....................... 29 iv Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 1.4.3. Một số vấn đề của bài toán phân lớp dữ liệu bằng cây quyết định mờ .......................................................................................................... 31 1.5. Kết luận chương 1 ..................................................................................... 35 Chƣơng 2. Phân lớp dữ liệu bằng cây quyết định mờ theo phƣơng pháp đối sánh điểm mờ dựa trên đại số gia tử ............................................................ 36 2.1. Giới thiệu ................................................................................................... 36 2.2. Phương pháp chọn tập mẫu huấn luyện đặc trưng cho bài toán học phân lớp dữ liệu bằng cây quyết định ..................................................................... 38 2.2.1. Tính chất thuộc tính của tập mẫu huấn luyện đối với quá trình huấn luyện ................................................................................................ 40 2.2.2. Ảnh hưởng từ phụ thuộc hàm giữa các thuộc tính trong tập huấn luyện ........................................................................................................ 41 2.3. Phân lớp dữ liệu bằng cây quyết định dựa trên ngưỡng miền trị thuộc tính .................................................................................................................. 44 2.3.1. Cơ sở của việc xác định ngưỡng cho quá trình học phân lớp........ 44 2.3.2. Thuật toán MixC4.5 dựa trên ngưỡng miền trị thuộc tính .......... 44 2.3.3. Cài đặt thử nghiệm và đánh giá thuật toán MixC4.5.................... 47 2.4. Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đối sánh điểm mờ .... 53 2.4.1. Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định mờ 53 2.4.2. Vấn đề với tập mẫu huấn luyện không thuần nhất ........................ 55 2.4.3. Một cách định lượng giá trị ngôn ngữ ngoại lai trong tập mẫu huấn luyện ........................................................................................................ 58 2.4.4. Thuật toán học bằng cây quyết định mờ FMixC4.5 dựa trên đối sánh điểm mờ ........................................................................................... 63 2.4.5. Cài đặt thử nghiệm và đánh giá thuật toán FMixC4.5 ................. 64 2.5. Kết luận Chương 2 .................................................................................... 67 Chƣơng 3. Phƣơng pháp huấn luyện cây quyết định mờ cho bài toán phân lớp dữ liệu dựa trên đối sánh khoảng mờ ........................................................... 69 3.1. Giới thiệu ................................................................................................... 69 3.2. Phương pháp đối sánh giá trị khoảng trên thuộc tính mờ ....................... 70 3.2.1. Xây dựng cách thức đối sánh giá trị khoảng dựa trên đại số gia tử70 v Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 3.2.2. Phương pháp định lượng khoảng mờ khi chưa biết miền trị MIN, MAX của các thuộc tính mờ .................................................................... 72 3.3. Phân lớp dữ liệu bằng cây quyết định mờ dựa trên cách thức đối sánh khoảng mờ ........................................................................................................ 77 3.3.1. Thuật toán phân lớp dữ liệu bằng cây quyết định mờ HAC4.5 dựa trên đối sánh khoảng mờ .......................................................................... 77 3.3.2. Cài đặt thử nghiệm và đánh giá thuật toán HAC4.5 .................... 80 3.4. Xây dựng khái niệm khoảng mờ lớn nhất và phương pháp học nhằm tối ưu mô hình cây quyết định mờ ........................................................................ 85 3.4.1. Phát biểu bài toán học phân lớp dữ liệu bằng cây quyết định mờ theo hướng đa mục tiêu ........................................................................... 85 3.4.2. Khái niệm khoảng mờ lớn nhất và cách thức tính khoảng mờ lớn nhất cho các thuộc tính mờ ...................................................................... 86 3.4.3. Thuật toán phân lớp dữ liệu bằng cây quyết định mờ HAC4.5* theo cách tiếp cận khoảng mờ lớn nhất ................................................. 88 3.4.4. Cài đặt thử nghiệm và đánh giá thuật toán HAC4.5* .................. 92 3.5. Kết luận chương 3 ..................................................................................... 96 Kết luận .................................................................................................................... 98 Danh mục các công trình khoa học của tác giả liên quan đến luận án ............ 100 Tài liệu tham khảo ................................................................................................ 101 vi Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Viết đầy đủ ĐSGT Đại số gia tử GĐ1 Giai đoạn 1 GĐ2 Giai đoạn 2 CART Classification and Regression Trees Dom Domain Gain Gain Information GainRatio Gain Information Ratio HA Hedge Algebra LDT Linguistic Decision Tree Sim Similar SplitInfo Split Information vii Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử DANH MỤC CÁC KÝ HIỆU Diễn giải ý nghĩa Ký hiệu Ai Thuộc tính Ai D Tập mẫu huấn luyện 𝐷𝐴𝑖 f Tập các giá trị kinh điển của Ai Ánh xạ fh(S) Hàm đánh giá tính hiệu quả của cây fn(S) Hàm đánh giá tính đơn giản của cây Ik 𝐿𝐷𝐴𝑖 O(log n) µA(v) S sim(x, y) Tập tất cả các khoảng mờ mức k của các giá trị ngôn ngữ Tập các giá trị ngôn ngữ của Ai Độ phức tạp logarit của thuật toán Hàm định lượng của giá trị ngôn ngữ A (đo độ thuộc của v) Cây quyết định Mức độ gần nhau của x và y v Giá trị định lượng theo điểm của giá trị ngôn ngữ X Đại số gia tử Y Thuộc tính phân lớp viii Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử DANH MỤC CÁC BẢNG BIỂU Bảng 2.1. Bảng dữ liệu DIEUTRA .......................................................................... 38 Bảng 2.2. Thông số thuộc tính tập huấn luyện chọn từ cơ sở dữ liệu Northwind ... 48 Bảng 2.3. Bảng so sánh kết quả huấn luyện của thuật toán MixC4.5 với 1000 mẫu trên cơ sở dữ liệu Northwind ................................................................... 49 Bảng 2.4. Bảng so sánh kết quả huấn luyện của thuật toán MixC4.5 với 1500 mẫu trên cơ sở dữ liệu Northwind ................................................................... 49 Bảng 2.5. Thông số thuộc tính tập huấn luyện từ cơ sở dữ liệu Mushroom ............ 50 Bảng 2.6. Bảng so sánh kết quả của thuật toán MixC4.5 với 5000 mẫu huấn luyện trên cơ sở dữ liệu có chứa thuộc tính mờ Mushroom ............................. 51 Bảng 2.7. Bảng dữ liệu DIEUTRA có thuộc tính Lương chứa dữ liệu rõ mà mờ ... 55 Bảng 2.8. Bảng so sánh kết quả kiểm tra độ chính xác của thuật toán FMixC4.5 trên cơ sở dữ liệu có chứa thuộc tính mờ Mushroom........................... 65 Bảng 2.9. Bảng so sánh thời gian kiểm tra của thuật toán FMixC4.5 trên cơ sở dữ liệu có chứa thuộc tính mờ Mushroom ............................................ 65 Bảng 3.1. Tập mẫu huấn luyện chứa thuộc tính Lương không thuần nhất, chưa xác định Min-Max ......................................................................................... 75 Bảng 3.2. Bảng so sánh kết quả với 5000 mẫu huấn luyện của thuật toán C4.5, FMixC4.5 và HAC4.5 trên cơ sở dữ liệu có chứa thuộc tính mờ Mushroom ............................................................................................... 80 Bảng 3.3. Thông số thuộc tính tập huấn luyện từ cơ sở dữ liệu Aldult ................... 82 Bảng 3.4. Bảng so sánh kết quả với 20000 mẫu huấn luyện của thuật toán C4.5, FMixC4.5 và HAC4.5 trên cơ sở dữ liệu có chứa thuộc tính mờ Adult 82 Bảng 3.5. Đối sách thời gian kiểm tra từ 1000 đến 5000 mẫu trên dữ liệu Adult ... 83 Bảng 3.6. Đối sánh kết quả huấn luyện trên dữ liệu Adult ...................................... 92 Bảng 3.7. Tỷ lệ kiểm tra của HAC4.5* trên dữ liệu Adult ...................................... 93 Bảng 3.8. Kết quả dự đoán trung bình của các thuật toán FMixC4.5, HAC4.5 và HAC4.5* đối với các cách tiếp cận khác .............................................. 94 ix Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử DANH MỤC CÁC HÌNH VẼ Hình 1.1. Tính mờ của phần tử sinh lớn .................................................................. 19 Hình 1.2. Mối tương quan I(y)  I(x) ...................................................................... 21 Hình 1.3. Mối tương quan của y được đối sánh theo x, khi I(y)  I(x) ................... 21 Hình 1.4. Mối tương quan của y được đối sánh theo x1, khi I(y)  I(x) .................. 21 Hình 1.5. Minh họa hình học về chỉ số Gini............................................................ 26 Hình 1.6. Vấn đề “quá khớp” trong cây quyết định ................................................ 27 Hình 1.7. Điểm phân chia đa phân theo giá trị ngôn ngữ tại thuộc tính mờ ........... 32 Hình 1.8. Điểm phân chia nhị phân theo giá trị ngôn ngữ hoặc giá trị số tại thuộc tính mờ, dựa trên phương pháp định lượng ngữ nghĩa theo điểm trong ĐSGT ...................................................................................................... 34 Hình 2.1. Cây quyết định được tạo từ tập mẫu huấn luyện M1 .............................. 39 Hình 2.2. Cây quyết định không có hiệu quả được tạo từ tập huấn luyện M2 ........ 39 Hình 2.3. So sánh thời gian huấn luyện của MixC4.5 với các thuật toán khác ....... 50 Hình 2.4. So sánh số nút trên cây kết quả của MixC4.5 với các thuật toán khác.... 52 Hình 2.5. So sánh tỷ lệ đúng trên kết quả của MixC4.5 với các thuật toán khác .... 52 Hình 2.6. Mô hình cho quá trình học phân lớp mờ ................................................. 53 Hình 2.7. Mô hình đề nghị cho việc học phân lớp bằng cây quyết định mờ ........... 54 Hình 2.8. Cây quyết định kết quả “sai lệch” khi tập mẫu huấn luyện bị loại bỏ giá trị ngôn ngữ .............................................................................................. 56 Hình 2.9. Tính mờ của thuộc tính Lương khi chưa xét các giá trị ngoại lai ............ 62 Hình 2.10. So sánh thời gian huấn luyện với 5000 mẫu Mushroom của FMixC4.5 với các thuật toán khác ............................................................................ 66 Hình 2.11. So sánh thời gian kiểm tra với 2000 mẫu Mushroom của FMixC4.5 với các thuật toán khác................................................................................... 66 Hình 2.12. So sánh tỷ lệ đúng trên cây kết quả của FMixC4.5 với các thuật toán khác .......................................................................................................... 67 Hình 3.1. So sánh thời gian huấn luyện trên mẫu 5000 mẫu của Mushroom.......... 81 x

Luận án Tiến sĩ Khoa học máy tính: Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử

Nội dung