Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
1
LỜI CẢM ƠN
Để hoàn thành đồ án này tác giả đã nhận được sự chỉ bảo tận tình,
cùng những yêu cầu nghiêm khắc của thầy giáo TS. Nguyễn Đức Thuần.
Em xin bày tỏ lòng biết ơn sâu sắc tới thầy vì đã hướng dẫn và chỉ bảo tận
tình để em có thể hoàn thành đồ án này.
Em xin cảm ơn các thầy cô trong Khoa Công nghệ Thông tin đã giúp
đỡ và tạo điều kiện cho em trong quá trình thực hiện đồ án cũng như trong
toàn khóa học.
Tác giả cũng xin chân thành cảm ơn tình cảm của bạn bè trong suốt
quá trình học tập, rèn luyện tại trường Đại học Nha Trang. Nha Trang, tháng 06 năm 2011

Hàng Nguyên Huy
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
2
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

2.2.1) Công thức 23
2.2.2) Độ chính xác và độ phủ của phân lớp 24
2.2.3) Luật nguyên tố 25
2.2.4) Luật khẳng định 25
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
5
2.2.5) Luật loại trừ và luật phủ định 26
2.3) Một số kết quả đạt được 28
2.3.1) Luật khẳng định 28
2.3.2) Luật phủ định 30
2.3.3) Mở rộng luật phủ định 31
2.3.4) Luật tối thiểu 33
2.3.5) Mối tương quan giữa luật khẳng định và phủ định 35
2.4) Bài toán xác định loại luật 39
2.4.1) Phát biểu 39
2.4.2) Các dạng bài toán xác định loại luật 39
2.5) Kết luận 40
CHƯƠNG 3 41
CHƯƠNG TRÌNH THỬ NGHIỆM 41
3.1) Tổ chức dữ liệu 41
3.2) Các kết quả đạt được 42
3.2.1) Luật nguyên tố 42
3.2.2) Luật tối thiểu 43
3.2.3) Xác định luật 45
3.3) Kết luận và hướng phát triển đề tài 45
Tài liệu tham khảo 47
PHỤ LỤC 48
1) Bộ dữ liệu NTU Data 48
2) Các bộ dữ liệu UCI 50


Hình 2.5: Giản đồ Venn cho luật phủ định. 32
Hình 2.6: Giản đồ Venn cho luật phủ định mở rộng 33
Hình 2.7: Giản đồ Venn cho κ nhỏ nhưng độ trùng lắp lớn. 35
Hình 2.8: Giản đồ Venn cho α nhỏ nhưng độ trùng lắp lớn. 36
Hình 2.9: Giản đồ Venn cho độ trùng lắp nhỏ 36
Hình 3.1: Sơ đồ lớp lớp MyList 42
Hình 3.2: Giao diện chương trình sinh luật nguyên tố ứng với bộ dữ liệu
Nursery 43
Hình 3.3: Giao diện chương trình sinh luật tối thiểu với bộ dữ liệu NTU
Data 44
Hình 3.4: Giao diện chương trình kiểm tra luật 45

Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
8
LỜI MỞ ĐẦU

Lý thuyết tập thô (rough set theory) – do Z. Pawlak đề xuất vào
những năm đầu thập niên tám mươi của thế kỷ hai mươi – đã thu hút được
nhiều sự quan tâm nghiên cứu và được áp dụng ngày càng rộng rãi trong
nhiều lĩnh vực. Lý thuyết này được phát triển trên một nền tảng toán học
vững chắc và cung cấp những công cụ hữu ích để giải quyết các bài toán
phân tích dữ liệu, phát hiện luật… Hiện nay, có nhiều công trình nghiên
cứu nhắm vào các hướng khai thác dữ liệu (data mining) và khám phá tri
thức (knowledge discovery) từ dữ liệu thô để biến thành thông tin, từ thông
tin thành tri thức và vận dụng tri thức đó vào cuộc sống. Một trong những
hướng khai thác dữ liệu là dựa vào lý thuyết tập thô nhằm làm rõ các mối
quan hệ của dữ liệu mang tính mơ hồ, phân lớp theo các thuộc tính quan
trọng, tinh giảm dữ liệu thừa, phát sinh các luật quyết định…
“Phát hiện tập luật khẳng định và phủ định dựa vào lý thuyết tập
thô và ứng dụng” là đề tài em nghiên cứu dưới sự hướng dẫn của thầy giáo

