Luận án Tiến sĩ: Phát triển phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ

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Ự NGUYỄN BÁ QUẢNG PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN FILTER-WRAPPER LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2021 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Ự NGUYỄN BÁ QUẢNG PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN FILTER-WRAPPER Chuyên 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. NGUYỄN LONG GIANG 2. NGÔ TRỌNG MẠI Hà Nội - 2021 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, các số liệu, kết quả nghiên cứu trong luận án này là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo được trích dẫn đầy đủ. Tác giả luận án Nguyễn Bá Quảng ii LỜI CÁM ƠN Tôi xin chân thành cám ơn Thủ trưởng Viện Khoa học và Công nghệ quân sự, Phòng Đào tạo, Viện Công nghệ thông tin và các đồng nghiệp đã luôn động viên, quan tâm, tạo điều kiện thuận lợi và giúp đỡ tôi trong quá trình học tập và nghiên cứu của mình.

Tôi xin bày tỏ sự biết ơn chân thành và sâu sắc đến PGS. TS Nguyễn Long Giang, TS Ngô Trọng Mại đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình nghiên cứu và hoàn thành bản luận án này. Tôi xin chân thành cám ơn các nhà khoa học của Viện Khoa học và Công nghệ quân sự, các nhà khoa học Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các nhà khoa học trong và ngoài quân đội đã giúp đỡ tôi hoàn thành luận án. Xin chân thành cám ơn gia đình và bạn bè đã luôn chia sẻ, động viên và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu.

iii MỤC LỤC Trang LỜI CAM ĐOAN. ii DANH MỤC CÁC KÝ HIỆU, CÁC 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.

TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI. Hệ thông tin và mô hình tập thô truyền thống. Hệ thông tin. Mô hình tập thô truyền thống.

Hệ thông tin không đầy đủ và mô hình tập thô dung sai. Hệ thông tin không đầy đủ. Mô hình tập thô dung sai. Bảng quyết định không đầy đủ.

Ma trận dung sai. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai. Tổng quan về rút gọn thuộc tính. Tiếp cận filter, wrapper trong rút gọn thuộc tính.

Rút gọn thuộc tính theo tiếp cận tập thô dung sai. Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô dung sai. Rút gọn thuộc tính theo tiếp cận tập thô dung sai. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai.

Kết luận chương 1. THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ. Xây dựng độ đo khoảng cách trong bảng quyết định không đầy đủ. Xây dựng độ đo khoảng cách giữa hai tập hợp.

Xây dựng độ đo khoảng cách giữa hai tập thuộc tính. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách. Xây dựng thuật toán filter tìm tập rút gọn của bảng quyết định không đầy đủ. Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ.

Thực nghiệm và đánh giá kết quả. Kết luận chương 2. CÁC THUẬT TOÁN GIA TĂNG FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH THAY ĐỔI. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập đối tượng.

Công thức cập nhật khoảng cách khi bổ sung tập đối tượng. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập đối tượng. Công thức cập nhật khoảng cách khi loại bỏ tập đối tượng. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập đối tượng.

Thực nghiệm và đánh giá các thuật toán. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập thuộc tính. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính.

Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập thuộc tính. Thực nghiệm và đánh giá các thuật toán. Kết luận chương 3 .108 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ .110 TÀI LIỆU THAM KHẢO .111 v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT C Số thuộc tính điều kiện trong bảng quyết định IDS  U , C  d  Bảng quyết định không đầy đủ IIS  U , A  Hệ thông tin không đầy đủ PX Tập xấp xỉ dưới của X đối với P PX Tập xấp xỉ trên của X đối với P POS P d  Miền dương của P đối với d SIM  P  Quan hệ dung sai trên tập thuộc tính P SP  u  Lớp dung sai chứa u của phủ U / SIM  P  SP  u  Lực lượng lớp dung sai S P  u  U Số đối tượng u a Giá trị của đối tượng u tại thuộc tính a U / SIM  P  Phủ của U trên P IDS_F_DAR Filter Distance based Attribute Reduction in Incomplete Decision Tables IDS_IFW_AA Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Add Attributes.

