HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
-------------------------------------

NGUYỄN QUANG HUY

RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT
ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ

LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

HÀ NỘI – 2017


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
-------------------------------------

NGUYỄN QUANG HUY

RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT
ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ KỸ THUẬT

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN LONG GIANG

HÀ NỘI – 2017

i

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Nội dung của
luận văn có tham khảo và sử dụng các tài liệu, thông tin được đăng tải trên các tạp
chí và các trang web theo danh mục tài liệu tham khảo. Tất cả các tài liệu tham khảo
đều có xuất xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỉ luật theo quy
định cho lời cam đoan của mình.

Tác giả

Nguyễn Quang Huy


ii

MỤC LỤC

LỜI CAM ĐOAN ...................................................................................................... I
MỤC LỤC ................................................................................................................ II
DANH MỤC HÌNH VẼ ......................................................................................... IV
DANH MỤC BẢNG ................................................................................................. V
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ......................................... VI
LỜI MỞ ĐẦU ............................................................................................................1
Chương 1: Cơ sở lý thuyết........................................................................................3
1.1

Lý thuyết tập thô ............................................................................................3


1.2

Lý thuyết tập mờ ............................................................................................8

1.3

Lý thuyết tập thô mờ....................................................................................10

1.3.1

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

1.3.2

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

1.4

Rút gọn thuộc tính trong bảng quyết định ...................................................13

1.4.1

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

1.4.2

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

1.4.3


Các phương pháp heuristic rút gọn thuộc tính phổ biến .......................18

Chương 2: Rút gọn thuộc tính trong bảng quyết định sử dụng độ đo khoảng
cách mờ.....................................................................................................................21
2.1

Xây dựng độ đo khoảng cách mờ theo tiếp cận tập thô mờ ........................21

2.1.1

Định nghĩa khoảng cách .......................................................................21

2.1.2

Khoảng cách Jaccard giữa hai tập mờ ..................................................22


iii

2.2

Thuật toán rút gọn thuộc tính sử dụng khoảng cách mờ .............................26

2.2.1

Định nghĩa tập rút gọn dựa trên khoảng cách mờ.................................27

2.2.2


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

2.3

Thuật toán rút gọn thuộc tính sử dụng khoảng cách mờ .............................27

Chương 3: Thử nghiệm và đánh giá kết quả ........................................................32
3.1

Phát biểu bài toán ........................................................................................32

3.2

Mục tiêu thử nghiệm....................................................................................32

3.3

Số liệu, công cụ và môi trường thử nghiệm ................................................32

3.4

Đánh giá kết quả thử nghiệm .......................................................................34

3.4.1

Thử nghiệm 1 ........................................................................................35

3.4.2

Thử nghiệm 2 ........................................................................................37


KẾT LUẬN ..............................................................................................................41
DANH MỤC TÀI LIỆU THAM KHẢO ...............................................................42


iv

DANH MỤC HÌNH VẼ

Hình 1.1. Minh họa tập thô .........................................................................................5
Hình 1.2. Quá trình lựa chọn thuộc tính....................................................................15
Hình 1.3. Lựa chọn thuộc tính theo hướng tiếp cận lọc & đóng gói ........................15
Hình 1.4. Mô hình phương pháp heuristic rút gọn thuộc tính...................................17
Hình 3.1. Giao diện chương trình thử nghiệm ..........................................................36
Hình 3.2. Thời gian thực hiện của thuật toán FA-FPR và FJ_DBAR ......................37
Hình 3.3. Phương pháp k-fold Cross validation (với k=10) .....................................38
Hình 3.4. Độ chính xác phân lớp C4.5 của thuật toán FA-FPR và FJ_DBAR .........40


v

DANH MỤC BẢNG

Bảng 1.1. Bảng thông tin về bệnh cúm .......................................................................6
Bảng 2.1. Bảng quyết định miền giá trị thực ............................................................29
Bảng 3.1. Các bộ số liệu thử nghiệm ........................................................................32
Bảng 3.2. Kết quả thực nghiệm của thuật toán FA-FPR và FJ_DBAR ....................35
Bảng 3.3. Độ chính xác phân lớp C4.5 của FA-FPR và FJ_DBAR .........................39



vi

DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT

Ký hiệu, từ viết tắt

Tiếng Anh

Tiếng Việt

IS  U , A

Information system

Hệ thông tin

DT  U , C  D 

Decision table

Bảng quyết định

Fuzzy decision table

Bảng quyết định mờ

