i

ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

VŨ VĂN TIỆP

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN GIA TĂNG CHO VIỆC RÚT
GỌN CÁC THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG
ĐẦY ĐỦ

LUẬN VĂN THẠC SĨ KHOA HỌC
KHOA HỌC MÁY TÍNH
HƢỚNG DẪN: GS.TS VŨ ĐỨC THI

THÁI NGUYÊN 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

ii

LỜI CẢM ƠN

Em xin chân thành cảm ơn và biết ơn sâu sắc đến GS.TS Vũ Đức Thi,
Viện Công nghệ thông tin – Đại học Quốc gia Hà Nội. Người đã tận tình
hướng dẫn và giúp đỡ em hoàn thành luận văn này.
Em xin chân thành cảm ơn các Thầy ở Viện Công nghệ thông tin đã
dạy bảo, giúp đỡ và truyền đạt kiến thức cho em trong suốt khóa học và quá
trình em làm luận văn.
Em xin chân thành cảm ơn các Thầy, các Cô ở trường Đại học Công


2.2. Các thuật toán tiếp cận gia tăng tìm tập rút gọn khi bổ sung, loại bỏ tập thuộc tính
25
2.2.1. Thuật toán tìm tập rút gọn khi bổ sung tập thuộc tính .....................................25
2.2.2. Thuật toán tìm tập rút gọn khi loại bỏ tập thuộc tính ......................................29

2.3. Kết luận chương 2 ...................................................... Error! Bookmark not defined.
Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .................................................. 34
3.1. Bài toán .......................................................................................................................... 34
3.2. Phân tích, lựa chọn công cụ ......................................................................................... 34

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

v
3.2.1. Thuật toán tìm tập rút gọn sử

dụng hàm phân biệt mở rộng .............................................

3.2.2. Các thuật toán tìm tập rút gọn khi bổ sung và loại bỏ tập thuộc tính ..............37

3.3. Đánh giá kết quả thử nghiệm ....................................................................................... 39
3.3.1. Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng hàm phân biệt mở rộng.
39
3.3.2. Kết quả thử nghiệm thuật toán tìm tập rút gọn khi bổ sung tập thuộc tính .....41
3.3.3. Kết quả thử nghiệm thuật toán tìm tập rút gọn khi loại bỏ tập thuộc tính .......45

KẾT LUẬN.........................................................................................................................................................49
Tài liệu tham khảo ..............................................................................................................................................50
Phụ lục ...................................................................................................................................................................52

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

Quan hệ dung sai

Tolerance Relation

Xấp xỉ dưới

Lower Approximation

Xấp xỉ trên

Upper Approximation


Bảng 3.5 Kết quả thực hiện Thuật toán 2.2 tìm tập rút gọn khi bổ sung 40% số thuộc tính
vào. ............................................................................................................................... 43
Bảng 3.6. Kết quả thực hiện Thuật toán 2.1 trên bộ số liệu ban đầu.................................. 45
Bảng 3.7 Kết quả thực hiện Thuật toán 2.1 sau khi loại ngẫu nhiên 40% số thuộc tính
điều kiện. ...................................................................................................................... 46
Bảng 3.8 Kết quả thực hiện Thuật toán 2.3 tìm tập rút gọn khi loại bỏ 40% số thuộc tính
điều kiện. ...................................................................................................................... 47

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

1

MỞ ĐẦU
Lý thuyết tập thô - do Zdzislaw Pawlak [10] đề 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.
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

Nghiên cứu hướng tiếp cận gia tăng rút gọn thuộc tính trong bảng

quyết định không đầy đủ sử dụng hàm phân biệt mở rộng trong trường hợp bổ
sung, loại bỏ tập thuộc tính.
2) Cài đặt thuật toán rút gọn thuộc tính trong bảng quyết định không đầy
đủ sử dụng hàm phân biệt mở rộng và các thuật toán gia tăng trong trường
hợp bổ sung, loại bỏ tập thuộc tính. Thử nghiệm và đánh giá kết quả trên các
bộ số liệ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 không đầy đủ
khi bổ sung, loại bỏ tập thuộc tính.
Phạm vi nghiên cứu của luận văn tập trung vào bài toán rút gọn thuộc
tính ở bước tiền xử lý số liệu trong quá trình khai phá dữ liệu.
Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên
cứu thực nghiệm. Về nghiên cứu lý thuyết: tổng hợp và nắm bắt các kết quả
nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận văn thực hiện cài
đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho
dữ liệu UCI [13], so sánh và đánh giá nghiên cứu thực nghiệm với nghiên
cứu lý thuyết.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

