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

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

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

BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT

Ký hiệu, từ viết tắt Diễn giải

Bảng quyết định

Số đối tượng

Số thuộc tính điều kiện trong bảng quyết định

Giá trị của đối tượng tại thuộc tính

Quan hệ tương đương trên B

Phân hoạch của U trên P

Lớp tương đương chứa của phân hoạch

Quan hệ tương đương mờ Quan hệ tương đương mờ 𝑅̃ trên tập thuộc tính P Ma trận tương đương mờ của 𝑅̃𝑃 Phân hoạch mờ trên 𝑅̃𝑃

Lớp tương đương mờ của thuộc phân hoạch mờ

Lực lượng lớp tương đương mờ

Tập xấp xỉ dưới mờ của đối với

Tập xấp xỉ trên mờ của đối với

Khoảng cách mờ giữa hai phân hoạch mờ 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

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

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ó

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

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.

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.

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.

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-

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̉.

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.

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à . 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

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]

Hình 1.2 Cách tiếp cận filter và wrapper trong rút gọn thuộc tính

Từ những ưu nhược điểm của 2 cách tiếp cận trên, nghiên cứu sinh đã nghiên

cứu và đề xuất một số cách tiếp cận mới nhằm kết hợp những ưu điểm của phương

pháp filter, wapper và loại bỏ đi những nhược điểm của nó, nghiên cứu sinh đã đề xuất

một số cách tiếp cận mới, như là: cách tiếp cận kết hợp fifter-wrapper [9, 61]

1.3. Tổng quan về tập thô mờ

Lý thuyết tập thô truyền thống của Pawlak [19] sử dụng quan hệ tương đương

để xấp xỉ tập hợp. Trong khi đó, lý thuyết tập thô mờ (Fuzzy Rough Set) do D.

Dübois và các cộng sự [1] đề xuất sử dụng quan hệ tương đương mờ để xấp xỉ tập

mờ. Giống như lý thuyết tập thô truyền thống, lý thuyết tập thô mờ được xem là công

cụ hiệu quả giải quyết bài toán rút gọn thuộc tính và trích lọc luật trên bảng quyết

định. Cho đến nay, 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ờ tập trung vào hai hướng chính: thứ nhất là rút gọn thuộc tính trên các bảng

quyết định mờ (bảng quyết định với giá trị thuộc tính là các tập mờ); thứ hai là rút

gọn thuộc tính trực tiếp trên bảng quyết định gốc (bảng quyết định không qua bước

rời rạc hóa dữ liệu) nhằm nâng cao độ chính xác của mô hình phân lớp. Luận án

nghiên cứu hướng thứ hai, do đó trong phần này luận án trình bày một số khái niệm

cơ bản về mô hình tập thô mờ trên bảng quyết định. Các khái niệm này được sử dụng

trong các chương sau của luận án.

1.3.1. Bảng quyết định và quan hệ tương đương

Bảng quyết định là một cặp trong đó U là tập hữu hạn, khác

rỗng các đối tượng; C là tập thuộc tính điều kiện, D là tập thuộc tính quyết định với

Lý thuyết tập thô truyền thống của Pawlak [19] sử dụng quan hệ tương đương để

xấp xỉ tập hợp. Xét bảng quyết định , mỗi tập con thuộc tính xác

định một quan hệ tương đương trên miền giá trị thuộc tính, ký hiệu là .

Với là giá trị thuộc tính a tại đối tượng x. Quan hệ xác định một phân

hoạch trên U, ký hiệu là với là lớp tương đương chứa

đối tượng x, . Với , tập xấp xỉ dưới và xấp xỉ trên của X

tương ứng là và . Cặp được

gọi là tập thô (rough set) của X đối với

1.3.2. Quan hệ tương đương mờ

Định nghĩa 1.1. [1] Cho bảng quyết định , một quan hệ xác

định trên miền giá trị thuộc tính được gọi là quan hệ tương đương mờ nếu thỏa mãn

các điều kiện sau với mọi

1) Tính phản xạ (reflexive): ;

2) Tính đối xứng (symetric): ;

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 bảng quyết định và quan hệ tương

đương mờ . Ký hiệu , xác định trên tập thuộc tính tương ứng là quan hệ

P, Q. Khi đó, với mọi ta có:

Một số quan hệ tương đương mờ được sử dụng trong bài toán rút gọn thuộc tính:

1) Trong các công trình [62, 63, 64], các tác giả sử dụng quan hệ tương đương mờ theo

(1.1)

công thức (1.1) trên thuộc tính có miền giá trị số

với là giá trị của thuộc tính a tại đối tượng , tương ứng là giá

trị lớn nhất, nhỏ nhất của thuộc tính .

2) Trong các công trình [9], các tác giả sử dụng quan hệ tương đương mờ theo công

thức (1.2) trên thuộc tính có miền giá trị thực thuộc đoạn [0, 1].

(1.2)

Trong trường hợp giá trị thuộc tính a không thuộc đoạn [0, 1], các tác giả sử

dụng một phương pháp tiền xử lý để ánh xạ miền giá trị thuộc tính a về đoạn [0, 1].

Ngoài ra, một số công trình [53] sử dụng quan hệ tương đương mờ

trên thuộc tính có miền giá trị số thuộc đoạn [0, 1].

3) Trên các thuộc tính

có miền giá trị định danh (nominal) hoặc nhị phân (binary), các tác giả sử dụng quan hệ tương đương. Quan hệ tương đương được xem là

quan hệ tương đương mờ theo công thức (1.3) như sau:

1.3.3. Ma trận tương đương mờ

Ma trận tương đương mờ là công cụ biểu diễn giá trị quan hệ tương đương mờ

giữa các đối tượng của bảng quyết định và được định nghĩa như sau:

Định nghĩa 1.2.[58] Cho bảng quyết định với

và là quan hệ tương đương mờ xác định trên tập thuộc tính

. Khi đó, ma trận tương đương mờ biểu diễn , ký hiệu là

được định nghĩa như sau:

với là giá trị của quan hệ giữa hai đối tượng và trên tập

thuộc tính P, , .

phụ thuộc vào

Như vậy, giá trị các phần tử của ma trận tương đương mờ

quan hệ tương đương mờ được chọn. Mặt khác, ma trận tương đương mờ là cơ sở để

xây dựng các độ đo sử dụng để giải quyết bài toán rút gọn thuộc tính trong bảng quyết

định. Do đó, việc lựa chọn các quan hệ tương đương mờ ảnh hưởng đến kết quả thực hiện

các phương pháp rút gọn thuộc tính.

1.3.4. Phân hoạch mờ

Mệnh đề 1.2.[64] Cho bảng quyết định và . Giả sử

, tương ứng là ma trận tương đương mờ của ,

khi đó ma trận tương đương mờ trên tập thuộc tính là:

với

Định nghĩa 1.3.[64] Cho bảng quyết định với ,

và là quan hệ tương đương mờ trên P. Khi đó phân hoạch mờ trên

sinh bởi , ký hiệu là: được xác định như sau:

(1.4)

với là một tập mờ đóng vai trò là một lớp tương

đương mờ (fuzzy equivalent class) của đối tượng .

Với lớp tương đương mờ , hàm thuộc của các của các đối tượng

được xác định bởi và lực lượng của lớp đương

đương mờ được tính bởi .

Gọi là tập tất cả các phân hoạch mờ trên U xác định bởi các quan hệ tương

đương mờ trên các tập thuộc tính, khi đó được gọi là một không gian phân hoạch

mờ trên U. Như vậy, một không gian phân hoạch mờ được xác định bởi quan hệ

tương đương mờ định nghĩa trực tiếp trên miền giá trị thuộc tính.

Định nghĩa 1.4. Xét phân hoạch mờ sinh bởi quan hệ tương

đương mờ với , có 2 trường hợp đặc biệt xảy ra:

(1) Nếu (với thì , , phân hoạch

mờ được gọi là mịn nhất ký hiệu là .

(2) Nếu với thì , , phân hoạch mờ được

gọi là thô nhất (roughest) ký hiệu là .

Định nghĩa 1.5 [64]. Xét hai phân hoạch mờ , quan hệ thứ

tự bộ phận được định nghĩa như sau:

, viết tắt là .

Dấu đẳng thức viết tắt là

và , viết tắt là .

Ví dụ 1.1. Cho bảng quyết định trong Bảng 1.1 với

và

𝑐1 0.5 0.8 0.2 0.2

𝑐2 0.6 0.6 0.2 0.8

𝑐3 0.8 0.8 1.0 0.6

D 1 1 0 0

𝑐4 0.4 0.4 0.6 0.6

U 𝑢1 𝑢2 𝑢3 𝑢4

Bảng 1.1 Bảng quyết định của Ví dụ 1.1

Luận án dùng quan hệ tương đương mờ trong [9] trên mỗi thuộc tính điều kiện

như sau: với và

Giả sử rằng , ta có:

và

Phân hoạch mờ trên như sau:

với

Cho , , tính toán tương tự ta có

với: ,

, ,

Và với ,

, ,

Điều đó chỉ ra rằng và .

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ờ

Kể từ khi Lý thuyết tập thô mờ (Fuzzy rough set) do Dübois và các cộng sự

[1] đề xuất, các phương pháp rút gọn thuộc tính trên bảng quyết định theo tiếp cận

tập thô mờ đã thu hút sự quan tâm của cộng đồng nghiên cứu. Trong phần này, luận

án trình bày tóm tắt 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ờ

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

Các phương pháp rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô

mờ đều dựa trên các phương pháp rút gọn thuộc tính theo tiếp cận tập thô đã được

nghiên cứu lâu nay. Đây là các phương pháp heuristic theo tiếp cận filter, bao gồm các

bước xây dựng độ đo, định nghĩa tập rút gọn và độ quan trọng của thuộc tính sử dụng

độ đo được xây dựng, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn theo

tiêu chuẩn là độ quan trọng của thuộc tính. Việc đánh giá độ chính xác của mô hình

phân lớp được thực hiện sau khi tìm được tập rút gọn. Cho đến nay, 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ờ tập trung vào các phương

pháp chính như: phương pháp sử dụng hàm thuộc mờ, phương pháp sử dụng miền

dương mờ, các phương pháp sử dụng entropy mờ, phương pháp sử dụng khoảng cách

mờ và một số phương pháp mở rộng gần đây.

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

Anoop Kumar Tiwari 2018, [3]

Các thuật toán tìm tập rút gọn sử dụng hàm thuộc mờ 1

STT 1) Hàm thuộc mờ   Z. Wang và cộng sự 2017, [4]  Zhang và cộng sự 2018, [5]

2) Miền dương mờ

T.K. Sheeja và cộng sự 2018, [6] 2 Các phương pháp sử dụng miền dương mờ   Y. Lin và cộng sự 2018, [7]

3) Entropy mờ

Các thuật toán tìm tập rút gọn sử dụng phương pháp entropy mờ. 3

 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) Phương pháp sử dụng khoảng cách mờ

4 Các thuật toán tìm tập rút gọn sử dụng độ đo phương pháp khoả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

Các thuật toán tìm tập rút gọn sử dụng một số phương pháp khác

 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 điểm chung của các nghiên cứu liên quan

Từ các nghiên cứu liên quan được trình bày ở phần 1.4.1.1, tác giả tổng kết các

phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ có các điểm chung như sau:

1) Các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ có độ chính xác

phân lớp cao hơn các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền

thống. Điều này được thể hiện ở các kết quả thử nghiệm trên các tập dữ liệu mẫu trong

các công bố.

2) Mục tiêu chung của các phương pháp đề xuất là nâng cao độ chính xác phân

lớp, tối thiểu hóa số thuộc tính của tập rút gọn và thời gian thực hiện. Vì vậy, các

phương pháp đã đề xuất trong luận án đều cố gắng cải thiện độ chính xác mô hình

phân lớp, rút gọn thuộc tính và cải thiện đáng kể thời gian thực hiện so với các phương

pháp trước đó.

3) Giống như các phương pháp rút gọn thuộc tính theo tiếp cận tập thô, các

phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ là các phương pháp heuristic

theo tiếp cận filter. Nghĩa là, độ chính xác phân lớp được đánh giá sau khi tìm được

tập rút gọn. Các phương pháp bao gồm 03 bước chính: (1) Xây dựng độ đo, (2) xây

dựng tập rút gọn và độ quan trọng của thuộc tính dựa trên độ đo và (3) xây dựng thuật

toán heuristic tìm một tập rút gọn theo tiêu chuẩn độ quan trọng của thuộc tính.

1.4.1.3 Các vấn đề còn tồn tại

Các thuật toán đã đề xuất được trình bày trong Bảng 1.2 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 là tập rút gọn thu được là

tập thuộc tính tối thiểu bảo toàn độ đo được định nghĩa. Việc đánh giá độ chính xác

của mô hình phân lớp được thực hiện sau khi tìm được tập rút gọn. Do đó, tập rút gọn

của các thuật toán filter nêu trên chưa tối ưu về số lượng thuộc tính và độ chính xác

phân lớp.

1.4.1.4 Đề xuất nghiên cứu của luận án

Trong các độ đo được sử dụng trong các thuật toán trong Bảng 1.2, khoảng

cách mờ được chứng minh là độ đo hiệu quả giải quyết bài toán rút gọn thuộc tính

trong bảng quyết định. Động lực nghiên cứu thứ nhất là nghiên cứu, đề xuất các

thuật toán tìm tập rút gọn theo hướng tiếp cận kết hợp filter-wrapper sử dụng

độ đo khoảng cách mờ, là sự kết hợp giữa tiếp cận lọc (filter) và đóng gói

(wrapper). Với cách tiếp cận này, giai đoạn filter tìm ra các tập rút gọn xấp xỉ, giai

đoạn wrapper sử dụng các bộ phân lớp để tính độ chính xác của các tập rút gọn xấp

xỉ và tìm ra tập rút gọn xấp xỉ có độ chính xác phân lớp cao nhất, đồng thời giảm

thiểu số lượng thuộc tính tập rút gọn.

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ờ

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. Trong đó, trường hợp bổ sung, loại bỏ tập

thuộc tính xuất hiện ngày càng phổ biến. Ví dụ bài toán chuẩn đoán bệnh trong lĩnh

vực y tế, các triệu chứng lâm sàng được xem như các thuộc tính ban đầu để bác sĩ

chẩn đoán bệnh. Sau đó, các chỉ số xét nghiệm được xem như các thuộc tính tiếp

theo liên tục được bổ sung, cập nhật nhằm hỗ trợ bác sĩ trong việc nâng cao độ chính

xác chẩn đoán. Để 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. Việc áp dụng các

thuật toán tìm tập rút gọn theo phương pháp truyền thống gặp nhiều thách thức. Với

trường hợp bảng quyết định có kích thước lớn, việc thực hiện các thuật toán tìm tập

rút gọn gặp khó khăn do hạn chế về không gian lưu trữ và tốc độ tính toán. Với

trường hợp bảng quyết định thay đổi, cập nhật, các thuật toán này phải tính toán lại

tập rút gọn trên toà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ể. Để vượt qua các thách thức trên, các nhà nghiên cứu đề

xuất hướng tiếp cận tính toán gia tăng tìm tập rút gọn. Các thuật toán gia tăng chỉ cập

nhật lại tập rút gọn trên phần dữ liệu bị thay đổi mà không tính lại tập rút gọn trên

toàn bộ bảng quyết định. Với các bảng quyết định thay đổi, cập nhật, các thuật toán

gia tăng giảm thiểu đáng kể thời gian thực hiện. Hơn nữa, các thuật toán gia tăng có

thể thực hiện được trên các bảng quyết định kích thước lớn bằng giải pháp chia nhỏ

bảng quyết định thành nhiều phần, sau đó tập rút gọn được tính khi lần lượt bổ sung

từng phần vào bảng quyết định.

Hướng tiếp cận tính toán gia tăng tìm tập rút gọn đã và đang thu hút sự quan

tâm của các nhà nghiên cứu trong suốt hơn hai thập kỷ qua. Trong phần này, tác giả

trình bày các nghiên cứu liên quan đến các thuật toán gia tăng tìm tập rút gọn của bảng

quyết định theo tiếp cận tập thô mờ, trên cơ sở đó đưa ra các vấn đề còn tồn tại và

động lực nghiên cứu của luận án.

1.4.2.1. Các nghiên cứu liên quan đến thuật toán gia tăng tìm tập rút gọn theo tiếp cận

tập thô mờ

Các hướng nghiên cứu được liệt kê tóm tắt trong bảng dưới đây:

Bảng 1.3 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

 Demetrovics, J., Thi, V.D., & Giang,

Các thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách 1 

N.L. [20], 2014 Huong, N. T. L., &Giang, N. L. [ 21], (2016)

Các thuật toán gia tăng tìm tập rút gọn sử dụng hạt thông tin

Các thuật toán gia tăng tìm tập rút gọn sử dụng ma trận phân biệt

Các thuật toán gia tăng tìm tập rút gọn sử dụng miền dương 4

 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]

 Shu và cộng sự 2020, [38] 7

 Xie và cộng sự 2018, [39] 8

 Y.Y. Yang và cộng sự 9 Các thuật toán gia tăng tìm tập rút gọn sử dụng hàm thuộc Các thuật toán gia tăng tìm tập rút gọn sử dụng quan hệ không phân biệt được Các thuật toán gia tăng tìm tập rút gọn sử dụng entropy thông tin Thuật toán gia tăng tìm tập rút gọn sử dụng độ đo không nhất quán Các thuật toán gia tăng tìm tập rút gọn sử dụng lựa chọn mẫu kích hoạ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]

 Yang và các cộng sự 2017, [54]

Thuật toán gia tăng FIAT tìm tập rút gọn sử dụng độ phụ thuộc mờ. Các thuật toán gia tăng IARM tìm tập rút gọn sử dụng quan hệ phân biệt mờ. Các thuật toán gia tăng IV-FS-FRS- 1 và IV-FS-FRS-2 tìm tập rút gọn sử dụng quan hệ phân biệt mờ.

gia  Giang và các cộng sự 2020, [55]

 Zhang và các cộng sự 2020, [56]

 Ni và các cộng sự 2020, [57]

tăng toán thuật Các IFW_FDAR_AdObj và IFW_FDAR_DelObj tìm tập rút gọn sử dụng quan hệ khoảng cách mờ. Thuật toán gia tăng AIFWAR tìm tập rút gọn sử dụng entropy có điều kiện mở rộng Thuật toán gia tăng DIAR sử dụng hàm thuộc mờ và thuật toán PIAR sử dụng miền dương mờ tìm tập rút gọ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

 F. Wang và cộng sự 2013, [42] 17

Thuật toán gia tăng tìm tập rút gọn sử dụng miền dương Thuật toán gia tăng tìm tập rút gọn sử dụng entropy thông tin Thuật toán gia tăng tìm tập rút gọn sử dụng ma trận phân biệt. 18

 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, 20 [48]

 M.S. Raza và cộng sự 2016, [49]

Thuật toán gia tăng tìm tập rút gọn sử dụng quan hệ không phân biệt. Thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách. Thuật toán gia tăng tìm tập rút gọn sử dụng độ phụ thuộc của thuộc tính. Các thuật toán gia tăng tìm tập rút gọn sử dụng hạt tri thức. 22  Y. Jing và cộng sự 2016, [50]  Y.G. Jing và cộng sự 2018, [51]

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

