Bộ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
===SOHG3===

TRẦN THỊ PHƯƠNG LIÊN

NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN
THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH
KHÔNG ĐẦY ĐỦ VÀ ỨNG DỤNG

LUẬN VĂN THẠC sĩ MÁY TÍNH


Bộ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
===#T)tïïIoa===

TRẦN THỊ PHƯƠNG LIÊN

NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GON
THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH
KHÔNG ĐẦY ĐỦ VÀ ỨNG DUNG

a

Chuyên ngành: Khoa Học Máy Tính
Mã số: 60480101

LUẬN VĂN THẠC sĩ MÁY TÍNH

Người hướng dẫn khoa học: TS. Nguyễn Long Giang


PHỤ LỤC


I
DANH MỤC CÁC THUẬT NGỮ


7
Thuật ngữ tiếng Việt

Thuật ngữ tiếng Anh

Tập thô

Rough Set

Tập thô dung sai

Tolerance Rough Set

Hệ thông tin

Information System

Hệ thông tin đầy đủ

Complete Information System

Hệ thông tin không đầy đủ


Rút gọn thuộc tính

Attribute Reduction

Tập rút gọn

Reduct

Tập lõi

Core

Luật quyết định

Decision Rule

Khoảng cách

Distance
DANH MỤC CÁC BẢNG


8


V
DANH MỤC CÁC HÌNH VẼ

Hình 2.1. Móỉ' liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ 15

các phương pháp rút gọn thuộc tính có ý nghĩa thực tiễn cao. Hơn nữa, mô hình tập thô
dung sai được chứng minh là công cụ hiệu quả để giải quyết bài toán rút gọn thuộc tính,
việc tiếp tục nghiên cứu nhằm tìm ra các phương pháp mới, hiệu quả có ý nghĩa khoa học.
Do đó, tôi chọn đề tài “Nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết
định không đầy đủ và ứng dụng”


1
2. Mục đích nghiên cứu (Các kết quả cần đạt được)
Mục đích của luận văn trước hết là tổng kết các kết quả nghiên cứu về lĩnh vực rút
gọn thuộc tính và trích lọc luật trong bảng quyết định không đầy đủ theo tiếp cận mô hình
tập thô dung sai. Trên cơ sở đó, luận văn đề xuất phương pháp rút gọn thuộc tính dựa trên
độ đo khoảng cách phân hoạch và ứng dụng phương pháp vào bài toán chuẩn đoán bệnh
dựa vào các triệu chứng thu thập được từ bệnh nhân.
3. Nhiệm vụ nghiên cứu
-

Nắm bắt được các khái niệm cơ bản về lý thuyết tập thô truyền thống trên hệ thông tin đầy
đủ và mô hình tập thô dung sai trên hệ thông tin không đầy đủ

-

Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và trích lọc luật
quyết định trong bảng quyết định không đầy đủ theo tiếp cận mô hình tập thô dung sai, bao
gồm phân nhóm các phương pháp, so sánh, đánh giá các phương pháp dựa vào tập rút
gọn...

-

Xây dựng phương pháp rút gọn thuộc tính dựa vào khoảng cách phân hoạch, đánh giá

6. Cấu trúc của luận văn
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ề hệ thông tin đầy đủ và mô hình tập thô
truyền thống, hệ thông tin không đầy đủ và mô hình tập thô dung sai
Chương 2: trình bày hai nội dung chính, thứ nhất là: tổng kết, phân nhóm các
phương pháp rút gọn thuộc tính. Luật quyết định và các độ đo đánh giá hiệu năng. Lựa
chọn, so sánh đánh giá các các phương pháp rút gọn thuộc tính. Nội dung thứ hai là xây
dựng phương pháp rút gọn thuộc tính sử dụng khoảng cách, bao gồm xây dựng độ đo
khoảng cách, định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách,
xây dựng thuật toán heuristic tìm một tập rút gọn dựa trên khoảng cách. Phân nhóm và
đánh giá phương pháp sử dụng khoảng cách với các phương pháp đã có.
Chương 3 trình bày kết quả thử nghiệm và đánh giá phương pháp đề xuất trên các bộ
số liệu mẫu từ kho dữ liệu UCI [13] nhằm sáng tỏ các kết quả nghiên cứu về lý thuyết.
Chương 3 cũng trình bày ứng dụng phương pháp rút gọn thuộc tính và trích lọc luật trên bộ
số liệu thử nghiệm của bệnh viêm gan B.
Cuối cùng, phần diết luận nêu những đóng góp của luận văn, hướng phát triển tiếp
theo.
Chương 1. CÁC KHÁI NIỆM cơ BẢN
Chương này trình bày các khái niệm cơ bản về mô hình tập thô truyền thống trên các
hệ thông tin đầy đủ do Pawlak [10] đề xuất và mô hình tập thô dung sai trên các hệ thông
tin không đầy đủ do Kryszkiewicz [5] đề xuất. Các khái niệm cơ bản này là kiến thức nền
tảng để sử dụng cho các chương sau.
1.1.

Hệ thông tin đầy đủ và mô hình tập thô truyền thống

