i

LỜI CAM ĐOAN
Tôi xin cam đoan luận án này là cơng trình
nghiên cứu của riêng tơi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của
các đồng tác giả trước khi đưa vào luận án. Các kết
quả được trình bày trong luận án là mới, các số liệu
là trung thực và chưa từng được ai cơng bố trong
các cơng trình nào khác./.

Nghiên cứu sinh


ii

LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình của PGS.TS
Nguyễn Bá Tường, người mà từ đó tác giả đã học được nhiều điều quí giá. Tác giả
cũng đã nhận được sự hướng dẫn và sự quan tâm giúp đỡ về nhiều mặt, cùng với
những đòi hỏi nghiêm khắc của PGS.TS Hà Quang Thụy. Tác giả xin bày tỏ lòng
biết ơn sâu sắc và chân thành tới những người Thầy đã giúp tác giả hoàn thành
những mục tiêu đặt ra của luận án.
Tác giả xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học
thuộc: Học viện Kỹ thuật Quân sự, Trường Đại học Công nghệ (đặc biệt là Phịng
Thí nghiệm Cơng nghệ Tri thức - KTLab) - Đại học Quốc gia Hà Nội, Trường Đại
học Kinh tế Kỹ thuật Công nghiệp đã giúp đỡ về chuyên môn và tạo điều kiện thuận
lợi cho tác giả trong suốt thời gian học tập và nghiên cứu.
Tác giả cũng xin bày tỏ lòng biết ơn đến các bạn đồng nghiệp đã giúp đỡ và có
những trao đổi, chia sẻ những kinh nghiệm về chun mơn, có nhiều ý kiến đóng
góp q báu cho tác giả trong quá trình nghiên cứu.

Tác giả mãi biết ơn những người thân, đặc biệt là chồng và các con, đã ln
chia sẻ mọi khó khăn và là chỗ dựa vững chắc về tinh thần và tạo mọi điều kiện cho
tác giả trong suốt thời gian hoàn thành luận án.


iii

MỤC LỤC
LỜI CẢM ƠN.............................................................................................................ii
DANH MỤC CÁC THUẬT NGỮ............................................................................vi
BẢNG KÝ HIỆU, TỪ VIẾT TẮT...........................................................................vii
DANH MỤC BẢNG.................................................................................................ix
DANH MỤC HÌNH VẼ..............................................................................................x
MỞ ĐẦU.....................................................................................................................1
Chương 1. LÝ THUYẾT TẬP THƠ VÀ CÁC MỞ RỘNG...............................................9
1.1.............................................................................................Hệ thơng tin và tập thô
9
1.1.1.Hệ thông tin....................................................................................................9
1.1.2. Quan hệ không phân biệt được...........................................................................10
1.1.3.Các tập xấp xỉ...............................................................................................12
1.1.4.Các tính chất của xấp xỉ...............................................................................15
1.1.5.Độ chính xác của xấp xỉ...............................................................................16
1.1.6.Bảng quyết định...........................................................................................16
1.1.7.Quan hệ dung sai..........................................................................................18
1.2.............................................................................................Hệ thông tin giá trị tập
19
1.2.1.Khái niệm.....................................................................................................19
1.2.2.Quan hệ dung sai trong hệ thông tin giá trị tập............................................20
1.2.3.Bảng quyết định giá trị tập...........................................................................21
1.2.4.Tập thô theo quan hệ dung sai.....................................................................21

1.3....................................................................................................................Kết luận
22
Chương 2. RÚT GỌN THUỘC TÍNH THEO LÝ THUYẾT TẬP THƠ..........................24
2.1.......................................................................................................Giới thiệu chung
24
2.2......................................................................Rút gọn thuộc tính trong hệ thơng tin
25
2.2.1.Tập rút gọn và tập lõi...................................................................................25


iv
2.2.2.Ma trận phân biệt và hàm phân biệt.............................................................30
2.2.3.Phụ thuộc xấp xỉ...........................................................................................33
2.2.3.1. Hàm thành viên thô..................................................................................34
2.2.3.2. Độ phụ thuộc xấp xỉ.................................................................................35
2.3. Rút gọn thuộc tính trong hệ thơng tin giá trị tập...........................................................35
2.3.1. Tập rút gọn trong hệ thông tin (bảng quyết định) giá trị tập..........................36
2.3.2. Ma trận phân biệt..........................................................................................36
2.3.3. Rút gọn thuộc tính sử dụng đối tượng đại diện..............................................38
2.4.Kết luận.................................................................................................................40
Chương 3. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP SỬ
DỤNG HÀM PHÂN BIỆT THEO BẢNG PHÂN BIỆT NGẪU NHIÊN
.........................................................................................................................................
42
3.1.Cơ sở lý thuyết......................................................................................................42
3.1.1. Hàm phân biệt mở rộng.................................................................................42
3.1.2. Bảng phân biệt ngẫu nhiên...........................................................................44
3.1.3.Bảng ngẫu nhiên dung sai............................................................................49
3.1.4. Dàn giá trị thuộc tính.....................................................................................54
3.2. Thuật tốn tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập............57

