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

------------------

CHỬ THỊ QUỲNH HOA

NGHIÊN CỨU MỐI QUAN HỆ GIỮA PHỤ THUỘC
HÀM VÀ BẢNG QUYẾT ĐỊNH TRONG CHẨN
ĐOÁN BỆNH

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

Thái Nguyên - 2015


LỜI CẢM ƠN
Em xin chân thành bày tỏ lòng biết ơn sâu sắc đến TS. Lê Văn Phùng,
người thầy đã hết lòng giúp đỡ và tạo điều kiện tốt nhất để em hoàn thành
luận văn này.
Em xin chân thành cảm ơn toàn thể các Thầy, cô công tác tại Viện
CNTT và Trường Đại học Công Nghệ Thông Tin và Truyền Thông - Đại Học
Thái Nguyên đã luôn tận tình chỉ bảo, giúp đỡ, tạo điều kiện và truyền đạt
kiến thức cho em trong suốt quá trình học tập và thực hiện luận văn.
Xin chân thành cảm ơn Ban Giám Hiệu Trường THPT Định Hóa, gia
đình, bạn bè và đồng nghiệp đã không ngừng quan tâm, động viên, giúp đỡ và
tạo mọi điều kiện tốt nhất cho tôi trong suốt thời gian học tập và thực hiện
luận văn.
Mặc dù đã cố gắng rất nhiều, nhưng do thời gian có hạn và bản thân còn
những hạn chế nhất định nên luận văn không tránh khỏi thiếu sót. Em rất
mong nhận được các ý kiến phê bình, góp ý của Hội đồng bảo vệ luận văn,

1.1. Các khái niệm cơ bản về hệ thông tin và tập thô ............................. 3
1.1.1. Hệ thông tin ............................................................................... 3
1.1.2. Tập thô ...................................................................................... 5
1.1.3. Bảng quyết định ........................................................................ 8
1.1.4. Cơ sở dữ liệu quan hệ ............................................................... 10
1.1.5. Tập rút gọn và lõi ...................................................................... 12
1.1.6. Luật quyết định ......................................................................... 14
1.2. Khai phá dữ liệu ................................................................................ 15
1.2.1. Khai phá dữ liệu và phát hiện tri thức ....................................... 15
1.2.2. Các chức năng khai phá dữ liệu ................................................ 17
1.2.3. Các hệ thống khai phá dữ liệu và kiến trúc tổng quát của chúng.. 18
1.2.4. Các loại dữ liệu có thể khai phá được ........................................ 22
1.2.5. Khai phá dữ liệu theo hướng tiếp cận tập thô ............................. 22
1.3. Bài toán chẩn đoán bệnh .................................................................... 23
1.3.1. Vai trò của phương pháp chẩn đoán lâm sàng trong y học ........ 23
1.3.2. Giá trị thực tiễn của việc xác định quan hệ giữa phụ thuộc hàm và
bảng quyết định trong chẩn đoán bệnh ................................................ 24


ii

1.4. Kết luận chương 1 ............................................................................. 26
Chương 2. MỐI QUAN HỆ GIỮA PHỤ THUỘC HÀM VÀ BẢNG
QUYẾT ĐỊNH THEO HƯỚNG TIẾP CẬN TẬP THÔ ........................ 27
2.1. Xác định các phụ thuộc hàm từ bảng quyết định ............................ 27
2.1.1. Thuộc tính rút gọn và các thuật toán tìm chúng ......................... 27
2.1.2. Thuật toán tìm họ tất cả các tập rút gọn trong bảng quyết định .. 36
2.1.3. Tập lõi trong bảng quyết định ................................................... 38
2.1.4. Thuật toán xác định các phụ thuộc hàm từ bảng quyết định .. .... 42
2.2. Xây dựng bảng quyết định từ tập phụ thuộc hàm ........................... 44

Thuật ngữ tiếng Việt

Thuật ngữ tiếng Anh

Tập thô

Rough Set

Hệ thông tin

Information System

Bảng quyết định

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


Sơ đồ quan hệ

Relation Schema

Phụ thuộc hàm

Functional Dependency

Khóa, phản khóa

Key, Antikey

Tập tối thiểu của thuộc tính a

Minimal set of the attribute a

Họ các tập tối thiểu của thuộc tính Family of all minimal sets of attribute
a

a


v