1.4.2.2 Các vấn đề còn tồn tại

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ờ nêu trên có thời

gian thực hiện nhỏ hơn đáng kể các thuật toán không gia tăng và có thể thực thi trên

các bảng dữ liệu kích thước lớn. Tuy nhiên, các thuật toán nêu trên đều theo hướng

tiếp cận lọc truyền thống (filter). Trong đó, 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 định nghĩa (hàm thuộc mờ, quan hệ phân biệt…), 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 tìm được của các thuật toán nêu trên chưa tối ưu cả về số lượng thuộc tính và độ

chính xác phân lớp, nghĩa là tập rút gọn tìm được chưa chắc có độ chính xác phân lớp

tốt nhất.

1.4.2.3 Các đề xuất của luận án

Từ vấn đề còn tồn tại của các thuật toán gia tăng đã trình bày ở trên, động lực

nghiên cứu của luận án là:

1) 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 theo tiếp cận kết hợp filter-wrapper nhằm giảm thiểu số lượng

thuộc tính tập rút gọn, trong khi cố gắng bảo toàn và cải thiện độ chính xác

mô hình phân lớp.

2) 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 kết

hợp được nghiên cứu, đề xuất trong các trường hợp: bổ sung, loại bỏ tập đối

tượng; bổ sung, loại bỏ tập thuộc tính.

1.5. Tóm tắt các đóng góp của luận án

Dựa trên lý thuyết tập thô mờ, luận án đề xuất các thuật toán cải tiến tìm tập rút

gọn theo tiếp cận tập thô mờ bằng thuật toán kết hợp filter-wrapper nhằm giải

quyết các vấn đề còn tồn tại được trình bày ở mục 1.4.1 và 1.4.2 với hai đóng góp 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

theo tiếp cận tập thô mờ: Thuật toán sử dụng khoảng cách mờ. Độ đo

khoảng cách mờ được xây dựng là mở rộng của độ đo khoảng cách trong công

trình [65]. Các đóng góp này được trình bày ở Chương 2 của luận án và được

công bố trong các công trình 1, 2 phần “Danh mục công trình của tác giả”.

2) Đề xuất các thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng

quyết định trong trường hợp bổ sung, loại bỏ tập đối tượng và bổ sung,

loại bỏ tập thuộc tính. Các đóng góp này được trình bày ở Chương 3 và

Chương 4 của luận án và được công bố trong công trình 1,3,4 phần “Danh

mục công trình của tác giả”.

1.6. Kết luận chương 1

Trong chương 1 luận án đã nêu tổng quan về những vấn đề cơ bản:

Tổng quan về rút gọn thuộc tính, các hướng tiếp cận fifter - wrapper trong rút

gọn thuộc tính; một số khái niệm cơ bản về tập thô mờ nhằm giải quyết bài toán rút

gọn thuộc tính. Ngoài ra, chương 1 còn trình bày tổng quan về rút gọn thuộc tính từ

đó đưa ra các thuật toán fifter-wrapper về tìm tập rút gọn của bảng quyết định và định

hướng nghiên cứu của luận án. Các khái niệm được trình bày ở chương 1 là kiến thức

nền tảng được sử dụng trong các chương sau của luận án.

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 của PGS.TS Nguyễn Long Giang và

cộng sự đã sử dụng các độ đo khoảng cách để giải quyết bài toán rút gọn thuộc tính

trong bảng quyết định theo tiếp cận tập thô truyền thống [48, 66, 67, 68] và bảng quyết

định không đầy đủ theo tiếp cận tập thô dung sai [66, 69, 70, 71, 72]. Đáng chú ý theo

tiếp cận tập thô mờ, nhóm nghiên cứu đã mở rộng các độ đo khoảng cách đã đề xuất

thành các độ đo khoảng cách mờ và đã có một số kết quả trong việc sử dụng độ đo

khoảng cách mờ để giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền

giá trị số. Trong công trình [73], nhóm tác giả xây dựng độ đo khoảng cách Jaccard

mờ giữa hai tập thuộc tính dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn và

chứng minh một số tính chất của nó. Trong công trình [74], các tác giả đã sử dụng

khoảng cách Jaccard mờ trong [73] để 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 có miền giá trị số. Trong công trình [12], các tác giả xây

dựng độ đo khoảng cách mờ và sử dụng khoảng cách mờ giải quyết bài toán rút gọn

thuộc tính trên bảng quyết định có miền giá trị số.

Tiếp tục hướng nghiên cứu này, với mục tiêu tìm kiếm các độ đo khoảng cách

hiệu quả (có công thức tính toán đơn giản) giải quyết bài toán rút gọn thuộc tính, giảm

thiểu thời gian thực hiện, trong chương này luận án đề xuất độ đo khoảng cách mờ

(sau đây gọi là khoảng cách mờ) dựa trên độ đo khoảng cách phân hoạch trong công

trình [65]. Sử dụng khoảng cách mờ được xây dựng, luận án đề xuất phương pháp

filter-wrapper rút gọn thuộc tính trong bảng quyết định nhằm nâng cao độ chính xác

phân lớp và giảm thiểu số lượng thuộc tính tập rút gọn. Bao gồm các nội dung sau:

(1) Xây dựng khoảng cách giữa hai tập mờ;

(2) Xây dựng khoảng cách mờ giữa hai phân hoạch mờ;

(3) Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ;

(4) Thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách mờ;

(5) Thử nghiệm và đánh giá tính hiệu quả của các thuật toán đề xuất.

Các kết quả trong chương này được công bố trong các công trình 1, 2 phần

“Danh mục công trình của tác giả”.

2.2. Xây dựng khoảng cách giữa hai tập mờ

Trong hệ thông tin, mỗi tập thuộc tính sinh ra một tri thức về tập các đối

tượng, trong đó mỗi phần tử của tri thức là một lớp tương đương, hay một khối.

Khoảng cách cho phép đánh giá độ gần nhau (hay độ tương đương) giữa các tri thức,

nghĩa là khoảng cách giữa hai tri thức càng nhỏ thì hai tri thức đó càng gần nhau,

hay càng tương đương nhau và ngược lại. Như vậy, khi một khoảng cách nào đó

được định nghĩa trên tập các tri thức thì cũng có nghĩa là một khoảng cách đã được

xác lập trên tập các thuộc tính. Sử dụng khoảng cách để đánh giá sự khác nhau giữa

các thuộc tính, phát hiện các thuộc tính quan trọng [63, 66, 67, 75]. Nhờ đó, xây

dựng thuật toán hiệu quả để giải quyết bài toán rút gọn thuộc tính trong lý thuyết tập

thô mờ.

Kế thừa sự thành công của kỹ thuật rút gọn thuộc tính sử dụng khoảng cách

phân hoạch theo tiếp cận tập thô truyền thống [76] luận án đề xuất thuật toán heuristic

để rút gọn thuộc tính của bảng quyết định miền giá trị thực sử dụng khoảng cách mờ.

Khoảng cách mờ giữa hai tập thuộc tính được xây dựng dựa trên khoảng cách mờ giữa

hai tập mờ. Kết quả thực nghiệm trên một số bộ số liệu lấy từ kho dữ liệu UCI[59] cho

thấy, phương pháp đề xuất cải thiện độ chính xác phân lớp dữ liệu tốt hơn so với các

công bố trước đây [77].

Đầu tiên trong chương này luận án xây dựng độ đo khoảng cách giữa hai tập

mờ, gọi là khoảng cách mờ.

Cho bảng quyết định với

và hai phân hoạch trên P và Q, với ,

, Liang và cộng sự [65] chứng minh rằng:

là khoảng cách phân hoạch giữa và với là lực lượng của X. Luận án

mở rộng khoảng cách này để xây dựng khoảng cách mờ.

2.2.1. Độ đo khoảng cách mờ

Bộ đề 2.1 [12]. Cho 3 tập mờ 𝑋, 𝑌, 𝑍 trên tập đối tượng U, khi đó ta có:

Mệnh đề 2.1. Cho 2 tập mờ 𝑋, 𝑌 trên tập đối tượng U, khi đó

là khoảng cách giữa 𝑋 và 𝑌.

Chứng minh: Đầu tiên, bất đẳng thức suy ra .

Hơn nữa, ta có . là độ đo khoảng cách nếu nó thỏa mãn

bất đẳng thức tam giác. Không mất tính tổng quát, ta cần chứng minh

. Theo Bộ đề 2.1, ta có:

(1)

(2)

Cộng (1) và (2) vế theo vế, ta có:

(3)

Với 2 số bất kì a, b, ta có . Khi đó, ta có

với mọi . Điều này

có nghĩa là . Từ (3), ta có:

Hoặc .

Từ đó, là 1 độ đo khoảng cách giữa hai tập mờ X và Y.

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 đó: (2.1)

Là một khoảng cách mờ giữa hai phân hoạch mờ và , gọi là

khoảng cách mờ.

Chứng minh: Rõ ràng và

. Chúng ta cần chứng minh (2.1) thỏa mãn

bất đẳng thức tam giác. Không mất tính tổng quát với mọi , , , ta

cần chứng minh:.

Theo Mệnh đề 2.1, vói mọi ta có

. Từ đó, ta cũng có:

Giá trị của đạt giá trị nhỏ nhất là 0 khi và chỉ khi

. Giá trị của đạt giá trị lớn nhất là (nếu và

chỉ nếu và ) (hoặc và ). Do

đó,

Ví dụ 2.1 (Tiếp tục từ Ví dụ 1.1), theo Mệnh đề 2.2, khi đó ta có

, ,

Vì vậy:

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 mờ giữa hai tập thuộc tính C và được xác định như sau:

(2.2)

Chứng minh:

Từ Mệnh đề 2.2, ta có:

Nếu thì khoảng cách mờ đạt giá trị nhỏ nhất khi

, nếu và for thì khoảng

cách mờ đạt giá trị lớn nhất . Do đó,

Mệnh đề 2.4. Cho bảng quyết định với, và là quan hệ

tương đương mờ trên miền giá trị tập thuộc tính điều kiện. Khi đó

Chứng minh: Từ , theo [29] ta có . Nghĩa là

với  với . Xét đối tượng , ta có:

(1) với ta có , do đó

(2) với ta có , vì vậy

Từ (1) và (2) ta có:

xảy ra khi và chỉ khi

với mọi .

Mệnh đề 2.4 cho thấy thỏa mãn tính phản đơn điệu với

tập thuộc tính điều kiện. Nghĩa là với mọi tập thuộc tính điều kiện B càng nhỏ,

khoảng cách mờ càng lớn. Do đó, có

thể được sử dụng làm tiêu chuẩn lựa chọn thuộc tính trong thuật toán tìm tập rút gọn,

được trình bày ở mục tiếp theo.

2.3. Thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ

Trong mục này, chúng tôi trình bày phương pháp rút gọn thuộc tính sử dụng

khoảng cách mờ theo tiếp cận filter. Giống các phương pháp filter khác theo tiếp cận

tập thô, phương pháp đề xuất bao gồm các bước:

(1) Định nghĩa tập rút gọn dựa trên khoảng cách mờ;

(2) Định nghĩa độ quan trọng của thuộc tính dựa trên khoảng cách mờ;

(3) Xây dựng thuật toán filter tìm tập rút gọn sử dụng khoảng cách mờ;

(4) Độ chính xác phân lớp được đánh giá sau khi tìm được tập rút gọn.

Định nghĩa 2.1. Bảng quyết định và 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 . Nếu:

Thì B là tập rút gọn của bảng quyết định sử dụng khoảng cách mờ.

Định nghĩa 2.2. Bảng quyết định với và . Độ

quan trọng của thuộc tính 𝑏 đối với 𝐵 được định nghĩa bởi:

(2.3)

Theo tính chất của khoảng cách mờ (Mệnh đề 2.4) ta có . Độ quan

trọng đặc trưng cho chất lượng phân lớp của thuộc tính b đối với thuộc tính

quyết định D và được sử dụng làm tiêu chuẩn lựa chọn thuộc tính cho thuật toán filter

F_FDBAR tìm tập rút gọ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ờ.

, quan hệ tương Đầu vào: Bảng quyết định

đương mờ xác định trên tập thuộc tính điều kiện.

Đầ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

do 3. While

tính 4. Begin 5. Với mỗi

sao cho ; 6. Chọn

; 7.

8. End;

//Loại bỏ các thuộc tính dư thừa trong B nếu có

9. For each 10. Begin

; 11. Tính

then 12. If

;

13. End; 14. Return ;

Tiếp theo, luận án đánh giá độ phức tạp thời gian của thuật toán F_FDBAR, gọi

tắt là độ phức tạp. Giả sử và ký hiệu tương ứng là số thuộc tính điều kiện

và số đối tượng. Độ phức tạp tính ma trận tương đương mờ là , do đó

độ phức tạp tính khoảng cách mờ trong câu lệnh 2 là . Xét vòng lặp While từ

câu lệnh 3 đến 8, để tính ta phải tính vì

đã được tính ở bước trước. Độ phức tạp tính

bằng độ phức tạp tính ma trận tương đương mờ của thuộc

tính a, nghĩa là . Do có hai vòng lặp lồng nhau theo nên độ phức tạp của vòng

lặp While là . Tương tự, độ phức tạp của vòng lặp For từ dòng lệnh số 9 đến

13 là . Do đó, độ phức tạp của thuật toán F_FDBAR là

Ví dụ 2.2. Xét bảng quyết định cho ở Bảng 2.1 với

, , . Với các thuộc tính điều kiện,

chúng tôi sử dụng quan hệ tương đương mờ trên thuộc tính trong [10] như sau:

ới

Với thuộc tính quyết định D chúng tôi sử dụng quan hệ tương đương .

0.8

0.2

0.6

0.4

0.8

0.2

0.6

0.8

0.2

0.6

0.4

0.8

0.2

0.4

0.6

0.4

0.6

0.4

0.6

0.4

0.6

Bảng 2.1 Bảng quyết định của Ví dụ 2.2

Áp dụng các bước của thuật toán F_FDBAR tìm tập rút gọn, ta có:

Khởi tạo ; . Tính các ma trận tương đương mờ

Từ đó ta có: ,

, ,

Chọn có giá trị lớn nhất và .

Do nên tiếp tục vòng lặp

While,

ta có: ; ; ;

; .

Chọn có độ quan trọng lớn nhất và .

Tính nên tiếp

tục vòng lặp While.

Ta có ; ; ;

. Chọn có độ quan trọng lớn nhất và .

Do nên

thuật toán dừng và là tập rút gọn tìm được của thuật toán.

Xét bảng quyết định với và là quan hệ

tương đương mờ xác định trên miền giá trị thuộc tính điều kiện. Đặt

. Theo thuật toán F_FDBAR, giả sử các thuộc tính

được thêm vào tập rỗng theo giá trị lớn nhất của độ quan trọng thuộc tính cho đến khi

tồn tại sao cho . Kết thúc thuật

toán, ta thu được tập rút gọn , độ chính xác phân lớp trên tập dữ liệu

được tính bởi độ chính xác phân lớp trên B. Do đó, thuật toán F_FDBAR theo hướng

tiếp cận filter truyền thống.

Mặt khác, theo Mệnh đề 2.4 ta có

Với ngưỡng cho

trước, đặt thỏa mãn và

. Khi đó, được gọi là tập rút gọn xấp xỉ ngưỡng

. Nếu và được sử dụng để xây dựng bộ phân lớp, công bố [9]

cho thấy, độ chính xác phân lớp trên chưa chắc đã tốt hơn trên .

Giả sử có độ chính xác phân lớp tốt hơn . Khi đó, nếu chọn là

kết quả của thuật toán thì có độ chính xác phân lớp cao hơn, có số lượng thuộc tính

ít hơn nên khả năng khái quát hóa và hiệu năng thực hiện các thuật toán phân lớp sẽ

cao hơn. Điều đó dẫn đến hướng tiếp cận kết hợp tìm tập rút gọn xấp xỉ, là sự kết hợp

giữa filter (lọc) và wrapper (gói). Phương pháp filter tìm ra các tập rút gọn xấp xỉ,

phương pháp wrapper kiểm tra độ chính xác phân lớp của các tập rút gọn xấp xỉ để

chọn tập rút gọn có độ chính xác cao nhất. Với hướng tiếp cận này, độ chính xác phân

lớp trên tập rút gọn tìm được cao hơn so với các phương pháp filter truyền thống. Tuy

nhiên, thời gian thực hiện sẽ lớn hơn vì phải thực hiện các bộ phân lớp.

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 gọn xấp xỉ sử dụng khoảng cách mờ được

mô tả 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ờ.

, quan hệ tương Đầu vào: Bảng quyết định

đương mờ 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ỉ có độ chính xác phân

lớp tốt nhất.

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

do 3. While

tính 4. Begin 5. Với mỗi

;

; sao cho 6. Chọn

; 7.

8. 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 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 pháp 10-fold;

với có độ chính xác phân lớp lớn nhất. 14. End 15.

Return ;

Tiếp theo, chúng tôi đánh giá độ phức tạp thời gian của thuật toán filter-wrapper

FW_FDBAR, gọi tắt là độ phức tạp. Giả sử và ký hiệu tương ứng là số

thuộc tính điều kiện và số đối tượng của DS. Theo mục 2.3, độ phức tạp của thuật toán

filter F_FDBAR là , do đó độ phức tạp của giai đoạn filter (từ câu lệnh 3

đến 8) là . Độ phức tạp của giai đoạn wrapper (từ câu lệnh số 9 đến số 15)

phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ phức tạp của bộ

phân lớp là , khi đó độ phức tạp của giai đoạn wrapper là . Vì vậy, độ

phức tạp của thuật toán FW_FDBAR 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

Theo hướng tiếp cận filter, các tác giả trong công trình [12] đã xây dựng một độ

đo khoảng cách mờ và xây dựng thuật toán filter tìm tập rút gọn sử dụng khoảng cách

mờ, gọi là thuật toán FPDAR (Fuzzy Partition Distance Based Attribute Reduction).

Các tác giả trong [12] cũng chỉ ra bằng thực nghiệm thuật toán FPDAR hiệu quả hơn

các thuật toán sử dụng miền dương mờ và entropy mờ về thời gian thực hiện và độ

chính xác phân lớp. Hơn nữa, công thức khoảng cách mờ trong [12] đơn giản hơn công

thức khoảng cách Jaccard mờ trong [74] nên thuật toán FPDAR hiệu quả hơn thuật

toán trong [74] về thời gian thực hiện.

Theo hướng tiếp cận filter-wrapper, gần đây Zhang và các cộng sự [9] đề xuất

thuật toán filter-wrapper FEBAR (Fuzzy Entropy Based Attribute Reduction) tìm tập

rút gọn xấp xỉ sử dụng độ đo -entropy mờ, là cải tiến của độ đo entropy mờ trong

[8,78, 79]. Để tính -entropy mờ cần mất chi phí tính hệ số  dựa vào miền dương mờ.

Do đó, chi phí thời gian của FEBAR sẽ tăng lên.

Mục tiêu của thực nghiệm là:

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 gọ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 gọn và độ chính

xác phân lớp.

2.5.2. Số liệu, phương pháp và môi trường thực nghiệm

