Luận án Tiến sĩ Máy tính: Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi theo tiếp cận tập thô mờ

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

Thêm vào BST

Báo xấu

43
lượt xem 5
download

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

Mục tiêu nghiên cứu của Luận án nhằm đề 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 thay đổi dựa trên tập thô mờ 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 của mô hình phân lớp, từ đó giảm thiểu độ phức tạp của mô hình khai phá dữ liệu 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ĩ Máy tính: Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi theo tiếp cận tập thô mờ

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- HỒ THỊ PHƯỢNG PHƯƠNG PHÁP GIA TĂNG RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI THEO TIẾP CẬN TẬP THÔ MỜ LUẬN ÁN TIẾN SĨ MÁY TÍNH HÀ NỘI - 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- HỒ THỊ PHƯỢNG PHƯƠNG PHÁP GIA TĂNG RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI THEO TIẾP CẬN TẬP THÔ MỜ Chuyên ngành : Khoa học máy tính Mã số : 9 48 01 01 LUẬN ÁN TIẾN SĨ MÁY TÍNH Người hướng dẫn khoa học: PGS.TS. Nguyễn Long Giang HÀ NỘI - 2021
LỜI CẢM ƠN Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự giúp đỡ hết mình từ các thầy giáo hướng dẫn, bạn bè và người thân. Đầu tiên, tác giả xin bày tỏ lời tri ân tới PGS.TS Nguyễn Long Giang, Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam người thầy đã tận tình hướng dẫn tác giả hoàn thành luận án này. Tác giả xin gửi lời cảm ơn sâu sắc đến thầy cô, bạn bè công tác tại Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã nhiệt tình giúp đỡ và tạo ra môi trường nghiên cứu tốt để tác giả hoàn thành công trình của mình; cảm ơn các thầy cô và các đồng nghiệp ở các nơi mà tác giả tham gia viết bài đã có những góp ý chính xác để tác giả có được những công bố như ngày hôm nay. Cảm ơn Học Viện Khoa học và Công nghệ Việt Nam đã tạo mọi điều kiện thuận lợi để tác giả hoàn thành Luận án này. Tác giả xin gửi lời cảm ơn tới Đảng ủy, Ban Giám hiệu trường Đại học Tây Nguyên nơi tác giả công tác đã ủng hộ và tạo mọi điều kiện để tác giả hoàn thành luận án đúng thời hạn. Cuối cùng, tác giả xin gửi tới bạn bè, người thân lời cảm ơn chân thành nhất vì đã đồng hành cùng tác giả trong suốt thời gian qua. Con xin cảm ơn Cha, Mẹ và gia đình đã luôn là chỗ dựa vững chắc về tinh thần và vật chất, cũng là những người luôn mong mỏi cho con thành công; cảm ơn chồng và các anh chị em đã gánh vác công việc gia đình thay cho em; xin lỗi các con vì phần nào đó đã chịu thiệt thòi trong thời gian mẹ học tập nghiên cứu, chính các con là nguồn động lực lớn lao giúp mẹ hoàn thành được công việc khó khăn này. Hà Nội, tháng 01 năm 2021 Hồ Thị Phượng
LỜI CAM ĐOAN Các kết quả trình bày trong luận án là công trình nghiên cứu của tôi được hoàn thành dưới sự hướng dẫn của PGS.TS. Nguyễn Long Giang. Những kết quả trình bày là mới và chưa từng được công bố ở các công trình của người khác. Tôi xin chịu trách nhiệm về những lời cam đoan của mình. Hà Nội, Ngày….tháng ….năm 2021 Nghiên cứu sinh Hồ Thị Phượng
i MỤC LỤC MỞ ĐẦU ........................................................................................................................................ 1 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TẬP THÔ MỜ........................................................................................................................................ 8 1.1. Tổng quan về rút gọn thuộc tính...............................................................................8 1.2. Các hướng tiếp cận filter-wrapper trong rút gọn thuộc tính ...................................10 1.3. Tổng quan về tập thô mờ ........................................................................................11 1.3.1. Bảng quyết định và quan hệ tương đương............................................................... 12 1.3.2. Quan hệ tương đương mờ ......................................................................................... 12 1.3.3. Ma trận tương đương mờ .......................................................................................... 14 1.3.4. Phân hoạch mờ ........................................................................................................... 14 1.4. Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô mờ ...........17 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô mờ............................................................ 17 1.4.2. Phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô mờ....................... 19 1.5. Tóm tắt các đóng góp của luận án ..........................................................................23 1.6. Kết luận chương 1 ..................................................................................................24 CHƯƠNG 2. THUẬT TOÁN FIFTER-WRAPPER RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG KHOẢNG CÁCH MỜ ................. 25 2.1. Mở đầu ....................................................................................................................25 2.2. Xây dựng khoảng cách giữa hai tập mờ .................................................................26 2.2.1. Độ đo khoảng cách mờ.............................................................................................. 27 2.2.2. Độ đo khoảng cách mờ và các tính chất .................................................................. 27 2.3. Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ ....................................30 2.4. Thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách mờ ......................36 2.5. Thực nghiệm và đánh giá kết quả các thuật toán ...................................................37 2.5.1. Mục tiêu thực nghiệm................................................................................................ 37 2.5.2. Số liệu, phương pháp và môi trường thực nghiệm ................................................. 38 2.5.3. Kết quả so sánh độ chính xác phân lớp và số lượng thuộc tính tập rút gọn ......................................................................................................................... 39 2.5.4. Kết quả so sánh thời gian thực hiện ......................................................................... 41 2.6. Kết luận Chương 2..................................................................................................42
ii CHƯƠNG 3. THUẬT TOÁN GIA TĂNG FIFTER-WRAPPER TÌM TẬP RÚT GỌN KHI BỔ SUNG, LOẠI BỎ TẬP ĐỐI TƯỢNG ............................................. 44 3.1. Mở đầu ....................................................................................................................44 3.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn bổ sung tập đối tượng .............47 3.2.1. Công thức gia tăng để tính khoảng cách mờ khi bổ sung một đối tượng............. 47 3.2.2. Công thức gia tăng tính khoảng cách mờ khi bổ sung tập đối tượng ................... 50 3.3. Thuật toán gia tăng fifter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng...........71 3.4. Kết luận Chương 3..................................................................................................88 CHƯƠNG 4. THUẬT TOÁN GIA TĂNG FIFTER-WRAPPER TÌM TẬP RÚT GỌN KHI BỔ SUNG, LOẠI BỎ TẬP THUỘC TÍNH .......................................... 90 4.1. Mở đầu ....................................................................................................................90 4.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính..............93 4.2.1. Công thức gia tăng cập nhật khoảng cách khi bổ sung tập thuộc tính .................. 93 4.2.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính ................................................................................................................. 94 4.2.3. Thực nghiệm và đánh giá thuật toán ........................................................................ 97 4.3. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi loại bỏ tập thuộc tính .............106 4.3.1. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính ................................ 106 4.3.2. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập thuộc tính ................................................................................................................. 106 4.4. Kết luận Chương 4................................................................................................108 KẾT LUẬN ............................................................................................................................... 110 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ .................................................................. 111 TÀI LIỆU THAM KHẢO...................................................................................................... 112
iii DANH MỤC CÁC THUẬT NGỮ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Tập thô Rough Set Tập thô mờ Fuzzy Rough Set Hệ thông tin Information System Bảng quyết định Decision Tables Bảng quyết định mờ Fuzzy Decision Tables Quan hệ tương đương Equivalence Relation Quan hệ tương đương mờ Fuzzy Equivalence Relation Phân hoạch mờ Fuzzy Partition Ma trận tương đương mờ Fuzzy Equivalence Matrix Lớp tương đương mờ Fuzzy equivalence Classes Xấp xỉ dưới mờ Fuzzy Lower Approximation Xấp xỉ trên mờ Fuzzy Upper Approximation Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Phương pháp gia tăng Incremental Methods Khoảng cách mờ Fuzzy Distance Hàm thuộc mờ Fuzzy Dependency Function Lọc Filter Đóng gói Wrapper
iv BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT Ký hiệu, từ viết tắt Diễn giải DS  U , C  D  Bảng quyết định U Số đối tượng C Số thuộc tính điều kiện trong bảng quyết định u a Giá trị của đối tượng u tại thuộc tính a IND  B  Quan hệ tương đương trên B U/P Phân hoạch của U trên P  u B Lớp tương đương chứa u của phân hoạch U / P Ra Quan hệ tương đương mờ R . RP Quan hệ tương đương mờ 𝑅̃ trên tập thuộc tính P M ( RP ) Ma trận tương đương mờ của 𝑅̃𝑃 Φ RP  Phân hoạch mờ trên 𝑅̃𝑃 Lớp tương đương mờ của xi thuộc phân hoạch mờ Φ  RP   xi P  xi P Lực lượng lớp tương đương mờ  xi P PX Tập xấp xỉ dưới mờ của X đối với RP PX Tập xấp xỉ trên mờ của X đối với RP      FPD Φ RP ,Φ RQ Khoảng cách mờ giữa hai phân hoạch mờ Φ  RP  và Φ  RQ 
v DANH MỤC CÁC BẢNG Bảng 1.1 Bảng quyết định của Ví dụ 1.1 ......................................................................16 Bảng 1.2 Liệt kê các nghiên cứu liên quan đến các thuật toán heuristic tìm tập rút gọn của bảng quyết định theo tiếp cận tập thô mờ. ..............................................................18 Bảng 1.3 Liệt kê các nghiên cứu liên quan đến các thuật toán gia tăng tìm tập rút gọn của bảng quyết định theo tiếp cận tập thô mờ. ..............................................................21 Bảng 2.1 Bảng quyết định của Ví dụ 2.2 ......................................................................33 Bảng 2.2 Bộ dữ liệu thử nghiệm thuật toán FW_FDBAR ............................................38 Bảng 2.3 Độ chính xác phân lớp và số lượng thuộc tính tập rút gọn............................39 Bảng 2.4 Thời gian thực hiện FW_FDBAR, FEBAR, FPDAR ...................................41 Bảng 3.1 Bảng quyết định của Ví dụ 3.1 ......................................................................48 Bảng 3.2 Bảng quyết định sau khi thêm đối tượng u4 của Ví dụ 3.1 ............................49 Bảng 3.3 Bảng quyết định của Ví dụ 3.2 ......................................................................51 Bảng 3.4 Bảng quyết định của Ví dụ 3.2 sau khi thêm tập đối tượng ..........................52 Bảng 3.5 Bộ dữ liệu thử nghiệm khi thêm tập đối tượng .............................................59 Bảng 3.6 Thời gian thực hiện của các thuật toán IFW_FDAR_AdObj, IV-FS-FRS-2 IARM, ASS-IAR và IFSA (tính bằng giây) ..................................................................60 Bảng 3.7 Độ chính xác phân lớp và số lượng thuộc tính tập rút gọn của các thuật toán IFW_FDAR_AdObj, IV-FS-FRS-2, IARM, ASS-IAR và IFSA ..................................65 Bảng 3.8 Bảng quyết định của Ví dụ 3.3 ......................................................................72 Bảng 3.9 Bảng quyết định sau khi loại bỏ 1 đối tượng của Ví dụ 3.3 ..........................74 Bảng 3.10 Bảng quyết định của Ví dụ 3.4 ....................................................................76 Bảng 3.11 Bảng quyết định sau khi loại bỏ tập đối tượng của Ví dụ 3.4 .....................78 Bảng 3.12 Mô tả dữ liệu khi loại bỏ tập đối tượng .......................................................83 Bảng 3.13 Thời gian thực hiện của thuật toán IFW_FDAR_DelObj và IFSD .............84 Bảng 3.14 Độ chính xác phân lớp của thuật toán IFW_FDAR_DelObj và IFSD .......86 Bảng 4.1 Bộ dữ liệu thử nghiệm ...................................................................................98 Bảng 4.2 Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của IFW_FDAR_AA và FRSA-IFS-HIS(AA) ....................................................................99 Bảng 4.3 Thời gian thực hiện của IFW_FDAR_AA và FRSA-IFS-HIS(AA) ...........103
vi DANH SÁCH CÁC HÌNH VẼ Hình 1.1 Quy trình rút gọn thuộc tính .........................................................................10 Hình 1.2 Cách tiếp cận filter và wrapper trong rút gọn thuộc tính ..............................11 Hình 2.1 Độ chính xác phân lớp của ba thuật toán ......................................................40 Hình 2.2 Số lượng thuộc tính tập rút gọn của ba thuật toán .........................................41 Hình 2.3 Thời gian thực thiện của ba thuật toán...........................................................42 Hình 3.1 Thời gian thực hiện các thuật toán IFW_FDAR_AdObj, IV-FS-FRS-2 IARM, ASS-IAR và IFSA .............................................................................................64 Hình 3.2 Số lượng thuộc tính tập rút gọn của các thuật toán IFW_FDAR_AdObj, IV- FS-FRS-2 IARM, ASS-IAR và IFSA ...........................................................................71 Hình 3.3 Thời gian thực hiện các thuật toán IFW_FDAR_DelObj và IFSD ...............86 Hình 3.4 Số lượng thuộc tính tập rút gọn của các thuật toán IFW_FDAR_DelObj và IFSD...............................................................................................................................88 Hình 4.1 Độ chính xác phân lớp của các thuật toán IFW_FDAR_AA và FRSA-IFS- HIS(AA) ......................................................................................................................103 Hình 4.2 Thời gian thực hiện của thuật toán IFW_FDAR_AA và FRSA-IFS- HIS(AA) ......................................................................................................................105
1 MỞ ĐẦU 1. Tính cấp thiết Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu của quá trình khai phá tri thức từ dữ liệu. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa, không cần thiết nhằm nâng cao tính hiệu quả của các mô hình khai phá dữ liệu. Rút gọn thuộc tính của bảng quyết định là quá trình lựa chọn tập con nhỏ nhất của tập thuộc tính điều kiện, loại bỏ các thuộc tính dư thừa mà bảo toàn thông tin phân lớp của bảng quyết định, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Cho đến nay, có hai hướng tiếp cận chính đối với bài toán lựa chọn thuộc tính: Lọc (filter) và đóng gói (wrapper). Cách tiếp cận fifter thực hiện việc lựa chọn thuộc tính độc lập với thuật toán khai phá sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc mô tả dữ liệu. Trong khi đó, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách áp dụng ngay thuật khai phá, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Lý thuyết tập thô mờ (fuzzy rough set) do Dübois và các cộng sự [1] đề xuất là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định gốc không qua bước tiền xử lý dữ liệu nhằm nâng cao hiệu quả độ chính xác mô hình phân lớp. Cho đến nay, nhiều phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ đã được đề xuất, điển hình là các phương pháp sử dụng hàm thuộc mờ [2, 3, 4], các phương pháp sử dụng miền dương mờ [5, 6], các phương pháp sử dụng entropy mờ [7, 8, 9], các phương pháp sử dụng khoảng cách mờ [10, 11, 12] và một số phương pháp khác [13, 14, 15, 16, 17, 18]. Trong xu thế dữ liệu lớn (Big data) hiện nay, các bảng quyết định ngày càng có số thuộc tính rất lớn, ví dụ các bảng dữ liệu trong lĩnh vực tin sinh học có hàng triệu thuộc tính. Hơn nữa, các bảng quyết định luôn luôn thay đổi, cập nhật với các tình huống như bổ sung và loại bỏ tập đối tượng, bổ sung và loại bỏ tập thuộc tính, giá trị tập đối tượng, tập thuộc tính thay đổi. Để xây dựng mô hình phân lớp hiệu quả, ta cần giải quyết bài toán rút gọn thuộc tính trên các bảng quyết định kích thước lớn và thay đổi. Các phương pháp rút gọn thuộc tính theo tiếp cận truyền thống trên các bảng quyết định như vậy gặp hai thách thức. Thứ nhất, với các bả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 gọn gặp khó
2 khăn về không gian lưu trữ và tốc độ tính toán. Thứ hai, với các bảng quyết định thay đổi, cập nhật, các thuật toán này phải tính toán lại tập rút gọn trên toàn bộ bảng quyết định sau khi thay đổi, do đó chi phí về thời gian tính toán tăng lên đáng kể. Để giải quyết hai thách thức trên, các nhà nghiên cứu đề xuất hướng tiếp cận tính toán gia tăng tìm tập rút gọn. Các thuật toán gia tăng chỉ cập nhật lại tập rút gọn trên phần dữ liệu bị thay đổi mà không tính lại tập rút gọn trên toàn bộ bảng quyết định ban đầu. Do đó, chúng giảm thiểu đáng kể thời gian thực hiện. Hơn nữa, các thuật toán gia tăng có thể thực hiện được trên các bảng quyết định kích thước lớn bằng giải pháp chia nhỏ bảng quyết định thành nhiều phần, tập rút gọn được tính khi lần lượt bổ sung từng phần. Hướng tiếp cận tính toán gia tăng tìm tập rút gọn của bảng quyết định đã và đang thu hút sự quan tâm của các nhà nghiên cứu trong suốt hơn thập kỷ qua. Theo tiếp cận lý thuyết tập thô truyền thống của Pawlak [19] và các mô hình tập thô mở rộng, các nhà nghiên cứu đã đề xuất nhiều thuật toán gia tăng tìm tập rút gọn của bảng quyết định thay đổi. Với trường hợp bổ sung, loại bỏ tập đối tượng, một số thuật toán gia tăng đề xuất sử dụng khoảng cách [20, 21], hạt thông tin [22, 23, 24, 25, 26, 27], ma trận phân biệt [28, 29, 30, 31, 32], miền dương [33, 34, 35], hàm thuộc [36], quan hệ không phân biệt được [37], entropy thông tin [38], độ đo không nhất quán [39], lựa chọn mẫu kích hoạt [40]. Với trường hợp bổ sung, loại bỏ tập thuộc tính, một số thuật toán gia tăng tìm tập rút gọn đã được đề xuất sử dụng miền dương [41], entropy thông tin [42], ma trận phân biệt [43, 44, 45], quan hệ không phân biệt [46, 47], khoảng cách [48], độ phụ thuộc của thuộc tính [49], hạt tri thức [50, 51]. Theo tiếp cận tập thô mờ [1], trong mấy năm gần đây một số thuật toán gia tăng tìm tập rút gọn của bảng quyết định đã được đề xuất với các trường hợp: bổ sung và loại bỏ tập đối tượng [52, 53, 54, 56, 57], bổ sung và loại bỏ tập thuộc tính [58]. Với trường hợp bổ sung, loại bỏ tập đối tượng, Liu và các cộng sự [52] xây dựng công thức gia tăng tính độ phụ thuộc mờ và đề xuất thuật toán giăng FIAT tìm tập rút gọn khi bổ sung tập đối tượng. Yang và các cộng sự [53] xây dựng công thức gia tăng tính quan hệ phân biệt, trên cơ sở đó xây dựng thuật toán gia tăng IARM tìm tập rút gọn khi bổ sung tập đối tượng. Yang và các cộng sự [54] xây dựng cơ chế cập nhật quan hệ phân biệt và đề xuất hai thuật toán IV-FS-FRS-1 và IV-FS-FRS-2 tìm tập rút gọn trong trường hợp bổ sung tập đối tượng. Zhang và các cộng sự [56] đề xuất thuật toán gia
3 tăng AIFWAR tìm tập rút gọn sử dụng entropy có điều kiện mở rộng trong trường hợp bổ sung tập đối tượng. Ni và các cộng sự [57] đưa ra khái niệm tập đối tượng chính (key instance set), trên cơ sở đó xây dựng hai thuật toán gia tăng tìm tập rút gọn dựa trên tập đối tượng chính trong trường hợp bổ sung tập đối tượng: thuật toán DIAR sử dụng hàm thuộc mờ và thuật toán PIAR sử dụng miền dương mờ. Với trường hợp bổ sung, loại bỏ tập thuộc tính, các kết quả nghiên cứu về các thuật toán gia tăng tìm tập rút gọn theo tiếp cận tập thô mờ còn hạn chế. Zeng và các cộng sự [58] xây dựng các công thức gia tăng cập nhật độ phụ thuộc mờ trong hệ thông tin hỗn hợp (HIS), trên cơ sở đó đề xuất hai thuật toán gia tăng cập nhật tập rút gọn sử dụng độ phụ thuộc mờ: thuật toán FRSA-IFS-HIS(AA) trong trường hợp bổ sung tập thuộc tính và thuật toán FRSA-IFS-HIS(AD) trong trường hợp loại bỏ tập thuộc tính. Kết quả thực nghiệm trong các công trình nêu trên cho thấy, các thuật toán gia tăng giảm thiểu đáng kể thời gian thực hiện so với các thuật toán không gia tăng. Do đó, chúng có thể thực thi hiệu quả trên các bảng quyết định có kích thước lớn và thay đổi, cập nhật. Tuy nhiên, phần lớn các thuật toán đề xuất đều theo hướng tiếp cận lọc (filter) truyền thống. Với cách tiếp cận này, tập rút gọn tìm được là tập thuộc tính tối thiểu bảo toàn độ đo được xây dựng. Việc đánh giá độ chính xác phân lớp được thực hiện sau khi tìm được tập rút gọn. Vì vậy, tập rút gọn thu được chưa phải là lựa chọn tốt nhất trên hai tiêu chí: số lượng thuộc tính tập rút gọn và độ chính xác phân lớp. Do đó, động lực nghiên cứu của luận án là nghiên cứu, đề xuất các thuật toán gia tăng theo tiếp cận kết hợp filter- wrapper nhằm mục tiêu giảm thiểu số 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. 2. Mục tiêu nghiên cứu Nghiên cứu, đề xuất các thuật toán gia tăng tìm tập rút gọn của bảng quyết định thay đổi dựa trên tập thô mờ 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 của mô hình phân lớp, từ đó giảm thiểu độ phức tạp của mô hình khai phá dữ liệu. Với mục tiêu đặt ra, luận án đã thu được các kết quả chính như sau: 1) Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định sử dụng độ đo khoảng cách mờ. Đóng góp này được trình bày ở Chương 2 của luận án.
4 2) Đề xuất hai thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định thay đổi trong trường hợp bổ sung, loại bỏ tập đối tượng. Đóng góp này được trình bày ở Chương 3 của luận án. 3) Đề xuất hai thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định thay đổi trong trường hợp bổ sung, loại bỏ tập thuộc tính. Đóng góp này được trình bày ở Chương 4 của luận án. 3. Đối tượng nghiên cứu của luận án: - Tập thô mờ và các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ - Bảng quyết định thay đổi trong trường hợp bổ sung, loại bỏ tập đối tượng, tập thuộc tính. - Các độ đo được sử dụng trong lý thuyết tập thô mờ, tập trung vào độ đo khoảng cách mờ. 4. Phạm vi nghiên cứu Về lý thuyết: Nghiên cứu các thuật toán heuristic tìm tập rút gọn của bảng quyết định thay đổi (bổ sung, loại bỏ tập đối tượng; bổ sung, loại bỏ tập thuộc tính) sử dụng các độ đo trong tập thô mờ. Về thử nghiệm: Thử nghiệm, so sánh, đánh giá các thuật toán đề xuất với các thuật toán đã công bố trên các bộ dữ liệu mẫu từ kho dữ liệu UCI [59] nhằm đánh giá tính hiệu quả của các thuật toán đề xuất theo các mục tiêu đặt ra. 5. Phương pháp nghiên cứu Nghiên cứu lý thuyết: Tổng hợp các nghiên cứu liên quan về các phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô mờ, trên cơ sở đó phân tích, đánh giá các vấn đề còn tồn tại và xây dựng các đề xuất cải tiến: Cải tiến về độ chính xác mô hình phân lớp và cải tiến về số lượng thuộc tính tập rút gọn, từ đó giảm độ phức tạp của mô hình. Nghiên cứu thực nghiệm: Các thuật toán đề xuất được cài đặt, chạy thử nghiệm, so sánh, đánh giá 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 [59] nhằm minh chứng về tính hiệu quả của các nghiên cứu về lý thuyết.
5 6. Nội dung nghiên cứu 1) Nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định dựa trên mô hình tập thô mờ theo tiếp cận kết hợp filter-wrapper. 2) Nghiên cứu các phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi theo tiếp cận kết hợp filter-wrapper. Bảng quyết định thay đổi trong trường hợp bổ sung, loại bỏ tập đối tượng; bổ sung, loại bỏ tập thuộc tính. 3) Cài đặt, thử nghiệm, so sánh, đánh giá các thuật toán đề xuất với các thuật toán khác đã công bố trên các bộ dữ liệu thử nghiệm từ kho dữ liệu UCI [59]. 7. Ý 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 gọn của bảng quyết định theo tiếp cận kết hợp filter-wrapper trong trường hợp bảng quyết định thay đổi. Cụ thể luận án có các kết quả chính như sau: 1) Xây dựng một độ đo khoảng cách mờ và đề xuất thuật toán theo tiếp cận kết hợp filter-wrapper FW_FDBAR tìm tập rút gọn của bảng quyết định sử dụng độ đo khoảng cách mờ. Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [59] cho thấy, thuật thoán filter-wrapper FW_FDBAR giảm thiểu đáng kể số lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với các thuật toán filter truyền thống khác. 2) Xây dựng các công thức gia tăng tính khoảng cách và đề xuất 04 thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định : a. Thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj tìm tập rút gọn trong trường hợp bổ sung tập đối tượng. b. Thuật toán gia tăng filter-wrapper IFW_FDAR_DelObj tìm tập rút gọn trong trường hợp loại bỏ tập đối tượng. c. Thuật toán gia tăng filter-wrapper IFW_FDAR_AA tìm tập rút gọn trong trường hợp bổ sung tập thuộc tính. d. Thuật toán gia tăng filter-wrapper IFW_FDAR_DA tìm tập rút gọn trong trường hợp loại bỏ tập thuộc tính.
6 Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [59] cho thấy, bốn thuật toán đề xuất đều theo tiếp cận kết hợp filter-wrapper, trong đó giai đoạn filter tìm các ứng viên cho tập rút gọn (là các tập thuộc tính bảo toàn độ đo sử dụng), giai đoạn wrapper tìm tập rút gọn có độ chính xác phân lớp cao nhất. Bốn thuật toán đề xuất đều giảm thiểu số thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với các thuật toán được so sánh. Ý nghĩa thực tiễn Các thuật toán đề xuất có thể áp dụng để giải quyết bài toán rút gọn thuộc tính trong các ứng dụng thực tiễn nhằm loại bỏ các thuộc tính dư thừa, nâng cao hiệu quả các mô hình khai phá dữ liệu và học máy, đặc biệt là trong các hệ thống cơ sở dữ liệu trong các lĩnh vực chẩn đoán y tế, tài chính ngân hàng,... 8. Bố cục của luận án Bố cục của luận án gồm: phần mở đầu và bốn chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Cụ thể như sau: Chương 1 trình bày một số khái niệm cơ bản gồm: tổng quan về rút gọn thuộc tính và về cách tiếp cận filter-wrapper trong rút gọ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 gọn thuộc tính theo tiếp cận tập thô mờ, các nghiên cứu liên quan đến phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô mờ 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 tạ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 quả đạt được. Các kiến thức cơ bản này được sử dụng trong các chương sau, là các đóng góp chính của luận án. Các đóng góp chính của luận án được trình bày trong Chương 2, Chương 3 và Chương 4. Chương 2 trình bày kết quả nghiên cứu về xây dựng độ đo khoảng cách mờ và đề xuất thuật toán kết hợp filter-wrapper FW_FDBAR tìm tập rút gọn của bảng quyết định. Chương 3 và Chương 4 đề xuất các công thức gia tính khoảng cách mờ và vận dụng các khoảng cách này để xây dựng 4 thuật toán gia tăng filter-wrapper; thuật toán gia tăng filter-wrapper thứ nhất tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung tập đối tượng; thuật toán gia tăng filter-wrapper thứ hai tìm tập rút gọn của bảng quyết định trong trường hợp loại bỏ tập đối tượng; thuật toán gia tăng filter-
7 wrapper thứ ba tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung tập thuộc tính; thuật toán gia tăng filter-wrapper thứ bốn tìm tập rút gọn của bảng quyết định trong trường hợp loại bỏ tập thuộc tính. Cả bốn thuật toán đề xuất đều sử dụng độ đo khoảng cách mờ đề xuất ở Chương 2 và đều có mục tiêu là giảm thiểu thời gian thực hiện so với thuật toán không gia tăng, nâng cao độ chính xác phân lớp và tối thiểu hóa số lượng thuộc tính tập rút gọn so với các thuật toán gia tăng khác đã công bố. Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của tác giả.
8 CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TẬP THÔ MỜ Trong chương này, luận án sẽ trình bày tổng quan về rút gọn thuộc tính, các hướng tiếp cận filter và hướng tiếp cận kết hợp fifter-wrapper trong rút gọn thuộc tính, nhằm rút ra những ưu nhược điểm của các cách tiếp cận trên, từ đó đề xuất hướng tiếp cận phù hợp; trình bày tổng quan lý thuyết tập thô mờ là những khái niệm cơ bản để nghiên cứu vận dụng vào bài toán rút gọn trên tập mờ, là cơ sở nền tảng để đưa ra đề xuất thuật toán rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter-wrapper và cũng là căn cứ cơ bản để chúng tôi nghiên cứu và phát triển cho các thuật toán gia tăng rút gọn thuộc tính trong các chương tiếp theo. 1.1. Tổng quan về rút gọn thuộc tính Trong bối cảnh ngày nay, các cơ sở dữ liệu ngày càng gia tăng về dung lượng dữ liệu cũng như số lượng thuộc tính, gây rất nhiều khó khăn cho việc thực thi các thuật toán khai phá dữ liệu. Vấn đề đặt ra là phải tìm cách rút gọn số lượng thuộc tính mà không làm mất mát những thông tin cần thiết phục vụ nhiệm vụ khai phá dữ liệu. Do đó, rút gọn thuộc tính (hay còn gọi là rút gọn chiều – dimension reduction, rút gọn đặc trưng – feature reduction) trở thành đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu trong việc xử lý dữ liệu lớn thuộc các hệ thống Internet of Things (IoT) nơi xuất hiện một lượng lớn dữ liệu ở các dạng và khối lượng khác nhau. Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không liên quan, chỉ giữ lại các thuộc tính hữu ích nhất từ một tập các thuộc tính ban đầu nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu: Gia tăng tốc độ, cải thiện chất lượng và tính dễ hiểu của các kết quả thu được. Các kỹ thuật rút gọn thuộc tính thường được phân thành hai loại: Lựa chọn thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation). [60] Lựa chọn thuộc tính là chọn một tập con tối tiểu tốt nhất (theo một nghĩa nào đó) từ tập thuộc tính ban đầu của tập dữ liệu. Biến đổi thuộc tính là thực hiện việc biến đổi các thuộc tính ban đầu thành một tập các thuộc tính mới với số lượng ít hơn sao cho bảo tồn được thông tin nhiều nhất.
9 Với những cách thực hiện việc rút gọn thuộc tính như trên, trong quá trình phân tích luận án đề xuất nghiên cứu hướng tiếp cận lựa chọn thuộc tính, gọi chung là rút gọn thuộc tính. Các công trình nghiên cứu về rút gọn thuộc tính thường tập trung vào nghiên cứu các kỹ thuật lựa chọn thuộc tính. Lựa chọn thuộc tính là quá trình lựa chọn một tập con gồm P thuộc tính từ tập gồm A thuộc tính (P A) sao cho không gian thuộc tính được thu gọn lại một cách tối ưu theo một tiêu chuẩn nhất định. Việc tìm ra một tập con thuộc tính tốt nhất thường khó thực hiện; bài toán liên quan đến vấn đề này thuộc lớp bài toán NP-khó. Nhìn chung, một thuật toán lựa chọn thuộc tính thường bao gồm bốn khâu cơ bản: (1) Tạo lập tập con; (2) Đánh giá tập con; (3 ) Kiểm tra điều kiện dừng; (4) Kiểm chứng kết quả. Tạo lập tập con thuộc tính là quá trình tìm kiếm liên tiếp nhằm tạo ra các tập con để đánh giá, lựa chọn. Giả sử có A thuộc tính trong tập dữ liệu ban đầu, khi đó số tất cả các tập con từ A thuộc tính sẽ là 2A. Như vậy, rất khó khăn khi tìm tập con tối ưu từ tất cả các tập con này. Phương pháp chung để tìm tập con thuộc tính tối ưu là lần lượt tạo ra các tập con để so sánh. Mỗi tập con sinh ra bởi một thủ tục sẽ được đánh giá theo một tiêu chuẩn nhất định và đem so sánh với tập con tốt nhất trước đó. Nếu tập con này tốt hơn, nó sẽ thay thế tập cũ. Quá trình tìm kiếm tập con thuộc tính tối ưu sẽ dừng khi một trong bốn điều kiện sau xảy ra: - Đã thu được số thuộc tính quy định. - Số bước lặp quy định cho quá trình lựa chọn đã hết. - Việc thêm vào hay loại bớt một thuộc tính nào đó không làm cho một tập con trở nên tốt hơn. - Đã thu được tập con tốt nhất theo tiêu chuẩn đánh giá. Tập con tốt nhất cuối cùng phải được kiểm chứng thông qua việc tiến hành các phép kiểm định, so sánh các kết quả khai phá với tập thuộc tính “tốt nhất” này và tập
10 thuộc tính ban đầu trên các tập dữ liệu khác nhau. Quá trình lựa chọn thuộc tính được biểu diễn như hình sau: [60] Hình 1.1 Quy trình rút gọn thuộc tính 1.2. Các hướng tiếp cận filter-wrapper trong rút gọn thuộc tính Hiện nay có hai cách tiếp cận chính đối với bài toán lựa chọn thuộc tính: Lọc (filter) và đóng gói (wrapper), với mỗi hướng tiếp cận có những mục tiêu riêng về giảm số lượng thuộc tính hoặc nâng cao độ chính xác của mô hình phân lớp. Cách tiếp cận kiểu lọc thực hiện việc lựa chọn thuộc tính độc lập với các thuật toán khai phá sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc mô tả dữ liệu. Cách tiếp cận kiểu lọc có ưu điểm là thời gian tính toán nhanh, nhược điểm là không sử dụng thông tin nhãn lớp của các bộ dữ liệu nên độ chính xác không cao Ngược lại với cách tiếp cận lọc, lựa chọn thuộc tính kiểu đóng gói tiến hành việc lựa chọn bằng cách áp dụng ngay kỹ thuật khai phá cụ thể với tập rút gọn vừa thu được, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Các hướng tiếp cận lọc và đóng gói của bài toán lựa chọn thuộc tính được biểu diễn.[60]