The value of the object u at

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


the attribute a

tại thuộc tính a

Equivalence relation

Quan hệ P  không phân



DT  U , C  D

u a
IND  P 



biệt

 u P

ui R

P

The equivalent class containing

Lớp tương đương chứa

u of P


u của quan hệ P

The fuzzy equivalent class

Lớp tương đường mờ

containing u of R P

chứa u của quan hệ
tương đương mờ R P

PX

P  lower approximation of X

P  xấp xỉ dưới của X

PX

P  upper approximation of X

P  xấp xỉ trên của X

PN P  X 

P  border region of X

P  miền biên của X


POS P  D 

P  positive region of D

P  miền dương của D

SIGP  b 

The importance of attribute b

Độ quan trọng của thuộc

with attribute set P

tính b với tập thuộc
tính P


vii

 A (u)

d FJ  C , C  D 

Dependent function of object

Hàm thuộc của đối

u with fuzzy set


tượng u với tập mờ A

A

Fuzzy Jaccard distance between Khoảng cách Jaccard mờ
two attributes C and C  D
giữa hai tập thuộc tính

C và C  D
FJ_DBAR

Fuzzy Jaccard Distance Based

Rút gọn thuộc tính dựa

Attribute Reduction

trên khoảng cách
Jaccard mờ

FA-FPR

CSDL

Forward Approximation -

Rút gọn thuộc tính dựa

Fuzzy Positive Region


trên miền dương mờ cải

Reduction

tiến

Database

Cơ sở dữ liệu


1

LỜI MỞ ĐẦU
Thời gian gần đây, phương pháp tiếp cận dựa trên tập thô mờ dần được nhiều
nhóm nghiên cứu quan tâm và mở rộng ứng dụng trong bài toán rút gọn thuộc tính,
sinh luật quyết định. Đây là bài toán quan tro ̣ng trong bước tiền xử lý số liệu với
mu ̣c tiêu là nâng cao chấ t lươ ̣ng phân lớp của dữ liê ̣u nhằm tăng tính hiệu quả của
các thuật toán khai phá dữ liệu và học máy. Mục đích của rút gọn thuộc tính trong
bước tiền xử lý dữ liệu là loại bỏ các thuộc tính dư thừa nhằm tăng tính hiệu quả
của các thuật toán trích lọc luật, khai phá tri thức. Một phương pháp truyền thống
dựa trên lý thuyết tập thô do Pawlak [6] đề xuất được đánh giá là công cụ hiệu quả
để giải quyết bài toán rút gọn thuộc tính và trích lọc luật trên bảng quyết định. Tuy
nhiên, phương pháp này phải được thực hiện trên các bảng quyết định với miền giá
trị thuộc tính rời rạc, nghĩa là ta phải thực hiện các phương pháp rời rạc hóa dữ liệu
trước khi áp dụng các phương pháp rút gọn thuộc tính theo tiếp cần tập thô. Do đó,
nó làm giảm thiểu độ chính xác phân lớp của bảng quyết định. Lý thuyết tập thô mờ
do Dubois và các cộng sự [3][4] đề xuất được xem là công cụ hiệu quả để giải quyết
bài toán rút gọn trực tiếp trên bảng quyết định có miền giá trị thuộc tính liên tục. Ưu
điểm dễ thấy của phương pháp đó là không cầ n thông qua bước rời ra ̣c hóa dữ liê ̣u

như các kỹ thuâ ̣t này trong tâ ̣p thô truyề n thố ng nên giảm thiể u đươ ̣c sự mấ t mát
thông tin.
Với mục tiêu nghiên cứu các phương pháp rút gọn thuộc tính nhằm nâng cao
độ chính xác phân lớp của bảng quyết định, học viên chọn đề tài nghiên cứu “Rút
gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô mờ”. Luận văn này trình
bày về các phương pháp rút go ̣n thuô ̣c tiń h của bảng quyết định sử dụng khoảng
cách mờ. Đô ̣ đo khoảng cách giữa hai tâ ̣p mờ và hai phân hoa ̣ch mờ đươ ̣c xây dựng
dựa trên đô ̣ đo khoảng cách Jaccard giữa hai tâ ̣p hơ ̣p rõ hữu ha ̣n phầ n tử, đươ ̣c go ̣i
là khoảng cách Jaccard mờ. Khoảng cách Jaccard mờ sử du ̣ng để rút go ̣n thuô ̣c tin
́ h
đươ ̣c xây dựng dựa trên ma trâ ̣n quan hê ̣ tương tự mờ, quan hê ̣ này đươ ̣c đinh
̣ nghiã
mề m dẻo trên miề n giá tri ̣ của các thuô ̣c tiń h nên ha ̣n chế đươ ̣c sự mấ t mát thông


