BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
======

TRẦN THỊ PHƢƠNG LIÊN

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 ĐỦ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ MÁY TÍNH

HÀ NỘI, 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
======

TRẦN THỊ PHƢƠNG LIÊN

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 ĐỦ VÀ ỨNG DỤNG
Chuyên ngành: Khoa Học Máy Tính
Mã số: 60480101

LUẬN VĂN THẠC SĨ MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS. Nguyễn Long Giang


MỤC LỤC
LỜI CẢM ƠN
LỜI CAM ĐOAN
MỤC LỤC .................................................................................................................. i
DANH MỤC CÁC THUẬT NGỮ ......................................................................... iii
DANH MỤC CÁC BẢNG ...................................................................................... iv
DANH MỤC CÁC HÌNH VẼ...................................................................................v
MỞ ĐẦU ....................................................................................................................1
Chƣơng 1. CÁC KHÁI NIỆM CƠ BẢN .................................................................4
1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống..........................................4
1.1.1. Hệ thông tin đầy đủ ...........................................................................................4
1.1.2. Bảng quyết định đầy đủ.....................................................................................7
1.1.3. Tập rút gọn và tập lõi ........................................................................................7
1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai .....................................8
1.2.1. Hệ thông tin không đầy đủ ................................................................................8
1.1.2. Bảng quyết định không đầy đủ .........................................................................9
Chƣơng 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG
BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ ............................................................11
2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định không đầy đủ .........11
2.1.1. Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính ............................11
2.1.2. Luật quyết định và các độ đo đánh giá hiệu năng ...........................................16
2.1.3. Lựa chọn, so sánh, đánh giá các phương pháp rút gọn thuộc tính ..................20
2.2. Xây dựng 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 .................................................................................................22
2.2.1. Xây dựng khoảng cách giữa hai tập thuộc tính ...............................................23
2.2.2. Phương pháp rút gọn thuộc tính sử dụng khoảng cách .................................. 27
2.2.3. Phân nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách ................32
Chƣơng 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .....................................33
3.1. Bài toán ..............................................................................................................33


Tolerance Rough Set

Hệ thông tin

Information System

Hệ thông tin đầy đủ

Complete Information System

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

Incomplete Information System

Bảng quyết định

Decision Table

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

Complete Decision Table

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

Incomplete Decision Table

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

Indiscernibility Relation


Distance


iv

DANH MỤC CÁC BẢNG

Bảng 1.1. Bảng thông tin về bệnh cúm ......................................................................6
Bảng 1.2. Bảng quyết định không đầ đủ về các xe hơi .............................................10
Bảng 2.1. Các phương pháp rút gọn thuộc tính trong công trình [3, 8, 14] ............13
Bảng 2.2. Bảng quyết định không đầy đủ về các xe hơi ...........................................17
Bảng 2.3. Bảng quyết định không đầy đủ về các xe hơi ...........................................30
Bảng 3.1. Kết quả thực hiện Thuật toán DBAR và Thuật toán IQBAR ....................36
Bảng 3.2. Tập rút gọn của Thuật toán DBAR và Thuật toán IQBAR.......................36
Bảng 3.3. Kết quả thực hiện Thuật toán DBAK và Thuật toán IQBAK trên các bộ số
liệu lớn.......................................................................................................................37
Bảng 3.4. Tập rút gọn tốt nhất của bộ số liệu Soybean-small.................................38
Bảng 3.5. Các luật phân lớp trên bảng quyết định rút gọn ......................................38


v

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

Hình 2.1. Mối liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ ......15
Hình 3.1. Kết quả rút gọn thuộc tính ........................................................................42
Hình 3.2. Kết quả sinh luật quyết định .....................................................................43


1



