Số hóa bởi Trung tâm Học liệu
1
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
HOÀNG TIẾN HIẾU
RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC
LUẬT TRÊN BẢNG QUYẾT ĐỊNH KHÔNG
ĐẦY ĐỦ DỰA TRÊN MÔ HÌNH TẬP THÔ
DUNG SAI LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Long Giang
Thái Nguyên – 2013
Số hóa bởi Trung tâm Học liệu
2
KẾT LUẬN 50
Tài liệu tham khảo 51
Số hóa bởi Trung tâm Học liệu
3
Danh mục các thuật ngữ
Thuật ngữ tiếng Việt
Thuật ngữ tiếng Anh
Tập thô
Rough Set
Hệ thông tin
Information System
Hệ thông tin đầy đủ
Complete Information System
Hệ thông tin không đầy đủ
Incomplete Information System
Hệ thông tin không nhất quán
Inconsistent Information System
Bảng quyết định
Decision Table
Bảng quyết định đầy đủ
Complete Decision Table
Bảng quyết định không đầy đủ
Incomplete 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
Bảng 3.3. Kết quả thực hiện Thuật toán HDBAK và Thuật toán IQBAK 47
trên các bộ số liệu lớn 47
Bảng 3.4. Tập rút gọn tốt nhất của bộ số liệu Soybean-small 48
Bảng 3.5. Các luật phân lớp trên bảng quyết định rút gọn 49 Số hóa bởi Trung tâm Học liệu
5
MỞ ĐẦU
Lý thuyết tập thô - do Zdzislaw Pawlak [16] đề 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 quyết
các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, 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 tiền xử lý số liệu, khai phá dữ
liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và trích lọc luật quyết định
(luật phân lớp) là hai ứng dụng chính của lý thuyết tập thô trong khai phá dữ liệu.
Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn trích lọc luật thuộc giai
đoạn khai phá dữ liệu. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư
thừa nhằm tím tập con nhỏ nhất của tập thuộc tính điều kiện (tập rút gọn) mà bảo
toàn thông tin phân lớp của bảng quyết định. Dựa trên tập rút gọn thu được, việc
sinh luật và phân lớp đạt hiệu quả cao nhất.
Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị trên miền
giá trị thuộc tính, gọi là các bảng quyết định không đầy đủ. Trên bảng quyết định
không đầy đủ, Kryszkiewicz [10] đã mở rộng quan hệ tương đương trong lý thuyết
tập thô truyền thống thành quan hệ dung sai và đề xuất mô hình tập thô dung sai
nhằm trích lọc luật trực tiếp không qua bước xử lý giá trị thiếu. Dựa trên mô hình
tập thô dung sai, một số công trình công bố trong mấy năm gần đây đã đề xuất một
số độ đo không chắc chắn nhằm giải quyết bài toán rút gọn thuộc tính và trích lọc
luật, đáng chú ý là các công trình [6, 7, 8, 11, 13, 12, 23]. Tuy nhiên, các kết quả
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ề mô hình tập thô truyền thống,
phương pháp rút gọn thuộc tính trong mô hình tập thô truyền thống và mô hình tập
thô mở rộng dựa trên quan hệ dung sai, phương pháp rút gọn thuộc tính trong mô
hình tập thô dung sai. Tổng kết các công bố mới nhất về các phương pháp rút gọn
thuộc tính, mối liên hệ, phân nhóm các phương pháp
Số hóa bởi Trung tâm Học liệu
7
Chương 2 đề xuất phương pháp rút gọn thuộc tính sử dụng khoảng cách
Hamming. Trích lọc luật quyết định từ tập rút gọn theo phương pháp rút gọn thuộc
tính sử dụng khoảng cách Hamming.
Chương 3 cài đặt, thử nghiệm, đánh giá phương pháp trên các bộ số liệu
mẫu từ kho dữ liệu UCI.
Cuối cùng, phần kế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. Số hóa bởi Trung tâm Học liệu
8
Chương 1. RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN LÝ THUYẾT
TẬP THÔ
Mô hình tập thô truyền thống do Pawlak đề xuất [16] là công cụ hiệu quả để
giải quyết bài toán phân lớp trên các hệ thông tin đầy đủ dựa trên quan hệ tương
đương. Tuy nhiên trong thực tế, các hệ thông tin thường thiếu giá trị trên miền giá
trị của thuộc tính, gọi là các hệ thông tin không đầy đủ. Trong hệ thông tin không
đầy đủ, Kryszkiewicz [10] được xem là người đầu tiên mở rộng quan hệ tương
đương thành quan hệ dung sai và xây dựng mô hình tập thô mở rộng dựa trên quan
f u a V
.
Với mọi
,u U a A
, ta ký hiệu giá trị thuộc tính a tại đối tượng u là
au
thay vì
,f u a
. Nếu
12
, , ,
k
B b b b A
là một tập con các thuộc tính thì ta ký
hiệu bộ các giá trị
i
bu
bởi
Bu
. Như vậy, nếu u và v là hai đối tượng, thì ta viết
B u B v
nếu
ii
b u b v
với mọi
1, ,ik
.
Cho hệ thông tin
,,,IS U A V f
thì hai đối tượng u và v không phân biệt được
bởi các thuộc tính trong P. 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
/UP
. Ký hiệu lớp tương đương trong phân hoạch
/UP
chứa đối tượng u là
P
u
, khi đó
,
P
u v U u v IND P
.
2) Mô hình tập thô truyền thống
Cho hệ thông tin
,,,IS U A V f
và tập đối tượng
XU
. Với một tập thuộc
tính
BA
cho trước, chúng ta có các lớp tương đương của phân hoạch
/UB
, 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?
Số hóa bởi Trung tâm Học liệu
10
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 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
B
BN X
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 D A
, ta gọi B-miền dương của D là tập được xác định như sau
/
()
B
X U D
POS D BX
Rõ ràng
()
B
POS D
Có
u
3
Có
Rất cao
Có
u
4
Không
Bình thường
Không
u
5
Không
Cao
Không
u
6
Không
Rất cao
Có
u
7
Không
Cao
Như vậy, các bệnh nhân
23
,uu
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à:
Số hóa bởi Trung tâm Học liệu
11
1 2 3 4 5 7 6 8
, , , , , , ,u u u u u u u u
.
Đặt
{X u u
(Cảm cúm) = Có} =
2 3 6 7
, , ,u u u u
. Khi đó:
23
,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
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.2 Rút gọn thuộc tính trong mô hình tập thô truyền thống
1) 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 là một hệ thông tin 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 C D V f
với
CD
.
Xét bảng quyết định
, , ,DS U C D V f
với giả thiết
,u U d D
,
du
12
2) Tập lõi và tập rút gọn trong bảng quyết định
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 lõ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 lõ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 khô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.
- Tập lõi
Cho bảng quyết định
, , ,DS U C D V f
. Thuộc tính
cC
được gọi là
không cần thiết (dispensable) trong DS dựa trên miền dương nếu
()
C
Cc
POS D POS D
; Ngược lại, c đượ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 dựa trên miền dương 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.
- Tập rút gọn
Cho bảng quyết định
, , ,DS U C D V f
và tập thuộc tính
.
Cho bảng quyết định
, , ,DS U C D V f
và
aC
. Ta nói rằng a là thuộc
tính dư thừa của DS nếu
R PRED C
a C R
.
Số hóa bởi Trung tâm Học liệu
13
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
Cảm cúm
u
1
Có
Có
Có
Bình thường
Không
Cao
Không
u
6
Có
Không
Có
Rất cao
Có
Bảng này có hai tập rút gọn là R
1
= {Đau cơ, Thân nhiệt} và R
2
= {Đ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
lõi 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 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 chuẩn
đoán đúng bệnh. Tức là
POS
{Đau cơ, Thân nhiệt}
({Cảm cúm}) = POS
C
({Cảm cúm})
POS
{Đau đầu, Thân nhiệt}
3) Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt
4) Phương pháp rút gọn thuộc tính sử dụng các độ đo trong tính toán hạt
5) Phương pháp rút gọn thuộc tính sử dụng entropy thông tin
1.2. Rút gọn thuộc tính theo tiếp cận mô hình tập thô dung sai
1.2.1 Hệ thông tin không đầy đủ và mô hình tập thô dung sai
Với hệ thông tin
,IS U A
, nếu tồn tại
uU
và
aA
sao cho
au
chứa giá
trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ, trái lại IS
được gọi là hệ thông tin đầy đủ. Ta biểu diễn giá trị thiếu được ký hiệu là „*‟ và hệ
thông tin không đầy đủ là
,IIS U A
.
Xét hệ thông tin không đầy đủ
,IIS U A
), với tập thuộc tính
PA
ta định
nghĩa một quan hệ nhị phân trên U như sau
, , '*' '*'SIM P u v U U a P a u a v a u a v
.
Số hóa bởi Trung tâm Học liệ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
PA
là
COVER U
.
Trên
COVER U
ta định nghĩa một quan hệ thứ tự bộ phận
,COVER U
như sau.
Định nghĩa 1.1. [10] Cho hệ thông tin không đầy đủ
,IIS U A
với
,P Q A
. Ta nói:
1) Phủ
/U SIM P
và phủ
/U SIM Q
là như nhau (viết
//U SIM P U SIM Q
) khi và chỉ khi
,
PQ
u U S u S u
.
2)
/U SIM P
mịn hơn
/U SIM P
Số hóa bởi Trung tâm Học liệu
16
2) Nếu
P Q A
thì
//U SIM Q U SIM P
.
3) Nếu
,P Q A
thì
P Q P Q
S u S u S u
với
uU
.
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
PP
PX u U S u X u X S u X
PP
PX u U S u X S u u U
Tốc độ tối đa
u
1
Cao
Cao
Đầy đủ
Thấp
u
2
Thấp
*
Đầy đủ
Thấp
u
3
*
*
Gọn nhẹ
Cao
u
4
Cao
*
Đầy đủ
Cao
u
( ) { }
A
S u u
,
4 4 5
( ) { , }
A
S u u u
5 4 5 6
( ) { , , }
A
S u u u u
,
6 2 5 6
( ) { , , }
A
S u u u u
.
Với
34
,P a a
ta có
Số hóa bởi Trung tâm Học liệu
17
1 2 3 4 5 6
/ ( ) { ( ), ( ), ( ), ( ), ( ), ( )}
P P P P P P
Xét bảng quyết định
,DS U C D
với giả thiết
,u U d D
,
du
đầy
đủ giá trị, nếu tồn tại
uU
và
cC
sao cho
cu
thiếu giá trị thì DS được gọi là
bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ. Ta
biểu diễn bảng quyết định không đầy đủ là
,IDS U C D
với
,'*'
d
d D V
.
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 A d
. Với
BA
POS d U
.
Ví dụ 1.4. Xét bảng quyết định không đầy đủ
,IDS U A d
cho ở Bảng 1.3 được
xây dựng từ hệ thông tin không đầy đủ ở Ví dụ 1.3 bằng cách thêm vào thuộc tính
quyết định d (Gia tốc), với
1 2 3 4 5 6
{ , , , , , }U u u u u u u
,
1 2 3 4
{ , , , }A a a a a
.
Số hóa bởi Trung tâm Học liệu
18
Bảng 1.4. Bảng quyết định về các xe hơi
Ô tô
Đơn giá
Km đã đi
Kích thước
Tốc độ
Gia tốc
u
1
Cao
Cao
Đầy đủ
*
Đầy đủ
Cao
Tuyệt hảo
u
6
Thấp
Cao
Đầy đủ
*
Tốt
Ta có
1 2 3
/ { , , }U d X X X
với
1 1 2 4 6 2 3 3 5
{ , , , }, { }, { }X u u u u X u X u
.
Các tập xấp xỉ dưới đối với A là
1 1 2 2 3 3
, , ,AX u u AX u AX
.
Do đó,
1 2 3
( ) { , , }
A
POS d u u u
.
Hàm quyết định suy rộng của các đối tượng trên tập thuộc tính A là
Do đó, IDS là bảng quyết định không nhất quán.
1.2.2 Rút gọn thuộc tính trong mô hình tập thô dung sai
Rút gọn thuộc tính trong hệ thông tin đầy đủ theo tiếp cận mô hình tập thô truyền
thống của Pawlak [16] là chủ đề nghiên cứu sôi động trong nhiều năm qua [1]. Trong
các hệ thông tin không đầy đủ, kể từ khi Kryszkiewicz [10] xây dựng mô hình tập thô
dung sai dựa trên quan hệ dung sai, nhiều công trình đã công bố các phương pháp rút
gọn thuộc tính dựa trên các độ đo khác nhau [6, 7, 8, 11, 12, 13, 23]. Giống như trên
bảng quyết định đầy đủ, 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 đều thực hiện:
1) Đưa ra khái niệm tập rút gọn dựa trên độ đo mà phương pháp sử dụng.
Số hóa bởi Trung tâm Học liệu
19
2) Đưa ra khái niệm độ quan trọng của thuộc tính, đặc trưng cho khả năng đóng
góp của thuộc tính vào việc phân lớp tập đối tượng. Thuộc tính có độ quan trọng càng
lớn thì khả năng đóng góp vào việc phân lớp đối tượng càng nhiều và ngược lại.
3) Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu
chuẩn đánh giá là độ quan trọng của thuộc tính (chất lượng phân lớp của thuộc tính).
Thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối
với các bài toán có dữ liệu lớn. Các thuật toán heuristic này thường được xây dựng
theo hai hướng tiếp cận khác nhau: hướng tiếp cận từ dưới lên (bottom-up) và
hướng tiếp cận từ trên xuống (top-down). Dựa vào nhận xét tập lõi xuất hiện trong
mọi tập rút gọn nên các thuật toán xây dựng theo hướng tiếp cận bottom-up được
chia thành hai nhóm: các thuật toán tính toán lõi và các thuật toán không tính toán
lõi. Ý tưởng chung của các thuật toán tính toán lõi là xuất phát từ tập lõi, bổ sung dần
dần các thuộc tính có độ quan trọng lớn nhất vào tập lõi cho đến khi thu được tập rút
gọn. Các thuật toán không tính toán lõi xuất phát từ tập rỗng và bổ sung dần các
thuộc tính có độ quan trọng lớn nhất cho cho đến khi thu được tập rút gọn. Các
thuật toán được xây dựng theo hướng tiếp cận buttom-up xuất phát từ tập thuộc tính
Định nghĩa 2.1. [10] Cho bảng quyết định không đầy đủ
,IDS U A d
. Nếu
RA
thỏa mãn:
(1)
RA
uu
với mọi
uU
(2)
'
RR
, tồn tại
uU
sao cho
'
A
R
uu
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.
Zuqiang Meng và các cộng sự [24] đưa ra khái niệm về tập rút gọn dựa trên
miền dương.
Định nghĩa 2.2. [24] Cho bảng quyết định không đầy đủ
,IDS U A d
. Nếu
RA
thỏa mãn:
n
Bi
i
I B S u
U
và
12
, , ,
n
U u u u
.
Định nghĩa 2.3. [7] Cho bảng quyết định không đầy đủ
,IDS U A d
. Nếu
RA
thỏa mãn:
''
1;
2 , .
I R d I A d
R R I R d I A d
.
thì R được gọi là một tập rút gọn của IDS dựa trên lượng thông tin.
Trong [9], Huasheng ZOU và cộng sự đưa ra khái niệm tập rút gọn dựa trên
ma trận phân biệt. Ma trận phân biệt (discernibility matrix) của IDS là
ij
nn
Mm
,
(2) Với mọi
rR
,
Rr
không thỏa mãn (1)
thì R được gọi là một tập rút gọn của IDS dựa trên ma trận phân biệt.
Số hóa bởi Trung tâm Học liệu
22
Cũng theo hướng tiếp cận này, công trình [14] đưa ra khái niệm tập rút gọn
dựa trên ma trận dung sai. Ma trận dung sai (tolerance matrix) của IDS là
ij
nn
TM m
, các phần tử
ij
m
được xác định như sau:
, ( ) ( ) ( ) ( )
i j i j i j
ij
ij
a a A a u a u a u a u d u d u
m
d u d u
Định nghĩa 2.5. Cho bảng quyết định không đầy đủ
,IDS U A d
và ma trận
U u u
,
1
/ , ,
m
U d Y Y
. Với
i
uU
, đặt:
1
, ,
RR
R i i m i
u Y u Y u
với
j R i
R
ji
Ri
Y S u
Yu
Su
,
1, ,jm
.
:
R i j j R i
u Y Y S u
Số hóa bởi Trung tâm Học liệu
23
Trong mục này, tôi tổng kết các kết quả nghiên cứu mỗi liên hệ giữa các khái
niệm tập rút gọn của bảng quyết định không đầy đủ nhất quán và không nhất quán
trong công trình số [14]. Để mô tả một cách ngắn gọn, tôi ký hiệu các tập rút gọn ở
Bảng 2.1 như sau:
Bảng 2.1. Ký hiệu các tập rút gọn trong bảng quyết định không đầy đủ.
Ký hiệu tập rút gọn
Mô tả
P
R
Tập rút gọn dựa trên miền dương
R
Tập rút gọn dựa trên hàm quyết định suy rộng
R
Tập rút gọn ấn định
M
R
Tập rút gọn dựa trên ma trận phân biệt
I
R
Tập rút gọn dựa trên lượng thông tin
TM
tương đương với
R
.
- Các tác giả trong công trình [9] đã chứng minh
R
tương đương với
M
R
.
- Các tác giả trong công trình [14] đã chứng minh
I
R
tương đương với
TM
R
.
- Các tác giả trong công trình [14] đã chứng minh
P
R
là tập con của
R
,
nghĩa là: nếu
R
là một tập rút gọn dựa trên hàm quyết định suy rộng thì tồn tại
P
RR
với
P
R
R
là một tập rút
gọn dựa trên hàm quyết định suy rộng.
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 đủ không
nhất quán được biểu diễn bằng sơ đồ sau:
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 [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 1: Bao gồm tập rút gọn
P
R
.
Nhóm 2: Bao gồm các tập rút gọn
R
,
R
,
M
R
.
Nhóm 3: Bao gồm các tập rút gọn
R
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
2
R
thuộc nhóm 2 và một tập rút gọn
1
R
thuộc nhóm 1 sao cho
1 2 3
R R R
.
Nếu
4
R
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
2
R
thuộc nhóm 2 và một tập rút gọn
1
R
thuộc nhóm 1 sao cho
1 2 4
R R R
.
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 bốn nhóm tương ứng.
Nhóm phương pháp 1: Bao gồm phương pháp miền dương (tập rút gọn
P
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 độ đo mang tính định lượng để đánh giá chất
lượng phân lớp của tập rút gọn. Trong lý thuyết tập thô, các nhà nghiên cứu sử
Copyright: Tài liệu đại học ©