Danh mục các ký hiệu, các từ viết tắt
Ký hiệu, từ viết tắt

Diễn giải

S  U , A


U /B

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

 B (u )

Hàm quyết định suy rộng của đối tượng u đối với B .

BX

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

BX

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

BN B  X 

B - miền biên của X

POS B  D 

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

PRED  C 

Họ tất cả các tập rút gọn Pawlak

PCORE  C 

PTH

Phụ thuộc hàm


vii

Danh sách bảng
Bảng 1.1. Bảng dữ liệu về bệnh cúm .......................................................... 4
Bảng 1.2. Bảng thông tin về bệnh cúm ....................................................... 7
Bảng 1.3. Bảng quyết định ......................................................................... 9
Bảng 1.4. Bảng quyết định về bệnh cúm .................................................... 14
Bảng 2.1. Bảng quyết định ở Ví dụ 2.1 ...................................................... 30
Bảng 2.2. Bảng quyết định về bệnh cúm ở Ví dụ 2.2 ................................. 32
Bảng 2.3. Bảng rút gọn thứ nhất của hệ thống bệnh cúm R1 ...................... 33
Bảng 2.4. Bảng rút gọn thứ hai của hệ thống bệnh cúm R2 ........................ 33
Bảng 2.5. Bảng quyết định ở Ví dụ 2.3 ...................................................... 37
Bảng 2.6. Bảng quyết định minh họa Ví dụ 2.4 ........................................... 41
Bảng 2.7. Bảng quyết định được xây dựng từ Thuật toán 2.16 ................... 54


viii

Danh sách hình vẽ

Hình 1.1. Quá trình phát hiện tri thức ..........................................................16
Hình 1.2. Kiến trúc của một hệ thống khai phá dữ liệu điển hình ............... 20
Hình 2.1. Sơ đồ thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định
.................................................................................................................... 43
Hình 2.2. Sơ đồ thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm

với C  D =  . Bảng quyết định là mô hình thường gặp trong thực tế, khi mà
giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về
giá trị của thuộc tính quyết định. Bảng quyết định là nhất quán khi phụ thuộc
hàm C → D là đúng, trái lại là không nhất quán.
Với bảng quyết định nhất quán T = (U,C  D) , tập thuộc tính R  C
được gọi là một tập rút gọn của tập thuộc tính điều kiện C nếu R là tập tối


2

thiểu thỏa mãn phụ thuộc hàm R  D . Giả sử D chỉ chứa một thuộc tính duy
nhất d  , nếu xem bảng quyết định T là quan hệ r trên tập thuộc tính C  d 
thì khái niệm tập rút gọn tương đương với khái niệm tập tối thiểu của thuộc
tính d  trên quan hệ. Khi đó, một số bài toán trong bảng quyết định liên
quan đến tập rút gọn có thể được giải quyết bằng một số kết quả liên quan đến
tập tối thiểu của một thuộc tính trong lý thuyết cơ sở dữ liệu quan hệ; bao
gồm bài toán tìm tập tất cả các thuộc tính rút gọn, bài toán trích lọc các phụ
thuộc hàm từ bảng quyết định, bài toán xây dựng bảng quyết định thỏa mãn
tập phụ thuộc hàm cho trước.
Do tính hấp dẫn và tính thời sự của khai phá dữ liệu, đặc biệt là mối
quan hệ giữa phụ thuộc hàm và bảng quyết định để từ bảng quyết định trích
lọc các phụ thuộc hàm và xây dựng bảng quyết định thỏa mãn tập phụ thuộc
hàm cho trước nên tôi lựa chọn đề tài “Nghiên cứu mối quan hệ giữa phụ
thuộc hàm và bảng quyết định trong chẩn đoán bệnh” là luận văn cao học của
mình. Trong đó vận dụng kiến thức nghiên cứu này vào chẩn đoán bệnh lâm
sàng trong lĩnh vực y học.


3


tượng u và v giống nhau (không phân biệt được) nếu chỉ xem xét giá trị tại các
thuộc tính trong B. Quan hệ tương đương IND(B) xác định một phân hoạch
trên U, ký hiệu U/IND(B) hay U/B, tức là U/IND(B) = U/B =

u B | u  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. Khi đó [u]B = {vU|(u,v) IND(B)}. [6]
Ví dụ 1.1. Xét hệ thông tin cho ở bảng 1.1
U