2
hiệu quả có ý nghĩa khoa học. Do đó, tôi chọn đề tài “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 đủ và ứng dụng”
2. Mục đích nghiên cứu (Các kết quả cần đạt đƣợc)
Mục đích của luận văn trước hết là tổng kết các kết quả nghiên cứu về lĩnh
vực rút gọn thuộc tính và trích lọc luật trong bảng quyết định không đầy đủ theo
tiếp cận mô hình tập thô dung sai. Trên cơ sở đó, luận văn đề xuất phương pháp rút
gọn thuộc tính dựa trên độ đo khoảng cách phân hoạch và ứng dụng phương pháp
vào bài toán chuẩn đoán bệnh dựa vào các triệu chứng thu thập được từ bệnh nhân.
3. Nhiệm vụ nghiên cứu
- Nắm bắt được các khái niệm cơ bản về lý thuyết tập thô truyền thống trên
hệ thông tin đầy đủ và mô hình tập thô dung sai trên hệ thông tin không đầy đủ
- Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và
trích lọc luật quyết định trong bảng quyết định không đầy đủ theo tiếp cận mô hình
tập thô dung sai, bao gồm phân nhóm các phương pháp, so sánh, đánh giá các
phương pháp dựa vào tập rút gọn…
- Xây dựng phương pháp rút gọn thuộc tính dựa vào khoảng cách phân
hoạch, đánh giá phương pháp đề xuất với các phương pháp đã có.
- Ứng dụng phương pháp vào việc giải quyết một bài toán cụ thể trong lĩnh
vực chuẩn đoán bệnh, bao gồm: phát biểu bài toán, cài đặt chương trình, thử nghiệm
chương trình, đánh giá kết quả thu được.
4. Đối tƣợng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Các bảng quyết định không đầy đủ (thiếu giá trị) với
kích thước trung bình và kích thước lớn trong lĩnh vực nghiên cứu và bảng quyết
định đầy đủ
- Phạm vi nghiên cứu: Nghiên cứu bài toán rút gọn thuộc tính trong bước tiền
xử lý dữ liệu của quá trình khai phá dữ liệu và khám phá tri thức.
5. Phƣơng pháp nghiên cứu

Chƣơng 1. CÁC KHÁI NIỆM CƠ BẢN
Chương này trình bày các khái niệm cơ bản về mô hình tập thô truyền thống
trên các hệ thông tin đầy đủ do Pawlak [10] đề xuất và mô hình tập thô dung sai trên
các hệ thông tin không đầy đủ do Kryszkiewicz [5] đề xuất. Các khái niệm cơ bản
này là kiến thức nền tảng để sử dụng cho các chương sau.
1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống
1.1.1. Hệ thông tin đầy đủ
Hệ thông tin đầy đủ, gọi tắt là hệ thông tin, là một bảng dữ liệu gồm p cột ứng
với p thuộc tính và n hàng ứng với n đối tượng. Một cách hình thức, hệ thông tin
được định nghĩa như sau.
Định nghĩa 1.1. Hệ thông tin là một bộ tứ IS  U , A,V , f  trong đó U là tập hữu hạn,
khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính; V 

Va với
aA

Va là tập giá trị của thuộc tính a  A ; f : U  A  Va là hàm thông tin, a  A, u U
f  u, a  Va .

Với mọi u U , a  A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a  u 
thay vì f  u, a  . Nếu B  b1 , b2 ,..., bk   A là một tập con các thuộc tính thì ta ký
hiệu bộ các giá trị bi  u  bởi B  u  . Như vậy, nếu u và v là hai đối tượng, thì ta viết
B  u   B  v  nếu bi  u   bi  v  với mọi i  1,..., k .

Xét hệ thông tin IS  U , A,V , f  , mỗi tập con các thuộc tính P  A xác định
một quan hệ hai ngôi trên U, ký hiệu là IND  P  , xác định bởi






BX  u U u B  X , BX  u U u B  X   .

Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập
BX bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính B. Từ

hai tập xấp xỉ nêu trên, ta định nghĩa các tập
BN B  X   BX  BX : B-miền biên của X , U  BX : B-miền ngoài của X.

B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X,
còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các
lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể viết lại
BX 

Y U / B Y  X  , BX  Y U / B Y  X  .

Trong trường hợp BN B  X    thì X được gọi là tập chính xác (exact set),
ngược lại X được gọi là tập thô (rough set).
Với B, D  A , ta gọi B-miền dương của D là tập được xác định như sau

 BX 

POSB ( D) 
X U / D

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






u3

Có

Rất cao

Có

u4

Không

Bình thường

Không

u5

Không

Cao

Không

u6

Không

Rất cao

3

4

5

6

7

8

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

4

2

5

7

3

6

8

u , u , u , u ,u , u , u , u 


6

7

Như vậy, các bệnh nhân u2 , u3 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.
Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là:

u1 , u2 , u3  , u4  , u5 , u7 , u6 , u8  .
Đặt X  {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u7  . Khi đó:
BX  u2 , u3  và BX  u2 , u3 , u5 , u6 , u7 , u8 . Như vậy, B-miền biên của X là tập

hợp BN B  X   u5 , u6 , u7 , u8  . Nếu đặt D = {Cảm cúm} thì
U / D   X1  u1, u4 , u5 , u8 ; X 2  u2 , u3 , u6 , u7  , BX1  u1 , u4  ; BX 2  u2 , u3  ,

 BX   u1 , u2 , u3 , u4  .

POS B ( D) 
X U / D


7
Với các khái niệm của tập xấp xỉ đối với phân hoạch U / B , mô hình tập thô
truyền thống phân chia các tập hợp thành bốn lớp cơ bản:
1) Tập X là B-xác định thô nếu BX   và BX  U .
2) Tập X là B-không xác định trong nếu BX   và BX  U .
3) Tập X là B-không xác định ngoài nếu BX   và BX  U .
4) Tập X là B-không xác định hoàn toàn nếu BX   và BX  U .
1.1.2. Bảng quyết định đầy đủ

2) r  R, POSRr ( D)  POSC ( D)
thì R là một tập rút gọn 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.
1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai
Mô hình tập thô truyền thống do Pawlak đề xuất [10] là công cụ hiệu quả để
giải quyết bài toán phân lớp trên các hệ thông tin đầy đủ dựa trên quan hệ tương
đương. Tuy nhiên trong thực tế, các hệ thông tin thường thiếu giá trị trên miền giá
trị của thuộc tính, gọi là các hệ thông tin không đầy đủ. Trong hệ thông tin không
đầy đủ, Kryszkiewicz [5] được xem là người đầu tiên mở rộng quan hệ tương
đương thành quan hệ dung sai và xây dựng mô hình tập thô mở rộng dựa trên quan
hệ dung sai, gọi là mô hình tập thô dung sai. Trong mục này, tôi trình bày các khái
niệm cơ bản về mô hình tập thô dung sai.
1.2.1. Hệ thông tin không đầy đủ
Xét hệ thông tin IS  U , A,V , f  , nếu tồn tại u U và a  A sao cho a  u 
thiếu giá trị thì IS được gọi là hệ thông tin không đầy đủ. Ta biểu diễn giá trị thiếu là
„*‟ và hệ thông tin không đầy đủ là IIS  U , A,V , f  .
Xét hệ thông tin không đầy đủ IIS  U , A,V , f  ), với tập thuộc tính P  A 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   '*' .


9
Quan hệ SIM  P  không phải là quan hệ tương đương vì chúng có tính phản xạ,
đối xứng nhưng không có tính bắc cầu. SIM  P  là một quan hệ dung sai (tolerance
relation), hay quan hệ tương tự (similarity relation) trên U. Theo [5],

PX  u U S P  u   X   

P



 u  u U 

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
BN P  X   PX  PX , và P-miền ngoài của X là tập U  PX .

Với các tập xấp xỉ được định nghĩa như trên, mô hình tập thô truyền thống
được mở rộng thành mô hình tập thô dung sai, nghĩa là mô hình tập thô dựa trên
quan hệ dung sai.
1.1.2. Bảng quyết định không đầy đủ
Xét bảng quyết định DS  U , C  D,V , f  , nếu tồn tại u U và c  C sao cho
c  u  thiếu giá trị thì DS được gọi là bảng quyết định không đầy đủ. Ta biểu diễn giá

trị thiếu là „*‟ và bảng quyết định không đầy đủ là IDS  U , C  D,V , f

 với

d  D, '*' Vd . Không mất tính chất tổng quát, giả thiết D chỉ gồm một thuộc tính

quyết định duy nhất d  .


10
Cho bảng quyết định không đầy đủ IDS  U , C  d  ,V , f  . Với B  C ,
u U ,  B (u)   f d  v  v  S B (u) gọi là hàm quyết định suy rộng, nếu | C (u) | 1 với

Thấp

Tốt

u2

Thấp

*

Đầy đủ

Thấp

Tốt

u3

*

*

Gọn nhẹ

Cao

Xấu

u4


*

Tốt

Ta có U / d   {X1 , X 2 , X 3} với X1  {u1 , u2 , u4 , u6 }, X 2  {u3}, X 3  {u5} .
Các tập xấp xỉ dưới đối với C là CX1  u1 , u2  , CX 2  u3  , CX 3   .
Do đó, POSC (d)  {u1 , u2 , u3} .
Hàm quyết định suy rộng của các đối tượng trên tập thuộc tính C là
C (u1 )  {Tốt}, C (u2 )  {Tốt}, C (u3 )  {Xấu}, C (u4 )  {Tốt, Tuyệt hảo},

