MỤC LỤC
MỞ ĐẦU ..................................................................................................... - 1 CHƢƠNG 1. CÁC KHÁI NIỆM VỀ LÝ THUYẾT TẬP THÔ VÀ LÝ
THUYẾT VỀ CƠ SỞ DỮ LIỆU ............................................................... - 3 1.1. CÁC KHÁI NIỆM VỀ LÝ THUYẾT TẬP THÔ ................................ - 4 1.1.1 Hệ thông tin đầy đủ ......................................................................... - 4 1.1.2. Mô hình tập thô truyền thống......................................................... - 5 1.1.3. Bảng quyết định đầy đủ ................................................................. - 7 1.1.4 Tập rút gọn và tập lõi ...................................................................... - 8 1.1.5. Ma trận phân biệt và hàm phân biệt ............................................. - 10 1.2. LÝ THUYẾT VỀ CƠ SỞ DỮ LIỆU ................................................ - 11 1.2.1. Quan hệ ........................................................................................ - 11 1.2.2. Phụ thuộc hàm .............................................................................. - 11 1.2.3. Hệ tiên đề Armstrong ................................................................... - 12 1.2.4. Sơ đồ quan hệ ............................................................................... - 12 1.2.5. Khoá và phản khoá ....................................................................... - 12 1.2.6. Hệ bằng nhau và hệ bằng nhau cực đại........................................ - 13 1.3. MỘT SỐ THUẬT TOÁN CƠ BẢN .................................................. - 14 CHƢƠNG 2: MỘT SỐ PHƢƠNG PHÁP TÌM MỘT TẬP RÚT GỌN VÀ
TÌM CÁC TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH ............. - 19 2.1.Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric ..... - 19 2.1.1.Khoảng cách Jaccard giữa hai tập hợp hữu hạn............................ - 19 2.1.2. Một số tính chất của metric trên bảng quyết định........................ - 21 2.2. THUậT TOÁN TÌM TậP TấT Cả CÁC THUộC TÍNH RÚT GọN CủA BảNG QUYếT
ĐịNH NHấT QUÁN ....................................................................................... - 33 -

2.2.1. Đặt vấn đề .................................................................................... - 33 2.2.2. Thuật toán..................................................................................... - 34 -


2.3. THUậT TOÁN TÌM Họ TấT Cả CÁC TậP RÚT GọN CủA BảNG QUYếT ĐịNH NHấT
QUÁN ......................................................................................................... - 37 -

2.4. THUậT TOÁN XÂY DựNG CÁC PHụ THUộC HÀM Từ BảNG QUYếT ĐịNH NHấT QUÁN
.................................................................................................................. - 40 2.5. THUậT TOÁN XÂY DựNG BảNG QUYếT ĐịNH Từ TậP PHụ THUộC HÀM...... - 41 CHƢƠNG 3: THỰC NGHIỆM THUẬT TOÁN TÌM MỘT TẬP RÚT
GỌN ........................................................................................................... - 46 3.1. THử NGHIệM CÁC THUậT TOÁN HEURISTIC TÌM MộT TậP RÚT GọN TốT NHấT - 46 3.1.1.Mô tả thuật toán CEBARKCC ...................................................... - 47 3.1.2.Thử nghiệm và đánh giá các thuật toán trên các bộ số liệu mẫu trong
UCI ......................................................................................................... - 48 3.2. THử NGHIệM THUậT TOÁN TÌM TậP RÚT GọN THEO THAM Số Độ CHắC CHắN . - 51 3.3. THử NGHIệM THUậT TOÁN TÌM TấT Cả CÁC THUộC TÍNH RÚT GọN CủA BảNG
QUYếT ĐịNH NHấT QUÁN .............................................................................. - 52 -