Việc thực nghiệm được thực hiện trên 8 bộ dữ liệu mẫu lấy từ kho dữ liệu UCI

[59] cho ở Bảng 2.2. Trên mỗi bộ dữ liệu, với mỗi thuộc tính a có miền giá trị thực,

chúng tôi chuẩn hóa về miền [0, 1] như sau với

với max(a), min(a) là giá trị lớn nhất, nhỏ nhất trên miền giá trị thuộc tính a. Luận án

sử dụng quan hệ tương đương mờ trên thuộc tính a trong [9, 54] như sau

với

Với các thuộc tính a có miền giá trị định danh (nominal) hoặc phân loại

(catergorized), chúng tôi sử dụng quan hệ tương đương mờ , với

Bảng 2 2 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ả

Thuộc tính định danh (nominal)

Lympho

1 2 Wine Libra 3

148 178 360

18 13 90

18 0 0

Thuộc tính thực (Real- valued) 0 13 90

2 3 15

4 WDBC

569

Lymphography Wine Libras movement Wisconsin diagnostic breast cancer

5 6 7 8

Horse Heart Credit German

Horse colic Statlog (heart) Credit approval German credit data

368 270 690 1000

22 13 15 20

15 7 9 13

7 6 6 7

2 2 2 2

Với các thuật toán filter-wrapper FW_FDBAR và FEBAR [9], chúng tôi sử dụng

bộ phân lớp CART (cây phân lớp, hồi quy) để tính độ chính xác phân lớp trong giai

đoạn wrapper. Với thuật toán filter FPDAR [12], chúng tôi cũng sử dụng bộ phân lớp

CART để tính độ chính xác phân lớp sau khi tìm được tập rút gọn. Chúng tôi sử dụng

phương pháp kiểm tra chéo 10-fold, nghĩa là bộ dữ liệu được chia thành 10 phần xấp

xỉ bằng nhau, lấy ngẫu nhiên 1 phần làm bộ dữ liệu kiểm tra, 9 phần còn lại làm dữ

liệu huấn luyện. Quá trình được lặp lại 10 lầ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 bình (mean) của 10 lần lặp và là

sai số chuẩn (standard error). Công cụ lập trình thực nghiệm là ngôn ngữ lập trình C#

và công cụ phân tích dữ liệu R.

Môi trường thực nghiệm là máy tính PC với cấu hình Intel(R) Core(TM) i7-

3770CPU @3.40 GHz, sử dụng hệ điều hành Windows 7, 32 bit.

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

Kết quả so sánh độ chính xác phân lớp và số lượng thuộc tính tập rút gọn của 3

thuật toán được mô tả ở Bảng 2.3 và Hình 2.1. Trong đó, ký hiệu là số thuộc tính

của bộ dữ liệu ban đầu, là số thuộc tính của tập rút gọn. Kết quả ở Bảng 2.3 và

Hình 2.1 cho thấy, so với thuật toán FPDAR sử dụng khoảng cách mờ theo tiếp cận

filter, số thuộc tính tập rút gọn của thuật toán đề xuất FW_FDBAR nhỏ hơn nhiều, đặc

biệt là đối với các bộ dữ liệu Horse, Heart, Credit, German. Độ chính xác của

FW_FDBAR cao hơn FPDAR trên tất cả các bộ dữ liệu. Do đó, hiệu năng và tính khái

quát hóa của tập luật phân lớp trên tập rút gọn của FW_FDBAR cao hơn nhiều so với

FPDAR. Với thuật toán filter-wrapper FEBAR [9] sử dụng -entropy mờ, số lượng

thuộc tính tập rút gọn của FW_FDAR xấp xỉ FEBAR, độ chính xác phân lớp của

FW_FDBAR xấp xỉ FEBAR.

Bảng 2.3 Độ chính xác phân lớp và số lượng thuộc tính tập rút gọn

FW_FDBAR, FEBAR, FPDAR

STT

Bộ dữ liệu

Độ chính xác ban đầu

Thuật toán FW_FDBAR

Thuật toán FEBAR [9]

Thuật toán FPDAR [12]

Độ chính xác

Lympho

Wine

Libra

WDBC

Horse

Heart

Credit

German

Độ chính xác 0.776± 0.008 0.910 ± 0.066 0.566 ± 0.137 0.924 ± 0.037 0.829 ± 0.085 0.744 ± 0.072 0.826 ± 0.052 0.692 ± 0.030

Độ chính xác 0.768 ± 0.085 0.893 ± 0.072 0.605 ± 0.103 0.952 ± 0.027 0.802 ± 0.066 0.803 ± 0.074 0.846 ± 0.048 0.702 ± 0.043

Độ chính xác 0.722 ± 0.062 0.886 ± 0.058 0.556 ± 0.205 0.925 ± 0.644 0.798 ± 0.058 0.752 ± 0.055 0.820 ± 0.078 0.684 ± 0.024

0.768 ± 0.085 0.893 ± 0.072 0.658 ± 0.077 0.968 ± 0.058 0.816 ± 0.052 0.803 ± 0.074 0.865 ± 0.028 0.716 ± 0.029

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

2.5.4. Kết quả so sánh thời gian thực hiện

Bảng 2.4 Thời gian thực hiện FW_FDBAR, FEBAR, FPDAR

Thuật toán FW_FDBAR

Thuật toán FEBAR [9]

STT

Bộ dữ liệu

Thủ tục Wrapper

Tổng cộng

Thủ tục Wrapper

Tổng cộng

Thuật toán FPDAR [12]

Lympho

Thủ tục Filer 0.32 0.46 46.28 20.15 4.85 1.22 16.58 52.48

Thủ tục Filer 0.38 0.51 55.12 26.38 5.26 1.45 19.26 71.22

0.50 1.21 86.18 8.74 2.68 1.52 3.42 8.64

0.82 1.67 132,46 28.89 7.53 2.74 20.00 61.12

0.52 1.18 88.26 8.22 2.65 1.78 3.98 8.28

0.90 1.69 143.38 34.60 7.91 3.23 23.24 79.50

1 2 Wine 3 Libra 4 WDBC 5 6 7 8

Horse Heart Credit German

0.34 0.48 48.48 22.32 4.98 1.26 18.02 54.65

Hình 2.3 Thời gian thực thiện của ba thuật toán

Kết quả so sánh về thời gian thực hiện ở Bảng 2.4 và Hình 2.3 cho thấy, thuật

toán FW_FDBAR có thời gian thực hiện nhỏ hơn đáng kể thuật toán FEBAR [9], chủ

yếu là ở thủ tục filter tìm tập rút gọn. Nguyên nhân là thuật toán FEBAR phải tính

miền dương mờ để xác định hệ số , hơn nữa thuật toán FEBAR phải tính toán các

công thức logarit phức tạ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_FDBAR và FEBAR [9] có thời gian thực hiện lớn

hơn thuật toán theo tiếp cận filter FPDAR [12] vì phải thực hiện bộ phân lớp để tính

độ chính xác của các tập rút gọn xấp xỉ trong giai đoạn wrapper.

2.6. Kết luận Chương 2

Trong Chương 2, luận án trình bày kết quả xây dựng một độ đo khoảng cách

trong bảng quyết định. Dựa vào độ đo khoảng cách được xây dựng, luận án xây dựng

thuật toán F_FDBAR tìm tập rút gọn của bảng quyết định theo tiếp cận filter truyền

thống, trên cơ sở đó đề xuất thuật toán theo tiếp cận kết hợp filter-wrapper FW_DBAR

nhằm giảm thiểu số thuộc tính của tập rút gọn và nâng cao độ chính xác của mô hình

phân lớp. 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 toán filter-wrapper FW_DBAR đề xuất giảm thiểu đáng kể số lượng thuộc tính

tập rút gọn so với các thuật toán filter FPDAR. Hơn nữa, thuật toán FW_DBAR duy trì

và nâng cao độ chính xác phân lớp so với thuật toán filter FPDAR. Tuy nhiên, thuật

toán FW_FDBAR mất thêm chi phí thời gian tính toán các bộ phân lớp. Với các bài

toán có số lượng thuộc tính lớn (high dimention data), ví dụ trong lĩnh vực tin sinh

học, việc giảm thiểu số lượng thuộc tính có ý nghĩa quan trọng vì giảm thiểu độ phức

tạp của mô hình, do đó lựa chọn các thuật toán filter-wrapper FW_DBAR là phù hợp.

Tuy nhiên, với các bảng có số thuộc tính nhỏ và có dữ liệu lớn, việc chọn các thuật

toán filter phù hợp hơn vì thời gian thực hiện nhỏ hơn.

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

Nội dung chương này trình bày hai thuật toán gia tăng rút gọn thuộc tính trong

bảng quyết định sử dụng khoảng cách mờ: thuật toán gia tăng filter-wrapper rút gọn

thuộc tính sử dụng khoảng cách mờ khi bổ sung tập đối tượng và thuật toán gia tăng

fifter-wrapper rút gọn thuộc tính khi loại bỏ tập đối tượng. Bằng lý thuyết và thực

nghiệm đánh giá hiệu quả về thời gian thực hiện, độ chính xác phân lớp và số lượng

thuộc tính của từng thuật toán so với các thuật toán truyền thống khác.

3.1. Mở đầu

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. Lý thuyết tập thô mờ (fuzzy rough set) do Dübois và cộng sự [1] đề xuất được

chứng minh 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 mà không qua tiền xử lý dữ liệu. Trong các bài toán thực tế, các

bảng quyết định thường có kích thước lớn và luôn thay đổi, cập nhật. Việc áp dụng các

thuật toán tìm tập rút gọn dựa trên tập thô mờ theo tiếp cận truyền thống gặp nhiều

thách thức. Trường hợp bảng quyết định thay đổi, cập nhật, các thuật toán này tính lại

tập rút gọn trên toàn bộ bảng quyết định sau khi thay đổi nên chi phí về thời gian tính

toán tăng lên đáng kể. Trường hợp bảng quyết định có kích thước lớn, việc thực hiện

thuật toán trên toàn bộ bảng quyết định kích thước lớn sẽ gặp khó khăn về dung lượng

bộ nhớ lưu trữ và thời gian thực hiện. Do đó, các nhà nghiên cứu đã đề xuất hướng tiếp

cận tính toán gia tăng (incremental) tìm tập rút gọn. Các thuật toán gia tăng chỉ thực

hiện cập nhật lại tập rút gọn trên phần dữ liệu thay đổi, do đó chúng giảm thiểu đáng

kể thời gian thực hiện. Theo tiếp cận tập thô truyền thống của Pawlak [19] và các mô

hình tập thô mở rộng, một số thuật toán gia tăng tìm tập rút gọn đã được đề xuất 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. Với trường

hợp bổ sung, loại bỏ 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, loại bỏ 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], ngoài ra còn một số phương pháp khác[80, 81,82,

83, 84, 90, 98, 102, 105, 106, 107, 108, 109, 110]

Theo tiếp cận tập thô mờ [1], trong mấy năm gần đây đã có một số 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. Với

trường hợp bổ sung và loại bỏ tập thuộc tính, Zeng và cộng sự [16] đã giới thiệu mô

hình tập thô mờ mở rộng dựa trên các hệ thống thông tin lai (HIS) và đề xuất hai

thuật toán gia tăng (FRSA-IFS-HIS-AA và FRSA-IFS-HIS-AD) tìm ra tập rút gọn

dựa trên hàm phụ thuộc mờ. Với trường hợp bổ sung tập đối tượng, Liu và cộng sự

[17] đã xây dựng các công thức gia tăng tính hàm thành viên mờ và đề xuất thuật

toán gia tăng FIAR tìm tập rút gọn. Yang và cộng sự [18] đã xây dựng cơ chế gia

tăng tính quan hệ không phân biệt mờ và đề xuất thuật toán gia tăng IARM tìm tập

rút gọn. Yang và cộng sự [20] đề xuất hai thuật toán gia tăng (V-FS-FRS-1 và V-FS-

FRS-2) tìm tập rút gọn dựa trên ma trận phân biệt mờ. 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, 55, 56], bổ sung và loại bỏ tập thuộc tính [57], và một số phương pháp khác [86,

87, 88, 89 ,93 ,94 ,95 ,96 ,97]. Với trường hợp bổ sung, loại bỏ 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 toán gia 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, loại bỏ 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, các thuật

toán nêu trên đều theo hướng tiếp cận lọc truyền thống (filter). Trong đó, 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 định nghĩa (hàm thuộc mờ,

quan hệ phân biệt…), 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 tìm được của các thuật toán nêu trên chưa

tối ưu cả về số lượng thuộc tính và độ chính xác phân lớp, nghĩa là tập rút gọn tìm

được chưa chắc có độ chính xác phân lớp tốt nhất.

Từ những vấn đề phân tích nêu trên, trong chương nà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 khoảng cách mờ (được đề xuất ở Chương 2) trong

trường hợp bổ sung, loại bỏ tập đối tượng. Dựa trên các công thức tính toán gia tăng

khoảng cách mờ được xây dựng, luận án trình bày 02 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 kết hợp filter-wrapper:

1) 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.

2) 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.

Hai thuật toán đề xuất nêu trên đều theo tiếp cận kết hợp filter-wrapper, hai

thuật toán này nhằm mục tiê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.

Kết quả nghiên cứu ở chương này được công bố ở công trình số 1, 3 phần “Danh

mục các công trình của tác giả”.

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

Trong phần này, luận án trình bày thuật toán gia tăng filter-wrapper tìm tập rút

gọn sử dụng khoảng cách mờ khi bổ sung tập đối tượng vào bảng quyết định. Trước

hết, luận án xây dựng các công thức gia tăng tính khoảng cách mờ khi bổ sung một đối

tượng và một 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 một đối tượng

là quan hệ

Cho bảng quyết định với và

tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện. Theo Mệnh đề 2.3

của Chương 2 , khoảng cách mờ sinh bởi và trên là:

Mệnh đề 3.1. 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ử đối

tượng được bổ sung vào . Khi đó, công thức tính gia tăng khoảng cách mờ là:

Chứng minh: Giả sử , tương ứng là ma

trận tương đương mờ của trên U và , với

. Ma trận tương đương của D trên U và

. là ,

Khi đó ta có:

Mặt khác

Từ đó ta có:

và

Ví dụ 3.1 Cho bảng quyết định , với

c1 0.8 0 0

c2 0.2 0.4 0.6

c3 0.6 0.6 0.6

c4 0.4 0.4 0.4

D 0 1 1

U u1 u2 u3

Bảng 3.1 Bảng quyết định của Ví dụ 3.1

với

như sau: Luận án sử dụng quan hệ tương đương mờ 𝑅̃𝑎 trên thuộc tính

Từ đó, tính các ma trận tương đương mờ lần lượt là:

Áp dụng công thức tính khoảng cách mờ sinh bởi C và trên U là:

Tiếp theo tiến hành bổ sung một đối tượng

c1 0.8 0 0 0

c2 0.2 0.4 0.6 0.6

c4 0.4 0.4 0.4 1

D 0 1 1 0

c3 0.6 0.6 0.6 0

U u1 u2 u3 x1

Bảng 3.2 Bảng quyết định sau khi thêm đối tượng u4 của Ví dụ 3.1

1)Tính khoảng cách mờ theo công thức gia tăng cho bởi Mệnh đề 3.1

Các ma trận tương đương mờ sau khi bổ sung một đối tượng x1

Ta có:

2)Tính khoảng cách trên toàn bộ bảng quyết định theo công thức không gia tăng

Với n= 4

Như vậy, kết quả tính toán khoảng cách mờ bởi công thức gia tăng của Mệnh đề

3.1 và công thức không gia tăng khi bổ sung thêm một đối tượng trên toàn bộ bảng

quyết định là như nhau, điều này chứng minh tính đúng đắn của công thức gia tăng.

3.2.2. Công thức gia tăng tính khoảng cách mờ khi bổ sung tập đối tượng

Từ Mệnh đề 3.1, chúng tôi giới thiệu công thức gia tăng tính khoảng cách mờ

khi thêm một tập đối tượng ở Mệnh đề 3.2

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 gồm s phần tử được bổ sung vào U, mà s2. Với

là ma trận tương đương mờ

tương ứng trên C và D. Khi đó, công thức gia tăng khoảng cách mờ như sau:

mà

Chứng minh: Ký hiệu tương ứng là công thức tính khoảng cách

mờ khi thêm lần lượt các đối tượng vào U, và là khoảng cách

mờ trên tập đối tượng ban đầu U.

Khi bổ sung đối tượng vào U, ta có:

(2.1)

Ở đây, lớp tương đương mờ tính trên đối tượng. Để tính toán trên

đối tượng sau khi bổ sung (tương ứng với ma trận quan hệ , công

thức (2.1) trở thành:

Với

Tính tương tự như vậy, ta được:

Với

Ví dụ 3.2 Cho bảng quyết định , với

Bảng 3.3 Bảng quyết định của Ví dụ 3.2

U

D

0.8

0.2

0.4

0.6

0.8

0.2

0.6

0.2

0.8

0.6

0.4

0.2

0.8

0.6

0.4

với

Luận án sử dụng quan hệ tương đương mờ trên thuộc tính như sau:

Từ đó, tính các ma trận tương đương mờ lần lượt:

Khoảng cách mờ giữa hai tập thuộc tính C và D của bảng quyết định

được tính bằng công thức không gia tăng:

Tiếp theo, tiến hành bổ sung tập đối tượng

vào bảng quyết định

.

0.8

0.2

0.6

0.4

0.8

0.2

0.6

0.2

0.8

0.6

0.4

0.8

0.2

0.6

0.4

0.6

0.4

0.6

0.4

0.6

Bảng 3.4 Bảng quyết định của Ví dụ 3.2 sau khi thêm tập đối tượng

1)Tính khoảng cách mờ theo công thức gia tăng cho bởi Mệnh đề 3.2

Các ma trận tương đương mờ khi bổ sung tập đối tượng

Ta có:

2) Tính khoảng cách mờ trên toàn bộ bảng quyết định theo công thức không gia

tăng

Với

Với n= 3, s=3, ta có:

Như vậy, kết quả tính toán khoảng cách mờ bởi công thức gia tăng của Mệnh đề

3.2 và công thức không gia tăng khi bổ sung thêm tập đối tượng trên toàn bộ bảng

quyết định là như nhau, điều này chứng minh tính đúng đắn của công thức gia tăng.

3.2.3. 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ệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, 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ử

được bổ sung vào . Khi đó ta có:

1) Nếu với mọi thì:

2) Nếu với mọi thì

Chứng minh: Giả sử tương ứng

là ma trận tương đương mờ trên C và B.

1) Nếu với mọi thì với mọi và ta

có . Do đó, , từ Mệnh đề 3.2 ta có công

thức trong trường hợp đầu tiên.

2) Nếu với mọi thì . Khi đó, ta

có và . Do đó

, ,

, .

Hơn nữa, với

. Từ Mệnh đề 3.2 ta có:

(3.1)

(3.2)

Từ B là tập rút gọn của C nên ta có:

. Từ (3.1) và (3.2) ta có:

Từ kết quả của Mệnh đề 3.3, thuật toán gia tăng filter-wrapper rút gọn thuộc

tính sử dụng khoảng cách mờ IFW_FDAR_AdObj gồm 3 bước chính:

Algorithm IFW_FDAR_AdObj

Đầu vào:

với , quan 1. Bảng quyết định

hệ tương đương mờ , tập rút gọn .

2. Các ma trận tương đương mờ

3. Tập đối tượng bổ sung

của với Đầu ra: Tập rút gọn xấp xỉ

độ chính xác phân loại cao nhất.

Bước 1: Khởi tạo

// T chứa ứng của viên tập rút gọn tốt nhất 1.

2. Tính các ma trận tương đương mờ trên tập đối tượng

;

Bước 2: Kiểm tra tập đối tượng thêm vào

; 3. Đặt

to s do 4. For

then ; 5. If

then Return ; // Tập xấp xỉ 6. If

không thay đổi

; //Gán lại tập đối tượng 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

do While 10.

Begin 11.

do 12. For each

13. Begin

bởi công thức gia Tính 14.

tăng;

Tính 15.

16. End;

satisfying ; 17. Select

; 18.

; 19.

; 20.

End; 21.

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

Đặt //t là số phần tử của T, 22.

;

Đặt ; 23.

For j:= 1 to t do 24.

Tính độ chính xác phân lớp trên bằng một bộ 25.

phân lớp sử dụng phương pháp 10-fold;

với có độ chính xác phân lớp cao nhất; 26.

Return ;

3.2.4. Đánh giá độ phức tạp của thuật toán

Trong phần này, Luận án sẽ đánh giá độ phức tạp của thuật toán

IFW_FDAR_AdObj . Giả sử , tương ứng là số thuộc tính điều

kiện, số đối tượng và số đối tượng bổ sung từ tập ban đầu. Độ phức tạp của thuật toán

được tính dựa trên thuật toán trên.

Độ phức tạp của ma trận tương đương mờ ở câu lệnh 2 trên là

và độ phức tạp của vòng for ở câu lệnh 4, 5 là

. Trong trường hợp tốt nhất, thuật toán kết thúc ở câu lệnh 6 (tập

rút gọn không thay đổi). Khi đó, độ phức tạp của thuật toán IFW_FDAR_AdObj là

. Ngược lại, độ phức tạp của khoảng cách mờ ở câu lệnh 9 là

, độ phức tạp tính gia tăng

là . Bằng cách tính độ phức tạp tương tự như thuật toán

FW_FDBAR ở trong phần 2.4, độ phức tạp của vòng lặp While (từ câu lệnh 10 đến

câu lệnh 21) là . Kết quả độ phức tạp của giai đoạn

fifter trong trường hợp xấu nhất là . Độ phức tạp của giai

đoạn wrapper phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ

phức tạp của bộ phân lớp là , khi đó độ phức tạp của giai đoạn wrapper là

Từ những phân tích trên độ phức tạp của thuật toán IFW_FDAR_AdObj là:

Nếu thực hiện thuật toán không gia tăng FW_FDBAR trực tiếp trên bảng

quyết định có số đối tượng , theo mục 2.4 của Chương 2, độ phức tạp của

FW_FDBAR là . Dựa trên kết quả này chúng ta thấy

rằng thuật toán IFW_FDAR_AdObj giảm thiểu đá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 và nhỏ.

3.2.5. Thực nghiệm thuật toán

3.2.5.1 Mục tiêu thực nghiệm

1) Đánh giá về thời gian thực hiện của thuật toán gia tăng filter-wrapper

IFW_FDAR_AdObj với hai thuật toá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 chọn mẫu hoạt động, trong khi IFSA là thuật toán filter

dựa trên chức năng phụ thuộc.

2) Đánh giá tính hiệu quả về độ chính xác phân lớp và số lượng thuộc tính của

tập rút gọn của thuật toá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.5.2 Dữ liệu thực nghiệm

Việc thực nghiệm được triển khai trên 8 tập dữ liệu mẫu lấy từ kho dữ liệu

UCI[59] trong Bảng 3.5.

Với thuật toán IV-FS-FRS-2 và IARM bằng cách tiếp cận tập thô mờ, tất cả

các thuộc tính giá trị thực được chuẩn hóa thành giá trị trong khoảng [0, 1] trên mỗi

tập dữ liệu [54]:

(3.3)

Với , tương ứng là giá trị lớn nhất và nhỏ nhất của thuộc tính .

Quan hệ tương đương mờ [9,54] trên thuộc tính được xác định như sau:

với (3.4)

với mỗi thuộc tính có giá trị định danh hoặc nhị phân, quan hệ tương

đương mờ trong (3.5) với :

(3.5)

Trên thuộc tính quyết định , Luận án sử dụng quan hệ tương đương .

Với

(3.6)

Phân hoạch , với và là

một lớp tương đương. Khi đó, lớp tương đương được xem là lớp tương đương mờ,

ký hiệu bởi

. Hàm thành viên được định nghĩa là nếu và

nếu .

Với thuật toán ASS-IAR và IFSA được tiếp cận theo tập thô truyền thống, luận

án dùng thuật toán phân cụm C-mean mờ (FCM) để phân biệt dữ liệu có giá trị thực

trước khi rút gọn thuộc tính.

Mỗi tập dữ liệu được chia thành 2 phần xấp xỉ nhau: dữ liệu ban đầu (Cột 5

trong Bảng 3.5) và dữ liệu gia tăng (Cột 6 trong Bảng 3.5). Dữ liệu ban đầu được ký

hiệu là U0. Tập dữ liệu gia tăng được tách ngẫu nhiên thành 5 phần bằng nhau, mỗi

phần được ký hiệu tương ứng là U1, U2, U3, U4, U5.

Để áp dụng thuật toán gia tăng IFW_FDAR_AdObj, IV-FS-FRS-2, IARM,

ASS-IAR và IFSA, đầu tiên chúng tôi thực hiện thuật toán này trên bộ dữ liệu gốc.

Tiếp đến, thuật toán này sẽ được bổ sung lần lượt từ phần đầu tiên đến phần thứ năm

của bộ dữ liệu gia tăng.

Bảng 3.5 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

Tổng số

Số lớp quyết định

Giá trị thực

(1) (2) 1 Libra

(4) 360

(5) 180

Số đối tượng gia tăng (6) 180

Số thuộc tính điều kiện Giá trị định danh (8) 0

(7) 90

(9) 90

(10) 15

2 WDBC

569

284

285

3 Horse 4 Heart 5 Credit

368 270 690

183 135 345

185 135 345

22 13 15

2 2 2

15 7 9

7 6 6

6 German

1000

500

7 Cmc

1473

733

740

(3) Libras movement Wisconsin diagnostic breast cancer Horse colic Statlog (heart) Credit approval German credit data Contraceptive Method Choice

5000

2500

8 Wave Waveform

3.2.5.3 Phương pháp, công cụ và môi trường thử nghiệm

Chúng tôi dùng bộ phân lớp CART (CART – Classification And Regression

Tree) để tính độ chính xác phân lớp trong giai đoạn wrapper của thuật toán

IFW_FDAR_AdObj. Đồng thời dùng bộ phân lớp CART để tính độ chính xác phân

lớp cho các thuật toán IFW_FDAR_AdObj , IV-FS-FRS-2, IARM, ASS-IAR sau khi

rút gọn tập thuộc tính. Chúng tôi sử dụng phương pháp kiểm tra chéo 10-fold và chia

bộ dữ liệu thành 10 phần xấp xỉ bằng nhau. Lấy ngẫu nhiên một phần làm bộ dữ liệu

kiểm tra, các phần còn lại làm dữ liệu huấn luyện. Quá trình được lặp lại 10 lần. Độ

chính xác được biểu diễn bởi 𝑣 ± 𝜎 với 𝑣 là giá trị độ chính xác trung bình của 10 lần

lặp và 𝜎 là sai số chuẩn (standard error). Tất cả các thử nghiệm được cài đặt trên PC

Core(TM) Intel (R) i7-3770CPU, 3.40 GHz, Windows 7 sử dụng Matlab.

3.2.5.4 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

Bảng 3.6 và Hình 3.1 trình bày thể hiện kết quả so sánh về thời gian thực hiện

của thuật toán IFW_FDAR_AdObj với các thuật toán IV-FS-FRS-2, IARM, ASS-IAR,

IFSA với các cột T0, T1, T2, T3, T4 tương ứng là tổng thời gian tính toán của các thuật

toán IFW_FDAR_AdObj, IV-FS-FRS-2, IARM, ASS-IAR, IFSA. Cột DS là dữ liệu

gia tăng ban đầu.

Bảng 3.6 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 (tính bằng giây)

Stt

DS

T0

T1

T2

T3

T4

Bộ dữ liệu

Libra

WDBC

Horse

4.26 4.84 5.22 5.68 6.28 6.78 2.86 3.04 3.28 3.56 3.85 4.08 0.68 0.76 0.85 0.94 0.99 1.08

3.12 3.98 4.46 4.98 5.24 5.76 2.12 2.46 2.72 2.91 3.24 3.35 0.54 0.59 0.66 0.74 0.78 0.82

3.04 3.86 4.24 4.56 4.86 5.08 2.10 2.42 2.68 2.85 3.02 3.12 0.52 0.58 0.67 0.75 0.79 0.86

3.02 3.16 3.49 3.98 4.54 5.06 2.06 2.18 2.34 2.61 2.88 3.19 0.50 0.54 0.59 0.66 0.75 0.84

3.82 3.86 3.94 4.12 4.48 4.86 2.63 2.72 2.80 2.89 2.98 3.04 0.58 0.63 0.69 0.72 0.75 0.78

U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5

Heart

Credit

German

Cmc

Wave

0.11 0.14 0.18 0.20 0.21 0.22 0.52 0.66 0.81 0.92 1.04 1.15 2.02 2.21 2.58 2.92 3.28 3.46 1.55 1.78 2.01 2.28 242 2.96 160.68 175.48 189.28 202.85 219.46 226.26

0.10 0.12 0.14 0.17 0.20 0.24 0.48 0.56 0.68 0.79 0.94 1.18 2.04 2.12 2.26 2.48 2.96 3.42 1.58 1.72 1.96 2.32 2.58 2.82 154.28 162.18 173.69 188.26 202.17 220.46

0.68 0.72 0.86 0.92 1.08 1.26 0.74 0.96 1.29 1.54 1.75 1.86 2.36 2.58 2.94 3.28 3.68 4.26 1.92 2.12 2.48 2.74 2.98 3.22 182.26 198.64 210.12 228.84 252.26 274.48

0.11 0.13 0.18 0.19 0.20 0.22 0.52 0.68 0.82 0.94 1.05 1.18 2.04 2.25 2.62 2.98 3.36 3.84 1.54 1.76 1.98 2.25 2.34 2.72 164.26 182.98 198.24 209.17 223.89 238.64

0.14 0.15 0.17 0.18 0.19 0.20 0.56 0.62 0.69 0.78 0.88 1.12 2.86 2.92 2.98 3.06 3.12 3.18 1.86 1.98 2.12 2.28 2.45 2.64 172.58 176.12 182.64 189.25 192.46 198.16

U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5 U0 U1 U2 U3 U4 U5

Hình 3.1a. Thời gian thực hiện các thuật toán trên bộ dữ liệu Libra

4,5

n ệ i h

IFW_FDAR_AdObj

3,5

c ự h t

IV-FS-FRS-2

n a i g

IARM

i ờ h T

ASS-IAR

2,5

IFSA

Tập đối tượng của dữ liệu WDBC

1,2

n ệ i h

IFW_FDAR_AdObj

0,8

IV-FS-FRS-2

c ự h t

0,6

IARM

n a i g

0,4

ASS-IAR

i ờ h T

0,2

IFSA

Tập đối tượng của dữ liệu Horse

Hình 3.1b. Thời gian thực hiện các thuật toán trên bộ dữ liệu WDBC

Hình 3.1c. Thời gian thực hiện các thuật toán trên bộ dữ liệu Horse

Hình 3.1d. Thời gian thực hiện các thuật toán trên bộ dữ liệu Heart

4,5

n ệ i h

IFW_FDAR_AdObj

3,5

c ự h t

IV-FS-FRS-2

n a i g

IARM

i ờ h T

ASS-IAR

2,5

IFSA

Tập dữ liệu của đối tượng German

Hình 3.1.e Thời gian thực hiện các thuật toán trên bộ dữ liệu Credit

3,5

n ệ i h

IFW_FDAR_AdObj

c ự h t

IV-FS-FRS-2

2,5

n a i g

IARM

i ờ h T

ASS-IAR

IFSA

1,5

Tập đối tượng của dữ liệu Cmc

Hình 3.1.f Thời gian thực hiện các thuật toán trên bộ dữ liệu German

Hình 3.1.g Thời gian thực hiện các thuật toán trên bộ dữ liệu Cmc

Hình 3.1.h Thời gian thực hiện các thuật toán trên bộ dữ liệu Wave

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

Bảng 3.6 và Hình 3.1 chỉ ra rằng thời gian thực hiện của thuật toán

IFW_FDAR_AdObj cao hơn thời gian thực hiện của các thuật toán IV-FS-FRS-2 và

IARM trên tất cả các bộ dữ liệu. Mặc dù việc tính toán khoảng cách mờ trong thuật

toán IFW_FDAR_AdObj đơn giản hơn việc tính toán độ đo trong các thuật toán IV-

FS-FRS-2, IARM, ASS-IAR và IFSA, thuật toán IFW_FDAR_AdObj cần nhiều thời

gian hơn để thực hiện phân lớp. Thời gian thực hiện của thuật toán ASS-IAR là nhỏ

nhất vì loại bỏ các dữ liệu nhiễu trong tính toán gia tăng.

3.2.5.5 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

Kết quả của độ chính xác phân lớp và số lượng thuộc tính của tập rút gọn

được trình bày trong Bảng 3.7. Theo kết quả này, số lượng thuộc tính của tập rút gọn

tại mỗi bước tăng dần, thuật toán filter-wrapper IFW_FDAR_AdObj đề xuất có số

lượng thuộc tính của tập rút gọn nhỏ hơn nhiều các thuật toán IV-FS-FRS-2, IARM,

ASS-IAR và IFSA. Đồng thời, tính chính xác và tính khái quát hóa của tập luật phân

lớp trên tập rút gọn của thuật toán IFW_FDAR_AdObj tốt hơn các thuật toán IV-FS-

FRS-2, IARM, ASS-IAR và IFSA. Hơn nữa, với việc chọn tập rút gọn có độ chính

xác cao nhất trong giai đoạn wrapper, độ chính xác phân lớp của thuật toán

IFW_FDAR_AdObj cao hơn các thuật toán IV-FS-FRS-2, IARM, ASS-IAR và IFSA

trên tất cả các bộ dữ liệu. Độ chính xác phân lớp của thuật toán IV-FS-FRS-2, IARM

theo tiếp cận tập thô mờ cao hơn các thuật toán ASS-IAR, IFSA theo tiếp cận tập thô

truyền thống.

Với mỗi bộ dữ liệu, chúng ta thấy rằng, độ chính xác phân lớp không tăng khi

bổ sung bộ dữ liệu gia tăng. Điều này là do có một vài đối tượng nhiễu trong bộ dữ

liệu gia tăng làm giảm độ chính xác phân lớp của thuật toán học.

Bảng 3.7 Độ chính xác phân lớp và 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

(Giá trị tô đậm trên mỗi hàng là giá trị tốt nhất trên bộ dữ liệu đó)

IV-FS-FRS-2

IARM

ASS-IAR

IFSA

IFW-FDAR- AdObj

Stt

Bộ dữ liệu

Độ chính xác

Dữ liệu gốc, dữ liệu gia tăng

0.546 ± 0.028

0.518 ± 0.037

0.508 ± 0.028

0.594 ± 0.032

0.556 ± 0.026

0.564 ± 0.037

0.594 ± 0.032

0.580 ± 0.019

0.588 ± 0.028

1 Libra

0.649 ± 0.028

0.621 ± 0.034

0.632 ± 0.016

0.649 ± 0.028

0.628 ± 0.028

0.614 ± 0.038

10

0.502 ± 0.020

0.517 ± 0.014

0.582 ± 0.076

0.889 ± 0.018

0.886 ± 0.043

0.852 ± 0.028

2 WDBC

0.889 ± 0.018

0.886 ± 0.043

0.852 ± 0.028

0.492 ± 0.021 0.524 ± 0.042 0.556 ± 0.017 0.602 ± 0.028 0.576 ± 0.041 0.498 ± 0.024 0.846 ± 0.028 0.846 ±

0.496 ± 0.016 0.528 ± 0.023 0.542 ± 0.036 0.598 ± 0.029 0.565 ± 0.018 0.496 ± 0.012 0.836 ± 0.016 0.836 ±

0.841 ± 0.025

0.824 ± 0.032

0.849 ± 0.034

0.841 ± 0.025

0.824 ± 0.032

0.849 ± 0.034

0.932 ± 0.056

0.885 ± 0.018

0.908 ± 0.019

6

0.895 ± 0.012

0.912 ± 0.014

0.932 ± 0.056

0.765 ± 0.048

0.712 ± 0.028

0.706 ± 0.032

0.765 ± 0.048

0.712 ± 0.028

0.706 ± 0.032

0.765 ± 0.048

0.708 ± 0.016

0.701 ± 0.024

3 Horse

0.806 ± 0.052

0.769 ± 0.028

0.758 ± 0.036

0.806 ± 0.052

0.795 ± 0.037

0.758 ± 0.036

5

0.788 ± 0.048

0.744 ± 0.023

0.806 ± 0.052

0.768 ± 0.064

0.744 ± 0.052

0.726 ± 0.038

0.028 0.818 ± 0.032 0.818 ± 0.032 0.872 ± 0.029 0.886 ± 0.025 0.705 ± 0.012 0.705 ± 0.012 0.695 ± 0.028 0.742 ± 0.036 0.758 ± 0.024 0.742 ± 0.018 0.712 ± 0.028

0.016 0.812 ± 0.018 0.812 ± 0.018 0.862 ± 0.022 0.874 ± 0.017 0.702 ± 0.026 0.702 ± 0.026 0.693 ± 0.021 0.722 ± 0.037 0.722 ± 0.037 0.718 ± 0.024 0.706 ± 0.025

0.768 ± 0.064

0.758 ± 0.026

0.738 ± 0.018

0.728 ± 0.019

0.719 ± 0.019

4 Heart

0.864 ± 0.048

0.758 ± 0.026

0.738 ± 0.018

0.728 ± 0.019

0.719 ± 0.019

0.864 ± 0.048

0.815 ± 0.052

0.806 ± 0.047

0.764 ± 0.028

0.745 ± 0.024

0.864 ± 0.048

0.815 ± 0.052

0.798 ± 0.049

0.764 ±

0.726 ±

0.028

0.021

5

0.766 ± 0.058

0.772 ± 0.014

0.812 ± 0.072

0.738 ± 0.039

0.726 ± 0.036

0.786 ± 0.027

0.764 ± 0.027

0.802 ± 0.048

0.684 ± 0.018

0.692 ± 0.026

0.786 ± 0.027

0.764 ± 0.027

0.802 ± 0.048

0.684 ± 0.018

0.692 ± 0.026

0.798 ± 0.035

0.792 ± 0.026

0.865 ± 0.026

0.696 ± 0.029

0.708 ± 0.032