k
} ⊆ A, ta ký hiệu bộ các giá trị u(b
i
)
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
u(b
i
) = v(b
i
), với mọi i =1, 2, , k.
1.2) Quan hệ không phân biệt được
Xét hệ thống thông tin S = (U, A), với mỗi tập thuộc tính B ⊆ A
tạo ra một quan hệ hai ngôi trên U, ký hiệu IND(B)
IND(B) =
{( , ) | ( ) ( ), }
u v U U u a v a a B
∈ × = ∀ ∈

IND(B) được gọi là quan hệ B_không phân biệt được. Dễ kiểm chứng đây
là một quan hệ tương đương trên U. Với mọi đối tượng u ∈ U, lớp tương
đương của u trong quan hệ IND(B) được kí hiệu bởi [u]
B
. Tập thương xác
định bởi quan hệ IND(B) được ký hiệu U/IND(B) hay U/B, tức là
U/IND(B)= U/B = {[u]
B
| u ∈ U}.
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
10
Ví dụ 1.1: Xét hệ thống thông tin cho ở bảng 1.1

4
, x
5
, x
6
}.
A = {Đau đầu, Đau cơ, Nhiệt độ, Cúm}.
Trong bảng, các bệnh nhân x
2
, x
3
và x
5
không phân biệt được đối với
thuộc tính Đau đầu, bệnh nhân x
3
và x
6
không phân biệt được đối với thuộc
tính Đau cơ, Cúm và bệnh nhân x
2
, x
5
không phân biệt được đối với thuộc tính
Đau đầu, Đau cơ và Nhiệt độ.
Do đó:
IND({Đau đầu}) = {{x
1
, x
4

, x
6
}, {x
4
}},
IND({Cúm}) = {{x
1
, x
2
, x
3
, x
6
}, {x
4
, x
5
}},
IND({Đau đầu, Đau cơ}) = {{x
1
, x
4
, x
6
}, {x
2
, x
5
}, {x
3

( )
R X
bao gồm các phần tử của U có khả năng được phân loại
vào những phần tử thuộc X ứng với quan hệ R.
Từ hai tập xấp xỉ người ta định nghĩa các tập:
BN
B
(X) =
( ) ( )
R X R X
−
: B- miền biên của X.
POS
B
(X) =
( )
R X
: B-vùng dương của X.
NEG
B
(X) =
( )
U R X
−
: B-vùng âm của X.
Ký hiệu tập thương của IND(B) trên U là U/B, các xấp xỉ trên và
dưới của X có thể viết lại:
( )
R X
=

8
},
A = {a, b, c, d, e}

Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
12
U a b c d e
x
1
1 0 2 2 0
x
2
0 1 1 1 2
x
3
2 0 2 1 1
x
4
1 1 0 2 2
x
5
1 0 2 0 1
x
6
2 2 0 1 1
x
7
2 1 1 1 2
x
8

, E
6
}.
Với tập X = {x
2
, x
3
, x
4
} ta có các xấp xỉ, miền biên, miền ngoài là:
XR
= E
3
∪ E
4
= {x
3
, x
4
},
X
R
= E
2
∪ E
3
∪ E
4
= {x
2

= {x
1
, x
5
, x
6
, x
7
}.

Hình 1.1: Minh họa tập thô
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
13
Đối với một hệ thống thông tin S = (U, A), B, D ⊆ A, ký hiệu R =
IND(B), người ta gọi B-miền khẳng định dương của D là tập được xác định
như sau:
/
( ) ( ( ))
B
V U D
POS D R V
∈
=
U

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

}, {x
2
, x
4
, x
7
, x
8
}, {x
6
}},
U/D = {{x
1
}, {x
2
, x
4
, x
7
}, {x
3
, x
5
, x
6
, x
8
}}.
Với V = {x
1

1.4) Các tính chất của xấp xỉ
Cho một hệ thống thông tin S = (U, A), ∀X, Y ⊆ U và B ⊆ A.
Đặt R = IND(B). Khi đó:
(1L)
( )
R U U
=