3.2.1. Thuật tốn 3.1. tìm tập rút gọn thuộc tính GMDSDT....................................57
3.2.2. Độ phức tạp thuật tốn GMDSDT.................................................................58
3.2.3. Ví dụ minh họa.............................................................................................58
3.3. Thực nghiệm thuật toán GMDSDT.............................................................................61
3.3.1. Cài đặt thuật toán..........................................................................................62
3.3.2. Chuẩn bị số liệu thực nghiệm.............................................................................62
3.3.3. Thi hành thực nghiệm thuật toán...................................................................62
3.4.Thuật toán tìm tập xấp xỉ trong hệ thơng tin giá trị tập.............................................65
3.4.1. Đặt vấn đề..........................................................................................................65
3.4.2. Thuật tốn tìm tập xấp xỉ dưới và xấp xỉ trên VASDT...............................66


v
3.4.3. Độ phức tạp của thuật tốn VASDT..............................................................66
3.4.4. Ví dụ minh họa thuật tốn tìm tập xấp xỉ......................................................67
3.5.Kết luận.................................................................................................................68
Chương 4. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP SỬ
DỤNG HÀM PHÂN BIỆT THEO MA TRẬN PHÂN BIỆT MỞ RỘNG
.........................................................................................................................................
70
4.1.Chọn mẫu đại diện cho bài tốn tìm tập rút gọn......................................................70
4.1.1. Đặt vấn đề..........................................................................................................70
4.1.2. Chọn tập đối tượng đại diện trong hệ thông tin giá trị tập..............................71
4.1.2.1. Cơ sở lý thuyết.........................................................................................71
4.1.2.2. Thuật toán chọn đối tượng đại diện trên hệ thơng tin giá trị tập..............73
4.1.2.3. Ví dụ minh họa.........................................................................................74
4.1.3. Chọn tập đối tượng đại diện trong bảng quyết định giá trị tập.......................75
4.1.3.1. Cơ sở lý thuyết.........................................................................................75
4.1.3.2. Thuật toán chọn đối tượng đại diện trên bảng quyết định giá trị tập.......78
4.1.3.3. Ví dụ minh họa.........................................................................................79

4.2.Rút gọn thuộc tính trong bảng quyết định giá trị tập sử dụng hàm phân biệt mởrộng.80
4.2.1. Cơ sở lý thuyết..............................................................................................80
4.2.2. Thuật tốn tìm tập rút gọn trong bảng quyết định giá trị tập sử dụng hàm
phân biệt mở rộng.............................................................................................85
4.2.3. Đánh giá độ phức tạp của thuật tốn RGDSDT.............................................86
4.2.4. Ví dụ minh họa thuật tốn RGDSDT.................................................................87
4.3.Rút gọn thuộc tính trong bảng quyết định giá trị tập khi bổ sung và loại bỏ thuộc tính 89
4.3.1. Cơ sở lý thuyết..............................................................................................89
4.3.2. Một số thuật tốn gia tăng tìm tập rút gọn thuộc tính RSDTAAS và RSDTDA. 95

4.3.3. Đánh giá độ phức tạp của các thuật toán RSDTAAS và RSDTDAS.............96
4.3.4. Ví dụ minh họa thuật tốn RSDTAAS và RSDTDAS...................................97
4.4. Thực nghiệm thuật toán RGDSDT.............................................................................100


vi
4.4.1. Cài đặt thuật toán RGDSDT........................................................................100
4.4.2. Thi hành thực nghiệm thuật toán RGDSDT.................................................100
4.5.Kết luận chương 4................................................................................................102
KẾT LUẬN VÀ KIẾN NGHỊ........................................................................................103
DANH MỤC CÁC CƠNG TRÌNH ĐÃ CƠNG BỐ.......................................................105
TÀI LIỆU THAM KHẢO..............................................................................................106


vii

DANH MỤC CÁC THUẬT NGỮ
Thuật ngữ tiếng Việt

Thuật ngữ tiếng Anh


