Luận án Tiến sĩ Toán học: Phát triển một số phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận Filter-Wrapper

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

NGUYỄN BÁ QUẢNG

PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN FILTER-WRAPPER

LUẬN ÁN TIẾN SĨ TOÁN HỌC

Hà Nội - 2021

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

NGUYỄN BÁ QUẢNG

PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN FILTER-WRAPPER

Chuyên ngành: Cơ sở toán học cho tin học 9 46 01 10 Mã số:

LUẬN ÁN TIẾN SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. PGS. TS. NGUYỄN LONG GIANG

2. TS. NGÔ TRỌNG MẠI

Hà Nội - 2021

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các số liệu,

kết quả nghiên cứu trong luận án này là hoàn toàn trung thực và chưa từng

được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo được

trích dẫn đầy đủ.

Tác giả luận án

Nguyễn Bá Quảng

LỜI CÁM ƠN

Tôi xin chân thành cám ơn Thủ trưởng Viện Khoa học và Công nghệ

quân sự, Phòng Đào tạo, Viện Công nghệ thông tin và các đồng nghiệp đã

luôn động viên, quan tâm, tạo điều kiện thuận lợi và giúp đỡ tôi trong quá

trình học tập và nghiên cứu của mình.

Tôi xin bày tỏ sự biết ơn chân thành và sâu sắc đến PGS. TS Nguyễn

Long Giang, TS Ngô Trọng Mại đã tận tình chỉ bảo, hướng dẫn tôi trong suốt

quá trình nghiên cứu và hoàn thành bản luận án này.

Tôi xin chân thành cám ơn các nhà khoa học của Viện Khoa học và

Công nghệ quân sự, các nhà khoa học Viện Hàn lâm Khoa học và Công nghệ

Việt Nam, các nhà khoa học trong và ngoài quân đội đã giúp đỡ tôi hoàn

thành luận án.

Xin chân thành cám ơn gia đình và bạn bè đã luôn chia sẻ, động viên và

giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu.

iii

MỤC LỤC

Trang

LỜI CAM ĐOAN ................................................................................................................................................. i

LỜI CÁM ƠN ....................................................................................................................................................... ii

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .......................................................................... v

DANH MỤC CÁC BẢNG ............................................................................................................................. vi

DANH MỤC CÁC HÌNH VẼ....................................................................................................................... vii

MỞ ĐẦU ............................................................................................................................................................... 1

CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ

DUNG SAI............................................................................................................................... 10

1.1. Hệ thông tin và mô hình tập thô truyền thống ............................................................ 10 1.1.1. Hệ thông tin ........................................................................................... 10 1.1.2. Mô hình tập thô truyền thống ................................................................ 11 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai ........................................... 12 1.2.1. Hệ thông tin không đầy đủ .................................................................... 12 1.2.2. Mô hình tập thô dung sai ....................................................................... 12 1.2.3. Bảng quyết định không đầy đủ .............................................................. 14 1.2.4. Ma trận dung sai .................................................................................... 16 1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai ............................... 18 1.3.1. Tổng quan về rút gọn thuộc tính ............................................................ 18 1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính .................................. 19 1.3.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai ................................. 21 1.4. Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô dung sai .... 24 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai ................................. 24 1.4.2. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai ..................................................... 27 1.5. Kết luận chương 1 ......................................................................................................... 36 CHƯƠNG 2. THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ ................................................ 37 2.1. Xây dựng độ đo khoảng cách trong bảng quyết định không đầy đủ ....................... 38 2.1.1. Xây dựng độ đo khoảng cách giữa hai tập hợp ..................................... 39 2.1.2. Xây dựng độ đo khoảng cách giữa hai tập thuộc tính ........................... 40

2.2. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách ..... 42

2.2.1. Xây dựng thuật toán filter tìm tập rút gọn của bảng quyết định không đầy đủ ......................................................................................... 43 2.2.2. Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ ......................................................................................... 46 2.2.3. Thực nghiệm và đánh giá kết quả ............................................................ 49 2.3. Kết luận chương 2 ......................................................................................................... 54 CHƯƠNG 3. CÁC THUẬT TOÁN GIA TĂNG FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH THAY ĐỔI ....................................... 55 3.1. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập đối tượng ....................................................................................................................... 58 3.1.1. Công thức cập nhật khoảng cách khi bổ sung tập đối tượng ................. 58 3.1.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập đối tượng ............................................................................................... 62 3.1.3. Công thức cập nhật khoảng cách khi loại bỏ tập đối tượng .................. 67 3.1.4. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập đối tượng ......................................................................................... 70 3.1.5. Thực nghiệm và đánh giá các thuật toán ............................................... 74

3.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập thuộc tính ....................................................................................................................... 92 3.2.1. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính ................ 92 3.2.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính .............................................................................................. 93 3.2.3. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính .................. 97 3.2.4. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập thuộc tính ........................................................................................ 98 3.2.5. Thực nghiệm và đánh giá các thuật toán ............................................. 101 3.3. Kết luận chương 3 ....................................................................................................... 106 KẾT LUẬN ....................................................................................................................................................... 108 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ................................................ 110 TÀI LIỆU THAM KHẢO ............................................................................................................................ 111

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Số thuộc tính điều kiện trong bảng quyết định

Bảng quyết định không đầy đủ

Hệ thông tin không đầy đủ

Tập xấp xỉ dưới của

đối với P

Tập xấp xỉ trên của Miền dương của P đối với d

Quan hệ dung sai trên tập thuộc tính P

Lớp dung sai chứa

của phủ

Lực lượng lớp dung sai

Số đối tượng

Giá trị của đối tượng

tại thuộc tính

Phủ của U trên P

IDS_F_DAR

IDS_IFW_AA

IDS_IFW_AO

IDS_IFW_DA

IDS_IFW_DO

IDS_FW_DAR

Filter Distance based Attribute Reduction in Incomplete Decision Tables Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Add Attributes. Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Add Objects. Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Delete Attributes. Incremental Filter-Wrapper Algorithm for Distance based Attribute Reduction in Incomplete Decision Tables when Delete Objects. Filter-Wrapper Distance based Attribute Reduction in Incomplete Decision Tables

DANH MỤC CÁC BẢNG

Trang

Bảng 1.2. Các thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ

theo tiếp cận tập thô dung sai .................................................................. 24

Bảng 1.3. Các thuật toán gia tăng tính toán các tập xấp xỉ và tìm tập rút gọn

theo tiếp cận tập thô truyền thống và các mô hình mở rộng. ................... 28

Bảng 1.4. Các thuật toán gia tăng tính toán các tập xấp xỉ và tìm tập rút gọn

theo tiếp cận tập thô dung sai .................................................................. 33

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

Bảng 2.2. Bộ dữ liệu thực nghiệm thuật toán IDS_FW_DAR ................................. 50

