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].
, một quan hệ xác định trên 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
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
1) Tính phản xạ (reflexive): ;
2) Tính đối xứng (symetric): ;
4
3)Tính bắc cầu max-min (max-min transitive): với
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 và quan hệ tương đương mờ .
Ký hiệu , xác định trên tập thuộc tính P, Q. Khi đó, với mọi tương ứng là quan hệ
ta có:
1)
2)
3)
4)
1.3.2. Ma trận tương đương mờ
Định nghĩa 1.2.[58] Cho bảng quyết định với và là
. Khi đó, ma trận tương đương
quan hệ tương đương mờ xác định trên tập thuộc tính mờ biểu diễn , ký hiệu là được định nghĩa như sau:
với là giá trị của quan hệ giữa hai đối tượng và trên tập thuộc tính P,
. ,
Như vậy, giá trị các phần tử của ma trận tương đương mờ
phụ thuộc vào quan hệ tương đương mờ đượ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 với , và
là quan hệ tương đương mờ trên P. Khi đó phân hoạch mờ trên U sinh bởi , ký hiệu
là: được xác định như sau: với
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 Với lớp tương đương mờ . , hàm thuộc của các đối tượng được xác định bởi
và lực lượng của lớp đương đương mờ được tính
bởi .
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ờ.
Công bố, năm xuất bản Thuật toán STT 1) Hàm thuộc mờ
1 Các thuật toán tìm tập rút gọn sử dụng hàm thuộc mờ Anoop Kumar Tiwari 2018, [3] Z. Wang và cộng sự 2017, [4] Zhang và cộng sự 2018, [5]
2) Miền dương mờ
2 T.K. Sheeja và cộng sự 2018, [6] Y. Lin và cộng sự 2018, [7] Các phương pháp sử dụng miền dương mờ
3) Entropy mờ
3 Các thuật toán tìm tập rút gọn sử dụng phương pháp entropy mờ. J.H. Dai và cộng sự 2018, [8] Q.H. Hu và cộng sự 2016, [9] X. Zhang và cộng sự 2016,[10]
4 Các thuật toán tìm tập rút gọn sử dụng độ đo phương pháp khoảng cách mờ 4) Phương pháp sử dụng khoảng cách mờ C.Z. Wang và cộng sự 2019, [11] C.Z. Wang và cộng sự 2015, [12] Cao Chinh Nghia và cộng sự 2016, [13]
5) Các phương pháp khác
Các thuật toán tìm tập rút gọn sử dụng một số phương pháp khác
5
J.H. Dai và cộng sự 2018, [14] J.H. Dai và cộng sự 2017, [15] L.J.Ping và cộng sự 2020, [16] 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ờ.
Thuật toán Công bố, năm xuất bản
STT 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
Các thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách 1
Demetrovics, J., Thi, V.D., & Giang, N.L. [20], 2014 Huong, N. T. L., &Giang, N. L. [ 21], (2016)
6
Các thuật toán gia tăng tìm tập rút gọn sử dụng hạt thông tin 2
Các thuật toán gia tăng tìm tập rút gọn sử dụng ma trận phân biệt
3
4 Các thuật toán gia tăng tìm tập rút gọn sử dụng miền dương
Y.G. Jing và cộng sự [22, 23], 2017 Zhang và cộng sự [24], 2020 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] G. Lang và cộng sự 2017, [29] 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] Lang và cộng sự 2018, [34] Hao và cộng sự 2019, [35] Shua và cộng sự 2019, [36] 5
Nandhini và cộng sự 2019, [37] 6
Shu và cộng sự 2020, [38] 7
Xie và cộng sự 2018, [39] 8
Y.Y. Yang và cộng sự 9 Các thuật toán gia tăng tìm tập rút gọn sử dụng hàm thuộc Các thuật toán gia tăng tìm tập rút gọn sử dụng quan hệ không phân biệt được Các thuật toán gia tăng tìm tập rút gọn sử dụng entropy thông tin Thuật toán gia tăng tìm tập rút gọn sử dụng độ đo không nhất quán Các thuật toán gia tăng tìm tập rút gọn 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] 10
Yang và các cộng sự 2017, [53] 11
Yang và các cộng sự 2017, [54]
12
Giang và các cộng sự 2020, [55]
13
Zhang và các cộng sự 2020, [56]
14
Ni và các cộng sự 2020, [57]
15
Thuật toán gia tăng FIAT tìm tập rút gọn sử dụng độ phụ thuộc mờ. Các thuật toán gia tăng IARM tìm tập rút gọn sử dụng quan hệ phân biệt mờ. Các thuật toán gia tăng IV-FS-FRS-1 và IV-FS-FRS-2 tìm tập rút gọn sử dụng quan hệ phân biệt mờ. Các thuật toán gia tăng IFW_FDAR_AdObj và IFW_FDAR_DelObj tìm tập rút gọn sử dụng quan hệ khoảng cách mờ. 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 Thuật toán gia tăng DIAR sử dụng hàm thuộc mờ và thuật toán PIAR sử 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] 16 Thuật toán gia tăng tìm tập rút gọn sử dụng miền dương
7
F. Wang và cộng sự 2013, [42] 17
18 Thuật toán gia tăng tìm tập rút gọn sử dụng entropy thông tin Thuật toán gia tăng tìm tập rút gọn sử dụng ma trận phân biệt.
19
M.J. Cai và cộng sự 2017, [43] Ma và cộng sự 2019, [44] Wei và cộng sự 2019, [45] Nandhini và cộng sự 2019, [46] Chen và cộng sự 2020, [47] Demetrovics Janos và cộng sự 2016, [48] 20
M.S. Raza và cộng sự 2016, [49] 21
22 Y. Jing và cộng sự 2016, [50] Y.G. Jing và cộng sự 2018, [51] Thuật toán gia tăng tìm tập rút gọn sử dụng quan hệ không phân biệt. Thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách. Thuật toán gia tăng tìm tập rút gọn sử dụng độ phụ thuộc của thuộc tính. Các thuật toán gia tăng tìm tập rút gọn 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]
23
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
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ố”.
là 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 đó
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 với và ,
là 2 phân hoạch mờ sinh bởi hai quan hệ tương đương mờ , trên P khi đó:
Là một khoảng cách mờ giữa và , gọi là khoảng cách mờ.
Mệnh đề 2.3. Cho bảng quyết định với và
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 sau: mờ tính C thuộc được giữa định như xác hai tập và
và là các quan hệ tương đương
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 mờ trên tập thuộc tính điều kiện B, C với
1) . Nếu:
2)
với và
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 đối tính thuộc được với định của . Độ quan trọng bởi: nghĩa
Theo tính chất của khoảng cách mờ ta có . Độ quan trọng
đặ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
, quan hệ tương đương mờ xác định trên tập
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 thuộc tính điều kiện.
9
Đầu ra: Một tập rút gọn
1. ; ;
2. Tính khoảng cách mờ ;
// Thêm dần vào B các thuộc tính có độ quan trọng lớn nhất 3. While do
4. Begin 5. Với mỗi tính
6. Chọn sao cho ;
;
7. 8. End; //Loại bỏ các thuộc tính dư thừa trong B nếu có 9. For each 10. 11. Begin Tính ;
12. If then ;
13. 14. End; Return ;
Độ phức tạp của thuật toán F_FDBAR là
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):
trên miền giá trị , quan hệ tương đương mờ
có độ chính xác phân lớp tốt nhất.
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 thuộc tính điều kiện. Đầu ra: Tập rút gọn xấp xỉ // Khởi tạo ; 1. ;
2. Tính khoảng cách mờ ;
// 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 do
4. Begin 5. Với mỗi tính ;
6. Chọn sao cho ;
;
7. 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 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à ;
10. Đặt
11. For j = 1 to t 12. Begin 13. Tính độ chính xác phân lớp trên bằng một bộ phân lớp và sử dụng phương
với có độ chính xác phân lớp lớn nhất.
pháp 10-fold; 14. End 15. Return ;
Độ phức tạp của thuật toán FW_FDBAR là , trong đó độ phức tạp
của bộ phân lớp là và độ phức tạp của giai đoạn wrapper là .
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
STT Bộ dữ liệu Mô tả Số đối tƣợng Số lớp quyết định Tất cả
Lympho
1 2 Wine Libra 3 148 178 360 18 13 90 Thuộc tính định danh (nominal) 18 0 0 Thuộc tính thực (Real- valued) 0 13 90 2 3 15
4 WDBC 569 30 0 30 2
5 Horse 6 Heart 7 Credit 368 270 690 22 13 15 15 7 9 7 6 6 2 2 2
8 German 1000 20 13 7 2 Lymphography Wine Libras movement Wisconsin diagnostic breast cancer Horse colic Statlog (heart) Credit approval German credit 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 trong đó
là giá trị độ chính xác trung là sai số chuẩn (standard error). Sử dụng bộ phân lớp CART (cây phân bình (mean) và
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 với và
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 được bổ sung vào U, mà s2. Với gồm s phần tử
trên C và D. Khi đó, công thức gia là ma trận tương đương mờ tương ứng tăng khoảng cách mờ như sau:
mà
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 với
và là quan hệ là tập rút gọn dựa được bổ
tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, trên khoảng cách mờ. Giả sử tập đối tượng gồm s phần tử sung vào . Khi đó ta có:
1) Nếu với mọi thì:
2) Nếu với mọi thì
.
13
Algorithm IFW_FDAR_AdObj Đầu vào:
1. Bảng quyết định
với
, quan hệ tương đương mờ
, tập
rút gọn
.
2. Các ma trận tương đương mờ
của
với độ chính xác phân loại cao nhất.
// T chứa ứng của viên tập rút gọn tốt nhất
3. Tập đối tượng bổ sung Đầu ra: Tập rút gọn xấp xỉ Bước 1: Khởi tạo 1. 2. Tính các ma trận tương đương mờ trên tập đối tượng
;
; to s do
Bước 2: Kiểm tra tập đối tượng thêm vào 3. Đặt 4. For 5. If
then
;
then Return
; // Tập xấp xỉ không thay đổi
; //Gán lại tập đối tượng
6. If 7. Đặt 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
;
9. Tính khoảng cách mờ bởi công thức gia tăng:
// Giai đoạn fifter: tìm các ứng viên cho tập rút gọn 10. While
do
do
11. Begin 12. For each 13. Begin 14. Tính
bởi công thức gia tăng;
15. Tính
16. End; 17. Select
satisfying
;
;
;
;
18. 19. 20. 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 là số phần tử của T,
;
;
Đặt For j:= 1 to t do
23. 24. 25. Tính độ chính xác phân lớp trên
bằng một bộ phân lớp sử dụng phương pháp 10-fold;
26.
với
có độ chính xác phân lớp cao nhất;
Return
;
14
Độ phức tạp của thuật toán IFW_FDAR_AdObj là:
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 lớn hoặc tập điều kiện
lớn và 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
Stt Mô tả Bộ dữ liệu Số đối tƣợng Số đối tƣợng ban đầu Số lớp quyết định Tổng số Số đối tƣợng gia tăng Giá trị thực
Số thuộc tính điều kiện Giá trị định danh (8) (9) (7) (10) (5) (6) (4) (1) (2)
360 180 180 90 90 15 1 Libra 0
569 284 285 30 30 2 2 WDBC 0
368 270 690 183 135 345 185 135 345 22 13 15 7 6 6 2 2 2 15 7 9
1000 500 500 20 7 2 6 German 13
1473 733 740 9 2 3 Cmc 7 7
5000 2500 2500 21 21 3 (3) Libras movement Wisconsin diagnostic breast cancer Horse colic 3 Horse 4 Statlog (heart) Heart 5 Credit Credit approval German credit data Contraceptive Method Choice Waveform 8 Wave 0
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)
0.65
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
p ớ
l
0.6
IFW-FDAR-AdObj
IV-FS-FRS-2
0.55
IARM
í
0.5
ASS-IAR
n â h p c á x h n h c ộ Đ
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 và
với hệ tương đương mờ. Giả sử tập đối tượng gồm s phần tử U, định bởi là một quan bị loại khỏi . 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 . Khi đó, công thức cập nhật
khoảng cách mờ như sau:
(3.8)
Với
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 và với
là một quan là tập rút bị
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. gọn dựa trên khoảng cách mờ. Giả sử tập đối tượng gồm s phần tử loại khỏi . Khi đó ta có: ,
1) Nếu với thì
2) Nếu với thì
Algorithm IFW_FDAR_DelObj Input: Đầu vào với , một quan hệ tương đương
1. Bảng quyết định ; , tập rút gọn mờ
2. Ma trận tương đương mờ
3. Tập đối tượng gồm s phần tử bị loại bỏ ,
Output: Tập rút gọn xấp xỉ của có độ chính xác phân lớp cao
nhất.
;
to
;
Đặt For If If Đặt do then then Return ; 1. 2. 3. 4. 5. 6.
7. Tính các FPDs ban đầu:
8. Tính khoảng cách mờ bởi Mệnh đề 3.6 khi loại tập đối tượng :
17
// Giai đoạn Fifter, tìm các ứng viên cho tập rút gọn 9. While do
For each do
10. Begin 11. 12. Begin 13. Tính bởi Mệnh đề 3.6 khi loại bỏ tập đối tượng
; 14. Tính ;
15. 16. End; Chọn sao cho ;
;
;
End;
// ;
17. 18. 19. 20. // 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 22. Đặt * + * + * +; 23. For j:= 1 to t do
bằng một bộ phân lớp sử dụng phương Tính độ chính xác phân lớp trên
với có độ chính xác phân lớp cao nhất;
24. pháp 10-fold; 25. 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 2 3 4 5 6 7 8 Audiology Dermatology Arrhythmia Mfeat-factor Chess-kr-vs-kp Satimage Mushroom Letter 226 366 452 2000 3196 6435 8124 20000 69 34 279 216 36 36 22 16 24 6 16 10 2 6 2 26
18
4
n ệ i h
3
2
c ự h t
IFW_FDAR_DelObj
1
n a i g
IFSD
0
U1
U3
U4
i ờ h T
U2 Tập đối tượng bị loại của Bộ dữ liệu Audiology
Để đá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
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.
19
2) Thuật toán gia tăng filter-wrapper IFW_FDAR_DA tìm tập rút gọn khi loại bỏ tập thuộc tính.
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ố 4, phần “Danh mục các công trình của tác giả”.
4.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 4.2.1. Công thức gia tăng cập nhật khoảng cách khi bổ sung tập thuộc tính Mệnh đề 4.1. Cho bảng quyết định tính điều kiện B được bổ sung vào C với . Giả sử tập thuộc , với . Giả sử ,
là các ma trận tương đương mờ của các quan hệ tương đương mờ
1) Nếu 2) Nếu thì thì trên B, C, D tương ứng. Khi đó ta có: với mọi với mọi
3) Nếu với mọi thì
4.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 Từ công thức gia tăng tính khoảng cách mờ trong Mệnh đề 4.1 ta có Mệnh đề 4.2 sau đây:
Mệnh đề 4.2. Cho bảng quyết định với và
là tập rút gọn dựa trên khoảng cách mờ. Giá sử tập thuộc tính điều kiện B được bổ sung vào C là các ma trận tương với . Đặt , ,
đương mờ của các quan hệ tương đương mờ trên B, C, D tương ứng. Khi đó ta có:
1) Nếu với mọi thì R là tập rút gọn của .
2) Nếu với mọi thì B chứa một tập rút gọn của
Bảng quyết định , tập rút gọn với
Thuật toán IFW_FDAR_AA (Incremental Filter-Wrapper Fuzzy Distance-based Attribute Reduction Algorithm when Adding Attributes). Đầu vào: 1) trận tương đương mờ , các ma của các quan hệ tương đương ,
, khoảng cách mờ ;
mờ 2) Tập thuộc tính bổ sung B với ;
của
Đầu ra: Tập rút gọn Bước 1: Khởi tạo và kiểm tra tập thuộc tính bổ sung 1. // Chứa các ứng viên tập rút gọn;
20
2. Tính ma trận quan hệ tương đương mờ ;
;
3. If 4. If với mọi với mọi then Return then ; //Tìm tập rút gọn trong tập B
Bước 2: Thực hiện thuật toán tìm tập rút gọn // Giai đoạn filter, tìm các ứng viên cho tập rút gọn xuất phát từ tập R. do
5. While 6. Begin 7. For each tính với
được tính bởi công thức trong Mệnh đề 3.7. ; sao cho Chọn 8.
;
; 9. 10. 11. 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 12. Đặt //t là số phần tử của T, T chứa các chuỗi thuộc tính được chọn, nghĩa là
;
13. Đặt
với
14. For j = 1 to t tính độ chính xác phân lớp trên bằng một bộ phân lớp; 15. 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_AA là:
4.2.3. Thực nghiệm và đánh giá thuật toán 4.2.3.1. Mục tiêu thực nghiệm Nhằm đánh giá tính hiệu quả của thuật toán gia tăng filter-wrapper đề xuất IFW_FDAR_AA với thuật toán gia tăng filter FRSA-IFS-HIS(AA) trong công trình [58] về số lượng thuộc tính tập rút gọn và độ chính xác của mô hình phân lớp. FRSA-IFS-HIS(AA) là thuật toán gia tăng filter tìm tập rút gọn sử dụng độ phụ thuộc mờ trong tập thô mờ trong trường hợp bổ sung tập thuộc tính. 4.2.3.2. Dữ liệu thực nghiệm
STT Tập dữ liệu Số đối tƣợng
(1) Bảng 4.1 Bộ dữ liệu thử nghiệm Số thuộc tính ban đầu (5) Số thuộc tính điều kiện (4) (3) Số thuộc tính gia tăng (6) Số lớp quyết định (7)
1 360 90 45 45 15
2 569 30 15 15 2
3 368 22 12 10 2
4 690 15 5 10 2 (2) Libras movement (Libra) Wisconsin diagnostic breast cancer (WDBC) Horse colic (Horse) Credit approval (Credit)
21
5 1000 20 10 10 2 German credit data (German)
6 Waveform (Wave) 5000 21 11 10 3
4.2.3.3. Kết quả so sánh số lượng thuộc tính của tập rút gọn và độ chính xác phân lớp
của hai thuật toán IFW_FDAR_AA và thuật toán FRSA-IFS-HIS(AA)
Hình 4.1 trình bày kết quả so sánh về độ chính xác phân lớp và Hình 4.2 trình bày về số lượng thuộc tính tập rút gọn của hai thuật toán IFW_FDAR_AA và FRSA-IFS-HIS(AA). Kết quả ở các hình này cho thấy, với mỗi bước lặp khi bổ sung tập thuộc tính gia tăng và trên toàn bộ thuộc tính, độ chính xác phân lớp của IFW_FDAR_AA cao hơn FRSA-IFS- HIS(AA) một chút trên tất cả các tập dữ liệu. Hơn nữa, số thuộc tính tập rút gọn của IFW_FDAR_AA nhỏ hơn khá nhiều FRSA-IFS-HIS(AA), đặc biệt trên tập rút gọn có số thuộc tính lớn như Libra. Do đó, thời gian thực hiện và tính khái quát hóa của tập luật phân lớp trên tập rút gọn của IFW_FDAR_AA hiệu quả hơn so với FRSA-IFS-HIS(AA).
Hình 4.1 Độ chính xác phân lớp của IFW_FDAR_AA và FRSA-IFS-HIS(AA)
Hình 4.2 Số lượng thuộc tính tập rút gọn của IFW_FDAR_AA và FRSA-IFS-HIS(AA)
4.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_AA và thuật toán FRSA-IFS-HIS(AA)
Hình 4.3 trình bày kết quả so sánh thời gian thực hiện hai thuật toán IFW_FDAR_AA và FRSA-IFS-HIS(AA) (tính bằng giây s). Kết quả Hình 4.3 cho thấy, thời gian thực hiện của IFW_FDAR_AA cao hơn FRSA-IFS-HIS(AA) trên tất cả các tập dữ liệu, nguyên nhân là IFW_FDAR_AA mất thêm chi phí thời gian thực hiện bộ phân lớp trong giai đoạn wrapper, đây cũng là nhược điểm chung của các thuật toán theo tiếp cận filter-wrapper. Tuy
22
nhiên, với mục tiêu giảm thiểu độ phức tạp và tăng độ chính xác của tập luật phân lớp thì chi phí về thời gian tìm tập rút gọn của thuật toán đề xuất là chấp nhận được.
Hình 4.2 Thời gian thực hiện của IFW_FDAR_AA và FRSA-IFS-HIS(AA) (Tính bằng s)
4.3. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi loại bỏ tập thuộc tính
4.3.1. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính
Mệnh đề 4.3. Cho bảng quyết định với . Giá sử tập thuộc
tính điều kiện B được loại bỏ khỏi C với và là tập thuộc tính còn lại. Đặt
, , tương ứng là ma trận tương ,
đương mờ của các quan hệ tương đương mờ . Khi đó ta có:
4.3.2. 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
Thuật toán IFW_FDAR_DA (Incremental Filter-Wrapper Fuzzy Distance-based Attribute
Reduction Algorithm when Deleting Attributes).
Đầu vào:
1) Bảng quyết định , tập rút gọn , các ma với
trận tương đương mờ , khoảng cách mờ ; ,
2) Tập thuộc tính B loại bỏ khỏi C với ;
Đầu ra: Tập rút gọn của ;
1) Trường hợp 1: If then Retturn (R);
then thực hiện thuật toán không gia tăng filter-
2) Trường hợp 2: If wrapper tìm tập rút gọn sử dụng khoảng cách FW_FDBAR trong mục 2.4 của
Chƣơng 2.
23
then thực hiện các bước của thuật toán tìm tập rút
3) Trường hợp 3: If gọn.
Bước 1: Khởi tạo
1. Đặt ; // Chứa các ứng viên tập rút gọn
; 2.Tính ma trận tương đương mờ ,
3.Đặt //Xét các thuộc tính trong tập rút gọn
Bước 2: Thực hiện thuật toán tìm tập rút gọn // Giai đoạn filter, tìm các ứng viên cho tập rút gọn xuất phát từ tập R.
4. While do
5. Begin
6. For each tính với
được tính bởi công thức trong Mệnh đề 3.9;
7. Chọn sao cho ;
8. ;
;
9. 10. 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
11. Đặt //t là số phần tử của T, T chứa các chuỗi thuộc tính được chọn,
nghĩa là ;
12. Đặt
13. For j = 1 to t tính độ chính xác phân lớp trên bằng một bộ phân lớp;
14. với có độ chính xác phân lớp lớn nhất.
15. Return ;
Trường hợp tốt nhất, thuật toán rơi vào Trƣờng hợp 1, nghĩa là tập rút gọn không
thay đổi.
Trường hợp xấu nhất, thuật toán rơi vào Trƣờng hợp 2, thực hiện lại thuật toán FW_FDAR tìm tập rút gọn trên bảng quyết định sau khi xóa tập thuộc tính B với độ phức
tạp là: .
Trƣờng hợp 3: độ phức tạp của thuật toán IFW_FDAR_DA là
24
KẾT LUẬN
1. Các kết quả đạt đƣợc của Luận án
Luận án 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 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 phân lớp và nâng cao độ chính xác của mô hình phân lớp. Kết quả chính của
luận án bao gồm:
(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 trong Chương 2
(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
trong Chương 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
trong Chương 4
2. Định hƣớng phát triển
(1) Triển khai các thuật toán đề xuất vào việc giải quyết các lớp bài toán trong thực tiễn,
đặc biệt các bài toán có dữ liệu với số thuộc tính lớn (high dimention data) trong các lĩnh
vực khác nhau như dữ liệu gen trong tin sinh học…
(2) Tiếp tục nghiên cứu, đề xuất các thuật toán gia tăng filter-wrapper hiệu quả nhằm
giảm thiểu thời gian thực hiện dựa trên các mô hình tập thô mở rộng khác phù hợp với các
lớp bài toán trong thực tiễn.