1.1.1.

Hệ thông tin đầy đủ

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
BNg (x) = BX -BX : B-miền biên của X, u -BX : B-miền ngoài của X.


1
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 chan 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= u B\Y^X},BX=\J fl|ynX*0Ị.
Trong trường hợp BNB(X) = 0 thì X được gọi là tập chính xác ịexact set),
ngược lại X được gọi là tập thô ịrough set).
Với B,ũcẨ,ta gọi B-miền dương của D là tập được xác định như sau
POSB(D)= u
X
Rõ ràng POSB(D) là tập tất cả các đối tượng u sao cho với mọi VẼÍ/ mà M(B) =
V(B) ta đều có W(D) = V(D). Nói cácỉrkhác, POSg(D) = Ịw eơ| [w] c[w] j.


1
Ví dụ 1.1. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân cho ở Bảng 1.1.
u
li Ị

Bảng 1.1. Bảng thông tin về bệnh cúm
Đau đầu
Thần nhiệt
Cảm cúm
Có


Không

U

Không

Rất cao

Có

Uy

Không

Cao

Có

Ug

Không

Rất cao

Không

6

Ta có: u I {Đau đầu} = {{«!,M2,M3},

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,CuD,V,f) với
Cnơ = 0.
Bảng quyết định DS được gọi là nhất quán nếu D phụ thuộc hàm vào c, tức là với
mọi M,VEƠ, c(w) = c(v) kéo theo D(W) = D(V). Ngược lại thì gọi là không nhất quán
hay mâu thuẫn. Theo định nghĩa miền dương, bảng quyết định 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.3.

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 ba nhóm: thuộc

tính ỉõi (core attribute), thuộc tính rút gọn (reductive attribute) và thuộc tính dư thừa
(redundant attribute). Thuộc tính ỉõi là thuộc tính 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 lõi xuất hiện trong tất cả các tập rút gọn của bảng quyết
định. Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ chúng rkhông ảnh hưởng đến
việc phân lớp tập dữ liệu, thuộc tính dư thừa không xuất hiện trong bất kỳ tập rút gọn nào
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 = (í/,CuD,V,/). Thuộc tính ceC được gọi là không cần thiết
(dispensable) trong DS nếu /,ỠSc(D) = /,OS(C_jc|)(D); Ngược lại, c


1
đượ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 ícC thỏa mãn:
1) POSR(D) = POSc(D)

hay một hạt thông tin. Ký hiệu tập tất cả các lớp dung sai sinh bởi quan hệ SIM(P) trên u là
u

khi đó các lớp dung sai trong u /5/M(P) không phải


1
là một phân hoạch của u mà hình thành một phủ của u vì chúng có thể giao nhau và u

)

= u . Ký hiệu tập tất cả các phủ của u sinh bởi các tập con thuộc tính
PcA là COVER{U).
Tương tự hệ thông tin đầy đủ, các tập P-xẩp xỉ dưới và P-xẩp xỉ trên của X trong hệ
thông tin không đầy đủ, ký hiệu lần lượt là PX và PX , được xác định như sau
PX = ịueuịsp (w) c X j = Ịw e X ỊS;, (w) c X j
PX = ịusu\sp(u)^x *0Ị = U Sp u u s 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 - P X , và
P-miền ngoài của X là tập u -PX .
Với các tập xấp xỉ được định nghĩa như trên, mô hình tập thô truyền thống được mở
rộng thành mô hình tập thô dung sai, nghĩa là mô hình tập thô dựa trên quan hệ dung sai.
1.1.2.

Bảng quyết định không đầy đủ
Xét bảng quyết địnhDS = {u ,c uD,V,/), nếu tồn tại u e u và ceC sao cho c(w) thiếu

giá trị thì DS được gọi là bảng quyết định không đầy đủ. Ta biểu diễn giá trị thiếu là và
bảng quyết định không đầy đủ là IDS = (ơ,Cuỡ,V,/) với Vú! ^D,'*' £Vd. Không mất tính
chất tổng quát, giả thiết D chỉ gồm một thuộc tính quyết định duy nhất {d|.
Cho bảng quyết định không đầy đủ IDS =ịu,Cuịd},V,fỴ Với flcC, u^U , dg(u) = ịfd (v)|v e


Thấp

*

Đầy đủ

Thấp

Tốt

u3
Uậ

*
Cao

*
*

Gọn nhẹ
Đầy đủ

Cao
Cao

Xấu
Tốt

U

Do đó, POSc([d)) = {u1,u2,u3}.
Hàm quyết định suy rộng của các đối tượng trên tập thuộc tính c là ÔC(M1) = {Tốt},
ẽc{ụ2) = {Tốt}, ôc(w3) = {Xẩu}, ỔC(M4)= {Tốt, Tuyệt hảo}, Ỡ (M5) = {Tốt, Tuyệt hảo},
C