Bảng 2.3. Thời gian thực hiện ba thuật toán (tính bằng giây) .................................. 51

Bảng 2.4. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của ba

thuật toán .................................................................................................. 52

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

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

Bảng 3.3. Bộ dữ liệu thử nghiệm thuật toán IDS_IFW_AO ..................................... 75

Bảng 3.4. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR (s) . 77

Bảng 3.5. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của thuật

toán IDS_IFW_AO và IDS_FW_DAR ................................................... 80

Bảng 3.6. Số lượng thuộc tính tập rút gọn và độ chính xác của thuật toán

IDS_IFW_AO và IARM-I ....................................................................... 82

Bảng 3.7. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I (s) .......... 86

Bảng 3.8. Thời gian thực hiện của 03 thuật toán (s) ................................................. 89

Bảng 3.9. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của 03 thuật toán . 90

Bảng 3.10. Bộ dữ liệu thực nghiệm của thuật toán IDS_IFW_AA ........................ 102

Bảng 3.11. Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của thuật

toán IDS_IFW_AA và UARA ............................................................ 103

Bảng 3.12. Thời gian thực hiện của thuật toán IDS_IFW_AA và UARA (s) ........ 105

Bảng 1.1. Bảng quyết định không đầy đủ về các xe hơi ........................................... 16

vii

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Quy trình rút gọn thuộc tính ..................................................................... 20

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

Hình 1.3. Mô hình phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai . 22

Hình 2.1. Thời gian thực hiện ba thuật toán (tính bằng giây) ................................... 51

Hình 2.2. Số lượng thuộc tính tập rút gọn của ba thuật toán .................................... 53

Hình 2.3. Độ chính xác phân lớp của ba thuật toán .................................................. 54

Hình 3.1. Thời gian thực hiện của thuật toán IDS_IFW_AO và IDS_FW_DAR .... 79

Hình 3.2. Độ chính xác phân lớp của IDS_IFW_AO và IDS_FW_DAR ................ 81

Hình 3.3.a. Bộ số liệu Audiology .............................................................................. 84

Hình 3.3.b. Bộ số liệu Soybean-large ....................................................................... 84

Hình 3.3.c. Bộ số liệu Congressional Voting Records.............................................. 84

Hình 3.3.d. Bộ số liệu Arrhythmia ............................................................................ 85

Hình 3.3.e. Bộ số liệu Anneal ................................................................................... 85

Hình 3.3.f. Bộ số liệu Advertisements ...................................................................... 85

Hình 3.3. Số lượng thuộc tính tập rút gọn và độ chính xác của thuật toán

IDS_IFW_AO và IARM-I ........................................................................ 85

Hình 3.4. Thời gian thực hiện của thuật toán IDS_IFW_AO và IARM-I ................ 88

Hình 3.5. Thời gian thực hiện của 03 thuật toán (s) ................................................. 89

Hình 3.6. Độ chính xác phân lớp của 03 thuật toán .................................................. 91

Hình 3.7. Số thuộc tính tập rút gọn của 03 thuật toán............................................... 91

Trang

MỞ ĐẦU

1. Tính cấp thiết của đề tài luận án

Trong bối cảnh ngày nay, sự tăng trưởng không ngừng của dung lượng

dữ liệu và số lượng các thuộc tính đã gây khó khăn, thách thức cho việc thực

thi các thuật toán khai phá dữ liệu, phát hiện tri thức. Rút gọn thuộc tính (còn

gọi là rút gọn chiều, hay rút gọn đặc trưng) là bài toán quan trọng trong bước

tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không cần

thiết nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu. Hiện nay có

hai cách tiếp cận chính đối với bài toán rút gọn thuộc tính [39-40]: filter (lọc)

và wrapper (đóng gói). Cách tiếp cận filter thực hiện việc rút gọn thuộc tính

độc lập với thuật khai phá dữ liệu sử dụng sau này. Các thuộc tính được chọn

chỉ dựa trên độ quan trọng của chúng trong việc phân lớp dữ liệu. Trong khi

đó, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách áp dụng ngay

thuật khai phá, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn

các tập con thuộc tính.

Lý thuyết tập thô (Rough set) do Pawlak đề xuất [113] được xem là công

cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trong bảng quyết định đầy

đủ, đã và đang được cộng đồng nghiên cứu về tập thô thực hiện lâu nay.

Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị trên miền

giá trị thuộc tính, gọi là bảng quyết định không đầy đủ. Ví dụ với bảng quyết

định chẩn đoán bệnh viêm gan với các thuộc tính là các triệu chứng, các bác

sĩ không thể thu thập đầy đủ các triệu chứng của tất cả các bệnh nhân để ra

quyết định. Để giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết

định không đầy đủ mà không qua bước tiền xử lý giá trị thiếu, Kryszkiewicz

[67] mở rộng quan hệ tương đương trong lý thuyết tập thô truyền thống thành

quan hệ dung sai và xây dựng mô hình tập thô dung sai (tolerance rough set).

Các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo

tiếp cận mô hình tập thô dung sai là các nghiên cứu mở rộng của các phương

pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống. Đây là các phương

pháp heuristic bao gồm các bước: xây dựng độ đo, định nghĩa tập rút gọn và

độ quan trọng của thuộc tính sử dụng độ đo được xây dựng, trên cơ sở đó xây

dựng thuật toán heuristic tìm tập rút gọn theo tiêu chuẩn là độ quan trọng của

thuộc tính. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết

định không đầy đủ theo tiếp cận tập thô dung sai tập trung vào các phương

pháp chính như: các phương pháp sử dụng miền dương mở rộng [25], [51],

[99], [114], [117], các phương pháp sử dụng ma trận phân biệt, hàm phân biệt

mở rộng [29], [45], [47], [57], [77], [80], [116], các phương pháp sử dụng

entropy thông tin mở rộng [26], [48-50], [64], [79], [107], các phương pháp

sử dụng độ đo lượng thông tin [72], [91], [94], phương pháp sử dụng khoảng

cách [62], [78] và một số phương pháp sử dụng các độ đo khác như quan hệ

không phân biệt mở rộng [85], độ bao phủ của thuộc tính [93]. Nhìn chung,

các phương pháp rút gọn thuộc tính theo tiếp cận tập thô và tập thô dung sai

đều hướng tới mục tiêu là tìm được tập rút gọn hiệu quả nhất để thực thi mô

hình phân lớp dựa trên các tiêu chí: giảm thiểu số thuộc tính tập rút gọn để

giảm thiểu độ phức tạp và nâng cao độ chính xác của mô hình. Các thuật toán

đã đề xuất trong các phương pháp nêu trên đều là các thuật toán heuristic theo

tiếp cận filter truyền thống, nghĩa là tập rút gọn thu được là tập thuộc tính tối

thiểu bảo toàn độ đo được định nghĩa. Việc đánh giá độ chính xác của mô