3.4. MộT Số GIAO DIệN CHƢƠNG TRÌNH THử NGHIệM ...................................... - 53 3.4.1. Giao diện chính của chƣơng trình ................................................ - 53 3.4.2.Nạp các tệp dữ liệu mẫu lấy từ kho dữ liệu UCI .......................... - 53 3.4.3. Thực hiện thuật toán CEBARKCC .............................................. - 54 3.4.4. Thực hiện thuật toán sử dụng khoảng cách.................................. - 55 3.4.5.Thực hiện thuật toán sinh luật quyết định từ tập rút gọn .............. - 55 3.4.6.Thực hiện thuật toán tìm tất cả thuộc tính rút gọn ........................ - 56 KẾT LUẬN ............................................................................................... - 57 -


-1-

MỞ ĐẦU
Khai phá dữ liệu là một trong những vấn đề rất sôi động hiện nay và
đƣợc ứng dụng rộng rãi. Có rất nhiều phƣơng pháp khai phá dữ liệu, một
trong những phƣơng pháp đó là sử dụng lý thuyết tập thô - một trong những
công cụ quan trọng trong khai phá dữ liệu. 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út gọn dữ liệu, trích lọc các tri thức tiềm ẩn trong
dữ liệu dƣới dạng mẫu và các luật quyết định, bảng quyết định.

rút gọn.
- Tìm hiểu một số lý thuyết về cơ sở dữ liệu
- Tìm hiểu một số thuật toán tìm một tập rút gọn và tất cả các tập rút
gọn trong bảng quyết định
- Cài đặt thử nghiệm một thuật toán tìm tập rút gọn trong bảng quyết định.
Bố cục luận văn gồm:
Mở đầu: Đặt vấn đề về ý nghĩa, tính cấp thiết của đề tài
Chƣơng 1: Các khái niệm cơ bản
Trong chƣơng này, sẽ đi tìm hiểu về các khái niệm hệ thống thông tin,
bảng quyết định, tập rút gọn, quan hệ, phụ thuộc hàm, tiên đề Armstrong,
khoá, phản khoá... và một số thuật toán cơ bản trong cơ sở dữ liệu quan hệ
đƣợc sử dụng để xây dựng các thuật toán rút gọn trong bảng quyết định....
Đây là những phần lý thuyết cơ sở để triển khai, nghiên cứu trong các chƣơng
tiếp theo.
Chƣơng 2: Tìm hiểu về một số thuật toán tìm một tập rút gọn và thuật
toán tìm tất cả các tập rút gọn trong bảng quyết định.
Trong chƣơng này, chúng tôi đề xuất một số thuật toán trên bảng quyết
định liên quan đến tập rút gọn: xác định một tập rút gọn và tất cả các tập rút
gọn trong bảng quyết định (dựa trên lý thuyết cơ sở dữ liệu quan hệ).
Chƣơng 3: Triển khai cài đặt thử nghiệm một thuật toán tìm một tập rút
gọn trong bảng quyết định, từ đó rút ra một số kết luận.
Kết luận


-3-

Chƣơng 1. CÁC KHÁI NIỆM VỀ LÝ THUYẾT TẬP THÔ VÀ LÝ
THUYẾT VỀ CƠ SỞ DỮ LIỆU
Lý thuyết tập thô - do Zdzislaw Pawlak [12] đề 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

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   Va với Va là tập giá trị của thuộc tính a  A ; f là hàm thông tin,
a A

với mọi a  A và u U hàm f cho giá trị f u, a  Va .
Với mọi u U , a  A , ta ký hiệu giá trị của đối tƣợng u tại thuộc tính a
là u  a  thay vì f 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ị u  bi  bởi u  B  . Nhƣ vậy, nếu u và v là hai đối
tƣợng, thì ta viết u  B  v  B nếu u bi   v bi  với mọi i  1,..., k .
Nếu với mọi u U và a  A , u  a  đều chứa giá trị khác rỗng thì hệ
thông tin đƣợc gọi là hệ thông tin đầy đủ. Trong luận văn này, hệ thông tin đầy
đủ đƣợc gọi tắt là hệ thông tin và đƣợc ký hiệu là IS  U , A,V , f  .
Xét hệ thông tin IS  U , A,V , f  . Với 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, u  a   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 u, v   IND B  thì hai đối tƣợng u và v
không phân biệt đƣợc bởi các thuộc tính trong B. 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


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   .

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 dựa


