Luận án Tiến sỹ Toán học: 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

1

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

VŨ VĂN ĐỊNH

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

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

HÀ NỘI – 2016

2

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Ệ ……..….***…………

VŨ VĂN ĐỊNH

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

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

Chuyên ngành: Cơ sở toán học cho tin học

Mã số: 62 46 01 10

Người hướng dẫn khoa học:

1. GS.TS Vũ Đức Thi

2. PGS.TS Ngô Quốc Tạo

HÀ NỘI – 2016

1

LỜI CAM ĐOAN

Tôi xin cam đoan bản luận án tiến sĩ này là công trình do chính tôi

nghiên cứu và thực hiện. Các thông tin số liệu được sử dụng trong luận án

hoàn toàn trung thực và chính xác. Tất cả sự giúp đỡ cho việc thực hiện luận

án đã được xin phép và cảm ơn. Các thông tin trích dẫn trong luận án đã được

ghi rõ nguồn gốc.

Vũ Văn Định

Tác giả luận án

2

LỜI CẢM ƠN

Lời đầu tiên, tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TS Vũ Đức Thi,

PGS.TS Ngô Quốc Tạo, TS. Nguyễn Long Giang, những người Thầy đã

không ngại gian khó tận tình giúp đỡ và hướng dẫn tôi trong suốt quá trình

nghiên cứu và hoàn thành luận án.

Tôi xin chân thành cảm ơn đến Ban lãnh đạo Viện Công nghệ thông tin

thuộc 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ệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Phòng

quản lý đào tạo, các phòng ban chức năng và tập thể các Nhà khoa học của

Viện Công nghệ thông tin và Học viện Khoa học và Công nghệ đã giúp đỡ tôi

trong suốt quá trình học tập và nghiên cứu.

Tôi xin được bày tỏ lòng biết ơn đến Ban giám hiệu, lãnh đạo các đơn vị

Trường Đại học Điện lực đã hỗ trợ, tạo điều kiện tốt nhất cho tôi trong suốt

quá trình thực hiện luận án.

Tôi xin chân thành cảm ơn tới lãnh đạo và các đồng nghiệp tại Khoa

Công nghệ thông tin, Phòng Khảo thí và Đảm bảo chất lượng giáo dục

trường Đại học Điện lực đã động viên giúp đỡ tôi trong thời gian tôi học tập

và nghiên cứu.

Cuối cùng tôi bày tỏ lòng biết ơn đến gia đình và người thân của tôi,

những người luôn sát cánh bên tôi để động viên, giúp đỡ tôi vượt qua khó

khăn để hoàn thành luận án.

3

MỤC LỤC

LỜI CAM ĐOAN.............................................................................................................................1

LỜI CẢM ƠN....................................................................................................................................2

MỤC LỤC ..........................................................................................................................................3

DANH MỤC CÁC THUẬT NGỮ...............................................................................................6

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

DANH MỤC HÌNH, BẢNG..........................................................................................................8

MỞ ĐẦU.............................................................................................................................................9

CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ.........................................................................18

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

1.1.1. Hệ thông tin....................................................................................18

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

1.1.3. Bảng quyết định đầy đủ..................................................................21

1.1.4. Tập rút gọn và tập lõi ....................................................................22

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

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

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

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

1.3. Các khái niệm về tập rút gọn của bảng quyết định không đầy đủ.................29

1.3.1. Tập rút gọn dựa trên hàm quyết định suy rộng .............................29

1.3.2. Tập rút gọn dựa trên miền dương ..................................................30

1.3.3. Tập rút gọn dựa trên độ đo lượng thông tin ..................................30

1.3.4. Tập rút gọn dựa trên ma trận phân biệt ........................................30

1.3.5. Tập rút gọn dựa trên ma trận dung sai..........................................31

1.3.6. Tập rút gọn dựa trên hàm phân bố, hàm ấn định ..........................32

1.3.7. Tập rút gọn dựa trên metric...........................................................32

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

4

CHƯƠNG 2. ĐỀ XUẤT PHÂN NHÓM VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP

RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ........34

2.1. Mở đầu ..............................................................................................................34

2.2. Đề xuất phân nhóm các phương pháp rút gọn thuộc tính ..............................35

2.2.1 Bảng ký hiệu các tập rút gọn của bảng quyết định không đầy đủ .36

IR ,

TMR ...............37

PR ..............................................................40

2.2.2 Mối liên hệ giữa các khái niệm tập rút gọn DR ,

2.2.3 Mối liên hệ giữa R và

2.2.4 Mối liên hệ giữa DR và R .............................................................41

2.2.5 Mối liên hệ giữa R và R .............................................................44

2.2.6 Đề xuất phân nhóm các phương pháp rút gọn thuộc tính .............45

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

2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng .........................48

2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định ....54

2.3.3. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút

gọn ........................................................................................................57

2.3.4. Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút

gọn ........................................................................................................60

2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính..............65

2.4. Kết luận chương 2 ............................................................................................67

CHƯƠNG 3. ĐỀ XUẤT CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG

BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ.............................................................................68

3.1. Mở đầu ..............................................................................................................68

3.2. Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính.........................68

3.2.1. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ.........69

3.2.2. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ ..73

3.3. Phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều

kiện ...........................................................................................................................78

5

3.3.1. Độ đo lượng thông tin mở rộng .....................................................79

3.3.2. Xây dựng lượng thông tin mở rộng có điều kiện ...........................80

3.3.3. Rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều kiện82

3.3.4. Thử nghiệm và đánh giá kết quả....................................................87

3.4. Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ..................................91

3.4.1. Ma trận quan hệ và hàm quan hệ ..................................................92

3.4.2. Rút gọn thuộc tính sử dụng hàm quan hệ ......................................95

3.4.3. Thử nghiệm và đánh giá kết quả....................................................98

3.5. Kết luận chương 3 ..........................................................................................100

DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ.....................................................................104

6

DANH MỤC CÁC THUẬT NGỮ

Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh

Hệ thông tin không đầy đủ Incomplete Information System

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

Quan hệ không phân biệt được Indiscernibility Relation

Tolerance Relation Quan hệ dung sai

Tolerance Rough Set Tập thô dung sai

Lower Approximation Xấp xỉ dưới

Upper Approximation Xấp xỉ trên

Rút gọn thuộc tính Attribute Reduction

Reduct Tập rút gọn

Core Tập lõi

Ma trận phân biệt Indiscernibility Matrix

Indiscernibility Function Hàm phân biệt

Relational Matrix Ma trận quan hệ

Relations Function Hàm quan hệ

Lượng thông tin mở rộng Extended information quantity

Luật quyết định Decision Rule

7

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

,

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

 IIS U A 



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

,



  d

 IDS U A 



U

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

A

Số đối tượng

u

a

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

 u a



Giá trị của đối tượng tại thuộc tính

 SIM A



u

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

  AS u

U

/U A

Lớp dung sai của đối tượng trên tập thuộc tính A

/U SIM A

Phân hoạch của sinh bởi tập thuộc tính A.





COVER U

Phủ của U sinh bởi tập thuộc tính A.





u

Họ tất cả các phủ của U.

A u ( )

AX

X

A 

Hàm quyết định suy rộng của đối tượng đối với A.

X

A 

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

AX



X

xấp xỉ trên của

BN P

D

A 

B - miền biên của X





POS D A

dBI    /

miền dương của

Lượng thông tin của tập thuộc tính B đối với thuộc

tính quyết định d

    CEI R d

Lượng thông tin mở rộng của tập thuộc tính R đối

với thuộc tính quyết định d

AMC

Họ các khối đồng nhất cực đại trên tập A

RDIS 

Hàm quan hệ của IDS trên R

8

DANH MỤC HÌNH, BẢNG

Hình 1.1. Mối quan hệ giữa các tập rút gọn .................................................46

Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn..................................64

Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán

EIQBAR và MBAR....................................................................................90

Bảng 1.1. Bảng quyết định về bệnh cúm.........................................................21

Bảng 1.2. Bảng thông tin về xe hơi.................................................................24

Bảng 1.3. Bảng quyết định về các xe hơi........................................................28

Bảng 2.1. Ký hiệu các tập rút gọn trong bảng quyết định không đầy đủ. ......36

Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.1 ..............................................41

Bảng 2.3. Bảng quyết định minh họa Ví dụ 2.2 ..............................................43

Bảng 2.4. Bảng quyết định không đầy đủ về các tivi ......................................49

Bảng 2.5. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1 ..63

Bảng 2.6. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2 ..63

Bảng 3.1. Bảng thông tin về các xe hơi ..........................................................72

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

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

Bảng 3.5. Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR ...........89

Bảng 3.6. Kết quả tính toán độ chắc chắn, độ nhất quán và độ hỗ trợ trên các

tập rút gọn ................................................................................................90

Bảng 3.7. Bảng quyết định không đầy đủ mô tả về các tivi ............................92

Bảng 3.8. Kết quả thực hiện thuật toán MBAR, Thuật toán EIQBAR và Thuật

toán RBAR ................................................................................................99

Bảng 3.9. Tập rút gọn của thuật toán MBAR, Thuật toán EIQBAR và Thuật

toán RBAR ................................................................................................99

9

MỞ ĐẦU

Lý thuyết tập thô do Pawlak [31] đề xuất vào những năm đầu thập niên

tám mươi của thế kỷ hai mươi được xem là công cụ hữu hiệu để giải quyết

các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, không chắc

chắn. Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các

bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý

số liệu, khai phá dữ liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và

trích lọc luật quyết định (luật phân lớp) là hai ứng dụng chính của lý thuyết

tập thô trong khai phá dữ liệu. Rút gọn thuộc tính thuộc giai đoạn tiền xử lý

dữ liệu còn trích lọc luật thuộc giai đoạn khai phá dữ liệu. Mục tiêu của rút

gọn thuộc tính là loại bỏ các thuộc tính dư thừa nhằm tìm tập con nhỏ nhất

của tập thuộc tính điều kiện (tập rút gọn) mà bảo toàn thông tin phân lớp của

bảng quyết định. Dựa trên tập rút gọn thu được, việc sinh luật và phân lớp đạt

hiệu quả cao nhất.

Rút gọn thuộc tính trong bảng quyết định theo tiếp cận lý thuyết tập thô

của Pawlak [31] là chủ đề nghiên cứu sôi động trong hai thập kỷ qua. Cho đến

nay, có rất nhiều phương pháp rút gọn thuộc tính đã được đề xuất bởi các

nhóm nghiên cứu theo các hướng tiếp cận khác nhau như: hướng tiếp cận dựa

trên miền dương, hướng tiếp cận dựa trên ma trận, hướng tiếp cận dựa trên độ

đo entropy, hướng tiếp cận tính toán hạt, hướng tiếp cận dựa trên độ đo

khoảng cách... Phương pháp rút gọn thuộc tính dựa trên miền dương do

Pawlak [48] đề xuất, phương pháp này đã xây dựng thuật toán tính miền



D

POSC

dương . Về sau, các công bố trong [31][49][11][25] đã tiếp tục cải

tiến thuật toán này. Phương pháp rút gọn thuộc tính sử dụng các phép toán

trong đại số quan hệ do Hu Xiaohua và các cộng sự [14] đưa ra, phương pháp

này xây dựng thuật toán tìm tập lõi và tập rút gọn của bảng quyết định. Tuy

nhiên khái niệm tập lõi có nhược điểm và đã được tác giả trong luận án [1]

10

khắc phục. Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt do

Skowron [8] đề xuất được xây dựng trên khái niệm ma trận phân biệt, hàm

phân biệt. Phương pháp này cũng đã được Ye Dong Yi và các cộng sự [51]

khắc phục nhược điểm tìm tập rút gọn và tập lõi trong bảng quyết định không

nhất quán. Phương pháp rút gọn thuộc tính sử dụng các độ đo trong tính toán

hạt được Zadeh [53] giới thiệu về mô hình tính toán hạt và đã được các tác giả

[21], [22], [54] đề xuất các thuật toán heuristic tìm tập rút gọn sử dụng độ đo

phép kết hạt bởi thuộc tính làm tiêu chuẩn đánh giá độ quan trọng của thuộc

tính. Phương pháp rút gọn thuộc tính sử dụng entropy thông tin do các tác giả

Wang Guo Yin và các cộng sự [43], [45], [46], [47], [48] phát triển từ khái

niệm Entropy thông tin Shannon giới thiệu vào năm 1948. Tuy nhiên, các tác

giả trong [42], [43], đã phân tích nhược điểm của định nghĩa độ quan trọng

của thuộc tính trong [47] và đề xuất định nghĩa độ quan trọng mới, từ đó xây

dựng thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon có điều

kiện. Phương pháp rút gọn thuộc tính sử dụng metric do tác giả trong luận

án[2] đề xuất dựa trên cơ sở khái niệm metric do R.López de Mántaras [38]

xây dựng. Song song với việc đề xuất các phương pháp rút gọn thuộc tính,

các nhà nghiên cứu tập trung vào đề xuất các độ đo làm tiêu chuẩn định lượng

để so sánh, đánh giá các phương pháp rút gọn thuộc tính. Trong luận án [2]

tác giả đã tìm mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn,

dựa vào đó đã phân các phương pháp rút gọn làm 3 nhóm: Nhóm 1: Nhóm

phương pháp tìm tập rút gọn Pawlak; Nhóm 2: Nhóm phương pháp tìm tập rút

gọn Entropy Shannon (bao gồm phương pháp sử dụng entropy Shannon và

phương pháp sử dụng các phép toán trong đại số quan hệ); Nhóm 3: Nhóm

phương pháp tìm tập rút gọn Entropy Liang (Bao gồm phương pháp sử dụng

entropy Liang, phương pháp sử dụng ma trận phân biệt và phương pháp sử

dụng độ khác biệt của tri thức). Dựa vào ba độ đo độ chắc chắn, độ nhất quán

và độ hỗ trợ của Yuhua Qian [36], tác giả trong luận án [2] cũng đã đề xuất độ

11

nhất quán mới, nhằm so sánh, đánh giá các nhóm phương pháp rút gọn thuộc

tính.

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à các bảng quyết định không đầy đủ. Trên bảng

quyết định không đầy đủ, Kryszkiewicz [18] đã 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à đề xuất

mô hình tập thô dung sai nhằm giải quyết bài toán rút gọn thuộc tính và trích

lọc luật trực tiếp không qua bước xử lý giá trị thiếu. Giống như các phương

pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo tiếp cận lý thuyết

tập thô truyền thống được trình bày trong luận án [2], 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 đã công bố là các phương pháp heuristic, đều thực hiện các bước sau

đây:

1) Đưa ra khái niệm tập rút gọn dựa trên độ đo được xây dựng.

2) Đưa ra khái niệm độ 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)

Trong mấy năm gần đây 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 đã được các nhà khoa

học quan tâm nghiên cứu và đã thu được một số kết quả đáng kể. Các phương

pháp điển hình có thể kể đến là: Kryszkiewicz [18] định nghĩa tập rút gọn dựa

trên hàm quyết định suy rộng và đề xuất phương pháp rút gọn thuộc tính sử

12

dụng hàm quyết định suy rộng. Zuqiang Meng và các cộng sự [56] đưa ra

khái niệm về tập rút gọn dựa trên miền dương và đề xuất phương pháp rút gọn

thuộc tính dựa trên miền dương. Theo hướng tiếp cận tính toán hạt (granular

computing), Huang B và các cộng sự [16] đưa ra khái niệm tập rút gọn dựa

trên độ đo lượng thông tin (information quantity) và đề xuất phương pháp rút

gọn thuộc tính dựa trên độ đo lượng thông tin. Theo hướng tiếp cận mở rộng

khái niệm ma trận phân biệt trong lý thuyết tập thô truyền thống, Huasheng

ZOU và cộng sự [17] đưa ra khái niệm tập rút gọn dựa trên ma trận phân biệt

và đề xuất phương pháp rút gọn thuộc tính dựa trên ma trận phân biệt . Cũng

theo hướng tiếp cận này, các tác giả trong [19] đưa ra khái niệm tập rút gọn

dựa trên ma trận dung sai (tolerance matrix) và xây dựng phương pháp rút

gọn thuộc tính dựa trên ma trận dung sai. Ngoài ra, có thể kể đến các phương

pháp rút gọn thuộc tính trong các công trình [29], [31], các tác giả này đã đưa

ra khái niệm tập rút gọn phân bố (distribution reduct), tập rút gọn ấn định

(assignment reduct) và xây dựng phương pháp rút gọn thuộc tính dựa trên

hàm phân bố, hàm ấn định. Theo hướng tiếp cận độ đo khoảng cách (metric),

tác giả trong luận án [2] xây dựng độ đo metric và đề xuất phương pháp rút

gọn thuộc tính trên bảng quyết định không đầy đủ dựa trên metric được xây

dựng.

Giống như cách tiếp cận trong lý thuyết tập thô truyền thống, để tiến hành

so sánh, đánh giá các phương pháp rút gọn thuộc tính theo các hướng tiếp cận

khác nhau nhằm tìm ra một phương pháp hiệu quả với một bài toán thực tế,

các nhà nghiên cứu tập trung giải quyết hai vấn đề: vấn đề thứ nhất là tìm

kiếm mối liên hệ giữa các khái niệm tập rút gọn của các phương pháp nhằm

phân nhóm các phương pháp; vấn đề thứ hai là đề xuất các độ đo hiệu quả

nhằm đánh giá các phương pháp về mặt định lượng.

13

Về vấn đề thứ nhất, cho đến nay đã có một số kết quả nghiên cứu về mối

liên hệ giữa các khái niệm tập rút gọn. Trong bảng quyết định nhất quán,

công bố [37], [56] đã chỉ ra tập rút gọn dựa trên miền dương [56], tập rút gọn

dựa trên hàm quyết định suy rộng [18], tập rút gọn dựa trên hàm phân bố, tập

rút gọn dựa trên hàm ấn định [37], [55] là có định nghĩa độ đo tương đương

nhau. Trong bảng quyết định không nhất quán, Renpu Li và cộng sự [37] đã

chứng minh tập rút gọn dựa trên miền dương, tập rút gọn dựa trên hàm ấn

định là có định nghĩa độ đo tương đương nhau. Huasheng ZOU và cộng sự [17]

đã chứng minh tập rút gọn dựa trên hàm quyết định suy rộng, tập rút gọn dựa

trên ma trận phân biệt là có định nghĩa độ đo tương đương nhau. Tuy nhiên,

theo tài liệu hiện có thì cho đến nay chưa có nghiên cứu tổng thể về mối liên hệ

đầy đủ giữa các khái niệm tập rút gọn, từ đó có một bức tranh tổng thể về mối

liên hệ giữa các khái niệm tập rút gọn, là cơ sở để phân nhóm các phương pháp

rút gọn thuộc tính dựa vào tập rút gọn.

Về vấn đề thứ hai, Yuhua Qian và các cộng sự [33] đã xây dựng các độ đo

đánh giá hiệu năng của tập luật quyết định, tuy nhiên các độ đo này các tác

giả đã xây dựng dựa trên khối đồng nhất cực đại, nhưng các phương pháp trên

được định nghĩa dựa trên quan hệ dung sai, do đó không thể sử dụng các độ

đo của Yuhua Qian và các cộng sự [33] để đánh giá các phương pháp rút gọn

thuộc tính và đòi hỏi phải xây dựng các độ đo mới.

Trên cơ sở tổng kết các nghiên cứu liên quan đến các phương pháp rút

gọn thuộc tính và các độ đo đánh giá hiệu năng tập luật quyết định dựa trên

các tập rút gọn theo tiếp cận tập thô dung sai như đã trình bày ở trên, luận án

đặt ra các vấn đề cần nghiên cứu như sau:

1) Có thể nói rằng tập rút gọn chính là kết quả của một phương pháp rút

gọn thuộc tính. Trong bảng quyết định nhất quán, công bố [37], [56]

đã chỉ ra tập rút gọn của phương pháp dựa trên miền dương [56], tập

14

rút gọn của phương pháp sử dụng hàm quyết định suy rộng [18], tập

rút gọn sử dụng hàm phân bố, phương pháp sử dụng hàm ấn định

[37], [55] là có định nghĩa độ đo tương đương nhau. Tuy nhiên trên

bảng quyết định không nhất quán, các tập rút gọn của các phương

pháp là khác nhau và theo tài liệu hiện có mà tác giả biết thì chưa có

nghiên cứu liên quan đến việc so sánh các tập rút gọn làm cơ sở để so

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

2) Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính thường

dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán heuristic

tìm tập rút gọn và khả năng phân lớp của tập rút gọn [2]. Từ việc

tổng kết các phương pháp rút gọn thuộc tính, tác giả thấy rằng nếu

cùng sử dụng một đơn vị tính toán cơ sở trong tập thô dung sai (lực

lượng các lớp dung sai) thì độ phức tạp thời gian các thuật toán

heuristic của các phương pháp là gần như nhau (độ phức tạp thời

gian đa thức). Do đó, việc so sánh, đánh giá các phương pháp đều sử

dụng tiêu chuẩn khả năng phân lớp (độ hỗ trợ của tập luật) của tập

rút gọn. Về mặt định tính, tập rút gọn bảo toàn khả năng phân lớp

của bảng quyết định. Về mặt định lượng, tập rút gọn bảo toàn độ

chắc chắn của tập luật quyết định [2]. Tập rút gọn của phương pháp

nào có độ hỗ trợ của tập luật cao (luật quyết định phủ nhiều đối

tượng) thì có khả năng phân lớp cao [2]. Do đó, khả năng phân lớp

được tính bằng độ hỗ trợ của tập luật. Trong công trình [33], các tác

giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật

quyết định trên bảng quyết định không đầy đủ. Tuy nhiên, các tác giả

chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút gọn

của các phương pháp rút gọn thuộc tính, do đó các độ đo này không

đánh giá được khả năng phân lớp của tập rút gọn và đòi hỏi phải có

15

độ chắc chắn, độ hỗ trợ mới để đánh giá khả năng phân lớp của tập

rút gọn, làm cơ sở để so sánh, đánh giá các phương pháp rút gọn

thuộc tính.

3) Hướng nghiên cứu rút gọn thuộc tính đã đạt được một số kết quả

nhất định. Tuy nhiên, việc nghiên cứu và tìm kiếm các phương pháp

mới vẫn đòi hỏi nhiều nỗ lực nghiên cứu nhằm phong phú thêm các

phương pháp rút gọn thuộc tính. Trên cơ sở đó, lựa chọn các phương

pháp phù hợp để giải quyết các bài toán trong thực tiễn.

Từ các vấn đề cần nghiên cứu đã trình bày ở trên, mục tiêu nghiên cứu

của luận án là so sánh, đánh giá các phương pháp rút gọn thuộc tính đã công

bố, trên cơ sở đó đề xuất các phương pháp mới.

Với mục tiêu trên, nội dung nghiên cứu của luận án là:

1) Nghiên cứu mối liên hệ giữa các tập rút gọn nhằm: phân nhóm các

phương pháp rút gọn thuộc tính đã công bố theo nguyên tắc: các tập

rút gọn của các phương pháp có định nghĩa độ đo tương đương nhau

được phân thành một nhóm; mối quan hệ giữa các tập rút gọn của các

nhóm phương pháp.

2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ

chắc chắn, độ nhất quán, độ hỗ trợ) và nghiên cứu sự thay đổi các độ

đo này trên các tập rút gọn của các nhóm phương pháp nhằm đánh

giá các phương pháp theo tiêu chuẩn khả năng phân lớp của tập rút

gọn. Tập rút gọn của phương pháp nào có khả năng phân lớp tốt nhất,

kém nhất...

3) Đề xuất hai phương pháp mới rút gọn thuộc tính trong bảng quyết

định không đầy đủ: phương pháp sử dụng hàm quan hệ và phương

16

pháp sử dụng lượng thông tin mở rộng. So sánh, đánh giá phương

pháp đề xuất với các phương pháp đã công bố.

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

với kích thước trung bình và kích thước lớn.

Phạm vi nghiên cứu của luận án: Tập trung vào bài toán toán rút gọn

thuộc tính ở bước tiền xử lý số liệu trên bảng quyết định không đầy đủ.

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

- Nghiên cứu lý thuyết: các mệnh đề được đưa ra đều được chứng minh

chặt chẽ trên nền tảng kiến thức cơ bản kết hợp với các kết quả đã được công

bố trên các tạp chí chuyên ngành uy tín.

- Nghiên cứu thực nghiệm: Thực nghiệm các phương pháp đề xuất trên

các bộ số liệu lấy từ kho dữ liệu UCI [40], kết quả thực nghiệm kiểm chứng

kết quả lý thuyết để khẳng định tính đúng đắn của kết quả nghiên cứu.

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 tổng quan về các khái niệm cơ bản về mô hình tập thô