hình phân lớp được thực hiện sau khi tìm được tập rút gọn. Do đó, tập rút gọn

của các thuật toán filter nêu trên chưa tối ưu về số lượng thuộc tính và độ

chính xác phân lớp.

Tại Việt Nam, đã có một số luận án tiến sĩ giải quyết bài toán rút gọn

thuộc tính trong bảng quyết định theo tiếp cận mô hình tập thô truyền thống

và các mô hình tập thô mở rộng của nhóm nghiên cứu của thầy hướng dẫn. Cụ

thể, luận án tiến sĩ [2] đề xuất các thuật toán gia tăng tìm tập rút gọn của bảng

quyết định đầy đủ theo tiếp cận filter truyền thống. Luận án tiến sĩ [1] đề xuất

các thuật toán rút gọn thuộc tính trong bảng quyết định không đầy đủ cố định.

Trong luận án tiến sĩ [3], các tác giả đề xuất hướng tiếp cận kết hợp filter-

wrapper tìm tập rút gọn của bảng quyết định đầy đủ dựa trên lý thuyết tập thô

mờ (fuzzy rough set). Trong đó, giai đoạn filter tìm các ứng viên cho tập rút

gọn dựa vào độ đo (còn gọi là tập rút gọn xấp xỉ), giai đoạn wrapper tính toán

độ chính xác phân lớp của các ứng viên và lựa chọn tập rút gọn xấp xỉ có độ

chính xác phân lớp cao nhất. Kết quả thử nghiệm cho thấy, số lượng thuộc

tính tập rút gọn giảm thiểu đáng kể so với các phương pháp filter, trong khi

độ chính xác phân lớp vẫn được bảo toàn và cải thiện hơn. Tuy nhiên, các

phương pháp trong luận án [3] đều thực hiện trên bảng quyết định đầy đủ theo

tiếp cận tập thô mờ (fuzzy rough set). Do đó, mục tiêu nghiên cứu thứ nhất

của luận án là nghiên cứu hướng tiếp cận kết hợp filter-wrapper tìm tập rút

gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai nhằm

giảm thiểu số lượng thuộc tính tập rút gọn, trong khi cố gắng bảo toàn, cải

thiện độ chính xác mô hình phân lớp.

Ngày nay, trong xu thế phát triển của dữ liệu lớn (Big data), các bảng

quyết định ngày càng có kích thước lớn và luôn thay đổi, cập nhật. Việc áp

dụng các thuật toán tìm tập rút gọn theo phương pháp truyền thống gặp nhiều

thách thức. Với trường hợp bảng quyết định có kích thước lớn, việc thực hiện

các thuật toán tìm tập rút gọn gặp khó khăn do hạn chế về không gian lưu trữ

và tốc độ tính toán. Với trường hợp bảng quyết định thay đổi, cập nhật, các

thuật toán này phải tính toán lại tập rút gọn trên toàn bộ bảng quyết định sau

khi thay đổi, do đó chi phí về thời gian tính toán tăng lên đáng kể. Để vượt

qua các thách thức trên, các nhà nghiên cứu đề xuất hướng tiếp cận tính toán

gia tăng tìm tập rút gọn. Phương pháp gia tăng tìm tập rút gọn là kỹ thuật chỉ

tính toán sự thay đổi của tập rút gọn trên phần dữ liệu bổ sung (hoặc loại bỏ)

chứ không tính lại tập rút gọn trên toàn bộ tập dữ liệu ban đầu. Do các thuật

toán gia tăng chỉ cập nhật lại tập rút gọn trên phần dữ liệu bị thay đổi nên

chúng giảm thiểu đáng kể thời gian thực hiện khi thực thi trên các bảng dữ

liệu thay đổi, biến động. Hơn nữa, các thuật toán gia tăng có thể thực hiện

được trên các bảng quyết định kích thước lớn bằng giải pháp chia nhỏ bảng

quyết định thành nhiều phần, sau đó tập rút gọn được tính khi lần lượt bổ

sung từng phần vào bảng quyết định.

Hướng tiếp cận tính toán gia tăng tìm tập rút gọn đã và đang thu hút sự

quan tâm của các nhà nghiên cứu trong suốt hơn hai thập kỷ qua. Theo tiếp

cận tập thô truyền thống và các mô hình mở rộng, các nghiên cứu liên quan

đến thuật toán gia tăng tìm tập rút gọn và tính toán các tập xấp xỉ của bảng

quyết định thay đổi khá sôi động và phong phú. Các nghiên cứu liên quan đến

các thuật toán gia tăng tìm tập rút gọn và tập trung vào các trường hợp: bổ

sung và loại bỏ tập đối tượng [14], [20-21], [30], [33], [35], [37], [52], [55],

[59], [70], [87], [89], [95-96], [100], [102], [106], [108], [110-112], bổ sung

và loại bỏ tập thuộc tính [6], [19], [32], [53], [58], [60], [68], [76], [101],

[104], tập đối tượng thay đổi giá trị [10], [66], [88], [90], [103], tập thuộc tính

thay đổi giá trị [22], [31], [34], [36], [65]. Ngoài ra, một số công bố đề xuất

các thuật toán gia tăng tính toán các tập xấp xỉ trong các trường hợp: bổ sung

và loại bỏ tập đối tượng [12], [15], [43], [97], [105], [109], bổ sung và loại bỏ

tập thuộc tính [7], [24], [73], [75], tập đối tượng thay đổi giá trị [44], tập

thuộc tính thay đổi giá trị [11], [41], [74]. Theo tiếp cận tập thô dung sai,

trong mấy năm gần đây các nghiên cứu liên quan đến thuật toán gia tăng tính

toán các tập xấp xỉ và tìm tập rút gọn của bảng quyết định không đầy đủ khá

sôi động và phong phú. Giống như tiếp cận tập thô truyền thống và các mô

hình mở rộng được trình bày ở trên, các nghiên cứu liên quan chủ yếu tập

trung vào trường hợp bổ sung, loại bỏ tập đối tượng [9], [13], [18], [23], [28],

[38], [42], [46], [56], [71], [81-82], [86]. Ngoài ra, công bố [83] giải quyết bài

toán trong trường hợp bổ sung, loại bỏ tập thuộc tính; công bố [84] giải quyết

bài toán trong trường hợp tập đối tượng thay đổi giá trị; công bố [92] giải

quyết bài toán trong trường hợp tập thuộc tính thay đổi giá trị.

Giống như các thuật toán tìm tập rút gọn trong bảng quyết định không

đầy đủ đã trình bày ở trên, các thuật toán gia tăng tìm tập rút gọn trong các

phương pháp nêu trên đều theo hướng tiếp cận filter truyền thống. Do đó, tập

rút gọn tìm được chưa tối ưu cả về số lượng thuộc tính và độ chính xác phân

lớp. Gần đây, các tác giả trong công trình [4] đề xuất thuật toán gia tăng tìm