5 Credit

0.839 ± 0.029

0.818 ± 0.034

0.865 ± 0.026

0.806 ± 0.048

0.802 ± 0.022

0.865 ± 0.026

4

0.828 ± 0.014

0.826 ± 0.014

0.865 ± 0.026

0.706 ± 0.018

0.725 ± 0.026

0.748 ± 0.029

0.768 ± 0.026

0.748 ± 0.029

0.768 ± 0.026

6 German

0.642 ± 0.038

0.716 ± 0.028

0.696 ± 0.024

0.716 ± 0.028

0.688 ± 0.032

0.690 ± 0.015

0.716 ± 0.028

0.512 ± 0.027

0.505 ±0.038

0.692 ± 0.012

7 Cmc

0.789 ± 0.036 0.743 ± 0.024 0.743 ± 0.024 0.684 ± 0.029 0.705 ± 0.032 0.702 ± 0.026 0.622 ± 0.037 0.622 ± 0.037 0.618 ± 0.018 0.502 ± 0.017 0.543 ±

0.782 ± 0.036 0.736 ± 0.027 0.736 ± 0.027 0.695 ± 0.028 0.714 ± 0.019 0.709 ± 0.019 0.615 ± 0.024 0.615 ± 0.033 0.602 ± 0.022 0.504 ± 0.026 0.552 ±

0.586 ± 0.048

0.576 ± 0.042

0.692 ± 0.012

0.586 ± 0.048

0.576 ± 0.042

0.692 ± 0.012

0.502 ± 0.035

0.502 ± 0.029

0.658 ± 0.072

0.502 ± 0.035

0.502 ± 0.029

0.658 ± 0.072

4

0.489 ± 0.042

0.482 ± 0.012

0.658 ± 0.072

0.694 ± 0.036

0.682 ± 0.015

0.785 ± 0.016

0.716 ± 0.012

0.706 ± 0.011

0.794 ± 0.025

0.716 ± 0.012

0.765 ± 0.032

0.816 ± 0.017

8 Wave

0.764 ± 0.043

0.728 ± 0.036

0.806 ± 0.048

0.786 ± 0.028

0.732 ± 0.018

0.811 ± 0.016

8

0.784 ± 0.016

0.702 ± 0.024

0.812 ± 0.022

0.028 0.543 ± 0.028 0.498 ± 0.036 0.498 ± 0.036 0.476 ± 0.029 0.646 ± 0.026 0.695 ± 0.038 0.695 ± 0.038 0.723 ± 0.026 0.726 ± 0.017 0.701 ± 0.029

0.037 0.552 ± 0.037 0.492 ± 0.023 0.492 ± 0.023 0.469 ± 0.024 0.652 ± 0.027 0.702 ± 0.034 0.704 ± 0.029 0.726 ± 0.029 0.716 ± 0.017 0.702 ± 0.028

0,65

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

Các tập đối tượng của dữ liệu Libra

Hình 3.2a. Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Libra

0,85

p ớ l

0,8

IFW-FDAR-AdObj

n â h p

IV-FS-FRS-2

0,75

c á x

IARM

h n í h c

0,7

ASS-IAR

ộ Đ

IFSA

0,65

U1 U4 Các tập đối tượng của dữ liệu Horse

Hình 3.2.b Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu WDBC

0,9

p ớ l

0,85

IFW-FDAR-AdObj

n â h p

IV-FS-FRS-2

0,8

c á x

IARM

h n í h c

0,75

ASS-IAR

ộ Đ

IFSA

0,7

Các tập đối tượng của dữ liệu Heart

Hình 3.2.c Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Horse

Hình 3.2.d Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Heart

0,8

p ớ l

0,75

IFW-FDAR-AdObj

n â h p

IV-FS-FRS-2

0,7

c á x

IARM

h n í h c

0,65

ASS-IAR

Hình 3.2.e Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Credit

IFSA

0,6

U1 U4 Các tập đối tượng của dữ liệu Germen

ộ Đ

0,75

0,7

p ớ l

0,65

IFW-FDAR-AdObj

n â h p

IV-FS-FRS-2

0,6

c á x

IARM

0,55

h n í h c

ASS-IAR

0,5

IFSA

0,45

Các tập đối tượng của dữ liệu Cmc

Hình 3.2.f Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Germen

ộ Đ Hình 3.2.g Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Cmc

Hình 3.2.h Độ chính xác phân lớp của các thuật toán trên bộ dữ liệu Wave

Hình 3.2 Độ chính xá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

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

Tiếp theo, chúng tôi trình bày thuật toán filter-wrapper tìm tập rút gọn sử dụng

khoảng cách mờ khi loại bỏ tập đối tượng theo hướng tiếp cận tính toán gia tăng.

Trước hết, chúng tôi xây dựng các công thức cập nhật khoảng cách mờ khi loại bỏ một

đối tượng.

3.3.1. Cập nhật khoảng cách mờ khi loại bỏ một đối tượng

Mệnh đề 3.4: Cho bảng quyết định với và là một

quan hệ tương đương mờ được xác định trên miền giá trị của tập thuộc tính điều

kiện. Giả sử đối tượng bị loại khỏi U. Khi đó, công thức tính khoảng cách mờ

như sau:

(3.7)

Với tương ứng là khoảng

cách mờ trên các tập đối tượng .

Chứng minh: Giả sử rằng tương ứng là ma trận tương

đương mờ của

trên và . Khi đó, ta có:

Ví dụ 3.3. Cho bảng quyết định với

0.8

0.2

0.6

0.4

0.8

0.2

0.6

0.2

0.8

0.6

0.4

0.8

0.2

0.6

0.4

0.6

0.4

0.6

0.4

0.6

Bảng 3.8 Bảng quyết định của Ví dụ 3.3

với

Luận án sử dụng quan hệ tương đương mờ trên thuộc tính như sau:

Từ đó, tính các ma trận tương đương mờ lần lượt:

,

Khoảng cách mờ giữa hai tập thuộc tính C và D của bảng quyết định

được tính bằng công thức không gia tăng:

Tiếp theo, ta tiến hành loại bỏ 1 đối tượng khỏi bảng quyết định

.

0.8

0.2

0.6

0.4

0.8

0.2

0.6

0.2

0.8

0.4

0.6

0.4

0.6

0.4

0.6

Bảng 3.9 Bảng quyết định sau khi loại bỏ 1 đối tượng của Ví dụ 3.3

1)Tính khoảng cách mờ theo công thức gia tăng cho bởi Mệnh đề 3.4

Các ma trận tương đương mờ khi loại bỏ 1 đối tượng

2)Tính khoảng cách mờ trên toàn bộ bảng quyết định theo công thức không gia

tăng

Như vậy, kết quả tính toán khoảng cách mờ bởi công thức gia tăng của Mệnh đề

3.4 và công thức không gia tăng khi loại bỏ 1 đối tượng trên toàn bộ bảng quyết định

là như nhau, điều này chứng minh tính đúng đắn của công thức gia tăng.

3.3.2. Cập nhật khoảng cách mờ khi loại bỏ tập đối tượng

Trên cơ sở Mệnh đề 3.4, chúng tôi xây dựng công thức cập nhật khoảng cách

mờ trong trường hợp loại bỏ tập đối tượng bởi Mệnh đề 3.5 như sau:

Mệnh đề 3.5. Cho bảng quyết định với và là một

quan hệ tương đương mờ. Giả sử tập đối tượng gồm s phần tử

bị loại khỏi U, . 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 .

Khi đó, công thức cập nhật khoảng cách mờ như sau:

(3.8)

Với

Chứng minh: Ký hiệu tương ứng là khoảng cách mờ khi

loại bỏ lần lượt các đối tượng khỏi U và là khoảng cách mờ trên

tập đối tượng ban đầu U. Áp dụng Mệnh đề 3.4, ta có:

Tính tương tự như vậy, ta được:

Vì vậy,

Với

Ví dụ 3.4 Cho bảng quyết định , với

0.4

0.8

0.2

0.6

0.2

0.8

0.2

0.6

0.4

0.6

0.4

0.8

0.4

0.6

0.4

0.6

Bảng 3. 10 Bảng quyết định của Ví dụ 3.4

với

Luận án sử dụng quan hệ tương đương mờ trên thuộc tính như sau:

Từ đó, tính các ma trận tương đương mờ lần lượt:

Khoảng cách mờ giữa hai tập thuộc tính C và D của bảng quyết định

được tính bằng công thức không gia tăng:

Tiếp theo, ta tiến hành loại bỏ tập đối tượng

khỏi bảng quyết

định

.

0.8

0.2

0.6

0.4

0.8

0.2

0.6

0.2

0.8

0.6

0.4

0.8

0.2

0.6

0.4

Bảng 3.11 Bảng quyết định sau khi loại bỏ tập đối tượng của Ví dụ 3.4

1)Tính khoảng cách mờ theo công thức gia tăng cho bởi Mệnh đề 3.5

Ta có các ma trận

2)Tính khoảng cách mờ trên toàn bộ bảng quyết định theo công thức không gia

tăng

Như vậy, kết quả tính toán khoảng cách mờ bởi công thức gia tăng của Mệnh đề

3.5 và công thức không gia tăng khi loại bỏ tập đối tượng trên toàn bộ bảng quyết định

là như nhau, điều này chứng minh tính đúng đắn của công thức gia tăng.

3.3.3. 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

Cho bảng quyết định với và là một quan hệ

tương đương mờ. Giả sử tập đối tượng gồm s phần tử bị loại

khỏi U,

. Ma trận tương đương mờ và ma trận tương đương trên C và D tương

ứng được xác định bởi . Khi đó,

công thức cập nhật khoảng cách phân mờ như sau:

là một

Mệnh đề 3.6. Cho bảng quyết định với và

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.

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ử

bị loại khỏi , . Khi đó ta có:

1) Nếu với thì

2) Nếu với thì .

Chứng minh. Giả sử tương ứng

là ma trận tương đương mờ trên C và B sau khi loại bỏ tập đối tượng 𝛥𝑈. Có hai trường

hợp xảy ra:

- Nếu với thì với mọi ta có

. Do đó, . Từ Mệnh đề 3.5 ta có công thức (1).

- Nếu với mọi thì . Khi đó ta có

và . Do đó, ta có

, và

, . Hơn nữa, với

, có hai công thức

Từ kết quả của Mệnh đề 3.5, ta có:

(3.9)

(3.10)

Mặt khác do B là tập rút gọn của C, ta có

Từ (3.9) và (3.10) ta có công thức 2).

Dựa trên kết quả của Mệnh đề 3.6, thuật toán filter-wrapper cập nhật tập rút gọn

xấp xỉ có độ chính xác phân lớp tốt nhất sử dụng khoảng cách mờ khi loại bỏ tập đối

tượng được thực hiện như sau:

Algorithm IFW_FDAR_DelObj Input: Đầu vào

với , một quan 1. Bảng quyết định

hệ tương đương mờ , tập rút gọn ;

2. Ma trận tương đương mờ

3. Tập đối tượng gồm s phần tử bị loại bỏ

của có độ

Output: Tập rút gọn xấp xỉ chính xác phân lớp cao nhất.

;

to do

then 1. 2. Đặt 3. For 4. If

then Return ; 5. If

; 6. Đặt

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 :

// Giai đoạn Fifter, tìm các ứng viên cho tập rút gọn

do 9. While

10. Begin 11. For each 12. Begin

Tính bởi Mệnh đề 13.

;

3.6 khi loại bỏ tập đối tượng Tính 14.

;

End; 15.

Chọn sao cho ; 16.

; 17.

; 18.

19.

End; 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

Đặt // ; 21.

Đặt ; 22.

For j:= 1 to t do

23. 24. 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;

với có độ chính xác phân lớp cao nhất; 25.

Return ;

3.3.4. Phân tích độ phức tạp của thuật toán

Độ phức tập của thuật toán IFW_FDAR_DelObj được tính như bên dưới. Giả

sử . Độ phức tạp của vòng lặp trong câu lệnh 3 (For) là .

Trong trường hợp tốt nhất, thuật toán kết thúc ở câu lệnh 5 (khi tập rút gọn

không thay đổi). Độ phức tạp của thuật toán IFW_FDAR_DelObj là .

Ngược lại, độ phức tạp của thuật toán tính khoảng cách mờ ở câu lệnh 7 là . Để

tính độ phức tạp của thuật toán khi loại bỏ tập ra khỏi U ở câu lệnh 8, độ phức tạp

. Để tính giá trị của , ta phải tính là

. Độ phức tạp của

. Do đó, độ phức tạp của vòng lặp While là và độ là

phức tạp của giai đoạn fifter trong trường hợp xấu nhất là . Giả sử độ

phức tạp của bộ phân lớp là khi đó độ phức tạp của giai đoạn wrapper là

Tóm lại, độ phức tạp của thuật toán IFW_FDAR_DelObj là

. Khi áp dụng thuật toán FW_FDBAR trực tiếp vào bảng

quyết định với đối tượng, từ kết quả của phần 2.4 độ phức tạp của

FW_FDBAR là . Nếu nhỏ, thuật toán IFW_FDAR_DelObj

tốt hơn thuật toán FW_FDBAR. Nhưng nếu và đều lớn, thuật toán

FW_FDBAR tốt hơn thuật toán IFW_FDAR_DelObj.

3.3.5. Thực nghiệm thuật toán

3.3.5.1 Mục tiêu thử nghiệm

Trong phần này chúng tôi cài đặt thử nghiệm để đánh giá độ chính xác phân

loại của thuật toán IFW_FDAR_DelObj so với các thuật toán gia tăng dựa trên tập thô

theo tiếp cận fifter IFSD [36]. IFSD là thuật toán gia tăng rút gọn thuộc tính dựa trên

hàm phụ thuộc khi loại bỏ tập đối tượng.

3.3.5.2 Dữ liệu thử nghiệm

Các thử nghiệm được triển khai trên một số bộ dữ liệu mẫu lấy từ kho dữ liệu

UCI [59] trong Bảng 3.12. Tất cả dữ liệu mẫu trong Bảng 3.12 là dữ liệu đã được rời

rạc, luận án sử dụng quan hệ tương đương mờ như sau:

Với và .

Dùng bộ phân lớp CART để tính toán độ chính xác phân lớp trong giai đoạn

wrapper của thuật toán IFW_FDAR_DelObj. Chúng tôi cũng sử dụng bộ phân lớp

CART để tính độ chính xác phân lớp cho các thuật toán IFW_FDAR_DelObj, IFSD

sau khi rút gọn thuộc tính. Đồng thời sử dụng phương pháp kiểm tra chéo 10-fold.

Bảng 3.12 Mô tả dữ liệu khi loại bỏ tập đối tượng

Stt

Bộ dữ liệu

Số đối tượng

Số lớp quyết định

Số các thuộc tính điều kiện

1 Audiology

226

2 Dermatology

366

3 Arrhythmia

452

279

4 Mfeat-factor

2000

216

Chess-kr-vs-kp

3196

Satimage

6435

7 Mushroom

8124

Letter

20000

Để đánh giá hiệu quả về thời gian thực hiện và độ chính xác của thuật toán,

chúng tôi chọ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 cá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.5.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

Bảng 3.13 so sánh kết quả về thời gian thực hiện của thuật toán

IFW_FDAR_DelObj với thuật toán IFSD, mà các cột T1, T2 tương ứng là thời gian

thực hiện của IFW_FDAR_DelObj, IFSD. Bảng 3.12 chỉ ra rằng thời gian thực hiện

của thuật toán IFW_FDAR_DelObj cao hơn thuật toán IFSD trên tất cả các bộ dữ liệu

vì thuật toán IFW_FDAR_DelObj cần nhiều thời gian để xử lý bộ phân lớp.

Bảng 3.13 Thời gian thực hiện của thuật toán IFW_FDAR_DelObj và IFSD (tính bằng giây)

Stt

Bộ dữ liệu

Audiology

Dermatology

Arrhythmia

4 Mfeat-factor

Chess-kr-vs-kp

Statimage

T1 1.15 1.84 2.26 2.98 1.18 2.16 2.86 3.12 9.98 13.26 18.64 22.36 28.67 34.16 39.08 48.58 21.06 28.65 34.08 39.89 58.29 74.28 79.14

T2 0.98 1.36 1.82 2.24 1.02 1.84 2.26 2.84 7.06 9.84 12.16 15.06 23.16 28.68 32.36 38.64 18.06 23.08 29.16 33.18 51.18 68.24 72.06

Tập đối tượng bị loại U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3

7 Mushroom

Letter

86.68 19.26 24.76 30.12 39.08 116.78 128.68 199.46 228.69

78.85 16.46 20.08 24.58 32.06 98.06 112.87 178.89 202.65

U4 U1 U2 U3 U4 U1 U2 U3 U4

3,5

n ệ i h

2,5

c ự h t

1,5

n a i g

IFW_FDAR_Del Obj

IFSD

i ờ h T

0,5

U1 U2 U3 U4

Tập đối tượng bị loại của Bộ dữ liệu Audiology

Hình 3.3 Thời gian thực hiện các thuật toán IFW_FDAR_DelObj và IFSD

3.3.5.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

Kết quả của độ chính xác phân lớp thu được bởi IFW_FDAR_DelObj và IFSD

được trình bày ở Bảng 3.14 với là số lượng thuộc tính của tập rút gọn, Acc là độ

chính xác phân lớp của tập rút gọn. Theo kết quả trong bảng này, độ chính xác phân

lớp của thuật toán IFW_FDAR_DelObj cao hơn thuật toán IFSD trên tất cả các bộ dữ

liệu. Hơn nữa, số thuộc tính trong tập rút gọn của thuật toán IFW_FDAR_DelObj nhỏ

hơn thuật toán IFSD.

Bảng 3.14 Độ chính xác phân lớp của thuật toán IFW_FDAR_DelObj và IFSD

IFW_FDAR_DelObj

IFSD

Stt

Bộ dữ liệu

RO

Acc

0.724 ± 0.058

10 0.729 ± 0.086

0.692 ± 0.044

9 0.710 ± 0.032

Audiology

0.687 ± 0.064

8 0.692 ± 0.037

0.689 ± 0.042

8 0.691 ± 0.056

0.894 ± 0.038

7 0.901 ± 0.024

0.923 ± 0.062

6 0.931 ± 0.048

Dermatology

0.923 ± 0.062

6 0.931 ± 0.022

0.912 ± 0.028

5 0.927 ± 0.054

0.745 ± 0.086

15 0.756 ± 0.058

0.713 ± 0.072

13 0.723 ± 0.072

Arrhythmia

0.722 ± 0.069

11 0.739 ± 0.064

0.722 ± 0.034

11 0.739 ± 0.027

0.782 ± 0.052

4 Mfeat-factor

12 0.831 ± 0.064

U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1

0.815 ± 0.083

0.831 ± 0.086

12

0.803 ± 0.092

0.822 ± 0.079

10

0.798 ± 0.058

0.803 ± 0.064

9

0.848 ± 0.073

0.861 ± 0.064

18

0.840 ± 0.058

0.844 ± 0.069

16

Chess-kr-vs-kp

0.831 ± 0.049

0.838 ± 0.018

14

0.831 ± 0.049

0.838 ± 0.026

14

0.837 ± 0.069

0.842 ± 0.046

10

0.837 ± 0.074