3

Bố cục của luận văn gồm phần mở đầu và hai chương nội dung, phần
kết luận và danh mục các tài liệu tham khảo.
Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô của Pawlak
[10] và mô hình tập thô mở rộng dựa trên quan hệ dung sai, gọi tắt là mô hình
tập thô dung sai [5]. Trình bày tổng quan các kết quả nghiên cứu về các

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.
Hệ thông tin đầy đủ và mô hình tập thô truyền thống

1.1.

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

V

a

với Va là tập giá trị của thuộc tính a A ; f : U A

Va là hàm thông

a A

tin, a A, u U f u, a

Va .

a v .

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

quan hệ tương đương trên U. Nếu u, v
Số hóa bởi Trung tâm Học liệu - ĐHTN

IND P thì hai đối tượng u và v không

/>

5

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 . Ký hiệu lớp tương đương
trong
u

P

phân

tượng

u

là

u


BX

u U u

X , BX

B

u U u

X

B

.

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
BNB 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ể


Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

6

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

ta

v B

POS B ( D)

đều

u U u

u

B

có

u D

v D



u2

Có

Cao

Có

u3

Có

Rất cao

Có

u4

Không

Bình thường

Không

u5

Không

Cao


U / {Thân nhiệt} =
U / {Cảm cúm} =

u1 , u4 , u2 , u5 , u7 , u3 , u6 , u8

u1 , u4 , u5 , u8 , u2 , u3 , u6 , u7

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

u1 , u2 , u3 , u4 , u5 , u8 , u6 , u7

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

tập hợp BN B X
U/D

X1

u2 , u3 , u5 , u6 , u7 , u8 . Như vậy, B-miền biên của X là


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 đủ
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 đầy đủ, gọi tắt 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

U,C

D, V , f

với C D

.


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.
Với bảng quyết định DS

U,C

D,V , f . Thuộc tính c C được gọi là

không cần thiết (dispensable) trong DS nếu POSC D

POS(C

c )

D ; 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 và được ký hiệu là PCORE C . Khi đó, thuộc
tính cần thiết chính là thuộc tính lõi. Như vậy, thuộc tính không cần thiết là
thuộc tính dư thừa hoặc thuộc tính rút gọn.
Nếu tập thuộc tính R C thỏa mãn:
1) POS R ( D) POSC ( D)
2) r R, POS R

r

( D)

POSC ( D)


thiếu là „*‟ và hệ thông tin không đầy đủ là IIS
Xét hệ thông tin không đầy đủ IIS

U , A,V , f .

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

'*' .

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

u U SP u

PX

u U SP u

X
X

u

X SP u

X

 SP 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
BNP X

PX

PX , và P-miền ngoài của X là tập U

Số hóa bởi Trung tâm Học liệu - ĐHTN

PX .
/>

10


d ,V , f . Với B

U,C

f d v v S B (u ) gọi là hàm quyết định suy rộng, nếu |

(u )

C

C,

(u ) | 1

với mọi u U thì IDS là nhất quán, trái lại IDS là không nhất quán [5].
Tương tự trong bảng quyết định đầy đủ, với B C , miền dương của d đối
với B, ký hiệu là POS B ( d ) , được định nghĩa POS B ( d )

{BX | X

U / {d }} ,

khi đó IDS là nhất quán khi và chỉ khi POSB ( d ) U .
Ví dụ 1.2. Xét bảng quyết định không đầy đủ IDS

U,C

d ,V , f



u2

Thấp

*

Đầy đủ

Thấp

Tốt

u3

*

*

Gọn nhẹ

Cao

Xấu

u4

Cao

*


*

Đầy đủ

Cao

Tuyệt
hảo

u6

Thấp

Cao

Đầy đủ

*

Tốt

Ta có U / d

{ X 1 , X 2 , X 3} với X 1 {u1 , u2 , u4 , u6 }, X 2

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

{u3 }, X 3


(u6 )

C

(u3 )

{Xấu},

C

(u4 )

{Tốt, Tuyệt hảo},

{Tốt, Tuyệt hảo}.

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

Rút gọn thuộc tính trong bảng quyết định không đầy đủ