2

tin. Do không sử du ̣ng các phân hoa ̣ch mờ tin
́ h trực tiế p trên tâ ̣p thuô ̣c tin
́ h nên
phương pháp đề xuấ t tránh đươ ̣c đô ̣ phức ta ̣p tính toán là hàm mũ của số thuô ̣c tính
điề u kiê ̣n. Luâ ̣t quyế t đinh
̣ của phương pháp đươ ̣c rút ra từ tâ ̣p thuô ̣c tính rút go ̣n
của bảng quyế t đinh
̣ nên đơn giản mà vẫn đảm bảo đươ ̣c chấ t lươ ̣ng phân lớp của
dữ liê ̣u.
Mục tiêu của luận văn là nghiên cứu một số phương pháp rút gọn thuộc tính trực
tiếp trên bảng quyết định có miền giá trị thuộc tính liên tục theo tiếp cận tập thô mờ
và thử nghiệm trên các bộ số liệu mẫu từ kho dữ liệu UCI.
Đối tượng nghiên cứu của luận văn là các bảng quyết định có miền giá trị thuộc

tính số liên tục và lý thuyết tập thô mờ.
Phạm vi nghiên cứu là tập trung giải quyết bài toán rút gọn thuộc tính theo tiếp
cận tập thô mờ.
Bố cục luận văn được chia làm 3 chương:
 Chương 1. Cơ sở lý thuyết
Trình bày các lý thuyết cơ bản về tập thô, tập mờ và tập thô mờ.
 Chương 2. Rút gọn thuộc tính trong bảng quyết định sử dụng độ đo
khoảng cách mờ
Sử dụng độ đo khoảng cách mờ theo tiếp cận tập thô mờ, ở đây là khoảng cách
Jaccard mờ, dùng để rút gọn thuộc tính, từ đó xây dựng thuật toán
 Chương 3. Thử nghiệm và đánh giá kết quả
Áp dụng thuật toán xây dựng được ở chương 2 để giải các bài toán thử nghiệm
có đầu vào là bộ dữ liệu từ UCI [11] và đầu ra là tập các thuộc tính sau khi rút
gọn.


3

CHƯƠNG 1: CƠ SỞ LÝ THUYẾT

Chương này trình bày những kiến thức cơ sở về tập thô, tập mờ và tập thô
mờ. Ngoài ra, nội dung chương 1 cũng đề cập tổng quan về các phương pháp rút
gọn thuộc tính trong bảng quyết định tiếp cận lý thuyết tập thô truyền thống, là cơ
sở để phát triển các kỹ thuật này theo tiếp cận tập thô mờ.

1.1 Lý thuyết tập thô
Phần này trình bày tóm tắt một số khái niệm cơ bản về lý thuyết tập thô truyền
thống của Pawlak [6]
Định nghĩa 1.1. Hệ thông tin là một cặp IS  U , A trong đó U là tập hữu hạn các
đối tượng gọi là tập vũ trụ; A là tập hữu hạn, khác rỗng các thuộc tính. Với mọi


u U , a  A , ta ký hiệu giá trị của thuộc tính a tại đối tượng u là 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 . Mỗi tập con các thuộc tính P  A , tồn tại một
quan hệ hai ngôi trên U, ký hiệu là IND  P  , xác định bởi
IND( P)  {(u, v) U U | a  P, a(u )  a(v)}

(1.1)

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

quan hệ tương đương trên U . Nếu (u, v)  IND( P) thì hai đối tượng u và v không phân
biệt được bởi các thuộc tính trong P . Quan hệ tương đương IND  P  xác định một phân
hoạch trên U, ký hiệu là U / IND  P  hay U / P , cụ thể:


4





U / P   a  P : U / IND a

(1.2)

với A  B   X  Y : X  A, Y  B, X  Y   .

Ký hiệu lớp tương đương trong phân hoạch U / P chứa đối tượng u là u  P , khi