0.843 ± 0.038

10

Statimage

0.815 ± 0.082

0.820 ± 0.025

8

0.804 ± 0.078

0.819 ± 0.048

8

0.983 ± 0.038

0.987 ± 0.026

6

0.983 ± 0.069

0.991 ± 0.059

5

7 Mushroom

0.968 ± 0.026

0.972 ± 0.064

4

0.968 ± 0.041

0.972 ± 0.025

4

0.842 ± 0.064

0.857 ± 0.047

8

0.852 ± 0.073

0.860 ± 0.058

8

Letter

0.822 ± 0.028

0.835 ± 0.019

7

0.822 ± 0.034

0.829 ± 0.026

6

U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4 U1 U2 U3 U4

Hình 3.4 Số lượng thuộc tính tập rút gọn của các thuật toán IFW_FDAR_DelObj và IFSD

3.4. Kết luận Chương 3

Trong Chương 3, luận án trình bày kết quả xây dựng các công thức gia tăng tính

khoảng cách mờ đề xuất ở Chương 2 trong trường hợp bổ sung, loại bỏ tập đối tượng.

Dựa vào các công thức gia tăng được xây dựng, luận án trình bày kết quả đề xuất của

hai 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 filter-wrapper:

1) 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.

2) 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ác thuật toán gia tăng đề xuất sử dụng độ đo khoảng cách mờ nên hiệu quả hơn

các thuật toán gia tăng khác sử dụng quan hệ phân biệt giữa các cặp đối tượng trong

tập thô mờ. Kết quả thử nghiệm trên các tập dữ liệu mẫu từ kho dữ liệu UCI cho

những kết luận quan trọng:

Số thuộc tính trong tập rút gọn của thuật toán IFW_FDAR_AdObj nhỏ hơn thuật

toán IV-FS-FRS-2 [54], IARM [18], ASS-IAR [40] và IFSA [36]. Hơn nữa thuật toán

IFW_FDAR_AdObj có độ chính xác phân lớp cao hơn các thuật toán IV-FS-FRS-2,

IARM, ASS-IAR và IFSA.

Số thuộc tính trong tập rút gọn của thuật toán IFW_FDAR_DelObj nhỏ hơn thuật

toán IFSD [36] và thuật toán IFW_FDAR_DelObj có độ chính xác phân lớp cao hơn

thuật toán IFSD.

Về thời gian thực hiện của các thuật toán gia tăng filter-wrapper rút gọn thuộc

tính trong trường hợp bổ sung, loại bỏ tập đối tượng đề xuất đều cao hơn so với các

thuật toán gia tăng filter truyền trống trên tất cả các tập dữ liệu, nguyên nhân là các

thuật toán gia tăng kết hợp filter-wrapper đều mất thêm chi phí thời gian thực hiện bộ

phân lớp trong giai đoạn wrapper, đây cũng là nhược điểm chung của các thuật toán

theo tiếp cận filter-wrapper. Tuy nhiên, với mục tiêu giảm thiểu độ phức tạp và tăng

độ chính xác của tập luật phân lớp thì chi phí về thời gian tìm tập rút gọn của thuật

toán đề xuất là chấp nhận được.

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

Tiếp nối sự thành công của thuật toán gia tăng filter-wrapper sử dụng khoảng

cách mờ trong chương trước, Chương 4 của luận án tiếp tục đề xuất hai thuật toán gia

tăng filter-wrapper sử dụng công thức tính khoảng cách mờ rút gọn thuộc tính trong

trường hợp bổ sung, loại bỏ tập thuộc tính. Dựa trên công thức gia tăng cập nhật

khoảng cách mờ đề xuất, chương này xây dựng các thuật toán gia tăng rút gọn thuộc

tính của bảng quyết định trong trường hợp bổ sung, loại bỏ tập thuộc tính. Thử nghiệm

trên một số bộ dữ liệu cho thấy, thuật toán đề xuất hiệu quả hơn thuật toán gia tăng

filter truyền thống theo tiêu chí đánh giá độ chính xác phân lớp dữ liệu và thời gian

thực hiện của thuật toán.

4.1. Mở đầu

Trong xu thế dữ liệu lớn (Big data) hiện nay, các bảng quyết định ngày càng có

số thuộc tính rất lớn, ví dụ các bảng dữ liệu trong lĩnh vực tin sinh học có hàng triệu

thuộc tính. Hơn nữa, các bảng quyết định luôn luôn thay đổi, cập nhật với các tình

huống như bổ sung và loại bỏ tập đối tượng, bổ sung và loại bỏ tập thuộc tính, giá trị

tập đối tượng, tập thuộc tính thay đổi. Trong đó, trường hợp bổ sung, loại bỏ tập thuộc

tính xuất hiện ngày càng phổ biến. Ví dụ bài toán chẩn đoán bệnh trong lĩnh vực y tế,

các triệu chứng lâm sàng được xem như các thuộc tính ban đầu để bác sĩ chẩn đoán

bệnh. Sau đó, các chỉ số xét nghiệm được xem như các thuộc tính tiếp theo liên tục

được bổ sung, cập nhật nhằm hỗ trợ bác sĩ trong việc nâng cao độ chính xác chẩn

đoán. Để xây dựng mô hình phân lớp hiệu quả, ta cần giải quyết bài toán rút gọn thuộc

tính trên cá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 các bảng quyết định như vậy gặp hai thách

thức. Thứ nhất, với các bảng quyết định có kích thước lớn, việc thực hiện các thuật

toán tìm tập rút gọn gặp khó khăn về không gian lưu trữ và tốc độ tính toán. Thứ hai,

với các bảng quyết định thay đổi, cập nhật, các thuật toán này phải tính toán lại tập rút

gọn trên toà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 thách thức trên, các nhà nghiên cứu đề xuất hướng

tiếp cận tính toán gia tăng tìm tập rút gọn. Các thuật toán gia tăng chỉ cập nhật lại tập

rút gọn trên phần dữ liệu bị thay đổi mà không tính lại tập rút gọn trên toàn bộ bảng

quyết định ban đầu. Do đó, chúng giảm thiểu đáng kể thời gian thực hiện. Hơn nữa,

các thuật toán gia tăng có thể thực hiện được trên các bảng quyết định kích thước lớn

bằng giải pháp chia nhỏ bảng quyết định thành nhiều phần, tập rú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 rút gọn của bảng quyết định đã và

đang thu hút sự quan tâm của các nhà 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 của của Pawlak [19] và các mô hình tập thô mở

rộng, các nhà nghiên cứu đã đề xuất nhiều thuật toán gia tăng tìm tập rút gọn của bảng

quyết định thay đổi. Với trường hợp bổ sung, loại bỏ tập đối tượng, một số thuật toán

gia tăng đề xuất sử dụng khoảng cá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 quán [39], lựa

chọn mẫu kích hoạt [40]. Với trường hợp bổ sung, loại bỏ tập thuộc tính, một số thuật

toán gia tăng tìm tập rú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 rút gọn của bảng quyết định đã được đề xuất với các trường hợp: bổ sung và

loại bỏ tập đối tượng [52, 53, 54, 55, 56], bổ sung và loại bỏ tập thuộc tính [57]. Với

trường hợp bổ sung, loại bỏ tập đối tượng, Liu và cá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 rút gọn

khi bổ sung tập đối tượng. Yang và cá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 rút gọn

khi bổ sung tập đối tượng. Yang và cá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 toán IV-FS-FRS-1 và IV-FS-FRS-2 tìm tập rút gọn trong

trường hợp bổ sung tập đối tượng. Trong Chương 2 của luận án này đã xây dựng công

thức gia tăng tính khoảng cách mờ, trên cơ sở đó trong Chương 3 đã đề xuất hai thuật

toán gia tăng filter – wrapper tìm tập rút gọn: thuật toán IFW_FDAR_AdObj trong

trường hợp bổ sung tập đối tượng và thuật toán IFW_FDAR_DelObj trong trường hợp

loại bỏ tập đối tượng. Zhang và các cộng sự [56] đề xuất thuật toán gia tăng AIFWAR

tìm tập rú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 và cá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 rú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 toán DIAR sử dụng hàm thuộc

mờ và thuật toá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, các kết quả nghiên cứu về các thuật toán gia tăng tìm tập rút gọn theo tiếp

cận tập thô mờ còn hạn chế. Zeng và các cộng sự [58] xây dựng cá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 rút gọn sử dụng độ phụ thuộc mờ: thuật toán

FRSA-IFS-HIS(AA) trong trường hợp bổ sung tập thuộc tính và thuật toá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 các công

trình nêu trên cho thấy, cá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 các thuật toán không gia tăng. Do đó, chúng có thể thực thi hiệu quả trên cá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 các thuật

toán đề xuất đều theo hướng tiếp cận lọc (filter) truyền thống. Với cách tiếp cận này,

tập rút gọn tìm được là 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 xác phân lớp được thực hiện sau khi tìm được tập rút gọn. Do đó,

tập rút gọn thu được chưa phải là lựa chọn tốt nhất trên hai tiêu chí: số lượng thuộc

tính tập rút gọn và độ chính xác phân lớp. Với trường hợp bổ sung, loại bỏ tập đối

tượng nêu trên, các tác giả trong [55, 56] đã đề xuất các thuật toán gia tăng tìm tập rút

gọn theo tiếp cận kết hợp filter-wrapper, trong đó giai đoạn filter tìm các ứng viên tập

rút gọn khi bổ sung thuộc tính có độ quan trọng lớn nhất, giai đoạn wapper tìm tập rút

gọn có độ chính xác phân lớp cao nhất. Các kết quả thử nghiệm cho thấy, tập rút gọn

thu được của cách tiếp cận filter-wrapper giảm thiểu số lượng thuộc tính và cải thiện

độ chính xác phân lớp so với cách tiếp cận filter.

Đồng thời qua kết quả nghiên cứu Chương 3 của luận án cho thấy sự hiệu quả

của thuật toán gia tăng filter-wrapper rút gọn thuộc tính trong trường hợp bổ sung, loại

bỏ tập đối tượng sử dụng khoảng cách mờ. Vì vậy, động lực nghiên cứu của chương

này là tiếp tục áp dụng hướng tiếp cận filter-wrapper vào việc xây dựng các thuật toán

gia tăng tìm tập rút gọn trong trường hợp bổ sung, loại bỏ tập thuộc tính nhằm giảm

thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp.

Từ những vấn đề phân tích nêu trên, trong chương nà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 khoảng cách mờ (được đề xuất ở Chương 2) trong

trường hợp bổ sung, loại bỏ tập thuộc tính. Dựa trên các công thức tính toán gia tăng

khoảng cách mờ được xây dựng, luận án trình bày 02 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 kết hợp filter-wrapper:

1) Thuật toá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.

2) Thuật toá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.

Hai thuật toán đề xuất nêu trên đều theo tiếp cận kết hợp filter-wrapper, hai thuật

toán nêu trên nhằm mục tiê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.

Kết quả nghiên cứu ở chương này được công bố ở công trình số 4, phần “Danh

mục công trình của tác giả”.

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

Cho bảng quyết định với khi đó, khoảng cách

mờ giữa hai tập thuộc tính C và D theo Mệnh đề 2.3 được đề xuất trong Chương 2

được xác định như sau:

Mệnh đề 4.1. Cho bảng quyết định với . Giả sử tập

thuộc tính điều kiện B được bổ sung vào 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ờ trên B, C, D tương ứng. Khi đó ta có:

1) Nếu với mọi thì

2) Nếu với mọi thì

3) Nếu với mọi thì

Chứng minh: Khi bổ sung thêm B vào C, theo mục 2.4 của Chương 2 về khoảng cách

mờ được xác định như sau:

1) Nếu với mọi thì và .

Từ đó ta có:

2) Từ ta có và với mọi . Từ đó ta có:

3) Từ ta có và với mọi . Từ đó ta có:

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 khoảng cá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 với . Đặt , , là các ma

trận tương đươ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 mọi thì R là tập rút gọn của

2) Nếu với mọi thì B chứa một tập rút gọn của

Chứng minh:

1) Theo Mệnh đề 4.1, nếu với thì

. Do R là tập rút gọn của DS nên

và

. Theo Định nghĩa 2.1 của Chương 2, R

là tập rút gọn của .

2) Cũng theo Mệnh đề 4.1, nếu với thì

, nghĩa là tồn tại sao cho thỏa mãn

Định nghĩa 1 về tập rút gọn của .

Dựa trên Mệnh đề 4.2, đề xuất thuật toán gia tăng filter-wrapper tìm tập rút gọn

trong bảng quyết định sử dụng khoảng cách mờ khi bổ sung tập thuộc tính B vào C.

Thuật toán gồm hai giai đoạn: giai đoạn filter tìm các ứng viên cho tập rút gọn mỗi khi

bổ sung thuộc tính có độ quan trọng lớn nhất, giai đoạn wapper tìm tập rút gọn có độ

chính xác phân lớp cao nhất. Thuật toán được mô tả như sau:

Thuật toán IFW_FDAR_AA (Incremental Filter-Wrapper Fuzzy Distance-based Attribute Reduction Algorithm when Adding Attributes).

Đầu vào:

Bảng quyết định với , tập 1)

rút gọn , các ma trận tương đương mờ

, của các quan hệ tương đương mờ ,

khoảng cách mờ ;

Tập thuộc tính bổ sung B với ; 2)

Đầu ra: Tập rút gọn của

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

Tính ma trận quan hệ tương đương mờ ; 2.

với mọi then Return ; 3. If

với mọi then ; //Tìm 4. If

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

each tính 7. For

với

được tính bởi công thức trong Mệnh đề 3.7.

sao cho ; 8. Chọn

; 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

Đặt //t là số phần tử của T, T chứa các 12.

chuỗi thuộc tính được chọn, nghĩa là

;

13. Đặt

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;

với có độ chính xác phân lớp cao nhất. 15.

Return ;

Tiếp theo, chúng tôi đánh giá độ phức tạp của thuật toán IFW_FDAR_AA. Ký

hiệu tương ứng là số thuộc tính điều kiện, số đối tượng và số thuộc tính điều

kiện bổ sung thêm. Ở câu lệnh 2, độ phức tạp tính quan hệ tương đương mờ là

. Trong trường hợp tốt nhất, thuật toán kết thúc ở câu lệnh 3 (tập rút gọn

không thay đổi). Khi đó, độ phức tạp thuật toán IFW_FDAR_AA là .

Ngược lại xét vòng lặp While từ câu lệnh 5 đến 11, để tính ta phải tính

. Độ phức tạp tính là . Do đó, độ

phức tạp của vòng lặp While là và độ phức tạp của giai đoạn filter là

. Giả sử độ phức tạp của bộ phân lớp là , khi đó độ phức tạp của giai

đoạn wrapper là . Vì vậy, độ phức tạp của thuật toán IFW_FDAR_AA là

. Nếu thực hiện thuật toán không gia tăng filter-wrapper

FW_FDAR trong mục 2.4 của Chương 2 trực tiếp trên bảng quyết định có số thuộc

tính , độ phức tạp là . Do đó, thuật toán gia tăng

IFW_FDAR_AA giảm thiểu đáng kể độ phức tạp thời gian thực hiện, đặc biệt trong

trường hợp nhỏ.

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

Trong phần này, chúng tôi trình bày kết quả thử nghiệm nhằm đánh giá tính

hiệu quả của thuật toá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

gọn và độ chính xác của mô hình phân lớp. FRSA-IFS-HIS(AA) là thuật toán gia tăng

filter tìm tập rút gọ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

Việc thử nghiệm được thực hiện trên 06 bộ dữ liệu mẫu lấy từ kho dữ liệu UCI

[59] được mô tả ở Bảng 3.14. Trên mỗi tập dữ liệu, với các thuộc tính có miền giá trị

thực, chúng tôi chuẩn hóa miền dữ liệu về đoạn [0, 1] sử dụng công thức [9,54]

với max(a), min(a) là giá trị lớn nhất, nhỏ nhất trên miền giá trị thuộc tính a. Chúng tôi

sử dụng quan hệ tương đương mờ trong [9,54] trên thuộc tính a như sau

với

Với các thuộc tính có miền giá trị định danh hoặc nhị phân (nominal hoặc

binary), chúng tôi sử dụng quan hệ tương đương , với

Trên thuộc tính quyết định chúng tôi sử dụng quan hệ tương đương

. Phân hoạch với là một lớp

tương đương. Khi đó, lớp tương đương được xem là lớp đương đương mờ, ký

hiệu là , với hàm thuộc nếu và nếu .

Mỗi tập thuộc tính được chia ngẫu nhiên thành hai phần: tập thuộc tính ban đầu

(cột 5 Bảng 4.1) ký hiệu là C0, và tập thuộc tính gia tăng (cột 6 Bảng 4.1). Tập thuộc

tính gia tăng được chia ngẫu nhiên thành 5 phần bằng nhau, ký hiệu tương ứng là C1,

C2, C3, C4, C5.

Bảng 4.1 Bộ dữ liệu thử nghiệm

STT

Tập dữ liệu

Số lớp quyết định

Số đối tượng

Số thuộc tính điều kiện

Số thuộc tính ban đầu

Số thuộc tính gia tăng

(1)

(2)

(3)

(4)

(5)

(6)

(7)

360

Libras movement (Libra)

569

Wisconsin diagnostic breast cancer (WDBC)

Horse colic (Horse)

368

690

Credit approval (Credit)

1000

German credit data (German)

6 Waveform (Wave)

5000

11 4.2.3.3. Phương pháp, công cụ và môi trường thử nghiệm

Để tiến hành thử nghiệm hai thuật toán IFW_FDAR_AA và FRSA-IFS-

HIS(AA), trước hết chúng tôi thực hiện hai thuật toán trên tập dữ liệu với tập thuộc

tính ban đầu (coi tập thuộc tính ban đầu là tập gia tăng). Tiếp theo, thực hiện hai thuật

toán khi lần lượt bổ sung từ phần thứ nhất đến phần thứ năm của tập thuộc tính gia

tăng. Với thuật toán đề xuất theo tiếp cận lai filter-wrapper IFW_FDAR_AA, chúng tôi sử dụng bộ phân lớp CART (cây phân lớp, hồi quy) để tính độ chính xác phân lớp

trong bước tìm tập rút gọn có độ chính xác tốt nhất. Chúng tôi sử dụng phương pháp

kiểm tra chéo 10-fold, nghĩa là bộ dữ liệu được chia thành 10 phần xấp xỉ bằng nhau,

lấy ngẫu nhiên 1 phần làm bộ dữ liệu kiểm tra, 9 phần còn lại làm dữ liệu huấn luyện.

Quá trình được lặp lại 10 lần. Công cụ thực hiện thử nghiệm là Matlab R2016a. Môi

trường thử nghiệm là máy tính PC với cấu hình Intel(R) Core(TM) i7-3770CPU

@3.40 GHz, sử dụng hệ điều hành Windows 7, 32 bit.

4.2.3.4. 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)

Bảng 4.2 và Hình 4.1 trình bày kết quả so sánh về số lượng thuộc tính tập rút

gọn (ký hiệu là ) và độ chính xác phân lớp của hai thuật toán IFW_FDAR_AA và

FRSA-IFS-HIS(AA). Kết quả Bảng 4.2 cho thấy, với mỗi bước lặp khi bổ sung tập