truyền thống và mô hình tập thô dung sai dựa trên quan hệ dung sai trong hệ

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

định không đầy đủ đã có. Các đóng góp chính của luận án sẽ được trình bày

trong chương 2 và chương 3.

Chương 2 trình bày hai kết quả chính. Thứ nhất là kết quả phân nhóm các

phương pháp rút gọn thuộc tính dựa vào kết quả nghiên cứu mối liên hệ giữa

các tập rút gọn. Thứ hai là đề xuất các độ đo mới đánh giá hiệu năng tập luật

quyết định (độ chắc chắn, độ nhất quán, độ hỗ trợ) và nghiên cứu sự thay đổi

giá trị các độ đo này trên các tập rút gọn nhằm so sánh, đánh giá các nhóm

17

phương pháp rút gọn thuộc tính trên tiêu chuẩn khả năng phân lớp của tập rút

gọn (độ hỗ trợ của tập luật).

Chương 3 trình bày ba kết quả chính. Thứ nhất là chọn tập tối tượng đại

diện cho bài toán rút gọn thuộc tính nhằm giảm thiểu số đối tượng (dữ liệu),

tăng tính hiệu quả của các thuật toán rút gọn thuộc tính. Thứ hai là đề xuất

phương pháp mới rút gọn thuộc tính sử dụng hàm quan hệ và so sánh, thử

nghiệm phương pháp với các phương pháp đã có trên các bộ số liệu UCI. Thứ

ba là đề xuất phương pháp mới rút gọn thuộc tính sử dụng lượng thông tin mở

rộng và so sánh, thử nghiệm phương pháp với các phương pháp đã có trên các

bộ số liệu UCI.

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 tiếp theo và các vấn đề khác mà tác giả quan tâm.

18

CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ

Chương này trình bày một số khái niệm cơ bản về hệ thông tin và mô

hình tập thô truyền thống của Pawlak[31], mô hình tập thô mở rộng dựa trên

quan hệ dung sai do Kryszkiewicz [18] đề xuất, gọi là mô hình tập thô dung

sai, trên các hệ thông tin không đầy đủ, bao gồm: hệ thông tin không đầy đủ,

quan hệ dung sai, các tập xấp xỉ dựa trên quan hệ dung sai, bảng quyết định

không đầy đủ. Chương này cũng trình bày một số khái niệm về tập rút gọn

của các phương pháp rút gọn thuộc tính đã công bố làm cơ sở cho nghiên cứu

về mối liên hệ giữa các khái niệm tập rút gọn ở Chương 2.

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

,



1.1.1. Hệ thông tin

 IS U A



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

a U :

a A

a A

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

V a

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

u U a A ,





.

B

,...,

A





Với mọi , ta ký hiệu giá trị thuộc tính a tại đối tượng u là

  a u



 b b 2, 1

b k

Nếu là một tập con các thuộc tính thì ta ký hiệu bộ

 B u

  ib u





i

1,...,

k



các giá trị bởi . Như vậy, nếu u và v là hai đối tượng, thì ta viết

  B u

  B v

  b u i

  b v i

A

,

P



nếu với mọi .

 IS U A



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

 IND P



,

,



   



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

 IND P



  u v U U a P a u



 

   a v

.

 IND P



 IND P



,u v



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





 IND P



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

19

/U IND P

/U P

 IND P







/U P

không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương . Ký xác định một phân hoạch trên U, ký hiệu là hay

 P u

,



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



 IND P

  u

P

  v U u v  

 

.

,

X U



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

 IS U A



B

A

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

/U B

/U B

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

BX

BX

(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 của 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-

BX

X

BX



B

B

   u U u  

,

   u U u  

. X   

BX

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

BX

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

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

U BX



BX BX 

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



 BBN X

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





BX

X

BX

.











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

 Y U B Y /



 Y U B Y /

 X   

,



 BBN X  

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

,B D A

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

(

)

BX





POS D B

 

X U D

/



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

20

(

)

v U

POS D B



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

 u B



 v B





(

)



. Nói cách khác,

  u

POS D B

D

 ta đều có    u U u  

  u D v D 

B

.

Ví dụ 1.1. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân

cho ở Bảng 1.1.

Bảng 1.1. Bảng thông tin về bệnh cúm

Đau đầu Thân nhiệt Cảm cúm U

Bình thường Không Có u1

Có Cao Có u2

Có Rất cao Có u3

Không Bình thường Không u4

Không Cao Không u5

Không Rất cao Có u6

Không Cao Có u7

,

,

,

,

,

/U

Không Rất cao Không u8

  ,

u u u u u , 6 8

5

7

4

  u u u 1 2 3

 

,

,

/U

Ta có: {Đau đầu} =

  ,

  ,

4

u u u , 5

2

7

u u u , 3 6 8

  u u , 1

 

,

,

,

,

/U

{Thân nhiệt} =

  ,

5

u u u u , 3

6

2

7

  u u u u , 1 4 8

 

,

/U

{Cảm cúm} =

  ,

  ,

u u , 2 3

u u u , 5 8

4

u u , 6

7

    u , 1

 

{Đau đầu, Cảm cúm} =

,u u 2 3

Như vậy, các bệnh nhân không phân biệt được về đau đầu và cảm

cúm, nhưng phân biệt được về thân nhiệt.

u

u

,

,

,

Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là:

  ,



         u u , 1 3

4

2

u u , 5

7

u u , 6 8

u u

,

,

{X 

.



 u u u u , 3

6

2

7

Đặt (Cảm cúm) = Có} = . Khi đó:

21

BX

BX

,

,

,

,

.











 u u , 2 3

u u u u u u , 5 8

2

3

6

7

,

,

và Như vậy, B-miền biên của X là

  



 BBN X

u u u u , 5 6 8

7

U D /

X

,

,

;

X

,

,

,

BX

BX











tập hợp . Nếu đặt D = {Cảm cúm} thì











1

u u u u , 1 4 8

5

2

u u u u , 3

2

6

7

1

 u u , 1

4

2

 u u , 2 3



 

(

)

BX

,

,



; ,



  



POS D B

u u u u , 1 2

3

4



X U D

/



/U B

.

Với các khái niệm của tập xấp xỉ đối với phân hoạch , các tập thô

BX U

BX  

được chia thành bốn lớp cơ bản:

BX U

BX  

1) Tập X là B-xác định thô nếu và .

BX U

BX  

2) Tập X là B-không xác định trong nếu và .

BX U

BX  

3) Tập X là B-không xác định ngoài nếu và .

4) Tập X là B-không xác định hoàn toàn nếu và .

1.1.3. Bảng quyết định đầy đủ

DS

DCU (

,

)





C D  

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à

DS

DCU (

,

)





u U d D ,    

với .

  d u

u U

c C

Xét bảng quyết định với giả thiết ,

  c u

đầy đủ giá trị, nếu tồn tại và sao cho thiếu giá trị thì DS

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

  D u

  D v

  C v

kéo theo tức là với mọi được gọi là nhất quán nếu D phụ thuộc hàm vào C,   . Ngược lại thì gọi là u v U C u



C

không nhất quán hay mâu thuẫn. Theo định nghĩa miền dương, bảng quyết  . Trong trường hợp bảng không định là nhất quán khi và chỉ khi POS D U





POS D C

C

D

nhất quán thì chính là tập con cực đại của U sao cho phụ thuộc hàm

đúng.

22

1.1.4. Tập rút gọn và tập lõi

DCU (

DS

)

,





c C

Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba nhóm: thuộc tính lõi (core attribute), thuộc tính rút gọn (reductive attribute) và thuộc tính dư thừa (redundant attribute). Thuộc tính lõi là thuộc tính không thể thiếu trong việc phân lớp chính xác tập dữ liệu. Thuộc tính lõi xuất hiện trong tất cả các tập rút gọn của bảng quyết định. Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ chúng không ảnh hưởng đến việc phân lớp tập dữ liệu, thuộc tính dư thừa không xuất hiện trong bất kỳ tập rút gọn nào của bảng quyết định. Thuộc tính rút gọn là thuộc tính xuất hiện trong một tập rút gọn nào đó của bảng quyết định.

D



Định nghĩa 1.1. [31] (Tập lõi dựa trên miền dương) Cho bảng quyết được gọi là không cần thiết . Thuộc tính định

 POS D POS





C

)

(

C c 

  

(dispensable) trong DS dựa trên miền dương nếu ;

PCORE C

Ngược lại, c được gọi là cần thiết (indispensable). Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên miền dương và được ký hiệu là





. Khi đó, thuộc tính cần thiết chính là thuộc tính lõi.

DS

DCU (

,

)

R C





Định nghĩa 1.2. [31] (Tập rút gọn dựa trên miền dương) Cho bảng quyết

(

)

(

)

POS D POS D 

định và tập thuộc tính . Nếu

C

R

r R POS ,

(

D POS D

)

(

)

 



1)

C

  R r 

2)

PRED C

thì R là một tập rút gọn của C dựa trên miền dương.



PCORE C

R

là họ tất cả các tập rút gọn Pawlak của C. Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu 





 

R PRED C







Khi đó .

23

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

,



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

 IS U A



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

a U :

a A

a A

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

V a

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

u U a A ,





.

B

,...,

A





Với mọi , ta ký hiệu giá trị thuộc tính a tại đối tượng u là

  a u



 b b 2, 1

b k

Nếu là một tập con các thuộc tính thì ta ký hiệu bộ

 B u

  ib u





i

1,...,

k



các giá trị bởi . Như vậy, nếu u và v là hai đối tượng, thì ta viết

  B u

  B v

  b u i

  b v i

,

u U

a A



nếu với mọi .

 IS U A



  a u

Với 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à

 IIS U A 



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

,

U

,

,

A

,

}





Ví dụ 1.2. Bảng 1.2 biểu diễn thông tin về các xe hơi là hệ thông tin không

 IIS U A 



u u u u u u , { , 1 3

, } 6

4

5

2

a a a a , { , 1 2 4

3

đầy đủ với , với a1 (Đơn giá),

a2 (Km đã đi), a3 (Kích thước), a4 (Tốc độ tối đa).

24

Bảng 1.2. Bảng thông tin về các xe hơi

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

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

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

* * Gọn nhẹ Cao u3

Cao * Trung bình Cao u4

* * Trung bình Cao u5

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

P

,

A

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

 IIS U A 



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:

 SIM P



  u v U U a P a u



  a v

  a u

  a v

 

 '*'

.

 SIM P



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

 SIM P



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

 SIM P



a P 

   SIM a



,





U. Theo [18], .

  u

  u



 SIM P

PS

PS

  v U u v

 

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, còn gọi

/U SIM P

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

25

/U SIM P







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

u U PS



U vì chúng có thể giao nhau và .





Ví dụ 1.3. Từ hệ thông tin đầy đủ cho ở ví dụ 1.2 Ta tính:

AS u (

1

u ) { } 1

AS u (

2

u u ) { , } 2

6

AS u (

3

u ) { } 3

AS u (

4

u u ) { , } 4 5





, , ,

AS u (

5

) { , 4

u u u 5

, } 6

AS u (

6

) { , 2

u u u 5

, } 6

U SIM A

(

/

),

),

),

),

),

)}

) { 

, .

S u ( 1 A

S u ( A

2

S u ( A 3

S u ( A

4

S u ( 5 A

S u ( A

6

,

,

    u , ,

  ,

  ,

    u , 1

uu , 2

6

3

uu , 4

5

uuu , 5

4

6

uuu , 5

2

6 

P



Ta có =





a a , 3 4

)

)

,





Với ta tính :

S u ( 1 P

S u ( P

2

) { , u u u  1 2

, }, 6

S u ( 3 P

) { }, u  3

S u ( P

4

S u ( 5 P

) { , u u u  4 5

, } 6

PS u (

6

) { , u u u u u ,  1 4

, } 6

5

2

U SIM P

(

/

),

),

),

),

),

)}

) { 

,

S u ( 1 P

S u ( P

2

S u ( P 3

S u ( P

4

S u ( 5 P

S u ( P

6

,

,

,

,

,

,

,

,

,

,

  ,

    u , ,

  ,

  ,

  uuu 2 1

6

uuu 2 1

6

3

uuu , 5

4

6

uuu , 5

4

6

uuuuu 4 1

2

5

6 

Ta có =

COVER U

COVER U

P

A

Ta ký hiệu tập tất cả các phủ của U sinh bởi các tập con thuộc tính









,

là . Trên ta định nghĩa một quan hệ thứ tự bộ

 COVER U 







,

,P Q A

phận như sau.

 IIS U A 



Định nghĩa 1.3. [24] Cho hệ thông tin không đầy đủ với .

/U SIM P

/U SIM Q

Ta nói:









/

/

S

 



1) Phủ và phủ là như nhau (viết

  u U S u ,

  u

 U SIM P U SIM Q 







P

Q

/U SIM P

/U SIM P



U SIM P

/

U SIM Q

/

) khi và chỉ khi .

















u U S

,

S

 



2) mịn hơn (viết ) khi

  u

  u

P

Q

và chỉ khi .

26

,

 COVER U 







S

S

u u U

,





Trên , phần tử nhỏ nhất gọi là phủ rời rạc

  u

    u 

A

A





S

S







và phần tử lớn nhất gọi là phủ một khối

  u

  u U u U ,

A

A





,

.

 IIS U A 



S

S



 u U

P Q A  

Tính chất 1.1. [24] Cho hệ thông tin không đầy đủ

  u

  u

P

Q

/

/

P Q A  

1) Nếu thì với .

  U SIM Q U SIM P







S

S

S





 u U

,P Q A

2) Nếu thì .

  u

  u

  u

P

Q

P Q 

3) Nếu thì với .

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à

PX

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

PX

X

X





  u

  u

P

P

 u U S  



 u X S  





PX

X

S



  u

  u u U

P

P





 u U S  

    

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

,

U PX



PX PX 

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



 PBN X

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



 PBN X  

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

,P D A

là tập thô (rough set) dựa trên quan hệ dung sai.

(

)

PX





POS D P

 

X U D

/



v

(

)



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

  S u P

POS D P

(

)



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

  u

  u D v D





POS D P

P

   u U S u  



D

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

27

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.

P



Ví dụ 1.4. Từ hệ thông tin không đầy đủ cho ở ví dụ 1.2





a a , 3 4

U SIM P

(

/

),

),

),

),

),

)}

) { 

Với ta có

S u ( 1 P

S u ( P

2

S u ( 3 P

S u ( P

4

S u ( 5 P

S u ( P

6

)

)

,





, với

S u ( 1 P

S u ( P

2

) { , u u u  1 2

, }, 6

S u ( 3 P

) { }, u  3

S u ( P

4

S u ( P 5

) { , u u u  4 5

, } 6

PS u (

6

) { , u u u u u ,  1 4

, } 6

5

2

PX



X



,



 u u , 1

2

u u u u , { , 1 2

, } 6

4

PX

,

,

,



Xét tập đối tượng , khi đó và



 u u u u u , 1 4

2

5

6

.

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

DS U C D ,





C D  

đượ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à





DS U C D ,





u U d D ,    

với .





  d u

u U

c C

Xét bảng quyết định với giả thiết ,

  c u

đầy đủ giá trị, 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

 IDS U C D



d D

, '*'

 



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

V d

với . Không mất tính chất tổng quát, giả thiết D chỉ gồm một

 d

,

P



A

u U

thuộc tính quyết định duy nhất .

  d

 IDS U A 



u ( )







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

P

   d v v

 S u ( ) P

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

28

|

( ) | 1 

u U

A u

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

P

A

không nhất quán.

 d

POS

/ { }}

|

{  

PX X U d 

Theo khái niệm miền dương, với miền dương của đối với P là

  d ) (

P

POS

U

) 

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

  d (

B

,



.

  d

 IDS U A 



Ví dụ 1.5. Xét bảng quyết định không đầy đủ cho ở Bảng

U

,

,



1.3 được xây dựng từ hệ thông tin không đầy đủ ở Ví dụ 1.2 bằng cách thêm

u u u u u u { , , 1 3

, } 6

2

4

5

A

,

}



vào thuộc tính quyết định d (Gia tốc), với ,

a a a a , { , 1 2 4

3

.

Bảng 1.3. Bảng quyết định về các xe hơi

Km đã Kích Ô tô Đơn giá Tốc độ Gia tốc đi thướ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

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

{

X X X

,

,

}

X

X

X









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

  U d /

1

2

3

1

u u u u , { , 1 2

, }, 6

4

2

u { }, 3

3

u { } 5

AX

,

AX

,

AX





Ta có với .



   

1

 u u , 1

2

2

  u 3

3

POS



Các tập xấp xỉ dưới đối với A là .

  d (

A

u u u ) { , , } 1 2 3

Do đó, .

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

29

)

)

)

)









A u 1(

A u 2(

A u 3(

A u 4(

)

)





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

A u 5(

A u 6(

nhanh}, {Nhanh, Rất nhanh}, {Nhanh, Rất nhanh}.

Do đó, IDS là bảng quyết định không nhất quán.

1.3. Các khái niệm về tập rút gọn của bảng quyết định không đầy đủ

Trong mấy năm gần đây, một số phương pháp rút gọn thuộc tính trong

bảng quyết định không đầy đủ đã được đề xuất theo hướng tiếp cận mô hình tập

thô dung sai của Kryszkiewicz [18]. Tương tự như các phương pháp rút gọn

thuộc tính theo tiếp cận lý thuyết tập thô truyền thống, mỗi phương pháp đều đưa

ra khái niệm về tập rút gọn dựa trên một độ đo được chọn và xây dựng thuật toán

heuristic tìm một tập rút gọn tốt nhất dựa trên tiêu chuẩn là chất lượng phân lớp

của tập rút gọn hay độ hỗ trợ của tập luật dựa trên tập rút gọn. Trong mục này,

luận án trình bày một số khái niệm về tập rút gọn của các phương pháp rút gọn

thuộc tính đã công bố làm cơ sở cho việc nghiên cứu mối liên hệ giữa các tập rút

gọn ở Chương 2.

1.3.1. Tập rút gọn dựa trên hàm quyết định suy rộng

Sau khi đề xuất mô hình tập thô dung sai, Kryszkiewicz [18] đưa ra khái

niệm về tập rút gọn của bảng quyết định không đầy đủ, là tập con tối thiểu của

tập thuộc tính điều kiện mà bảo toàn hàm quyết định suy rộng của tất cả các

,



đối tượng.

  d

 IDS U A 



R

A

Định nghĩa 1.4. [18] Cho bảng quyết định không đầy đủ . Nếu



 

u U

thỏa mãn:

  u

  u

A

R



 

R

u U

' R

'

(1) với mọi

  u

  u

A

R

(2) , tồn tại sao cho

thì R được gọi là một tập rút gọn của IDS dựa trên hàm quyết định suy rộng.

30

1.3.2. Tập rút gọn dựa trên miền dương

Dựa trên ý tưởng mở rộng khái niệm tập rút gọn của Pawlak trong lý

thuyết tập thô truyền thống, Zuqiang Meng và các cộng sự [56] đưa ra khái

,



niệm về tập rút gọn dựa trên miền dương.

  d

 IDS U A 



R

A

Định nghĩa 1.5. [56] Cho bảng quyết định không đầy đủ . Nếu

POS

POS



thỏa mãn:

  d

  d

R

A









R

' R

POS

POS



'

(1)

  d

  d

A









R

(2) ,

thì R được gọi là một tập rút gọn của IDS dựa trên miền dương.

1.3.3. Tập rút gọn dựa trên độ đo lượng thông tin

Theo tiếp cận tính toán hạt (granular computing), Huang B và các cộng

B

B

A

sự [16] đưa ra khái niệm về tập rút gọn dựa trên lượng thông tin (information

n

S

U

,...,

u









quantity). Với , lượng thông tin của đối với {d} là

 I B









  d

 I B



B

u i

 u u , 1

2

n

 I B



   I B d



1    1 2 U  1 i

,



với và .

  d

 IDS U A 



R

A

Định nghĩa 1.6. [16] Cho bảng quyết định không đầy đủ . Nếu

;

  1



thỏa mãn:

'

.

   I R d ' R  



  2

     R I R d ,

   I A d 

   I A d



.

thì R được gọi là một tập rút gọn của IDS dựa trên lượng thông tin.

1.3.4. Tập rút gọn dựa trên ma trận phân biệt

Theo hướng tiếp cận mở rộng khái niệm ma trận phân biệt trong lý

thuyết tập thô truyền thống, trong công trình [17] Huasheng ZOU và các cộng

31

sự đưa ra khái niệm tập rút gọn dựa trên ma trận phân biệt. Ma trận phân biệt

i jm

 M m   i j

 

n n 

(discernibility matrix) của IDS là , các phần tử được xác định

)

a u (

)

)

a u (

)



  

  



 





a a A a u ( , i

j

a u ( i

j

j

u i

A



m i j

 

 





j

u i

A

 d u  d u

 

    

,



như sau:

  d

 IDS U A 



R C

Định nghĩa 1.7. [17] Cho bảng quyết định không đầy đủ và

 M m   i j

 

n n 

R m

 

ma trận phân biệt . Nếu thỏa mãn:

i j

i jm  

R

r R

(1) với mọi

  r

(2) Với mọi , không thỏa mãn (1)

thì R được gọi là một tập rút gọn của IDS dựa trên ma trận phân biệt.

1.3.5. Tập rút gọn dựa trên ma trận dung sai

Cũng theo hướng tiếp cận mở rộng ma trận phân biệt, công trình [19]

đưa ra khái niệm tập rút gọn dựa trên ma trận dung sai. Ma trận dung sai

i jm

 TM m   i j

 

n n 

(tolerance matrix) của IDS là , các phần tử được xác định

)

a u (

)

)

a u (

)



  

  







a a A a u ( , i

j

a u ( i

j

 d u i

j



m i j

 





 d u i

j

 d u  d u

 

    

,



như sau:

  d

 IDS U A 



R C

Định nghĩa 1.8. Cho bảng quyết định không đầy đủ và ma

 TM m   i j

 

n n 

R m

 

trận dung sai . Nếu thỏa mãn:

i j

i jm  

R

r R

(1) với mọi

  r

(2) Với mọi , không thỏa mãn (1)

thì R được gọi là một tập rút gọn của IDS dựa trên ma trận dung sai.

32

1.3.6. Tập rút gọn dựa trên hàm phân bố, hàm ấn định

Trong các công trình [29], [31], các tác giả đưa ra khái niệm tập rút gọn

dựa trên hàm phân bố, gọi tắt là tập rút gọn phân bố (distribution reduct), tập

rút gọn dựa trên hàm ấn định, gọi tắt là tập rút gọn ấn định (assignment

,



reduct).

  d

 IDS U A 



U

U d /



R C

 

Định nghĩa 1.9. [29], [31] Cho bảng quyết định không đầy đủ ,



   Y  1

Y ,..., m

iu U

 u 1,..., U u



Y





j

R

Y



j

1,...,

m

,...,





, , . Với , đặt:

















R j

u i

 R

u i

Y 1

u i

R Y m

u i





S

S 

 u i 

R u i

R

S













 R

u i

j

R

u i

 Y Y : j

  

với , .









 R

u i

 A

u i

i

1,...,

U



P

'P  

u

u

(1) R được gọi là một tập rút gọn phân bố của IDS nếu

ju U

 R

j

 A

j









với và , tồn tại sao cho .









 R

u i

 A

u i

i

1,...,

U



P

'P  

u

u

(1) R được gọi là một tập rút gọn ấn định của IDS nếu với

ju U

 R

j

 A

j









và , tồn tại sao cho .

,



1.3.7. Tập rút gọn dựa trên metric

  d

 IDS U A 

/

/

,P Q A





hệ thông tin không đầy đủ . Theo hướng tiếp cận metric công trình [2] đưa ra khái niệm metric. trên 

 K P U SIM P K Q U SIM Q ,















Với , giả sử tương ứng là hai

,

:



phủ sinh bởi hai tập thuộc tính P và Q. Khi đó với mọi

 K P K Q COVER U 



















 Ed COVER U COVER U

 0,  

, ánh xạ xác định

,







  Ed K P K Q

 IE P Q IE Q P 











COVER U

bởi





là một metric trên tập .

33

,



  d

 IDS U A 



R C

Định nghĩa 1.10. [2] Cho bảng quyết định không đầy đủ và

.



  1













E

E





,

,

D

.

 











  2

   r

  r

 d K C K C D ,







E

 





 d K R K R D ,   r R d K R E

  d K C K C D ,       K R

metric Nếu thỏa mãn:

thì R được gọi là một tập rút gọn của IDS dựa trên metric.

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

Chương 1 đã trình bày tổng quan một số khái niệm cơ bản trong mô hình

tập thô dung sai do Kryszkiewicz [18] đề xuất và một số khái niệm cơ bản về

tập rút gọn và tập lõi [56] trong hệ thông tin không đầy đủ và bảng quyết định

không đầy đủ. Khái niệm tập rút gọn và tập lõi của bảng quyết định không

đầy đủ được mở rộng từ khái niệm tập lõi và tập rút gọn dựa trên miền dương

trong lý thuyết tập thô truyền thống của Pawlak và tổng kết một số khái niệm

về tập rút gọn của các phương pháp rút gọn thuộc tính đã công bố. Các khái

niệm này được sử dụng trong chương 2 và chương 3 của luận án.

34

CHƯƠNG 2. ĐỀ XUẤT PHÂN NHÓM VÀ ĐÁNH GIÁ CÁC

PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT

ĐỊNH KHÔNG ĐẦY ĐỦ

2.1. Mở đầu

Mục tiêu của rút gọn thuộc tính trong bảng quyết định là tìm tập con nhỏ

nhất của tập thuộc tính điều kiện mà bảo toàn thông tin phân lớp của bảng quyết

định. Dựa vào tập rút gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao

nhất. Rút gọn thuộc tính trong bảng quyết định đầy đủ theo tiếp cận mô hình tập

thô truyền thống của Pawlak [31] là chủ đề nghiên cứu sôi động trong nhiều năm

qua. Trên bảng quyết định không đầy đủ, dựa trên mô hình tập thô dung sai của

Kryszkiewicz [18], nhiều phương pháp heuristic rút gọn thuộc tính đã được đề

xuất trong mấy năm gần đây [15], [16], [17], [20], [27], [29], [37], [55], [56].

Giống như cách tiếp cận tập thô truyền thống của Pawlak, các phương pháp này

đều thực hiện các bước chính như sau:

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

2) Đưa ra khái niệm độ 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). 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). Dựa vào

nhận xét tập lõi xuất hiện trong mọi tập rút gọn nên các thuật toán xây dựng

theo hướng tiếp cận bottom-up được chia thành hai nhóm: các thuật toán tính

35

toán lõi và các thuật toán không tính toán lõi. Ý tưởng chung của các thuật

toán tính toán lõi là xuất phát từ tập lõi, bổ sung dần dần các thuộc tính có độ

quan trọng lớn nhất vào tập lõi cho đến khi thu được tập rút gọn. Các thuật

toán không tính toán lõi xuất phát từ tập rỗng và bổ sung dần các thuộc tính

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 top-down xuất phát từ tập thuộc tính

điều kiện ban đầu, loại bỏ dần 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ự giảm dần hoặc tăng dần của độ quan trọng

tại mỗi bước lặp.

Trên cơ sở tổng kết các kết quả đã công bố về các phương pháp rút gọn

thuộc tính trong bảng quyết định không đầy đủ, chương này trình bày các kết

quả nghiên cứu sau đây:

1) Phân nhóm 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 vào nghiên cứu mối liên hệ giữa các khái

niệm tập rút gọn.

2) Đánh giá các phương pháp rút gọn thuộc tính dựa vào nghiên cứu sự

thay đổi các độ đo đánh giá hiệu năng tập luật quyết định trên các

khái niệm tập rút gọn.

2.2. Đề xuất phân nhóm các phương pháp rút gọn thuộc tính

Phần này trình bày kết quả phân nhóm các phương pháp rút gọn thuộc

tính và mối quan hệ giữa các tập rút gọn của các nhóm phương pháp dựa vào

nghiên cứu mối liên hệ giữa các khái niệm tập rút gọn. Tiêu chí phân nhóm là:

các phương pháp có khái niệm tập rút gọn dựa vào độ đo như nhau được phân

thành một nhóm.

36

Vì kết quả của một phương pháp rút gọn thuộc tính chính là tập rút gọn

nên kết quả phân nhóm này có ý nghĩa rất quan trọng, là cơ sở để so sánh,

đánh giá các phương pháp được trình bày ở phần sau.

Các kết quả trong phần này đã được tác giả công bố trong công trình

[CT1] .

2.2.1 Bảng ký hiệu các tập rút gọn của bảng quyết định không đầy đủ

Để trình bày kết quả nghiên cứu về mối liên hệ giữa các khái niệm tập

rút gọn, chúng tôi ký hiệu các khái niệm tập rút gọn đã mô tả ở chương 1

trong Bảng 2.1 như sau:

Bảng 2.1. Ký hiệu các tập rút gọn trong bảng quyết định không đầy đủ.

Ký hiệu tập rút gọn Mô tả

PR

Tập rút gọn dựa trên miền dương

R

Tập rút gọn dựa trên hàm quyết định suy rộng

R

Tập rút gọn ấn định

MR

Tập rút gọn dựa trên ma trận phân biệt

DR

Tập rút gọn dựa trên metric

IR

Tập rút gọn dựa trên lượng thông tin

TMR

Tập rút gọn dựa trên ma trận dung sai

R

Tập rút gọn phân bố

Trước hết, chúng tôi tổng kết các kết quả đã công bố về mối liên hệ giữa

các khái niệm tập rút gọn trong bảng quyết định không đầy đủ.

37

1) Nếu bảng quyết định nhất quán, các tác giả trong [37], [56] đã chỉ ra