đó u  P  v U  u, v   IND  P  .
Lý thuyết tập thô (Rough set theory) do Zdzislaw Pawlak [6] đề xuất vào
những năm 1982 tỏ ra rất hiệu quả trong các bài toán phân lớp, phát hiện luật chứa
dữ liệu mơ hồ không chắc chắn. Trong lý thuyết tập thô, dữ liệu được biểu diễn
thông qua một hệ thông tin IS  U , A với U là tập các đối tượng và A là tập các
thuộc tính. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ
không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát.
Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới (lower
approximation) và xấp xỉ trên (upper approximation) của nó. Xấp xỉ dưới bao gồm
các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có
khả năng thuộc về tập đó. Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập đối tượng
cần quan sát là tập rõ (crip set), ngược lại là tập thô (rough set). Các tập xấp xỉ là
cơ sở để đưa ra các kết luận từ dữ liệu, chính là quá trình khám phá tri thức từ dữ
liệu.
Cho hệ thông tin IS  U , A và tập đối tượng X  U . Với một tập thuộc tính

B  A cho trước, chúng ta có các lớp tương đương của phân hoạch U / B . Trong lý
thuyết tập thô truyền thống, để biểu diễn X thông qua các lớp tương đương của
U/B

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

một số hữu hạn các lớp tương đương của U / B . Có hai cách xấp xỉ tập đối tượng X
thông qua tập thuộc tính B, được gọi là B-xấp xỉ dưới và B-xấp xỉ trên của X, ký

hiệu là lượt là BX và BX , được xác định như sau :









BX  u U u  B  X , BX  u U u  B  X  

(1.3)


5

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ó khả năng thuộc vào X dựa vào 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.

Dễ thấy B-miền biên của X là tập chứa các đối tượng có thể thuộc X, còn Bmiề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  

(1.4)

Mô hình tập thô định nghĩa thông qua xấp xỉ tập hợp được minh họa như hình 1.1

Hình 1.1. Minh họa tập thô

Trong trường hợp BN B  X    thì X được gọi là tập rõ, ngược lại X được
gọi là tập thô.
Xét hệ thông tin IS  U , A với P, Q  A , ta gọi tập POSP (Q) 

X U / Q

 PX 

là P-miền dương của Q. Dễ thấy POSP (Q) là tập các đối tượng trong U được phân lớp
đúng vào các lớp của U / Q sử dụng tập thuộc tính P. Rõ ràng, POSP (Q) là tập tất cả


6

các đối tượng u sao cho với mọi v U mà u  P   v  P  ta đều có u  Q   v  Q  . Nói





một cách hình thức, POSP (Q)  u U u   u  Q .

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

Đau đầu

Thân nhiệt

Cảm cúm

u1

Có

Bình thường

Không

u2

Có

Cao

Có

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

Có


u7

Không

Cao

Có

u8

Không

Rất cao

Không

Ta có: U / {Đau đầu} = u1, u2 , u3  , u4 , u5 , u6 , u7 , u8 
U / {Thân nhiệt} =
U / {Cảm cúm} =

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

4

2

5

7


3

6

8

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

4

5

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

8

2

3

6

7

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

2


3

4

5

8

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 đó:


7

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  ,
POSB ( D) 


X U / D

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

Với các khái niệm của tập xấp xỉ đối với phân hoạch U / B , các tập thô được
chia thành bốn loại như sau:
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 .
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 dạng đặc biệt của 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  (U, C  D) với C  D   .
Xét bảng quyết định DS  (U, C  D) với giả thiết u  U, d  D , d u
đầy đủ giá trị, 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 đủ, trái lại DS được gọi là bảng quyết
định đầy đủ.
Bảng quyết định DS được gọi là nhất quán khi và chỉ khi phụ thuộc hàm
CD nghiệm đúng, nghĩa là với mọi u, v U , u  C   v  C  kéo theo u  D   v  D  .
Ngược lại DS là không nhất quán hay mâu thuẫn. Dễ thấy bảng quyết định DS là


8

nhất quán khi và chỉ khi POSC  D   U . Trong trường hợp bảng không nhất quán thì
POSC  D  chính là tập con cực đại của U sao cho phụ thuộc hàm C  D đúng.


DS được gọi là bảng quyết định miền giá trị số nếu miền giá trị của mọi c  C là các
giá trị số.