thuộc tính gia tăng và trên toàn bộ thuộc tính, độ chính xác phân lớp của

IFW_FDAR_AA cao hơn FRSA-IFS-HIS(AA) một chút trên tất cả các tập dữ liệu. Hơn nữa, số thuộc tính tập rút gọn của IFW_FDAR_AA nhỏ hơn khá nhiều FRSA- IFS-HIS(AA), đặc biệt trên tập rút gọ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 của tập luật phân lớp trên tập rút gọn của

IFW_FDAR_AA hiệu quả hơn so với FRSA-IFS-HIS(AA).

Bảng 4.2 Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của IFW_FDAR_AA và FRSA-IFS-HIS(AA)

IFW_FDAR_AA

FRSA-IFS- HIS(AA)

STT

Tập dữ liệu

Tập thuộc tính

Số thuộc tính

Tổng số thuộc tính

Độ chính xác

58.45

56.94

59.02

58.72

59.95

59.24

Libra

61.48

60.98

61.87

61.26

61.48

100

10

62.16

76.14

75.96

79.02

78.25

79.02

79.82

WDBC

85.98

84.85

93.18

89.36

92.86

6

93.18

80.26

78.47

82.49

81.06

82.49

81.06

Horse

84.78

83.92

85.02

84.45

86.26

9

86.75

78.64

77.92

81.92

80.15

84.26

82.39

Credit

84.26

82.39

86.05

84.72

85.96

6

86.05

72.16

70.46

72.16

72.02

73.08

German

73.08

74.28

73.92

74.16

7

74.28

65.96

65.02

68.72

67.78

69.08

68.25

Wave

69.08

68.97

70.88

70.02

70.85

101

8

71.49

Hình 4.1.a. Tập dữ liệu Libra

Hình 4.1.b. Tập dữ liệu WDBC

102

Hình 4.1.c. Tập dữ liệu Horse

Hình 4.1.e. Tập dữ liệu Credit

Hình 4.1.f. Tập dữ liệu German

p ớ l

IFW_FDAR_A A

n â h p

c á x

h n í h c

ộ Đ

C0 C1 C2 C3 C4 C5

Các tập thuộc tính của dữ liệu Wave

103

Hình 4.1.g. Tập dữ liệu Wave

Hình 4. 1 Độ chính xác phân lớp của các thuật toán IFW_FDAR_AA và FRSA-IFS-HIS(AA)

4.2.3.5. 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)

Bảng 4.3 và Hình 4.2 trình bày kết quả 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 quả Bảng 4.3

cho thấy, thời gian thực hiện của IFW_FDAR_AA cao hơn FRSA-IFS-HIS(AA) trên

tất cả 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 đoạn wrapper, đây cũng là nhược điểm chung của các thuật

toán theo tiếp cận filter-wrapper. Tuy nhiên, với mục tiêu giảm thiểu độ phức tạp và

tăng độ chính xác của tập luật phân lớp thì chi phí về thời gian tìm tập rút gọn của

thuật toán đề xuất là chấp nhận được.

Bảng 4.3 Thời gian thực hiện của IFW_FDAR_AA và FRSA-IFS-HIS(AA)

(Tính bằng s)

IFW_FDAR_AA

FRSA-IFS- HIS(AA)

STT

Tập dữ liệu

Tập thuộc tính

Số thuộc tính

Thời gian

Tổng thời gian

Thời gian

Tổng thời gian

Tổng số thuộ c tính

4.26

3.68

0.42

4.68

0.24

3.92

Libra

0.46

5.14

0.35

4.27

0.61

5.75

0.27

4.54

0.57

6.32

0.22

4.76

0.52

6.84

0.16

104

4.92

2.92

2.16

0.33

3.25

0.28

2.44

0.34

3.59

0.32

2.76

2 WDBC

0.22

3.81

0.20

2.96

0.21

4.02

0.18

3.14

0.24

4.26

0.16

3.30

1.86

1.45

0.29

2.15

0.17

1.62

0.19

2.34

0.18

1.80

Horse

0.24

2.59

0.18

1.98

0.13

2.72

0.17

2.15

0.22

2.94

0.20

2.35

2.05

1.74

0.24

2.29

0.18

1.92

0.29

2.58

0.22

2.14

Credit

0.26

2.84

0.21

2.35

0.28

3.12

0.20

2.55

0.22

3.34

0.18

2.73

3.08

2.64

0.21

3.29

0.17

2.81

0.30

3.59

0.17

2.98

German

0.32

3.91

0.21

3.19

0.38

4.29

0.24

3.43

0.35

4.64

0.26

3.69

64.56

56.02

64.56

56.02

8.00

72.56

6.8

62.82

6.52

79.08

5.62

68.44

6 Wave

7.17

86.25

6.08

74.52

5.79

92.04

4.94

79.46

6.68

98.72

5.18

84.64

105

Hình 4.2 Thời gian thực hiện của thuật toán IFW_FDAR_AA và FRSA-IFS-HIS(AA)

Tiếp theo, chúng tôi trình bày thuật toán filter-wrapper tìm tập rút gọn sử dụng

khoảng cách mờ khi loại bỏ tập thuộc tính theo hướng tiếp cận tính toán gia tăng.

Trước hết, chúng tôi xây dựng các công thức cập nhật khoảng cách khi loại bỏ tập

thuộc tính.

106

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

Chứng minh: 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

Dựa trên Mệnh đề 4.3, thuật toán gia tăng filter-wrapper tìm tập rút gọn trong

bảng quyết định sử dụng khoảng cách mờ khi loại bỏ tập thuộc tính B như sau:

Thuật toán IFW_FDAR_DA (Incremental Filter-Wrapper Fuzzy Distance-based Attribute Reduction Algorithm when Deleting Attributes). Đầu vào:

Bảng quyết định với , tập 1)

rút gọn , các ma trận tương đương mờ ,

, khoảng cách mờ ;

Tập thuộc tính B loại bỏ khỏi C với ; 2)

107

Đầ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

2) Trường hợp 2: If không gia tăng filter-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.

then thực hiện các bước

3) Trường hợp 3: If của thuật toán tìm tập rút gọn.

; // Chứa các ứng viên tập rút Bước 1: Khởi tạo ; 1. Đặt gọn

, 2.Tính ma trận tương đương mờ

//Xét các thuộc tính trong tập rút gọn 3.Đặt

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 4. While

tính 5. Begin 6. For each

với

được tính bởi công thức trong

3.9;

sao cho ; 7. Chọn

; 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

//t là số phần tử của T, T chứa các

11. Đặt 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;

với có độ chính xác phân lớp lớn

14. nhất.

108

; 15. Return

Tiếp theo, chúng tôi đánh giá độ phức tạp của thuật toán IFW_FDAR_DA. Ký

hiệu tương ứng là số thuộc tính điều kiện, số đối tượng và số thuộc tính điều

kiện xóa khỏi C.

Trường hợp tốt nhất, thuật toán rơi vào Trường hợp 1, nghĩa là tập rút gọn không

thay đổi.

Trường hợp xấu nhất, thuật toán rơi vào Trường hợp 2, thực hiện lại thuật toán

FW_FDAR tìm tập rút gọn trên bảng quyết định sau khi xóa tập thuộc tính B với độ

phức tạp là: .

Tiếp theo, ta xét độ phức tạp trong Trường hợp 3. Xét vòng lặp While từ câu

lệnh 4 đến 10, để tính ta phải tính . Độ phức tạp tính

là . Do đó, độ phức tạp của vòng lặp While là

và độ phức tạp của giai đoạn filter là . Giả sử độ

phức tạp của bộ phân lớp là , khi đó độ phức tạp của giai đoạn wrapper là

. Vì vậy, độ phức tạp của thuật toán IFW_FDAR_DA là

. Nếu thực hiện thuật toán không gia tăng filter-

wrapper FW_FDBAR trực tiếp trên bảng quyết định có số thuộc tính , độ phức

tạp là . Do đó, với Trường hợp 3 thì thuật toán

IFW_FDAR_DA hiệu quả. Nếu R càng nhỏ thì thuật toán IFW_FDAR_DA càng hiệu

quả. Nếu thuật toán rơi vào Trường hợp 2 (tính lại tập rút gọn) thì độ phức tạp thuật

toán IFW_FDAR_DA tương đương thuật toán FW_FDBAR .

4.4. Kết luận Chương 4

Trong Chương 4, luận án trình bày kết quả xây dựng các công thức gia tăng tính

khoảng cách mờ đề xuất ở Chương 2 trong trường hợp bổ sung, loại bỏ tập thuộc tính.

Dựa vào các công thức gia tăng được xây dựng, luận án trình bày kết quả đề xuất hai

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

109

1)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.

2)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.

Các thuật toán gia tăng đề xuất sử dụng độ đo khoảng cách mờ nên hiệu quả hơn

các thuật toán gia tăng khác sử dụng quan hệ phân biệt giữa các cặp đối tượng trong

tập thô mờ. Kết quả thử nghiệm trên các tập dữ liệu mẫu từ kho dữ liệu UCI cho

những kết luận quan trọng:

Độ chính xác phân lớp của thuật toán IFW_FDAR_AA cao hơn thuật toán

FRSA-IFS-HIS(AA) trên tất cả các tập dữ liệu. Hơn nữa, số thuộc tính tập rút gọn của

IFW_FDAR_AA nhỏ hơn khá nhiều FRSA-IFS-HIS(AA), đặc biệt trên tập rút gọn có

số thuộc tính lớn như Libra.

Về thời gian thực hiện của các thuật toán gia tăng filter-wrapper đề xuất đều cao

hơn so với các thuật toán gia tăng filter truyền trống trên tất cả các tập dữ liệu, nguyên

nhân là các thuật toán gia tăng kết hợp filter-wrapper đều mất thêm chi phí thời gian

thực hiện bộ phân lớp trong giai đoạn wrapper, đây cũng là nhược điểm chung của các

thuật toán theo tiếp cận filter-wrapper. Tuy nhiên, với mục tiêu giảm thiểu độ phức tạp

và tăng độ chính xác của tập luật phân lớp thì chi phí về thời gian tìm tập rút gọn của

thuật toán đề xuất là chấp nhận được.

110

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 gọn của bảng

quyết định nhằm giảm thiểu số lượng thuộc tính tập rút gọn, từ đó giảm thiểu độ phức tạp

của mô hình phân lớp và nâng cao độ chính xác của mô hình phân lớp. Kết quả chính của

luận án bao gồm:

(1) Đề 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.