PR

R R R

, , , có khái niệm tập rút gọn dựa trên độ đo là như nhau.

2) Nếu bảng quyết định không nhất quán, Renpu Li và cộng sự [37] đã

R

R

chứng minh , có khái niệm tập rút gọn dựa trên độ đo là như nhau.

MR

R

Huasheng ZOU và cộng sự [17] đã chứng minh , có khái niệm tập rút

gọn dựa trên độ đo là như nhau.

Tiếp theo, chúng tôi tiếp tục nghiên cứu các mối liên hệ còn lại giữa các

tập rút gọn trong trường hợp bảng quyết định không đầy đủ nhất quán hoặc

không nhất quán.

DR

IR

TMR

,



, , 2.2.2 Mối liên hệ giữa các khái niệm tập rút gọn

  d

 IDS U A 



Cho bảng quyết định không đầy đủ . Trong mục này,

DR

IR

TMR

chúng tôi chứng minh ba khái niệm tập rút gọn , và là tương đương

R

A

,



nhau trong cả hai trường hợp IDS nhất quán và không nhất quán.

  d

 IDS U A 



,

,







Mệnh đề 2.1. Cho bảng quyết định không đầy đủ và .

  d

  d K A K A

  d

E

E

   d K R K R

















Khi đó khi và chỉ khi

   I R d



   I A d



,



.

  d

 IDS U A 



U

,...,

u



A

,

,

R 







Chứng minh. Xét bảng quyết định không đầy đủ với



  d

  d K A K A

  d

 u u , 1

2

n

E

E

   d K R K R















và . Từ ,

U

U

S

S

S

S

















R

u i

u i

A

u i

u i

d

R

d

A





  

  







1 U

U

U

1 U

i

i

1 

1 

   

   

   

   

U

U

U

U

1

1

1

1

S

1

S

1

S

1

S

























u i

R

u i

u i

A

u i

R

d

d

A





2

2

2

2

  

  









i

i

i

i

1 

1 

1 

1 

U

U

U

U

  1    

   

   

   

   

   

   

   

theo định nghĩa metric ta có:

38















Theo định nghĩa lượng thông tin ta có:

  d

 I R



  d

 I A



 I R



 I A



   I R d



   I A d



.

Mệnh đề 2.1 cho thấy khái niệm tập rút gọn dựa trên metric và tập rút

DR

gọn dựa trên lượng thông tin là tương đương nhau, hay tương đương với

R

A

,



.IR

  d

 IDS U A 



Mệnh đề 2.2. Cho bảng quyết định không đầy đủ , và

 TM m   i j

 

n n 

,

,

 







là ma trận dung sai của IDS. Khi đó

  d

  d K A K A

  d

R m i j

E

E

   d K R K R















khi và chỉ khi với mọi

i jm  

,



.

  d

 IDS U A 



U

,...,

u



R

,

,

A







Chứng minh. Xét bảng quyết định không đầy đủ với



  d

  d K A K A

  d

 u u , 1

2

n

E

E

   d K R K R















và . Từ ,

U

U

S

S

S

S

















R

u i

u i

A

u i

u i

d

R

d

A





  

  







1 U

U

U

1 U

i

i

1 

1 

   

   

   

   

S

S

S

S









theo định nghĩa metric ta có:













iu U

R

u i

u i

A

u i

u i

d

R

d

A





  

  

S

S

,

S

S





với mọi . (2.1)













u i

R

u i

u i

u i

A

d

R

d

A





  

  

S

S

S

S

 







Do nên (2.1) tương đương với:













iu U

R

u i

u i

A

u i

u i

d

R

d

A





  

  

S

S

S

S











với . (2.2)





















u i

A

R

u i

u i

A

u i

R

u i

u i

d

d

   S

   S

S

S

S

S

S

S

S

S





















































u i

A

u i

A

u i

R

u i

R

u i

u i

u i

A

u i

R

u i

u i

d

d

d

A

d

R





   S

   S

  

  

Từ

.

Do đó (2.2) tương đương với:

39

S

S

S

S

 



















iu U

R

u i

u i

A

u i

u i

d

R

d

A





  

  

 

với (2.3)

R m i j

i jm  

 

U

1) Ta chứng minh nếu (2.3) thỏa mãn thì với mọi .

jm  

u u ,i

i 0 0

R m i j 0 0

0

j 0

u



Giả sử tồn tại sao cho . Khi đó tồn tại sao

u ,i

0

j 0

j 0

 d u i 0



 d u



u

A R

cho . không phân biệt được nhau bởi các thuộc tính trong

u ,i

0

j 0

u

S

u

S





R và phân biệt được nhau bởi các thuộc tính trong , nghĩa là

A

R

j 0

u i 0

j 0

u i 0









u

S

u

S

S







và .

A

A

d

A



j 0

u i 0

j 0

u i 0

u i 0











  

u

S

u

S

S











Từ suy ra (*)

R

R

R

d

j 0

u i 0

j 0

j 0

u i 0

u i 0

u i 0





 d u i 0



 d u













   S

u

S

S





Từ và ta suy ra

R

R

d



j 0

u i 0

u i 0







  

S

S

S

S







hay . (**)













R

u i

u i

A

u i

u i

d

R

d

A





  

  

 

Từ (*) và (**) suy ra , điều này mâu thuẫn

R m i j

với (2.3). Do đó, giả sử là sai và ta kết luận nếu (2.3) thỏa mãn thì

i jm  

 

với mọi .

R m i j

i jm  

2) Ngược lại, ta cần chứng minh nếu với mọi thì (2.3)

S

S

S

S







thỏa mãn.

R

A

R

d

d

A





0iu

u i 0

u i 0

u i 0

u i 0





 







 



S

S

S

S

U







Giả sử tồn tại sao cho . Do

A

R

d

A

R

d





u i 0

u i 0

u i 0

u i 0

0ju





  







  



u

S

S

u

S

S

u

S

S













nên tồn tại sao cho

R

A

R

R

d

d

A

R

d







j 0

u i 0

u i 0

j 0

u i 0

u i 0

j 0

u i 0

u i 0





  







  







  



u

S

S

u

S









và . Từ suy ra

A

A

d

A



j 0

j 0

u i 0

u i 0

j 0

u i 0





 d u



 d u i 0







  



a R

, kết hợp với suy ra . Theo định

jm  

i 0 0

a m i j 0 0

u

S

 



nghĩa ma trận dung sai, tồn tại sao cho với mọi thì (vì

R

j 0

u i 0

R m i j 0 0





), nghĩa là . Điều đó mâu thuẫn với điều kiện

40

 

 

R m i j

i jm  

R m i j

với mọi . Do đó, giả sử là sai và ta kết luận nếu

i jm  

,

,







với mọi thì (2.3) thỏa mãn.

  d

  d K A K A

  d

E

E

   d K R K R















 

Từ 1) và 2) ta kết luận khi và

R m i j

i jm  

chỉ khi với mọi .

Mệnh đề 2.2 cho thấy khái niệm tập rút gọn dựa trên metric và tập rút

DR

gọn dựa trên ma trận dung sai là tương đương nhau, hay tương đương

TMR

DR

IR

TMR

với . Kết hợp với Mệnh đề 2.1 ta kết luận , và là tương đương

nhau

PR

R

R

A

,



2.2.3 Mối liên hệ giữa và

  d

 IDS U A 



POS

POS





 

u U

Mệnh đề 2.3. Cho bảng quyết định không đầy đủ và .

  u

  u

  d

  d

A

R

R

A









POS

POS



Nếu với mọi thì .

  d

  d

R

A









u

POS

u

POS

u

POS







Chứng minh. Giả sử , khi đó chắc chắn tồn tại

  d

  d

  d

0

A

0

R

0

A

0u U













1

1

u

u

u

POS











 



sao cho và . Từ suy ra









  d

 A u

0

 R u

0

R

0

0

A

0

R





u

u

S

u

S

u

u

u



 





 

, từ suy ra . Vì vậy, . Do

























R

0

0

A

A

0

R

0

A

0

R

0

u

u



 



 

u U

nên , kết hợp với suy ra









  u

  u

A

0

R

0

A

R



 

u U

. Điều này mâu thuẫn với điều kiện với mọi

  u

  u

R

A

POS

POS



. Do đó giả sử là sai và ta kết luận nếu với mọi thì

  d

  d

R

A









.

Chú ý: Nếu IDS không nhất quán thì chiều ngược lại của Mệnh đề 2.3

,



không thỏa mãn. Điều này được minh họa bằng Ví dụ 2.1 sau đây.

  d

 IDS U A 



U

,

,

,

,

A

,

,





Ví dụ 2.1. Xét bảng quyết định không đầy đủ với







 u u u u u 1 3 5

2

4

a a a 1 2 3

, cho ở Bảng 2.2.

41

2a

3a

1a

Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.1

1u

d U

2u

1 0 0 1

3u

1 0 1 1

4u

* 0 0 1

5u

2 2 2 *

u

u



 

 



 

2 * 0 2











  

 0,1







  

 0, 2

u 1

A

2

A

u 3

A

4

A

u 5

A

POS

R

 



Ta có , . Do đó IDS

  d





A

a a , 1 2





POS

POS

,

,



 



không nhất quán và dễ thấy rằng . Xét , dễ thấy rằng

  



  d

  d

 A u

3

u u u 1 2 3

R

A









,

,





 

. Tuy nhiên, và

  











 R u

3

u u u u , 1 2

3

4

u 3

u 3

A

R

, do đó .

R

Mệnh đề 2.3 cho thấy nếu là một tập rút gọn dựa trên hàm quyết định

PR

PR

R

POS

POS

U





u U

suy rộng thì tồn tại với là một tập rút gọn dựa trên miền dương.

  d

  d

R

A









1



 





 



 

u U

Nếu IDS nhất quán thì , nghĩa là với mọi

  u

  u

  u

  u

  u

  u

R

A

A

R

A

R

POS

POS



ta có , hay . Do đó, với mọi

  d

  d

R

A

R









khi và chỉ khi , điều này có nghĩa là tương đương

với .PR

DR

R

R

A

,



2.2.4 Mối liên hệ giữa và

  d

 IDS U A 



,

,







Mệnh đề 2.4. Cho bảng quyết định không đầy đủ và .

  d K R K R

  d

  d K A K A

  d

E

E

















u U

,

 



 

Nếu thì

  u

  u

R

A

.

42

,



  d

 IDS U A 



U

,...,

u



R

,

,

A







Chứng minh. Xét bảng quyết định không đầy đủ với



  d

  d K A K A

  d

 u u , 1

2

n

E

E

   d K R K R















và . Từ ,

S

S

S

S

 







theo phần chứng minh của Mệnh đề 2.2 (công thức (2.3)), ta có:













iu U

R

u i

u i

A

u i

u i

d

R

d

A





  

  

với (2.4)

S

S

S

S











Mặt khác





















B

u i

B

u i

u i

B

u i

B

u i

u i

d

d

   S

   S













S

S

S

S











.





















C

u i

C

u i

u i

C

u i

C

u i

u i

d

d

   S

   S













d



S

S









.















i

 d u i

B i

 d v i

v i

B

u i

B

u i

u i

d

   S





 

S

S





















C i

 d v i

v i

C

u i

C

u i

u i

d

   S





 

Giả sử , ,

S

S

S

d









































B

u i

 d v i

v i

B

u i

u i

B

u i

B

u i

u i

i

B i

d

d

   S

   S











Khi đó ta có:



   

d

S

S

S









































i

C i

C

u i

 d v i

v i

C

u i

u i

C

u i

C

u i

u i

d

d

   S

   S













   



 









u i

B

C

u i

B C i

i

iu U

Từ công thức (2.4) ta suy ra , do đó với mọi .

,

 

Chú ý: Nếu IDS không nhất quán thì chiều ngược lại của Mệnh đề 2.4









u U    i

B

u i

C

u i

S



không thỏa mãn vì điều kiện chỉ bảo toàn giá trị hàm









B

iu

B

u i

,

,







quyết định tổng quát của lớp dung sai , còn điều kiện

  d

  d

E

E

   d K R K R



   d K A K A











S

bảo toàn các đối tượng không





B

u i

iu

nhất quán đối với của lớp dung sai (điều kiện này chặt hơn). Điều

này được minh họa bằng Ví dụ 2.2 sau đây.

43

,



  d

 IDS U A 



U

,

,

,

,

A

,

,





Ví dụ 2.2. Xét bảng quyết định không đầy đủ với







 u u u u u 1 3 5

4

2

a a a 1 2 3

, cho ở Bảng 2.3

1a

3a

2a

Bảng 2.3. Bảng quyết định minh họa Ví dụ 2.2

1u

U d

2u

1 0 1 *

3u

1 0 0 1

4u

1 0 0 *

5u

* 2 0 2

S

S

u

S

,

,





2 * 1 2











  



u 1

A

A

2

A

u 3

u u u 1 2 3

S

u

S

u

u





 

 

 

 

Từ Bảng 2.3 ta có: ,







  





















  

 0,1

A

4

A

u 5

u u , 4 5

A

u 1

2

A

u 3

A

4

A

u 5

A

R

S

S

,

,





, . Do đó







  







u 1

R

R

u 3

u u u u , 1 2

3

4

a a , 1 2

u

,

,

u

,

,

IDS không nhất quán. Xét ta có ,



  





  





  



RS

2

u u u 1 2 3

RS

4

u u u u , 1 3 5

4

RS

u 5

u u , 4 5

u

u

1..5



 

 

 

 

 



, , ,



















  

 0,1

R

u 1

R

2

R

u 3

R

4

R

u 5

iu U i ,



 

. Vì vậy với ,









R

u i

u i

A

U

)

S

)



S u ( A i

u ( i

A



  d

,









  d K A K A

  d



 2 1 1 1 1    

E











1 U

U

1 4.4

6 16

i

1 

U

)

S

)



S u ( R i

u ( i

R



  d

,









. Mặt khác

  d



 3 1 1 2 1    

E

   d K R K R









1 U

U

1 4.4

8 16

i

1 

,

,







.

  d

  d K A K A

  d

E

E

   d K R K R















Do đó, .

DR

Mệnh đề 2.4 cho thấy nếu là một tập rút gọn dựa trên metric thì tồn

R D

R  

R

tại với là một tập rút gọn dựa trên hàm quyết định suy rộng.

44

,

1



 











u U   i

R

u i

u i

A

S

S

S

S





Nếu IDS nhất quán, từ điều kiện suy ra













iu U

R

u i

u i

u i

A

u i

d

R

d

A





  

  

và với mọi . Theo định nghĩa metric

,

,

0









ta có:

  d K R K R

  d

  d K A K A

  d

E

E

















,

,







.

  d K R K R

  d

  d K A K A

  d

E

E

















,

 

Vì vậy, khi và chỉ khi









u U    i

R

u i

u i

A

DR

R

, điều này có nghĩa là tương đương với .

R

R

R

A

,



2.2.5 Mối liên hệ giữa và

  d

 IDS U A 



u U

,

 



 

u U

,

 



Mệnh đề 2.5. Cho bảng quyết định không đầy đủ và .

  u

  u

  u

  u

R

A

 R

 A

,



Nếu thì .

  d

 IDS U A 



U

,...,

u

u

u





 

R

A

Chứng minh. Xét bảng quyết định không đầy đủ với











R

0

0

A

 u u , 1

2

n

0u U

d

u

d

u

d

/

,

 

 



và . Giả sử tồn tại sao cho . Khi









0

R

0

0

A

0

0

  Y Y U d  0

0

d

u

S

u

d

u

S

u

 



 

 



 

đó tồn tại sao cho , với . Do

















0

A

0

Y 0

A

0

0

R

0

Y 0

R

0

S

u

S

u



nên . Mặt khác, nên . Từ









Y 0

A

0

Y   0

R

0













Y 0

0

Y 0

0



đó ta có , nghĩa là:

R u

S

A u

S

S 

u 

S 

u 

0

R

0

A

u

u

u

u



,

















R Y 0

0

A Y 0

0

 R

0

 A

0

u U

,

 



theo định nghĩa hàm phân bố ta có , từ đó .

  u

  u

 R

 A

u U

,

 



 

u U

,

 



Điều này mâu thuẫn với điều kiện . Do đó giả sử là sai

  u

  u

  u

  u

R

A

 R

 A

và ta kết luận nếu thì . 

,

 

Chú ý: Nếu IDS không nhất quán thì chiều ngược lại của Mệnh đề 2.5









u U    i

B

u i

C

u i

S



không thỏa mãn vì điều kiện chỉ bảo toàn giá trị hàm









B

iu

B

u i

quyết định tổng quát của lớp dung sai , còn điều kiện

45

,











u U   i

 R

u i

 A

u i

iu

bảo toàn hàm phân bố của đối tượng (điều kiện này

1..5



 

 



chặt hơn). Điều này được minh họa bằng Ví dụ 2.3 sau đây.









R

u i

u i

A

iu U i ,

U d /

,

,





Ví dụ 2.3. Tiếp tục Ví dụ 2.2, ta có , . Giả sử

   







1u U

Y Y , 1 2

Y 1

 u u , 1 5

Y 2

 u u u , 3

2

4

R

A









với . Xét đối tượng .

















 R u

1

Y 1

 R u Y , 1 2

u 1

 A u

1

Y 1

 A u Y , 1 2

u 1









1 3 , 4 4

1 2 , 3 3

   

  

   

  









 R

u 1

 A

u 1

, .Do đó,

R

Mệnh đề 2.5 cho thấy nếu là một tập rút gọn phân bố thì tồn tại

R

R  

R

,

1

d



 





với là một tập rút gọn dựa trên hàm quyết định suy rộng.











u U   i

B

u i

C

u i

i

 d u i

d

/

,



Nếu IDS nhất quán thì . Giả sử với

i

  Y Y U d  i

i

S

S













Y i

R

Y i

A

R

A

1

1













. Khi đó:









Y i

u i

Y i

u i

S

S

S

S

S 

u i 

 

 

S 

u i 

 

 

R u i

R

R

u i u i

A u i

A

A

u i u i

j

i

,

j

1,...,

m

,





và (2.5)









 R

u i

 A

u i

iu

Y

Y









j

j

Y

0

Y

0













Với , các phần tử trong hàm phân bố của









R j

u i

A j

u i

S

S

S

S

S 

 u i 

 



S 

 u i 

 



R u i

R

R

u i

A u i

A

A

u i

 

và (2.6)









iu U

 R

u i

 A

u i



 

u U 

Từ công thức (2.5), (2.6) ta có với . Vì vậy ta kết

  u

  u

  u

  u

R

A

 R

 A

luận khi và chỉ khi với , điều này có

R

R

nghĩa là tương đương với .

2.2.6 Đề xuất phân nhóm các phương pháp rút gọn thuộc tính

Từ các công bố và các kết quả nghiên cứu đã trình bày ở trên, chúng tôi

tổng kết mối liên hệ giữa các khái niệm tập rút gọn của bảng quyết định

không đầy đủ như sau:

46

PR

MR

DR

IR

Nếu bảng quyết định nhất quán, các tập rút gọn , , , , , , R R

TMR

R

, có khái niệm tập rút gọn dựa trên độ đo là như nhau.

Từ những mối quan hệ giữa các khái niệm tập rút gọn của các tác giả và các

mối quan hệ đã trình bày trên ta có nhận xét là nếu bảng quyết định không nhất

, RRR

,

D

I

TM





,

,  MRRR



PR



R

quán, mối liên hệ giữa các tập rút gọn được biểu diễn bằng sơ đồ sau:

Hình 1.1 Mối quan hệ giữa các tập rút gọn

Sơ đồ trên cho thấy các tập rút gọn trong bảng không nhất quán được chia

thành bốn nhóm:

1) Nhóm 1: Bao gồm tập rút gọn .PR

MR

2) Nhóm 2: Bao gồm các tập rút gọn , . , R R