(1H)
( )
R U U
=

(2L)
( )R
∅ = ∅

(2H)
( )R
∅ = ∅

(3L)
( )
R X X
⊆

(3H)
( )
R X X
⊇

R U X U RX
− = −

(7L)
( ) ( )
X Y R X R Y
⊆ ⇒ ⊆

(7H)
( ) ( )
X Y R X R Y
⊆ ⇒ ⊆

(8L)
( ( )) ( )
R U R X U R X
− = −

(8H)
( ( )) ( )
R U R X U R X
− = −

(9L)
/ , ( )
K U R R K K
∀ ∈ =

(9H)
/ , ( )

≤ ≤
. Nếu
( ) 1
R
X
α
=
, ta nói X là chính xác đối với R, còn
( ) 1
R
X
α
<
, X được gọi là thô đối với R.

Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
15
Ví dụ 1.4: Xét hệ thông tin S = (U, A) ở bảng 1.2
Với B = {a, b, c} và X = {x
2
, x
3
, x
4
} thì độ chính xác của X trên B là:
α
B
(X
1
) =

, x
4
, x
5
, x
6
},
A = {Đau đầu, Đau cơ, Nhiệt độ, Cúm}.
Tập thuộc tính điều kiện C = {Đau đầu, Đau cơ, Nhiệt độ}
Tập thuộc tính quyết định D = {Cúm}.
U Đau đầu Đau cơ Nhiệt độ Cúm
x
1
Không Có Cao Có
x
2
Có Không Cao Có
x
3
Có Có Rất cao Có
x
4
Không Có
Bình
thường
Không
x
5
Có Không Cao Không
x

∀ ∈ ≠

B được gọi là rút gọn C-miền khẳng định dương của D.
Ví dụ 1.6: Xét hệ thông tin S = (U, A) ở bảng 1.3
Cho D = {Cúm}, C = {Đau đầu, Đau cơ,Nhiệt độ}.
Ta có:
U/D = {{x
1
, x
2
, x
3
, x
6
}, {x
4
, x
5
}},
U/C = {{x
1
}, {x
2
, x
5
}, {x
3
}, {x
4
}, {x

}, {x
3
}}
=> POS
R1
(D) = {x
3
} ≠ POS
C
(D).
Vậy R
1
không phải là rút gọn của C.
Đặt R
2
= {Đau đầu, Nhiệt độ}
⊆
C
=> U/R
2
= {{x
1
}, {x
2
, x
5
}, {x
3
}, {x
4

}, {x
2
, x
5
}, {x
3
}, {x
4
}, {x
6
}}
=> POS
R3
(D) = {x
1
, x
3
, x
4
, x
6
} = POS
C
(D).
Vậy R
3
là 1 rút gọn của C.
Đặt R
4
= {Đau đầu}

=> U/R
5
= {{x
1
, x
3
,

x
4
, x
6
}, {x
2
, x
5
}}
=> POS
R5
(D) = Ø ≠ POS
C
(D).
Vậy R
5
không phải là rút gọn của C.
Đặt R
6
= {Nhiệt độ}
⊆
C

Vậy R
6
không phải là rút gọn của C.
Do đó: RED(C) = {{Đau đầu, Nhiệt độ}, {Đau cơ, Nhiệt độ}}
=> CORE(C) = {Đau đầu, Nhiệt độ} ∩ {Đau cơ, Nhiệt độ}
= {Nhiệt độ}.
1.8) Ma trận phân biệt được và hàm phân biệt được
1.8.1) Ma trận phân biệt được
Xét bảng quyết định T = (U, C ∪ D), với U = {u
1
, u
2
, , u
n
}. Ma trận
phân biệt được của T ký hiệu M(T) =
ij
( )
n n
m
×
là một ma trận đối xứng, trong
đó mỗi phần tử của nó là một tập thuộc tính được xác định như sau:
ij
{ | ( ) ( )} , ( ) ( )
, ( ) ( )