Bảng ngẫu nhiên dựa trên quan hệ dung sai

Tolerance Based Contingency Table

Bảng phân biệt

Contingency Table

Bảng quyết định

Decision Table

Bảng quyết định giá trị tập

Set valued Decision Information System

Hàm phân biệt

Discernibility Function

Hệ thông tin

Information System

Hệ thông tin đầy đủ

Complete Information System

Hệ thông tin giá trị tập


Set valued Information System

Hệ thông tin không nhất quán

Inconsistent Information System

Ma trận không phân biệt được

Indiscernibility Matrix

Quan hệ dung sai

Tolerance Relation

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

Indiscernibility Relation

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

Attribute Reduction

Tập lõi

Core

Tập rút gọn

Reduct


Tập thơ

Rough Set

Xấp xỉ dưới

Lower Approximation

Xấp xỉ trên

Upper Approximation


viii

BẢNG KÝ HIỆU, TỪ VIẾT TẮT
Ký hiệu, từ viết tắt
S  U, A,V , f 
T  U,C  D,V , f

Diễn giải
Hệ thông tin



Bảng quyết định

IS  U, A,V , f 


Hệ thông tin giá trị tập

DS  (U,C d,V , f )

Bảng quyết định giá trị tập

|X|

u a

Số phần tử (lực lượng) của tập X
Giá trị của đối tượng u tại thuộc tính a

INDB

Quan hệ B  khơng phân biệt

u B

Lớp tương đương chứa u của quan hệ INDB

U /B

COVERU 

Phân hoạch của U sinh bởi tập thuộc tính B
Tập tất cả các phủ của U

B (u)


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

BX

B  xấp xỉ dưới của X trong hệ thông tin

BX
BNB  X 

B  xấp xỉ trên của X trong hệ thông tin

POSB  D 

B  miền dương của D trong hệ thông tin

TB

Quan hệ dung sai của tập thuộc tính B

TB (X )

Xấp xỉ trên của X trong hệ thông tin giá trị tập

TB (X )

Xấp xỉ dưới của X trong hệ thông tin giá trị tập

BNDT ( X )

Miền biên của X trong hệ thông tin giá trị tập


NEGT ( X )

Miền ngoài của X trong hệ thông tin giá trị tập

B

B

POST ( X
)

B  miền biên của X trong hệ thông tin

Miền dương của X trong hệ thông tin giá trị tập

B

CTB

Bảng ngẫu nhiên của tập thuộc tính B

TCTB
M DT

Bảng ngẫu nhiên dựa trên quan hệ dung sai
của tập thuộc tính B
Ma trận phân biệt

discern(A)


Hàm phân biệt


ix

ISP

Hệ thông tin giá trị tập đại diện

DSP

Bảng quyết định giá trị tập đại diện

UP

Tập đối tượng đại diện của hệ thông tin giá trị tập

RP

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

RM

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


RDF

Tập rút gọn dựa trên hàm phân biệt mở rộng

RCF

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


x

DANH MỤC BẢNG
Bảng 1.1. Một ví dụvềhệthơng tin.............................................................................10
Bảng 1.2. Bảng quyết định vềbệnh cúm...................................................................17
Bảng 1.3. Hệthông tin giá trị tập..............................................................................19
Bảng 2.1. Bảng rút gọn thứ nhất của hệ thống bệnh cúm R1.......................................27
Bảng 2.2. Bảng rút gọn thứhai của hệ thống bệnh cúm R2..........................................28
Bảng 2.3. Ma trận phân biệt được xây dựng từBảng 1.2.........................................31
Bảng 2.4. Ma trận phân biệt của bảng quyết định giá trị tập được xây dựng từBảng 1.335
Bảng 3.1. Bảng phân biệt ngẫu nhiên biểu diễn giá trị tập thuộc tính............................49
Bảng 3.2. Minh họa giá trị của hàm phân biệt.........................................................54
Bảng 3.3. Bảng quyết định giá trị tập gồm 4 cột thuộc tính (a1, a2 , a3, a4 ).........................59
Bảng 3.4. Kết quả thực hiện Thuật toán GMDSDT.................................................64
Bảng 3.5. Tập rút gọn của Thuật toán GMDSDT....................................................64
Bảng 3.6. Bảng quyết định giá trị tập gồm 4 cột thuộc tính điều kiện và cột d X.......................................67
Bảng 4.1. Bảng quyết định giá trị tập......................................................................74
Bảng 4.2. Hệthông tin giá trị tập đại diện từBảng 4.1.............................................75
Bảng 4.3. Bảng quyết định giá trị tập đại diện từBảng 4.1............................................79
Bảng 4.4. Bảng quyết định giá trị tập khi bổsung a5,a6........................................90
Bảng 4.5. Kết quả thực hiện Thuật toán RGDSDT và Thuật toán GMDSDT................100