1.2 Lý thuyết tập mờ
L.A. Zadeh là người sáng lập ra lý thuyết tập mờ với hàng loạt bài báo mở
đường cho sự phát triển và ứng dụng của lý thuyết này, khởi đầu là bài báo “Fuzzy
Sets” trên Tạp chí Information and Control, 8, 1965 [5]. Ý tưởng nổi bật của khái
niệm tập mờ của Zadeh là từ những khái niệm trừu tượng về ngữ nghĩa của thông
tin mờ, không chắc chắn như: trẻ, nhanh, cao-thấp, xinh đẹp.., ông đã tìm ra cách
biểu diễn nó bằng một khái niệm toán học, được gọi là tập mờ, như là một sự khái
quát trực tiếp của khái niệm tập hợp kinh điển.
Trong lý thuyết tập hợp cổ điển (crip set), quan hệ thành viên của các phần tử
đối với một tập hợp được đánh giá theo kiểu nhị phân một cách rõ ràng, mỗi phần
tử u của tập vũ trụ tham chiếu U là thuộc tập A hoặc không thuộc tập A. Để xem
một phần tử có là thành viên của tập A hay không, ta gán cho phần tử đó giá trị là 1
nếu nó chắc chắn thuộc về A, gán giá trị 0 khi phần tử đó chắc chắn không thuộc về
tập A. Nói một cách khác, ta có thể xây dựng một hàm thành viên (hàm thuộc) để
đánh giá xem một phần tử có thuộc về một tập hợp hay không
1 if u  A

 A (u)  

0 if u  A

u U

(1.5)

Rõ ràng, hàm thuộc  A sẽ xác định tập con cổ điển A trên tập vũ trụ U với


 A chỉ nhận giá trị {0,1}. Ngược lại lý thuyết tập mờ cho phép đánh giá nhiều mức
độ khác nhau về một phần tử có thể thuộc về một tập hợp, hàm thành viên để xác
định mức độ một phần tử u thuộc về một tập A là 0   A (u)  1, u U .


9

Định nghĩa 1.2. Cho U là một vũ trụ tham chiếu, tập con mờ A (hay còn gọi là tập
mờ A) trên U được xác định bởi hàm thuộc  A . Mỗi phần tử u của U, gán cho một
giá trị  A (u) , với 0   A (u)  1 . Nói cách khác, tập con mờ A trên U được xác định
bởi ánh xạ  A : U  [0,1] . Với U  u1, un ,..., un  , tập mờ A trên U được biểu diễn:

A  { A (u1) / u1,  A (u2 ) / u2 ,...,  A (un ) / un}, ui U , i  1..n

(1.6)

Lực lượng của tập mờ A được ký hiệu và xác định

A    A (u )

(1.7)

uU

Ví dụ 1.2. Xét tập hợp U gồm 8 người U  {u1 , u2 ,...u8} , mỗi người tương ứng có
tuổi là 10, 15, 20, 25, 50, 55, 60, 65. Gọi A là tập hợp gồm những người “trẻ”. Khi
đó ta có thể xây dựng hàm thuộc cho tập mờ A

 A :  A (u1 )  0.96;  A (u2 )  0.85;  A (u3 )  0.7;  A (u4 )  0.6;
 A (u5 )  0.3;  A (u6 )  0.2;  A (u7 )  0.1;  A (u8 )  0.069;

Tập mờ A được biểu diễn

A  {0.96 / u1,0.85 / u2 ,0.7 / u3 ,0.6 / u4 ,0.3/ u5 ,0.2 / u6 , 0.1/ u7 , 0.069 / u8}
Dấu “/” biểu diễn một cặp giá trị hàm thuộc tương ứng với một đối tượng cụ
thể trong tập mờ.
Định nghĩa 1.3. Cho U là tập vũ trụ hữu hạn các đối tượng và F (U  U ) là một tập
mờ thực sự trên U U . Quan hệ

R

được gọi là một quan hệ mờ trên U U nếu

R  F (U U ) , trong đó R( x, y ) đo độ liên hệ giữa x U và y  U .
Nếu hai phần tử x, y U có liên hệ với nhau theo quan hệ

R

với cấp độ  thì

ta viết R( x, y)   . Nếu U  {u1, u2 ,...un} thì quan hệ mờ hai ngôi trên U có thể
được biểu diễn bằng ma trận vuông cấp n, ký hiệu M ( R) mà phần tử  ij nằm trên
hàng i và cột j là mức độ liên hệ giữa ui và u j , tức là  ij  R(ui , u j ) .


10

M ( R)  ij ; i, j  1..n
Việc cho một quan hệ hai ngôi

R


(1.8)

trên U tương đương với việc cho một ma

trận M ( R) .
Định nghĩa 1.4. Cho

R

là một quan hệ mờ trên U U . Nếu

R

thỏa mãn các tính

chất:


Phản xạ (Reflexive): R( x, x)  1 x U ;



