THÔNG TIN TÓM TẮT NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN
Đề tài luận án: Nghiên cứu rút gọn tập thuộc tính trong hệ quyết định giá trị tập
Chuyên ngành: Cơ sở toán học cho tin học
Mã số: 62 46 01 10
Họ và tên Nghiên cứu sinh: Phùng Thị Thu Hiền
Người hướng dẫn khoa học:
1. PGS. TS. Nguyễn Bá Tường
2. PGS. TS. Hà Quang Thụy
Cơ sở đào tạo: Học viện Kỹ thuật Quân sự
Tóm tắt những đóng góp mới của luận án
1. Định hướng theo kỹ thuật bảng ngẫu nhiên [56], luận án đề xuất hai cấu trúc dữ liệu mới là bảng ngẫu nhiên tổng quát hóa và các dàn giá trị thuộc tính trong hệ thông tin giá trị tập. Các cấu trúc dữ liệu mới này cho phép phát triển kỹ thuật bảng ngẫu nhiên để đề xuất thuật toán tương ứng tìm tập rút gọn trên hệ quyết định giá trị tập. Kết quả là, luận án đề xuất một thuật toán rút gọn thuộc tính trong hệ quyết định giá trị tập mới là Thuật toán GMDSVDT (Generalized Maximal Discernibility heuristic for Set valued Decision Tables, Thuật toán 3.1).
2. Hơn nữa, luận án chứng tỏ rằng hai cấu trúc dữ liệu bảng ngẫu nhiên tổng quát hóa và các dàn giá trị thuộc tính cũng là công cụ hữu hiệu đề nghị thuật toán tìm các tập xấp xỉ thô trong hệ thông tin giá trị tập. Luận án đề xuất thuật toán VASDT (Verifying upper and lower Approximation for Set valued Decision Tables, Thuật toán 3.2.) tìm tập xấp xỉ trong hệ thông tin giá trị tập. Ngoài việc áp dụng hai cấu trúc dữ liệu nói trên, Thuật toán VASDT còn khai thác ý nghĩa của các khái niệm hàm phân biệt và độ đo bao hàm trong hệ thông tin giá trị tập. Bằng lý thuyết, luận án chứng minh Thuật toán VASDT do luận án đề xuất hiệu quả hơn Thuật toán tìm tập xấp xỉ trong công trình [74] dựa trên độ phức tạp tính toán.
3. Dựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu của công trình [27], kết quả là, luận án đề xuất Thuật toán chọn tập đối tượng đại diện (Select a representative object set, Thuật toán 4.1 và Thuật toán 4.2) trong hệ thông tin và trong hệ quyết định giá trị tập từ tập đối tượng ban đầu cho bài toán tìm tập rút gọn. Và chứng minh tập rút gọn trên tập đối tượng ban đầu và tập rút gọn trên tập đối tượng đại diện là tương đương trên cả hệ thông tin và hệ quyết định giá trị tập, từ đó khẳng định tính đúng đắn của phương pháp. Các thuật toán chọn tập đối tượng đại diện có ý nghĩa quan trọng trong bước tiền xử lý số liệu của hệ quyết định trước khi thực hiện các nhiệm vụ khai phá dữ liệu.
Trong lý thuyết tập thông truyền thống, Skowron và Rauszer [52] đã đưa ra khái niệm ma trận phân biệt và hàm phân biệt để tìm tập rút gọn. Dựa trên cách tiếp cận này, luận án đề xuất hai cấu trúc dữ liệu mới là hàm phân biệt mở rộng và ma trận phân biệt mở rộng trong bảng quyết định giá trị tập. Hai cấu trúc dữ liệu mới này là công cụ để xây dựng thuật toán tìm tập rút gọn trên bảng quyết định giá trị tập. Kết quả là, luận án đề xuất ba thuật toán tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập mới là Thuật toán RGDSDT tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập, Thuật toán RSDTAAS và Thuật toán RSDTDAS lần lượt tìm tập rút gọn thuộc tính khi bổ sung và loại bỏ tập thuộc tính trong bảng quyết định giá trị tập, đồng thời luận án đánh giá độ phức tạp của từng thuật toán.