-6-

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
BNB  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 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ể viết lại
BX  Y U / B Y  X  , BX  Y U / B Y  X  .

Trong trƣờng hợp BN B  X    , X đƣợc gọi là tập rõ, ngƣợc lại X đƣợc gọi là
tập thô.

Có
Không
Bình thƣờng
Không
Không
Cao
Không
Không
Rất cao
Có
Không
Cao
Có
Không
Rất cao
Không
Ta có: U / {Đau đầu} = u1 , u2 , u3  , u4 , u5 , u6 , u7 , u8 
U
u1
u2
u3
u4
u5
u6
u7
u8

U / {Thân nhiệt} =

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


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.

ứng dụng là bảng quyết định.
Bảng quyết định đầy đủ là một dạng đặc biệt của hệ thông tin đầy đủ,
trong đó tập các thuộc tính A bao gồm hai tập con tách biệt 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. Trong luận văn


-8-

này, bảng quyết định đầy đủ đƣợc gọi tắt là bảng quyết định và đƣợc ký hiệu
là DS  U , C  D,V , f  với 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  .
Ngƣợc lại DS là không nhất quán. Dễ thấy bảng quyết định DS là 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.
1.1.4 Tập rút gọn và tập lõi
Trong bảng quyết định, các thuộc tính điều kiện đƣợc phân thành thuộc
tính lõi và thuộc tính không cần thiết. 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. Thuộc tính không
cần thiết là thuộc tính dƣ thừa mà việc loại bỏ thuộc tính này không ảnh
hƣởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết đƣợc phân
thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính
dư thừa thực sự là những thuộc tính dƣ thừa mà việc loại bỏ tất cả các thuộc
tính nhƣ vậy không ảnh hƣởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn,
với một tổ hợp thuộc tính nào đó, nó là thuộc tính dƣ thừa và với một tổ hợp
các thuộc tính khác nó có thể là cốt yếu.
Định nghĩa 1.3. [8] (Tập lõi dựa trên miền dƣơng) Cho 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 (dƣ thừa)

trong DS dựa trên miền dƣơng nếu POSC  D   POS(C c)  D  ; Ngƣợc lại, c đƣợc

nói rằng a là thuộc tính dư thừa thực sự của DS nếu a  C 



R.

RPRED C 

Ví dụ 1.2. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.2.
Bảng 1.2. Bảng quyết định về bệnh cúm
U

Mệt mỏi

Đau đầu

Đau cơ

Thân nhiệt

u1

Có

Có

Có

Bình thƣờng Không


Có

Bình thƣờng Không

u5

Có

Không

Không

Cao

Không

u6

Có

Không

Có

Rất cao

Có

Cảm cúm




 c  C ui (c)  u j (c)
mi j  



if

ui ( D)  u j ( D),

if

ui ( D)  u j ( D) .

Định nghĩa 1.7. [2, 7] (Tập rút gọn dựa trên ma trận phân biệt) Cho
bảng quyết định DS  U , C  D,V , f  , M   mi j nn là ma trận phân biệt của DS
và tập thuộc tính R  C . Nếu
1) R  mi j   với mọi mi j  
2) Với mọi r  R , R  r không thỏa mãn 1) thì R đƣợc gọi là một tập
rút gọn của C dựa trên ma trận phân biệt. Ký hiệu SRED C  là họ tất cả các tập
rút gọn dựa trên ma trận phân biệt.
Định nghĩa 1.8. [2, 7] (Tập lõi dựa trên ma trận phân biệt) Cho bảng
quyết định DS  U , C  D,V , f  , M   mi j nn là ma trận phân biệt của DS.
Thuộc tính c  C đƣợc gọi là không cần thiết (dƣ thừa) trong DS dựa trên ma
trận phân biệt nếu C  c  mi j   với mọi mi j   . Ngƣợc lại, c đƣợc gọi là


- 11 -