Bảng 4.6. Tập rút gọn của Thuật toán RGDSDTvà Thuật toán GMDSDT...................101


xi

DANH MỤC HÌNH VẼ
Hình 3.1. Cấu trúc dàn của bảng quyết định giá trị tập................................................56
Hình 3.2. Minh họa các thuật tốn tìm tập rút gọn.......................................................63
Hình 3.3. Minh họa thuật tốn sửdụng hàm phân biệt..................................................63


1

MỞ ĐẦU
Tính cấp thiết của đề tài
Lý thuyết tập thơ được Zdzislaw Pawlak đề xuất vào năm 1982 [36, 38] mở ra
một tiếp cận mới về tính khơng chắc chắn (uncertainty). Xuất phát điểm của lý
thuyết tập thô là khái niệm hệ thông tin (information system) được sử dụng để biểu
diễn dữ liệu có được về miền ứng dụng. Một hệ thông tin [35] là một bộ bốn
S  U, A,V , f

 bao gồm một tập (vũ trụ) gồm hữu hạn các đối tượng U

(U 

) ,

một tập hữu hạn các thuộc tính A của các đối tượng ( A  , một tập hữu hạn các
giá trị V (V), và một hàm thông tin f : U  A  V. Tương ứng với mỗi thuộc
tính a 

A

là tập giá trị tương ứng Va   f (u, a) V ,u U. Trực quan hóa, một hệ

thơng tin được trình bày dưới dạng một bảng hai chiều với các hàng là các đối
tượng u trong U (số lượng hàng là ||U||), các cột là các thuộc tính a trong A (số cột
là
||A||) và phần tử tại hàng u, cột a là giá trị f(u,a). Khái niệm hệ thông tin làm nền
tảng của một loạt khái niệm như tập sơ cấp (elementary set hay atom), tập hợp
thành (composed set, cịn được gọi là tập mơ tả được), bảng quyết định (decision
table, còn được gọi là hệ quyết định: decision system), quan hệ không phân biệt
được (indiscernibility relation), không gian xấp xỉ (approximation space), tập xấp
xỉ (approximation set) v.v. cùng với một tập phong phú các tính chất liên quan [36,
37, 38, 39, 40, 41, 42] làm nền tảng cho các tiếp cận đại số và logic cũng như một
số tiếp cận tốn học đối với tính khơng chắc chắn. Theo Zdzislaw Pawlak và
Andrzej Skowron [42], Andrzej Skowron và cộng sự [54], lý thuyết tập thơ có ưu
điểm chính là không cần bất kỳ thông tin sơ bộ và bổ sung nào về dữ liệu như phân
bố xác suất trong thống kê, chuyển nhượng xác suất cơ bản trong lý thuyết chứng
minh, một mức hàm thành viên hoặc giá trị khả năng trong lý thuyết tập mờ. Chính
từ ưu điểm đó, lý thuyết tập thơ giữ một vị trí nền tảng quan trọng trong trí tuệ nhân
tạo (artificial intelligence) và khoa học nhận thức (cognitive sciences), đặc biệt
trong một loạt lĩnh vực nghiên cứu như học máy (machine learning), các hệ thống
thông minh (intelligent systems), lập luận quy nạp (inductive reasoning), nhận dạng


2

mẫu (pattern recognition), lý thuyết bộ phận-toàn bộ (mereology), phát hiện tri thức
(knowledge discovery), phân tích quyết định (decision analysis), và các hệ chuyên
gia (expert systems) [7, 38, 40, 42, 55, 56, 58]. Trong thời đại kinh tế tri thức hiện

nay, tầm quan trọng của các lĩnh vực nghiên cứu trên đây ngày càng được nâng cao,
tương ứng, lý thuyết tập thô ngày càng thu hút sự quan tâm của cộng đồng hàn lâm công nghiệp. Hiệp hội tập thô thế giới (The International Rough Set Society - IRSS1)
đã được thành lập từ năm 2005. IRSS bao gồm một số hiệp hội thành viên2, trong
đó Hiệp hội Tập thơ và Tính tốn mềm Trung Quốc (Rough Set and Soft Computing
Society, Chinese Association for AI3) là một hiệp hội thành viên điển hình nhất.
Trong lời tựa Kỷ yếu Hội nghị khoa học thế giới về Tập thơ và Các mơ hình hệ
thống thông minh mới nổi năm 2007 (The International Conference on Rough Sets
and Emerging Intelligent Systems Paradigms: RSEISP 2007) tưởng nhớ GS.
Zdzislaw Pawlak, Marzena Kryszkiewicz, và các cộng sự cho biết có hơn 4000 ấn
phẩm khoa học về tập thơ đã được cơng bố tới thời điểm đó. Lý thuyết tập thô và lý
thuyết tập mờ (Fuzzy Set Theory) do Zadeh L.A. đề xuất năm 1965 [72] là hai lý
thuyết điển hình nhất về các mơ hình biểu diễn tính không chắc chắn [22, 37].
Việc mở rộng lý thuyết tập thơ nhằm làm cho các khái niệm và mơ hình biểu
diễn tri thức dựa trên lý thuyết tập thô ngày càng phù hợp với miền ứng dụng cũng
ngày càng được mở rộng [24, 37, 42, 43, 54]. Theo Andrzej Skowron và cộng sự,
2013 [54], cộng đồng nghiên cứu quan tâm đặc biệt tới các tiếp cận mở rộng lý
thuyết tập thơ dựa trên tính tương tự (hay dung sai; similarity/tolerance based rough
sets), tập thô dựa trên quan hệ nhị phân (binary relation based rough sets), tập thô
lân cận và phủ (neighborhood and covering rough sets), tập thô trội (dominance
based rough sets), kết hợp tập thô và tập mờ (hybridization of rough sets and fuzzy
sets), v.v. Trong tiếp cận tập thô dựa trên tính tương tự, hệ thơng tin giá trị tập (setvalued informaton system [44], hay còn được gọi là "hệ thông tin đa trị": multi1

(truy nhập tháng 8/2013)

2

(8/2013)

3


(8/2013)


3

valued informaton system [11]/many-valued informaton system [10]) là một phương
án mở rộng có tính điển hình.
Hệ thơng tin giá trị tập là bộ bốn IS = (U, A, V, f), trong đó tập đối tượng U,
tập thuộc tính A, tập giá trị V có ý nghĩa như trong định nghĩa của hệ thơng tin, cịn
hàm thơng tin f nhận giá trị là một tập giá trị trong V (f: U  A  2V). Tương ứng
với việc mở rộng khái niệm hệ thông tin thành khái niệm hệ thông tin giá trị tập, các
khái niệm liên quan trong hệ thông tin cũng được mở rộng một cách tương ứng.
Trong lý thuyết tập thô giá trị tập, một số khái niệm và tính chất chưa có trong lý
thuyết tập được xuất hiện. Đáng chú ý là quan hệ dung sai [51] nhận được sự quan
tâm đặc biệt. Lý thuyết tập thô giá trị tập và ứng dụng của nó trở thành một chủ đề
nghiên cứu nhận được sự quan tâm đặc biệt của cộng đồng nghiên cứu. Nhiều cơng
trình nghiên cứu về lý thuyết tập thô giá trị tập và ứng dụng đã được công bố, chẳng
hạn như [8, 10, 15, 44, 45], đồng thời, các kết quả nghiên cứu - triển khai về tập thơ
giá trị tập cũng có xu hướng ngày càng tăng theo thời gian. Trong luận án này, thuật
ngữ "hệ thông tin" được dùng để chỉ hệ thơng tin theo định nghĩa ban đầu của
Zdzislaw Pawlak, cịn thuật ngữ "hệ thông tin giá trị tập" để chỉ hệ thông tin giá trị
tập.
Theo Zdzislaw Pawlak và Andrzej Skowron [42], Andrzej Skowron và cộng
sự [54], tiếp cận tập thô (i) cung cấp các thuật toán hiệu quả để phát hiện các mẫu
tiềm ẩn trong dữ liệu; (ii) xác định tập dữ liệu tối ưu (rút gọn dữ liệu: data reduction
hay ngắn gọn là reduction) và ước lượng tính quan trọng dữ liệu; (iii) sinh các tập
luật quyết định từ dữ liệu; (iv) hình thức hóa tính dễ hiểu; (v) giải thích đơn giản
hóa các kết quả thu được; và (vi) làm phù hợp nhiều thuật tốn của nó để xử lý song
song. Rút gọn thuộc tính (attribute reduction), một thành phần chủ chốt của rút gọn
dữ liệu, là một trong những bài toán ứng dụng quan trọng nhất của lý thuyết tập thơ.

Mục tiêu của rút gọn thuộc tính trong hệ thơng tin là tìm ra tập nhỏ nhất các
thuộc tính để phân tích dữ liệu mà vẫn giữ được hiệu năng (hoặc hầu hết hiệu năng)
như tập toàn bộ các thuộc tính [70]. Rút gọn thuộc tính vừa làm giảm khối lượng xử


4

lý dữ liệu do chỉ phải thao tác trên một khối lượng dữ liệu nhỏ hơn, vừa làm cho kết
quả thu được trở nên cô đọng và dễ hiểu hơn.
Theo Yiyu Yao và Yan Zhao [70], hai mơ hình rút gọn thuộc tính trong lý
thuyết tập thơ là mơ hình Pawlak và mơ hình xác suất. Tồn tại các phương pháp rút
gọn thuộc tính điển hình theo hai mơ hình này là các phương pháp dựa trên miền
dương [13, 31, 46, 57], các phương pháp sử dụng ma trận phân biệt [12, 47, 50, 68,
71], các phương pháp sử dụng các phép toán đại số quan hệ [21], các phương pháp
sử dụng entropy thông tin [29, 59, 60, 61, 63, 67, 68], các phương pháp sử dụng các
độ đo, điển hình là độ đo trong tính tốn hạt (granular computing) [6, 14, 15, 28, 53,
75], các phương pháp tích hợp lý thuyết tập thô với lý thuyết tập mờ [22, 24].
Trong hệ thông tin giá trị tập, các phương pháp tìm tập rút gọn thuộc tính
được hình thành dựa trên quan hệ dung sai [15, 51]. Theo hướng tiếp cận mơ hình
quan hệ dung sai, một số kết quả nghiên cứu đáng chú ý về rút gọn thuộc tính trên
bảng quyết định giá trị tập được công bố trong [8, 27, 44, 45, 64, 65, 66].
Trên thế giới, một số luận án tiến sỹ về rút gọn thuộc tính theo lý thuyết tập
thô đã được công bố. Dale E. Nelson, 2001 [32] trình bày nghiên cứu rút gọn thuộc
tính dựa trên khái niệm tập rút gọn và tập nhân để lựa chọn thuộc tính phân lớp mục
tiêu rada, bao gồm việc đề xuất một phương pháp và một thuật toán độ phức tạp đa
thức lựa chọn tập con thuộc tính thích hợp. Richard Jensen, 2005 [22] phát triển các
kỹ thuật mới rút gọn thuộc tính theo tiếp cận tập mờ-thơ mà vẫn giữ nguyên ngữ
nghĩa của dữ liệu, trong đó, độ đo mức độ quan trọng của các thuộc tính được đề
xuất. Neil S. Mac Parthalain, 2009 [34] đề xuất một kỹ thuật rút gọn thuộc tính dựa
trên tập mờ dung sai, ba kỹ thuật rút gọn thuộc tính dựa theo tập mờ-thô và áp dụng

các kỹ thuật này trong các phân lớp ảnh X-quang tại bệnh viện. Gần đây, Senan
Norhalina, 2013 [33] đề xuất một kỹ thuật lựa chọn thuộc tính dựa trên xấp xỉ tập
thơ sử dụng độ phụ thuộc cực đại giữa các thuộc tính để giải quyết bài toán phân
lớp âm thanh nhạc cụ Malaysia truyền thống. Kỹ thuật nói trên tìm ra tập thuộc tính
rút gọn tốt nhất gồm 17 thuộc tính từ 35 thuộc tính liên quan ban đầu.


5

Tại Việt Nam, một số luận án tiến sỹ về chủ đề rút gọn thuộc tính theo lý
thuyết tập thơ đã được hoàn thành. Hoàng Thị Lan Giao [2] đề nghị một số thuật
tốn heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất
quán, bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán
sử dụng ma trận phân biệt. Nguyễn Đức Thuần [5] đề nghị một thuật tốn heuristic
tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô. Nguyễn
Long Giang [1] đề nghị một thuật 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 đủ sử dụng metric.
Luận án này tập trung nghiên cứu vấn đề rút gọn thuộc tính trong lý thuyết tập
thơ, tập trung vào bài tốn rút gọn thuộc tính trong hệ thơng tin giá trị tập. Luận án
giải đáp các câu hỏi nghiên cứu sau đây:
 Những nội dung điển hình nào được quan tâm khi mở rộng lý thuyết tập thô
theo hướng hệ thông tin giá trị tập; lý thuyết tập thô theo hướng hệ thông tin giá trị
tập đưa đến các nội dung gì mới ?
 Bài tốn rút gọn thuộc tính trong lý thuyết tập thô (bao gồm cả các phương
án mở rộng của lý thuyết này) có nội dung ra sao; các giải pháp điển hình nào để
giải quyết bài tốn đó ?
 Hình thành các tiếp cận rút gọn thuộc tính trong lý thuyết tập thô giá trị tập
như thế nào ?
Trả lời cho các câu hỏi nghiên cứu trên đây, luận án trình bày các nội dung
nghiên cứu chính sau đây:

 Một nghiên cứu khái quát về lý thuyết tập thô, tập trung vào lý thuyết hệ
thông tin giá trị tập.
 Một nghiên cứu khái quát các tiếp cận điển hình rút gọn thuộc tính trong hệ
thơng tin và hệ thơng tin giá trị tập.
 Nghiên cứu một số mơ hình, kỹ thuật rút gọn thuộc tính trong hệ thơng tin
giá trị tập, trên cơ sở đó đề xuất một số thuật tốn rút gọn thuộc tính trong hệ thơng
tin giá trị tập.


6

Đối sánh các nội dung nghiên cứu được trình bày trên đây với nội dung
nghiên cứu của các luận án tiến sỹ trong và ngoài nước đã được giới thiệu, luận án
này có những điểm khác biệt.
Mục tiêu nghiên cứu của luận án là hoàn thành các nội dung nghiên cứu
chính nêu trên để giải đáp các câu hỏi nghiên cứu. Luận án tập trung nghiên cứu bài
toán rút gọn thuộc tính trong các phiên bản hệ thống thơng tin được quan tâm và đề
xuất được các thuật toán rút gọn thuộc tính mới. Mục tiêu cơ bản trên đây được cụ
thể hóa bằng các mục tiêu cụ thể sau đâu. Thứ nhất, cung cấp được một khái quát
song đủ tồn diện về lý thuyết tập thơ trong phạm vi xem xét bài tốn rút gọn thuộc
tính. Thứ hai, cung cấp được một khảo sát các phương pháp điển hình giải quyết bài
tốn rút gọn thuộc tính trong lý thuyết tập thô và lý thuyết tập thô giá trị tập. Thứ ba,
đề xuất được các thuật tốn tìm tập rút gọn thuộc tính dựa trên khái niệm bảng
quyết định giá trị tập.
Đối tượng nghiên cứu của luận án là bài tốn rút gọn thuộc tính trong bảng
quyết định giá trị tập như đã trình bày theo các vấn đề nghiên cứu của luận án.
Phạm vi nghiên cứu của luận án được giới hạn ở bài tốn rút gọn thuộc tính
trong bước tiền xử lý số liệu.
Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và có sử dụng
phương pháp nghiên cứu thực nghiệm.

Luận án có các đóng góp chính sau đây:
1. Cung cấp một kết quả nghiên cứu khái quát về lý thuyết tập thô, lý thuyết
tập thô giá trị tập. Kết quả nghiên cứu này được trình bày trong Chương 1 của luận
án.
2. Cung cấp một kết quả nghiên cứu khái quát về rút gọn thuộc tính trong lý
thuyết tập thơ, lý thuyết tập thơ giá trị tập. Kết quả nghiên cứu này được trình bày
trong Chương 2 của luận án. Luận án đưa ra các thay đổi nhỏ đối với các thuật tốn
trong hệ thơng tin [19, 69] thành các thuật toán tương ứng trong bảng quyết định
(các thuật toán 2.1-2.6-2.7).


7

3. Trên cơ sở kỹ thuật bảng ngẫu nhiên (contingency table) [56], luận án đề
xuất các thuật toán rút gọn thuộc tính (Generalized Maximal Discernibility
heuristic for Set valued Decision Tables: GMDSVDT) và thuật tốn tính xấp xỉ trên
- xấp xỉ dưới của một tập (Verifying upper and lower Approximation for Set valued
Decision Tables: VASDT) dựa trên hai cấu trúc dữ liệu mới là bảng ngẫu nhiên
tổng quát hóa (generalized contingency table) và các dàn giá trị thuộc tính (lattices
of attribute values) trong hệ thơng tin giá trị tập. Thuật tốn VASDT có độ phức tạp
tính tốn là O(m2) so với độ phức tạp tính tốn O(n 3) [74]. Kết quả nghiên cứu này
được cơng bố trong cơng trình số 1, phần “Danh mục các cơng trình của tác giả”.
và được trình bày trong Chương 3 của luận án.
4. Dựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu của cơng trình [27],
luận án đề xuất hai thuật toán lựa chọn tập đối tượng đại diện từ tập đối tượng ban
đầu cho bài tốn tìm tập rút gọn của hệ thông tin giá trị tập và bảng quyết định giá
trị tập. Luận án chứng minh 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 trong hệ thông tin và trong bảng quyết định giá trị là
tương đương (nghĩa là như nhau qua một song ánh), từ đó khẳng định tính đúng đắn
của phương pháp. Các thuật tốn chọn tập đối tượng đại diện có ý nghĩa quan trọng

trong bước tiền xử lý số liệu của bảng quyết định trước khi thực hiện các nhiệm vụ
khai phá dữ liệu. Các kết quả nghiên cứu này được công bố trong công trình số 2.
5. Trong lý thuyết tập thơng truyền thống, Skowron và Rauszer [52] đã đư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. Dựa trên cách tiếp
cận này, luận án đề xuất hai cấu trúc dữ liệu mới là hàm phân biệt mở rộng và ma
trận phân biệt mở rộng trong bảng quyết định giá trị tập. Hai cấu trúc dữ liệu mới
này là cơng cụ để xây dựng thuật tốn tìm tập rút gọn trên bảng quyết định giá trị
tập. Theo đó, Chương 4 đưa ra phương pháp thứ hai tìm tập rút gọn thuộc tính, cụ
thể luận án đề xuất ba thuật tốn mới tìm tập rút gọn thuộc tính (RGDSDT:
heuristic algorithm to find a Reduct based on Generalized Discernibility function in
Set-valued Decision Table, RSDTAAS: extended algorithm to find a Reduct in Setvalued Decision Table when Adding an Attribute Set, RSDTDAS: extended
algorithm to find a Reduct in Set-valued Decision Table when Deleting an Attribute


8

Set) khi bổ sung và loại bỏ tập thuộc tính trong bảng quyết định giá trị tập, đánh giá
độ phức tạp của từng thuật toán. Các kết quả nghiên cứu này được cơng bố trong
cơng trình số 3.
Bố cục của luận án gồm phần mở đầu và bốn chương nội dung (như trình bày
ở trên), phần kết luận và danh mục các tài liệu tham khảo.


9

Chương 1. LÝ THUYẾT TẬP THÔ VÀ CÁC MỞ RỘNG
Chương này được bắt đầu bằng việc giới thiệu các khái niệm cơ bản về hệ
thông tin, tập thô, bảng quyết định được Zdzislaw Pawlak đề xuất vào năm 1982
[36, 38, 54], các tính chất cơ bản của chúng, cùng một số khái niệm liên quan. Tiếp
theo, một mở rộng của hệ thông tin là hệ thông tin giá trị tập (Set-valued

Information System, cịn được gọi là "hệ thơng tin đa trị": Multi-valued Information
System) [15] cùng các khái niệm liên quan được trình bày. Đây là những kiến thức
nền tảng liên quan tới bài tốn rút gọn thuộc tính trong hệ thơng tin giá trị tập được
trình bày trong các chương tiếp theo.
1.1. Hệ thông tin và tập thô
1.1.1. Hệ thông tin
Một cách khơng hình thức, một hệ thơng tin là một tập dữ liệu được cho dưới
dạng bảng, trong đó mỗi hàng biểu diễn thông tin về một đối tượng, mỗi cột biểu
diễn thơng tin về một thuộc tính của các đối tượng trong tập dữ liệu. Một cách hình
thức, hệ thông tin được định nghĩa như sau.
Định nghĩa 1.1 [36]. (Hệ thông tin)
Hệ thông tin là một bộ bốn S  U, A,V , f  trong đó U là tập đối tượng là một
tập hữu hạn, khác rỗng các đối tượng (U còn được gọi là tập vũ trụ: the universe) và
A là tập thuộc tính là một tập hữu hạn, khác rỗng các thuộc tính; V là tập giá trị,
trong đó V  
V

aA

a

với Va là tập giá trị của thuộc tính a  A ; f là hàm thơng tin

f :U  A V, trong đó a  A, u U : f ( u,a )Va .

Với mỗi u U, a  A , dùng ký hiệu u  a  thay
cho
của đối tượng u tại thuộc tính a; rõ ràng là u(a)
Va


các thuộc
tính

f u,
a

để biểu thị giá trị

với mọi u U . Với một tập con

B  b1,b2 ,...,bk   A , ký hiệu bộ các giá trị { u  bi  |biB} là u  B  ; với

hai đối tượng u, vU, viết u  B   v  B  nếu u bi   v bi  :  i 1,..., k .