Đối xứng (Symmetric): R( x, y)  R( y, x) x, y U ;



Bắc cầu-T (T-transitive): R( x, y)  T ( R( x, y), R( y, z )) theo một dạng chuẩn
T với mọi x, y, z U ;


thì

R

được gọi là quan hệ tương đương T (T-similarity). Đặc biệt nếu T=min,

R

được gọi là một quan hệ tương đương mờ.

1.3 Lý thuyết tập thô mờ
Lý thuyết tập thô do Pawlak [6] đề xuất và lý thuyết tập mờ do Zadeh [5] đề
xuất là những lý thuyết độc lập, nhưng có mối quan hệ khăng khít với nhau và bổ
sung cho nhau trong việc biểu diễn và xử lý thông tin không chính xác, không đầy
đủ. Trong lý thuyết tập mờ, tính không chính xác được biểu diễn bởi một hàm
thuộc, trong khi cách tiếp cận tập thô lại dựa trên tính không phân biệt được và các
xấp xỉ. Tuy lý thuyết tập mờ và lý thuyết tập thô có những điểm khác biệt, song
chúng đều là các mô hình biểu diễn tính không chắc chắn, trong đó lý thuyết tập thô
đặc trưng cho tính không rõ ràng và lý thuyết tập mờ đặc trưng cho tính thô sơ, vì
vậy kết hợp hai mô hình này là một lẽ tự nhiên trong tiến trình mở rộng lý thuyết
tập thô. Việc kết hợp cho phép hai lý thuyết này hỗ trợ cho nhau nhằm biểu diễn tốt
hơn tính không chắc chắn. Công trình của Dubois, D., và Prade, H., đề xuất [3][4] là
công trình đầu tiên kết hợp giữa lý thuyết tập mờ với lý thuyết tập thô. Hai khái
niệm cơ bản trong công trình của Dubois, D., và Prade, H., là tập mờ thô (rough
fuzzy set) và tập thô mờ (fuzzy rough set). Theo định nghĩa của Dubois, D., và


11

Prade, H., nếu một tập mờ được tiếp cận bằng một họ các tập rõ trong cùng một

không gian vũ trụ, khi đó cặp xấp xỉ dưới và xấp xỉ trên tương ứng được gọi là tập
mờ thô; nếu một tập rõ (hoặc mờ) được tiếp cận bằng một họ các tập mờ trên cùng
một không gian vũ trụ, khi đó cặp xấp xỉ dưới và xấp xỉ trên tương ứng được gọi là
một tập thô mờ [3][4]. Tập thô mờ đã được ứng dụng trong nhiều bài toán phân tích
dữ liệu, điển hình là bài toán rút gọn thuộc tính và sinh luật quyết định.
Dưới đây là một số khái niệm về tập thô mờ xác định trên bảng quyết định
miền giá trị thực. Các khái niệm này được sử dụng để xây dựng phương pháp rút
gọn thuộc tính trong bảng quyết định miền giá trị thực theo tiếp cận tập thô mờ,
được trình bày ở Chương 2.

1.3.1 Quan hệ tương đương mờ
Bảng quyết định DT  U , C  D  được gọi là bảng quyết định miền giá trị
thực nếu miền giá trị của mọi thuộc tính c  C là các giá trị số thực. Một quan hệ R
xác định trên miền giá trị thuộc tính được gọi là quan hệ tương đương mờ nếu thỏa
mãn các điều kiện sau với mọi x, y, z U
1) Tính phản xạ (reflexive): R  x, x   1 ;
2) Tính đối xứng (symetric): R  x, y   R  y, x  ;





3)Tính bắc cầu max-min (max-min transitive): R  x, z   min R  x, y  , R  y, z  ;
Cho hai quan hệ tương đương mờ R P và RQ xác định trên tập thuộc tính P và Q,
khi đó với mọi x, y U ta có (theo [14])
1) R P  RQ  R P  x, y   RQ  x, y  ;


 R  x, y   min R


(1.9)


 x, y  ;

2) R PQ  R P  RQ  R  x, y   max R P  x, y  , RQ  x, y  ;
3) R PQ  R P  RQ

4) R P  RQ  R P  x, y   RQ  x, y  .

P

 x, y  , R Q

(1.10)
(1.11)
(1.12)


12

1.3.2 Ma trận tương đương mờ
Cho bảng quyết định miền giá trị thực DT  U , C  D  với U   x1 , x2 ,..., xn 
và R P là quan hệ tương đương mờ xác định trên tập thuộc tính P  C . Quan hệ R P

 

