Luận án Tiến sĩ Toán học: Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ

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

Thêm vào BST

Báo xấu

2
lượt xem 1
download

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

Luận án Tiến sĩ Toán học "Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ" trình bày các nội dung chính sau: Tổng quan về tập thô và các mở rộng của tập thô; Cập nhật các quyết định ba nhánh trong hệ thông tin không đầy đủ động; Cập nhật các tập xấp xỉ trong không gian xấp xỉ phủ động; Đề xuất phương pháp cân bằng dữ liệu theo hướng tiếp cận tập thô mờ.

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ĩ Toán học: Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ TRẦN THỊ THANH HUYỀN NGHIÊN CỨU PHÁT TRIỂN CÁC PHƯƠNG PHÁP CẬP NHẬT BẢNG QUYẾT ĐỊNH PHỦ ĐỘNG VÀ XỬ LÝ MẤT CÂN BẰNG DỮ LIỆU DỰA TRÊN TẬP THÔ MỜ LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2025
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ TRẦN THỊ THANH HUYỀN NGHIÊN CỨU PHÁT TRIỂN CÁC PHƯƠNG PHÁP CẬP NHẬT BẢNG QUYẾT ĐỊNH PHỦ ĐỘNG VÀ XỬ LÝ MẤT CÂN BẰNG DỮ LIỆU DỰA TRÊN TẬP THÔ MỜ Ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC Người hướng dẫn khoa học: 1. PGS.TS Lê Bá Dũng 2. TS. Nguyễn Đỗ Văn Hà Nội - 2025
i LỜI CAM ĐOAN Tôi xin cam đoan, đây là công trình nghiên cứu của riêng tôi. Những nội dung, số liệu và kết quả trình bày trong luận án là hoàn toàn trung thực và chưa có tác giả nào công bố trong bất cứ một công trình nào khác. Các tài liệu tham khảo được trích dẫn đầy đủ. Hà Nội, ngày ....tháng .... năm 2024 Tác giả
ii MỤC LỤC Trang DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ........................................... v DANH MỤC CÁC BẢNG............................................................................. vi DANH MỤC CÁC HÌNH VẼ ...................................................................... vii MỞ ĐẦU ......................................................................................................... 1 Chương 1 TỔNG QUAN VỀ TẬP THÔ VÀ CÁC MỞ RỘNG CỦA TẬP THÔ ............................................................................................................... 10 1.1 Mô hình tập thô truyền thống .................................................................. 10 1.1.1 Hệ thông tin đầy đủ .............................................................................. 10 1.1.2 Bảng quyết định ................................................................................... 11 1.1.3 Tập thô.................................................................................................. 12 1.2. Tập thô dung sai ..................................................................................... 15 1.2.1 Hệ thông tin không đầy đủ ................................................................... 15 1.2.2 Tập thô dung sai ................................................................................... 16 1.3. Tập thô mờ (Fuzzy rough set) ................................................................ 18 1.3.1 Tập mờ ................................................................................................. 18 1.3.2 Tập thô mờ ........................................................................................... 20 1.4. Quyết định ba nhánh (Three-way decisions) ......................................... 21 1.5. Tập thô phủ............................................................................................. 24 1.6 Những vấn đề luận án cần tập trung nghiên cứu giải quyết.................... 26 1.6.1 Các nghiên cứu liên quan đến cập nhật tăng cường theo hướng tiếp cận tập thô ............................................................................................................ 26 1.6.2 Các vấn đề còn tồn tại .......................................................................... 28 1.6.3 Các đề xuất của luận án ........................................................................ 29 1.7 Kết luận Chương 1 .................................................................................. 29 Chương 2 CẬP NHẬT QUYẾT ĐỊNH BA NHÁNH TRONG HỆ THÔNG TIN KHÔNG ĐẦY ĐỦ ĐỘNG.................................................................... 30
iii 2.1 Bài toán cập nhật tăng cường các quyết định ba nhánh .......................... 30 2.1.1 Bài toán cập nhật tăng cường quyết định ba nhánh trong hệ thông tin đầy đủ ............................................................................................................ 31 2.1.2 Bài toán cập nhật tăng cường quyết định ba nhánh trong hệ thông tin không đầy đủ ................................................................................................. 35 2.1.3 Nhận xét ............................................................................................... 38 2.2 Khảo sát xu hướng thay đổi của xác suất có điều kiện ........................... 39 2.2.1 Sự thay đổi của các xác suất có điều kiện khi tập đối tượng thay đổi . 40 2.2.2 Sự thay đổi của các xác suất có điều kiện khi thay đổi các giá trị thuộc tính của các đối tượng ................................................................................... 44 2.3 Cập nhật quyết định ba nhánh dưới sự thay đổi của xác suất có điều kiện51 2.4 Đề xuất phương pháp cập nhật các quyết định ba nhánh........................ 54 2.5 Ví dụ minh họa ........................................................................................ 56 2.6 Kết luận chương 2 ................................................................................... 65 Chương 3 CẬP NHẬT TẬP XẤP XỈ TRONG KHÔNG GIAN XẤP XỈ PHỦ ĐỘNG .................................................................................................. 66 3.1 Khảo sát về hàm thành viên thô và các tập xấp xỉ phân bậc trong không gian xấp xỉ phủ .............................................................................................. 66 3.1.1 Hàm thành viên thô .............................................................................. 66 3.1.2 Các tập xấp xỉ phân bậc ....................................................................... 68 3.1.3 Khảo sát các phương pháp cập nhật các tập xấp xỉ phân bậc .............. 70 3.1.4 Nhận xét ............................................................................................... 71 3.2 Đề xuất phương pháp cập nhật tập xấp xỉ ............................................... 71 3.2.1 Xu hướng thay đổi của hàm thành viên thô dạng ba ........................... 71 3.2.2 Cập nhật các tập xấp xỉ phân cấp ......................................................... 77 3.2.3 Đề xuất phương pháp cập nhật các tập xấp xỉ ..................................... 79 3.3 Ví dụ minh họa ........................................................................................ 80 3.4 Kết luận chương 3 ................................................................................... 83
iv Chương 4 PHƯƠNG PHÁP CÂN BẰNG DỮ LIỆU SỬ DỤNG TẬP THÔ MỜ................................................................................................................. 85 4.1 Bài toán cân bằng dữ liệu ........................................................................ 85 4.1.1 Hàm đo lường chất lượng .................................................................... 87 4.1.2 Thuật toán MFRIS1.............................................................................. 87 4.1.3 Thuật toán MFRIS2.............................................................................. 89 4.1.4 Nhận xét ............................................................................................... 90 4.2 Đề xuất thuật toán ................................................................................... 92 4.2.1 Thuật toán MFRIS3.............................................................................. 92 4.2.2 Tối ưu hóa ngưỡng và điều chỉnh độ chi tiết ....................................... 93 4.3 Thử nghiệm ............................................................................................. 96 4.3.1 Thiết lập thí nghiệm ............................................................................. 96 4.3.2 Kết quả thực nghiệm ............................................................................ 98 4.4 Kết luận chương 4 ................................................................................. 103 KẾT LUẬN ................................................................................................. 104 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ............ 106 TÀI LIỆU THAM KHẢO........................................................................... 107
v DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Ký hiệu, chữ viết tắt Ý nghĩa 𝐼𝐼𝑆 Hệ thông tin không đầy đủ 𝐸𝑄 Quan hệ không phân biệt được 𝐸 Lớp không phân biệt được 𝑎𝑝𝑝𝑟 ( 𝑋) Tập xấp xỉ dưới của tập 𝑋 𝑎𝑝𝑝𝑟 (𝑋) Tập xấp xỉ trên của tập 𝑋 𝑃𝑂𝑆 (𝑋) Miền dương của tập 𝑋 𝐵𝑁𝐷 (𝑋) Miền biên của tập 𝑋 𝑁𝐸𝐺 (𝑋) Miền âm của tập 𝑋 ~𝑋 Tập bù của tập 𝑋 |𝑋| Lực lượng của tập 𝑋 𝐶𝐴𝑆 Không gian xấp xỉ phủ 𝑇𝑂𝐿 Quan hệ dung sai 𝑇 Lớp dung sai 𝑃𝑟(𝐵 ⁄ 𝑇 (𝑥)) Xác suất có điều kiện NCS Nghiên cứu sinh 𝜎 𝒞 (𝑥) Hàm thành viên thô dạng một 𝜙 𝒞 (𝑥) Hàm thành viên thô dạng hai 𝒱 𝒞 (𝑥) Hàm thành viên thô dạng ba 𝜑 𝒞 (𝑥) Hàm thành viên thô dạng bốn 𝒞 (𝑋) Tập xấp xỉ dưới phân cấp 𝒞 (𝑋) Tập xấp xỉ trên phân cấp 𝑁 𝒞 (𝑥) Lân cận của 𝑥
vi DANH MỤC CÁC BẢNG Trang Bảng 1.1. Một ví dụ về hệ thông tin............................................................. 11 Bảng 1.2. Ví dụ về hệ thông tin không đầy đủ ............................................. 16 Bảng 1.3. Bảng thông tin đầy đủ ................................................................... 23 Bảng 2. 1. Cập nhật các mẫu của xác suất có điều kiện ............................... 32 Bảng 2.2. So sánh phương pháp luận án đề xuất với phương pháp tính toán ban đầu .......................................................................................................... 56 Bảng 2. 3. Hệ thông tin tại thời điểm 𝒕 ......................................................... 57 Bảng 2. 4. Hệ thông tin tại thời điểm 𝒕 + 𝟏 .................................................. 59 (Khi tập đối tượng thay đổi) .......................................................................... 59 Bảng 2. 5. Hệ thông tin tại thời điểm 𝒕 + 𝟏 .................................................. 61 Bảng 2. 6. Hệ thông tin tại thời điểm 𝒕 + 𝟏 .................................................. 62 Bảng 2. 7. Hệ thông tin tại thời điểm 𝒕 + 𝟏 .................................................. 64 Bảng 3. 1. So sánh phương pháp đề xuất và phương pháp tính toán ban đầu80 Bảng 3. 2. Hệ thông tin tại thời điểm 𝒕 ......................................................... 81 Bảng 4. 1. Bộ dữ liệu thử nghiệm ................................................................. 97 Bảng 4. 2. Bảng ma trận nhầm lẫn cho hai lớp vấn đề ................................. 99 Bảng 4. 3. 𝐴𝑈𝐶 trung bình được lưu trữ bởi các phân loại khác nhau cho mỗi phương pháp chọn đối tượng (số in đậm hiển thị mức cao nhất) ................. 99 Bảng 4. 4. Xếp hạng Friedman đối với 𝑨𝑼𝑪 .............................................. 100 Bảng 4. 5. Thống kê Friedman .................................................................... 101 Bảng 4. 6. So sánh MFRIS3 với các thuật toán khác.................................. 101 Bảng 4. 7. Thời gian chuẩn bị trước cho mỗi phương pháp lựa chọn đối tượng............................................................................................................ 102
vii DANH MỤC CÁC HÌNH VẼ Trang Hình 1. 1. Tập 𝑋 được xấp xỉ bởi các tập xấp xỉ dưới và xấp xỉ trên ........... 13 Hình 4. 1. Biểu đồ hiển thị phân phối của các xấp xỉ và xấp xỉ trung bình của tập dữ liệu ...................................................................................................... 91 Hình 4. 2. Độ lệch chuẩn của tập dữ liệu ozon_one_hr ................................ 94 Hình 4. 3. So sánh trung bình của 𝐴𝑈𝐶 (trên tất cả các bộ dữ liệu) và tăng trung bình của 𝐴𝑈𝐶 bằng cách sử dụng MFRIS cho các phân loại khác nhau102
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Lý thuyết tập thô được Pawlak đề xuất vào năm 1982 [61] và được ông và các cộng sự nghiên cứu và phát triển [62-64] đã được sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức. Kể từ khi ra đời, lý thuyết tập thô đã cung cấp nhiều công cụ hữu ích để giải quyết các vấn đề về học máy, thu nhận kiến thức, phân tích quyết định và khai phá tri thức từ cơ sở dữ liệu. Trong lý thuyết tập thô, dữ liệu được biểu diễn dưới dạng bảng gọi là bảng thông tin [61]. Các hàng của bảng tương ứng với các đối tượng, các cột tương ứng với các thuộc tính của các đối tượng đó. Cách tiếp cận chính của lý thuyết Tập thô dựa trên mối quan hệ không phân biệt được cùng với việc đưa ra hai tập “rõ” (scrip), là các tập xấp xỉ của tập đối tượng cần quan sát. Tức là, tất cả các tập đối tượng được xấp xỉ bởi hai tập là tập xấp xỉ dưới, bao gồm tất cả các đối tượng chắc chắn thuộc tập hợp đó, và tập xấp xỉ trên, chứa tất cả các đối tượng có khả năng thuộc tập hợp đó. Cách tiếp cận của tập thô nguyên thủy giả thiết rằng tất cả các đối tượng trong hệ thông tin đều có các giá trị thuộc tính được xác định. Tuy nhiên, trong thực tế, dữ liệu đôi khi bị lỗi, một số giá trị trong cơ sở dữ liệu không xác định. Do đó, cần mở rộng lý thuyết tập thô để việc phân loại dữ liệu hiệu quả hơn, các khái niệm và mô hình phù hợp hơn với thực tế. Đã có nhiều nhà khoa học mở rộng tập thô để giải quyết vấn đề này [19, 23, 26-28, 33-39, 45, 46, 60, 74, 75, 78, 79, 89, 100]. Kryszkiewicz [45, 46] đã mở rộng tập thô bằng cách xây dựng quan hệ dung sai (Tolerance relation), Stefanowskiand và Tsoukias [74, 75] thảo luận về giới hạn và giới thiệu quan hệ tương tự (similarity relation) dựa trên quan hệ dung sai. Yang và các cộng sự [89] đã khái quát một phân lớp hợp lý và linh hoạt trong hệ thông tin không đầy đủ, gọi là quan hệ nhị phân mới (new binary relation), Wang [100]
2 giới thiệu quan hệ dung sai giới hạn (limited tolerance relation). Nhóm của Tiến sĩ Nguyễn Đỗ Văn đã định nghĩa một mối quan hệ dung sai mở rộng bằng cách sử dụng tần suất các giá trị thuộc tính và xây dựng mô hình tập thô xác suất tham số (Parameterized Probabilistic Rough Set) [26-28, 79]. Trong thực tế khi mở rộng tập thô để xử lý các giá trị thuộc tính điều kiện bị thiếu trong hệ thông tin không đầy đủ được chia làm hai hướng. Hướng thứ nhất gọi là “Giá trị bị mất (Lost value)” tiếp cận theo cách coi giá trị thuộc tính chưa biết là giá trị bị mất (Lost value) [13]. Hướng thứ hai gọi là “Không quan tâm (Do not care)”, các giá trị chưa biết có thể thay thế bằng bất cứ giá trị nào trong miền giá trị. Grzymala-Busse [33-39] đã xây dựng một quan hệ đặc trưng dựa trên cả trường hợp "Giá trị bị mất" và trường hợp "Không quan tâm". Tại Việt Nam một số luận án Tiến sĩ về lý thuyết tập thô và các mở rộng của tập thô đã được hoàn thành [1-5]. Các công trình nghiên cứu về tập thô [6-8, 14, 66, 67, 73, 76, 77, 91-93, 106] chứng tỏ rằng lý thuyết tập thô đóng vai trò quan trọng, là nền tảng trong tính toán hạt, trí tuệ nhân tạo, khai phá dữ liệu, khám phá tri thức, nhận dạng mẫu, hệ thống thông minh… Các phương pháp dựa trên tập thô được ứng dụng trong nhiều lĩnh vực như âm học, tin sinh học, kinh doanh và tài chính, hóa học, kỹ thuật máy tính, hệ thống và phân tích quyết định, kinh tế học, kỹ thuật điện, nghiên cứu môi trường, xử lý ảnh số, tin học, y học, sinh học phân tử, âm nhạc học, thần kinh học, người máy, khoa học xã hội, kỹ thuật phần mềm, trực quan hóa không gian, kỹ thuật web và khai phá web …Chính vì vậy lý thuyết tập thô đã nhận được sự quan tâm của đông đảo các nhà khoa học trong nước và thế giới. Một trong những công cụ nhận thức và phương pháp phỏng đoán hiệu quả nhất trong việc giải quyết vấn đề của con người là hiểu, biểu diễn và xử lý một tổng thể theo ba phần liên quan được gọi là phép chia ba. Ví dụ như, Khi muốn đánh giá một lĩnh vực nghiên cứu nào đó thì chúng ta thường đánh giá
3 theo ba khía cạnh là triết học, lý thuyết và thực tiễn. Khi đánh giá chất lượng của một sản phẩm thường sẽ có ba mức độ đánh giá định tính là thấp, trung bình, và cao. Hay cảm xúc của con người thường được chia thành ba loại là tích cực, trung lập, và tiêu cực. Từ các ý tưởng về phép chia ba trong nhiều lĩnh vực khác nhau, nhóm nghiên cứu của Yao [94, 95] đã đề xướng và đóng góp quan trọng về lý thuyết quyết định ba nhánh. Ý tưởng chính của phương pháp này là dùng mô hình tập thô lý thuyết quyết định (decision-theoretic rough set) (DTRS) để chia một tập hợp thành ba miền dời nhau, là miền dương (positive region), miền biên (boundary region) và miền âm (negative region). Ưu điểm của mô hình này là sử dụng một cặp ngưỡng để xác định các tập xấp xỉ, vì vậy nó cho phép các sai số chấp nhận được của các lỗi. Trong những năm gần đây, lý thuyết này đã nhận được sự quan tâm ngày càng nhiều của các nhà khoa học trên toàn thế giới [22, 90, 96, 98, 99, 101, 102]. Trong các ứng dụng thực tế, dữ liệu trong một hệ thông tin thường thay đổi không ngừng, vì thế các kỹ thuật được đề xuất để khai thác các cơ sở dữ liệu động. Kỹ thuật này thường sử dụng các kết quả khai thác thu được từ cơ sở dữ liệu đầu tiên để làm điều kiện bảo trì và cập nhật lại các kiến thức trong cơ sở dữ liệu động mà không cần khai thác lại từ đầu. Đã có nhiều nghiên cứu theo hướng này [19, 55-59, 85]. Liu và các cộng sự đề xuất một DTRS động bằng cách xem xét sự thay đổi động của hàm mất mát trong môi trường quyết định động [52]. Gần đây nhất, Luo và các cộng sự đề xuất một phương pháp để cập nhật tăng cường các quyết định ba nhánh trong hệ thông tin không đầy đủ (incomplete information system) khi tập đối tượng thay đổi theo thời gian [55-59]. Trong đó, các luật quyết định ba nhánh được cập nhật trong hai trường hợp riêng biệt là thêm hoặc xóa một đối tượng trong hệ thống. Xu và các cộng sự đề xuất phương pháp tính toán ròng (stream computing) trong hệ thông tin đầy đủ khi đồng thời thêm và xóa các đối tượng [85]. Các phương pháp này được chứng minh là nhanh hơn đáng kể so với các kỹ thuật khác.
4 Tuy nhiên chúng chủ yếu được sử dụng trong hệ thông tin đầy đủ, còn đối với hệ thống không hoàn chỉnh thì chỉ áp dụng trong từng trường hợp đơn lẻ. Khi nghiên cứu cập nhật các tập xấp xỉ, Hu và các cộng sự đã đề xuất một phương pháp rút gọn thuộc tính gia tăng dựa trên các tập cơ bản [40]. Chan đã thảo luận một cách tiếp cận gia tăng để cập nhật các xấp xỉ của một khái niệm khi thêm hoặc xóa một thuộc tính trong một hệ thống thông tin hoàn chỉnh bằng cách sử dụng các biên dưới và trên [16, 17]. Li và các cộng sự đã nghiên cứu phương pháp cập nhật các tập xấp xỉ thô đối với dữ liệu dominance khi tập thuộc tính và tập đối tượng thay đổi [49, 50]. Zhang và cộng sự đề xuất một cách tiếp cận ma trận dựa trên tập thô để tính toán các xấp xỉ cập nhật gia tăng [105]. Trong những năm gần đây, các nhà nghiên cứu đã mở rộng các nghiên cứu về các phương pháp cập nhật gia tăng trong không gian xấp xỉ phủ. Lang và các cộng sự đã cung cấp một số phương pháp để tính toán các ma trận đặc trưng loại 1 và loại 2 của các phủ động khi các đối tượng thay đổi [47]. Cai và các cộng sự nghiên cứu rút gọn tri thức của hệ thông tin quyết định phủ động do thay đổi giá trị thuộc tính [13]. Hu và các cộng sự đề xuất một phương pháp để cập nhật các xấp xỉ dựa trên ma trận quan hệ tương đương, ma trận đường chéo và ma trận cắt trong tập thô đa hạt khi một cấu trúc hạt đơn lẻ thay đổi theo thời gian [41]. Các phương pháp này chủ yếu tiếp cận theo hướng chia tập biên thành các tập biên trên và các tập biên dưới, hoặc dựa vào sự thay đổi của các ma trận để cập nhật các tập xấp xỉ. Một nguyên nhân có thể gây ra vấn đề không nhất quán là dữ liệu mất cân bằng (imbalance data) [54]. Dữ liệu mất cân bằng là tập dữ liệu mà trong đó số đối tượng trong một số lớp, gọi là lớp thiểu số (minority classes) ít hơn nhiều so với số đối tượng trong lớp đa số (majority classes). Đã có nhiều nghiên cứu dùng các ưu điểm của lý thuyết tập thô để nâng cao hiệu suất phân lớp khi cân bằng dữ liệu [12, 18, 20, 25, 70, 71, 83]. Với cách tiếp cận dùng tập thô mờ để chọn các đối tượng từ tập dữ liệu mất cân bằng, một số nghiên
5 cứu đã kết hợp giữa các phương pháp cân bằng và tập thô để loại bỏ nhiễu bên cạnh một số nghiên cứu dùng các tiêu chí khác nhau để xác định ngưỡng cho các tập thiểu số và đa số. Nhóm của tác giả Do Van, N (TS Nguyễn Đỗ Văn) đã giới thiệu cách tiếp cận dựa trên tập thô mờ để cân bằng và chọn các đối tượng chất lượng từ các tập dữ liệu không cân bằng [80]. Phương pháp này sử dụng các ngưỡng khác nhau cho các lớp đa số và thiểu số để chọn được nhiều đối tượng hơn từ các lớp thiểu số. Tuy nhiên, việc chọn ngưỡng của phương pháp này vẫn thực hiện thủ công vì vậy chưa tối ưu. Trên thế giới, quyết định ba nhánh là chủ đề của các luận án Tiến sĩ, điển hình là các luận án Tiến sĩ trong nhóm nghiên cứu của GS. Y. Yao [9, 24, 30, 43, 107]. Ở Việt Nam lý thuyết tập thô và mở rộng nhận được sự quan tâm nghiên cứu của một số nhóm nghiên cứu, điển hình là các nhóm nghiên cứu tại Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam (thầy PGS. TS Hồ Thuần, thầy PGS. TS Nguyễn Long Giang,…) và một số luận án tiến sĩ đã được công bố (chẳng hạn [1-5]). Tuy nhiên chưa có luận án Tiến sĩ nào về quyết định ba nhánh tại Việt Nam. Xuất phát từ thực tiễn nêu trên, luận án chọn “Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ” với mong muốn đề xuất phương pháp học tăng cường và cân bằng dữ liệu giúp tối ưu hóa thời gian và hiệu năng của mô hình. 2. Mục tiêu nghiên cứu - Nghiên cứu bài toán cập nhật tăng cường các quyết định ba nhánh và tập xấp xỉ trong hệ thông tin đầy đủ và không đầy đủ động. Nghiên cứu các kỹ thuật cân bằng dữ liệu đối với các tập dữ liệu mất cân bằng. Từ đó, luận án đề xuất hai phương pháp cập nhật tăng cường trong không gian xấp xỉ và không gian xấp xỉ phủ động. Luận án cũng đề xuất cải tiến thuật toán cân
6 bằng dữ liệu và tối ưu hóa ngưỡng để việc cân bằng dữ liệu đạt hiệu quả cao hơn. Để đạt được các mục tiêu nghiên cứu đặt ra, luận án tập trung giải quyết các câu hỏi nghiên cứu sau: - Thứ nhất, làm thế nào để cập nhật được các miền ba nhánh khi đồng thời thêm và xóa các đối tượng trong hệ thông tin không đầy đủ? - Thứ hai, làm thế nào để cập nhật các tập xấp xỉ phân cấp trong hệ thông tin không đầy đủ? Các câu hỏi nghiên cứu này được giải quyết bằng phương pháp cập nhật trình bày trong Chương 2 và Chương 3 của luận án. - Cuối cùng, luận án cần có những cải tiến gì để có thể giải quyết bài toán cân bằng dữ liệu trong hệ thống mất cân bằng? Bài toán này được giải quyết bằng thuật toán cân bằng dữ liệu và tối ưu hóa ngưỡng được trình bày trong Chương 4 của luận án. 3. Đối tượng và phạm vi nghiên cứu Đối tượng: Đối tượng luận án nghiên cứu là các bảng quyết định đầy đủ và không đầy đủ với kích thước trung bình và kích thước lớn. Phạm vi: Phạm vi nghiên cứu trọng tâm của luận án là bài toán cập nhật các tập xấp xỉ và các quyết định ba nhánh trong hệ thông tin không đầy đủ và bài toán ứng dụng tập thô vào tối ưu ngưỡng để giảm sự mất cân bằng của dữ liệu. 4. Nội dung nghiên cứu - Nghiên cứu, phân tích, đánh giá và đề xuất mới các phương pháp mới để cập nhật các tập xấp xỉ và các quyết định ba nhánh trong hệ thông tin không đầy đủ động. - Nghiên cứu, phân tích, đánh giá và đề xuất thuật toán trích chọn đối tượng thô mờ và tối ưu hóa các ngưỡng nhằm giải quyết bài toán giảm mất cân bằng dữ liệu.
7 5. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận án kết hợp nghiên cứu lý thuyết với nghiên cứu thực nghiệm. Về lý thuyết: Luận án nghiên cứu tổng quan về bài toán cập nhật gia tăng trong hệ thông tin không đầy đủ động và bài toán giảm sự mất cân bằng dữ liệu. Các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về thực nghiệm: Luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so sánh và đánh giá kết quả thực nghiệm với kết quả nghiên cứu lý thuyết. Từ đó kết luận tính đúng đắn của kết quả nghiên cứu. 6. Ý nghĩa khoa học và thực tiễn Việc nghiên cứu các bài toán cập nhật tăng cường và giảm sự mất cân bằng dữ liệu có ý nghĩa trên cả hai phương diện khoa học và thực tiễn: Về khía cạnh khoa học: Nghiên cứu về bài toán cập nhật gia tăng các quyết định ba nhánh và các tập xấp xỉ trong bảng quyết định động và thuật toán làm giảm sự mất cân bằng của dữ liệu. Dựa trên các nhận xét, đánh giá, luận án đề xuất phương pháp cập nhật các quyết định ba nhánh trong hệ thông tin không đầy đủ động, cập nhật các tập xấp xỉ đối với bảng quyết định phủ động và cải tiến của thuật toán cân bằng dữ liệu. Về khía cạnh thực tiễn: Các kết quả nghiên cứu trong luận án được biểu diễn bằng mô hình toán học và được cài đặt thử nghiệm, đánh giá. Chương trình cài đặt này có thể kế thừa để xây dựng các phương pháp giảm mất cân bằng dữ liệu trong tương lai. 7. Bố cục của luận án Luận án gồm bốn chương cùng với các phần mở đầu, kết luận, danh mục các công trình khoa học đã công bố của tác giả và danh mục tài liệu tham khảo.
8 Chương 1. Tổng quan về tập thô và các mở rộng của tập thô Chương này trình bày tổng quan các kiến thức cơ sở liên quan như mô hình tập thô truyền thống và các mở rộng cũng như các khái niệm cơ bản về quyết định ba nhánh. Tổng hợp phân tích đánh giá các nghiên cứu trong nước và trên thế giới từ đó nêu ra một số vấn đề còn tồn tại làm cơ sở xác định các vấn đề luận án cần tập trung nghiên cứu giải quyết. Chương 2. Cập nhật các quyết định ba nhánh trong hệ thông tin không đầy đủ động Nội dung chương này trình bày các khảo sát về bài toán cập nhật các quyết định ba nhánh trong hệ thông tin động. Từ đó đề xuất phương pháp cải tiến để giải quyết bài toán này cho hệ thông tin không đầy đủ động. Nội dung chính của Chương tập trung nghiên cứu và đề xuất phương pháp cập nhật các quyết định ba nhánh trong khi tập đối tượng thay đổi do đồng thời thêm và xóa các đối tượng. Chương này cũng trình bày kết quả cập nhật quyết định ba nhánh khi giá trị thuộc tính của đối tượng thay đổi theo thời gian. Các phương pháp đề xuất được chứng minh tính đúng đắn bằng cơ sở toán học và có ví dụ minh họa. Chương 3. Cập nhật các tập xấp xỉ trong không gian xấp xỉ phủ động Nội dung chương này trình bày các khảo sát về hàm thành viên thô và tập thô phân bậc trong không gian xấp xỉ phủ. Từ đó đề xuất phương pháp cập nhật các tập xấp xỉ phân bậc khi hệ thông tin không đầy đủ thay đổi do đồng thời thêm và xóa các đối tượng. Nội dung chính của Chương tập trung nghiên cứu xu hướng thay đổi của hàm thành viên thô dạng ba, từ đó đề xuất phương pháp cập nhật các tập xấp xỉ phân cấp dựa trên sự thay đổi đó. Các phương pháp đề xuất được chứng minh bằng cơ sở toán học và ví dụ minh họa. Chương 4. Đề xuất phương pháp cân bằng dữ liệu theo hướng tiếp cận tập thô mờ Chương 4 trình bày các khảo sát về bài toán cân bằng dữ liệu và thuật toán trích chọn đối tượng thô mờ đối với bài toán này, chỉ ra các điểm đạt
9 được và chưa được của các thuật toán trước đó. Từ đó đề xuất phương pháp cải tiến thuật toán trích chọn đối tượng thô mờ và đề xuất thuật toán tối ưu ngưỡng trong thuật toán trích chọn dữ liệu. Đồng thời luận án cũng trình bày kết quả chạy thử nghiệm của thuật toán trích chọn đối tượng thô mờ với các bộ số liệu lấy từ kho dữ liệu UCI.
10 Chương 1 TỔNG QUAN VỀ TẬP THÔ VÀ CÁC MỞ RỘNG CỦA TẬP THÔ Nội dung chính của chương giới thiệu tổng quan về hệ thông tin tĩnh và động. Mô hình tập thô truyền thống và các mở rộng của tập thô. Các khái niệm cơ bản và tính chất cuả các quyết định ba nhánh. 1.1 Mô hình tập thô truyền thống Phần này giới thiệu một số định nghĩa cơ bản của tập thô nguyên thủy được phát triển bởi Pawlak [61, 62, 64, 65]. 1.1.1 Hệ thông tin đầy đủ Trong lý thuyết tập thô, dữ liệu thường được trình bày trong một bảng, mỗi cột tương ứng với một thuộc tính, mỗi hàng tương ứng với một đối tượng và giao của chúng là giá trị thuộc tính của một đối tượng. Các bảng như vậy được gọi là hệ thông tin. Một hệ thông tin có thể được biểu diễn bởi 𝑝 dòng, 𝑛 cột, tương ứng với 𝑝 thuộc tính và 𝑛 đối tượng. Một hệ thông tin trong tập thô thường được định nghĩa như sau: Định nghĩa 1.1. [61] Một hệ thông tin là một bộ 𝐼 = (𝑈, 𝐴, 𝑉, 𝑓), trong đó 𝑈 là tập hữu hạn khác rỗng các đối tượng, gọi là vũ trụ, 𝐴 là tập hữu hạn khác rỗng các thuộc tính, 𝑓: 𝑈 × 𝐴 → 𝑉 là hàm thông tin, 𝑉 = ⋃ ∈ 𝑉 , với 𝑉 là tập các giá trị thuộc tính 𝑎 ∈ 𝐴. Với bất kỳ 𝑎 ∈ 𝐴, 𝑢 ∈ 𝑈, 𝑓(𝑢, 𝑎) ∈ 𝑉 . Với mỗi 𝑢 ∈ 𝑈, 𝑎 ∈ 𝐴, dùng ký hiệu là 𝑎(𝑢) thay cho 𝑓(𝑢, 𝑎) để biểu thị giá trị của đối tượng u tại thuộc tính a; rõ ràng 𝑎(𝑢) ∈ 𝑉 . Nếu 𝐵 = {𝑏 ; 𝑏 ; … ; 𝑏 } ⊆ 𝐴 thì ta ký hiệu 𝑏 (𝑢) bằng 𝐵(𝑢). Do đó, nếu 𝑢, 𝑣 ∈ 𝑈, 𝑏 (𝑢) = 𝑏 (𝑣), ∀𝑏 ∈ 𝐵 thì 𝐵(𝑢) = 𝐵(𝑣). Một hệ thông tin còn được gọi là bảng giá trị thuộc tính, bảng dữ liệu hoặc bảng thông tin.
11 Bảng 1.1. Một ví dụ về hệ thông tin 𝑈 Đau đầu Đau cơ Thân nhiệt Cảm cúm 𝑢 Không Có Cao Có 𝑢 Có Không Cao Có 𝑢 Có Có Rất cao Có 𝑢 Không Có Bình thường Không 𝑢 Có Không Cao Không 𝑢 Không Có Rất cao Có Ví dụ 1.1: Cho hệ thông tin trong Bảng 1.1. Khi đó ta có: Tập các đối tượng 𝑈 = {𝑢 ; 𝑢 ; 𝑢 ; 𝑢 ; 𝑢 ; 𝑢 }. Tập các thuộc tính: 𝐴 = {Đau đầu; Đau cơ; Thân nhiệt; Cảm cúm}. Tập giá trị của thuộc tính Đau đầu là: 𝑉Đ đầ = {Có; Không}. Tập giá trị của thuộc tính Đau cơ là: 𝑉Đ ơ = {Có; Không}. Tập giá trị của thuộc tính Thân nhiệt là: 𝑉 â ệ = {Bình thường; Cao; Rất cao}. Và tập giá trị của thuộc tính Cảm cúm là: 𝑉 ả ú = {Có; Không} Hàm 𝑓 được biểu thị bằng giá trị tương ứng tại điểm giao của mỗi hàng đối tượng và mỗi cột thuộc tính, ví dụ, 𝑓 (𝑢 ; Đau đầu) = Đau đầu(𝑢 ) = Không;𝑓 (𝑢 ; Cảm cúm) = Cảm cúm(𝑢 ) = Có; và 𝑓 (𝑢 ; Thân nhiệt) = Thân nhiệt(𝑢 ) = Rất cao. 1.1.2 Bảng quyết định Định nghĩa 1.2. [61] Bảng quyết định là một hệ thông tin đặc biệt 𝐼 = (𝑈, 𝐶 ∪ 𝐷, 𝑉, 𝑓), trong đó tập thuộc tính A được chia thành hai tập 𝐶, 𝐷 khác rỗng và 𝐶 ∩ 𝐷 = ∅, trong đó, 𝐶 được gọi là tập thuộc tính điều kiện và 𝐷 được gọi là tập thuộc tính quyết định.