õc(u6) = {Tốt, Tuyệt hảo}.
Do đó, IDS là bảng quyết định không nhất quán.
Chương 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT
TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
Chương này trình bày hai nội dung chính như sau:
1) Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và trích lọc luật
trong bảng quyết định không đầy đủ, bao gồm: tổng hợp và phân nhổm các phương pháp
rút gọn thuộc tính dựa vào tập rút gọn; tổng hợp các kết quả nghiên cứu về luật quyết định
và các độ đo đánh giá hiệu năng; tổng hợp các kết quả nghiên cứu về so sánh, đánh giá các
phương pháp rút gọn thuộc tính. Các kết quả này được công bố trong các công trình [3, 8].
2) Xây dựng phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao gồm: xây dựng
độ đo khoảng cách; định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng
cách; xây dựng thuật toán heuristic tìm tập rút gọn; phân nhóm, đánh giá phương pháp với
các phương pháp đã công bố.


2
2.1.

Rút gọn thuộc tính và trích lọc luật trong bảng quyết định không đầy đủ

2.1.1.

Tổng kết, phân nhóm 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ủ đề

2
mãn:
(1) ÕR (M) = ÕA (M) với mọi u G u
(2) V/? d R, tồn tại MẼƠ sao cho ÔR. (w) ^ ÕA (w)
thì R được gọi là một tập rút gọn của IDS dựa trên hàm quyết định suy rộng, a)
Các phương 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, cho đến nay đã có rất nhiều phương pháp rút
gọn thuộc tính dựa trên các độ đo khác nhau đã được công bố [3, 7, 8, 14]. Trong công
trình [7, 8, 14], các tác giả đã tổngrkết khá đầy đủ các phương pháp rút gọn thuộc tính
trong bảng quyết định không đầy đủ và các tập rút gọn tương ứng.


2
Bảng 2.1. Các phương pháp rút gọn thuộc tính trong công trình [3, 8, 14]
STT
1
2

Phương pháp

Tập rút gọn

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

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

dương[10].

miền dương



ma trận phân biệt

Phương pháp sử dụng độ đo

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

lượng thông tin[ 1 ].

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[2].

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

Như đã trình bày ở trên, mỗi phương pháp rút gọn thuộc tính đều đưa ra định nghĩa
về tập rút gọn và xây dựng thuật toán heuristic tìm tập rút gọn. Do đó, có thể nói rằng tập
rút gọn lỀnkết quả của phương pháp rút gọn thuộc tính. Vì vậy, việc phân nhóm các
phương pháp rút gọn thuộc tính cũng dựa vào tập rút gọn và được thực hiện theo nguyên
tắc: các phương pháp có tập rút gọn như nhau được phân thành một nhóm. Trong công
trình [7, 8, 14], các tác giả đã công bố về mối liên hệ giữa các tập rút gọn và kết quả phân
nhóm các phương pháp rút gọn thuộc tính như sau:


2
1) Nếu bảng quyết định nhất quán, các tập rút gọn Rp, Rg, Rg, RM , Rj,
Rm ,Rd, R F , R p là tương đương nhau.
2) Nếu bảng quyết định không nhất quán:
-

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
hàm ấn định Rg.

-

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 (/?,) tương đương với tập rút gọn dựa trên ma trận
dung sai (Rm ).

-


Hình 2.1. Mối liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ
Từ sơ đồ về mối liên hệ giữa các tập rút gọn, các tác giả trong [7, 8, 14] đã thực hiện
phân nhóm các tập rút gọn và chỉ ra mối liên quan hệ giữa các tập rút gọn của các nhóm.
Cụ thể:
Các tập rút gọn trong bảng không nhất quán được chia thành bốn nhóm:
Nhóm r. Bao gồm tập rút gọn Rp .
Nhóm 2: Bao gồm các tập rút gọn Rõ, Rg, RM .
Nhóm 3: Bao gồm các tập rút gọn RỊ , Rm , RD, Rp
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 Rl thuộc nhóm 1 sao cho /?J (Z (Z /?3.
• Neu 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 Cl R2 CI 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 bon nhóm tương ứng.
Đe đánh giá tính hiệu quả của một phương pháp rút gọn thuộc tính, cộng đồng
nghiên cứu về tập thô sử dụng hai tiêu chuẩn: 1) độ phức tạp về thời gian thực hiện thuật
toán heuristic tìm một tập rút gọn tốt nhất và 2) chất lượng phân lớp của tập rút gọn. Các
công bố về rút gọn thuộc tính đều tính toán độ phức tạp thời gian thuật toán tìm tập rút
gọn. Do đó, hoàn toàn có thể so sánh được tính hiệu quả của các phương pháp về tiêu


2
chuẩn thời gian. Vì vậy, luận văn tập trung nghiên cứu việc đánh giá các phương pháp dựa
trên tiêu chuẩn chất lượng phân lớp của tập rút gọn.
Việc đánh giá chất lượng phân lớp của tập rút gọn dựa vào số lượng thuộc tính của
tập rút gọn và chất lượng phân lớp của từng thuộc tính, về mặt định tính, tập rút gọn có số
thuộc tính càng ít thì chất lượng phân lớp càng cao. Tuy nhiên, điều này chưa hẳn đã chính
xác vì chất lượng phân lớp của từng thuộc tính khác nhau. Tóm lại, ta cần phải sử dụng độ