được biểu diễn bởi ma trận tương đương mờ M R P   pij  nn như sau:

 p11

p
M ( R P )   21
 ...

 pn1

p12
p22
...
pn 2

p1n 
p2 n 

... 

pnn 

...
...
...
...

(1.13)

với pij  R P  xi , x j  là giá trị của quan hệ giữa hai đối tượng xi và x j trên tập thuộc
tính P , pij  0,1 , xi , x j U ,1  i, j  n .
Theo [13][14][15], ta có công thức sau để xây dựng các ma trận tương đương
mờ trực tiếp từ các thuộc tính của bảng quyết định có miền giá trị thực:


p  xi   p  x j 
1  4*
, if
pij  
pmax  pmin

0, otherwise

p  xi   p  x j 
pmax  pmin

 0.25

(1.14)

với p  xi  là giá trị của thuộc tính p tại đối tượng xi , pmax , pmin tương ứng là giá trị
lớn nhất, nhỏ nhất của thuộc tính p. Dễ thấy, giá trị các phần tử của ma trận tương
đương mờ thuộc đoạn [0,1], nếu pmax  pmin (tử thức và mẫu thức đều bằng 0) thì
định nghĩa pij  1 . Khi đó sử dụng quan hệ tương đương mờ ở công thức (1.14) và
quan hệ tương đương ở công thưc (1.15) là như nhau

pij  1 nếu x j   xi  P và pij  0 nếu x j   xi  P

(1.15)


13

Nói cách khác, lớp tương đương  xi  P có thể xem là lớp đương đương mờ,


 

 

ký hiệu là  xi  P , với hàm thuộc  xi  x j  1 nếu x j   xi  P và  xi  x j  0 nếu
 P
 P

x j   xi  P .
1.4 Rút gọn thuộc tính trong bảng quyết định
1.4.1 Tổng quan về rút gọn thuộc tính
Trong bảng quyết định, không phải mọi thuộc tính đều có vai trò như nhau
trong tác vụ phân lớp tập đối tượng. Các thuộc tính điều kiện trong bảng quyết định
có thể chia thành thuộc tính lõi và thuộc tính dư thừa. Trong khi thuộc tính lõi là
thuộc tính cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu, thì
thuộc tính dư thừa là thuộc tính mà việc loại bỏ nó không ảnh hướng đến việc phân
lớp dữ liệu. Để xác định được tập rõ và loại bỏ tập thuộc tính dư thừa, chúng ta cần
phải thực hiện rút gọn thuộc tính. Rút gọn thuộc tính là bài toán quan tro ̣ng trong
bước tiền xử lý số liệu với mục tiêu là giảm số chiều dữ liệu (số thuộc tính) bằng
cách loại bỏ dữ liệu dư thừa nhằm nâng cao hiệu quả của các thuật toán khai phá dữ
liệu và học máy. Rút gọn thuộc tính của bảng quyết định là quá trình lựa chọn 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, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính ảnh hưởng trực
tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất
lượng, tính dễ hiểu của các kết quả thu được.
Các kỹ thuật rút gọn thuộc tính được phân thành hai loại: Lựa chọn thuộc
tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation). Lựa
chọn thuộc tính là chọn một tập con tốt nhất (theo một nghĩa nào đó) từ tập dữ liệu
ban đầu. Biến đổi thuộc tính thực hiện việc biến đổi các thuộc tính ban đầu thành
thành một tập các thuộc tính mới với số lượng ít hơn sao cho bảo tồn được thông tin

nhiều nhất.


14

Các công trình nghiên cứu về rút gọn thuộc tính thường tập trung vào nghiên
cứu các kỹ thuật lựa chọn thuộc tính. Lựa chọn thuộc tính là quá trình lựa chọn một
tập con gồm P thuộc tính từ tập gồm A thuộc tính (P ≤ A) sao cho không gian thuộc
tính được thu gọn lại một cách tối ưu theo một tiêu chuẩn nhất định. Việc tìm ra
một tập con thuộc tính tốt nhất thường khó thực hiện; nhiều bài toán liên quan đến
vấn đề này là những bài toán NP-khó. Nhìn chung, một thuật toán lựa chọn thuộc
tính thường bao gồm bốn khâu cơ bản:


Tạo lập tập con



Đánh giá tập con



Kiểm tra điều kiện dừng