C (u5 )  {Tốt, Tuyệt hảo}, C (u6 )  {Tốt, Tuyệt hảo}.

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


11
Chƣơng 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT
TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
Chương này trình bày hai nội dung chính như sau:
1) Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và
trích lọc luật trong bảng quyết định không đầy đủ, bao gồm: tổng hợp và 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; tổng hợp các kết quả
nghiên cứu về luật quyết định và các độ đo đánh giá hiệu năng; tổng hợp các kết
quả nghiên cứu về so sánh, đánh giá các phương pháp rút gọn thuộc tính. Các kết
quả này được công bố trong các công trình [3, 8].
2) Xây dựng phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao
gồm: xây dựng độ đo khoảng cách; định nghĩa tập rút gọn và độ quan trọng của
thuộc tính dựa trên khoảng cách; xây dựng thuật toán heuristic tìm tập rút gọn; phân
nhóm, đánh giá phương pháp với các phương pháp đã công bố.
2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định không đầy đủ

Kryszkiewicz [5] đưa ra khái niệm đầu tiên 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.
Định nghĩa 2.1. [5] Cho bảng quyết định không đầy đủ IDS  U , A  d  . Nếu
R  A thỏa mãn:

(1)  R  u    A  u  với mọi u U
(2) R'  R , tồn tại u U sao cho  R'  u    A  u 
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.
a) 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, cho đến nay đã có rất nhiều phương pháp
rút gọn thuộc tính dựa trên các độ đo khác nhau đã được công bố [3, 7, 8, 14]. Trong
công trình [7, 8, 14], các tác giả đã tổng kết khá đầy đủ các phương pháp rút gọn
thuộc tính trong bảng quyết định không đầy đủ và các tập rút gọn tương ứng.


13
Bảng 2.1. Các phương pháp rút gọn thuộc tính trong công trình [3, 8, 14]
STT

Phƣơng pháp

Tập rút gọn

1

Phương pháp sử dụng miền

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



8

9

Phương pháp sử dụng hàm ấn

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

định[11].

hàm ấn định

Phương pháp sử dụng ma trận

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

phân biệt[8].

ma trận phân biệt

Phương pháp sử dụng độ đo

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

lượng thông tin[1].

lượng thông tin

Phương pháp sử dụng ma trận


R

RM

RI

RTM

RD

RF

R

b) Phân nhóm các phương pháp rút gọn thuộc tính
Như đã trình bày ở trên, mỗi phương pháp rút gọn thuộc tính đều đưa ra định
nghĩa về tập rút gọn và xây dựng thuật toán heuristic tìm tập rút gọn. Do đó, có thể
nói rằng tập rút gọn là kết quả của phương pháp rút gọn thuộc tính. Vì vậy, việc phân
nhóm các phương pháp rút gọn thuộc tính cũng dựa vào tập rút gọn và được thực hiện
theo nguyên tắc: các phương pháp có tập rút gọn như nhau được phân thành một


14
nhóm. Trong công trình [7, 8, 14], các tác giả đã công bố về mối liên hệ giữa các tập
rút gọn và kết quả phân nhóm các phương pháp rút gọn thuộc tính như sau:
1) Nếu bảng quyết định nhất quán, các tập rút gọn RP , R , R , RM , RI ,
RTM , RD , RF , R là tương đương nhau.

2) Nếu bảng quyết định không nhất quán:



RI  RTM  RD  RF

R  R  RM


R

Hình 2.1. Mối liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ
Từ sơ đồ về mối liên hệ giữa các tập rút gọn, các tác giả trong [7, 8, 14] đã
thực hiện phân nhóm các tập rút gọn và chỉ ra mối liên quan hệ giữa các tập rút gọn
của các nhóm. Cụ thể:
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:
Nhóm 1: Bao gồm tập rút gọn RP .
Nhóm 2: Bao gồm các tập rút gọn R , R , RM .
Nhóm 3: Bao gồm các tập rút gọn RI , RTM , RD , RF
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:
 Nếu R3 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 R2
thuộc nhóm 2 và một tập rút gọn R1 thuộc nhóm 1 sao cho R1  R2  R3 .
 Nếu R4 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 R2
thuộc nhóm 2 và một tập rút gọn R1 thuộc nhóm 1 sao cho R1  R2  R4 .
Dựa vào 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