i j i j
i j
c C u c u c u D u D


∅ ∅
2 {b, c}

Ø {a, b}

{b, c}

3
∅
{a, b}

∅
{a, c}

4
∅
{b, c}

{a, c}

∅
Bảng 1.5: Ma trận phân biệt được của hệ thông tin ở bảng 1.4.

1.8.2) Hàm phân biệt được
Hàm phân biệt được
f
Τ
là một hàm boole, được xác định từ ma trận
phân biệt M(T) như sau:

= ∅ và u
i
(D) = u
j
(D),
(3)
∨m
ij
= false, nếu m
ij
= ∅ và u
i
(D) ≠ u
j
(D).
U a b c
d
1 1 0 1 1
2 1 1 2 0
3 0 0 2 1
4 1 0 1 2
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
19
Ví dụ 1.8: Xét hệ thông tin S = (U, C
∪
D) ở bảng 1.6.
U = {o
1
, o
2

o
3
o
4
o
5

o
1
∅

{a, c, d}
∅

{a, d}
∅

o
2

{a, c, d}

∅

{a, c, d}

{c} {a, b, c, d}

o
3

cdcatruedatruedcaf
∨∨∧∨∧∨∧∨∨∨
∧∧∨∨∧∧∨∧∧∨∨=
Τ

1.9) Luật quyết định
Cho T = (U, C ∪ D) là một bảng quyết định, giả sử U/C={X
1
, X
2
, , X
m
}
và U/D = {Y
1
, Y
2
, , Y
n
}. Nếu X
i
∩ Y
j
≠ ∅, ký hiệu des(X
i
), des(Y
j
) lần lượt là
các mô tả của các lớp tương đương ứng với X
i


Ở đây |.| là bản số hay lực lượng của một tập hợp. Rõ ràng giá trị của
( ), ( )
ij ij
Z s Z
µ
của luật quyết định Z
ij

rơi vào đoạn
1
,1
U
 
 
 
. Để thuận tiện
trong trình bày ký hiệu |Z
ij
| được sử dụng thay cho
i j
X Y
∩
.
1.10) Phụ thuộc độ k
Cho hệ thống thông tin S = (U, A), X, Y ⊆ A. Chúng ta nói rằng tập
thuộc tính Y phụ thuộc độ k ∈ [0,1] vào tập thuộc tính X, ký hiệu
k
X Y
→

U
VR
k
/
)(

Khi
0
X Y
→
, chúng ta sẽ viết X → Y và
1
X Y
→
được viết X → Y.
Dễ thấy rằng phụ thuộc độ k là sự tổng quát hóa của phụ thuộc hàm và
1
X Y
→
là phụ thuộc hàm đã biết trong CSDL quan hệ.
Ví dụ 1.9: Xét hệ thống thông tin S = (U, C
∪
D) ở bảng 1.8:
U = {u
1
, u
2
, u
3
, u

4
2 2 2
u
5
3 3 3
u
6
3 1 3
u
7
1 3 3
u
8
2 3 3
u
9
3 2 2
Bảng 1.8: Hệ thông tin dùng để minh họa phụ thuộc độ k
Ta có:
IND(C) = {{u
1
}, {u
2
}, {u
3
}, {u
4
}, {u
5
}, {u

1
, u
2
, u
3
, u
4
, u
5
, u
6
, u
7
, u
8
, u
9
}
=>
1
9
9
)(
===
U
DPOS
k
C

Vậy D → C.

7
, u
8
, u
9
}.
=> k = 6/9 = 2/3.
Vậy D phụ thuộc một phần vào B với độ phụ thuộc là k = 2/3.
1.11) Kết luận
Chương này đã trình bày một số khái niệm cơ bản nhất trong lý
thuyết tập thô như hệ thống thông tin, bảng quyết định, quan hệ không phân
biệt được, luật quyết định, phụ thuộc độ k… Đây là cơ sở để ta tìm các luật
quyết định ở chương tiếp theo.
Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
22
CHƯƠNG 2
LUẬT KHẲNG ĐỊNH VÀ LUẬT PHỦ ĐỊNH
2.1) Giới thiệu
Các phương pháp sinh luật được phân thành hai lớp: - Lớp các luật
tất định (deteministic rules) và Lớp các luật xác suất (probabilistic rules).
Luật tất định và luật xác suất đều có dạng if X then Y. Xét U là tập vũ trụ,
ký hiệu tập các đối tượng thỏa điều kiện X là C, tập các đối tượng thỏa kết
luận Y của luật là D.
Nếu C ⊆ D thì luật if X then Y là luật tất định. Trong trường hợp C
không là tập con của D, C ∩ D ≠ ∅ và |C ∩ D| / |C| ≥ δ, δ là ngưỡng thể
hiện độ khít của sự trùng lắp của 2 tập hợp, luật if X then Y là luật xác suất.
Cả hai lập luận để rút trích luật tất định và luật xác suất là lập luận khẳng
định (positive reasoning).
Tuy nhiên, trong một số lĩnh vực ngoài lập luận khẳng định còn cần
thiết phải lập luận bác bỏ (negative reasoning), nhất là trong lĩnh vực y tế.

