Luận án Tiến sĩ Toán học: 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

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

Thêm vào BST

Báo xấu

25
lượt xem 4
download

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

Mục tiêu của Luận án là nghiên cứu các thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận kết hợp filter-wrapper nhằm giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác phân lớp so với các thuật toán đã công bố. Mời các bạn cùng tham khảo!

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: 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

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. PGS. TS. NGUYỄN LONG GIANG 2. TS. 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 .................................................................................................................................................i LỜI CÁM ƠN....................................................................................................................................................... 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 ............................................................................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI...............................................................................................................................10 1.1. Hệ thông tin và mô hình tập thô truyền thống............................................................ 10 1.1.1. Hệ thông tin ........................................................................................... 10 1.1.2. Mô hình tập thô truyền thống ................................................................ 11 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai........................................... 12 1.2.1. Hệ thông tin không đầy đủ .................................................................... 12 1.2.2. Mô hình tập thô dung sai ....................................................................... 12 1.2.3. Bảng quyết định không đầy đủ .............................................................. 14 1.2.4. Ma trận dung sai .................................................................................... 16 1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai ............................... 18 1.3.1. Tổng quan về rút gọn thuộc tính ............................................................ 18 1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính .................................. 19 1.3.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai ................................. 21 1.4. 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.... 24 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai ................................. 24 1.4.2. 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 ..................................................... 27 1.5. Kết luận chương 1 ......................................................................................................... 36 CHƯƠNG 2. THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ ................................................ 37 2.1. Xây dựng độ đo khoảng cách trong bảng quyết định không đầy đủ ....................... 38 2.1.1. Xây dựng độ đo khoảng cách giữa hai tập hợp ..................................... 39 2.1.2. Xây dựng độ đo khoảng cách giữa hai tập thuộc tính ........................... 40
iv 2.2. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách..... 42 2.2.1. 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 đủ ......................................................................................... 43 2.2.2. Đề 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 đủ ......................................................................................... 46 2.2.3. Thực nghiệm và đánh giá kết quả............................................................ 49 2.3. Kết luận chương 2 ......................................................................................................... 54 CHƯƠNG 3. 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 .......................................55 3.1. 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 ....................................................................................................................... 58 3.1.1. Công thức cập nhật khoảng cách khi bổ sung tập đối tượng ................. 58 3.1.2. 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 ............................................................................................... 62 3.1.3. Công thức cập nhật khoảng cách khi loại bỏ tập đối tượng .................. 67 3.1.4. 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 ......................................................................................... 70 3.1.5. Thực nghiệm và đánh giá các thuật toán ............................................... 74 3.2. 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....................................................................................................................... 92 3.2.1. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính ................ 92 3.2.2. 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 .............................................................................................. 93 3.2.3. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính .................. 97 3.2.4. 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 ........................................................................................ 98 3.2.5. Thực nghiệm và đánh giá các thuật toán ............................................. 101 3.3. Kết luận chương 3 ....................................................................................................... 106 KẾT LUẬN.......................................................................................................................................................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.1. Bảng quyết định không đầy đủ về các xe hơi ...........................................16 Bảng 1.2. 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 ..................................................................24 Bảng 1.3. 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....................28 Bảng 1.4. 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 ..................................................................33 Bảng 2.1. Bảng quyết định của Ví dụ 2.1 .................................................................45 Bảng 2.2. Bộ dữ liệu thực nghiệm thuật toán IDS_FW_DAR .................................50 Bảng 2.3. Thời gian thực hiện ba thuật toán (tính bằng giây) ..................................51 Bảng 2.4. 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..................................................................................................52 Bảng 3.1. Bảng quyết định của Ví dụ 3.1 .................................................................61 Bảng 3.2. Bảng quyết định của Ví dụ 3.2 .................................................................69 Bảng 3.3. Bộ dữ liệu thử nghiệm thuật toán IDS_IFW_AO.....................................75 Bảng 3.4. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR (s) .77 Bảng 3.5. 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 ...................................................80 Bảng 3.6. 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 .......................................................................82 Bảng 3.7. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I (s) ..........86 Bảng 3.8. Thời gian thực hiện của 03 thuật toán (s) .................................................89 Bảng 3.9. 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 .90 Bảng 3.10. Bộ dữ liệu thực nghiệm của thuật toán IDS_IFW_AA ........................102 Bảng 3.11. 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 ............................................................103 Bảng 3.12. 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.1. Quy trình rút gọn thuộc tính .....................................................................20 Hình 1.2. Cách tiếp cận filter và wrapper trong rút gọn thuộc tính ..........................21 Hình 1.3. 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 .22 Hình 2.1. Thời gian thực hiện ba thuật toán (tính bằng giây) ...................................51 Hình 2.2. Số lượng thuộc tính tập rút gọn của ba thuật toán ....................................53 Hình 2.3. Độ chính xác phân lớp của ba thuật toán ..................................................54 Hình 3.1. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR ....79 Hình 3.2. Độ chính xác phân lớp của IDS_IFW_AO và IDS_FW_DAR ................81 Hình 3.3.a. Bộ số liệu Audiology..............................................................................84 Hình 3.3.b. Bộ số liệu Soybean-large .......................................................................84 Hình 3.3.c. Bộ số liệu Congressional Voting Records..............................................84 Hình 3.3.d. Bộ số liệu Arrhythmia ............................................................................85 Hình 3.3.e. Bộ số liệu Anneal ...................................................................................85 Hình 3.3.f. Bộ số liệu Advertisements ......................................................................85 Hình 3.3. 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 ........................................................................85 Hình 3.4. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I ................88 Hình 3.5. Thời gian thực hiện của 03 thuật toán (s) .................................................89 Hình 3.6. Độ chính xác phân lớp của 03 thuật toán ..................................................91 Hình 3.7. Số thuộc tính tập rút gọn của 03 thuật toán...............................................91
1 MỞ ĐẦU 1. 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). Các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo
2 tiếp cận mô hình tập thô dung sai là các nghiên cứu mở rộng của các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống. Đây là các phương pháp heuristic bao gồm các bước: xây dựng độ đo, định nghĩa tập rút gọn và độ quan trọng của thuộc tính sử dụng độ đo được xây dựng, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn theo tiêu chuẩn là độ quan trọng của thuộc tính. Các nghiên cứu liên quan đến 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 tập trung vào các phương pháp chính như: các phương pháp sử dụng miền dương mở rộng [25], [51], [99], [114], [117], các phương pháp sử dụng ma trận phân biệt, hàm phân biệt mở rộng [29], [45], [47], [57], [77], [80], [116], các phương pháp sử dụng entropy thông tin mở rộng [26], [48-50], [64], [79], [107], các phương pháp sử dụng độ đo lượng thông tin [72], [91], [94], phương pháp sử dụng khoảng cách [62], [78] và một số phương pháp sử dụng các độ đo khác như quan hệ không phân biệt mở rộng [85], độ bao phủ của thuộc tính [93]. Nhìn chung, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô và tập thô dung sai đều hướng tới mục tiêu là tìm được tập rút gọn hiệu quả nhất để thực thi mô hình phân lớp dựa trên các tiêu chí: giảm thiểu số thuộc tính tập rút gọn để giảm thiểu độ phức tạp và nâng cao độ chính xác của mô hình. Các thuật toán đã đề xuất trong các phương pháp nêu trên đều là các thuật toán heuristic theo tiếp cận filter truyền thống, nghĩa là tập rút gọn thu được là tập thuộc tính tối thiểu bảo toàn độ đo được định nghĩa. Việc đánh giá độ chính xác của mô hình phân lớp được thực hiện sau khi tìm được tập rút gọn. Do đó, tập rút gọn của các thuật toán filter nêu trên chưa tối ưu về số lượng thuộc tính và độ chính xác phân lớp. Tại Việt Nam, đã có một số luận án tiến sĩ giải quyết bài toán rút gọn thuộc tính trong bảng quyết định theo tiếp cận mô hình tập thô truyền thống và các mô hình tập thô mở rộng của nhóm nghiên cứu của thầy hướng dẫn. Cụ
3 thể, luận án tiến sĩ [2] đề xuất các thuật toán gia tăng tìm tập rút gọn của bảng quyết định đầy đủ theo tiếp cận filter truyền thống. Luận án tiến sĩ [1] đề xuất các thuật toán rút gọn thuộc tính trong bảng quyết định không đầy đủ cố định. Trong luận án tiến sĩ [3], các tác giả đề xuất hướng tiếp cận kết hợp filter- wrapper tìm tập rút gọn của bảng quyết định đầy đủ dựa trên lý thuyết tập thô mờ (fuzzy rough set). Trong đó, giai đoạn filter tìm các ứng viên cho tập rút gọn dựa vào độ đo (còn gọi là tập rút gọn xấp xỉ), giai đoạn wrapper tính toán độ chính xác phân lớp của các ứng viên và lựa chọn tập rút gọn xấp xỉ có độ chính xác phân lớp cao nhất. Kết quả thử nghiệm cho thấy, số lượng thuộc tính tập rút gọn giảm thiểu đáng kể so với các phương pháp filter, trong khi độ chính xác phân lớp vẫn được bảo toàn và cải thiện hơn. Tuy nhiên, các phương pháp trong luận án [3] đều thực hiện trên bảng quyết định đầy đủ theo tiếp cận tập thô mờ (fuzzy rough set). Do đó, mục tiêu nghiên cứu thứ nhất của luận án là nghiên cứu hướng tiếp cận kết hợp filter-wrapper 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 nhằm giảm thiểu số lượng thuộc tính tập rút gọn, trong khi cố gắng bảo toàn, cải thiện độ chính xác mô hình phân lớp. Ngày nay, trong xu thế phát triển của dữ liệu lớn (Big data), các bảng quyết định ngày càng có kích thước lớn và luôn thay đổi, cập nhật. Việc áp dụng các thuật toán tìm tập rút gọn theo phương pháp truyền thống gặp nhiều thách thức. Với trường hợp bảng quyết định có kích thước lớn, việc thực hiện các thuật toán tìm tập rút gọn gặp khó khăn do hạn chế về không gian lưu trữ và tốc độ tính toán. Với trường hợp bảng quyết định thay đổi, cập nhật, các thuật toán này phải tính toán lại tập rút gọn trên toàn bộ bảng quyết định sau khi thay đổi, do đó chi phí về thời gian tính toán tăng lên đáng kể. Để vượt qua các thách thức trên, các nhà nghiên cứu đề xuất hướng tiếp cận tính toán gia tăng tìm tập rút gọn. Phương pháp gia tăng tìm tập rút gọn là kỹ thuật chỉ tính toán sự thay đổi của tập rút gọn trên phần dữ liệu bổ sung (hoặc loại bỏ)
4 chứ không tính lại tập rút gọn trên toàn bộ tập dữ liệu ban đầu. Do các thuật toán gia tăng chỉ cập nhật lại tập rút gọn trên phần dữ liệu bị thay đổi nên chúng giảm thiểu đáng kể thời gian thực hiện khi thực thi trên các bảng dữ liệu thay đổi, biến động. Hơn nữa, các thuật toán gia tăng có thể thực hiện được trên các bảng quyết định kích thước lớn bằng giải pháp chia nhỏ bảng quyết định thành nhiều phần, sau đó tập rút gọn được tính khi lần lượt bổ sung từng phần vào bảng quyết định. Hướng tiếp cận tính toán gia tăng tìm tập rút gọn đã và đang thu hút sự quan tâm của các nhà nghiên cứu trong suốt hơn hai thập kỷ qua. Theo tiếp cận tập thô truyền thống và các mô hình mở rộng, các nghiên cứu liên quan đến thuật toán gia tăng tìm tập rút gọn và tính toán các tập xấp xỉ của bảng quyết định thay đổi khá sôi động và phong phú. Các nghiên cứu liên quan đến các thuật toán gia tăng tìm tập rút gọn và tập trung vào các trường hợp: bổ sung và loại bỏ tập đối tượng [14], [20-21], [30], [33], [35], [37], [52], [55], [59], [70], [87], [89], [95-96], [100], [102], [106], [108], [110-112], bổ sung và loại bỏ tập thuộc tính [6], [19], [32], [53], [58], [60], [68], [76], [101], [104], tập đối tượng thay đổi giá trị [10], [66], [88], [90], [103], tập thuộc tính thay đổi giá trị [22], [31], [34], [36], [65]. Ngoài ra, một số công bố đề xuất các thuật toán gia tăng tính toán các tập xấp xỉ trong các trường hợp: bổ sung và loại bỏ tập đối tượng [12], [15], [43], [97], [105], [109], bổ sung và loại bỏ tập thuộc tính [7], [24], [73], [75], tập đối tượng thay đổi giá trị [44], tập thuộc tính thay đổi giá trị [11], [41], [74]. Theo tiếp cận tập thô dung sai, trong mấy năm gần đây các nghiên cứu liên quan đến 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 của bảng quyết định không đầy đủ khá sôi động và phong phú. Giống như tiếp cận tập thô truyền thống và các mô hình mở rộng được trình bày ở trên, các nghiên cứu liên quan chủ yếu tập trung vào trường hợp bổ sung, loại bỏ tập đối tượng [9], [13], [18], [23], [28], [38], [42], [46], [56], [71], [81-82], [86]. Ngoài ra, công bố [83] giải quyết bài
5 toán trong trường hợp bổ sung, loại bỏ tập thuộc tính; công bố [84] giải quyết bài toán trong trường hợp tập đối tượng thay đổi giá trị; công bố [92] giải quyết bài toán trong trường hợp tập thuộc tính thay đổi giá trị. Giống như các thuật toán tìm tập rút gọn trong bảng quyết định không đầy đủ đã trình bày ở trên, các thuật toán gia tăng tìm tập rút gọn trong các phương pháp nêu trên đều theo hướng tiếp cận filter truyền thống. Do đó, tập rút gọn tìm được chưa tối ưu cả về số lượng thuộc tính và độ chính xác phân lớp. Gần đây, các tác giả trong công trình [4] đề xuất thuật toán gia tăng tìm tập rút gọn theo tiếp cận kết hợp filter-wrapper. Tuy nhiên, thuật toán gia tăng trong [4] chỉ tìm tập rút gọn của bảng quyết định đầy đủ theo tiếp cận tập thô mờ trong trường hợp bổ sung tập đối tượng. Vì vậy, mục tiêu nghiên cứu thứ hai của luận án là nghiên cứu các thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận kết hợp filter-wrapper nhằm giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác phân lớp so với các thuật toán đã công bố. 2. Mục tiêu nghiên cứu Trên cơ sở phân tích các vấn đề còn tồn tại của các nghiên cứu liên quan, mục tiêu của luận án là: 1) Đề 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 đủ theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính tập rút gọn (từ đó giảm thiểu độ phức tạp của mô hình) và cải thiện độ chính xác của mô hình phân lớp. 2) Đề xuất 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 không đầy đủ thay đổi theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác của mô hình phân lớp so với các thuật toán gia tăng khác. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận án là bảng quyết định không đầy đủ, mô
6 hình tập thô dung sai, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai và các phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô dung sai. Phạm vi nghiên cứu của luận án là các 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 tập thô dung sai. 4. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 1) Nghiên cứu lý thuyết: Nghiên cứu các thuật toán rút gọn thuộc tính theo tiếp cận tập thô dung sai đã công bố, bao gồm các thuật toán trên bảng quyết định không thay đổi và các thuật toán gia tăng trên bảng quyết định thay đổi. Phân tích ưu điểm, nhược điểm và các vấn đề còn tồn tại của các thuật toán đã có. Trên cơ sở đó, đề xuất các độ đo cải tiến và các thuật toán theo hướng tiếp cận kết hợp filter-wrapper. Các đề xuất, cải tiến được chứng minh chặt chẽ về lý thuyết bởi các định lý, mệnh đề. 2) Nghiên cứu thực nghiệm: Các thuật toán đề xuất được cài đặt, chạy thử nghiệm, so sánh, đánh giá với các thuật toán khác trên các bộ số liệu mẫu từ kho dữ liệu UCI nhằm minh chứng về tính hiệu quả của các nghiên cứu về lý thuyết. 5. Nội dung nghiên cứu 1) Nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ dựa trên mô hình tập thô dung sai theo tiếp cận kết hợp filter-wrapper. 2) Nghiên cứu các phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định không đầy đủ thay đổi theo tiếp cận kết hợp filter-wrapper. Bảng
7 quyết định thay đổi trong trường hợp bổ sung, loại bỏ tập đối tượng, tập thuộc tính. 3) Cài đặt, thử nghiệm, so sánh, đánh giá các thuật toán đề xuất với các thuật toán khác đã công bố trên các bộ dữ liệu thử nghiệm từ kho dữ liệu UCI [118]. 6. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học: Đề xuất các thuật toán mới tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận kết hợp filter-wrapper trong trường hợp bảng quyết định cố định và bảng quyết định thay đổi. Cụ thể luận án có các kết quả chính như sau: 1) Xây dựng một độ đo khoảng cách mới và đề xuất thuật toán theo tiếp cận kết hợp filter-wrapper IDS_FW_DAR tìm tập rút gọn của bảng quyết định không đầy đủ sử dụng độ đo khoảng cách. Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI (UC Irvine Machine Learning Repository) [118] cho thấy, thuật thoán filter-wrapper IDS_FW_DAR giảm thiểu đáng kể số lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với các thuật toán filter khác. 2) Xây dựng các công thức gia tăng tính khoảng cách và đề xuất 04 thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ: (1) Thuật toán gia tăng filter-wrapper IDS_IFW_AO tìm tập rút gọn trong trường hợp bổ sung tập đối tượng; (2) Thuật toán filter-wrapper IDS_IFW_DO tìm tập rút gọn trong trường hợp loại bỏ tập đối tượng; (3) Thuật toán gia tăng filter-wrapper IDS_IFW_AA tìm tập rút gọn trong trường hợp bổ sung tập thuộc tính.
8 (4) Thuật toán gia tăng filter-wrapper IDS_IFW_DA tìm tập rút gọn trong trường hợp loại bỏ tập thuộc tính. Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [118] cho thấy, các thuật toán gia tăng filter-wrapper IDS_IFW_AO và IDS_IFW_AA giảm thiểu đáng kể số lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với các thuật toán gia tăng filter khác. Ý nghĩa thực tiễn Các thuật toán đề xuất có thể áp dụng để giải quyết bài toán rút gọn thuộc tính trong các ứng dụng thực tiễn nhằm loại bỏ các thuộc tính dư thừa, nâng cao hiệu quả các mô hình khai phá dữ liệu và học máy, đặc biệt là các hệ thống cơ sở dữ liệu không đầy đủ, thiếu giá trị trong các lĩnh vực chẩn đoán y tế, tài chính ngân hàng. 7. Bố cục của luận án Bố cục của luận án gồm phần mở đầu và ba chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô truyền thống, mô hình tập thô dung sai và tổng quan về tiếp cận filter-wrapper trong rút gọn thuộc tính. Chương 1 cũng trình bày 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, các nghiên cứu liên quan đến phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô dung sai trong mấy năm gần đây. Trên cơ sở đó, luận án phân tích các vấn đề còn tồn tại và nêu rõ các mục tiêu nghiên cứu cùng với tóm tắt các kết quả đạt được. Các đóng góp chính của luận án được trình bày trong chương 2, chương 3. Chương 2 trình bày kết quả nghiên cứu về xây dựng độ đo khoảng cách mới. Sử dụng độ đo khoảng cách mới, chương 2 đề xuất thuật toán IDS_F_DAR tìm tập rút gọn theo tiếp cận filter và thuật toán IDS_FW_DAR tìm tập rút gọn
9 theo tiếp cận kết hợp filter-wrapper. Các thuật toán trên thực hiện trên bảng quyết định không đầy đủ cố định. Chương 3 xây dựng các công thức gia tăng tính độ đo khoảng cách và đề xuất bốn thuật toán gia tăng filter-wrapper tìm tập rút gọn trong bảng quyết định thay đổi, cụ thể là: 1) Thuật toán IDS_IFW_AO tìm tập rút gọn trong trường hợp bổ sung tập đối tượng; 2) Thuật toán IDS_IFW_DO tìm tập rút gọn trong trường hợp loại bỏ tập đối tượng; 3) Thuật toán IDS_IFW_AA tìm tập rút gọn trong trường hợp bổ sung tập thuộc tính; 4) Thuật toán IDS_IFW_DA tìm tập rút gọn trong trường hợp loại bỏ tập thuộc tính. Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của tác giả.
10 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI 1.1. Hệ thông tin và mô hình tập thô truyền thống Lý thuyết tập thô truyền thống do Z.Pawlak [113] đề xuất là công cụ toán học hiệu quả để biểu diễn và xử lý các khái niệm không chắc chắn. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ tương đương (hay quan hệ không phân biệt được) để xấp xỉ tập hợp. Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó. Mỗi tập xấp xỉ được hợp thành bởi một hoặc nhiều lớp tương đương, là cơ sở để xây dựng các thuật toán rút gọn thuộc tính và khai phá tri thức từ dữ liệu. Trong phần này, luận án trình bày một số khái niệm cơ bản trong lý thuyết tập thô truyền thống của Z.Pawlak [113], là cơ sở nền tảng cho mô hình tập thô dung sai được trình bày ở phần 1.2. 1.1.1. Hệ thông tin Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm n cột ứng với n thuộc tính và m hàng ứng với m đối tượng. Một cách hình thức, hệ thông tin là một cặp IS  U , A trong đó U là tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính. Mỗi thuộc tính a  A xác định một ánh xạ: a : U  Va với Va là tập giá trị của thuộc tính a A . Xét hệ thông tin IS  U , A . Mỗi tập con các thuộc tính P  A xác định một quan hệ hai ngôi trên U, ký hiệu là IND  P  , xác định bởi   IND  P    u, v  U U a  P, a  u   a  v  . IND  P  là quan hệ P-không phân biệt được. Dễ thấy rằng IND  P  là một quan hệ tương đương trên U. Nếu  u, v   IND  P  thì hai đối tượng u và v
11 không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND  P  xác định một phân hoạch trên U, ký hiệu là U / IND  P  hay U / P . Ký hiệu lớp tương đương trong phân hoạch U / P chứa đối tượng u là  u P , khi đó u P  v U  u, v   IND  P  . 1.1.2. Mô hình tập thô truyền thống Cho hệ thông tin IS  U , A và tập đối tượng X  U . Với một tập thuộc tính B  A cho trước, chúng ta biểu diễn X thông qua các lớp tương đương của U / B (còn gọi là biểu diễn X bằng tri thức có sẵn B), người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương đương của U / B . Có hai cách xấp xỉ tập đối tượng X thông qua tập thuộc tính B , được gọi là B-xấp xỉ dưới và B- xấp xỉ trên của X, ký hiệu là lượt là BX và BX , được xác định như sau:    BX  u U u B  X , BX  u U u B  X   .  Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập BX bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập BN B  X   BX  BX : B-miền biên của X , U  BX : B-miền ngoài của X. B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể viết lại BX  Y U / B Y  X  , BX  Y U / B Y  X  . Trong trường hợp BN B  X    thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô (rough set).