1.3.1. Tổng quan về các phƣơng pháp rút gọn thuộc tính
Rút gọn thuộc tính theo tiếp cận tập thô truyền thống của Pawlak [10] là
chủ đề nghiên cứu sôi động trong nhiều năm qua [1]. Tuy nhiên trong các bài
toán 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,
còn gọi là các hệ thông tin không đầy đủ. Ví dụ, trong các kho dữ liệu thuộc lĩnh
vực y khoa, các bác sỹ thường không thu thập đủ các triệu trứng của các bệnh
nhân để chuẩn đoán bệnh.... Trên hệ thông tin không đầy đủ, các nhà nghiên
cứu quan tâm đến việc xây dựng các mô hình hiệu quả 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. Một trong những giải pháp hiệu quả

của bảng quyết định DS nếu R bảo toàn “khả năng phân lớp” của DS, nghĩa là
việc phân lớp đối tượng dựa trên tập thuộc tính R tương đương với tập thuộc
tính A. Khả năng phân lớp được “lượng hóa” bằng độ chắc chắn của tập luật
quyết định sẽ trình bày ở phần sau. Mỗi phương pháp rút gọn thuộc tính đều đưa
ra một độ đo nhằm lượng hóa khả năng phân lớp và đưa ra định nghĩa tập rút
gọn dựa trên độ đo được chọn.
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
R

U, A

d . Nếu

A thỏa mãn:

(1)

R

(2) R'

u

A

u với mọi u U


1

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

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

dương.

miền dương

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

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

quyết định suy rộng.

hàm quyết định suy

2

Ký hiệu tập
rút gọn
RP

R

rộng
3

4


lượng thông tin

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

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

dung sai.

ma trận dung sai

Phương pháp sử dụng metric

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

[7]

metric

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

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

phân bố.

hàm phân bố

Số hóa bởi Trung tâm Học liệu - ĐHTN

R

- Tập rút gọn dựa trên hàm quyết định suy rộng ( R ) tương đương với tập
rút gọn dựa trên ma trận phân biệt ( RM ).
- Tập rút gọn dựa trên lượng thông tin ( RI ) tương đương với tập rút gọn
dựa trên ma trận dung sai ( RTM ).
- Tập rút gọn dựa trên metric ( RD ) tương đương với tập rút gọn dựa trên
độ đo lượng thông tin ( RI ) [7].
- Tập rút gọn dựa trên miền dương ( RP ) là tập con của tập rút gọn dựa
trên hàm quyết định suy rộng ( R ), nghĩa là: nếu R là một tập rút gọn dựa
trên hàm quyết định suy rộng thì tồn tại RP

R với RP là một tập rút gọn

dựa trên miền dương.
Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

15

- Tập rút gọn dựa trên hàm quyết định suy rộng ( R ) là tập con của tập
rút gọn dựa trên lượng thông tin ( RI ), nghĩa là: nếu RI là một tập rút gọn dựa
trên lượng thông tin thì tồn tại R

RI với R là một 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 hàm quyết định suy rộng ( R ) là tập con của tập
rút gọn dựa trên hàm phân bố ( R ), nghĩa là: nếu R là một tập rút gọn phân
bố thì tồn tại R


/>

16

Nhóm 3: Bao gồm các tập rút gọn RI , RTM , RD
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.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

tốt nhất sử dụng hàm phân biệt mở rộng; phân nhóm phương pháp sử dụng
hàm phân biệt mở rộng.
2) Dựa vào hàm phân biệt mở rộng, chương này trình bày hai thuật toán
theo hướng tiếp cận gia tăng tìm tập rút gọn của bảng quyết định không đầy
đủ.
2.1.

Rút gọn thuộc tính sử dụng hàm phân biệt mở rộng
Trong lý thuyết tập thô truyền thống, Skowron đã đư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 hướng tiếp cận này, luận văn trình khái niệm ma trận phân biệt
mở rộng (generalized discernibility function) và hàm phân biệt mở rộng
(generalized discernibility matrix) để tìm tập rút gọn của bảng quyết định
không đầy đủ. Phương pháp heuristic cũng bao gồm các bước: xây dựng ma
trận phân biệt và hàm phân biệt mở rộng, định nghĩa tập rút gọn và độ quan
trọng của thuộc tính sử dụng hàm phân biệt mở rộng, 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 phân biệt mở rộng.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>