tập rút gọn theo tiếp cận kết hợp filter-wrapper. Tuy nhiên, thuật toán gia tăng

trong [4] chỉ tìm tập rút gọn của bảng quyết định đầy đủ theo tiếp cận tập thô

mờ trong trường hợp bổ sung tập đối tượng. Vì vậy, mục tiêu nghiên cứu thứ

hai của luận án là nghiên cứu các thuật toán gia tăng tìm tập rút gọn của bảng

quyết định không đầy đủ theo tiếp cận kết hợp filter-wrapper nhằm giảm thiểu

số lượng thuộc tính tập rút gọn và cải thiện độ chính xác phân lớp so với các

thuật toán đã công bố.

2. Mục tiêu nghiên cứu

Trên cơ sở phân tích các vấn đề còn tồn tại của các nghiên cứu liên quan,

mục tiêu của luận án là:

1) Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định

không đầy đủ theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc

tính tập rút gọn (từ đó giảm thiểu độ phức tạp của mô hình) và cải thiện độ

chính xác của mô hình phân lớp.

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

bảng quyết định không đầy đủ thay đổi theo tiếp cận tập thô dung sai nhằm

giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác của mô

hình phân lớp so với các thuật toán gia tăng khác.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của luận án là bảng quyết định không đầy đủ, mô

hình tập thô dung sai, các phương pháp rút gọn thuộc tính theo tiếp cận tập

thô dung sai và các phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập

thô dung sai.

Phạm vi nghiên cứu của luận án là các phương pháp rút gọn thuộc tính

trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai.

4. Phương pháp nghiên cứu

Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên

cứu thực nghiệm.

1) Nghiên cứu lý thuyết: Nghiên cứu các thuật toán rút gọn thuộc tính

theo tiếp cận tập thô dung sai đã công bố, bao gồm các thuật toán trên bảng

quyết định không thay đổi và các thuật toán gia tăng trên bảng quyết định

thay đổi. Phân tích ưu điểm, nhược điểm và các vấn đề còn tồn tại của các

thuật toán đã có. Trên cơ sở đó, đề xuất các độ đo cải tiến và các thuật toán

theo hướng tiếp cận kết hợp filter-wrapper. Các đề xuất, cải tiến được chứng

minh chặt chẽ về lý thuyết bởi các định lý, mệnh đề.

2) Nghiên cứu thực nghiệm: Các thuật toán đề xuất được cài đặt, chạy

thử nghiệm, so sánh, đánh giá với các thuật toán khác trên các bộ số liệu mẫu

từ kho dữ liệu UCI nhằm minh chứng về tính hiệu quả của các nghiên cứu về

lý thuyết.

5. Nội dung nghiên cứu

1) Nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết

định không đầy đủ dựa trên mô hình tập thô dung sai theo tiếp cận kết hợp

filter-wrapper.

2) Nghiên cứu các phương pháp gia tăng rút gọn thuộc tính trong bảng

quyết định không đầy đủ thay đổi theo tiếp cận kết hợp filter-wrapper. Bảng

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

thuộc tính.

3) Cài đặt, thử nghiệm, so sánh, đánh giá các thuật toán đề xuất với các

thuật toán khác đã công bố trên các bộ dữ liệu thử nghiệm từ kho dữ liệu UCI

[118].

6. Ý nghĩa khoa học và thực tiễn

Ý nghĩa khoa học:

Đề xuất các thuật toán mới tìm tập rút gọn của bảng quyết định không

đầy đủ theo tiếp cận kết hợp filter-wrapper trong trường hợp bảng quyết định

cố định và bảng quyết định thay đổi. Cụ thể luận án có các kết quả chính như

1) Xây dựng một độ đo khoảng cách mới và đề xuất thuật toán theo tiếp

cận kết hợp filter-wrapper IDS_FW_DAR tìm tập rút gọn của bảng quyết định

không đầy đủ sử dụng độ đo khoảng cách. Kết quả thử nghiệm trên các bộ số

liệu mẫu từ kho dữ liệu UCI (UC Irvine Machine Learning Repository) [118]

cho thấy, thuật thoán filter-wrapper IDS_FW_DAR giảm thiểu đáng kể số

lượng thuộc tính tập rút gọn và cải thiện độ chính xác mô hình phân lớp so với

các thuật toán filter khác.

2) Xây dựng các công thức gia tăng tính khoảng cách và đề xuất 04

thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định không

đầy đủ:

(1) Thuật toán gia tăng filter-wrapper IDS_IFW_AO tìm tập rút gọn

trong trường hợp bổ sung tập đối tượng;

(2) Thuật toán filter-wrapper IDS_IFW_DO tìm tập rút gọn trong trường

hợp loại bỏ tập đối tượng;

(3) Thuật toán gia tăng filter-wrapper IDS_IFW_AA tìm tập rút gọn

trong trường hợp bổ sung tập thuộc tính.

(4) Thuật toán gia tăng filter-wrapper IDS_IFW_DA tìm tập rút gọn

trong trường hợp loại bỏ tập thuộc tính.

Kết quả thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI [118] cho

thấy, các thuật toán gia tăng filter-wrapper IDS_IFW_AO và IDS_IFW_AA

giảm thiểu đáng kể số lượng thuộc tính tập rút gọn và cải thiện độ chính xác

mô hình phân lớp so với các thuật toán gia tăng filter khác.

Ý nghĩa thực tiễn

Các thuật toán đề xuất có thể áp dụng để giải quyết bài toán rút gọn

thuộc tính trong các ứng dụng thực tiễn nhằm loại bỏ các thuộc tính dư thừa,

nâng cao hiệu quả các mô hình khai phá dữ liệu và học máy, đặc biệt là các hệ

thống cơ sở dữ liệu không đầy đủ, thiếu giá trị trong các lĩnh vực chẩn đoán y

tế, tài chính ngân hàng.

7. Bố cục của luận án

Bố cục của luận án gồm phần mở đầu và ba chương nội dung, phần kết

luận và danh mục các tài liệu tham khảo. Chương 1 trình bày các khái niệm cơ

bản về lý thuyết tập thô truyền thống, mô hình tập thô dung sai và tổng quan về

tiếp cận filter-wrapper trong rút gọn thuộc tính. Chương 1 cũng trình bày các

nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô dung sai, các

nghiên cứu liên quan đến phương pháp gia tăng rút gọn thuộc tính theo tiếp cận

tập thô dung sai trong mấy năm gần đây. Trên cơ sở đó, luận án phân tích các

vấn đề còn tồn tại và nêu rõ các mục tiêu nghiên cứu cùng với tóm tắt các kết

quả đạt được.

Các đóng góp chính của luận án được trình bày trong chương 2, chương

3. Chương 2 trình bày kết quả nghiên cứu về xây dựng độ đo khoảng cách mới.

Sử dụng độ đo khoảng cách mới, chương 2 đề xuất thuật toán IDS_F_DAR tìm

tập rút gọn theo tiếp cận filter và thuật toán IDS_FW_DAR tìm tập rút gọn

theo tiếp cận kết hợp filter-wrapper. Các thuật toán trên thực hiện trên bảng

quyết định không đầy đủ cố định.

Chương 3 xây dựng các công thức gia tăng tính độ đo khoảng cách và đề

xuất bốn thuật toán gia tăng filter-wrapper tìm tập rút gọn trong bảng quyết

định thay đổi, cụ thể là:

1) Thuật toán IDS_IFW_AO tìm tập rút gọn trong trường hợp bổ sung

tập đối tượng;

2) Thuật toán IDS_IFW_DO tìm tập rút gọn trong trường hợp loại bỏ tập

đối tượng;

3) Thuật toán IDS_IFW_AA tìm tập rút gọn trong trường hợp bổ sung

tập thuộc tính;

4) Thuật toán IDS_IFW_DA tìm tập rút gọn trong trường hợp loại bỏ tập

thuộc tính.

Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát

triển và những vấn đề quan tâm của tác giả.

CHƯƠNG 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH

THEO TIẾP CẬN TẬP THÔ DUNG SAI

1.1. Hệ thông tin và mô hình tập thô truyền thống

Lý thuyết tập thô truyền thống do Z.Pawlak [113] đề xuất là công cụ

toán học hiệu quả để biểu diễn và xử lý các khái niệm không chắc chắn.

Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ tương

đương (hay quan hệ không phân biệt được) để xấp xỉ tập hợp. Khi đó, mọi tập

đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó.

Mỗi tập xấp xỉ được hợp thành bởi một hoặc nhiều lớp tương đương, là cơ sở

để xây dựng các thuật toán rút gọn thuộc tính và khai phá tri thức từ dữ liệu.

Trong phần này, luận án trình bày một số khái niệm cơ bản trong lý thuyết tập

thô truyền thống của Z.Pawlak [113], là cơ sở nền tảng cho mô hình tập thô

dung sai được trình bày ở phần 1.2.

1.1.1. Hệ thông tin

Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu

gồm n cột ứng với n thuộc tính và m hàng ứng với m đối tượng. Một cách

hình thức, hệ thông tin là một cặp trong đó U là tập hữu hạn, khác

rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính. Mỗi thuộc tính

xác định một ánh xạ: với Va là tập giá trị của thuộc tính

Xét hệ thông tin . Mỗi tập con các thuộc tính xác định

một quan hệ hai ngôi trên U, ký hiệu là , xác định bởi

là quan hệ P-không phân biệt được. Dễ thấy rằng là một

quan hệ tương đương trên U. Nếu thì hai đối tượng u và v

không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương

xác định một phân hoạch trên U, ký hiệu là hay . Ký

hiệu lớp tương đương trong phân hoạch chứa đối tượng u là , khi đó

1.1.2. Mô hình tập thô truyền thống

Cho hệ thông tin và tập đối tượng . Với một tập thuộc

tính cho trước, chúng ta biểu diễn X thông qua các lớp tương đương

của (còn gọi là biểu diễn X bằng tri thức có sẵn B), người ta xấp xỉ X bởi

hợp của một số hữu hạn các lớp tương đương của . Có hai cách xấp xỉ

tập đối tượng X thông qua tập thuộc tính B , được gọi là B-xấp xỉ dưới và B-

xấp xỉ trên của X, ký hiệu là lượt là và , được xác định như sau:

Tập bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn

tập bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính

B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập

: B-miền biên của X , : B-miền ngoài của X.

B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không

thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc

X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể

viết lại

Trong trường hợp thì X được gọi là tập chính xác (exact

set), ngược lại X được gọi là tập thô (rough set).

Xét hệ thông tin với , ta gọi B-miền dương của D là

tập được xác định như sau

Rõ ràng là tập tất cả các đối tượng u sao cho với mọi mà

ta đều có . Nói cách khác,

1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai

Phần này trình bày một số khái niệm cơ bản về mô hình tập thô dung sai

trên hệ thông tin không đầy đủ do Kryszkiewicz [67] đề xuất

1.2.1. Hệ thông tin không đầy đủ

Xét hệ thông tin , nếu tồn tại và sao cho chứa

giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ, trái

lại IS được gọi là hệ thông tin đầy đủ. Ta biểu diễn giá trị thiếu được ký hiệu là

‘*’ và hệ thông tin không đầy đủ là .

1.2.2. Mô hình tập thô dung sai

Xét hệ thông tin không đầy đủ , với tập thuộc tính P, ta

định nghĩa một quan hệ nhị phân trên U như sau:

Quan hệ không phải là quan hệ tương đương vì chúng có tính

phản xạ, đối xứng nhưng không có tính bắc cầu. Do đó, là một quan

hệ dung sai (tolerance relation), hay quan hệ tương tự (similarity relation) trên

U. Dễ thấy rằng .

Gọi là tập . là tập lớn nhất các đối

tượng không có khả năng phân biệt được với u trên tập thuộc tính P dựa trên

quan hệ dung sai, còn gọi là một lớp dung sai hay một hạt thông tin. Ký hiệu

tập tất cả các lớp dung sai sinh bởi quan hệ SIM(P) trên U là , khi

đó các lớp dung sai trong không phải là một phân hoạch của U mà

hình thành một phủ của U vì chúng có thể giao nhau và .

Cho tập đối tượng X , dựa trên quan hệ dung sai các tập P-xấp xỉ dưới và

P-xấp xỉ trên của X trong hệ thông tin không đầy đủ, ký hiệu lần lượt là

và , được xác định như sau

Với các tập xấp xỉ nêu trên, ta gọi P-miền biên của X là tập

và P-miền ngoài của X là tập . Trong trường hợp

thì X được gọi là tập chính xác (exact set), ngược lại X được gọi

là tập thô dung sai (tolerance rough set).

Với , ta gọi P-miền dương của D là tập được xác định như sau

Rõ ràng là tập tất cả các đối tượng u sao cho với mọi

ta đều có . Nói cách khác, .

Như vậy, mô hình tập thô dung sai là mô hình tập thô mở rộng dựa trên

quan hệ dung sai trên các hệ thông tin không đầy đủ với các tập xấp xỉ dưới,

xấp xỉ trên được định nghĩa dựa trên quan hệ dung sai.

1.2.3. Bảng quyết định không đầy đủ

Một lớp đặc biệt của các hệ thông tin có vai trò quan trọng trong nhiều

ứng dụng là bảng quyết định. Bảng quyết định là một hệ thông tin DS với tập

thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt

được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là

với .

Xét bảng quyết định , nếu tồn tại và sao cho

thiếu giá trị thì DS được gọi là bảng quyết định không đầy đủ, trái lại DS