Đau đầu

Đau cơ

Thân nhiệt

u1

Không

Có

Bình thường Không

u2

Có

Không


Rất cao

Có

u6

Có

Có

Rất cao

Có

Cúm

Bảng 1.1. Bảng dữ liệu về bệnh cúm
Trong đó:

U = {u1, u2, u3, u4, u5, u6}
A = {Đau đầu, Đau cơ, Thân nhiệt, Cúm}

Trong bảng, các bệnh nhân u2, u4 và u6 không phân biệt được đối với
thuộc tính Đau đầu; bệnh nhân u5 và u6 không phân biệt được đối với thuộc
tính Đau cơ, Cúm và bệnh nhân u2, u4 không phân biệt được đối với thuộc
tính Đau đầu, Đau cơ và Thân nhiệt.
Do đó:
IND({Đau đầu}) = {{u1, u3, u5},{u2, u4, u6}}
IND({Đau cơ}) = {{u1, u3, u5, u6},{u2, u4}}

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ần lượt là BX và BX , được xác định
như sau:









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ó khả năng được phân loại vào X ứng
với quan hệ R 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,

POSB ( X )  BX : B-vùng dương của X
NEGB  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
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

Nói

cách

khác,



POS B ( D)  u U u B  u D .

Trên cơ sở đó có thể tính B-xấp xỉ dưới và B-xấp xỉ trên của X nhờ thuật
toán sau:
Thuật toán 1.1. [2] Xác định xấp xỉ dưới, xấp xỉ trên
Đầu vào: Hệ thông tin S = (U, A), tập thuộc tính B  A , tập đối tượng

X U .
Đầu ra: Tập các đối tượng BX và BX
Phương pháp:
1. Xác định các lớp tương đương X 1B , X 2B ,......, X mB của IND(B)
2. Khởi tạo BX : ; và BX : ;
3. Với mọi giá trị của j  1,...., m
begin
Nếu X Bj  X thì BX : BX  X Bj
Nếu X Bj  X   thì BX : BX  X Bj
end.
Thuật toán 1.1 có độ phức tạp là O(k|U|log|U|), trong đó |B|  |A| = k. [2]
Ví dụ 1.2. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân


7


Có

u4

Không

Bình thường

Không

u5

Không

Cao

Không

u6

Không

Cao

Có

u7

