Tóm tắt 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:27

Thêm vào BST

Báo xấu

20
lượt xem 2
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: Tóm tắt 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Ờ Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội - 2021
Công trình đƣợc hoàn thành tại: Học viện Khoa học và Công nghệ Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học: PGS.TS. Nguyễn Long Giang Phản biện 1: Phản biện 2: Phản biện 3: Luận án đƣợc bảo vệ trƣớc Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Vào hồi…....... ngày........ tháng........ năm 20.... Có thể tìm hiểu luận án tại: - Thƣ viện Học viện Khoa học và Công nghệ - Thƣ viện Quốc gia Việt Nam
1 MỞ ĐẦU Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu của quá trình khai phá tri thức từ dữ liệu. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa, không cần thiết nhằm nâng cao tính hiệu quả của các mô hình khai phá dữ liệu. Rút gọn thuộc tính của bảng quyết định là quá trình lựa chọn tập con nhỏ nhất của tập thuộc tính điều kiện, loại bỏ các thuộc tính dư thừa mà bảo toàn thông tin phân lớp của bảng quyết định, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Cho đến nay, có hai hướng tiếp cận chính đối với bài toán lựa chọn thuộc tính: Lọc (filter) và đóng gói (wrapper). Cách tiếp cận fifter thực hiện việc lựa chọ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 chọn chỉ dựa trên độ quan trọng của chúng trong việc mô tả 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ô mờ (fuzzy rough set) do Dübois và các cộng sự [1] đề xuất là công cụ hiệu quả 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 gốc không qua bước tiền xử lý dữ liệu nhằm nâng cao hiệu quả độ chính xác mô hình phân lớp. Cho đến nay, nhiều phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ đã được đề xuất, điển hình là các phương pháp sử dụng hàm thuộc mờ [2, 3, 4], các phương pháp sử dụng miền dương mờ [5, 6], các phương pháp sử dụng entropy mờ [7, 8, 9], các phương pháp sử dụng khoảng cách mờ [10, 11, 12] và một số phương pháp khác [13, 14, 15, 16, 17, 18]. Trong xu thế dữ liệu lớn (Big data) hiện nay, các bảng quyết định ngày càng có số thuộc tính rất lớn, ví dụ các bảng dữ liệu trong lĩnh vực tin sinh học có hàng triệu thuộc tính. Hơn nữa, các bả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à loại bỏ tập đối tượng, bổ sung và loại bỏ 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 quả, ta cần giải quyết bài toán rút gọn thuộc tính trên các bảng quyết định kích thước lớn và thay đổi. Các phương pháp rút gọn thuộc tính theo tiếp cận truyền thống trên các bảng quyết định như vậy gặp hai thách thức. Thứ nhất, với các 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 về không gian lưu trữ và tốc độ tính toán. Thứ hai, với các 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ể. Để giả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 toán gia tăng tìm tập rút gọn. 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 mà không tính lại tập rút gọn trên toàn bộ bảng quyết định ban đầu. Do đó, chúng giảm thiểu đáng kể thời gian thực hiện. 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, tập rút gọn được tính khi lần lượt bổ sung từng phần. Hướng tiếp cận tính toán gia tăng tìm tập rút gọn của bảng quyết định đã và đang thu hút sự quan tâm củ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 toán gia tăng tìm tập rút gọn của bả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 toán gia tăng đề xuất sử dụng khoảng cách [20, 21], hạ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], hà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 chọn mẫu kích hoạt
2 [40]. Với trường hợp bổ sung, loại bỏ tập thuộc tính, một số thuật toán gia tăng tìm tập rút gọ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], khoảng cách [48], độ phụ thuộc của thuộc tính [49], hạ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 toán gia tăng tìm tập rút gọn của bảng quyết định đã được đề xuất với các trường hợp: bổ sung và loại bỏ tập đối tượng [52, 53, 54, 55, 56, 57], bổ sung và loại bỏ 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ờ và đề xuất thuật toán giăng FIAT tìm tập rút gọ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 toán gia tăng IARM tìm tập rút gọ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 và đề xuất hai thuật toán IV-FS- FRS-1 và IV-FS-FRS-2 tìm tập rút gọ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 tăng AIFWAR tìm tập rút gọ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 khái niệm tập đối tượng chính (key instance set), trên cơ sở đó xây dựng hai thuật toán gia tăng tìm tập rút gọ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 quả nghiên cứu về các thuật toán gia tăng tìm tập rút gọn theo tiếp cận tập thô mờ còn hạ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 toán gia tăng cập nhật tập rút gọ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 loại bỏ tập thuộc tính. Kết quả thực nghiệm trong các công trình nêu trên cho thấy, các thuật toán gia tăng giảm thiểu đáng kể thời gian thực hiện so với các thuật toán không gia tăng. Do đó, chúng có thể thực thi hiệu quả trên các bảng quyết định có kích thước lớn và 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 gọn tìm được là tập thuộc tính tối thiểu bảo toàn độ đo được xây dựng. Việc đánh giá độ chính xác phân lớp được thực hiện sau khi tìm được tập rút gọn. Vì vậy, tập rút gọn thu được chưa phải là lựa chọn tốt nhất trên hai tiêu chí: số lượng thuộc tính tập rút gọn và độ chính xác phân lớp. Do đó, động lực nghiên cứu củ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. Mục tiêu nghiên cứu Nghiên cứu, đề 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. 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 gọn của bảng quyết định sử dụng độ đo khoảng cách mờ. Đóng góp này được trình bày ở Chương 2 của luận án. 2) Đề xuất hai 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 trong trường hợp bổ sung, loại bỏ tập đối tượng. Đóng góp này được trình bày ở Chương 3 của luận án.
3 3) Đề xuất hai 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 trong trường hợp bổ sung, loại bỏ tập thuộc tính. Đóng góp này được trình bày ở Chương 4 của luận án. CHƢƠNG 1 TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TẬP THÔ MỜ 1.1. Tổng quan về rút gọn thuộc tính Rút gọn thuộc tính 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 liên quan nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu: Gia tăng tốc độ, cải thiện chất lượng và tính dễ hiểu của các kết quả thu được. Các kỹ thuật rút gọn thuộc tính thường được phân thành hai loại: Lựa chọn thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation). Trong luận án này, tác giả nghiên cứu hướng tiếp cận lựa chọn thuộc tính, gọi chung là 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 rút gọn thuộc tính [43, 44]: 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. Cho đến nay, phần lớn các phương pháp rút gọn thuộc tính dựa trên lý thuyết tập thô và các mở rộng đều theo hướng tiếp cận này. 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. Cách tiếp cận filter có ưu điểm là thời gian tính toán nhanh, nhược điểm là không sử dụng sử dụng thông tin nhãn lớp của các bộ dữ liệu nên độ chính xác không cao. Hình 1.1 Cách tiếp cận filter và wrapper trong rút gọn thuộc tính Nhằm kết hợp các ưu điểm của cả hai cách tiếp cận filter và wrapper, một số cách tiếp cận mới cũng đã được các tác giả đã đề xuất, chẳng hạn cách tiếp cận lai ghép filter-wrapper [67, 91]. 1.3. Tổng quan về tập thô mờ 1.3.1. Quan hệ tương đương mờ Định nghĩa 1.1. [1] Cho bảng quyết định DS  U , C  D  , một quan hệ R xác định trên miền giá trị thuộc tính được gọi là quan hệ tương đương mờ nếu thỏa mãn các điều kiện sau với mọi x, y, z U 1) Tính phản xạ (reflexive): R  x, x   1 ; 2) Tính đối xứng (symetric): R  x, y   R  y, x  ;
4 3)Tính bắc cầu max-min (max-min transitive): R  x, y   sup zU min R  x, z  , R  y, z  với R  x, y  là giá trị quan hệ giữa hai đối tượng x và y. Mệnh đề 1.1. [58] Cho bảng quyết định DS  U , C  D  và quan hệ tương đương mờ R. Ký hiệu RP , RQ tương ứng là quan hệ R xác định trên tập thuộc tính P, Q. Khi đó, với mọi x, y U ta có: 1) RP  RQ  RP  x, y   RQ  x, y  2)  RPQ  RP  RQ  R( x, y)  max RP  x, y  , RQ  x, y   3) RPQ  RP  RQ  R( x, y)  min RP  x, y  , RQ  x, y  4) RP  RQ  RP  x, y   RQ  x, y  1.3.2. Ma trận tương đương mờ Định nghĩa 1.2.[58] Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  và RP là quan hệ tương đương mờ xác định trên tập thuộc tính P  C . Khi đó, ma trận tương đương mờ biểu diễn RP , ký hiệu là M ( RP )   pij  nn được định nghĩa như sau:  p11 p12 ... p1n  p p22 ... p2 n  M ( RP )   21  ... ... ... ...     pn1 pn 2 ... pnn  với pij  R P xi , x j  là giá trị của quan hệ giữa hai đối tượng xi và xj trên tập thuộc tính P, pij  0,1 , xi , x j U ,1  i, j  n . Như vậy, giá trị các phần tử của ma trận tương đương mờ M ( RP ) phụ thuộc vào quan hệ tương đương mờ RP được chọn. Mặt khác, ma trận tương đương mờ là cơ sở để xây dựng các độ đo sử dụng để giải quyết bài toán rút gọn thuộc tính trong bảng quyết định. Do đó, việc lựa chọn các quan hệ tương đương mờ ảnh hưởng đến kết quả thực hiện các phương pháp rút gọn thuộc tính. 1.3.3. Phân hoạch mờ Định nghĩa 1.3.[64] Cho bảng quyết định DS  U , C  D  với P  C , U  x1 , x2 ,..., xn  và RP là quan hệ tương đương mờ trên P. Khi đó phân hoạch mờ trên U sinh bởi RP , ký hiệu   được sau: Φ  RP   U / RP  xi P i 1   x1 P ,, xn P  với n là: Φ RP xác định như xi P  pi1 / x1  pi 2 / x2  ...  pin / xn là một tập mờ đóng vai trò là một lớp tương đương mờ (fuzzy equivalent class) của đối tượng xi  U . Với lớp tương đương mờ  xi P , hàm thuộc của các đối tượng x j U được xác định bởi xi   P  x j   R  xi , x j   RP  xi , x j   pij P và lực lượng của lớp đương đương mờ  xi P được tính n bởi  xi P  p j 1 ij .
5 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ô mờ 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô mờ 1.4.1.1 Các nghiên cứu liên quan Bảng 1 1 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 gọn của bảng quyết định theo tiếp cận tập thô mờ. STT Công bố, năm xuất bản Thuật toán 1) Hàm thuộc mờ Anoop Kumar Tiwari 2018, [3] Các thuật toán tìm tập rút gọn sử dụng 1 Z. Wang và cộng sự 2017, [4] hàm thuộc mờ Zhang và cộng sự 2018, [5] 2) Miền dương mờ T.K. Sheeja và cộng sự 2018, [6] Các phương pháp sử dụng miền dương 2 Y. Lin và cộng sự 2018, [7] mờ 3) Entropy mờ J.H. Dai và cộng sự 2018, [8] Các thuật toán tìm tập rút gọn sử dụng 3 Q.H. Hu và cộng sự 2016, [9] phương pháp entropy mờ. X. Zhang và cộng sự 2016,[10] 4) Phương pháp sử dụng khoảng cách mờ C.Z. Wang và cộng sự 2019, [11] Các thuật toán tìm tập rút gọn sử dụng 4 C.Z. Wang và cộng sự 2015, [12] độ đo phương pháp khoảng cách mờ Cao Chinh Nghia và cộng sự 2016, [13] 5) Các phương pháp khác J.H. Dai và cộng sự 2018, [14] Các thuật toán tìm tập rút gọn sử dụng J.H. Dai và cộng sự 2017, [15] một số phương pháp khác L.J.Ping và cộng sự 2020, [16] 5 W.P. Ding và cộng sự 2019, [17] X.M. Liu và cộng sự 2019, [18] Y.J. Lin và cộng sự 2017, [19] 1.4.1.2 Các vấn đề còn tồn tại Các thuật toán đã đề xuất được trình bày trong Bảng 1.1 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. 1.4.2. Phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô mờ 1.4.2.1. Các nghiên cứu liên quan Bảng 1.2 Liệt kê 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 của bảng quyết định theo tiếp cận tập thô mờ. STT Công bố, năm xuất bản Thuật toán 1. Trƣờng hợp bổ sung, loại bỏ tập đối tƣợng 1.1. Tiếp cận tập thô truyền thống Demetrovics, J., Thi, V.D., & Giang, N.L. Các thuật toán gia tăng tìm tập rút gọn [20], 2014 sử dụng khoảng cách 1 Huong, N. T. L., &Giang, N. L. [ 21], (2016)
6 Y.G. Jing và cộng sự [22, 23], 2017 Các thuật toán gia tăng tìm tập rút gọn Zhang và cộng sự [24], 2020 sử dụng hạt thông tin 2 Cai và cộng sự [25], 2019 Zhang và cộng sự [26], 2019 Zhang và cộng sự [27], 2020 W. Wei và cộng sự 2018, [28] Các thuật toán gia tăng tìm tập rút gọn G. Lang và cộng sự 2017, [29] sử dụng ma trận phân biệt 3 Ma và cộng sự 2019, [30] Yang và cộng sự, [31] Liu và cộng sự, [32] Das và cộng sự 2018, [33] Các thuật toán gia tăng tìm tập rút gọn 4 Lang và cộng sự 2018, [34] sử dụng miền dương Hao và cộng sự 2019, [35] Shua và cộng sự 2019, [36] Các thuật toán gia tăng tìm tập rút gọn 5 sử dụng hàm thuộc Nandhini và cộng sự 2019, [37] Các thuật toán gia tăng tìm tập rút gọn 6 sử dụng quan hệ không phân biệt được Shu và cộng sự 2020, [38] Các thuật toán gia tăng tìm tập rút gọn 7 sử dụng entropy thông tin Xie và cộng sự 2018, [39] Thuật toán gia tăng tìm tập rút gọn sử 8 dụng độ đo không nhất quán Y.Y. Yang và cộng sự Các thuật toán gia tăng tìm tập rút gọn 9 sử dụng lựa chọn mẫu kích hoạt 1.2. Tiếp cận tập thô mờ Liu và các cộng sự 2017, [52] Thuật toán gia tăng FIAT tìm tập rút 10 gọn sử dụng độ phụ thuộc mờ. Yang và các cộng sự 2017, [53] Các thuật toán gia tăng IARM tìm tập 11 rút gọn sử dụng quan hệ phân biệt mờ. Yang và các cộng sự 2017, [54] Các thuật toán gia tăng IV-FS-FRS-1 12 và IV-FS-FRS-2 tìm tập rút gọn sử dụng quan hệ phân biệt mờ. Giang và các cộng sự 2020, [55] Các thuật toán gia tăng IFW_FDAR_AdObj và 13 IFW_FDAR_DelObj tìm tập rút gọn sử dụng quan hệ khoảng cách mờ. Zhang và các cộng sự 2020, [56] Thuật toán gia tăng AIFWAR tìm tập 14 rút gọn sử dụng entropy có điều kiện mở rộng Ni và các cộng sự 2020, [57] Thuật toán gia tăng DIAR sử dụng hàm thuộc mờ và thuật toán PIAR sử 15 dụng miền dương mờ tìm tập rút gọn dựa trên tập đối tượng chính 2. Trƣờng hợp bổ sung, loại bỏ tập thuộc tính 2.1. Tiếp cận tập thô truyền thống W.H. Shu và cộng sự 2014, [41] Thuật toán gia tăng tìm tập rút gọn sử 16 dụng miền dương
7 F. Wang và cộng sự 2013, [42] Thuật toán gia tăng tìm tập rút gọn sử 17 dụng entropy thông tin M.J. Cai và cộng sự 2017, [43] Thuật toán gia tăng tìm tập rút gọn sử 18 Ma và cộng sự 2019, [44] dụng ma trận phân biệt. Wei và cộng sự 2019, [45] Nandhini và cộng sự 2019, [46] Thuật toán gia tăng tìm tập rút gọn sử 19 Chen và cộng sự 2020, [47] dụng quan hệ không phân biệt. Demetrovics Janos và cộng sự 2016, [48] Thuật toán gia tăng tìm tập rút gọn sử 20 dụng khoảng cách. M.S. Raza và cộng sự 2016, [49] Thuật toán gia tăng tìm tập rút gọn sử 21 dụng độ phụ thuộc của thuộc tính. Y. Jing và cộng sự 2016, [50] Các thuật toán gia tăng tìm tập rút gọn 22 Y.G. Jing và cộng sự 2018, [51] sử dụng hạt tri thức. 2.2. Tiếp cận tập thô mờ A.P. Zeng và các cộng sự 2015, [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 toán gia tăng cập nhật 23 tập rút gọ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 loại bỏ tập thuộc tính 1.4.2.2 Các vấn đề còn tồn tại Các thuật toán gia tăng tìm tập rút gọn theo tiếp cận tập thô mờ nêu trên có thời gian thực hiện nhỏ hơn đáng kể các thuật toán không gia tăng và có thể thực thi trên các bảng dữ liệu kích thước lớn. Tuy nhiên, các thuật toán nêu trên đều theo hướng tiếp cận lọc truyền thống (filter). Trong đó, tập rút gọn tìm được là tập thuộc tính tối thiểu bảo toàn độ đo được định nghĩa (hàm thuộc mờ, quan hệ phân biệt…), việc đánh giá độ chính xác phân lớp được thực hiện sau khi tìm được tập rút gọn. Vì vậy, tập rút gọn tìm được của các thuật toán nêu trên chưa tối ưu cả về số lượng thuộc tính và độ chính xác phân lớp, nghĩa là tập rút gọn tìm được chưa chắc có độ chính xác phân lớp tốt nhất. 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Ờ 2.1. Mở đầu Trong mấy năm gần đây, nhóm nghiên cứu của Nguyễn Long Giang và cộng sự đã sử dụng các độ đo khoảng cách để 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 tập thô truyền thống [9, 24, 57, 65] và bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai [9, 10, 12, 25, 58]. Theo tiếp cận tập thô mờ, nhóm nghiên cứu đã mở rộng các độ đo khoảng cách đã đề xuất thành các độ đo khoảng cách mờ và đã có một số kết quả trong việc sử dụng độ đo khoảng cách mờ để giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền giá trị số [3, 8, 18]. Tiếp tục hướng nghiên cứu này, với mục tiêu tìm kiếm các độ đo khoảng cách hiệu quả (có công thức tính toán đơn giản) giải quyết bài toán rút gọn thuộc tính, giảm thiểu thời gian thực hiện, trong chương này luận án đề xuất độ đo khoảng cách mờ (sau đây gọi là khoảng
8 cách mờ) dựa trên độ đo khoảng cách phân hoạch trong công trình [65]. Sử dụng khoảng cách mờ được xây dựng, luận án đề xuất phương pháp filter-wrapper rút gọn thuộc tính trong bảng quyết định nhằm nâng cao độ chính xác phân lớp và giảm thiểu số lượng thuộc tính tập rút gọn. Bao gồm các nội dung sau: (1) Xây dựng khoảng cách giữa hai tập mờ; (2) Xây dựng khoảng cách mờ giữa hai phân hoạch mờ; (3) Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ; (4) Thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách mờ; (5) Thử nghiệm và đánh giá tính hiệu quả của các thuật toán đề xuất. Các kết quả trong chương này được công bố trong các công trình 1, 2 phần “Danh mục các công trình khoa học đã công bố”. 2.2. Xây dựng khoảng cách giữa hai tập mờ 2.2.1. Độ đo khoảng cách mờ Mệnh đề 2.1. Cho 2 tập mờ trên tập đối tượng U, khi đó FD  X , Y   X  Y  X  Y là khoảng cách giữa và . 2.2.2. Độ đo khoảng cách mờ và các tính chất Mệnh đề 2.2. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,, xn  và   RP  ,   RQ  là 2 phân hoạch mờ sinh bởi hai quan hệ tương đương mờ RP , RQ trên P ,Q  C khi đó:       n1   x  FPD Φ RP , Φ RQ 2 n i 1 i P   xi Q   xi P   xi Q  Là một khoảng cách mờ giữa  RP  và   , gọi là khoảng cách mờ.  RQ Mệnh đề 2.3. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,, xn  và R là một quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, khi đó khoảng cách mờ giữa hai tập thuộc tính C và C  D được xác định như sau:       n12 i1 xi C  xi C  xi D  n FPD Φ RC , Φ RC  D 2.3. Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ Định nghĩa 2.1. Bảng quyết định DS  U , C  D  và RB , RC là các quan hệ tương đương mờ trên tập thuộc tính điều kiện B, C với B  C . Nếu: 1) FPD  Φ  RB  ,Φ  RBD    FPD  Φ  RC  ,Φ  RC D   2) b  B,     FPD Φ RB b ,Φ RB b D   FPD Φ  R  ,Φ  R  C C D Thì B là tập rút gọn của bảng quyết định sử dụng khoảng cách mờ. Định nghĩa 2.2. Bảng quyết định DS  U , C  D  với B  C và b  C  B . Độ quan trọng của thuộc tính đối với được định nghĩa bởi: SIGB  b   FPD  Φ  RB  ,Φ  RB  D    FPD  Φ  RB b  ,Φ  RB b D   Theo tính chất của khoảng cách mờ ta có SIGB  b   0 . Độ quan trọng SIGB  b  đặc trưng cho chất lượng phân lớp của thuộc tính b đối với thuộc tính quyết định D và được sử dụng làm tiêu chuẩn lựa chọn thuộc tính cho thuật toán filter F_FDBAR tìm tập rút gọn. Thuật toán F_FDBAR (Filter - Fuzzy Distance Based Attribute Reduction): Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ. Đầu vào: Bảng quyết định DS  U , C  D  , quan hệ tương đương mờ R xác định trên tập thuộc tính điều kiện.
9         b  B, FPD  Φ RB b ,Φ RB bD   FPD Φ RC ,Φ RC  D    Đầu ra: Một tập rút gọn B 1.     B   ; FPD  R B ,  R B D   1 ; 2. Tính khoảng cách mờ FPD    R  ,   R C C D  ; // Thêm dần vào B các thuộc tính có độ quan trọng lớn nhất 3. While FPD    R B  ,   R BD    FPD    RC  ,   RC D   do 4. Begin 5. Với mỗi a C  B tính     SIGB  a   FPD  R B ,  R BD   FPD   R B a , R B a D  6. Chọn am  C  B sao cho SIGB  am   Max SIGB  a  ; aC  B 7. B  B  am  ; 8. End; //Loại bỏ các thuộc tính dư thừa trong B nếu có a  C  B 9. For each a  B 10. Begin 11. Tính FPD    R B a  ,   RB aD   ; 12. If     FPD  R B a ,  RB aD   FPD   R  ,   R C C D  then B  B  a ; 13. End; 14. Return B; Độ phức tạp của thuật toán F_FDBAR là  O C U 2 2  2.4. Thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách mờ Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng khoảng cách mờ được mô tả như sau: Thuật toán FW_FDBAR (Filter-Wrapper Fuzzy Distance Based Attribute Reduction): Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng khoảng cách mờ. Đầu vào: Bảng quyết định DS  U , C  D  , quan hệ tương đương mờ R trên miền giá trị thuộc tính điều kiện. Đầu ra: Tập rút gọn xấp xỉ Bx có độ chính xác phân lớp tốt nhất. // Khởi tạo 1. B   ; FPD    RB  ,   RBD    1 ; 2. Tính khoảng cách mờ     FPD  RC ,  RC  D  ; // Giai đoạn filter, tìm các ứng viên cho tập rút gọn // Thêm dần vào B các thuộc tính có độ quan trọng lớn nhất 3. While FPD    RB  ,   RBD    FPD    RC  ,   RC D   do 4. Begin 5. Với mỗi a C  B tính     SIGB  a   FPD  RB ,  RBD   FPD   RBa  ,   RBaD  ; 6. Chọn am  C  B sao cho SIGB  am   Max SIGB  a  ; aC  B 7. B  B  am  ; 8. End;
10 // Giai đoạn Wrapper,tìm tập rút gọn có độ chính xác phân lớp cao nhất 9. Đặt t  B // t là số phần tử của B, B chứa các chuỗi thuộc tính được chọn tại mỗi bước lặp của vòng lặp While, nghĩa là B a ,a , a ,...,a , a ,..., a  ; i1 i1 i2 i1 i2 it 10. Đặt      B1  ai1 , B2  ai1 , ai2 ,..., Bt  ai1 , ai2 ,..., ait  11. For j = 1 to t 12. Begin 13. Tính độ chính xác phân lớp trên B j bằng một bộ phân lớp và sử dụng phương pháp 10-fold; 14. End 15. Bx  B jo với B jo có độ chính xác phân lớp lớn nhất. Return Bx ; Độ phức tạp của thuật toán FW_FDBAR là  O C *U 2 2   O  C *T  , trong đó độ phức tạp của bộ phân lớp là O T  và độ phức tạp của giai đoạn wrapper là O  C *T  . 2.5. Thực nghiệm và đánh giá kết quả các thuật toán 2.5.1. Mục tiêu thực nghiệm 1) So sánh thuật toán filter-wrapper đề xuất FW_FDBAR với thuật toán filter-wrapper FEBAR trong [9] về thời gian thực hiện, độ chính xác phân lớp và số lượng thuộc tính tập rút gọn. 2) So sánh thuật toán filter-wrapper đề xuất FW_FDBAR với thuật toán filter FPDAR trong [12] về thời gian thực hiện, số lượng thuộc tính tập rút gọn và độ chính xác phân lớp. 2.5.2. Số liệu thực nghiệm Bảng 2.1 Bộ dữ liệu thử nghiệm thuật toán FW_FDBAR Số thuộc tính điều kiện Thuộc Thuộc Số lớp Số đối STT Bộ dữ liệu Mô tả Tất tính định tính thực quyết tƣợng cả danh (Real- định (nominal) valued) 1 Lympho Lymphography 148 18 18 0 2 2 Wine Wine 178 13 0 13 3 3 Libra Libras movement 360 90 0 90 15 Wisconsin 4 WDBC diagnostic breast 569 30 0 30 2 cancer 5 Horse Horse colic 368 22 15 7 2 6 Heart Statlog (heart) 270 13 7 6 2 7 Credit Credit approval 690 15 9 6 2 German credit 8 German 1000 20 13 7 2 data 2.5.3. Kết quả so sánh độ chính xác phân lớp và số lượng thuộc tính tập rút gọn Độ chính xác phân lớp được biểu diễn bởi v   trong đó v là giá trị độ chính xác trung bình (mean) và  là sai số chuẩn (standard error). Sử dụng bộ phân lớp CART (cây phân
11 lớp, hồi quy) để tính độ chính xác phân lớp trong giai đoạn wrapper với phương pháp kiểm tra chéo 10-fold. Hình 2.1 Độ chính xác phân lớp của ba thuật toán Hình 2.2 Số lượng thuộc tính tập rút gọn của ba thuật toán Kết quả ở Hình 2.1 và Hình 2.2 cho thấy, số thuộc tính tập rút gọn của thuật toán đề xuất FW_FDAR nhỏ hơn nhiều so với thuật toán filter FPDAR. Độ chính xác của FW_FDAR cao hơn FPDAR trên tất cả các bộ dữ liệu. Với thuật toán filter-wrapper FEBAR [91] sử dụng -entropy mờ, số lượng thuộc tính tập rút gọn của FW_FDAR xấp xỉ FEBAR, độ chính xác phân lớp của FW_FDAR xấp xỉ FEBAR. 2.5.4. Kết quả so sánh thời gian thực hiện Hình 2.3 Thời gian thực hiện FW_FDBAR, FEBAR, FPDAR Hình 2.3 cho thấy, thuật toán FW_FDAR có thời gian thực hiện nhỏ hơn đáng kể thuật toán FEBAR [91], chủ yếu là ở thủ tục filter tìm tập rút gọn. Nguyên nhân là thuật toán FEBAR phải tính miền dương mờ để xác định hệ số , hơn nữa thuật toán FEBAR phải tính toán các công thức logarit phức tạp trong công thức entropy Shannon. Tuy nhiên, các thuật toán theo tiếp cận filter-wrapper FW_FDAR và FEBAR [91] có thời gian thực hiện lớn hơn thuật toán theo tiếp cận filter FPDAR [18] vì phải thực hiện bộ phân lớp để tính độ chính xác của các tập rút gọn xấp xỉ trong giai đoạn wrapper.
12 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 3.1. Mở đầu Trong chương này, trước hết luận án trình bày các công thức gia tăng cập nhật khoảng cách mờ (được đề xuất ở Chương 2) trong trường hợp bổ sung, loại bỏ tập đối tượng. Dựa trên các công thức tính toán gia tăng khoảng cách mờ được xây dựng, luận án trình bày 02 thuật toán gia tăng tìm tập rút gọn của bảng quyết định theo tiếp cận kết hợp filter-wrapper: 1) Thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj tìm tập rút gọn khi bổ sung tập đối tượng. 2) Thuật toán gia tăng filter-wrapper IFW_FDAR_DelObj tìm tập rút gọn khi loại bỏ tập đối tượng Hai thuật toán đề xuất đều theo tiếp cận kết hợp filter-wrapper, trong đó giai đoạn filter tìm các ứng viên cho tập rút gọn (là các tập thuộc tính bảo toàn độ đo sử dụng), giai đoạn wrapper tìm tập rút gọn có độ chính xác phân lớp cao nhất. Hai thuật toán đề xuất 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. Kết quả nghiên cứu ở chương này được công bố ở công trình số 1, 3 phần “Danh mục các công trình của tác giả”. 3.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn bổ sung tập đối tƣợng 3.2.1. Công thức gia tăng tính khoảng cách mờ khi bổ sung tập đối tượng Mệnh đề 3.2. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  và R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện. Giả sử tập đối tượng gồm s phần tử U  xn1, xn2 ,..., xn s  được bổ sung vào U, mà s2. Với   MU U RC  mij   n  s n  s  , MU U  RD   d ij  là ma trận tương đương mờ tương ứng n s  n s  trên C và D. Khi đó, công thức gia tăng khoảng cách mờ như sau:      FPDU U Φ RC , Φ RC  D  FPD  Φ  R  , Φ  R    x   2  n   2 s   C D C n i    xn i C   xn i D  i  n  s U C i 1  n s  2 mà i   j i  mni,n j 1  min  mni,n j 1 , dni,n j 1   s 1 3.2.2. Thuật toán gia tăng fifter-wrapper tìm tập rút gọn sau khi bổ sung tập đối tượng Mệnh đề 3.3. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  và R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, B  C là tập rút gọn dựa trên khoảng cách mờ. Giả sử tập đối tượng gồm s phần tử U  xn1, xn2 ,..., xn s  được bổ sung vào U . Khi đó ta có: 1) Nếu D  xni   d với mọi i  1, 2,, s thì:      FPDU U Φ RC , Φ RC  D FPD  Φ  R  , Φ  R    x  2  n   2 s    C D C n i    xn i C   xn i D  ns  n  s U C 2 i 1 2) Nếu xni B  xni D với mọi i  1, 2,..., s thì     FPDU U Φ RB ,Φ RBD   FPDU U Φ  RC  ,Φ  RC D  .
13 Algorithm IFW_FDAR_AdObj Đầu vào: 1. Bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  , quan hệ tương đương mờ R , tập rút gọn B  C . 2. Các ma trận tương đương mờ       MU RB  bij  , MU RC  cij  , MU RD  dij  nn nn nn 3. Tập đối tượng bổ sung U  xn1 , xn 2 ,..., xn s  Đầu ra: Tập rút gọn xấp xỉ Bbest của DS   U  U , C  D  với độ chính xác phân loại cao nhất. Bước 1: Khởi tạo 1. T : ; // T chứa ứng của viên tập rút gọn tốt nhất 2. Tính các ma trận tương đương mờ trên tập đối tượng U  U MU U  RB   bij  , MU U  RD    dij  ;    n s  n s   ns  ns Bước 2: Kiểm tra tập đối tượng thêm vào 3. Đặt X : U ; 4. For i  1 to s do 5. If xni B  xni D then X : X  xni  ; 6. If X   then Return B0 ; // Tập xấp xỉ không thay đổi 7. Đặt U : X ; s : U ; //Gán lại tập đối tượng Bước 3: Tìm tập rút gọn tốt nhất   8. Tính các khoảng cách mờ ban đầu FPDU Φ  RB  ,Φ  RBD  ; FPDU Φ  RC  ,Φ  RC D  ;   9. Tính khoảng cách mờ bởi công thức gia tăng:          FPDU U Φ RB ,Φ RB D ; FPDU U Φ RC ,Φ RC  D  // Giai đoạn fifter: tìm các ứng viên cho tập rút gọn    10. While FPDU U Φ  RB  ,Φ  RBD   FPDU U Φ  RC  ,Φ  RC D  do  11. Begin 12. For each a  C  B do 13. Begin 14.    Tính FPDU U Φ RBa ,Φ RBaD  bởi công thức gia tăng; 15. Tính SIGB  a   FPDU U  Φ  R  , Φ  R   FPD Φ  R    , Φ  R B BD U U B a B a D  ; 16. End; 17. Select a  C  B satisfying SIGB  am   Max SIGB  a  ; aC  B 18. B : B  am  ; 19. B0 : B0  am  ; 20. T : T  B0 ; 21. End; //Giai đoạn Wrapper: tìm tập rút gọn với độ chính xác phân loại cao nhất 22. Đặt t : T //t là số phần tử của T, T  B0  a1 , B0  a1 , a2  ,..., B0 a1 , a2 ,..., at  ; 23. Đặt T1 : B0  a1;T2 : B0  a1 , a2 ;...; Tt : B0  a1, a2 ,..., at  ; 24. For j:= 1 to t do 25. Tính độ chính xác phân lớp trên T j bằng một bộ phân lớp sử dụng phương pháp 10-fold; 26. Bbest : T jo với T jo có độ chính xác phân lớp cao nhất; Return Bbest ;
14 Độ phức tạp của thuật toán IFW_FDAR_AdObj là:  max  O B * U *  U  U  , O  C  B  * U *  U  U    O  C  B  *T  2  Dựa trên kết quả này chúng ta thấy rằng thuật toán IFW_FDAR_AdObj giảm thiểu đáng kể thời gian thực hiện, đặc biệt trong trường hợp tập đối tượng U lớn hoặc tập điều kiện C lớn và B nhỏ. 3.2.3. Thực nghiệm thuật toán 3.2.3.1 Mục tiêu thực nghiệm 1) Đánh giá về thời gian thực hiện của thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj với hai thuật toán hai thuật toán gia tăng theo tiếp cận filter trên tập thô mờ IV-FS-FRS-2 [54], IARM [18]) và hai thuật toán filter trên tập thô (ASS-IAR [40], IFSA [36])). Đặc biệt, thuật toán IV-FS-FRS-2 là một thuật toán filter dựa trên ma trận phân biệt mờ, trong khi IARM là một thuật toán filter dựa trên quan hệ phân biệt. ASS-IAR là thuật toán filter dựa trên lựa chọn mẫu hoạt động, trong khi IFSA là thuật toán filter dựa trên chức năng phụ thuộc. 2) Đánh giá tính hiệu quả về độ chính xác phân lớp và số lượng thuộc tính của tập rút gọn của thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj so với bốn thuật toán filter nêu trên. 3.2.3.2 Dữ liệu thực nghiệm Bảng 3.1 Bộ dữ liệu thử nghiệm khi thêm tập đối tượng Số thuộc tính điều Số kiện Số Số đối đối Bộ dữ Số đối Giá lớp Stt Mô tả tƣợng tƣợng Giá liệu tƣợng Tổng trị quyết ban đầu gia trị số định định tăng thực danh (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Libras 1 Libra 360 180 180 90 0 90 15 movement Wisconsin 2 WDBC diagnostic 569 284 285 30 0 30 2 breast cancer 3 Horse Horse colic 368 183 185 22 15 7 2 4 Heart Statlog (heart) 270 135 135 13 7 6 2 5 Credit Credit approval 690 345 345 15 9 6 2 German credit 6 German 1000 500 500 20 13 7 2 data Contraceptive 7 Cmc 1473 733 740 9 7 2 3 Method Choice 8 Wave Waveform 5000 2500 2500 21 0 21 3
15 3.2.3.3 Kết quả so sánh thời gian thực hiện của thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj với thuật toán IV-FS-FRS-2, IARM, ASS-IAR, IFSA Hình 3.1 Thời gian thực hiện của các thuật toán IFW_FDAR_AdObj, IV-FS-FRS-2 IARM, ASS-IAR và IFSA trên bộ dữ liệu mẫu Libra (tính bằng giây) 3.2.2.4 Kết quả so sánh độ chính xác phân lớp và số lượng thuộc tính của tập rút gọn của thuật toán gia tăng filter-wrapper IFW_FDAR_AdObj với thuật toán IV-FS-FRS-2, IARM, ASS-IAR, IFSA 0.65 Độ chính xác phân lớp 0.6 IFW-FDAR-AdObj 0.55 IV-FS-FRS-2 IARM 0.5 ASS-IAR IFSA 0.45 U0 U1 U2 U3 U4 U5 Các tập đối tượng của dữ liệu Libra Hình 3.2 Độ chính xác phân lớp của các thuật toán IFW_FDAR_AdObj, IV-FS-FRS-2, IARM, ASS-IAR và IFSA Hình 3.3 Số lượng thuộc tính tập rút gọn của các thuật toán IFW_FDAR_AdObj, IV-FS- FRS-2, IARM, ASS-IAR và IFSA
16 3.3. Thuật toán gia tăng fifter-wrapper tìm tập rút gọn khi loại bỏ tập đối tƣợng 3.3.1. Cập nhật khoảng cách mờ khi loại bỏ tập đối tượng Mệnh đề 3.5. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  và R là một quan hệ tương đương mờ. Giả sử tập đối tượng gồm s phần tử U  xk , xk 1,..., xk  s 1 bị loại khỏi U, s  n . Ma trận tương đương mờ và ma trận tương đương trên C và D tương ứng được xác định bởi MU U  RC   mij  ns  ns , MU U  RD   dij  ns  ns . Khi đó, công thức cập nhật       khoảng cách mờ như sau:      FPDU U Φ RC , Φ RC  D (3.8)  FPD  Φ  R  , Φ  R   n 2s   x  2  n  s 1  C D C   xk i C   xk i D   i k i   ns    U C 2 i 0  m   i Với  i  j 0 k i , k  j  min mk i,k  j , dk i,k  j 3.3.2. Thuật toán fifter-wrapper để cập nhật tập rút gọn khi loại bỏ tập đối tượng Mệnh đề 3.6. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  và R là một quan hệ tương đương mờ xác định trên miền giá trị của tập thuộc tính điều kiện. B  C là tập rút gọn dựa trên khoảng cách mờ. Giả sử tập đối tượng gồm s phần tử U  xk , xk 1,..., xk  s 1 bị loại khỏi U , s  n . Khi đó ta có: 1) Nếu D  x k i   d với i  0,...,s 1 thì      FPDU U Φ RC , Φ RC  D  FPD  Φ  R  , Φ  R    x  2  n   2 s 1   C D C k i    xk i C   xk i D  n  s U C i 0  n s  2 2) Nếu xk i B   xk i D với i  0,..., s  1 thì     FPDU U Φ RB ,Φ RB D   FPDU U Φ  RC  ,Φ  RC D  Algorithm IFW_FDAR_DelObj Input: Đầu vào 1. Bảng quyết định DS  U , C  D  với U  x1 , x2 ,..., xn  , một quan hệ tương đương mờ R , tập rút gọn B  C ; 2. Ma trận tương đương mờ MU  RB   mijB  , MU  RC   mijC  , MU  RD   dij  nn nn nn 3. Tập đối tượng gồm s phần tử bị loại bỏ U  xk 1 , xk 2 ,..., xk  s 1 , s  n Output: Tập rút gọn xấp xỉ Bbest của DS   U  U , C  D  có độ chính xác phân lớp cao nhất. 1. T :  ; 2. Đặt X : U ; 3. For i  0 to s  1 do 4. If xk i B  xk i D then X : X  xk i ; 5. If X   then Return B0 ; 6. Đặt U : X ; s  U ; 7. Tính các FPDs ban đầu: FPDU  Φ  RB  ,Φ  RBD   ; FPDU  Φ  RC  ,Φ  RC D   8. Tính khoảng cách mờ bởi Mệnh đề 3.6 khi loại tập đối tượng U :      FPDU U Φ RB ,Φ RB D ; FPDU U Φ RC ,Φ RC D ;     
17 // Giai đoạn Fifter, tìm các ứng viên cho tập rút gọn 9. While FPDU U  Φ  RB  ,Φ  RBD    FPDU U  Φ  RC  ,Φ  RC D   do 10. Begin 11. For each a  B do 12. Begin 13.   Tính FPDU U Φ  RB a  , Φ  RB aD  bởi Mệnh đề 3.6 khi loại bỏ tập đối tượng U ; 14. Tính    SIGB a  a  : FPDU U Φ RB a , Φ RB aD   FPDU U  Φ  R  , Φ  R  ; B BD 15. End; 16. Chọn am  B sao cho aB  SIGB  am   Min SIGB a  a  ; 17. B : B  am  ; 18. B0 : B0  am  ; 19. T : T  B0 ; 20. End; // Giai đoạn Wrapper tìm tập rút gọn có độ chính xác phân lớp cao nhất 21. Đặt t : T // T  B0  a1 , B0  a1 , a2  ,..., B0  a1 , a2 ,..., at  ; 22. Đặt * + * + * +; 23. For j:= 1 to t do T 24. Tính độ chính xác phân lớp trên j bằng một bộ phân lớp sử dụng phương pháp 10-fold; 25. Bbest : T jo với T jo có độ chính xác phân lớp cao nhất; Return; Độ phức tạp của thuật toán IFW_FDAR_DelObj là: (| | | | | |) (| | ) 3.3.3. Thực nghiệm thuật toán 3.3.3.1 Mục tiêu thử nghiệm Trong phần này chúng tôi cài đặt thử nghiệm để đánh giá độ chính xác phân loại của thuật toán IFW_FDAR_DelObj so với các thuật toán gia tăng dựa trên tập thô theo tiếp cận fifter IFSD [36]. IFSD là thuật toán gia tăng rút gọn thuộc tính dựa trên hàm phụ thuộc khi loại bỏ tập đối tượng. 3.3.3.2 Dữ liệu thử nghiệm Bảng 3.2 Mô tả dữ liệu khi loại bỏ tập đối tượng Stt Bộ dữ liệu Số đối tƣợng Số các thuộc tính điều kiện Số lớp quyết định 1 Audiology 226 69 24 2 Dermatology 366 34 6 3 Arrhythmia 452 279 16 4 Mfeat-factor 2000 216 10 5 Chess-kr-vs-kp 3196 36 2 6 Satimage 6435 36 6 7 Mushroom 8124 22 2 8 Letter 20000 16 26
18 Để đánh giá hiệu quả về thời gian thực hiện và độ chính xác của thuật toán, chúng tôi chọn xóa ngẫu nhiên 10%, 20%, 30%, 40% đối tượng trên mỗi bộ dữ liệu khi xóa các tập đối tượng ký hiệu tương ứng U1, U2, U3, U4. Dữ liệu ban đầu ký hiệu là U. 3.3.3.3 Kết quả so sánh thời gian thực hiện của thuật toán IFW_FDAR_DelObj với thuật toán IFSD 4 Thời gian thực hiện 3 2 1 IFW_FDAR_DelObj 0 IFSD U1 U2 U3 U4 Tập đối tượng bị loại của Bộ dữ liệu Audiology Hình 3.4 Thời gian thực hiện của thuật toán IFW_FDAR_DelObj và IFSD 3.3.3.4 Kết quả so sánh độ chính xác phân lớp và số lượng thuộc tính tập rút gọn thu được bởi thuật toán IFW_FDAR_DelObj và thuật toán IFSD Hình 3.5 Độ chính xác phân lớp của thuật toán IFW_FDAR_DelObj và thuật toán IFSD Hình 3.6 Số lượng thuộc tính tập rút gọn của IFW_FDAR_DelObj và IFSD 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 4.1. Mở đầu Trong chương này, trước hết luận án trình bày các công thức gia tăng cập nhật khoảng cách mờ khi bổ sung, loại bỏ tập thuộc tính. Dựa trên các công thức tính toán gia tăng khoảng cách mờ được xây dựng, luận án trình bày 02 thuật toán: 1) Thuật toán gia tăng filter-wrapper IFW_FDAR_AA tìm tập rút gọn khi bổ sung tập thuộc tính.