DR

IR

TMR

3) Nhóm 3: Bao gồm các tập rút gọn , , .

4) Nhóm 4: Bao gồm tập rút gọn .R

Mối liên hệ giữa các tập rút gọn trong các nhóm như sau:

3R

2R

là một tập rút gọn thuộc Nhóm 3 thì tồn tại một tập rút gọn  Nếu

1R





thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho

R 1

R 2

R 3

.

47

4R

2R

là một tập rút gọn thuộc Nhóm 4 thì tồn tại một tập rút gọn  Nếu

1R





thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho

R 1

R 2

R 4

.

Như vậy, tập rút gọn của Nhóm 1 có số thuộc tính nhỏ nhất, sau đó đến

Nhóm 2 và Nhóm 3, Nhóm 4.

Dựa vào kết quả phân nhóm các tập rút gọn, các phương pháp rút gọn

thuộc tính trong bảng quyết định không đầy đủ cũng được phân thành bốn

nhóm tương ứng.

Đế đánh giá tính hiệu quả của một phương pháp rút gọn thuộc tính, cộng

đồng nghiên cứu về tập thô sử dụng hai tiêu chuẩn: 1) độ phức tạp về thời

gian thực hiện thuật toán heuristic tìm một tập rút gọn tốt nhất và 2) chất

lượng phân lớp của tập rút gọn. Các công bố về rút gọn thuộc tính đều tính

toán độ phức tạp thời gian thuật toán tìm tập rút gọn. Do đó, hoàn toàn có thể

so sánh được tính hiệu quả của các phương pháp về tiêu chuẩn thời gian. Vì

vậy, luận án tập trung nghiên cứu việc đánh giá các phương pháp dựa trên tiêu

chuẩn về độ hỗ trợ của tập luật.

Việc đánh giá khả năng phân lớp của tập rút gọn dựa vào số lượng thuộc

tính của tập rút gọn và khả năng phân lớp của từng thuộc tính. Về mặt định

tính, tập rút gọn có số thuộc tính càng ít thì khả năng phân lớp càng cao. Tuy

nhiên, điều này chưa hẳn đã chính xác vì khả năng phân lớp của từng thuộc

tính khác nhau. Tóm lại, ta cần phải sử dụng độ đo mang tính định lượng để

đánh giá khả năng phân lớp của tập rút gọn. Trong lý thuyết tập thô, các nhà

nghiên cứu sử dụng ba độ đo để đánh giá tính đúng đắn và tính hiệu quả của

một phương pháp rút gọn thuộc tính: độ chắc chắn (certainty measure), độ

nhất quán (consistency measure) và độ hỗ trợ (support measure), cụ thể là:

tập rút gọn của phương pháp rút gọn thuộc tính phải bảo toàn độ chính xác, độ

48

nhất quán của tập luật quyết định. Độ hỗ trợ sử dụng để đánh giá khả năng

phân lớp của tập rút gọn. Độ hỗ trợ của tập luật quyết định dựa trên tập rút

gọn càng cao thì khả năng phân lớp của tập rút gọn đó càng cao.

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

Trong phần này, trước hết luận án sẽ tổng kết các kết quả nghiên cứu

liên quan đến luật quyết định và các độ đo đánh giá hiệu năng tập luật trong

bảng quyết định không đầy đủ. Tiếp theo, luận án sẽ phân tích nhược điểm

các độ đo đánh giá hiệu năng tập luật của Yuhua Qian và các cộng sự trong

công trình [33], trên cơ sở đó luận án đề xuất các độ đo mới và nghiên cứu sự

thay đổi giá trị các độ đo đề xuất trên các tập rút gọn nhằm đánh giá các

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

Các kết quả trong phần này đã được tác giả công bố trong công trình

[CT2]. (Danh mục các công trình của tác giả).

U



,



2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng



  d

 u 1,...,

u n

 IDS U A 



U SIM A

/

,...,

,...,

U SIM A

/







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







 }

  U d /







 S u { A 1

 S u A n

Y Y { , 1 2

Y }m

 S u A i

/



sử và . Với ,





  jY U d

 S u A i

Y   j

A

  des S u i



 des Y

j

và , ký hiệu và lần lượt là các mô



 S u A i

jY

tả của lớp dung sai và lớp tương đương . Chú ý rằng nếu giá trị





A

i a u  

  des S u i





thì bỏ giá trị này ra khỏi vì quy ước giá trị * bằng tất cả



:ij

A

j

  Z des S u i



 des Y



các giá trị khác. Một luật quyết định đơn có dạng

[33].

Giống như luật quyết định trong bảng quyết định đầy đủ, độ chắc chắn,

ijZ

Z

Y

/









ij

 S u A i

j

 S u A i

 



độ hỗ trợ và độ bao phủ của luật quyết định đơn tương ứng là:

49

Y U /







ij

 S u A i

j

 s Z



Z

Y

/

Y







ij

 S u A i

j

j

 



,



  d

 IDS U A 



U

,

,

,

,

,

,



A 

Ví dụ 2.4. Xét bảng quyết định không đầy đủ mô tả về các



 aaaa , 1 2

3

4

 u u u u u u , 1 3 6

4

2

5

1a

tivi cho ở Bảng 2.4 với , với (Đơn

2a

3a

4a

giá), (Màu sắc), (Tính năng), (Độ phân giải).

Bảng 2.4. Bảng quyết định không đầy đủ về các tivi

Chất Tivi Đơn giá Màu sắc Tính năng Độ phân giải lượng(d)

Tốt Cao Đen Đầy đủ Thấp u1

Tốt Thấp * Đầy đủ Thấp u2

Xấu * * Thiếu Thấp u3

Tốt Cao * Đầy đủ Cao u4

* * Đầy đủ Cao Tuyệt hảo u5

U SIM A

(

/

),

),

),

),

),

)}

) { 

Thấp Nâu Đầy đủ * Tốt u6

S u ( A 1

S u ( A

2

S u ( 3 A

S u ( A

4

S u ( A 5

S u ( A

6







Ta có , với

AS u (

1

u ) { } 1

AS u (

2

u u ) { , } 2

6

AS u (

3

u ) { } 3

AS u (

4

u u ) { , } 4 5

AS u (

5

) { , 4

u u u 5

, } 6

U d /

,





u

u

, , , , ,

   



Y Y Y , 1 2 3

AS u (

6

) { , 2

u u u 5

, } 6

Y 1

u u u u , { , , } 1 2 6

4

Y 2

3{ }

Y 3

5{ }

. với , , .

Các luật quyết định là:

11 :Z

(a1, Cao)  (a2, Đen)  (a3, Đầy đủ)  (a4, Thấp)  (d, Tốt)

21 :Z

(a1, Thấp)  (a3, Đầy đủ)  (a4, Thấp)  (d, Tốt)

50

32 :Z

(a3, Thiếu)  (a4, Thấp)  (d, Xấu)

41 :Z

(a1, Cao)  (a3, Đầy đủ)  (a4, Cao)  (d, Tốt)

43 :Z

(a1, Cao)  (a3, Đầy đủ)  (a4, Cao)  (d, Tuyệt hảo)

51 :Z

(a3, Đầy đủ)  (a4, Cao)  (d, Tốt)

53 :Z

(a3, Đầy đủ)  (a4, Cao)  (d, Tuyệt hảo)

61 :Z

(a1, Thấp)  (a2, Nâu)  (a3, Đầy đủ)  (d, Tốt)

63 :Z

(a1, Thấp)  (a2, Nâu)  (a3, Đầy đủ)  (d, Tuyệt hảo)

Z

:

Z

1,

1 / 6,

Z

1 / 4







Các độ đo của các luật quyết định đơn là:

 



 s Z



 



11

11

11

11

Z

:

Z

1,

1 / 3,

Z

1 / 2







,

 



 s Z



 



21

21

21

21

Z

:

Z

1,

1 / 6,

Z

1







,

 



 s Z



 



32

32

32

32

Z

:

Z

1 / 2,

1 / 6,

Z

1 / 4







,

 



 s Z



 



41

41

41

41

Z

:

Z

1 / 2,

1 / 6,

Z

1







,

 



 s Z



 



43

43

43

43

Z

:

Z

2 / 3,

1 / 3,

Z

1 / 2







,

 



 s Z



 



51

51

51

51

Z

:

Z

1 / 3,

1 / 6,

Z

1







,

 



 s Z



 



53

53

53

53

Z

:

Z

2 / 3,

1 / 3,

Z

1 / 2







,

 



 s Z



 



61

61

61

61

Z

:

Z

1 / 3,

1 / 6,

Z

1







,

 



 s Z



 



63

63

63

63

.

F U d

/



Các độ đo này chỉ sử dụng để đánh giá các luật quyết định đơn, không

   



Y Y , 1 2

Y ,..., m

phù hợp cho việc đánh giá tập luật quyết định. Giả sử

51

là một phân lớp của U theo d, độ chính xác của phân lớp F theo A, ký hiệu là



 A F

AY i



  Y U d /

i

F







 A

AY i



  Y U d /

i

 

, được Pawlak [45] định nghĩa:



 A F

Trong một số trường hợp, được dùng để đo độ chắc chắn của

bảng quyết định. Tuy nhiên, nhược điểm của độ đo này được minh họa trong

ví dụ sau:

U SIM a

/

,

,

,

,

,

,

,

,

,

,

,

,

  (





 }

2

 ) { u u u u u U U U U u u u u u ,  1 6

2

5

3

5

4

3

2

4

U SIM a a

/

,

,

,

,

,

,

,

,

,

,

 (

  ,

  ,

  ,

  ,

  ,

 }

2

4

u u u u , 1 2 6

3

u u u u , 1 2 6

3

u u u , 4 5 6

u u u , 4 5 6

u u u u u , 2 4 6

3

5

/



Y U d i

0







 a

    U d /

2

0 6 6 6  

/



Y U d i

  ) { u u u , ,  1 2 3     a Y 2 i     a Y 2 i

/



Y U d i

0







Ví dụ 2.5. Xét bảng quyết định ở Ví dụ 2.4, ta có:

    U d /



  a a , 2

4

0 6 4 3  

 a a Y , 2 4 i  a a Y , 2 4 i

/



   

Y U d i

 

.



 a

 ,a a 2

4

    U d /

    U d /

2



  a a 4, 2

Vì vậy, . Tuy nhiên, phủ sinh bởi mịn

 2a

hơn phủ sinh bởi . Do đó, độ chắc chắn phân lớp nêu trên không phù hợp

để đánh giá độ chắc chắn của bảng quyết định, hay tập luật quyết định

Trong bảng quyết định không đầy đủ, nghiên cứu đáng chú ý về độ đo

đánh giá hiệu năng phải kể đến nhóm nghiên cứu của Yuhua Qian và các

cộng sự [33], trong đó các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ

hỗ trợ của tập luật trong bảng quyết định không đầy đủ dựa trên khái niệm

khối đồng nhất cực đại (consistent block). Trước hết, luận án trình bày khái

niệm khối đồng nhất cực đại trong công trình [52].

52

,



  d

 IDS U A 



Cho bảng quyết định không đầy đủ và một quan hệ

 SIM P



,

SIM



dung sai xác định trên tập thuộc tính P. Khi đó,

 | vuUv 







P 

  uS P

là tập lớn nhất các đối tượng không có khả

  u

PS

năng phân biệt được với u trên tập thuộc tính P. là lớp dung sai, còn

  u

PS

gọi là hạt tri thức (knowledge granular). là đơn vị nhỏ nhất sử dụng để

  u

PS

mô tả tri thức và lực lượng của là đơn vị tính toán cơ sở cho các

phương pháp rút gọn thuộc tính [52]. Theo định nghĩa, các đối tượng trong

  u

PS

lớp dung sai có quan hệ dung sai với đối tượng u, tuy nhiên các đối

  u

PS

,



tượng trong có thể không quan hệ dung sai với nhau. Xét bảng quyết

uuu , 5

4

6

AS u (

5

) { , 4

u u u 5

, } 6

định trong Ví dụ 2.4, ta có , theo định nghĩa quan

4u

5u

6u

hệ dung sai với , tuy nhiên và không quan hệ dung sai với nhau. Do

đó, trong công trình [52], các tác giả nêu quan điểm rằng các lớp dung sai

  u

PS

chưa phải là đơn vị nhỏ nhất để mô tả tri thức và đưa ra khái niệm

khối đồng nhất cực đại (Maximal consistent block). Về bản chất, khối đồng

  u

PS

nhất cực đại của đối tượng u là tập con của lớp dung sai , trong đó tất

cả các đối tượng có quan hệ dung sai với nhau. Khối đồng nhất cực đại được

,

P



A

định nghĩa như sau.

  d

 IDS U A 



UX 

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

SIM

(

P

)

Xvu ,

vu  ,

, ta nói rằng X là đồng nhất (consistent) trên tập thuộc tính P nếu với

Y

UY 

X 

mọi ta có (nghĩa là u và v quan hệ dung sai với nhau).

Nếu không tồn tại một tập con sao cho và X là đồng nhất trên

tập thuộc tính P thì X được gọi là khối đồng nhất cực đại trên tập thuộc tính

PMC

P. Ký hiệu là tập tất cả các khối đồng nhất cực đại trên tập thuộc tính P

 uMC P

và là khối đồng nhất cực đại chứa đối tượng u. Với bảng quyết định

đã cho ở Ví dụ 2.4, các khối đồng nhất cực đại là

53

    u , ,

  ,

MC A

    u , 1

uu , 2

6

3

uu , 4

5

uu , 5

6 

SIMU /

A

,

,



, trong khi đó các lớp dung sai của các đối





    u , ,

  ,

  ,

    u , 1

uu , 2

6

3

uu , 4

5

uuu , 5

4

6

uuu , 5

2

6 

tượng là . Hiển nhiên,

các khối đồng nhất cực đại cũng tạo ra một phủ của U chứ không phải một

phân hoạch của U, nghĩa là các khối cực đại có thể giao nhau.

Trở lại với độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật trong

công bố của Yuhua Qian và các cộng sự [33], các độ đo này được định nghĩa

,

U

,....,



dựa trên các khối đồng nhất cực đại như sau:

  d

 u 1

nu

 IDS U A 



RULE

|

Z

:

des

X





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





 Z

 Ydes

ij

ij

i

j 

X

/

,

..1

, jn

..1

m







và tập luật với

  idUYMC , 

AMC

i

A

j

. là họ các khối đồng nhất cực đại trên



tập thuộc tính A.

m

iN

X

Y



i

j

IDS

 



  

1 m

1 N

X

i

j

1 

1 

i

i

Độ chắc chắn của IDS được định nghĩa [33]



.

m

iN

IDS

X

Y

Z

Z









 



i

j

ij

ij

 



 



 1







1 m

4 X

i

j

1 

1 

i

 1  

  



Độ nhất quán của IDS được định nghĩa [33]

jN

n

Y

X

Y



k

j

IDS







 



U

j

k

1 

1 

j N U i

Độ hỗ trợ của IDS được định nghĩa [33]

Từ các công thức trên ta thấy rằng độ chắc chắn, độ nhất quán, độ hỗ trợ được định nghĩa qua các khối đồng nhất cực đại. Trong khi đó, các phương pháp rút gọn thuộc tính trong các nhóm phương pháp được trình bày ở phần 1.1 đều sử dụng các độ đo được định nghĩa qua lực lượng của các lớp dung sai, ví dụ phương pháp sử dụng độ đo lượng thông tin (information quantity)

54

n

1

1 

[16], độ đo lượng thông tin được định nghĩa qua lực lượng của lớp dung sai

 BI





 B uS

i

Uui 

 B uS

i

2



i

1 

U

X 

của đối tượng , . Do đó, Yuhua Qian và

AMC

AMC

X

S

 

các cộng sự [33] chưa đánh giá sự thay đổi giá trị độ chắc chắn, độ nhất quán, độ hỗ trợ trên các tập rút gọn của của các phương pháp rút gọn thuộc tính, do đó các độ đo này gặp khó khăn trong việc đánh giá tính hiệu quả (về khả năng phân lớp hay độ hỗ trợ của tập luật) của các phương pháp rút gọn thuộc tính. Hơn nữa, vì các độ đo này được tính qua các khối đồng nhất cực đại nên việc nghiên cứu sự thay đổi các độ đo này trên các tập rút gọn ta cần chuyển đổi các độ đo này sang đơn vị tính toán cơ sở là lực lượng các lớp dung sai. Hướng nghiên cứu này hoàn toàn có thể thực hiện được vì công trình [52] cho phép tính toán lớp dung sai dựa trên khối đồng nhất cực đại. Theo [52], nếu khi và chỉ khi là tập tất cả các khối đồng nhất cực đại và

Xu 

 uA

. Tuy nhiên, việc chuyển đổi các công thức độ chắc chắn, độ nhất

quán, độ hỗ trợ trong [33] tính toán qua các lớp dung sai khá phức tạp vì bản thân các công thức độ chắc chắn, độ nhất quán, độ hỗ trợ cũng đã phức tạp và việc chuyển đổi sang lớp dung sai lại càng phức tạp. Do đó, luận án chuyển sang hướng nghiên cứu là định nghĩa lại độ chắc chắn, độ nhất quán, độ hỗ trợ qua các lớp dung sai. Việc định nghĩa các độ đo mới, độ chắc chắn, độ nhất quán, độ hỗ trợ, qua các lớp dung sai dựa trên ý tưởng mở rộng độ chắc chắn, độ nhất quán, độ hỗ trợ trên bảng quyết định đầy đủ trong luận án tiến sĩ [2].

2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định

Trên cơ sở mở rộng các kết quả nghiên cứu trong luận án tiến sĩ [2], luận

án đề xuất ba độ đo mới đánh giá hiệu năng tập luật quyết định: độ chắc chắn,

độ nhất quán và độ hỗ trợ. Các độ đo này được tính bằng trung bình cộng của

tất cả các luật quyết định đơn và được tính dựa trên lực lượng các lớp dung

sai. Từ đó, luận án đánh giá sự thay đổi các độ đo đề xuất trên các tập rút gọn

nhằm so sánh, đánh giá tính hiệu quả của các phương pháp rút gọn thuộc tính.

55

,

U







  d

 u 1,...,

u n

 IDS U A 



RULE

:





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



A

ij

j





 des Y



  Z Z des S u ij i



/

/

1..

n j ,

1..

m









tập luật với



   U SIM A Y U d i , ,



 S u A i

j



.

n

iN

Y

j

IDS

Độ chắc chắn của IDS được định nghĩa

 



1    N

1 n

j

i

1 

1 

 

i

  S u A i  S u A i



.

n

iN

Y

j

IDS





 



n

1

1   N

n

1

1 

1 

j

i

1 

1 

 

i

  S u A i  S u A i



Độ nhất quán của IDS được định nghĩa

S

Y





A

j

IDS







1 n m   n

 u i n

i

j

1 

1 

Độ hỗ trợ của IDS được định nghĩa

iN

Ký hiệu là số luật quyết định (số lớp quyết định) sinh bởi lớp dung



 S u A i

sai .

 IDS



 ijZ

 1 

RULE

1 / n



Dễ thấy rằng, đạt giá trị lớn nhất là 1 nếu với mọi

 IDS



ijZ

m U

U

n

, nghĩa là IDS nhất quán, và đạt giá trị nhỏ nhất là nếu



 IDS



 S u A i

iN

iu U

, nghĩa là và với mọi . Tương tự, đạt

 IDS



 IDS



1 / n

giá trị lớn nhất là 1 khi đạt giá trị lớn nhất là 1 và đạt giá trị

 IDS



 IDS



1 / n

U

nhỏ nhất là 0 khi đạt giá trị nhỏ nhất là . đạt giá trị lớn



 IDS



 S u A i

iu U

S

nhất là 1 nếu với mọi . đạt giá trị nhỏ nhất là nếu



A

u i

   u i

iu U

với mọi . Mệnh đề 2.6 sau đây chứng minh một số tính

chất quan trọng của các độ đo đánh giá hiệu năng.

56

,



 IDS U A 

   d

'

IDS





RULE

:





Mệnh đề 2.6. Cho hai bảng quyết định không đầy đủ ,



A

ij

ij

j





 U B ,

   d

 des Y



  Z Z des S u i



IDS

IDS

B

i

n 1..

j

A



/

/

m 1..





và với



   U SIM A Y U d ,



 



 S u A i

j

 

'

IDS

IDS

IDS

IDS





, , . Nếu thì ,

 







 

'



'

,





Chứng minh.

 iN A

 iN B

B

S

A



1) Giả sử , tương ứng là số luật quyết định sinh bởi lớp











 S u A i

 S u B i

 S u A i

B

u i







dung sai , . Theo [24], nếu thì với mọi

 N A i

 N B i

iu U



n

n

n

Y

j

IDS



, suy ra . Từ đó ta có:

 



 iN A 





1   n

1 n

1 n

i

j

i

i

1 

1 

1 

1 







 

1  N A i

1  N A i

1  N B i

  S u A i  S u A i



n

Y

j

IDS

IDS

= =

 



 IDS

'

 

'



 iN B 

1 n

i

j

1 

1 



 

1  N B i

  S u B i  S u B i

IDS

IDS



= . Do đó .

 







 N A i

 N B i

 

'

|

) |

) |

)

)



|  

 

 

Dấu đẳng thức khi và chỉ khi . Theo định

u ( i

A

u ( i

B

u ( i

A

u ( i

B

nghĩa hàm quyết định suy rộng ta có với mọi

iu U

IDS

IDS

.

 



 

'

IDS

IDS

)

)



 

2) Chứng minh tương tự như phần 1) ta có . Dấu đẳng

 



u ( i

A

u ( i

B

iu U

 

'

B

S

A



thức khi và chỉ khi với mọi .







 S u A i

B

u i

iu U

S

S

Y

/





S

S

Y





3) Nếu thì với , suy ra

















  jY U d

iu U

A

u i

Y   j

B

u i

j

A

u i

Y   j

B

u i

j

n m

n m

S

Y

S

Y









A

j

B

j

IDS

IDS













với ,







'





1 n

 u i n

1 n

 u i n

i

j

i

j

1 

1 

1 

1 

IDS

IDS

S

S







. Dấu đẳng thức













u i

A

B

u i



'

khi và chỉ khi .

57

2.3.3. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn

Trước hết, luận án tổng kết lại kết quả phân nhóm các tập rút gọn được

trình bày ở mục 2.2.6.

Nhóm 1: Tập rút gọn miền dương .PR

Nhóm 2: Bao gồm tập rút gọn dựa trên hàm quyết định suy rộng ( ), R

MR

R

tập rút gọn ấn định ( ), tập rút gọn dựa trên ma trận phân biệt ( ). Luận

R

án chọn tập rút gọn dựa trên hàm quyết định suy rộng làm đại diện.

IR

Nhóm 3: Bao gồm tập rút gọn dựa trên lượng thông tin ( ), tập rút

TMR

DR

gọn dựa trên ma trận dung sai ( ), tập rút gọn dựa trên khoảng cách ( ),

DR

luận án chọn tập rút gọn dựa trên khoảng cách làm đại diện.

Nhóm 4: Tập rút gọn phân bố .R

Trong mục này, chúng tôi nghiên cứu sự thay đổi của độ chắc chắn

 IDS



 IDS



 IDS



, độ nhất quán và độ hỗ trợ dựa trên bốn tập rút gọn

,



của bốn nhóm phương pháp nêu trên.

  d

 IDS U A 



'

IDS





Mệnh đề 2.7. Cho hai bảng quyết định không đầy đủ và

  d

 U B ,



.

PR

'

'

'

IDS

IDS

1

IDS

IDS

1

IDS

IDS









a) Nếu IDS nhất quán và B là một tập rút gọn miền dương ( ) thì

 



 







 



 







, ,

PR

'

'

'

IDS

IDS

IDS

IDS

IDS

IDS





b) Nếu IDS không nhất quán và B là một tập rút gọn miền dương ( ) thì

 



 







 



 







, ,

58

Chứng minh

IDS

,

IDS

|

) |



|  

) | 1 

a) Nếu IDS nhất quán và B là một tập rút gọn miền dương thì

 



 