được gọi là bảng quyết định đầy đủ. Ta biểu diễn bảng quyết định không đầy

đủ là với . Không mất tính chất tổng quát, giả

thiết D chỉ gồm một thuộc tính quyết định duy nhất .

Định nghĩa 1.1. Cho bảng quyết định , nếu tồn tại

và sao cho thiếu giá trị thì DS được gọi là bảng quyết định không

đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ.

Bảng quyết định không đầy đủ được ký hiệu là với giả

thiết . (thuộc tính quyết định có đầy đủ giá trị).

Định nghĩa 1.2. Cho bảng quyết định không đầy đủ ,

giả sử tập đối tượng được bổ sung vào U hoặc loại bỏ từ U. Khi đó, IDS

được gọi là bảng quyết định thay đổi khi bổ sung hoặc loại bỏ tập đối tượng và

bảng quyết định mới là hoặc

tương ứng.

Định nghĩa 1.3. Cho bảng quyết định không đầy đủ ,

giả sử tập thuộc tính điều kiện được bổ sung vào C hoặc loại bỏ từ C. Khi

đó, IDS được gọi là bảng quyết định thay đổi khi bổ sung hoặc loại bỏ tập

thuộc tính và bảng quyết định mới là hoặc

tương ứng.

Cho bảng quyết định không đầy đủ . Với , ,

gọi là hàm quyết định suy rộng của đối tượng u trên tập

thuộc tính P. Nếu với mọi thì IDS là nhất quán, trái lại IDS là

không nhất quán.

Với bảng quyết định không đầy đủ IDS, miền dương của C đối với

là , khi đó IDS là nhất quán khi và chỉ khi

Với , quan hệ dung sai xác định một phủ (covering) trên U,

ký hiệu là . Ký hiệu

là tập tất cả các phủ của U sinh bởi các tập con

thuộc tính . Trên , phần tử nhỏ nhất

được gọi là phủ rời rạc, phần tử lớn nhất

được gọi là phủ một khối. Một quan hệ thứ tự

bộ phận được định nghĩa trên như sau:

. Dấu đẳng thức

. và

Ví dụ 1.1. Xét bảng quyết định về các xe hơi cho ở Bảng 1.1. Bảng 1.1 là

bảng quyết định không đầy đủ với ,

với (Đơn giá), (Km đã đi), (Kích thước), (Tốc độ)

và (Gia tốc)

Bảng 1.1. Bảng quyết định không đầy đủ về các xe hơi

Ô tô Đơn giá Km đã đi Kích thước Tốc độ Gia tốc

Cao Nhiều Trung bình Thấp Nhanh u1

Thấp * Trung bình Thấp Nhanh u2

* * Gọn nhẹ Cao Chậm u3

Cao * Trung bình Cao Nhanh u4

* * Trung bình Cao Rất nhanh u5

Thấp Nhiều Trung bình Nhanh * u6

Các lớp dung sai của các đối tượng như sau:

, , , ,

, .

với Ta có . Các

tập xấp xỉ dưới đối với C là . Do đó,

Hàm quyết định suy rộng của các đối tượng trên tập thuộc tính C là:

{Nhanh}, {Nhanh}, {Chậm}, {Nhanh, Rất

nhanh}, {Nhanh, Rất nhanh}, {Nhanh, Rất nhanh}. Do đó,

IDS là bảng quyết định không đầy đủ không nhất quán.

1.2.4. Ma trận dung sai

Ma trận dung sai là công cụ biểu diễn giá trị quan hệ dung sai của các

đối tượng trong bảng quyết định không đầy đủ và được định nghĩa như sau:

Định nghĩa 1.4. Cho bảng quyết định không đầy đủ với

và . Khi đó, ma trận dung sai của quan hệ dung sai

, ký hiệu là , được định nghĩa như sau:

trong đó là giá trị của quan hệ dung sai giữa hai đối tượng và trên tập

thuộc tính P, nếu và nếu với

Với việc biểu diễn quan hệ dung sai bằng ma trận dung sai

, ta có mọi , và . Với

, ta có . Giả sử

là hai ma trận dung sai của , , khi đó ma trận

dung sai trên tập thuộc tính là

với

, Xét bảng quyết định không đầy đủ với

, . Giả sử tập đối tượng X được biểu diễn bằng véc tơ một chiều

với nếu và nếu . Khi đó,

và .

Ví dụ 1.2. Xét bảng quyết định ở Ví dụ 1.1, khi đó ma trận dung sai của

quan hệ là

Khi đó ta có , , , ,

, .

1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai

1.3.1. Tổng quan về rút gọn thuộc tính

Trong bối cảnh ngày nay, các cơ sở dữ liệu ngày cà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à phải tìm cách rút gọ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 đó, rút gọn thuộc tính (hay còn gọi là rút gọn

chiều - dimension reduction, rút gọn đặc trưng - feature reduction) trở thành

đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu thuộc các lĩnh vực nhận

dạng thống kê, học máy, khai phá dữ liệu.

Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu

với mục tiêu là loại bỏ các thuộc tính dư thừa, không liên quan nhằm tăng tính

hiệu quả của các thuật toán khai phá dữ liệu: Gia tăng tốc độ, cải thiện chất

lượng và tính dễ hiểu của các kết quả thu được. Các kỹ thuật rút gọn thuộc

tính thường được phân thành hai loại: Lựa chọn thuộc tính (Attribute

selection) và biến đổi thuộc tính (Attribute transformation). Lựa chọn thuộc

tính là chọn một tập con tối tiểu tốt nhất (theo một nghĩa nào đó) từ tập thuộc

tính ban đầu của tập dữ liệu. Trong khi đó, 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 thành một tập các thuộc tính mới

với số lượng ít hơn sao cho bảo tồn được thông tin nhiều nhất. Trong luận án

này, chúng tôi nghiên cứu hướng tiếp cận lựa chọn thuộc tính, gọi chung là

rút gọn thuộc tính.

1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính

Rút gọn thuộc tính là quá trình lựa chọn một tập con gồm P thuộc tính từ

tập gồm M thuộc tính (P ≤ M) sao cho không gian thuộc tính được thu gọn lạ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 (làm mất đi ít nhất lượng thông tin cần thiết) thường khó thực

hiện; nhiều bài toán liên quan đến vấn đề này là những bài toán NP - khó.

Nhìn chung, một thuật toán lựa chọn thuộc tính thường bao gồm bốn khâu cơ

bản:

(1) Tạo lập tập con,

(2) Đánh giá tập con,

(3) Kiểm tra điều kiện dừng,

(4) Kiểm chứng kết quả.

Tạo lập tập con thuộc tính là quá trình tìm kiếm liên tiếp nhằm tạo ra các

tập con để đánh giá, lựa chọn. Giả sử có M thuộc tính trong tập dữ liệu ban

đầu, khi đó số tất cả các tập con từ M thuộc tính sẽ là . Với số ứng viên