(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 thuộc tính. Đóng góp này được

trình bày ở Chương 4 của luận án.

2. Định hướng phát triển

(1) Triển khai các thuật toán đề xuất vào việc giả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 các lĩnh vực khác nhau như dữ liệu gen trong tin sinh học…

(2) Tiếp tục nghiên cứu, đề xuất các thuật toán gia tăng filter-wrapper hiệu quả

nhằm giả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.

111

DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ

STT TÊN BÀI BÁO

Nguyen Long Giang, Le Hoang Son, Tran Thi Ngan, Tran Manh Tuan, Ho Thi Phuong, Mohamed Abdel-Basset, Antônio Roberto L. de Macêdo, VictorHugo C. de Albuquerque, “Novel Incremental Algorithms for Attribute Reduction from DynamicDecision Tables using Hybrid Filter– Wrapper with Fuzzy Partition Distance”, IEEE Transactions on Fuzzy Systems, Volume 28, Issue 5, pp. 858-873, 2020 (SCIE, Q1, IF = 9.518).

Hồ Thị Phượng, Cao Chính Nghĩa, Nguyễn Long Giang, Nguyễn Ngọc Cương, “Về mộ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 khoảng cách mờ”, Kỷ yếu Hội thảo Quốc gia lần thứ XXII - Một số vấn đề chọn lọc của CNTT và TT, Thái Bình, 28-29/6/2019, Tr. 333- 339.

Hồ Thị Phượng, Cao Chính Nghĩa, Nguyễn Long Giang, “Về thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định sử dụng khoảng cách mờ”, Kỷ yếu Hội thảo Quốc gia lần thứ XXII - Một số vấn đề chọn lọc của CNTT và TT, Quảng Ninh, 5-6/11/2020, Tr. 483-490.

Ho Thi Phuong, Nguyen Long Giang, “fuzzy distance-based filter-wrapper incremental algorithms for attribute reduction when adding or deleting attribute set”, Vietnam Journal of Science and Technology - Vietnam Academy of Science and Technology. Accepted (06/01/2021)

112

TÀI LIỆU THAM KHẢO

[1] D. Dübois, H. Prade, “Rough fuzzy sets and fuzzy rough sets”, International

Journal of General Systems 17, pp.191-209, 1990.

[2] Anoop Kumar Tiwari, Shivam Shreevastava, Tanmoy Som, K.K. Shukla,

“Tolerance-based intuitionistic fuzzy-rough set approach for attribute

reduction”, Expert Systems With Applications 101, pp. 205–212, 2018.

[3] Z. Wang, Y.L. Qi, M.W. Shao, Q.H. Hu, D.G. Chen, Y.H. Qian, Y.J. Lin, “A

Fitting Model for Feature Selection with Fuzzy Rough Sets”, IEEE

Transactions on Fuzzy Systems, Volume: 25, Issue: 4, pp. 741-753, 2017.

[4] Zhang, C.L. Mei, D.G. Chen, Y.Y. Yang, “A fuzzy rough set-based feature

selection method using representative instances”, Knowledge-Based Systems,

Vol. 151, pp. 216-229, 2018.

[5] T.K. Sheeja, A. Sunny Kuriakose, “A novel feature selection method using

fuzzy rough sets”, Computers in Industry 97, pp. 111- 116, 2018.

[6] Y. Lin, Y. Li, C. Wang, J. Chen, “Attribute reduction for multi-label learning

with fuzzy rough set”, Knowl.-Based Syst. 152, pp. 51-61, 2018.

[7] J.H. Dai, Y.J. Yan, Z.W. Li, B.S. Liao, “Dominance-based fuzzy rough set

approach for incomplete interval-valued data”, Journal of Intelligent & Fuzzy

Systems 34, pp. 423-436, 2018.

[8] Q.H. Hu, D.R. Yu, Z.X. Xie, “Information-preserving hybrid data reduction

based on fuzzy-rough techniques”, Pattern Recognit. Lett. 27(5), pp. 414-423,

2016.

[9] X. Zhang, C.L. Mei, D. G. Chen, J. Li, “Feature selection in mixed data: A

method using a novel fuzzy rough set-based information entropy”, Pattern

Recognition 56, pp. 1-15, 2016.

[10] C.Z. Wang, Y.Huang, M.W. Shao, X.D.Fan, “Fuzzy rough setbased attribute

reduction using distance measures”, Knowledge-Based Systems, Vol. 164,

2019, pp. 205-212.

[11] C.Z. Wang, Y. Qi, Q. He, “Attribute reduction using distancebased fuzzy rough

113

sets”, International Conference on Machine Learning and Cybernetics, IEEE,

2015.

[12] Cao Chinh Nghia, Demetrovics Janos, Nguyen Long Giang, Vu Duc Thi,

“About a fuzzy distance between two fuzzy partitions and attribute reduction

problem”, Cybernetics and Information Technologies, Vol 16, No 4, pp. 13-28,

2016

[13] J.H. Dai, H. Hu, W.Z. Wu,Y.H. Qian, D.B. Huang, “Maximal Discernibility

Pairs Based Approach to Attribute Reduction in Fuzzy Rough Sets”, IEEE

Transactions on Fuzzy Systems, Vol. 26, Issue 4, pp. 2174-2187, 2018.

[14] J.H. Dai, Q.H. Hu, H. Hu, D.B.Huang, “Neighbor inconsistent pair selection for

attribute reduction by rough set approach”. IEEE Transactions on Fuzzy

Systems, Vol. 26, Issue 2, pp. 937-950, 2017.

[15] L.J.Ping, Z. W. Xia, T.Z. Hui, X.Y. Fang, M. T. Yu, Z.J. Jing, Z. G. Yong, J. P.

Niyoyita, “learning with fuzzy rough set-based attribute selection”, Expert

Systems with Applications, Vol. 139, pp. 1- 17, 2020.

[16] W.P. Ding, C.T. Lin, Z.H. Cao, “Deep neuro-cognitive coevolution for fuzzy

attribute reduction by quantum leaping PSO with nearest-neighbor

memeplexes”, IEEE Transactions on Cybernetics, 49(7):2744-2757, 2019

[17] X.M. Liu, C. Shen, W. Wang, X.H. Guan, “CoEvil: A Coevolutionary Model

for Crime Inference Based on Fuzzy Rough Feature Selection”, IEEE

Transactions on Fuzzy Systems, Early Access, 2019.

[18] Y.J. Lin, Q.H. Hu, J.H. Liu, J.J. Li, X.D. Wu, “Streaming feature selection for

multi-label learning based on fuzzy mutual information”, IEEE Transactions on

Fuzzy Systems, Vol. 25, Issue 6, pp. 1491-1507, 2017.

[19] Z. Pawlak, Rough sets: Theoretical Aspects of Reasoning about Data, Kluwer

Academic Publisher, London, 1991.

[20] Demetrovics, J., Thi, V.D., & Giang, N.L. (2014). Metric Based Attribute

Reduction in Dynamic Decision systems. Annales Univ. Sci. Budapest., Sect.

Comp, Vol. 42, 157-172.

[21] Huong, N. T. L., &Giang, N. L. (2016). Incremental algorithms based on metric

114

for finding reduct in dynamic decision systems. Journal on Research and

Development on Information & Communications Technology, Vol.E-3, No.9,

26-39.

[22] Y.G. Jing, T.R. Li, J.F. Huang, H.M. Chen, S.J. Horng, “A Group Incremental

Reduction Algorithm with Varying Data Values”, International Journal of

Intelligent Systems 32(9), pp. 900-925, 2017.

[23] Y.G. Jing, T.R. Li, H. Fujita, Z. Yu, B. Wang, “An incremental attribute

reduction approach based on knowledge granularity with a multi-granulation

view”, Information Sciences 411, pp. 23-38, 2017.

[24] Zhang, C., Dai, J. & Chen, J. (2020). Knowledge granularity based incremental

attribute reduction for incomplete decision systems. International Journal of

Machine Learning and Cybernetics. https://doi.org/10.1007/s13042-020-01089-4.

[25] Cai, M.J., Lang, G.M., Hamido, F., Li, Z.Y., &Yang, T. (2019). Incremental

approaches to updating reducts under dynamic covering granularity.

Knowledge-Based Systems 172, 130-140.

[26] Zhang, C., &Dai, J. (2019). An incremental attribute reduction approach based

on knowledge granularity for incomplete decision systems. Granular

Computing, 1-15.

[27] Zhang, C., Dai, J. &Chen, J. (2020). Knowledge granularity based incremental

attribute reduction for incomplete decision systems. International Journal of

Machine Learning and Cybernetics. https://doi.org/10.1007/s13042-020-01089-4.

[28] W. Wei, X.Y. Wu, J.Y. Liang, J.B. Cui, Y.J. Sun, “Discernibility matrix based

incremental attribute reduction for dynamic data”, Knowledge-Based Systems,

Vol. 140, pp. 142-157, 2018.

[29] G. Lang, Q. Li, M. Cai, T. Yang, Q. Xiao, “Incremental approaches to

knowledg reduction based on characteristic matrices”, Int. J. Mach. Learn.

Cybern. 8 (1) pp. 203-222, 2017.

[30] Ma, F.M., Ding, M.W., Zhang, T.F., &Cao, J. (2019). Compressed binary

115

discernibility matrix based incremental attribute reduction algorithm for group

dynamic data. Neurocomputing, Vol. 344, No. 7, 20-27.

[31] Yang, C.J., Ge, H., Li, L.S., &Ding, J. (2019). A unified incremental reduction

with the variations of the object for decision tables. Soft Computing 23, 6407-

6427.

[32] Liu, Y., Zheng, L.D., Xiu, Y.L., Yin, H., Zhao, S.Y., Wang, X.H., Chen, H., &Li,

C.P. (2020). Discernibility matrix based incremental feature selection on fused

decision tables. International Journal of Approximate Reasoning 118, 1-26.

[33] Das, A. K., Sengupta, S., & Bhattacharyya, S. (2018). A group incremental

feature selection for classification using rough set theory based genetic

algorithm. Applied Soft Computing, 65, 400-411.

[34] Lang, G., Cai, M., Fujita, H., &Xiao, Q. (2018). Related families-based

attribute reduction of dynamic covering decision information

systems. Knowledge-Based Systems, 162, 161-173.

[35] Hao, G., Longshu, L., Chuanjian, Y., &Jian, D. (2019). Incremental reduction

algorithm with acceleration strategy based on conflict region. Artificial

Intelligence Review, 51(4), 507-536.

[36] Shua, W.H., Qian, W.B., &Xie, Y.H. (2019). Incremental approaches for

feature selection from dynamic data with the variation of multiple objects.

Knowledge-Based Systems, Vol. 163, 320-331.

[37] Nandhini, N., &Thangadurai, K. (2019). An incremental rough set approach for

faster attribute reduction, International Journal of Information Technology.

https://doi.org/10.1007/s41870-019-00326-6.

[38] Shu, W.H., Qian, W., &Xie, Y. (2020). Incremental feature selection for

dynamic hybrid data using neighborhood rough set. Knowledge-Based Systems

194, 105516.

[39] Xie, X., &Qin, X. (2018). A novel incremental attribute reduction approach for

dynamic incomplete decision systems. International Journal of Approximate

Reasoning, 93, 443-462.

[40] Y.Y. Yang, D.G. Chen, H. Wang, “Active Sample Selection Based Incremental

116

Algorithm for Attribute Reduction With Rough Sets”, IEEE Transactions on

Fuzzy Systems, Vol. 25, Issue 4, pp. 825- 838, 2017.

[41] W.H. Shu, H. Shen, “Updating attribute reduction in incomplete decision

systems with the variation of attribute set”, International Journal of

Approximate Reasoning, vol. 55, no.3, pp. 867-884, 2014.

[42] F. Wang, J.Y. Liang, Y.H. Qian, “Attribute reduction: A dimension incremental

strategy”, Knowledge-Based Systems, Volume 39, pp. 95-108, 2013.

[43] M.J. Cai, Q.G. Li, J.M. Ma, “Knowledge reduction of dynamic covering

decision information systems caused by variations of attribute values”,

International Journal of Machine Learning and Cybernetics 8(4), pp. 1131-

1144, 2017.

[44] Ma, F.M., Ding, M.W., Zhang, T.F., &Cao, J. (2019). Compressed binary

discernibility matrix based incremental attribute reduction algorithm for group

dynamic data. Neurocomputing, Vol. 344, No. 7, 20-27.

[45] Wei, W., Song, P., Liang, J.Y., &Wu, X.Y. (2019). Accelerating incremental

attribute reduction algorithm by compacting a decision system. International

Journal of Machine Learning and Cybernetics 10, 2355-2373.

[46] Nandhini, N., &Thangadurai, K. (2019). An incremental rough set approach for

faster attribute reduction, International Journal of Information Technology.

https://doi.org/10.1007/s41870-019-00326-6.

[47] Chen, D.G., Dong, L.J., &Mi, J.H. (2020). Incremental mechanism of attribute

reduction based on discernible relations for dynamically increasing attribute.

Soft Computing 24, 321-332.

[48] Demetrovics Janos, Nguyen Thi Lan Huong, Vu Duc Thi, Nguyen Long Giang,

“Metric Based Attribute Reduction Method in Dynamic Decision Tables”,

Cybernetics and Information Technologies, Vol.16, No.2, pp. 3-15, 2016.

[49] M.S. Raza,U. Qamar, “An incremental dependency calculation technique for

feature selection using rough sets”, Information Sciences 343–344, pp. 41–65,

2016.

[50] Y. Jing, T. Li, J. Huang, et al., “An incremental attribute reduction approach

117

based on knowledge granularity under the attribute generalization”, Int. J.

Approx. Reason. 76, pp.80-95, 2016.

[51] Y.G. Jing, T.R. Li, H. Fujita, B.L. Wang, N. Cheng, “An incremental attribute

reduction method for dynamic data mining”, Information Sciences 465, pp. 202-

218, 2018.

[52] Y.M. Liu, S.Y. Zhao, H. Chen, C.P. Li, Y.M. Lu, “Fuzzy Rough Incremental

Attribute Reduction Applying Dependency Measures”, APWeb-WAIM 2017:

Web and Big Data, pp 484-492, 2017.

[53] Y.Y. Yang, D.G. Chen, H. Wang, Eric C.C.Tsang, D.L. Zhang, “Fuzzy rough

set based incremental attribute reduction from dynamic data with sample

arriving”, Fuzzy Sets and Systems, Volume 312, pp. 66-86, 2017

[54] Y.Y. Yang, D.G. Chen, H. Wang, X.H. Wang, “Incremental perspective for

feature selection based on fuzzy rough sets”, IEEE Transactions on Fuzzy

Systems, Vol. 26, Issue 3, pp. 1257-1273, 2017.

[55] Vu Van Dinh, Vu Duc Thi, Ngo Quoc Tao, Nguyen Long Giang, “Partition

Distance Based Attribute Reduction in Incomplete Decision Tables”, Journal on

Information Communications Technology, Research and Development on

Information & Communications Technology, Vol. V-2, No. 14(34), pp. 23-32,

12-2015.

[56] Zhang, X., Mei, C.L., Chen, D.G., Yang, Y.Y., &Li, J.H. (2020). Active

Incremental Feature Selection Using a Fuzzy-Rough-Set-Based Information

Entropy. IEEE Transactions on Fuzzy Systems, Volume 28, Issue 5, 901-915.

[57] Ni, P., Zhao, S.Y., Wang, X.H., Chen, H., Li, C.P., Tsang, E.C.C (2020).

Incremental Feature Selection Based on Fuzzy Rough Sets. Information

Sciences.

[58] A.P. Zeng, T.R. Li, D. Liu, J.B. Zhang, H.M. Chen, “A fuzzy rough set

approach for incremental feature selection on hybrid information systems”,

Fuzzy Sets and Systems, Vol. 258, pp. 39-60, 2015.

[59] The UCI machine

118

learning repository, http://archive.ics.uci.edu/ml/

datasets.html. https://sourceforge.net/projects/weka/

[60] Jensen, R., and Q. Shen, Q.(2008), Computational Intelligence and Feature

Selection, Rough and Fuzzy Approaches, Aberystwyth University, IEEE

Computational Intelligence Society, Sponsor.

[61] N. Long, D. Gianola, K.A. Weigel, “Dimension reduction and variable selection

for genomic selection : application to predicting milk yield in Holsteins”, Journal

of Animal Breeding and Genetics. 128 (4), pp. 247–257, 2011.

[62] J. Zhang, T. Li, D. Ruan, “Rough sets based matrix approaches with dynamic

attribute variation in set-valued information systems”, Int. J. Approx. Reason,

Vol.53, pp. 620-635, 2012

[63] Q.H. Hu, Z.X. Xie, D.R. Yu, “Hybrid attribute reduction based on a novel

fuzzy-rough model and information granulation”, Pattern Recognition 40, pp.

3509-3521, 2007.

[64] Y.H. Qian., J.Y. Liang, W.Z. Wu, C.Y. Dang, “Information Granularity in

Fuzzy Binary GrC Model”, IEEE Trans. Fuzzy Syst. 19, No 2, pp. 253-264,

2011.

[65] J.Y. Liang, R. Li, Y. H. Qian, “Distance: A more comprehensible perspective

for measures in rough set theory”, Knowledge-Based Systems, Volume 27, pp.

126-136, 2012.

[66] Nguyễn Long Giang, Nguyễn Thanh Tùng, Vũ Đức Thi, Một phương pháp mới

rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric, Tạp chí

Tin học và Điều khiển học, T.28, S.2, 2012, tr. 129-140.

[67] Long Giang Nguyen, “Metric Based Attribute Reduction in Decision Tables”,

Federated Conference on Computer Science and Information System

(FEDCSIS), Wroclaw, Poland, IEEE, pp. 311-316, 2012.

[68] Nguyen Thi Lan Huong, Nguyen Long Giang, “Incremental algorithms based

on metric for finding reduct in dynamic decision tables”, Journal on Research

and Development on Information & Communications Technology, Vol.E-3,

No.9 (13), pp. 26-39, 2016.

[69] Nguyen Long Giang, Nguyen Thi Lan Huong, Metric Based Attribute

119

Reduction in Incomplete Information Systems, Kỷ yếu Hội thảo Quốc gia lần

thứ XV “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Hà

Nội 11/2012, 2013, Tr. 185-190.

[70] Vũ Văn Định, Vũ Đức Thi, Ngô Quốc Tạo, Nguyễn Long Giang, Phương pháp

rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách

phân hoạch, Các công trình nghiên cứu, phát triển và ứng dụng CNTT&TT,

Tạp chí CNTT&TT, Tập V-2, số 14(34), 12-2015, Trang 23-32.

[71] Demetrovics Janos, Vu Duc Thi, Nguyen Long Giang, “A Distance-based

Method for Attribute Reduction in Incomplete Decision Systems”, Serdica

Journal of Computing 7, No 4, pp. 355-374, 2013.

[72] Long Giang Nguyen, Hung Son Nguyen, “Metric Based Attribute Reduction in

Incomplete Decision Tables”, Proceedings of 14th International Conference,

Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC

2013, Halifax, NS, Canada, Lecture Notes in Computer Science, SpingerLink,

Vol. 8170, pp. 99-110, 2013.

[73] Nguyễn Long Giang, Cao Chính Nghĩa, Nguyễn Quang Huy, Nguyễn Thị Lan

Hương, Nguyễn Ngọc Cương, Trần Anh Tú, Về một độ đo khoảng cách mờ và

ứng dụng rút gọn thuộc tính trong bảng quyết định, Kỷ yếu Hội thảo Quốc gia

lần thứ XX - Một số vấn đề chọn lọc của CNTT và TT, Quy Nhơn, 23-

24/11/2017, Tr. 404-409.

[74] Cao Chinh Nghia, Vu Duc Thi, Nguyen Long Giang, Tan Hanh, “Fuzzy distance

based attribute reduction in decision tables”, Journal on Information

Communications Technology, Research and Development on Information &

Communications Technology, Vietnam, Vol. V-2, No. 16 (36), pp. 104-111, 2016.

[75] Qian, Y., Li, Y., Liang, J., Lin, G., and Dang, C. (2015), Fuzzy granular

structure distance, IEEE Transactions on Fuzzy Systems, 23(6), pp. 2245-2259.

[76] Nguyễn Long Giang (2012), Nghiên cứu một số phương pháp khai phá dữ liệu

theo tiếp cận lý thuyết tập thô, Luận án Tiến sĩ Toán học, Viện Công nghệ

thông tin.

[77]

120

Qian, Y., Wang, Q., Cheng, H., Liang, J., and Dang, C. (2015), Fuzzy-rough

feature selection accelerator, Fuzzy Sets and Systems, 258, pp. 61-78.

[78] J.H. Dai, Q. Xu, “Attribute selection based on information gain ratio in fuzzy

rough set theory with application to tumor classification”, Applied Soft

Computing 13, pp. 211-221, 2013.

[79] Q.H. Hu, D.R. Yu, Z.X. Xie, J. F. Liu, “Fuzzy probabilistic approximation

spaces and their information measures”, IEEE Transaction on Fuzzy Systems,

vol. 14, no. 2, pp. 191-201, 2006.

[80] Pradipta Maji, Partha Garai, “On fuzzy-rough attribute selection: Criteria of

Max-Dependency, Max-Relevance, Min-Redundancy, and Max-Significance”,

Applied Soft Computing 13, pp. 3968-3980, 2013.

[81] Q. Shen, R. Jensen, “Selecting informative features with fuzzy-rough sets and

its application for complex systems monitoring”, Pattern Recognition 37, pp.

1351 – 1363, 2004.

[82] Nguyễn Thị Lan Hương, “Rút gọn thuộc tính trong bảng quyết định động theo

tiếp cận tập thô”, Luận án Tiến sĩ Toán học, Viện Công nghệ thông tin, 2017.

[83] Vũ Văn Định, “Rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp

cận tập thô dung sai”, Luận án Tiến sĩ Toán học, Viện Công nghệ thông tin, 2016.

[84] A.P. Zeng , T.R. Li, J. Hu, H.M. Chen, Chuan Luo, “Dynamical updating fuzzy

rough approximations for hybrid data under the variation of attribute values”,

Information Sciences 000, pp. 1-26, 2016.

[85] Nguyễn Văn Thiện, “Một số phương pháp kết hợp trong rút gọn thuộc tính theo

tiếp cận tập thô mờ”, Luận án Tiến sĩ Máy tính, Học viện Khoa học và Công

nghệ, 2018

[86] C. Luo, T. R. Li and H. M. Chen, “Dynamic maintenance of approximations in

setvalued ordered decision systems under the attribute generalization”,

Information Sciences 257, pp. 210 - 228, 2014.

[87] C. Luo, T.R. Li, H.M. Chen, H. Fujita, Z. Yi, “Efficient updating of

probabilistic approximations with incremental objects”, Knowledge-Based

Systems 109, pp. 71-83, 2017.

[88] C. Luo, T.R. Li, Y. Yao, “Dynamic probabilistic rough sets with incomplete

121

data”, Information Sciences 417, pp. 39–54, 2017.

[89] C. Luo, T.R. Li, Y.Y. Huang, H. Fujita, “Updating three-way decisions in

incomplete multi-scale information systems”, Information Sciences 476, pp.

274-289, 2019.

[90] C.X. Hu, S.X. Liu, G.X. Liu, “Matrix-based approaches for dynamic updating

approximations in multigranulation rough sets”, Knowl Based Syst 122, pp. 51-

63, 2017.

[91] C.Z. Wang, Y. Qi, Q. He, Attribute reduction using distance-based fuzzy rough

sets, 2015 International Conference on Machine Learning and Cybernetics ,

IEEE, 2015.

[92] C.Z. Wang, Y.Huang, M.W. Shao, X.D.Fan, Fuzzy rough set-based attribute

reduction using distance measures, Knowledge-Based Systems, Volume 164, 15

January 2019, pp. 205-212.

[93] D.G. Chen, Y. Yang, Z. Dong, “An incremental algorithm for attribute

reduction with variable precision rough sets”, Appl. Soft Comput., vol. 45, pp.

129-149, 2016.

[94] DF.M. Ma, J.W. Chen, W. Han, “A Positive Region Based Incremental

Attribute Reduction Algorithm for Incomplete System”, International

Conference on Electronic Information Technology and Intellectualization

(ICEITI 2016), pp. 153-158, 2016.

[95] F.M. Ma, T.F. Zhang, “Generalized binary discernibility matrix

for attribute reduction in incomplete information systems”, The Journal of

China Universities of Posts and Telecommunications, Volume 24, Issue 4, pp.

57-75, 2017.

[96] G.M. Lang, Q. Li, M.J. Cai, T. Yang, Q.M. Xiao, Incremental approaches to

knowledge reduction based on characteristic matrices, Int. J. Mach. Learn.

Cybern. 8 (1) pp. 203-222, 2017.

[97] G.M. Lang, D.Q. Miao , M.J. Cai, Z.F. Zhang, “ Incremental approaches for

updating reducts in dynamic covering information systems, Knowledge Based

Systems 134, pp. 85..104, 2017.

[98] G. Q. Wang, “ Valid Incremental Attribute Reduction Algorithm Based on

122

Attribute Generalization for an Incomplete Information System”, Chinese

Journal of Electronics, Vol.28, No.4, 2019.

[99] Huyen Tran, Thinh Cao, Koichi Yamada, Do Van Nguyen, “Incremental

Updating Methods with Three-way Decision Models in Incomplete Information

Systems”, IEEE Joint 10th International Conference on Soft Computing and

Intelligent Systems, pp. 27-32, 2018.

[100] J. Hu, K. Wang, H. Yu, “Attribute Reduction on Distributed Incomplete

Decision Information System”, IJCRS 2017, pp 289-305, 2017.

[101] J. Qian, C.Y. Dang, X.D. Yue, N. Zhang, “Attribute reduction for sequential

three-way decisions under dynamic granulation”, International Journal of

Approximate Reasoning 85(2017) 196-216.

[102] J. Yu, L. Sang, H. Dong, “Based on Attribute Order for Dynamic Attribute

Reduction in the Incomplete Information System”, IEEE IMCEC 2018, pp.

2475-2478, 2018.

[103] L.N. Wang , X. Yang , Y. Chen , L. Liu , S.Y. An , P. Zhuo , “ Dynamic

composite decision-theoretic rough set under the change of attributes”, Int. J.

Comput. Intell.Syst. 11 (2018) 355–370 .

[104] Long Giang Nguyen, Thien Nguyen, Nhu Son Nguyen , “Fuzzy Partition

Distance based Attribute Reduction in Decision Tables”, IJCRS 2018:

International Joint Conference on Rough Sets 2018, LNCS, Vol. 11103,

Springer Link, 2018, pp. 614-627.

[105] M. Kryszkiewicz (1998), “Rough set approach to incomplete information

systems”, Information Science, Vol. 112, pp. 39-49.

[106] Nguyen Long Giang, Vu Van Dinh, Relationships Among the Concepts of

Reduct in Incomplete Decision Tables, Frontiers in Artificial Intelligence and

Applications (FAIA), Volume 252: Advanced Methods and Technologies for

Agent and Multi-Agent Systems, IOS Press, 2013, pp. 417-426.

[107] S. Li, T. Li, “Incremental update of approximations in dominance-based rough

123

sets approach under the variation of attribute values”, Inf. Sci. 294, pp.348-361,

2015

[108] S. Wang , T. Li , C. Luo , H. Fujita , Efficient updating rough approximations

with multi-dimensional variation of ordered data, Inf. Sci. 372, pp. 690-708,

2016.

[109] Y.Y. Huang , T.R. Li , C. Luo , H. Fujita , S.J. Horng , Matrix-based dynamic

updating rough fuzzy approximations for data mining, Knowl. Based Syst. 119,

pp. 273-283, 2017.

[110] W.B. Qian, W.H. Shu, “Mutual information criterion for feature selection

from incomplete data”, Neurocomputing, Volume 168, pp. 210-220, 2015.