tập hữu hạn, khác rỗng các thuộc tính,

r  h1 ,..., hm  là một quan hệ trên tập thuộc tính R  a1,..., an  . Phụ thuộc hàm

(PTH) trên R là một dãy ký tự có dạng A B với A, B  R. PTH A B thỏa
mãn quan hệ r trên R nếu  hi , h j  r    a  A  hi  a   hj  a    b  B  hi  b  hj  b   .
Đặt Fr   A, B  : A, B  R, A  B là họ đầy đủ các PTH thỏa mãn quan hệ
r. Khi đó tất cả các PTH đúng trong r.


- 12 -

1.2.3. Hệ tiên đề Armstrong
Giả sử R là tập các thuộc tính, 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.
3  A, B  F , A  C, D  B  C, D  F.
4  A, B  F, C, D  F   A  C, B  D   F.
Rõ ràng là Fr là một họ f trên R. Nếu F là một họ f trên R thì có một
quan hệ r trên R sao cho Fr = F. Ký hiệu F  là tập tất cả các PTH đƣợc dẫn
xuất từ F bằng việc áp dụng các quy tắc 1   4 .
1.2.4. Sơ đồ quan hệ
Sơ đồ quan hệ (SĐQH) s là một cặp  R, F  với R là tập thuộc tính và F

Gọi K  P  R là một hệ Sperner trên R nếu với mọi A, B K kéo theo
A  B . Dễ thấy K r , K s , K ar , K as là các hệ Sperner trên R. Với tập K là một hệ

Sperner trên R, Giả sử K là một hệ Sperner trên R. Ta định nghĩa tập các
phản khoá của K là K
K

1

1

nhƣ sau:

  A  R :  B  K    B  A và nếu  A  C    B  K

Dễ thấy K

1

 B  C 

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

Nhận xét: 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



1


r

K    A  R : A  a  F
s
a

1





, A  B  B  a  Fr ,



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

1.2.6. Hệ bằng nhau và hệ bằng nhau cực đại
Cho r một quan hệ trên R. Đặt Er  Eij :1  i  j  r  với Eij  a  R : hi a   h j a  .





E r đƣợc gọi là hệ bằng nhau của r. Đặt M r  A  P  R  : Eij  A,  E pq : A  E pq .

1