Không

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 , u6 , u7 , u8 .
Đặt X  {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u8 .
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 , u7 ; X 2  u2 , u3 , u6 , u8 , BX 1  u1 , u4  ;

BX 2  u2 , u3 , POS B ( D) 

  BX   u1, u2 , u3 , u4 .
X U / D


8

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 . [1]
1.1.3. Bảng quyết định
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 (còn được gọi là hệ quyết định: decision system) là một
dạng đặc biệt của hệ thông tin T đầy đủ, trong đó tập các thuộc tính A bao
gồm hai tập con khác rỗng tách biệt nhau: tập các thuộc tính điều kiện C và

Thân nhiệt

Cúm

x1

Không

Có

Cao

Có

x2

Có

Không

Cao

Có

x3

Có

Có


Có

Bảng 1.3. Bảng quyết định
Cho

một

bảng

quyết

định

T  U , C  D  ,

giả

sử

U / C   X 1 , X 2 ,..., X m  và U / D  Y1 , Y2 ,..., Yn  . Một lớp X i U / C được gọi
là nhất quán nếu u (d )  v (d ), u , v  X i , d  D, lúc này cũng có thể viết
u ( D )  v ( D )  X i ( D); một lớp Yi U / D được gọi là nhất quán ngược nếu
u (a)  v( a), u, v  Yi , a  C.

Một bảng quyết định T  U , C  D  là nhất quán nếu mọi lớp
X i U / C là nhất quán, ngược lại T được gọi là không nhất quán. Dễ thấy

nếu U / C  U / D thì T  U , C  D  là nhất quán.
Tương tự, nếu U / D  U / C , thì T là nhất quán ngược. [6]


(PTH

AB

thỏa

mãn

quan

hệ

r

trên

hi , h j  r    a  A  hi  a   h j  a     b  B   hi  b   h j  b   .

R)

nếu
Đặt

Fr   A, B  : A, B  R, A  B là họ đầy đủ các PTH thỏa mãn quan hệ r. Ký

hiệu P  R  là tập các tập con của R. Cho F  P  R   P  R  . Ta nói rằng F là
một họ f trên R nếu với mọi A, B, C , D  R

1  A, A  F .
 2   A, B   F ,  B, C   F   A, C   F .




A  R A  R  F  ,  A, R   F . Ta gọi A là một khóa tối thiểu của r

(tương ứng của s) nếu A là một khóa của r (tương ứng của s) và bất kỳ một
tập con thực sự của A không là khóa của r (tương ứng của s). Ký hiệu K r và
K s tương ứng là tập tất cả các khóa tối thiểu của r và s.

Cho

s   R, F 

là

SĐQH



trên

R,

aR.

Đặt



K as  A  R : A  a,  B :  B  a  B  A . Khi đó, K as được gọi là họ

 B  C 

cũng là một hệ Sperner trên R. Nếu K là một hệ Sperner

trên R đóng vai trò là tập các khóa tối thiểu của quan hệ r (hoặc SĐQH s) thì
K

1

là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là


12

tập các phản khóa. Nếu K là một hệ Sperner trên R đóng vai trò là họ các tập
tối thiểu của thuộc tính a trên r (hoặc trên s), hay K  K ar (hoặc K  K as ),
thì K

1

 

 K ar

1

(hoặc K

1



trên



R.



B  B  a  Fr ,



, A  B  B  a  F  .

Đặt

Er   Eij :1  i  j  r  với

Eij  a  R : hi  a   h j  a  . Er được gọi là hệ bằng nhau của r. Đặt





M r  A  P  R  : Eij  A,  E pq : A  E pq . M

r

được gọi là hệ bằng nhau

dựa

trên

miền

dương

nếu

POSC  D   POS(C c)  D  ; Nói cách khác, c  C là không cần thiết khi và

chỉ khi trên POSC  D  phụ thuộc hàm C \ c  D nghiệm đúng; ngược lại, c
được gọi là cần thiết. Bảng quyết định T được gọi là độc lập nếu mọi thuộc
tính c  C đều cần thiết. Tập tất cả các thuộc tính cần thiết trong T được gọi
là tập lõi dựa trên miền dương và được ký hiệu là PCORE  C  . Lúc đó, thuộc
tính cần thiết còn được gọi là thuộc tính lõi.
Định nghĩa 1.4. [11] (Tập rút gọn dựa trên miền dương) Cho bảng quyết định

T  U , C  D  và tập thuộc tính R  C . Nếu
1) POS R ( D)  POSC ( D)
2) r  R, POS R r ( D)  POSC ( D) (Nghĩa là: T   U , R  D  độc lập)
thì R là một tập rút gọn của tập thuộc tính điều kiện C dựa trên miền dương.
Nói cách khác, R là tập rút gọn nếu nó là tập tối tiểu thỏa mãn
POS R ( D )  POSC ( D) .

Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Rõ ràng
là có thể có nhiều tập rút gọn của C. Ký hiệu PRED  C  là họ tất cả các tập
rút gọn Pawlak của C trong T. Một thuộc tính là cần thiết khi và chỉ khi nó
thuộc vào mọi tập rút gọn của C. Khi đó PCORE  C  


u1

Có

Có

Không

Bình thường Không

u2

Có

Có

Có

Cao

Có

u3

Có

Có

Có


Không

Có

Rất cao

Có

Cảm cúm

Bảng 1.4. Bảng quyết định về bệnh cúm
Bảng này có hai tập rút gọn là R1 = {Đau cơ, Thân nhiệt} và R2 = {Đau
đầu, Thân nhiệt}. Như vậy tập lõi là PCORE(C) = {Thân nhiệt} và Thân nhiệt
là thuộc tính cần thiết duy nhất. Các thuộc tính không cần thiết bao gồm:
 Thuộc tính Mệt mỏi là thuộc tính dư thừa thực sự vì không tham gia
vào rút gọn nào.
 Hai thuộc tính Đau đầu và Đau cơ là hai thuộc tính rút gọn vì đều có
mặt trong một tập rút gọn. Hai thuộc tính này đều không cần thiết
theo nghĩa là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính
này mà vẫn chẩn đoán đúng bệnh. Tức là
POS{Đau cơ, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm})
POS{Đau đầu, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}). [1]
1.1.6. Luật quyết định
Cho

T  (U , C  D)

là