IDS_IFW_AO Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Add Objects. IDS_IFW_DA Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Delete Attributes. IDS_IFW_DO Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Delete Objects. IDS_FW_DAR Filter-Wrapper Distance based Attribute Reduction in Incomplete Decision Tables vi DANH MỤC CÁC BẢNG Trang Bảng 1.

Bảng quyết định không đầy đủ về các xe hơi. Các thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai. Các thuật toán gia tăng tính toán các tập xấp xỉ và tìm tập rút gọn theo tiếp cận tập thô truyền thống và các mô hình mở rộng. Các thuật toán gia tăng tính toán các tập xấp xỉ và tìm tập rút gọn theo tiếp cận tập thô dung sai.

Bảng quyết định của Ví dụ 2. Bộ dữ liệu thực nghiệm thuật toán IDS_FW_DAR. Thời gian thực hiện ba thuật toán (tính bằng giây). Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của ba thuật toán.

Bảng quyết định của Ví dụ 3. Bảng quyết định của Ví dụ 3. Bộ dữ liệu thử nghiệm thuật toán IDS_IFW_AO. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR (s).

Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của thuật toán IDS_IFW_AO và IDS_FW_DAR. Số lượng thuộc tính tập rút gọn và độ chính xác của thuật toán IDS_IFW_AO và IARM-I. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I (s). Thời gian thực hiện của 03 thuật toán (s).

Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của 03 thuật toán. Bộ dữ liệu thực nghiệm của thuật toán IDS_IFW_AA. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của thuật toán IDS_IFW_AA và UARA. Thời gian thực hiện của thuật toán IDS_IFW_AA và UARA (s) .105 vii DANH MỤC CÁC HÌNH VẼ Trang Hình 1.

Quy trình rút gọn thuộc tính. Cách tiếp cận filter và wrapper trong rút gọn thuộc tính. Mô hình phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai. Thời gian thực hiện ba thuật toán (tính bằng giây).

Số lượng thuộc tính tập rút gọn của ba thuật toán. Độ chính xác phân lớp của ba thuật toán. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR. Độ chính xác phân lớp của IDS_IFW_AO và IDS_FW_DAR.

Bộ số liệu Audiology. Bộ số liệu Soybean-large. Bộ số liệu Congressional Voting Records. Bộ số liệu Arrhythmia.

Bộ số liệu Anneal. Bộ số liệu Advertisements. Số lượng thuộc tính tập rút gọn và độ chính xác của thuật toán IDS_IFW_AO và IARM-I. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I.

Thời gian thực hiện của 03 thuật toán (s). Độ chính xác phân lớp của 03 thuật toán. Số thuộc tính tập rút gọn của 03 thuật toán. Tính cấp thiết của đề tài luận án Trong bối cảnh ngày nay, sự tăng trưởng không ngừng của dung lượng dữ liệu và số lượng các thuộc tính đã gây khó khăn, thách thức cho việc thực thi các thuật toán khai phá dữ liệu, phát hiện tri thức.

Rút gọn thuộc tính (còn gọi là rút gọn chiều, hay rút gọn đặc trưng) là bài toán quan trọng trong bước tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không cần thiết nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu. Hiện nay có hai cách tiếp cận chính đối với bài toán rút gọn thuộc tính [39-40]: filter (lọc) và wrapper (đóng gói). Cách tiếp cận filter thực hiện việc rút gọn thuộc tính độc lập với thuật khai phá dữ liệu sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc phân lớp dữ liệu.

Trong khi đó, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách áp dụng ngay thuật khai phá, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Lý thuyết tập thô (Rough set) do Pawlak đề xuất [113] được xem là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trong bảng quyết định đầy đủ, đã và đang được cộng đồng nghiên cứu về tập thô thực hiện lâu nay. Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị trên miền giá trị thuộc tính, gọi là bảng quyết định không đầy đủ. Ví dụ với bảng quyết định chẩn đoán bệnh viêm gan với các thuộc tính là các triệu chứng, các bác sĩ không thể thu thập đầy đủ các triệu chứng của tất cả các bệnh nhân để ra quyết định.

Để giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định không đầy đủ mà không qua bước tiền xử lý giá trị thiếu, Kryszkiewicz [67] mở rộng quan hệ tương đương trong lý thuyết tập thô truyền thống thành quan hệ dung sai và xây dựng mô hình tập thô dung sai (tolerance rough set).