này, việc tìm tập con tối ưu, ngay cả khi M không lớn lắm, cũng là một việc

không thể. Vì vậy, phương pháp chung để tìm tập con thuộc tính tối ưu là lần

lượt tạo ra các tập con để so sánh. Mỗi tập con sinh ra bởi một thủ tục sẽ được

đánh giá theo một tiêu chuẩn nhất định và đ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ũ. Quá 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 xảy ra: (a)

đã thu được số thuộc tính quy định, (b) số bước lặp quy định cho quá trình lựa

chọn đã hết, (c) việc thêm vào hay loại bớt một thuộc tính nào đó không cho

một tập con tốt hơn, (d) đã thu được tập con tối ưu theo tiêu chuẩn đánh giá.

Tập con tốt nhất cuối cùng phả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 quả khai phá với tập thuộc tính “tốt nhất”

này và tập thuộc tính ban đầu trên các tập dữ liệu thực hoặc nhân tạo khác

Hình 1.1. Quy trình rút gọn thuộc tính

nhau.

Hiện nay có hai cách tiếp cận chính đối với bài toán rút gọn thuộc tính

[39-40]: filter (lọc) và wrapper (đóng gói). Mỗi cách tiếp cận có những mục

tiêu riêng về giảm thiểu số lượng thuộc tính hay nâng cao độ chính xác.

Cách tiếp cận filter thực hiện việc rút gọn thuộc tính độc lập với thuật

khai phá dữ liệu sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ

quan trọng của chúng trong việc mô tả dữ liệu, gọi là độ quan trọng của thuộc

tính. Cho đến nay, phần lớn các phương pháp rút gọn thuộc tính dựa trên lý

thuyết tập thô và các mở rộng đều theo hướng tiếp cận này. Ngược lại với

cách tiếp cận filter, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách

áp dụng ngay thuật khai phá, độ chính xác của kết quả được lấy làm tiêu

chuẩn để lựa chọn các tập con thuộc tính. Cách tiếp cận filter có ưu điểm là

thời gian tính toán nhanh, nhược điểm là không sử dụng sử dụng thông tin

nhãn lớp của các bộ dữ liệu nên độ chính xác không cao

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

Với phương pháp rút gọn thuộc tính dựa trên lý thuyết tập thô, theo cách

tiếp cận truyền thống filter, tập rút gọn là tập thuộc tính tối thiểu bảo toàn độ

đo được định nghĩa, độ chính xác phân lớp được tính sau khi tìm được tập rút

gọn, do đó tập rút gọn chưa tối ưu về số thuộc tính tập rút gọn và độ chính xác

phân lớp. Cách tiếp cận kết hợp filter-wrapper bao gồm hai giai đoạn: giai

đoạn filter tìm các ứng viên cho tập rút gọn, giai đoạn wrapper tìm ứng viên

tập rút gọn có độ chính xác phân lớp cao nhất. Do đó, tập rút gọn tìm được

giảm thiểu số thuộc tính và cải thiện độ chính xác phân lớp. Tuy nhiên, nhược

điểm của phương pháp filter-wrapper này là thời gian thực hiện lớn hơn các

phương pháp filter do phải chạy bộ phân lớp trong bước wrapper. Hướng tiếp

cận này được sử dụng chủ yếu trong bước rút gọn thuộc tính trong giai đoạn

tiền xử lý dữ liệu của khai phá dữ liệu.

1.3.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai

Lý thuyết tập thô truyền thống do Pawlak đề xuất [113] là công cụ hiệu

quả giải quyết bài toán rút gọn thuộc tính trong bảng quyết định đầy đủ, đã và

đang được cộng đồng nghiên cứu về tập thô thực hiện lâu nay. Trong các bài

toán thực tế, các bảng quyết định thường thiếu giá trị trên miền giá trị thuộc

tính, gọi là bảng quyết định không đầy đủ. Để giải quyết bài toán rút gọn

thuộc tính trực tiếp trên bảng quyết định không đầy đủ mà không qua bước

tiền xử lý giá trị thiếu, Kryszkiewicz [67] mở rộng quan hệ tương đương

trong lý thuyết tập thô truyền thống thành quan hệ dung sai và xây dựng mô

hình tập thô dung sai. Các phương pháp rút gọn thuộc tính trong bảng quyết

định không đầy đủ theo tiếp cận mô hình tập thô dung sai là các nghiên cứu

mở rộng của các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền

thống, bao gồm các bước như sau:

Tập thuộc tính ban đầu

Định nghĩa tập rút gọn

Định nghĩa độ quan trọng của thuộc tính

Xây dựng thuật toán heuristic tìm một tập rút gọn

Tập rút gọn

Hình 1.3. Mô hình phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai

1) Định nghĩa khái niệm tập rút gọn dựa trên một độ đo được định nghĩa,

ví dụ miền dương, ma trận phân biệt, hàm phân biệt, entropy thông tin,

khoảng cách, lượng thông tin, hạt thông tin...

2) Đưa ra khái niệm độ quan trọng của thuộc tính dựa trên độ đo được

định nghĩa. Độ quan trọng của thuộc tính đặc trưng cho khả năng đóng góp của

thuộc tính vào việc phân lớp tập đối tượng. Thuộc tính có độ quan trọng càng

lớn thì khả năng đóng góp vào việc phân lớp đối tượng càng nhiều và ngược lại.

3) Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo

tiêu chuẩn đánh giá là độ quan trọng của thuộc tính (khả năng phân lớp của

thuộc tính).

Như vậy, nhiệm vụ quan trọng nhất của một phương pháp rút gọn thuộc

tính theo tiếp cận tập thô là xây dựng một thuật toán heuristic tìm tập rút gọn

của bảng quyết định. Thuật toán này giảm thiểu đáng kể khối lượng tính toán,

nhờ đó có thể áp dụng đối với các bài toán có dữ liệu lớn. Các thuật toán

heuristic này thường được xây dựng theo hai hướng tiếp cận khác nhau:

hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-

down). Ý tưởng chung của các thuật toán theo tiếp cận top-down là xuất phát

từ tập rỗng, lần lượt bổ sung vào các thuộc tính điều kiện có độ quan trọng

lớn nhất cho cho đến khi thu được tập rút gọn. Các thuật toán được xây dựng

theo hướng tiếp cận bottom-up xuất phát từ tập thuộc tính điều kiện ban đầu,

lần lượt loại bỏ các thuộc tính có độ quan trọng nhỏ nhất cho đến khi thu được

tập rút gọn. Cả hai hướng tiếp cận này đều đòi hỏi phải sắp xếp danh sách các

thuộc tính theo thứ tự tăng dần hoặc giảm dần theo độ quan trọng tại mỗi bước

lặp của thuật toán. Tập rút gọn tìm được là tập thuộc tính điều kiện nhỏ nhất bảo