u ( i

A

u ( i

B

'

'

IDS

IDS

1

IDS

IDS

1





. Từ công thức tính dễ dàng suy ra

 



 



 



 



'DS

DS





, . Hơn nữa, theo Mệnh đề 2.6 ta có









.

PR

Như vậy, tập rút gọn miền dương ( ) bảo toàn độ chắc chắn bằng 1, độ

nhất quán bằng 1 và tăng độ hỗ trợ của tập luật đối với bảng quyết định

'

IDS

IDS

không đầy đủ nhất quán.

 



 



'

'

IDS

IDS

IDS

IDS





b) Nếu IDS không nhất quán: từ Mệnh đề 2.6 ta có ,

 







 







, .

PR

Như vậy, tập rút gọn miền dương ( ) làm giảm độ chắc chắn, giảm độ

nhất quán và tăng độ hỗ trợ của tập luật đối với bảng quyết định không đầy

,



đủ không nhất quán.

  d

 IDS U A 



'

IDS





Mệnh đề 2.8. Cho hai bảng quyết định không đầy đủ và

  d

 U B ,



'

'

'

IDS

IDS

IDS

IDS

IDS

IDS





. Nếu B là một tập rút gọn dựa trên hàm quyết định suy

 



 







R

 



 







rộng ( ) thì , ,

B

Chứng minh

)

)



 

Nếu là một tập rút gọn dựa trên hàm quyết định suy rộng thì

u ( i

A

u ( i

B

iu U

'

'

IDS

IDS

IDS

IDS

với mọi , theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta

 



 



 



 



'

IDS

IDS





có , . Cũng theo Mệnh đề 2.6 ta có









.

R

Như vậy, tập rút gọn dựa trên hàm quyết định suy rộng ( ) bảo toàn độ

chắc chắn, bảo toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định.

59

,



  d

 IDS U A 



'

IDS





Mệnh đề 2.9. Cho hai bảng quyết định không đầy đủ và

  d

DR

 U B ,



'

'

'

IDS

IDS

IDS

IDS

IDS

IDS





. Nếu B là một tập rút gọn dựa trên khoảng cách ( ) thì

 



 







 



 







, ,

B

Chứng minh

DR

,

,







Nếu là một tập rút gọn dựa trên khoảng cách ( ) thì

  d

  d K A K A

  d

E

E

   d K B K B















)

)



 

, theo kết quả nghiên cứu mối liên

u ( i

A

u ( i

B

iu U

'

IDS

IDS

hệ giữa các tập rút gọn đã trình bày ở trên ta có với mọi ,

 



 



'

'

IDS

IDS





IDS

IDS

theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta có ,





 







 



. Cũng theo Mệnh đề 2.6 ta có .

DR

R

Giống như tập rút gọn , tập rút gọn bảo toàn độ chắc chắn, bảo

toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. Theo kết quả

nghiên cứu về mối liên hệ giữa các tập rút gọn đã trình bày ở trên, mỗi tập

DR

R D

R

R  

rút gọn đều tồn tại một tập rút gọn sao cho . Theo Mệnh đề

DR

2.6, độ hỗ trợ của tập luật dựa trên tập rút gọn sẽ nhỏ hơn độ hỗ trợ của

R

tập luật dựa trên tập rút gọn . Nghĩa là, chất lượng phân lớp của tập rút

DR

R

,



gọn tốt hơn tập rút gọn .

  d

 IDS U A 



'

IDS





Mệnh đề 2.10. Cho hai bảng quyết định không đầy đủ và

  d

R

 U B ,



'

'

'

IDS

IDS

IDS

IDS

IDS

IDS





. Nếu B là một tập rút gọn phân bố ( ) thì

 



 







 



 







, ,

B

Chứng minh









 R

u i

 A

u i

iu U

R

Nếu là một tập rút gọn phân bố ( ) thì với mọi ,

theo kết quả nghiên cứu mối liên hệ giữa tập rút gọn phân bố và tập rút gọn

60

)

)



 

u ( i

A

u ( i

B

'

IDS

IDS

dựa trên hàm quyết định suy rộng trong [18] ta có với mọi

 



iu U

 



'

'

IDS

IDS





IDS

IDS

, theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta có ,





 







 



. Cũng theo Mệnh đề 2.6 ta có .

R

R

Giống như tập rút gọn , tập rút gọn bảo toàn độ chắc chắn, bảo

toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. Theo kết quả

nghiên cứu về mối liên hệ giữa các tập rút gọn đã trình bày ở trên, mỗi tập

R

R

R  

R

rút gọn đều tồn tại một tập rút gọn sao cho . Theo Mệnh đề 2.6,

R

độ hỗ trợ của tập luật dựa trên tập rút gọn sẽ nhỏ hơn độ hỗ trợ của tập

R

luật dựa trên tập rút gọn . Nghĩa là, chất lượng phân lớp của tập rút gọn

R

R

tốt hơn tập rút gọn .

2.3.4. Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn

Từ kết quả nghiên cứu về lý thuyết của mục 2.3.3 ta có:

PR

- Tập rút gọn miền dương thuộc Nhóm 1 ( ) làm giảm độ chắc chắn

 IDS



 IDS



, độ nhất quán ; tập rút gọn dựa trên hàm quyết định suy rộng

DR

R

thuộc Nhóm 2 ( ), tập rút gọn dựa trên khoảng cách ( ) thuộc Nhóm 3, tập

 IDS



R

rút gọn phân bố ( ) thuộc Nhóm 4 bảo toàn độ chắc chắn , độ nhất

 IDS



quán .

 IDS



PR

DR

R

R

- Các tập rút gọn , , và đều tăng độ hỗ trợ .

PR

R

R

- Tập rút gọn có độ hỗ trợ cao hơn . Tập rút gọn có độ hỗ trợ

DR

R

cao hơn và (tập rút gọn có độ hỗ trợ càng cao thì số luật sinh ra càng

ít).

61

Trong mục này, luận án trình bày thử nghiệm các kết quả nghiên cứu lý

 IDS



 IDS



thuyết nêu trên về sự thay đổi độ chắc chắn , độ nhất quán và

 IDS



độ hỗ trợ trên một số bộ số liệu từ kho dữ liệu UCI.

Để tiến hành thử nghiệm, luận án thực hiện các công việc sau:

1) Cài đặt các thuật toán sau bằng ngôn ngữ C# tìm một tập rút gọn của

 IDS



bảng quyết định. Với mỗi thuật toán, tính độ chắc chắn , độ

 IDS



 IDS



nhất quán và độ hỗ trợ trên bảng quyết định với tập

rút gọn thu được bằng công thức đề xuất trong mục 2.3.2.

PR

[56].  Thuật toán POSBAR tìm một tập rút gọn

R

[18].  Thuật toán GDBAR tìm một tập rút gọn

DR

[27].  Thuật toán MBAR tìm một tập rút gọn

R

[37].  Thuật toán DFBAR tìm một tập rút gọn

2) Trên máy tính PC với cấu hình Core i3 4150, 3 GB bộ nhớ RAM, sử

dụng hệ điều hành Windows 7, chạy thử nghiệm hai thuật toán với 6

bộ số liệu lấy từ kho dữ liệu UCI [40].

3) Dữ liệu thử nghiệm trên kho dữ liệu UCI như sau:

 Bộ số liệu Hepatitis.data với thông số:

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Life, Số đối tượng: 155, Số thuộc tính :19.

 Bộ số liệu Lung-cancer.data với thông số:

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Integer, Thiếu giá trị : Yes, Lĩnh vực : Life, Số đối tượng: 32, Số thuộc tính :56.

62

 Bộ số liệu Automobile.data với thông số:

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : N/A, Số đối tượng: 205, Số thuộc tính :26.

 Bộ số liệu Anneal.data với thông số:

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Physical, Số đối tượng: 798, Số thuộc tính :38.

 Bộ số liệu Congressional Voting Records với thông số:

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Thiếu giá trị : Yes, Lĩnh vực : Social, Số đối tượng: 435, Số thuộc tính :16.

 Bộ số liệu Credit Approval với thông số:

U

C

Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Financial, Số đối tượng: 690, Số thuộc tính :15.

R

4) Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính

điều kiện, là số thuộc tính của tập rút gọn, ,  và  tương ứng là

độ chắc chắn, độ nhất quán và độ hỗ trợ của bảng quyết định. Kết

quả thực hiện của hai thuật toán được mô tả ở Bảng 2.5 và Bảng 2.6

sau đây.

63

Bảng 2.5. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1

Thuật toán POSBAR

Thuật toán GDBAR

U

C

STT

Bộ số liệu

R

R













Hepatitis.data

155

0.909

0.819

0.598

0.909

0.819

0.504

3

3

19

1

1

Lung-cancer.data

32

1

0.814

1

0.814

4

4

56

2

1

Automobile.data

205

0.825

0.702

0.708

0.915

0.781

0.624

6

4

26

3

Anneal.data

798

0.804

0.713

0.586

0.852

0.755

0.503

7

6

38

4

1

435

15

1

0.616

15

1

0.616

16

5

1

Congressional Voting Records

Credit Approval

690

15

3

0.716

0.708

0.786

5

0.884

0.802

0.615

6

Bảng 2.6. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2

Thuật toán MBAR

Thuật toán DFBAR

U

C

STT

Bộ số liệu

R

R













Hepatitis.data

155

0.909

0.819

0.415

0.909

0.819

0.402

5

4

19

1

1

Lung-cancer.data

32

1

0.814

4

1

0.814

4

56

2

1

Automobile.data

205

0.915

0.781

0.518

0.915

0.781

0.518

8

8

26

3

Anneal.data

798

0.852

0.755

0.426

0.852

0.755

0.406

10

9

38

4

1

435

15

1

0.616

15

1

0.616

16

5

1

Congressional Voting Records

Credit Approval

690

15

7

0.884

0.802

0.487

6

0.884

0.802

0.512

6

Hình 2.1 sau đây biểu diễn sự thay đổi của độ hỗ trợ  trên 6 bộ số liệu

được chọn đối với các thuật toán: Thuật toán POSBAR, Thuật toán GDBAR,

Thuật toán MBAR, Thuật toán DFBAR.

64

Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn

Từ Bảng 2.5, Bảng 2.6 và Hình 2.1 cho thấy, kết quả thử nghiệm trên 6

bộ dữ liệu phù hợp với kết quả nghiên cứu về lý thuyết ở mục 2.3.3, cụ thể

như sau:

 Trên các bộ số liệu nhất quán Lung-cancer.data, Congressional Voting

Records.data, độ chắc chắn , độ nhất quán  và độ hỗ trợ  không thay đổi

trên cả 4 tập rút gọn thu được bởi 4 thuật toán (vì tập rút gọn thu được là như

nhau).

 Trên các bộ số liệu còn lại, độ hỗ trợ của thuật toán POSBAR lớn nhất,

tiếp theo đến thuật toán GDBAR và hai thuật toán MBAR và DFBAR.

 Độ chắc chắn , độ nhất quán  không thay đổi đối với ba thuật toán

GDBAR, MBAR, DFBAR. Tuy nhiên, độ chắc chắn , độ nhất quán  giảm

đối với thuật toán POSBAR đối với các bộ dữ liệu không nhất quán.

Như vậy, có thể kết luận thuật toán GDBAR thuộc nhóm phương pháp 2

hiệu quả nhất (bảo toàn độ chắc chắn, độ nhất quán và có độ hỗ trợ cao nhất).

65

2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính

1) Lựa chọn nhóm phương pháp phù hợp

Mục tiêu rút gọn thuộc tính trong bảng quyết định là tìm tập con nhỏ

nhất của tập thuộc tính điều kiện mà bảo toàn khả năng phân lớp của bảng

quyết định. Theo tiếp cận độ đo, rút gọn thuộc tính là tìm tập con nhỏ nhất

 IDS



của tập thuộc tính điều kiện mà bảo toàn độ chắc chắn của tập luật

quyết định. Từ các kết quả đã trình bày ở mục 3.2 luận án rút ra kết luận.

PR

DR

R

R

1) Tập rút gọn , tập rút gọn , tập rút gọn và tập rút gọn đều

bảo toàn độ chắc chắn của tập luật đối với bảng quyết định không đầy đủ nhất

quán. Do đó, tất cả các phương pháp rút gọn thuộc tính đã trình bày ở bài báo

này đều phù hợp với các bảng quyết định không đầy đủ nhất quán.

PR

2) Tập rút gọn làm giảm độ chắc chắc của tập luật đối với bảng

quyết định không đầy đủ không nhất quán, do đó phương pháp miền dương

thuộc Nhóm 1 không phù hợp với các bảng quyết định không đầy đủ không

nhất quán.

DR

R

R

3) Tập rút gọn , tập rút gọn và tập rút gọn đều bảo toàn độ

chắc chắn của tập luật đối với bảng quyết định không đầy đủ không nhất quán.

Do đó, các phương pháp trong Nhóm 2, Nhóm 3, Nhóm 4 đều phù hợp với các

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

2) Đánh giá các phương pháp

Sau khi đưa ra khái niệm tập rút gọn, các phương pháp rút gọn thuộc

tính đều 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 dựa

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

thuộc tính. Với bảng quyết định không đầy đủ nhất quán, các tập rút gọn tốt

nhất của bốn nhóm phương pháp là như nhau nên chúng có khả năng phân

66

lớp như nhau. Với bảng quyết định không nhất quán, chúng tôi đánh giá ba

nhóm phương pháp phù hợp (Nhóm 2, Nhóm 3, Nhóm 4) dựa trên tiêu chuẩn

R

khả năng phân lớp tập rút gọn của nhóm phương pháp.

esDB t

R

Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc

esDB t

Nhóm 3 ( tìm được bởi thuật toán heuristic sử dụng khoảng cách, lượng

thông tin hay ma trận dung sai). Theo kết quả nghiên cứu về mỗi liên hệ giữa

R

R

các tập rút gọn đã trình bày, tồn tại một tập rút gọn dựa trên hàm quyết định

esDB t

esDB t

R

R  

R

suy rộng sao cho ( tối thiểu hơn ).

esB tR

Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc Nhóm

esB tR

2 ( tìm được bởi thuật toán heuristic sử dụng hàm quyết định suy rộng,

R

tập rút gọn ấn định hay ma trận phân biệt). Ta có hai trường hợp.

esB tR

DB t es

esB tR

R



R 

R   es B t

esB tR

R

- Nếu chính là ( ) thì , nghĩa là tối

esDB t

esB tR

R

thiểu hơn . Theo Mệnh đề 2.6, độ hỗ trợ của tập luật dựa trên cao

esDB t

esB tR

R

hơn độ hỗ trợ của tập luật dựa trên , hay có khả năng phân lớp tốt

esDB t

hơn .

esB tR

R

esB tR

R

esB tR

R

R

- Nếu khác thì có khả năng phân lớp tốt hơn do

esDB t

esDB t

R  

R

R

có khả năng phân lớp tốt nhất. Mặt khác, do nên tốt hơn

esDB t

esB tR

R

về khả năng phân lớp. Do đó, tốt hơn về khả năng phân lớp.

esDB t

esB tR

Do đó, trong cả hai trường hợp có khả năng phân lớp tốt hơn .

Từ đó kết luận các phương pháp thuộc Nhóm 2 hiệu quả hơn các phương pháp

thuộc Nhóm 3 theo tiêu chuẩn đánh giá khả năng phân lớp của tập rút gọn.

Tương tự như trên ta có các phương pháp thuộc Nhóm 2 hiệu quả hơn

các phương pháp thuộc Nhóm 4 theo tiêu chuẩn đánh giá khả năng phân lớp

của tập rút gọn.

67

Các phương pháp thuộc Nhóm 3 không so sánh được với các phương

DR

R

pháp thuộc Nhóm 4 do tập rút gọn và tập rút gọn không có mối quan

hệ.

2.4. Kết luận chương 2

Chương 2 luận án đã thực hiện các nội dung nghiên cứu sau:

(1) Phân nhóm các phương pháp rút gọn thuộc tính trong bảng quyết

định không đầy đủ không nhất quán dựa vào kết quả nghiên cứu mối liên hệ

giữa các khái niệm tập rút gọn, mối liên hệ giữa các tập rút gọn của các nhóm

phương pháp. Dựa trên tập rút gọn, các phương pháp được phân thành bốn

PR

nhóm: Nhóm 1 (Tập rút gọn miền dương ), Nhóm 2 (tập rút gọn dựa trên

R

R

hàm quyết định suy rộng , tập rút gọn ấn định , tập rút gọn dựa trên ma

MR

IR

trận phân biệt ), Nhóm 3 (tập rút gọn dựa trên lượng thông tin , tập rút

TMR

DR

gọn dựa trên ma trận dung sai , tập rút gọn dựa trên khoảng cách ),

R

Nhóm 4 (Tập rút gọn phân bố ). Kết quả này được công bố trong công trình

[CT1].

(2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ

chắc chắn, độ nhất quán, độ hỗ trợ). Nghiên cứu sự thay đổi giá trị các độ đo

đề xuất trên các tập rút gọn của bốn nhóm phương pháp. Trên cơ sở đó, lựa

chọn và đánh giá các phương pháp rút gọn thuộc tính dựa trên tiêu chuẩn độ hỗ

trợ của tập luật. Kết quả này được công bố trong công trình [CT2].

Chương 3 luận án trình bày hai phương pháp mới: Phương pháp rút gọn

thuộc tính sử dụng lượng thông tin mở rộng và phương pháp rút gọn thuộc tính

sử dụng hàm quan hệ.

68

CHƯƠNG 3. ĐỀ XUẤT CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC

TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ

3.1. Mở đầu

Tiền xử lý dữ liệu là nhiệm vụ quan trọng trong quá trình khai phá dữ liệu

và học máy với mục tiêu xây dựng mẫu dữ liệu đầu vào cho các mô hình khai

phá dữ liệu từ các kho dữ liệu tác nghiệp. Tiền xử lý dữ liệu bao gồm các

bước như trích chọn và làm sạch dữ liệu, rời rạc hóa dữ liệu, rút gọn dữ liệu,

rút gọn thuộc tính. Trong đó, rút gọn dữ liệu và rút gọn thuộc tính là hai bài

toán quan trọng nhất. Trên các bảng quyết định có dung lượng dữ liệu lớn,

thời gian thực hiện các thuật toán rút gọn thuộc tính lớn do phải thực hiện các

công thức tính toán trên tất cả dữ liệu. Do đó, việc nghiên cứu các phương

pháp rút gọn dữ liệu trước khi thực hiện các phương pháp rút gọn thuộc tính

là yêu cầu cấp thiết.

Trong chương này, trước hết luận án giải quyết bài toán rút gọn dữ liệu

bằng đề xuất phương pháp chọn tập đối tượng đại diện. Sau đó, luận án đề

xuất hai phương pháp mới rút gọn thuộc tính trong bảng quyết định không

đầy đủ: Phương pháp sử dụng lượng thông tin mở rộng và phương pháp sử

dụng hàm quan hệ. Luận án chứng minh rằng phương pháp sử dụng lượng

thông tin mở rộng thuộc Nhóm 2 và phương pháp sử dụng hàm quan hệ cũng

thuộc Nhóm 2 (theo phân nhóm phương pháp đã trình bày ở Chương 2).

3.2. Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính

Trong phần này, luận án sử dụng phương pháp chọn tập đối tượng đại

diện để thu gọn đối tượng trước khi thực hiện bài toán rút gọn thuộc tính

trong hệ thông tin không đầy đủ và bảng quyết định không đầy đủ. Các kết

quả trong phần này đã được tác giả công bố trong công trình [CT3].

69

3.2.1. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ

Chọn tập đối tượng đại diện thực chất là bước tiền xử lý dữ liệu trước khi

thực hiện các thuật toán tìm tập rút gọn. Thay vì tìm tập rút gọn trên toàn bộ tập

đối tượng ban đầu, ta tìm tập rút gọn trên tập đối tượng đại diện và chứng minh

bằng lý thuyết tập rút gọn thu được từ tập đối tượng đại diện tương đương với

tập rút gọn thu được từ tập đối tượng ban đầu. Vì kích cỡ tập đối tượng đại diện

nhỏ hơn nhiều so với kích cỡ tập dữ liệu ban đầu nên thời gian thực hiện thuật

toán tìm tập rút gọn trên tập đối tượng đại diện giảm thiểu đáng kể. Tập đối

tượng đại diện bao gồm các đối tượng đại diện, mỗi đối tượng đại diện được

,

lựa chọn như sau:

 IIS U A 



,u v U

Xét hệ thông tin không đầy đủ , trước hết ta tìm các lớp dung



Aa 

sai trên tập đối tượng U ban đầu. Hai đối tượng thuộc cùng một lớp

a

a

    u S

    v S

tương đương nếu với mọi . Với mỗi lớp tương đương,

ta chọn ra một đối tượng đại diện cho lớp tương đương đó, không mất tính

chất tổng quát, ta chọn đối tượng đầu tiên làm đại diện. Khi đó, tập các đối

tượng được chọn là tập đại diện.

Thuật toán chọn tập đối tượng đại diện của hệ thông tin không đầy đủ

được mô tả như sau:

,

Thuật toán 3.1. Chọn tập đối tượng đại diện của hệ thông tin không đầy đủ.

 IIS U A 



U

A

,...,



Đầu vào: Hệ thông tin không đầy đủ ban đầu với



 a 1

ma

 u 1,...,

u n

IIS

U



,

AU  ,

P

P

U P 

Đầu ra: Hệ thông tin không đầy đủ đại diện với

là một tập đối tượng đại diện.

Bước 1: Đặt ;PU

70

iA

..1

m



, 



u U 

 

ai

U a / i

a i

    u



v U S

 



Bước 2: Với mỗi , Tính với

    u

a i

a i

   u

a i

.



     v S

/ AU





... 



Uu

  u

  u

/ A 

A

a

a

   u

  u



a 1

m

  i u

m  i 1 

X

,...,

/ AU

,...,

i

k 1..







Bước 3: Tính với .

 X

1

kX

i



 u i 1

u i l

U

U

i

k 1..





Giả sử và với .

/ AUX i  ,

:P 

P

 1 u i

IIS



Bước 4: Với mọi , , đặt ;

AU  ,

P

P

Bước 5: Return ;

,

Chứng minh thuật toán 3.1

 IIS U A 



IIS



Cho hệ thông tin không đầy đủ ban đầu và hệ thông tin

AU  ,

P

P

,

không đầy đủ đại diện , trước hết ta chứng minh bổ đề sau:



A





B 

Bổ đề 3.1. Nếu là một đối tượng đại diện được chọn trên





 uS B

p

 uS B

p

pu U  uS A

p

 IIS U A  p

 uS A

IIS



u U

sao cho với thì ta cũng có trên

AU  ,

P

P

p

p

,

X

[ u





với .



 uS A

p

] Ap

u

[







Chứng minh. Trên , giả sử , khi đó với mọi





 Y 

] Apu

  uS A

 uS A

p

 uS B

p

 uS A

p

 IIS U A  p

 uS A

y

u

y Y

y 

[

ta đều có suy ra . . Từ

 p uS 

 uS B p

 A uS

A

] Apu

IIS

u



[

Xét đối tượng bất kỳ , vì , nên với mọi , do

 y

AU  ,

S A

P

P

] Apu

 A yS

p

đó không chứa u với mọi , nghĩa là trên ,

pu

py

,

không chứa với là đối tượng đại diện của lớp tương đương chứa y trên

 IIS U A 



x

[ u

X

x X





(i).

 uS



A

 uS A

p

] Ap

u

u

[

[

Mặt khác, từ giả thiết , với thì với mọi

 xS A

] Apu

] Apu

S

y

y 



x X

[

, hay chứa u với mọi . Với đối tượng y được xét ở trên

  y

 xS

 y

 Ax

A

S A

A

] Apu

IIS

u



[

rõ ràng , giả sử với khi đó và chứa

AU  ,

P

P

] Apu

 A yS

p

pu

py

u với mọi , nghĩa là trên , chứa với là đối

71

IIS

[ u

X

y 



x X





AU  ,



 Ax

P

P

] Ap

p

X



. Với giả thiết với mọi thì trên , tượng đại diện của lớp tương đương chứa y, điều này mâu thuẫn với (i). Do đó  uS A

   u 

 uS A

p

p

p

y 

y Y



với là tập các đối tượng đại diện của các đối tượng



 Y 

 Ax

 uS A

p

p

pX  uS B

IIS

X

Y

y



x X





Y

thuộc X. Với giả thiết và kết quả chứng minh ,

AU  ,

   u 

P

P

 uS B

p

p

p

p

p

p

py

IIS



y Y

với mọi thì trên , với và

AU  ,

P

P



. Do đó ta kết luận trên ,



 uS A

 uS B

p

,  là đối tượng đại diện của p

Từ kết quả của Bổ đề 3.1, ta chứng minh rằng tập rút gọn của hệ thông