Bước q  1 (q

 2n1/2 /  .n1/2

hệ

Sperner

bất

kỳ

trên

R

không

vƣợt

quá

với n  R . Do đó, độ phức tạp thời gian của Thuật toán

2.2 là hàm số mũ theo n.
- Trƣờng hợp Iq  Im  q  1,..., m  1 , độ phức tạp của Thuật toán 2.2



không lớn hơn O R 2 K K 1
theo R , K và K


1

là hệ Sperner trên R và C  b1,..., bm   R sao cho

:BC

Đầu ra: D K
Bước 1: Đặt T  0  C .
Bước i  1 : Đặt
T (i  1)  T i   bi 1

nếu B K 1 không có T  B

T (i  1)  T i 

ngƣợc lại.

Cuối cùng đặt D  T  m .


- 16 -

Thuật toán 2.4. [5] Tìm tập K từ tập K 1 .
Đầu vào: Cho tập K 1  B1,..., Bm  là hệ Sperner trên R
Đầu ra: Tập K
Bước 1: Bởi Thuật toán 2.3 tính A1 , đặt H 1  A1 .
Bước i  1 : Nếu có B H i 1 sao cho B  B j j :1  j  k  thì bởi Thuật
toán 2.3 tính Ai 1 , ở đây Ai 1  K , Ai 1  B . Đặt H i 1  H i  Ai 1 . Trong trƣờng hợp
ngƣợc lại, đặt K  H i .


2

O R K

1 2

K

 , độ phức tạp này là đa thức theo

R,K

1

và K . Nếu K là

đa thức theo R , K 1 thì Thuật toán 2.4 là hiệu quả. Nếu K là nhỏ thì Thuật
toán 2.4 rất hiệu quả.
Nhận xét
- Nếu K

1

là hệ Sperner trên R đóng vai trò là tập phản khóa của quan

hệ r (hoặc SĐQH s) thì Thuật toán 2.4 thực hiện tìm tập khóa tối thiểu K
- Nếu K

1

2

Thuật toán 2.6. [4] Tìm họ các tập tối thiểu của thuộc tính a trên s.
Đầu vào: Cho s   R, F  là SĐQH và a  R .
Đầu ra: K as .
Bước 1: Đặt L 1  E1  a .
Bước i+1: Nếu có C và A  B mà C  L i  , A  B  F , E  L i   E  A  C  B 
thì bởi Thuật toán 2.5 ta xây dựng Ei 1 , ở đây Ei1  A  C  B  , Ei1 K as . Đặt
L(i  1)  L  i  Ei 1 . Trong trƣờng hợp ngƣợc lại đặt K as  L i  .

Độ phức tạp Thuật toán 2.6
Theo [4], độ phức tạp thời gian tồi nhất của Thuật toán 2.6 là





O R F K as R  K as

 . Nhƣ vậy, độ phức tạp này là đa thức theo

R , F và

K as . Nếu số lƣợng phần tử của K as đối với s   R, F  là đa thức theo kích

thƣớc của s thì thuật toán hiệu quả, đặc biệt khi K as nhỏ.
u2

Thấp


Tốt

u5

*

*

Đầy đủ

Cao

Tuyệt hảo

u6

Thấp

Cao

Đầy đủ

*

Tốt


- 18 -

Bảng 2.1 là bảng quyết định không đầy đủ IDS  U , C  d  ,V , f  với

3
3
3
3

Các lớp dung sai của phủ U / SIM a4 là
Sa  (u1 )  Sa  (u2 )  {u1 , u2 , u6 } , Sa  (u3 )  Sa  (u4 )  Sa  (u5 )  {u3 , u4 , u5 , u6}, Sa  (u6 )  U
4
4
4
4
4
4

Các lớp dung sai của phủ U / SIM d là
Sd (u1 )  Sd (u2 )  Sd (u4 )  S d (u6 )  {u1 , u2 , u4 , u6 }, S d (u3 )  {u3}, S d (u5 )  {u5 }

Thực hiện các bƣớc của Thuật toán 4.2 ta có





d E K  C  , K  C  d  

U

4
  S u    S u   S  u     36
U




i

d

i

a1

i

a 1 ,d



U

1
U

  S  u   S   u   S  u   S

2

  S u   S  u   S  u   S
i 1



thông tin phân lớp của bảng quyết định.
Đối với một bảng quyết định có thể có nhiều tập rút gọn khác nhau. Số
lƣợng các tập rút gọn trong trƣờng hợp xấu nhất có thể là 2k - 1, với k là các
thuộc tính điều kiện. Tuy nhiên, trong thực tế thƣờng 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 theo tiêu chí đánh giá nào
đó là đủ.
Trong phần này, chúng tôi xin giới thiệu một số phƣơng pháp tìm tập
rút gọn và đƣa ra một số thuật toán tìm một tập rút gọn mới với độ phức tạp
có thời gian đa thức đồng thời đƣa ra một số thuật toán tìm tất cả các tập rút
gọn.
2.1. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric
2.1.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn
Định nghĩa 2.1. [7] Cho U là tập hữu hạn các đối tƣợng và X , Y  U .
Biểu thức
D  X ,Y   1

X Y
X Y

đƣợc gọi là khoảng cách Jaccard (Jaccard distance) giữa X và Y và biểu thức
J  X ,Y  

X Y
X Y

đƣợc gọi là hệ số Jaccard. Hệ số Jaccard đo độ tƣơng tự giữa hai tập hợp X và
Y. Hiển nhiên D  X , Y   J  X , Y   1 .


- 20 -

J  X , Y   J  X , Z  và J Y , Z   J  X , Z  . Từ (3.2) ta có
V XY 

J  X ,Y 
V XX  V YY 
1 J  X ,Y 

(3.3)

Dễ thấy V Y V X V Y V Z   0 hoặc V YY  V YZ  V XY  V XY  0 thỏa mãn vì
phần tử thứ k của V Y  V X  và V Y  V Z  là 0 và 1. Kết hợp với (3.2) ta có
V YY 

J Y , Z 
J  X ,Y 
J X,Z
V YY  V ZZ  
V XX  V YY  
V XX  V ZZ   0



1  J Y , Z 
1 J  X ,Y 
1 J  X , Z 


- 21 -




Từ giả thiết J  X ,Y   J X ,Z   0 ta có

J  X ,Y 
J X,Z

 0 . Do đó từ (3.5)
1 J  X ,Y  1 J  X , Z 

 J  X ,Y 
 J  X ,Y 
J  X , Z   XX
J  X , Z   YY



 V  J  X , Y  
 V
 1 J  X ,Y  1 J  X , Z  
 1  J  X ,Y  1  J  X , Z  

(3.6)

Tƣơng tự
 J Y , Z 
 J Y , Z 
J  X , Z   ZZ
J  X , Z   YY



Nếu V YY  0 thì hiển nhiên (3.1) thỏa mãn. Giả sử V YY  0 . Khi đó, (3.8)
tƣơng đƣơng với:
 J  X , Y   J Y , Z  
J  X ,Y   J  X ,Y 
J  Y , Z   J Y , Z 
1

 J  X , Z  

1 J  X ,Y 
1  J Y , Z 
1 J  X , Z 


2

2

 J  X , Y   J Y , Z   1  J  X , Z  . Do đó, đẳng thức (3.1) đƣợc chứng minh.

2.1.2. Một số tính chất của metric trên bảng quyết định
Với bảng quyết định DS  U , C  D,V , f  , Mệnh đề 3.1 sau đây xây
dựng công thức tính khoảng cách giữa hai tri thức K C  và K C  D  dựa vào
các phân hoạch U / C và U / D .


- 22 -

Mệnh đề 3.1. Cho bảng quyết định DS  U , C  D,V , f  , giả sử
U / C  {C1 , C2 ,..., Cm } và U / D  {D1 , D2 ,..., Dn } . Ta có

 ti

 U . Ta có

i

i 1

m

Di  C j  ui1 D  ui1 C  ui 2 D  ui 2 C  ...  uis j   uis j  .
  D  C

Di  C j  ui1 D  ui1 C  ui 2 D  ui 2 C  ...  uis j   uis j   s j
  D  C
Di  C j

2



Cj

Di  C j Di  C j
Cj



ui1 D  ui1 C
ui1 C


n

m



m

Cj
n

m


i 1 j 1

sj

 

Di  C j

i 1 j 1

1
1
U

uik D  uik C

i 1

ui D  ui C
ui C

ui C  ui C D
i C  ui C  D

 u 
i 1

uik D  uik C
k 1
uik C
ti



 d J  K C  , K C  D  .


- 23 -

Mệnh đề 3.2. Cho bảng quyết định DS  U , C  D,V , f  . Giả sử
d J  K C  , K C  D   là khoảng cách giữa hai tri thức K C  và K C  D  ,

  DS  là độ chắc chắn của DS. Ta có
d J  K C  , K C  D      DS   1 .

Chứng minh

  DS1     DS2 

 1    DS1   1    DS2  . Do đó theo Mệnh đề 3.2 ta có
d J  K Q  , K Q  D    d J  K  P  , K  P  D   .

Dấu đẳng thức xảy ra khi và chỉ khi   DS1     DS2  . Từ Nhận xét 2.2 ta
kết

luận

d J  K Q  , K Q  D    d J  K  P  , K  P  D  

khi

và

chỉ

khi

H  D Q  H  D P .

Mệnh đề 3.3 cho thấy tập thuộc tính P càng lớn thì khoảng cách giữa
hai tri thức K  P  và K  P  D  càng nhỏ, hay K  P  càng gần (càng tƣơng tự)