a
là miền giá trị
thuộc tính a. Một bảng quyết định là một hệ thống thông tin S= (U,A∪{d}),
với bảng 2.1 ta có: U = {1, 2, 3, 4, 5, 6}, A = {Age, Location, Nature,
Prodrome, Nausea, M1} và d = Class. Đối với thuộc tính Location ∈ A,
miền trị của Location được xác định V
Location
= {Occular, Whole, Lateral}.
Ví dụ 2.1:
No

Age Location

Nature Prodrome

Nausea

M1

Class
1
2
3
4
5
6
50 – 59

40 – 49


Yes
Yes
No
Yes
Yes

Yes

No
No
Yes

Yes

M.c.h
M.c.h
Migra
Migra
M.c.h
Pyscho

Bảng 2.1: Một hệ thống thông tin đơn giản.

Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
24
Một công thức nguyên tố (atomic formula) xác định trên B ⊆ A∪{d}
và V là một biểu thức có dạng [a = v], a ∈ B, v ∈ V
a
. Với bảng 2.1 thì
[Location = Occular] là 1 công thức. Ký hiệu F(B, V) là tập nhỏ nhất chứa

¬
f)
S
= U – f
S

Ví dụ 2.2: f = [Location = Whole] => f
S
= {2, 4, 5, 6}
g = [Location = Whole]
∧
[Nausea = No]
=> g
S
= {2, 4, 5, 6}
I
{1, 2, 5} = {2, 5}.
2.2.2) Độ chính xác và độ phủ của phân lớp

Định nghĩa 2.1: Cho R, D là các công thức thuộc F(B, V), D là một
công thức xác định trên tập thuộc tính quyết định d. Độ chính xác, độ phủ
của phân lớp xác định bởi R → D (không nhầm lẫn ta ký hiệu D thay cho
D
S
) được biểu diễn lần lượt theo các công thức:
))|((
||
||
)( RDP
R


I
D = {3, 4}
=> α
R
(D) = 2/3; κ
R
(D) = 1

Đồ án tốt nghiệp GVHD: TS. Nguyễn Đức Thuần
25
2.2.3) Luật nguyên tố

Đinh nghĩa 2.2:
Luật R → D được gọi là luật nguyên tố, nếu R là một công thức
nguyên tố.
2.2.4) Luật khẳng định

a) Định nghĩa 2.3: Luật khẳng định
Luật R → D, với R =
∧
j
[a
j
= v
k
] được gọi là luật khẳng định nếu
α
R
(D) = 1.

= {1, 2, 5}
và D = [Class = M.c.h] ⇒ D
S
= {1, 2, 5}
⇒ α
R
(D) = 3/3 = 1, R là công thức nguyên tố.
⇒ Luật khẳng định nguyên tố:
[Nausea = No] → [Class = M.c.h].

Trích đoạn Bài toán xác định loại luật

---