toàn độ đo được định nghĩa. Việc kiểm tra độ chính xác phân lớp của bảng quyết

định được thực hiện sau khi tìm được tập rút gọn. Do đó, các phương pháp rút

gọn thuộc tính theo tiếp cận tập thô dung sai được đề xuất cho đến nay là các

phương pháp theo tiếp cận filter.

1.4. Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập

thô dung sai

Kể từ khi Kryszkiewicz [67] đề xuất mô hình tập thô dung sai, các

phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định không đầy đủ

theo tiếp cận tập thô dung sai đã thu hút sự quan tâm của cộng đồng nghiên

cứu về tập thô. Trong phần này, chúng tôi trình bày tóm tắt các nghiên cứu

liên quan đến rút gọn thuộc tính theo tiếp cận tập thô dung sai với hai trường

hợp: bảng quyết định không thay đổi và bảng quyết định thay đổi.

1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai

1.4.1.1. Các nghiên cứu liên quan

Trong hai thập kỷ vừa qua đã chứng kiến sự phát triển mạnh mẽ và sôi

động của lĩnh vực nghiên cứu về rút gọn thuộc tính theo tiếp cận tập thô dung

sai. Nhiều nhóm nhà khoa học trên thế giới và tại Việt Nam đã đề xuất các

thuật toán rút gọn thuộc tính hiệu quả trong bảng quyết định không đầy đủ sử

dụng các độ đo khác nhau như miền dương, entropy thông tin, lượng thông tin,

ma trận phân biệt, hàm phân biệt, khoảng cách…Bảng 2.1 trình bày 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

Bảng 1.2. Các thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai

quyết định không đầy đủ theo tiếp cận tập thô dung sai.

Công bố, năm xuất bản Thuật toán

STT 1) Miền dương 1

Các thuật toán tìm tập rút gọn sử dụng miền dương mở rộng

 Hu và các cộng sự [51], 2017.  Xu và các cộng sự [117], 2013.  Peng và các cộng sự [25], 2010.  Meng và các cộng sự [114],

2009.

2  Qian và các cộng sự [99], 2011. Thuật toán tìm tập rút gọn sử

dụng miền dương xấp xỉ

Thuật toán

STT Công bố, năm xuất bản 2) Ma trận phân biệt, hàm phân biệt 3

 Ma và các cộng sự [29], 2017.  Vu Van Dinh, Nguyen Long

Các thuật toán sử dụng ma trận phân biệt, hàm phân biệt mở rộng. Giang [77], 2013.

Các thuật toán tìm tập rút gọn sử dụng ma trận phân biệt, ma trận gán

5  Zou và các cộng sự [45], 2012.  Tan và các cộng sự [80], 2010.  Xu và các cộng sự [116], 2009.  Zhou và các cộng sự [57], 2009. Thuật toán tìm tập rút gọn sử

6  Li và các cộng sự [47], 2010.

dụng ma trận tương tự Thuật toán tìm tập rút gọn sử dụng ma trận nhị phân

3) Entropy thông tin 7

Các thuật toán tìm tập rút gọn sử dụng entropy thông tin mở rộng.

8  Tao và các cộng sự [107], 2017.  Yue và các cộng sự [26], 2015.  Xu và các cộng sự [49], 2013.  Dai và các cộng sự [50], 2013.  Sun và các cộng sự [64], 2012.  Qian và các cộng sự [79], 2015. Thuật toán tìm tập rút gọn sử

dụng entropy tương hỗ mở rộng

Các thuật toán tìm tập rút gọn sử dụng lượng thông tin mở rộng

10 4) Độ đo lượng thông tin, hạt thông tin 9  Xu và các cộng sự [91], 2019.  Xu và các cộng sự [94], 2012.  Sai Prasad và các cộng sự [72],

Thuật toán tìm tập rút gọn sử dụng hạt thông tin mở rộng 2012.

5) Độ đo khoảng cách 11  Vu Van Dinh và các cộng sự

Các thuật toán tìm tập rút gọn sử dụng độ đo khoảng cách [78], 2015.

 Long Giang Nguyen, Hung Son

Nguyen [62], 2013.

6) Các độ đo khác 12  Xie và các cộng sự [92], 2018.

Thuật toán tìm tập rút gọn sử dụng độ đo không nhất quán.

Thuật toán

STT 13 Công bố, năm xuất bản  Shu và các cộng sự [85], 2014.

 Zhao và các cộng sự [48], 2014.

15  Meng và các cộng sự [115],

2012.

Thuật toán tìm tập rút gọn sử dụng quan hệ không phân biệt được Các thuật toán tìm tập rút gọn sử dụng hàm quyết định suy rộng, entropy dựa trên quan hệ dung sai lân cận. So sánh, đánh giá các thuật toán heuristic tìm tập rút gọn Thuật toán tìm tập rút gọn sử dụng độ bao phủ của thuộc tính Nghiên cứu về các tập rút gọn và mối quan hệ giữa chúng.  Dai và các cộng sự [93], 2010.  Qian và các cộng sự [98], 2010.  Nguyen Long Giang và các

cộng sự [69], 2013.

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

Các thuật toán tìm tập rút gọn đều hướng tới mục tiêu là tìm được tập rút

gọn hiệu quả nhất để thực thi mô hình phân lớp dựa trên các tiêu chí: giảm

thiểu tối đa số thuộc tính tập rút gọn để giảm thiểu độ phức tạp của mô hình và

nâng cao độ chính xác của mô hình. Các thuật toán đã đề xuất được trình bày

trong Bả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 là tập rút gọn thu được là tập thuộc tính tối thiểu bảo toàn

độ đo được định nghĩa. Việc đánh giá độ chính xác của mô hình phân lớp được

thực hiện sau khi tìm được tập rút gọn. Do đó, tập rút gọn của các thuật toán

filter nêu trên chưa tối ưu về số lượng thuộc tính và độ chính xác phân lớp.

1.4.1.3. Định hướng nghiên cứu thứ nhất của luận án

Trong các độ đo được sử dụng trong các thuật toán trong Bảng 1.2,

khoảng cách được chứng minh là độ đo hiệu quả giải quyết bài toán rút gọn

thuộc tính trong bảng quyết định không đầy đủ [62], [78]. Do đó, mục tiêu

nghiên cứu thứ nhất của luận án là nghiên cứu, đề xuất các thuật toán tìm tập

rút gọn sử dụng độ đo khoảng. Khác với hướng tiếp cận filter của các phương

pháp đã công bố trong Bảng 1.2, luận án sử dụng hướng tiếp cận kết hợp

filter-wrapper để xây dựng các thuật toán nhằm giảm thiểu số lượng thuộc

tính của tập rút gọn, trong khi cố gắng bảo toàn và cải thiện độ chính xác mô

hình phân lớp.

1.4.2. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định

không đầy đủ theo tiếp cận tập thô dung sai