Kiểm chứng kết quả
Tạo lập tập con thuộc tính là quá trình tìm kiếm liên tiếp nhằm tạo ra các tập

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

A

số tất cả các tập con từ A thuộc tính sẽ là 2 . Như vậy, rất khó khăn khi tìm tập con
tối ưu từ tất cả các tập con này. Phương pháp chung để tìm tập con thuộc tính tối ưu
là lần lượt tạo ra các tập con để so sánh. Mỗi tập con sinh ra bởi một thủ tục sẽ được
đánh giá theo một tiêu chuẩn nhất định và đem so sánh với tập con tốt nhất trước
đó. Nếu tập con này tốt hơn, nó sẽ thay thế tập cũ. Quá trình tìm kiếm tập con thuộc
tính tối ưu sẽ dừng khi một trong bốn điều kiện sau xảy ra:


Đã thu được số thuộc tính quy định.



Số bước lặp quy định cho quá trình lựa chọn đã hết.



Việc thêm vào hay loại bớt một thuộc tính nào đó không cho một tập con trở

nên tốt hơn.


Đã thu được tập con tối ưu theo tiêu chuẩn đánh giá. Tập con tốt nhất cuối

cùng phải được kiểm chứng thông qua việc tiến hành các phép kiểm định, so sánh
các kết quả khai phá với tập thuộc tính “tốt nhất” này và tập thuộc tính ban đầu trên
các tập dữ liệu khác nhau. Quá trình lựa chọn thuộc tính được biểu diễn như sau:



15

Hình 1.2. Quá trình lựa chọn thuộc tính

Hiện nay có hai cách tiếp cận chính đối với bài toán lựa chọn thuộc tính: Lọc
(filter) và đóng gói (wrapper). Cách tiếp cận kiểu lọc thực hiện việc lựa chọn thuộc
tính độc lập với các thuật toán khai phá sử dụng sau này. Các thuộc tính được chọn
chỉ dựa trên độ quan trọng của chúng trong việc mô tả dữ liệu. Ngược lại với cách
tiếp cận lọc, lựa chọn thuộc tính kiểu đóng gói tiến hành việc lựa chọn bằng cách áp
dụng ngay kỹ thuật khai phá cụ thể với tập rút gọn vừa thu được, độ chính xác của
kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Các hướng tiếp
cận lọc và đóng gói của bài toán lựa chọn thuộc tính được biểu diễn như hình 1.3.

Hình 1.3. Lựa chọn thuộc tính theo hướng tiếp cận lọc & đóng gói

1.4.2 Rút gọn thuộc tính theo tiếp cận tập thô


16

Lý thuyết tập thô được xem là công cụ hiệu quả để giải quyết bài toán rút
gọn thuộc tính và được cộng đồng nghiên cứu về tập thô thực hiện lâu nay. Mục
tiêu của rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô là sử dụng
công cụ tập thô để 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.
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ô đều thực
hiện trên các bảng quyết định có miền giá trị rời rạc, nghĩa là các bảng quyết định
thu được sau khi thực hiện bước rời rạc hóa dữ liệu. Đối với một bảng quyết định có
thể có nhiều tập rút gọn khác nhau. Tuy nhiên, trong các bài toán thực tế không đòi

hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một tập rút gọn tốt nhất theo một
tiêu chuẩn đánh giá nào đó đặt ra. Do đó, các phương pháp rút gọn thuộc tính sử
dụng cận tập thô đều thực hiện theo hướng tiếp cận heuristic. Theo lý thuyết tập thô,
Pawlak đưa ra khái niệm tập rút gọn dựa trên miền dương và xây dựng thuật toán
heuristic tìm một tập rút gọn tốt nhất của bảng quyết định dựa trên tiêu chí đánh giá
là độ quan trọng của thuộc tính. Phương pháp heuristic tìm một tập rút gọn tốt nhất
bao gồm các bước:
 Đưa ra khái niệm tập rút gọn của phương pháp dựa trên một độ đo được
chọn. Các phương pháp khác nhau có độ đo khác nhau, điển hình là các độ đo trong
tính toán hạt (granunal computing), độ đo entropy, độ đo khoảng cách, sử dụng ma
trận…
 Đưa ra khái niệm độ quan trọng của thuộc tính đặc trưng cho chất lượng
phân lớp của thuộc tính dựa trên độ đo được chọn.
 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á độ quan trọng của thuộc tính (chất lượ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.
Phương pháp rút gọn thuộc tính heuristic được mô hình hóa như hình 1.4: