ðẠI HỌC THÁI NGUYÊN
TRƯỜNG ðẠI HỌC CNTT VÀ TRUYỀN THÔNG
HOÀNG THỊ NGỌC MAI MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH
TRONG BẢNG QUYẾT ðỊNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN



LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ ðức Thi

Thái Nguyên - Năm 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC

LỜI CẢM ƠN I
LỜI CAM ðOAN II
DANH MỤC CÁC THUẬT NGỮ III
BẢNG CÁC KÝ HIỆU IV
DANH SÁCH BẢNG VI
LỜI MỞ ðẦU 1
Chương 1. KHÁI QUÁT VỀ TẬP THÔ VÀ RÚT GỌN THUỘC TÍNH 5

2.3.4. Thuật toán tìm tập rút gọn sử dụng metric 54
2.3.5. Thuật toán tìm tập rút gọn theo ngưỡng chắc chắn của bảng quyết ñịnh 59
2.4. Kết luận Chương 2 61
Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM 62
3.1. Bài toán 62
3.2. Phương pháp 62
3.3. Xây dựng chương trình thử nghiệm 63
3.4. Kết quả thử nghiệm 64
3.5. Kết luận chương 3 65
KẾT LUẬN 66
TÀI LIỆU THAM KHẢO 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
I LỜI CẢM ƠN
Tôi xin chân thành cảm ơn ñến:
- Trường ðại học Công nghệ thông tin và Truyền thông, ðại học Thái
Nguyên
- Viện Công nghệ Thông tin và các thầy cô giáo ñã trực tiếp giảng dạy,
hướng dẫn tôi trong quá trình học tập và ñịnh hướng quan trọng trong việc
hình thành ý tưởng nghiên cứu.
Tôi xin chân thành cảm ơn Chi bộ, BGH, BCH Công ñoàn, Tổ Khoa
học tự nhiên và cán bộ giáo viên, nhân viên Trường THPT Bình ðộ ñã ñộng
viên, giúp ñỡ, tạo ñiều kiện thuận lợi cho tôi trong quá trình học tập và nghiên
cứu.
ðặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc ñến GS.TS Vũ ðức Thi,
người thầy ñã trực tiếp hướng dẫn và giúp ñỡ tôi hoàn thành luận văn tốt


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
III DANH MỤC CÁC THUẬT NGỮ

Tập thô Rough Set
Hệ thông tin Information System
Hệ thông tin ñầy ñủ Complete Information System
Bảng quyết ñịnh Decision Table
Bảng quyết ñịnh ñầy ñủ Comple Decision Table
Bảng quyết ñịnh không nhất quán Inconsistent Decision Table
Quan hệ không phân biệt ñược Indiscernibility Relation
Rút gọn thuộc tính Attribute Reduction
Tập rút gọn Reduct
Tập lõi Core
Shannon entropy Entropy
Liang entropy Entropy mới của Jiye Liang trong [28]

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
IV BẢNG CÁC KÝ HIỆU

(
)
, , ,
IS U A V f

của quan hệ
(
)
IND B

(
)
B
S u

Lớp dung sai của ñối tượng
u
trên quan hệ
(
)
SIM B

/
U B

Phân hoạch
U
sinh bởi tập thuộc tính
B

BX

B
- xấp xỉ dưới của
X

(
)
HRED C

Tập tất cả các rút gọn dựa trên Shannon entropy
(
)
SRED C

Tập tất cả các rút gọn của phương pháp ma trận phân biệt

(
)
ERED C

Tập tất cả các rút gọn dựa trên Liang entropy
(
)
NERED C

Tập tất cả các rút gọn dựa trên Liang entropy với phân
hoạch cải tiến.
(
)
MRED C

Tập tất cả các rút gọn dựa trên metric
(
)
KRED C

Tập lõi dựa trên Liang entropy.
(
)
M
CORE C

Tập lõi dựa trên metric
(
)
K
CORE C

Tập lõi dựa trên ñộ ño lượng tri thức khác nhau.
(
)
H P

Shannon entropy của tập thuộc tính
P

(
)
\
H Q P

Shannon entropy có ñiều kiện của
Q
khi ñã biết
P


,
d K P K Q

Metric giữa hai tri thức
(
)
K P
và
(
)
K Q
trên hệ thông tin
ñầy ñủ sử dụng khoảng cách Jaccard giữa hai tập hợp.
(
)
(
)
(
)
,
DQP K P K Q

Lượng tri thức khác nhau giữa
(
)
K P
và
(
)
K Q

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
mơ hồ, 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 rời rạc hóa dữ liệu, rút gọn thuộc tính, trích lọc các tri thức tiềm ẩn
trong dữ liệu dưới dạng các mẫu, các luật quyết ñịnh.
Trong lý thuyết tập thô, dữ liệu ñược biểu diễn thông qua một hệ thống
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.
Mỗi tập thuộc tính
B A
⊆
xác ñịnh một quan hệ tương ñương
(
)
IND B
trên
U

còn gọi là quan hệ không phân biệt ñược.
Rút gọn thuộc tính là bài toán quan trọng nhất trong lý thuyết tập thô. Mục

D
.
Nói cách khác,
(
)
,
DS U C D
= ∪
với
C D
∩ = ∅
. Bảng quyết ñịnh là nhất quán
khi phụ thuộc hàm
C D
→

là ñúng. ðối với bảng quyết ñịnh nhất quán, tập
con các thuộc tính ñiều kiện
R C
⊆
ñược gọi là một tập rút gọn của bảng quyết
ñịnh nếu
R
là tập tối thiểu thỏa mãn phụ thuộc hàm
R D
→
. Nếu xem bảng
quyết ñịnh là quan hệ
r
trên tập thuộc tính

Luận văn ñã có hai ñóng góp chính sau:
Thứ nhất là nghiên cứu mối liên hệ giữa các tập rút gọn của các phương
pháp rút gọn thuộc tính, tìm hiểu các ñộ ño cải tiến ñánh giá hiệu năng bảng
quyết ñịnh và nghiên cứu sự thay ñổi của các ñộ ño này khi thực hiện các
phương pháp rút gọn thuộc tính.
Thứ hai là xây dựng toán heuristic tìm tập rút gọn của bảng quyết ñịnh
ñầy ñủ sử dụng Liang entropy và metric.
4. Bố cục luận văn
Luận văn ñược viết trong ba chương, gồm 66 trang
Chương một khái quát về tập thô và rút gọn thuộc tính.
Chương hai trình bày kết quả nghiên cứu về ba vấn ñề. Thứ nhất nghiên
cứu mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn thuộc tính,
bao gồm phương pháp dựa trên miền dương, phương pháp sử dụng các ñộ ño
không chắc chắn (entropy thông tin, hạt tri thức) và phương pháp sử dụng ma
trận phân biệt. Thứ hai là tìm hiểu các ñộ ño cải tiến ñánh gia hiệu năng của
bảng quyết ñịnh và nghiên cứu sự thay ñổi của các ñộ ño này khi thực hiện
các phương pháp rút gọn thuộc tính. Thứ ba là ñề xây dựng chương trình thử
nghiệm thuật toán heuristic (Thuật toán 2.2, Thuật toán 2.4 và Thuật toán
2.5). Thuật toán 2.5 tìm tập rút gọn Pawlak sử dụng Liang entropy, Thuật toán
2.4 tìm tập rút gọn trong bảng quyết ñịnh sử dụng metric, Thuật toán 2.5 là
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4 cải tiến của Thuật toán 2.4 tìm tập rút gọn theo tham số là ngưỡng chắc chắn
của bảng quyết ñịnh. Các thuật toán trên ñều có ñộ phức tạp tính toán trong
thời gian ña thức và hiệu quả hơn các thuật toán khác ñã công bố.
Chương 3 Chương trình thử nghiệm xây dựng bảng quyết ñịnh dựa trên
Thuật toán 2.4 tìm tập rút gọn sử dụng metric ñã trình bày trong Chương 2.
Kết quả thử nghiệm của chương trình thực hiện trên công cụ mã nguồn mở

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;
a
a A
V V
∈
=
∏
với
a
V
là tập giá trị của thuộc tính
a A
∈
;
f
là hàm thông tin,
với mọi
a A
∈
và
u U
∈
hàm
f
cho giá trị
(

, , ,
k
B b b b A
= ⊆
là một tập con các thuộc tính
thì ta sẽ ký hiệu bộ các giá trị
(
)
i
u b
bởi
(
)
u B
. Như vậy, nếu
u
và
v
là hai ñối
tượng, thì ta sẽ viết
(
)
(
)
u B v B
=
nếu
(
)
(

(
)
(
)
{
}
, | , , ,
IND P u v U U a P f u a f v a
= ∈ × ∀ ∈ =
.
(
)
IND P
ñược gọi là quan hệ
B
- 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
(
)
(
)
,
v u IND B
∈
thì hai ñối tượng
u
và
v

P
u
, khi ñó,
[
]
(
)
(
)
{
}
| ,
P
u v U u v IND P
= ∈ ∈
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6 ðịnh nghĩa 1.2. [11, 12] Cho hệ thống thông tin
(
)
, , ,
IS U A V f
=
với
,
P Q A
⊆

3)
/ /
U P U Q
<
khi và chỉ khi
[
]
[
]
,
P Q
u U u u
∀ ∈ ⊆
và tồn tại
v
sao cho
[
]
[
]
P Q
v v
⊆

Tính chất 1.1. [11, 12] Xét hệ thống thông tin
(
)
, , ,
S U A V f
=

= ∩
.

Ví dụ 1.1. Xét hệ thông tin
(
)
, , ,
IS U A V f
=
biểu diễn các triệu chứng cúm của
bệnh nhân cho ở Bảng 1.1 với
(
)
1 2 3 4 5 6 7 8
, , , , , , ,
U u u u u u u u u
=
,
(
)
1 2 3
, ,
C a a a
=
với
1
a

(ðau ñầu),
2


Không Rất cao Có
7
u

Không Cao Có
8
u

Không Rất cao Không
Bảng 1.1. Bảng thông tin về bệnh cúm

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7 Ta có
{
}
{
}
{
}
{
}
1 1 2 3 4 5 6 7 8
/ , , , , , , ,
U a u u u u u u u u
=
,


{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
1 2 1 2 3 4 5 7 6 8
/ , , , , , , ,
U a a u u u u u u u u
=

Như vậy, các bệnh nhân
2 3
,
u u
không phân biệt nhau về ñau ñầu
(
)
1

, thế thì một tập ñối tượng
X
có thể biểu diễn thông qua các lớp tương
ñương này như thế nào?
Trong lý thuyết tập thô, ñể 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 sẵn có
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 thuộc tính
B
, ñược gọi là
B
-xấp xỉ dưới và
B
-

X
, còn
tập
BX
bao gồm các phần tử của
U
có khả năng ñược phân loại 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
(
)
B
BN X BX BX
= −
:
B
- miền biên của
X
.
U BX
−
:
B
-miền ngoài của
X

Dễ thấy

{
}
/ |
BX Y U B Y X
= ∈ ∩ = ∅
U
.
Trong trường hợp
(
)
B
BN X
= ∅
,
X
ñược gọi là tập rõ, ngược lại
X
ñược
gọi là tập thô.
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
(
)

u D v D
=
. Nói cách khác,
(
)
[
]
[
]
{
}
|
B
B D
POS D u U u u
= ∈ ⊆
.
Ví dụ 1.2. Xét hệ thông tin
(
)
, , ,
IS U A V f
=
ở Ví dụ 1.1. Với
{
}
1 2
,
B a a
=

,
BX u u
=
và
{
}
2 3 5 6 7 8
, , , , ,
BX u u u u u u
=
. Như vậy,
B
-miền biên của
X
là tập
hợp
{
}
5 6 7 8
( ) , , ,
B
BN X u u u u
=
.
Nếu ñặt
{
}
3
D a
=

∈
= =
U
.
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
≠

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, trong ñó tập các
thuộc tính A bao gồm hai tập con rời nhau: tập các thuộc tính ñiều kiện
C
và
tập các thuộc tính quyết ñịnh
D
. Như vậy, bảng quyết ñịnh là một hệ thống
thông tin
( , , , )
DS U C D V f
= ∪
trong ñó
C D
∩ = ∅
.
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
=

liệu.
- Thuộc tính cơ bản là thuộc tính nằm trong một tập rút gọn nào ñó.
Ta sẽ ñưa ra các ñịnh nghĩa chính xác như sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10 ðịnh nghĩa 1.3. Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
, thuộc tính
a C
∈

ñược gọi là cần thiết nếu
{ }
( )
( ) OS ( )
C
C a
POS D P D
−
≠
. 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à kí hiệu là
( )
P

R
là một rút gọn của
C

Tập rút gọn ñịnh nghĩa như trên gọi là một tập rút gọn dựa trên miền
dương theo Pawlak. ðịnh nghĩa 1.4 cho thấy,
R
là tập rút gọn nếu nó là tập
tối thiểu thỏa mãn
( ) ( )
R C
POS D POS D
=
. Có thể tồn tại nhiều tập rút gọn của
C
.
Ta kí hiệu
(
)
P
PRED C
là tập tất cả các rút gọn theo Pawlak của
C
. Khi ñó,
( )
( )
P
R PRED C
CORE C R
∈

a C
∈
. Ta nói
rằng
a
là thuộc tính dư thừa của
C
nếu
( )R PRED C
a C R
∈
∈ −
U
.
1.5. Ma trận phân biệt và hàm phân biệt
Người ñầu tiên xây dựng phương pháp rút gọn thuộc tính trong bảng
quyết ñịnh là Skowron. Ông ñã ñưa ra khái niệm ma trận phân biệt và hàm
phân biệt, từ ñó ñưa ra phương pháp tìm tập rút gọn sử dụng hàm phân biệt.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11 ðịnh nghĩa 1.7. Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
, ma trận phân biệt
của DS là ma trận
(
)


∅ =



ðịnh nghĩa 1.8. [6] Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
,
(
)
ij
M m
=
là ma
trận phân biệt của
DS
và tập thuộc tính
B C
⊆
. Nếu
b B
∈
thỏa mãn
{
}
(
)
ij

,
(
)
ij
M m
=

là ma trận phân biệt của
DS
. Nếu
R C
⊆
thỏa mãn
1)
ij
B m
∩ ≠ ∅
với mọi
ij
m
≠ ∅

2) Với mọi
{
}
,
b B B b
∈ −
không thỏa mãn (1)
thì
1.6.1. Entropy trong hệ thông tin và các tính chất.
Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
và
,
P Q C
⊆
. Giả sử
{
}
{
}
1 2 1 2
/ , , , , / , , ,
p q
U P X X X U Q Y Y Y
= =
,
{
}
1 2
/ , , ,
m
U C C C C
=
và

X
p X X
U
=
biểu diễn lực lượng của tập
X
và giả thiết
2
0.log 0 0
=

Nếu
/
U P U
=
thì
(
)
H P
ñạt giá trị nhỏ nhất là 0, còn nếu
{
}
i i
X u
=
với
,
i
u U
∈

D
khi ñã biết
C
ñược
ñịnh nghĩa
( ) ( )
( ) ( )
2
1 1
| | log |
m n
i j i j i
i j
H D C p C p D C p D C
= =
= −
∑ ∑
với
( )
|
i j
j i
i
C D
p D C
C
=
I
.
Trong công thức tính

)
|
H D C
là một trong những ñộ ño
không chắc chắn trong bảng quy ñịnh.
Mệnh ñề 1.2. Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
. Nếu
Q P C
⊆ ⊆
thì
(
)
(
)
| |
H D Q H D P
≥
. Dấu ñẳng thức xảy ra khi
, / ,
i j i j
X X U P X X
∀ ∈ ≠
, nếu
(
)
/
i j t

P
ñược ñịnh nghĩa bởi:
( )
1 1
1
c
p p
i
i i i
i i
X
X X X
E P
U U U U
= =
 
= = −
 
 
 
∑ ∑

với
c
i
X
là phần bù của
i
X
trong

ñạt giá trị lớn
nhất là
1 1/
U
−
. Vì vậy ta có
(
)
0 1 1/
E P U
≤ ≤ −
.
ðịnh nghĩa 1.13. Liang Entropy có ñiều kiện của
D
khi ñã biết
C
ñược ñịnh
nghĩa bởi:
1 1 1 1
| | | | | | | |
( | )
| | | | | | | |
c
m n m n
i j i j i j i i j
i j i j
C D C D C D C C D
E D C
U U U U
= = = =

k i k j
D X D X
∩ ∩ =
và
| || | 0
c
k j k i
D X D X
∩ ∩ =
với mọi
1,2, ,
k n
=
.
Chú ý: ñiều kiện bằng nhau
( | ) ( | )
E D Q E D P
=
của Mệnh ñề 2.3 tương
ñương với
i
X
và
j
X
ñều thuộc một khối
/
k
D U D
∈

CORE C
.
ðịnh nghĩa 1.15. Cho bảng quyết ñịnh
( , , , )
DS U C D V f
= ∪
. Nếu
R C
⊆
thỏa
mãn:
1)
( | ) ( | )
H D R H D C
=

2)
{
}
(
)
( | ) ( | )
r R H D R r H D C
∀ ∈ − ≠

thì
R
là một rút gọn của
C
dựa trên Shannon entropy.

)
{
}
(
)
| |
E D C E D C a
≠ −
, trái lại thuộc tính
a
gọi là không
cần thiết (dư thừa) dựa trên Liang entropy. Tập tất cả các thuộc tính cần thiết
trong
DS
dựa trên Liang entropy ñược gọi là tập lõi và ký hiệu là
(
)
E
CORE C
.
ðịnh nghĩa 1.17. Cho bảng quyết ñịnh
(
)
, , ,
DS U C D V f
= ∪
. Nếu
R C
⊆
thỏa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15 1.6.3. Mối liên hệ của tập rút gọn dựa trên Shannon entropy
1.6.3.1. Mối liên hệ giữa tập rút gọn Shannon entropy và tập rút gọn của
Pawlak
Cho bảng quyết ñịnh
(
)
, , ,
DS U C D V f
= ∪
, trong ñó Wang và các cộng sự
ñã chứng minh rằng với
B C
⊆
, nếu
( | ) ( | )
H D B H D C
=
thì
( ) ( )
B C
POS D POS D
=

nhưng chiều ngược lại không ñúng nếu
DS
không nhất quán. Hơn nữa, nếu

( )
H
R HRED C
∈ thì tồn tại một rút
gọn
P
R
của C dựa trên miền dương
(
)
( )
P
R PRED C
∈ sao cho
P H
R R
⊆

Nếu bảng quyết ñịnh
DS
nhất quán, khái niệm tập rút gọn dựa trên
miền dương và tập rút gọn dựa trên Shannon entropy là tương ñương nhau.
Ví dụ 1.3. Xét bảng quyết ñịnh
(
)
, , ,
DS U C D V f
= ∪
với
{


1
u

0 1 1 0
2
u

0 1 1 1
3
u

0 1 0 0
4
u

0 1 0 1
5
u

0 1 0 1
6
u

1 0 0 1
7
u

1 0 1 1
Bảng 1.3. Bảng quyết ñịnh minh họa Ví dụ 1.3