tin không đầy đủ ban đầu và tập rút gọn của hệ thông tin không đầy đủ đại

A

R 

diện là như nhau.

,

R



u U

u U

B  

Giả sử là tập rút gọn của hệ thông tin không đầy đủ ban đầu

 uS

 IIS U A 



  uS R

A



, khi đó với mọi và tồn tại sao

 uS

  uS B

A

,



u U

cho .

 uS

 IIS U A 



  uS R

A

IIS





u U

a) Từ với mọi trên dễ dàng suy ra

AU  ,



P

P

 uS R

p

 uS A

p

p

P

B

u U

R

với mọi trên .

,



b) Không mất tính tổng quát, giả sử và tồn tại sao cho

 uS

 IIS U A 



  uS B

A

u

u



trên .



 uS B

p

 uS A

p

p

IIS

,





Nếu u là đối tượng đại diện được chọn thì và trên

AU  ,



 IIS U A 



P

P

 uS B

p

 uS A

p

,

, theo Bổ đề 3.1 thì trên (i).

 IIS U A 



pu

Nếu u không phải đối tượng đại diện thì trên , giả sử là

[ Apu ]

pu

B

A

[ u

][ u

[ u

][ u

[ u

][ u

R 







đối tượng đại diện của lớp tương đương chứa u và , khi đó

] Ap

A

] Ap

A

] Bp

B

A

[ u

][ u

u





. Do nên từ ta cũng suy ra . Từ

ai 

] Ap

A

p

a

 

  i u

    a i

ta có với mọi , theo cách xây dựng trên ta có

72

u

S

S

A









 uS





 uS A

p

a

p

a

A

ai 

p

  u

   u



i

i

  S

    u S

a i

a i

m  i 1 

m  i 1 

S

u

S

u



với mọi , do đó .

  u

  u

B

p

B

p





B

 

   B

,





Từ , bằng cách tương tự ta suy ra . Theo giả thiết,

 uS



 IIS U A 



  uS B

A

 uS B

p

 uS A

p

IIS





nên ta thu được trên , theo Bổ đề 4.1

AU  ,



P

P

 uS B

p

 uS A

p



thì ta cũng có trên (ii)

p

 uS A

p

IIS

B





R

Như vậy, cả hai trường hợp (i) và (ii) ta đều có trên

AU  ,



P

P

 uS B

p

 uS B  uS A

 p

A

R 

, từ đó kết luận tồn tại sao cho . Từ a) và b)

IIS



theo định nghĩa ta có là một tập rút gọn của hệ thông tin không đầy đủ

AU  ,

P

P

,

đại diện .

 IIS U A 



,

,

,

,

,

,

,

,

A

,

}

U 



Ví dụ 3.1. Xét hệ thông tin không đầy đủ

 uuuuuuuuu 1 5

8

4

7

2

3

6

9

a a a a , { , 1 2 4

3

Với , cho ở Bảng 3.1

Bảng 3.1. Bảng thông tin về các xe hơi

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

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

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

* * Gọn nhẹ Cao u3

Cao * Trung bình Cao u4

* * Trung bình Cao u5

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

* Nhiều Gọn nhẹ * u7

Thấp Nhiều Trung bình Thấp u8

* * Gọn nhẹ Cao u9

73

,

,

,

,





  



u 1

u 4

u u u u u u , 1 4 9

5

7

3

   S

   S

a 1

a 1

U









Ta có: ,









u 3

u 5

u 7

u 9

  S

  S

  S

  S

a 1

a 1

a 1

a 1

,

,

,

,

,





,





  



u 2

u 6

u 8

u u u u u u u , 2 6 9

3

5

7

8

   S

   S

   S

a 1

a 1

a 1

,

,

,



.

 

  ,

  ,

U a / 1

u u u , 2 6 8

u u u u , 3 5 9

7

  u u , 1 4

 

/U a

U

Do đó: .

 2

U a /

,

,

,

,

,

U a /

,

,

,

,





Tính toán tương tự, ta có ,

 

  ,

 

  ,

  ,

3

5

2

6

u u u , 3 7 9

4

u u u u , 3 4 9

5

u u , 6 7

  u u u u u u , 1 4 8

 

  u u u 1 2 8

 

AU /

u

u

u

u

,

,



,

  ,

    u , 1

uu , 2

8

uu , 3

9

         7 , ,

4

6

5

,

,

,

,

,

,



Từ đó ta có .



PU

 u u u u u u u 1 4 7

2

5

3

6

IIS



Tập đối tượng đại diện được chọn là và hệ

AU  ,

P

P

thông tin không đầy đủ đại diện được chọn ở Bảng 3.1

3.2.2. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ

Từ phương pháp chọn tập đối tượng đại diện của hệ thông tin không đầy

đủ đã trình bày ở phần 3.2.1, trong mục này luận án trình bày phương pháp

chọn tập đối tượng đại diện cho bài toán tìm tập rút gọn của bảng quyết định

không đầy đủ. Luận án cũng chứng minh rằng tập rút gọn của bảng quyết định

không đầy đủ thu được từ tập đối tượng đại diện tương đương với tập rút gọn

thu được từ tập đối tượng ban đầu.

74

,



 IDS U A 

   d

/ AU

,...,



Xét bảng quyết định không đầy đủ , bằng phương pháp

 X

1

kX

X

/

,...,

được trình bày ở phần 3.2.1 ta tính được . Với mỗi lớp tương



/ AUX i

i

   Y d  1

Y l

Y

X

/



đương , ta tính . Với mỗi lớp tương đương

  d

j

i

, ta chọn ra một đối tượng đại diện cho lớp tương đương đó,

không mất tính chất tổng quát, ta chọn đối tượng đầu tiên làm đại diện. Khi

đó, tập đối tượng được chọn là tập các đối tượng đại diện.

Thuật toán chọn tập đối tượng đại diện của bảng quyết định không đầy

đủ được mô tả như sau:

Thuật toán 3.2. Chọn tập đối tượng đại diện của bảng quyết định không đầy

,



đủ.

 IDS U A 

   d

U

A

,...,



Đầu vào: Bảng quyết định không đầy đủ ban đầu với



 a 1

ma

 u 1,...,

u n

IDS





,

p

 U A , p

   d

U

Đầu ra: Bảng quyết định không đầy đủ đại diện với

PU

là một tập đối tượng đại diện.

PU  

iA

..1

m



, 



u U 

Bước 1: Đặt ;

 

ai

U a / i

a i

    u



v U S

 



Bước 2: Với mỗi , tính với

    u

a i

a i

   u

a i

.



     v S

/ AU





... 



Uu

  u

  u

/ A 

A

a

a

   u

  u



a 1

m

  i u

m  i 1 

/ AU

,...,



Bước 3: Tính với

 X

1

kX

i

k 1..



Giả sử ;

/ AUX i  ,

Bước 4: Với mỗi , , thực hiện lặp các bước 4.1 và 4.2

như sau:

75

X



u X 



  d

/i

i

d

d

   v X d u   i

   d v

   u

    u



Y

,...,

u

X

/

,...,

j

l 1..





Bước 4.1. Tính với .



j

i

   Y d  1

Y l

 u



j 1

j o

U

U

Y

X

/

j

l 1..







Giả sử và với .

  d

:P 

P

j

i

j

 u

1

IDS





Bước 4.2. Với mỗi , , đặt ;

p

 U A , p

   d

Bước 5: Return ;

Chứng minh thuật toán 3.2

,



Tương tự như phần 3.2.1, cho bảng quyết định không đầy đủ ban đầu

 IDS U A 

   d

IDS





và bảng quyết định không đầy đủ đại diện

p

 U A , p

   d

, ta cũng chứng minh bổ đề sau:

pu U

IIS

A









B 

Bổ đề 3.2. Nếu là một đối tượng đại diện được chọn trên

 , AU

d  

 u



 u

p

A

p

B

IIS









u U

sao cho với thì ta cũng có

 u



 u

d  

p

A

p

p

 , AU p

p

p

B

IIS









trên với .

 , AU

d  

 u



 u

p

A

p

B





y Y

Chứng minh. Trên , từ giả thiết suy ra



 Y 



p

 uS A

p

 uS B

p

p



, giả sử . Khi đó, tồn tại sao cho

  yd

 uS A p

 A u

 uS B Apu  y 

y

y

, suy ra .

p

u

IIS

 







1) Nếu y là đối tượng đại diện, nghĩa là , khi đó trên

d  

 yd



 u

p

 , AU p

p

p

A

p

B

p

 d y











, và , do đó ta kết luận

 u



 u

p

A

p

B

.

76

py

IIS











2) Nếu y không phải là đối tượng đại diện, giả sử là đối tượng đại diện

  yd

d  

 yd

 u



 d y



 , AU p

 A u

p

A

p

p

p

 d y



u

IIS



 





nên trên ta có , mà của lớp tương đương chứa y, theo cách xây dựng tập đối tượng đại diện ta có p

 , AU

d  

 d y



 d y



p

B

p

 d y







u

u

IIS

 

 





(i). Hơn nữa, trên ta có , mà nên

d  

p

 , AU p

p

B

p

p

B

p

 d y







 d y











. Như vậy, trên ta có (ii). Từ (i)

 u



 u

p

A

p

B





và (ii) suy ra .

 u



 u

p

A

p

B

IIS





Như vậy, cả hai trường hợp 1) và 2) ta đều có trên

d  

p

 , AU p

.

Tiếp theo, luận án chứng minh rằng tập rút gọn của hệ quyết định không

đầy đủ ban đầu và tập rút gọn của hệ quyết định không đầy đủ đại diện là như

A

R 

nhau.

IIS

R









u U

u U

B  

Giả sử là tập rút gọn của hệ quyết định không dầy đủ ban đầu

 , AU

d  

  u

 u

R

A





, khi đó với mọi và tồn tại

  u

 u

R

A

IIS





u U

sao cho .

  u

 u

d  

R

A

IIS





u U





với mọi dễ dàng suy ra

 u

 , AU  d  

A

 p

p

R

p

p

P

B

u U

R

với mọi trên . 1) Từ   u trên  , AU p

IIS









2) Không mất tính tổng quát, giả sử và tồn tại trên

 , AU

d  

  u

 u

A

B

u





u

sao cho .

 u



 u

p

A

p

p

B

IIS

IIS













Nếu u là đối tượng đại diện được chọn thì và trên

 , AU

d  

 u



 u

d  

p

A

p

p

 , AU p

B

IIS





, theo Bổ đề 3.2 thì trên (i).

 , AU

d  

pu

[ u

][ u



Nếu u không phải đối tượng đại diện thì trên , giả sử

[ Apu ]

] Ap

A

pu

u

B

A

[ u

][ u

[ u

][ u

R 





là đối tượng đại diện của lớp dung sai chứa u và , khi đó .

  u

] Ap

A

] Ap

A

p

B

 

   B

Do nên từ ta cũng suy ra . Từ ta

77

u







 uS

 u



 u



  u

 uS A

p

A

p

A

A

p

B

 

   B

u

 







có , do đó . Từ , bằng cách tương tự ta

  u

 u

  u

A

B

B

p

B



IIS









suy ra . Theo giả thiết, nên ta thu được

 , AU

d  

 u

 u



 p

A

p

B

IIS









trên , theo Bổ đề 3.2 thì ta cũng có

 u



 u

d  

p

A

p

p

 , AU p

B





trên (ii)

 u



 u

p

A

p

B

IIS

B









R

Tóm lại, cả hai trường hợp (i) và (ii) ta đều có trên

 u



 u

d  

p

A

p

p

 , AU p

B

A

R 

, từ đó kết luận tồn tại sao cho . Từ 1)

và 2) theo định nghĩa ta có là một tập rút gọn của hệ thông tin không

,



đầy đủ đại diện.

 IDS U A 

   d

A

,

}



U

,

,

,

,

,

,

,



Ví dụ 3.2. Xét bảng quyết định không đầy đủ



a a a a , { , 1 2 4

3

 u u u u u u u u u , 1 5 9

7

2

4

8

3

6

với và . cho ở Bảng 3.2

Bảng 3.2. 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 độ tối đa Gia tốc

Cao Cao Đầy đủ Thấp Tốt u1

Thấp * Đầy đủ Thấp Tốt u2

* * Gọn nhẹ Cao Xấu u3

Cao * Đầy đủ Cao Tốt u4

* * Đầy đủ Cao Tuyệt hảo u5

Thấp Cao Đầy đủ * Tốt u6

* Cao Gọn nhẹ * Xấu u7

Thấp Cao Đầy đủ Thấp Tốt u8

* * Gọn nhẹ Cao Xấu u9

78

AU /

u

u

u

u

,

,

XXXXXXX

,

,

,

,

,

,



  ,

         , ,

  

    u , 1

uu , 2

8

uu , 3

9

6

5

7

4

1

2

3

5

4

6

7

u

Từ Ví dụ 3.1 ta có:

  d

/X 1

:PU

 1

1u

    u 1

X

/



: 

- Tính , vậy được chọn và .

  d



2

PU

 u u , 1 2

2u

  u u , 2 8

 

X

/

,

,



: 

- Tính , vậy được chọn và .

  d



3

PU

 u u u 1 2 3

3u

  u u , 3 9

 

,

,

: 

- Tính , vậy được chọn và .

  d



/X 4

PU

 u u u u , 1 2 4

3

4u

    u 4

,

,

,

,

: 

- Tính , vậy được chọn và .

  d



/X 5

PU

 u u u u u 1 3 5

4

2

5u

    u 5

,

,

,

,

: 

- Tính , vậy được chọn và .

  d



/X 6

PU

 u u u u u u , 1 3 6

2

4

5

6u

    u 6

,

,

,

,

,

,

: 

- Tính , vậy được chọn và .

  d



/X 7

PU

 u u u u u u u 1 4 7

6

5

3

2

7u

    u 7

- Tính , vậy được chọn và .

,

,

,

,

,

,

: 

Như vậy, tập tập đối tượng đại diện được chọn là



PU

 u u u u u u u 1 4 7

6

2

3

5

IDS





và hệ quyết định không đầy đủ đại diện

P

 U AT , P

   d

.

Như vậy, luận án đã trình bày phương pháp chọn tập đối tượng đại diện

từ tập đối tượng ban đầu cho bài toán tìm tập rút gọn của hệ thông tin không

đầy đủ và bảng quyết định không đầy đủ. Luận án đã chứng minh được tập rút

gọn trên tập đối tượng ban đầu và tập rút gọn trên tập đối tượng đại diện là

tương đương trên cả hệ thông tin không đầy đủ và bảng quyết định không đầy

đủ, từ đó khẳng định tính đúng đắn của phương pháp và khắc phục được các

nhược điểm của các phương pháp nén dữ liệu trong công trình [19], [44]. Do

kích thước của tập đối tượng đại diện nhỏ hơn kích thước tập đối tượng ban

đầu nên phương pháp chọn tập đối tượng đại diện sẽ giảm thiểu đáng kể thời

gian thực hiện các thuật toán tìm tập rút gọn. Dung lượng tập đối tượng đại

79

diện nhỏ hay lớn phụ thuộc vào tập đối tượng ban đầu của mỗi bài toán cụ thể.

Phần tiếp theo, luận án trình bày phương pháp rút gọn thuộc tính sử dụng

lượng thông tin mở rộng. Phương pháp đề xuất này thuộc Nhóm 2.

3.3. Phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng

có điều kiện

Trong phần này, luận án đề xuất phương pháp heuristic rút gọn thuộc tính

trong bảng quyết định không đầy đủ sử dụng độ đo lượng thông tin mở rộng

có điều kiện (conditional extended information quantity), bao gồm các bước:

xây dựng độ đo lượng thông tin mở rộng có điều kiện, định nghĩa tập rút gọn

và độ quan trọng của thuộc tính dựa trên độ đo lượng thông tin mở rộng có

điều kiện, xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng

độ đo lượng thông tin mở rộng có điều kiện, phân nhóm và thử nghiệm

phương pháp trên các tập dữ liệu mẫu từ kho dữ liệu UCI [36 ].

Các kết quả trong phần này đã được tác giả công bố trong công trình

[CT5].

3.3.1. Độ đo lượng thông tin mở rộng

Dựa trên khái niệm độ đo lượng thông tin (information quantity) trong

công trình [16], trong mục này chúng tôi xây dựng độ đo lượng thông tin mở

rộng (extended information quantity) nhằm đánh giá số lượng lớp tương

đương được phân hoạch bởi tập thuộc tính P trên tập đối tượng U cho trước.

Độ đo lượng thông tin mở rộng được xây dựng dựa trên khoảng cách Jaccard

UYX ,

giữa hai tập hợp hữu hạn.

,

1  

 D X Y



X Y  X Y 

Cho U là tập hữu hạn các đối tượng và . Biểu thức

80

được gọi là khoảng cách Jaccard (Jaccard distance) giữa hai tập hợp X và Y

IS

U





[26].

AU  ,



 u 1,...,

u n

A

U P /

,...,

P 



Cho hệ thông tin đầy đủ với , giả sử





P 1

P k

,

là phân hoạch sinh bởi tập thuộc tính . Khi đó, lượng

 EI P U



thông tin mở rộng của P trên tập đối tượng U, ký hiệu là , được tính

iP

k

k

,

1

1









1  

bằng tổng khoảng cách Jaccard trung bình giữa tập U và như sau:

 EI P U







1 k

1 k

P i U

1 k

i

i

1 

1 

U P  i U P  i

  

  

  

  

,

1 

(3.1)

 EI P U



1 n

U P /

,...,

,

/U P





Dễ thấy rằng, đạt giá trị lớn nhất là khi

 EI P U



  U 

   u 1

   u n

,

. đạt giá trị nhỏ nhất là 0 khi .

 EI P U



Độ đo lượng thông tin mở rộng đặc trưng cho số lượng các lớp

,

/U P

tương đương trong phân hoạch sinh bởi tập thuộc tính P trên tập đối tượng U.

 EI P U



/U P

càng lớn thì phân hoạch càng mịn, hay số lượng các lớp tương

đương sinh bởi càng lớn và ngược lại.

Từ lượng thông tin mở rộng xác định bởi tập thuộc tính P trên tập đối

tượng U, mục tiếp theo chúng tôi xây dựng lượng thông tin mở rộng có điều

kiện (conditional extended information quantity) của tập thuộc tính điều kiện

 d

P đối với thuộc tính quyết định trong bảng quyết định không đầy đủ.

IDS

U

,...,





3.3.2. Xây dựng lượng thông tin mở rộng có điều kiện

 , AU

d  

 u 1

nu

A

/ SIMU

P

..1

P 







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







n

  , iUuuS i

p

i

ta có là một phủ của U. Khi đó, ta xây

dựng lượng thông tin mở rộng có điều kiện (conditional extended information

 d

    CEI P d

quantity) của tập thuộc tính P đối với thuộc tính , ký hiệu là , là

81

1  

trung bình cộng các lượng thông tin mở rộng thành phần của thuộc tính  d





 p uS

i

, P

P

    EI d S u i



    EI d S u , i



1 P k i

trên các tập đối tượng , . Giả sử

  d /

i pk

 uS p

i

n

n

n

1







1  

với là số lớp tương đương của phân hoạch . Khi đó ta có:



P

    EI d S u , i



    CEI P d







1 n

1 n

1 n

i

i

i

1 

1 

1 

1 i k P

1 i k P

  

  

IDS





(3.2)

 , AU

d  



AQP ,

QP 

Mệnh đề 3.2. Cho bảng quyết định không đầy đủ và

    CEI P d

    CEI Q d







Uu 

. Nếu thì . Dấu đẳng thức

  u

 u

P

Q

    CEI P d

    CEI Q d

IDS





khi và chỉ khi với mọi .

 , AU

d  

U

,...,

QP 



Chứng minh. Xét bảng quyết định không đầy đủ với



 u 1

nu

Uui 

 uS Q

i

 uS P

i



k

S

. Nếu thì với mọi , nghĩa là



   d /

   d /

i k  Q

i P

Uui 

Q

u i

 S u P i

n

n

1





1 

, hay với mọi . Vì vậy,

    CEI P d

    CEI Q d





1 n

1 n

i

i

1 

1 

1 i k P

1 i k Q

k



, nghĩa là : .

i k  Q

i P

    CEI P d

    CEI Q d





Dấu đẳng thức khi và chỉ khi với mọi

 u



 u

P

i

Q

i

Uui 







, theo định nghĩa hàm quyết định suy rộng ta có với



 u



 u

Uui 

Uui 

 uS Q

i

 uS P

i

i

P

Q

i

mọi . Từ ta suy ra với mọi .

Mệnh đề 3.2 chứng minh tính phản đơn điệu của lượng thông tin mở

rộng có điều kiện đối với lực lượng của tập thuộc tính điều kiện. Nghĩa là tập

thuộc tính điều kiện P càng nhỏ thì phủ sinh bởi P càng thô và lượng thông

tin mở rộng có điều kiện của P đối với {d} càng lớn và ngược lại. Mệnh đề

này rất quan trọng và cho ta cơ sở để xây dựng phương pháp rút gọn thuộc

IDS

A





P 

tính sử dụng lượng thông tin mở rộng có điều kiện.

 , AU

d  

Mệnh đề 3.3. Cho bảng quyết định không đầy đủ và .

Khi đó ta có:

82

n

1 







 ui

P

Uui 

    CEI P d

1 n



1

1) đạt giá trị lớn nhất là khi với mọi .



 P u

i

Uui 

    CEI P d

2) đạt giá trị nhỏ nhất là 0 khi với mọi (Bảng

quyết định IDS nhất quán trên tập thuộc tính P)

Chứng minh.

i Pk

    CEI P d

1) Từ công thức (3.2) ta thấy đạt giá trị lớn nhất khi đạt

 U 

Uui 

 uS P

i

n







giá trị lớn nhất là n với mọi , xảy ra khi và phân hoạch

   / d



Uuu    

 uS p

i

i

i

P

 ui

n

1

(phân hoạch rời rạc), nghĩa là . Khi đó, giá

1 n

1 n

i

1 

1     n 

 1  

trị lớn nhất là .

i Pk

    CEI P d



2) Tương tự, đạt giá trị nhỏ nhất khi đạt giá trị nhỏ nhất

   / d

Uui 

 uS p

i

  uS p

i 



1

là 1 với mọi , xảy ra khi phân hoạch (phân hoạch



 P u

i

Uui 

khối), nghĩa là với mọi , khi đó IDS là bảng quyết định nhất

IDS





quán trên tập thuộc tính điều kiện P.

 , AU

d  

Mệnh đề 3.4. Cho bảng quyết định không đầy đủ . Khi đó ta

 IDS

 1 

    CEI P d

có:

 IDS



với là độ chắc chắn của bảng quyết định IDS trong công trình [CT5].

Mệnh đề 3.4 dễ dàng được suy ra từ công thức (3.2) và công thức tính

 IDS



độ chắc chắn của bảng quyết định trong công trình [CT5]. Mệnh đề

3.4 cho thấy độ đo lượng thông tin mở rộng có điều kiện của P đối với {d} là

đại lượng đối ngẫu với độ chắc chắn của bảng quyết định. Nếu độ đo này

càng lớn thì độ chắc chắn của bảng quyết định càng nhỏ và ngược lại.

83

3.3.3. Rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều kiện

Trong phần này, luận án trình bày một phương pháp heuristic rút gọn

thuộc tính trong bảng quyết định không đầy đủ sử dụng độ đo lượng thông tin

mở rộng có điều kiện. Giống như các phương pháp heuristic khác, phương

pháp của này cũng bao gồm các bước: định nghĩa tập rút gọn dựa trên ượng

thông tin mở rộng có điều kiện, định nghĩa độ quan trọng của thuộc tính dựa

trên lượng thông tin mở rộng có điều kiện và 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 dựa trên tiêu chí đánh giá là độ quan

IDS





trọng của thuộc tính.

 , AU

d  

R

A

Định nghĩa 3.1. Cho bảng quyết định không đầy đủ và tập



thuộc tính . Nếu

    CEI R d

    CEI A d

,

 





1)

  r

 r R CEI R



    d

    CEI A d

2)

thì R là một tập rút gọn của A dựa trên lượng thông tin mở rộng có điều kiện

Từ Mệnh đề 3.2 ta thấy tập rút gọn dựa trên lượng thông tin mở rộng có

điều kiện và tập rút gọn dựa trên hàm quyết định suy rộng là như nhau. Từ

kết quả phân nhóm các phương pháp rút gọn thuộc tính được trình bày trong

Chương 2 ta có: phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở

IDS

A





B 

rộng có điều kiện thuộc Nhóm 2.

 , AU

d  

BAb 

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

và . Độ quan trọng của thuộc tính b đối với tập thuộc tính B được







  SIG b B

    CEI B d

 CEI B

     d b

định nghĩa bởi:

84





  0b

 b

SIGB

SIGB

    CEI B d

 CEI B

     d b

Theo Mệnh đề 3.2, nên .

được tính bởi lượng thay đổi lượng thông tin mở rộng có điều kiện giữa tập

thuộc tính điều kiện B và thuộc tính quyết định {d} khi thêm thuộc tính b vào

 b

SIGB

B và càng lớn thì lượng thay đổi lượng thông tin mở rộng có điều kiện

càng lớn, hay thuộc tính b càng quan trọng và ngược lại. Độ quan trọng của

thuộc tính này là tiêu chuẩn lựa chọn thuộc tính trong thuật toán heuristic tìm

tập rút gọn của bảng quyết định.

R

Ý tưởng của thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng

lượng thông tin mở rộng có điều kiện là xuất phát từ tập rỗng , lần lượt

bổ sung thêm vào R các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm

được tập rút gọn.

Thuật toán 3.3 (Thuật toán EIQBAR). Thuật toán heuristic tìm một tập rút

IDS





gọn sử dụng lượng thông tin mở rộng có điều kiện.

 , AU

d  

Đầu vào: Bảng quyết định không đầy đủ

Đầu ra: Một tập rút gọn .R

1. ;R

    CEI R d

    CEI A d

2. Tính lượng thông tin mở rộng có điều kiện và ;



// Thêm vào R các thuộc tính có độ quan trọng lớn nhất

    CEI R d

    CEI A d

3. While do







RAa 

4. Begin

  SIG a R

    CEI R d

 CEI R

     d a

SIG

RA





For tính ; 5.

 a



 SIG

a  

m

R

R

am

Max RAa 

RR



Chọn sao cho ; 6.

ma 

7. ;

    CEI R d

8. Tính ;

85

9. End;

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

10.For each doRa 



11. Begin

 CEI R

     d a





RR 



Tính ; 12.

 a

 CEI R

     d a

    CEI R d

13. If then ;

14.End;

15. Return ;R

 a

SIGR



Xét vòng lặp While từ dòng lệnh 3 đến 9, để tính ta cần phải tính

 CEI R

     d a

    CEI R d

S

phải tính vì đã được tính ở bước trước, nghĩa là

  d /

a

i

a

i

R

S  R



  u

  u

cần phải tính và phân hoạch . Theo Zhang và các cộng

Uui 

 R uS

i

a

i

S  R

  u

S

với mọi khi

  d /

Uui 

a

i

R



  u

, độ phức tạp để tính phân hoạch với mọi là . sự [9], độ phức tạp để tính 2UO  đã được tính là 2UO 

 a

SIGR

2

2

2

2

A

A

U

A

*

A

U





 









 1







 ... 1 *



 / 2 *

 O A U



A

U

Do đó, độ phức tạp thời gian để tính tất cả các ở dòng lệnh số 5 là:

1

A

A

A

A





... 

 1





với là số thuộc tính điều kiện và là số đối tượng. Độ phức tạp thời gian

 AO

để chọn thuộc tính có độ quan trọng lớn nhất ở dòng lệnh số 6 là: 2 . Do đó, độ phức tạp thời gian của

 2/1  2

vòng lặp While là

. Vì vậy, độ phức tạp thời gian của Thuật toán . Tương tự, độ phức tạp của vòng lặp For từ dòng 2

*  2 UAO  2 UAO lệnh số 10 đến 14 là 2

 2 UAO

EIQBAR là .

86

IDS

,

,

,

,

,





U 

Ví dụ 3.3. Bảng 3.3 [16] mô tả dữ liệu về các xe hơi là bảng quyết định

 , AU

d  

 uuuuuuu , 1 3

2

5

4

2

6

không đầy đủ với và A = {Đơn

giá, Km đã đi, Kích thước, Tốc độ}

87

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

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

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

,

SIM

R



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





  vuUv 

P 





















  uS P  U 

 uS R

1

 uS R

2

 uS R

3

 uS R

4

 uS R

5

 uS R

6

Ta khởi tạo Khi đó từ công thức ta có







   / d

   / d

   / d

  d /

1

 uS R

2

 uS R

3

 uS R

4

 uS R

5

 uS R

6

,

,





   / d   dU /

 uS  R     u u , ,

   uuuu , 2

4

1

   / d 5 

3

6

Khi đó ta có:

    CEI R d

, từ công thức tính lượng thông tin mở rộng có điều Ta tính

    CEI R d

kiện ta có:

    CEI R d 1/3)}=2/3.

u

u







= 1/6 { (1-1/3)+ (1-1/3)+(1-1/3)+ (1-1/3)+ (1-1/3)+(1-







 uS A

1

1

 uS A

2

 , uu 2

6

 uS A

3

3

    CEI A d

,

,







Tiếp tục tính ta có , , ,







 uS A

4

 , uu 4

5

 uS A

5

 uuu , 5

4

6

 uS A

6

 uuu , 5

2

6

u

d

u

d





, , . Khi đó:

   d /

  u

  u ,

   d /

    3 / 

3

 uS A

4

5 

4

  uu , 2

6 

2





, , ,

 uS A    d /

   d /

    1 1 /      uu u , , 4

6

 uS A 5 

 uS A

5

 uS A

6

  uu , 2

6

 uS A   5  . u ,

,

1 / 4















  1 1  

  1 1  

 1 1 / 2



 1 1 / 2



 1 1 / 2

   1 / 6 1 1  

 

    CEI A d

Từ công thức 3.2 ta có:

88



    CEI R d

    CEI A d

Vì vậy . Tiếp tục thực hiện vòng lặp While, tính

2 / 3



























  1 1 / 3

  1 1 / 3

   1 1 / 3

2 / 3 2 / 3 0













tương tự ta có:

 CEI R  SIG a 1 R

       1 / 6 1 1 / 3 d a  1       CEI R CEI R d

    1 1 / 3 1 1 / 3      d a 1

Từ đó

2 / 3 2 / 3 0















 SIG a R

2

2

    CEI R d

 CEI R

     d a

2 / 3 5 / 12 1 / 4















 SIG a R

3

3

2 / 9









2 / 3 4 / 9 





 SIG a R

4

4

    CEI R d     CEI R d

 CEI R  CEI R

     d a      d a

RR



Tương tự,

SIGR

3a 

 3a

   CEI R d

 5 / 12 

Vậy lớn nhất do đó ta có , vậy .

0









5 / 12 5 / 12 





 SIG a R 1

    CEI R d

 CEI R

     d a 1

0









5 / 12 5 / 12 





 SIG a R

2

2

    CEI R d

 CEI R

     d a

5 / 12 1 / 4 1 / 6















 SIG a R

4

4

    CEI R d

 CEI R

     d a

RR



Tiếp tục tính

SIGR

4a 

 4a

   CEI R d

 1 / 4 



R 

Vậy lớn nhất do đó ta có , Vậy

 3 , aa

4

    CEI R d

    CEI A d

Ta có dừng vòng lặp, Vậy .

5 / 12









Loại bỏ thuộc tính dư thừa trong R.

4

4

 CEI R

 CEI R

4 / 9









, do đó vậy không

3

3

         CEI R d d a       d a CEI R

    CEI R d

     d a       d a CEI R không loại bỏ a3.

R 

, do đó vậy loại bỏ a4.

 3 , aa

4

Vậy tập rút gọn thu được là .

3.3.4. Thử nghiệm và đánh giá kết quả

Luận án chọn thuật toán MBAR tìm tập rút gọn của bảng quyết định

không đầy đủ sử dụng metric trong [2] để so sánh với thuật toán sử dụng

89

lượng thông tin mở rộng có điều kiện đề xuất (Thuật toán EIQBAR) về thời

gian thực hiện và kết quả thực hiện. Sở dĩ chọn thuật toán MBAR vì theo lý

thuyết đã trình bày, tập rút gọn của Thuật toán EIQBAR (thuộc Nhóm 2) tối

thiểu hơn tập rút gọn của thuật toán MBAR (thuộc Nhóm 3). Để tiến hành thử

nghiệm, chúng tôi thực hiện các công việc sau:

1) Cài đặt thuật toán MBAR và Thuật toán EIQBAR bằng ngôn ngữ C#.

S

Cả hai thuật toán đều sử dụng thuật toán trong [17] để tính các lớp dung sai





B

u i

iu U

với . Với mỗi tập rút gọn thu được của mỗi thuật toán, thực hiện

 IDS



 IDS



 IDS



tính độ chắc chắn , độ nhất quán và độ hỗ trợ trên bảng

quyết định với tập rút gọn thu được bằng công thức đề xuất trong mục 2.3.2.

2) Trên máy tính PC với cấu hình Core i3 4150, 3 GB bộ nhớ RAM, sử

dụng hệ điều hành Windows 7, chạy thử nghiệm hai thuật toán với 6 bộ số

U

C

liệu lấy từ kho dữ liệu UCI [40]. (Mô tả bộ dữ liệu chi tiết tại mục 2.3.4)

R

Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính điều

kiện, là số thuộc tính của tập rút gọn, t là thời gian thực hiện thuật toán

(đơn vị là giây s), các thuộc tính điều kiện được đánh số là 1, 2,…, . C

- Kết quả thực hiện của hai thuật toán về tập rút gọn được mô tả ở Bảng

3.4 và Bảng 3.5 sau đây:

90

Bảng 3.4. Kết quả thực hiện thuật toán MBAR và Thuật toán EIQBAR

Thuật toán

Thuật toán

MBAR

EIQBAR

U

C

STT

Bộ số liệu

t

t

R

R

Hepatitis.data

155

4

19

1.296

3

1.29

1

Lung-cancer.data

32

4

56

0.171

4

0.17

2

Automobile.data

205

8

26

1.687

6

1.68

3

Anneal.data

798

9

38

179

7

178

4

16

Congressional Voting

435

15

16.7

15

16.73

5

Records

Credit Approval

690

15

7

15.7

5

15.68

6

Bảng 3.5. Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR

Tập rút gọn của

Tập rút gọn của

STT

Tập dữ liệu

Thuật toán MBAR

Thuật toán EIQBAR

Hepatitis.data

{1, 2, 4, 17}

{1, 2, 17}

1

Lung-cancer.data

{3, 4, 9, 43}

{3, 4, 9, 43}

2

Automobile.data

{1, 8, 9, 13, 14, 20,

{1, 4, 13, 14, 20, 21}

3

21, 24}

Anneal.data

{1, 3, 4, 5, 8, 9, 33,

{1, 3, 4, 5, 8, 9, 34}

4

34, 35}

Congressional Voting

{1, 2, 3, 4, 5, 7, 8, 9,

{1, 2, 3, 4, 5, 7, 8, 9,

5

Records

10, 11, 12, 13, 14, 15,

10, 11, 12, 13, 14, 15,

16}

16}

Credit Approval

{1, 2, 3, 4, 5, 6, 8}

{1, 3, 4, 5, 8}

6

91

Kết quả thực hiện của hai thuật toán về tập rút gọn và tính toán giá trị

các độ chắc chắn , độ nhất quán , độ hỗ trợ  mô tả ở Bảng 3.6 sau đây:

Bảng 3.6. Kết quả tính toán độ chắc chắn, độ nhất quán và độ hỗ trợ trên các

tập rút gọn

Thuật toán EIQBAR

Thuật toán MBAR

U

C

Bộ số liệu

R

R













S T T

1 Hepatitis.data

155

0.909 0.819

0.504 4

0.909

0.819 0.415

3

19

2

Lung-cancer.data

32

1

0.814 4

1

0.814

4

56

1

1

6

26

0.915 0.781

0.624 8

0.915

0.781 0.518

3 Automobile.data

205

7

38

0.852 0.755

0.503 9

0.852

0.755 0.426

4 Anneal.data

798

5

16

15

1

0.616 15

1

0.616

1

1

435

Congressional Voting Records

6

Credit Approval

690

15

5

0.884 0.802

0.615 7

0.884

0.802 0.487

Hình 3.1 biễu diễn sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai

0.900

0.800

0.700

0.600

0.500

0.400

0.300

0.200

0.100

Thuật toán EIQBAR Thuật toán MBAR

0.000

A nneal.data

H epatitis.data

Credit A pproval

A uto m obile.data

L ung-cancer.data

C. V oting R ecords

thuật toán EIQBAR và MBAR.

Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán

EIQBAR và MBAR.

92

1) Kết quả thử nghiệm từ Bảng 3.4 và Bảng 3.5 cho thấy:

 Trên các bộ số liệu Lung-cancer.data, Congressional Voting Records, tập

rút gọn thu được bởi Thuật toán EIQBAR và Thuật toán MBAR là như nhau.

Tuy nhiên, với các bộ số liệu còn lại, tập rút gọn thu được bởi Thuật toán

EIQBAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán MBAR. Điều này

cũng phù hợp với kết quả nghiên cứu về lý thuyết.

 Thời gian thực hiện Thuật toán EIQBAR và Thuật toán MBAR về cơ

bản là tương đương nhau.

2) Kết quả thử nghiệm từ Bảng 3.6 và Hình 3.1 cho thấy:

 Độ chắc chắn , độ nhất quán  của hai tập rút gọn thu được bởi hai

thuật toán EIQBAR và MBAR trên 6 bộ dữ liệu thử nghiệm là bằng nhau.

 Độ hỗ trợ của tập rút gọn thu được bởi Thuật toán EIQBAR cao hơn độ

hỗ trợ của tập rút gọn thu được bởi Thuật toán MBAR.

Phần tiếp theo, chúng tôi trình bày phương pháp rút gọn thuộc tính sử

dụng hàm quan hệ (relations function) được xây dựng trên ma trận quan hệ

(relational matrix). Phương pháp đề xuất này cũng thuộc Nhóm 2.

3.4. Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ

Theo tiếp cận lý thuyết tập thô truyền thống, Skowron [39] đã đưa ra khái

niệm ma trận phân biệt và hàm phân biệt để tìm tập rút gọn trong bảng quyết

định đầy đủ. Dựa trên cách tiếp cận này, luận án đưa ra khái niệm hàm quan hệ

(relations function) và ma trận quan hệ (relational matrix) để tìm tập rút gọn

của bảng quyết định không đầy đủ. Phương pháp heuristic đề xuất cũng bao

gồm các bước: xây dựng ma trận quan hệ và hàm quan hệ, định nghĩa tập rút

gọn và độ quan trọng của thuộc tính sử dụng hàm quan hệ, xây dựng thuật toán

heuristic tìm một tập rút gọn tốt nhất sử dụng hàm quan hệ.

Các kết quả trong phần này đã được tác giả công bố trong công trình số

[CT4].

93

,



3.4.1. Ma trận quan hệ và hàm quan hệ

  d

 IDS U A 



R

R

IDS

A

U n

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

. Ma trận quan hệ của trên tập thuộc chính , ký hiệu

 m

R ij

M  R

, là ma trận vuông cấp n, mỗi phần tử có giá trị 0 hoặc 1, được và nxn

1R



định nghĩa như sau:

 u

 ud



ijm

i

R

j

0R



(1) nếu

 u

 ud



ijm

i

R

j

R

0R

(2) nếu .

RM

ijm

i

1,...,

n

j

1,...,

n









Chú ý: Nếu thì quy ước và không phải là ma trận đối

 u

 ud



 ud



 u

j

i

R

i

R

j

xứng vì vẫn có thể với ; .

IDS

,

,

,

,

,





U 

A

,

,



Ví dụ 3.4. Bảng 3.7 mô tả dữ liệu về tivi là bảng quyết định không đầy đủ

 , AU

d  



 uuuuuuu , 1 3

4

2

2

5

6

 a a a a , 1 2

3

4

với và với a1 (Đơn

giá) a2 (Màu sắc), a3 (Kích thước), a4 (Độ phân giải), d ={Chất lượng}.

Bảng 3.7. Bảng quyết định không đầy đủ mô tả về các tivi

Kích Độ phân Chất Tivi Đơn giá Màu sắc thước giải lượng

Đen Gọn nhẹ Thấp Cao Tốt u1

Gọn nhẹ Thấp Thấp * Tốt u2

Nhỏ nặng Cao * * Xấu u3

Cao Nâu Gọn nhẹ Thấp Tốt u4

* * Gọn nhẹ Cao Tuyệt hảo u5

A

IDS

Thấp Nâu Gọn nhẹ * Tốt u6

Khi đó, ma trận quan hệ của trên tập thuộc tính là:

94



AM

010100   010100   111011  010100   000100  000100  

         

" "

X 

Y 



 R ijx

R ijy

mxn

mxn

" "

Định nghĩa 3.4. Cho hai ma trận và . Hai quan hệ và

X Y

y

i

1, 2,...,

m

j

1, 2,...,

n





được định nghĩa như sau:

R x  ij

R ij

X Y

y

i

1, 2,...,

m

j

1, 2,...,

n





(1) khi và chỉ khi , ,

R x  ij

R ij

AQP ,

,



(2) khi và chỉ khi , ,

  d

 IDS U A 



P Q

Mệnh đề 3.5. Cho bảng quyết định không đầy đủ với .

M M P

Q

A

,

,

R 

R 

Nếu thì .

 aaa 2 1

3

Ví dụ 3.5. Tiếp tục Ví dụ 3.4, giả sử với , khi đó ta tính

000100

000100



RM

000100

000100

000100

    111011      

         

M 

được:

R M

A

R

A

,



Rõ ràng,

  d

 IDS U A 



R

IDS

Định nghĩa 3.5. Cho hệ quyết định không đầy đủ , với

 m

M  R

R ij

nxn

R

IDS

và là ma trận quan hệ của trên tập thuộc tính . Khi đó,

RDIS 

n

n

1

n

, 1

n

i  

j  

hàm quan hệ của trên , ký hiệu là , được định nghĩa như sau:

 RDIS

R ijm

  

i

j

1 

1 

với .

95

AM

112522

13

ADIS





Ví dụ 3.6. Tiếp tục Ví dụ 3.4, với ma trận phân biệt , hàm phân biệt là:

AQP ,

,



Từ Định nghĩa 3.5 và Mệnh đề 3.5 ta có mệnh đề sau:

  d

 IDS U A 



P Q

Mệnh đề 3.6. Cho hệ quyết định không đầy đủ với .

 DIS Q DIS P 







,



Nếu thì .

ADIS 

  d

AM

 IDS U A 



A

IDS

Mệnh đề 3.7. Cho hệ quyết định không đầy đủ và ,

( ADIS )







u U 

tương ứng là ma trận quan hệ và hàm quan hệ của trên tập thuộc tính .

 RDIS



  u

 u

R

A

Khi đó, khi và chỉ khi với .









Chứng minh.

 u



R

A

i

A

R

i

i 0

i 0









sao cho

0iu U  ud



 u



 u  ud

 

 u  u

 ud



 u  u

j

R

j

A

i

j

i

A

0

i 0

0

0 . Vì 0

0

0 nên tồn 0

A

1

M

0

M

R 

sao cho tại . Từ ta có i) Giả sử tồn tại 0jud 

im

A

im

R

R j 00

R m  j i 00

R j 00

R m  j i 00

M 

( ADIS )



, (1). Từ , (2). Từ giả thiết ta có

 RDIS



R M

A

( ADIS )

( ADIS )









, kết hợp với (1) và (2) ta có

 RDIS



 RDIS



 u

 u

A

R

i

0

i 0

( ADIS )

A



R 

điều kiện . Vì vậy, nếu thì . , điều này mâu thuẫn với 

 RDIS



M 

( ADIS )



M 

ii) Ngược lại, giả sử . Theo bổ đề 1 từ ta có

 RDIS



R M

A

R M

A

0i

0j

m

0

m

1









, kết hợp với suy ra , khi đó tồn tại và

mM , R

mM , A

R i j 00

R i j 00

R i j 00

R i j 00







 

sao cho (3) và (4). Từ (4) suy ra

 ud



 u

 u



 u

j

A

i

R

A

i

R

0

0

i 0

0

j 0

u i 0

 d u















u U 

. Từ (3) suy ra . Do đó, , điều này

  u

 u

  u

 u

A

R

A

R

( ADIS )



u U 

mâu thuẫn với điều kiện với . Vì vậy nếu với

 RDIS



thì .

Từ i) và ii) ta có điều phải chứng minh.

96

3.4.2. Rút gọn thuộc tính sử dụng hàm quan hệ

Trong mục này, luận án trình bày phương pháp heuristic rút gọn thuộc

tính trong bảng quyết định không đầy đủ sử dụng hàm quan hệ. Giống như

các phương pháp heuristic khác, phương pháp của chúng tôi bao gồm các

bước: định nghĩa tập rút gọn dựa trên hàm quan hệ; định nghĩa độ quan trọng

của thuộc tính dựa trên hàm quan hệ; xây dựng thuật toán heuristic tìm một

tập rút gọn tốt nhất sử dụng độ quan trọng của thuộc tính làm tiêu chuẩn lựa

,



chọn thuộc tính.

  d

 IDS U A 



R

A

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

( ADIS )



thỏa mãn:

 RDIS



'

ADIS ) (

R



' R

(1)

 RDIS



IDS

(2) ,

thì R được gọi là một tập rút gọn của dựa trên hàm quan hệ.

Mệnh đề 3.7 cho thấy rằng tập rút gọn sử dụng hàm quan hệ tương đương

với tập rút gọn sử dựa trên hàm quyết định suy rộng. Do đó, phương pháp rút

gọn thuộc tính sử dụng hàm quan hệ thuộc Nhóm 2 (theo kết quả phân nhóm

R

A

,



các phương pháp rút gọn thuộc tính trình bày ở Chương 2).

  d

 IDS U A 



a

R

RAa 

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

. Độ quan trọng của thuộc tính đối với tập thuộc tính được định







  a

 RDIS

   a

RDIS 

SIG out R

R

A

,



nghĩa bởi

  d

 IDS U A 



a

R

Ra 

Định nghĩa 3.8. Cho hệ quyết định không đầy đủ , và

. Độ quan trọng của thuộc tính trong tập thuộc tính được định

nghĩa bởi

97







  a

 RDIS



 RDIS

a  

SIG in R

  0a

  0a

 a

SIG out R

SIG in R

SIG out R

Từ Mệnh đề trên ta có và Do đó, và

 a

SIG in R

được tính bởi lượng thay đổi hàm quan hệ khi thêm thuộc tính a vào

 a

 a

SIG out R

SIG in R

R hoặc loại bỏ a khỏi R và , càng lớn thì lượng thay đổi này

càng lớn, hay thuộc tính a càng quan trọng và ngược lại.

Tiếp theo, luận án đề xuất thuật toán heuristic tìm một tập rút gọn tốt

:R

nhất theo tiêu chuẩn đánh giá độ quan trọng của thuộc tính. Ý tưởng của thuật

toán là xuất phát từ tập thuộc tính rỗng , lần lượt bổ sung vào tập R các

thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. Thuật

toán đề xuất sử dụng chiến lược Thêm - Xóa [50].

Thuật toán 3.4(Thuật toán RBAR). Thuật toán heuristic tìm một tập rút gọn

,



tốt nhất sử dụng hàm quan hệ.

  d

 IDS U A 



Đầu vào: Bảng quyết định không đầy đủ .

R  

.R

( ADIS )



;

 RDIS



Đầu ra: Một tập rút gọn 1. // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất; 2. While do

RAa 





3. Begin





 out SIG a R

 DIS R

   a

SIG

RA





4. For each tính ;

 a



  SIG

 DIS R a  

out R

m

out R

am

Max RAa 

R R

 

5. Chọn sao cho ;



m a

6. ;

R R





 

7. End; //Loại bỏ các thuộc tính dư thừa trong R nếu có; 8. For each a R

  a

 DIS R



  a

 DIS R



9. If then ;

10. Return ;R

98

n

k

Giả sử là số đối tượng. Dễ thấy rằng độ

ADIS 

AM

 O kn

 O kn

2

là phức tạp để tính , do đó độ phức tạp tính là . Xét là số thuộc tính điều kiện và 2

2

2

k

k

kn

k

*

k









vòng lặp While từ dòng lệnh 2 đến dòng lệnh 7, độ phức tạp để tính tất cả các



 1   





 SIG a R



 ... 1 *



  1 / 2 *

 3 2 kn O k n



là . Độ phức tạp thời gian

k

k

... 1

k

*

k



   





để chọn thuộc tính độ quan trọng lớn nhất là



 1



 1 / 2

 O k

. Do đó, độ phức tạp của vòng lặp While là có 2

 3 2 O k n



 2 2 O k n



. Tương tự, độ phức tạp của vòng lặp For là . Vì vậy, độ phức

 3 2 O k n



,



tạp của Thuật toán RBAR là .

  d

 IDS U A 



R

Ví dụ 3.7. Xét bảng quyết định không đầy đủ cho ở Ví dụ 3.4.

R  

Áp dụng Thuật toán RBAR. tìm tập rút gon ta có:

DIS

0











 



  

 

a 1

out SIG 

 DIS a 1



 DIS a 1



DIS

0











 



  

 

a 2

out SIG 

 DIS a 2



 DIS a 2



DIS

DIS

DIS







 a



    a

  

   a

 10 

3

3

3

SIG out 

DIS

DIS

DIS







 a



    a

  

   a

 6 

4

4

4

SIG out 

R

a

Đặt và tính:

3a

 3

( ADIS )



Chọn thuộc tính có độ quan trọng lớn nhất và . Từ Ví dụ 3.5

 13ADIS 

 RDIS



DIS

DIS

10

10

0













 

    a

SIG out a

 a 1

  aa , 1

3

3

3

DIS

DIS

10

10

0











 a



 

    a

SIG out a

2

  aa , 2

3

3

3

DIS

DIS

13

10

3











 a



 

    a

SIG out a

4

  aa , 3

4

3

3

R



ta có , do đó . Chuyển vòng lặp thứ 2 và tính:





4a

a a , 3 4

Chọn thuộc tính có độ quan trọng lớn nhất, và .

99

DIS

ADIS ) (

13





 

  aa , 3

4

Ta thấy , chuyển đến vòng lặp For thực hiện

DIS

ADIS ( )

DIS

ADIS ) (





kiểm tra tập R thu được.

    a

    a

4

3

R



Theo tính toán ở trên, và . Do đó





a a , 3 4

thuật toán kết thúc và là một rút gọn “tốt nhất” của A.

3.4.3. Thử nghiệm và đánh giá kết quả

Luận án chọn thuật toán MBAR tìm tập rút gọn của bảng quyết định

không đầy đủ sử dụng metric trong [2] và Thuật toán EIQBAR tìm tập rút gọn

sử dụng lượng thông tin mở rộng để so sánh với Thuật toán RBAR tìm tập rút

gọn sử dụng hàm quan hệ về thời gian thực hiện và kết quả thực hiện. Bởi vì:

- Tập rút gọn của Thuật toán RBAR (thuộc Nhóm 2) tối thiểu hơn tập

rút gọn của Thuật toán MBAR (thuộc Nhóm 3).

- Tập rút gọn của Thuật toán RBAR (thuộc Nhóm 2) tương đương với

tập rút gọn của Thuật toán EIQBAR (thuộc Nhóm 2).

Để tiến hành thử nghiệm, Ta thực hiện các công việc sau:

1) Cài đặt thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR

S

bằng ngôn ngữ C#. Thuật toán MBAR, Thuật toán EIQBAR sử dụng thuật toán





u i

B

iu U

trong [17] để tính các lớp dung sai với .

2) Trên máy tính PC với cấu hình Core i3 4150, 3 GB bộ nhớ RAM, sử

dụng hệ điều hành Windows 7, chạy thử nghiệm ba thuật toán với 6 bộ số liệu

U

C

lấy từ kho dữ liệu UCI [40]. (Mô tả bộ dữ liệu chi tiết tại mục 2.3.4)

R

Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính điều

C

kiện, là số thuộc tính của tập rút gọn, t là thời gian thực hiện thuật toán

(đơn vị là giây s), các thuộc tính điều kiện được đánh số là 1, 2,…, . Kết

quả thực hiện của ba thuật toán được mô tả ở Bảng 3.8 và Bảng 3.9 như sau.

100

Bảng 3.8. Kết quả thực hiện thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR

Thuật toán

Thuật toán

Thuật toán

MBAR

EIQBAR

RBAR

U

C

STT

Bộ số liệu

t

t

t

R

R

R

Hepatitis.data

155

19

4

1.296

3

1.29

3

1.56

1

Lung-cancer.data

32

56

4

0.171

4

0.17

4

0.98

2

Automobile.data

205

26

8

1.687

6

1.68

6

1.92

3

Anneal.data

798

38

9

179

7

178

7

196

4

Congressional

435

16

15

16.7

15

16.73

15

18.45

5

Voting Records

Credit Approval

690

15

7

15.7

5

15.68

5

17.02

6

Bảng 3.9. Tập rút gọn của thuật toán MBAR, Thuật toán EIQBAR và Thuật toán RBAR Tập rút gọn của

Tập rút gọn của

Tập rút gọn của

STT

Tập dữ liệu

MBAR

EIQBAR

RBAR

Hepatitis.data

{1, 2, 4, 17}

{1, 2, 17}

{1, 2, 17}

1

Lung-cancer.data

{3, 4, 9, 43}

{3, 4, 9, 43}

{3, 4, 9, 43}

2

Automobile.data

{1, 8, 9, 13, 14, 20,

{1, 4, 13, 14, 20,

{1, 4, 13, 14, 20,

3

21, 24}

21}

21}

Anneal.data

{1, 3, 4, 5, 8, 9, 33,

{1, 3, 4, 5, 8, 9,

{1, 3, 4, 5, 8, 9,

4

34, 35}

34}

34}

Congressional

{1, 2, 3, 4, 5, 7, 8, 9,

{1, 2, 3, 4, 5, 7, 8,

{1, 2, 3, 4, 5, 7, 8,

5

Voting Records

10, 11, 12, 13, 14,

9, 10, 11, 12, 13,

9, 10, 11, 12, 13,

15, 16}

14, 15, 16}

14, 15, 16}

Credit Approval

{1, 2, 3, 4, 5, 6, 8}

{1, 3, 4, 5, 8}

{1, 3, 4, 5, 8}

6

101

Kết quả thử nghiệm cho thấy:

 Trên cả 6 bộ dữ liệu, tập rút gọn thu được bởi Thuật toán EIQBAR và

Thuật toán RBAR là như nhau. Điều này phù hợp với nghiên cứu lý thuyết,

phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng (Thuật toán

EIQBAR) và phương pháp rút gọn thuộc tính sử dụng hàm quan hệ (Thuật

toán RBAR) đều thuộc Nhóm 2.

 Trên các bộ số liệu nhất quán Lung-cancer.data, Congressional Voting

Records, tập rút gọn thu được bởi Thuật toán RBAR và Thuật toán MBAR là

như nhau. Tuy nhiên, với các bộ số liệu còn lại, tập rút gọn thu được bởi

Thuật toán RBAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán MBAR.

Điều này cũng phù hợp với kết quả nghiên cứu về lý thuyết.

 Thời gian thực hiện Thuật toán EIQBAR và Thuật toán MBAR về cơ

bản là tương đương nhau. Tuy nhiên, thời gian thực hiện của Thuật toán

RBAR lớn hơn thời gian thực hiện của Thuật toán EIQBAR. Bởi vì, độ phức

tạp thời gian của Thuật toán RBAR cao hơn so với Thuật toán EIQBAR. Sở

a

i

S  R

  u

dĩ cao hơn là vì Thuật toán EIQBAR sử dụng công thức cải tiến tính

Uui 

 R uS

i

với mọi khi đã được tính ở bước trước [17]. Còn Thuật toán 3.4



Uui 

 S u R i

tính ma trận quan hệ trực tiếp từ các lớp dung sai với mọi .

3.5. Kết luận chương 3

Chương 3 luận án đã thực hiện các nội dung nghiên cứu sau:

(1) Theo hướng tiếp cận rút gọn dữ liệu, chương 3 đề xuất kỹ thuật chọn

tập đối tượng đại diện cho bài toán rút gọn thuộc tính trong hệ thông tin

không đầy đủ và bảng quyết định không đầy đủ nhằm giảm thiểu thời gian

thực hiện các thuật toán tìm tập rút gọn trên các bảng quyết định có dung

lượng dữ liệu lớn. Kết quả này được công bố trong công trình [CT3].

102

(2) Đề xuất phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở

rộng và chứng minh phương pháp đề xuất thuộc Nhóm 2 (trong phân nhóm

các phương pháp rút gọn thuộc tính được trình bày ở Chương 2). Kết quả này

được công bố trong công trình [CT5].

(3) Đề xuất phương pháp rút gọn thuộc tính sử dụng hàm quan hệ và

chứng minh phương pháp đề xuất cũng thuộc Nhóm 2 (trong phân nhóm các

phương pháp rút gọn thuộc tính được trình bày ở Chương 2). Kết quả này

được công bố trong công trình [CT4].

Các kết quả nghiên cứu này góp phần làm phong phú thêm về hướng

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 đủ.

103

KẾT LUẬN

1) Những kết quả chính của luận án:

Luận án tập trung 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 đủ ở bước tiền xử lý dữ liệu với các kết quả chính như sau:

(1) Phân nhóm các phương pháp rút gọn thuộc tính dựa vào kết quả nghiên

cứu mối liên hệ giữa các khái niệm tập rút gọn dựa trên nguyên tắc: các phương

pháp có tập rút gọn giống nhau được phân vào một nhóm. Luận án chỉ ra các

phương pháp rút gọn thuộc tính được phân thành bốn nhóm: Nhóm 1, Nhóm 2,

Nhóm 3, Nhóm 4. Luận án cũng nghiên cứu mối liên hệ giữa các tập rút gọn của

các nhóm phương pháp. Kết quả phân nhóm là cơ sở để đánh giá các phương

pháp rút gọn thuộc tính. Kết quả này được công bố trong công trình [CT1].

(2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ chắc

chắn, độ nhất quán, độ hỗ trợ). Nghiên cứu sự thay đổi giá trị các độ đo đề xuất

trên các tập rút gọn của bốn nhóm phương pháp. Trên cơ sở đó, lựa chọn và

đánh giá các phương pháp rút gọn thuộc tính trong các nhóm dựa trên tiêu chuẩn

khả năng phân lớp của tập rút gọn. Kết quả này được công bố trong công trình

[CT2].

(3) Theo hướng tiếp cận rút gọn dữ liệu, luận án đề xuất kỹ thuật chọn

tập đối tượng đại diện cho bài toán rút gọn thuộc tính trong hệ thông tin

không đầy đủ và bảng quyết định không đầy đủ nhằm giảm thiểu thời gian

thực hiện các thuật toán tìm tập rút gọn trên các bảng quyết định có dung

lượng dữ liệu lớn. Kết quả này được công bố trong công trình [CT3].

(4) Đề xuất phương pháp mới rút gọn thuộc tính sử dụng lượng thông tin

mở rộng. Lượng thông tin mở rộng được xây dựng dựa trên khoảng cách Jaccard

giữa hai tập hợp hữu hạn. Chứng minh phương pháp đề xuất sử dụng lượng

thông tin mở rộng thuộc Nhóm 2. Kết quả này được công bố trong công trình

[CT5].

104

(5) Đề xuất phương pháp mới rút gọn thuộc tính sử dụng hàm quan hệ.

Hàm quan hệ được xây dựng theo ma trận quan hệ dựa trên tiếp cận ma trận

phân biệt trong lý thuyết tập thô truyền thống. Chứng minh phương pháp đề xuất

sử dụng hàm quan hệ cũng thuộc Nhóm 2. Kết quả này được công bố trong công

trình [CT4].

2) Hướng phát triển của luận án:

Tiếp tục nghiên cứu các phương pháp rút gọn thuộc tính trên bảng quyết

định không đầy đủ mới hiệu quả hơn.

Tiếp tục nghiên cứu và giải quyết bài toán rút gọn thuộc tính trong

trường hợp bổ sung và loại bỏ tập đối tượng, tập thuộc tính theo hướng tiếp

cận tính toán gia tăng bằng nhiều độ đo khác nhau nhằm tìm kiếm phương

pháp hiệu quả.

105

DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ

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

CT2 Nguyễn Long Giang, Vũ Văn Định, Nghiên cứu sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn của bảng quyết định không đầy đủ, Kỷ yếu Hội nghị khoa học Công nghệ Quốc gia lần thứ VI - Nghiên cứu cơ bản và ứng dụng CNTT - FAIR6, Huế, 20-21/06/2013, Tr. 394-402.

CT3 Nguyễn Long Giang, Vũ Văn Định, “Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính trong hệ thông tin không đầy đủ”, Kỷ yếu Hội nghị khoa học Công nghệ Quốc gia lần thứ VII - Nghiên cứu cơ bản và ứng dụng CNTT - FAIR7, Thái Nguyên, 20-21/06/2014, Tr. 51- 59.

CT4 Vu Van Dinh, Nguyen Long Giang, Duc Thi Vu, Generalized Discernibility Function based Attribute Reduction in Incomplete Decision Systems, Serdica Journal of Computing 7 (2013), Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, No 4, 2013, pp. 375-388.

CT5 Vũ Văn Định, Vũ Đức Thi, Ngô Quốc Tạ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”, Chuyên san các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT, Tạp chí thông tinm khoa học công nghệ của bộ thông tin &Truyền thông Kỳ 3, Tập V-2, số 14(34), 2015.

106

TÀI LIỆU THAM KHẢO

[1] Hoàng Thị Lan Giao (2007), “Khía cạnh đại số và lôgic phát hiện luật

theo tiếp cận tập thô”, Luận án Tiến sĩ Toán học, Viện Công Nghệ

Thông Tin.

[2] Nguyễn Long Giang (2012), “Nghiên cứu các phương pháp khai phá

dữ liệu theo tiếp cận lý thuyết tập thô”, Luận án Tiến sĩ Toán học, Viện

Công Nghệ Thông Tin.

[3] Phùng Thị Thu Hiền (2014), “Nghiên cứu rút gọn tập thuộc tính trong

hệ quyết định giá trị tập”, Luận án Tiến sĩ Toán học, Học viện kỹ thuật

quân sự.

[4] Nguyễn Long Giang, Nguyễn Thanh Tùng, Vũ Đức Thi, “Một phương

pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ 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.

[5] Nguyễn Long Giang, Vũ Đức Thi (2011), “Thuật toán tìm tất cả các rút

gọn trong bảng quyết định”, Tạp chí Tin học và Điều khiển học, T.27, S.3,

tr. 199-205.

[6] Nguyễn Long Giang, Vũ Văn Định,“Chọn tập đối tượng đại diện cho

bài toán rút gọn thuộc tính trong hệ thông tin không đầy đủ”,Kỷ yếu

Hội nghị khoa học Công nghệ Quốc gia lần thứ VII-Nghiên cứu cơ bản

và ứng dụng CNTT-FAIR7,Thái Nguyên, 20-21/06/2014,Tr.51-59.

[7] Nguyễn Long Giang, Vũ Văn Định, “Nghiên cứu sự thay đổi giá trị

các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn

của bảng quyết định không đầy đủ”, Kỷ yếu Hội nghị khoa học Công

nghệ Quốc gia lần thứ VI - Nghiên cứu cơ bản và ứng dụng CNTT -

FAIR6, Huế, 20-21/06/2013, Tr. 394-402.

107

Tài liệu tiếng Anh

[8] Andrzej Skowron and Rauszer C (1992), “The Discernibility Matrices

and Functions in Information Systems”, Interlligent Decision

Support, Handbook of Applications and Advances of the Rough Sets

Theory, Kluwer, Dordrecht, pp. 331-362.

[9] Chen D.G, Zhao S.Y., Zhang L., Yang Y.P. and Zhang X. (2011),

“Sample pair selection for attribute reduction with rough set”, IEEE

Transaction on Knowledge and Data Engineering, 29 March 2011.

[10] Chin K.S., Liang J.Y. and Dang C.Y. (2003), “Rough Set Data

Analysis Algorithms for Incomplete Information Systems”,

Proceedings of the 9th international conference on Rough sets, fuzzy

sets, data mining, and granular computing, RSFDGrC'03, pp. 264-

268.

[11] Ge H., Li L.S and Yang C.J. (2009), “Improvement to Quick

Attribution Reduction Algorithm”, Journal of Computers, Vol.30,

No.2, pp. 308-312.

[12] Grzymala-Busse J.W (2011), “Mining Incomplete Data - A Rough Set

Approach”, RSKT 2011: 1-7.

[13] Hu X.H. and Cercone N. (1995), “Learning in relational databases: a

rough set approach”, International Journal of computational intelligence,

pp. 323-338.

[14] Hu X.H., Lin T.Y. and Han J.C. (2004), “A new rough sets model based

on database systems”, Fundamenta Informaticae, 59(1), pp. 135-152 .

[15] Huang B., He X. and Zhou X.Z. (2004), “Rough Computational

methods based on tolerance matrix”, Acta Automatica Sinica, Vol. 30,

Vab. 2004, pp. 363-370.

[16] Huang B., Li H. X. and Zhou X. Z. (2005), “Attribute Reduction

108

Based on Information Quantity under Incomplete Information

Systems”, Systems Application Theory & Practice, Vol. 34, pp. 55-60.

[17] Huasheng ZOU, Changsheng ZHANG, “Efficient Algorithm for

Knowledge Reduction in Incomplete Information System”, Journal of

Computational Information Systems 8: 6, 2012, pp. 2531-2538.

[18] Kryszkiewicz M. (1998), “Rough set approach to incomplete

information systems”, Information Science, Vol. 112, pp. 39-49.

[19] Lang G. M., Lia Q. G., Data compression of dynamic set-valued

information systems, CoRR abs/1209.6509, 2012.

[20] Li X.H. and Shi K.Q. (2006), “A knowledge granulation-based

algorithm for attribute reduction under incomplete information

systems”, Computer Science, Vol. 33, pp. 169-171.

[21] Li J.H. and Shi K.Q. (2006), “A algorithm for attribute reduction

based on knowledge granularity”, Computer Applications, Vol. 26,

No. 6, pp. 76-77.

[22] Li X.H. and Shi K.Q. (2006), “A knowledge granulation-based

algorithm for attribute reduction under incomplete information

systems”, Computer Science, Vol. 33, pp. 169-171.

[23] Liang J.Y. and Qian Y.H. (2006), “Axiomatic approach of knowledge

granulation in information system”, Lecture Notes in Artificial

Intelligence 4304, pp. 1074-1078.

[24] Liang J.Y. and Qian Y.H. (2008), “Information granules and entropy

theory in information systems”, Information Sciences, Vol. 51, pp. 1-

18.

[25] Liu Y., Xiong R. and Chu J. (2009), “Quick Attribute Reduction

Algorithm with Hash”, Chinese Journal of Computers, Vol.32, No.8,

pp. 1493-1499.

[26] Long Giang Nguyen, “Metric Based Attribute Reduction in Decision

109

Tables”, Federated Conference on Computer Science and Information

System (FEDCSIS), Wroclaw, Poland, IEEE, 2012, pp. 311-316.

[27] 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, 2013, pp. 99-

110.

[28] Long Giang Nguyen, Van Dinh Vu, “Relationships Among the

Concepts of Reduct in Incomplete Decision Tables”, Frontiers in

Artificial Intelligence and Applications, Volume 252: Advanced

Methods and Technologies for Agent and Multi-Agent Systems, IOS

Press, 2013, pp. 417-426.

[29] Liang J.Y. and Xu Z.B. (2002), “The algorithm on knowledge

reduction in incomplete information systems”, International Journal

of Uncertainty, Fuzziness and Knowledge-Based Systems 10 (1), pp.

95-103.

[30] Luo P., He Q. and Shi Z.Z. (2005), “Theoretical study on a new

information entropy and its use in attribute reduction”, ICCI, pp. 73-79.

[31] Pawlak Z. (1991), Rough sets: Theoretical Aspects of Reasoning

About Data, Kluwer Aca-demic Publishers.

[32] Pawlak Z. (1998), “Rough set theory and its applications to data

analysis”, Cybernetics and systems 29, pp. 661-688.

[33] Qian Y. H. , Dang C. Y., Liang J. Y., Zhang H. Y., Ma J. M., “On the

evaluation of the decision performance of an incomplete decision

table”, Data & Knowledge Engineering 65, 2008, pp. 373–400.

[34] Qian Y.H. and Liang J.Y. (2006), “Combination Entropy and

110

Combination Granulation in Incomplete Information System”, RSKT

2006, pp. 184-190.

[35] Qian Y.H. and Liang J.Y. (2008), “New method for measuring

uncertainty in incomplete information systems”, International Journal

of Uncertainty, Fuzziness and Knowledge-Based Systems.

[36] Qian Y.H., Liang J.Y., Li D.Y., Zhang H.Y. and Dang C.Y. (2008),

“Measures for Evaluating The Decision Performace of a Decision

Table in Rough Set Theory”, Information Sciences, Vol.178, pp.181-

202.

[37] Renpu Li, Dao Huang, “Reducts in incomplete decision tables”,

Proceedings of the First international conference on Advanced Data

Mining and Applications, ADMA’05, 2005, pp. 165-174.

[38] R.López de Mántaras (1991), “A distance-based attribute selection

measure for decision tree induction”, Machine Learning Vol. 6, pp.81-

92.

[39] Skowron A., Rauszer C., The Discernibility Matrices and Functions

in Information systems, Interlligent Decision Support, Handbook of

Applications and Advances of the Rough Sets Theory, Kluwer,

Dordrecht, 1992, pp. 331-362.

[40] The UCI machine learning repository,

http://archive.ics.uci.edu/ml/datasets.html

[41] Vu Van Dinh, Nguyen Long Giang, Duc Thi Vu, "Generalized

Discernibility Function based Attribute Reduction in Incomplete

Decision Systems", Serdica Journal of Computing 7 (2013), Institute

of Mathematics and Informatics, Bulgarian Academy of Sciences, No

4, 2013, pp. 375-388.

[42] Wang B.Y. and Zhang S.M. (2007), “A Novel Attribute Reduction

111

Algorithm Based on Rough Set and Information Entropy Theory”,

2007 International Conference on Computational Intelligence and

Security Workshops, IEEE CISW, pp.81-84.

[43] Wang C.R. and OU F.F. (2008), “An Attribute Reduction Algorithm

in Rough Set Theory Based on Information Entropy”, 2008

International Symposium on Computational Intelligence and Design,

IEEE ISCID, pp. 3-6.

[44] Wang C. Z., Wua C. X., Chenb D. G., Duc W. J., Some properties of

relation information systems under homomorphisms, Applied

Mathematics Letters 21, 2008, pp. 940–945.

[45] Wang G.Y. (2001), “Algebra view and information view of rough sets

theory”, In: Dasarathy BV,editor. Data mining and knowledge discovery:

Theory, tools, and technology III, Proceedings of SPIE, pp. 200-207.

[46] Wang G.Y. (2003), “Rough reduction in algebra view and information

view”, International Journal of Intelligent System 18, pp. 679-688.

[47] Wang G.Y., Yu H. and Yang D.C. (2002), “Decision table reduction based

on conditional information entropy”, Journal of Computers, Vol. 25 No. 7,

pp. 759-766.

[48] Wang G.Y., Yu H., Yang D.C. and Wu Z.F. (2001), “Knowledge

Reduction Based on Rough Set and Information Entropy”, Proc. Of the

World Multi-conference on Systemics, Cybernetics and Informatics,

Orlando, Florida, pp. 555-560.

2

/

,

[49] Xu Z.Y., Liu Z.P., Yang B.R. and Song W. (2006), “A quick attribute

 Max O C U O C U C





reduction algorithm with complexity of ”,



 

Journal of Computers, Vol.29, No.3, pp. 391-399.

[50] Yao Y.Y., Zhao Y., Wang J., On reduct construction algorithms, Proceedings of International Conference on Rough Sets and

112

Knowledge Technology, 2006, pp. 297-304.

[51] Ye D.Y. and Chen Z.J. (2002), “A new discernibility matrix and

computation of a core”, Acta Electronica Sinica, Vol. 30, No. 7, pp.

1086-1088.

[52] Y. Leung, D.Y. Li, Maximal consistent block technique for rule acquisition in incomplete information systems, Information Sciences 153 (2003) 85–106.

[53] Zadeh L.A. (1997), “Towards a theory of fuzzy information

granulation and its centrality in human reasoning and fuzzy logic”,

Fuzzy Sets and System, 90, pp. 111-127.

[54] Zhao M., Luo K. and Qin Z. (2008), “Algorithm for attribute

reduction based on granular computing”, Computer Engineering and

Applications, Vol. 44, No. 30, pp. 157-159.

[55] Zhou, X.Z., Huang, B., “Rough Set-based Attribute Reduction under

Incomplete Information Systems”, Journal of Nanjing University of

Science and Technology, 27(2003), pp. 630-635.

[56] Zuqiang Meng, Zhongzhi Shi, “A fast approach to attribute reduction

in incomplete decision systems with tolerance relation-based rough

sets”, Information Sciences, Vol. 179, 2009, pp. 2774-2793.