BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
VIỆN CÔNG NGHỆ THÔNG TIN
NGUYỄN LONG GIANG
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ
DỮ LIỆU THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ

Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH
VÀ HỆ THỐNG TÍNH TOÁN
Mã số: 62.46.35.01
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1.GS.TS Vũ Đức Thi
2. PGS.TS Nguyễn Thanh Tùng
HÀ NỘI - 2012
i
MỤC LỤC
MỤC LỤC ii
Danh mục các thuật ngữ v
Bảng các ký hiệu, từ viết tắt vi
Danh sách bảng viii
Danh sách hình vẽ ix
MỞ ĐẦU 1
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 8
1.1.Hệ thông tin đầy đủ và mô hình tập thô truyền thống 8
1.1.1.Hệ thông tin đầy đủ 8
1.1.2.Mô hình tập thô truyền thống 9
1.1.3.Bảng quyết định đầy đủ 11
1.1.4.Tập rút gọn và tập lõi 11
1.1.5.Ma trận phân biệt và hàm phân biệt 13
1.2.Hệ thông tin không đầy đủ và mô hình tập thô dung sai 14
1.2.1.Hệ thông tin không đầy đủ 14

3.2.2.Metric trên họ các tri thức 58
3.2.3.Một số tính chất của metric trên bảng quyết định 59
3.3.Rút gọn thuộc tính trong bảng quyết định sử dụng metric 62
3.3.1.Tập lõi và tập rút gọn của bảng quyết định dựa trên metric 62
3.3.2.Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric 62
3.3.3.Mối liên hệ giữa tập rút gọn dựa trên metric và tập rút gọn Entropy Shannon. .69
3.3.4.Thuật toán tìm tập rút gọn theo tham số độ chắc chắn của tập luật 70
3.4.Thực nghiệm các thuật toán tìm tập rút gọn 72
3.4.1.Thực nghiệm thuật toán tìm tập rút gọn tốt nhất sử dụng metric 72
3.4.2.Thực nghiệm thuật toán tìm tập rút gọn theo tham số độ chắc chắn 74
3.5.Thực nghiệm các phương pháp phân lớp dựa trên tập rút gọn 75
3.5.1.Thực nghiệm phương pháp phân lớp sử dụng tập thô 75
3.5.2.Thực nghiệm phương pháp phân lớp bằng cây quyết định 77
3.6.Kết luận chương 3 79
Chương 4. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
SỬ DỤNG METRIC 80
4.1.Mở đầu 80
4.2.Entropy Liang mở rộng trong hệ thông tin không đầy đủ và các tính chất 81
iii
4.2.1.Entropy Liang mở rộng của tập thuộc tính 81
4.2.2.Entropy Liang mở rộng có điều kiện 83
4.2.3.Một số tính chất của entropy Liang mở rộng 84
4.3.Metric trên họ các phủ và các tính chất 88
4.3.1.Metric trên họ các phủ 88
4.3.2.Một số tính chất của metric 91
4.4.Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric 94
4.4.1.Tập rút gọn của bảng quyết định không đầy đủ dựa trên metric 94
4.4.2.Thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ 94
4.4.3.Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn Kryszkiewicz 101
4.4.4.Mối liên hệ giữa tập rút gọn dựa trên metric với tập rút gọn dựa trên lượng thông

Quan hệ dung sai Tolerance Relation
Xấp xỉ dưới Lower Approximation
Xấp xỉ trên Upper Approximation
Rút gọn thuộc tính Attribute Reduction
Tập rút gọn Reduct
Tập lõi Core
Ma trận phân biệt Indiscernibility Matrix
Hàm phân biệt Indiscernibility Function
Luật quyết định Decision Rule
Quan hệ Relation
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 a Family of all minimal sets of attribute a
Hàm biểu diễn khoảng cách giữa hai
tập hợp trong [17]
Metric
v
Bảng các ký hiệu, từ viết tắt
Ký hiệu, từ viết tắt Diễn giải
( )
, , ,IS U A V f=
Hệ thông tin, hệ thông tin đầy đủ
( )
, , ,IIS U A V f=
Hệ thông tin không đầy đủ
( )
, , ,DS U C D V f= ∪
Bảng quyết định, bảng quyết định đầy đủ

IND B
( )
B
S u
Lớp dung sai của đối tượng
u
trên quan hệ
( )
SIM B
/U B
Phân hoạch của
U
sinh bởi tập thuộc tính
B
.
( )
/U SIM B
Phủ của U sinh bởi tập thuộc tính
B
.
( )
COVER U
Họ tất cả các phủ của U.
( )
B
u∂
Hàm quyết định suy rộng của đối tượng
u
đối với
B

SRED C
Họ tất cả các tập rút gọn dựa trên ma trận phân biệt
( )
ERED C
Họ tất cả các tập rút gọn Entropy Liang
( )
MRED C
Họ tất cả các tập rút gọn dựa trên metric
( )
KRED C
Họ tất cả các tập rút gọn dựa trên độ khác biệt của tri thức
( )
PCORE C
Tập lõi dựa trên miền dương
( )
HCORE C
Tập lõi dựa trên entropy Shannon có điều kiện
( )
SCORE C
Tập lõi dựa trên ma trận phân biệt
( )
ECORE C
Tập lõi dựa trên entropy Liang có điều kiện
( )
MCORE C
Tập lõi dựa trên metric
vi
( )
H P
Entropy Shannon của tập thuộc tính P

Khoảng cách giữa
( )
K P
và
( )
K Q
trong hệ thông tin đầy
đủ dựa trên khoảng cách Jaccard giữa hai tập hợp.
( ) ( )
( )
,
E
d K P K Q
Khoảng cách giữa
( )
K P
và
( )
K Q
trong hệ thông tin
không đầy đủ dựa trên entropy Liang mở rộng
( ) ( )
( )
,DQP K P K Q
Độ khác biệt giữa
( )
K P
và
( )
K Q

Bảng 5.2. Kết quả thử nghiệm Thuật toán 5.1 110
Bảng 5.3. Bảng quyết định ở Ví dụ 5.2 112
Bảng 5.4. Bảng quyết định được xây dựng từ Thuật toán 5.4 118
viii
Danh sách hình vẽ
Hình 3.1. Sự thay đổi tập rút gọn theo ngưỡng độ chắc chắn 75
Hình 3.2. Cây quyết định tương ứng với bảng quyết định ban đầu 77
Hình 3.3. Cây quyết định tương ứng với bảng quyết định rút gọn 78
ix
MỞ ĐẦU
Lý thuyết tập thô - do Zdzislaw Pawlak [42] đề 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 mơ hồ 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, trích lọc các tri
thức tiềm ẩn trong dữ liệu và đánh giá kết quả thu được.
Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thông tin
( )
,IS U A=
với U là tập các đối tượng và A là tập các thuộc tính. Phương pháp tiếp
cận chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt được để đưa ra
các tập xấp xỉ biểu diễn tập đối tượng cần quan sát. Khi đó, mọi tập đối tượng đều
được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao
gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối
tượng có khả năng thuộc về tập đó. Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập
đối tượng cần quan sát là tập rõ, ngược lại là tập thô. Các tập xấp xỉ là cơ sở để đưa
ra các kết luận từ dữ liệu. Bảng quyết định là một hệ thông tin IS với tập thuộc tính
A
được chia thành hai tập con khác rỗng rời nhau
C

đại số quan hệ [20, 61], phương pháp sử dụng ma trận phân biệt [11, 19, 65, 69],
phương pháp sử dụng entropy thông tin [39, 52, 55, 56, 57, 58, 59, 60, 63], phương
pháp sử dụng các độ đo trong tính toán hạt [12, 24, 26, 27, 28, 70, 71]. Tại Việt
Nam, luận án tiến sĩ của tác giả Hoàng Thị Lan Giao [1] đã đề xuất các thuật toán
heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán,
bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán sử
dụng ma trận phân biệt. Luận án tiến sĩ của tác giả Nguyễn Đức Thuần [2] đề xuất
thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào
phủ tập thô.
Với mục tiêu tìm kiếm một phương pháp phù hợp, hiệu quả rút gọn thuộc tính
trong bảng quyết định, vấn đề trước tiên là cần đưa ra tiêu chuẩn lựa chọn các
phương pháp phù hợp với lớp bài toán cần giải quyết và tiêu chuẩn so sánh, đánh
giá các phương pháp. Tiêu chuẩn lựa chọn các phương pháp phù hợp là tập rút gọn
của phương pháp phải bảo toàn độ chắc chắn của bảng quyết định. Việc lựa chọn
các phương pháp phù hợp được thực hiện bằng việc nghiên cứu sự thay đổi giá trị
các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn. Tiêu chuẩn so
sánh, đánh giá các phương pháp là số lượng thuộc tính tập rút gọn của phương
pháp và độ phức tạp của thuật toán tìm tập rút gọn. Việc so sánh số lượng thuộc
tính tập rút gọn của phương pháp được thực hiện bằng việc nghiên cứu mối liên hệ
2
giữa các tập rút gọn. Tập rút gọn của phương pháp càng ít thuộc tính thì độ hỗ trợ
của tập luật dựa trên tập rút gọn đó càng cao và phương pháp đó càng hiệu quả. Độ
phức tạp thuật toán tìm tập rút gọn của phương pháp càng nhỏ thì phương pháp đó
càng hiệu quả. Từ hai tiêu chuẩn này, ta có thể chứng minh được phương pháp cần
tìm kiếm là phù hợp và hiệu quả hơn các phương pháp đã có hay không. Trên thế
giới và tại Việt Nam, một số nhóm tác giả đã nghiên cứu mối liên hệ giữa các loại
tập rút gọn của một số phương pháp rút gọn thuộc tính và nghiên cứu một số độ đo
đánh giá hiệu năng tập luật quyết định [2, 6, 37, 48, 61, 64]. Tuy nhiên trên cả bảng
quyết định nhất quán và không nhất quán, các tác giả trên chưa nghiên cứu đầy đủ
mối liên hệ giữa các loại tập rút gọn và chưa nghiên cứu đầy đủ sự thay đổi giá trị

{ }
R C d⊆ ∪
được gọi là một tập tối thiểu của thuộc tính
{ }
d
nếu
R
là tập tối
thiểu thỏa mãn phụ thuộc hàm
{ }
R d→
. Do đó, khái niệm tập rút gọn của bảng
quyết định 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ệ, và 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
3
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
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 tìm họ tất cả các tập rút gọn, bài toán trích lọc các tri thức dưới dạng 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 từ tập phụ thuộc
hàm cho trước. Cho đến nay, hướng tiếp cận này chưa được nhiều tác giả quan tâm
nghiên cứu.
Từ các nội dung đã trình bày ở trên, luận án đặt ra các vấn đề nghiên cứu sau:
1) Trên bảng quyết định đầy đủ, vấn đề đầu tiên là nghiên cứu đầy đủ mối
liên hệ giữa các loại tập rút gọn của các phương pháp rút gọn thuộc tính và nghiên
cứu đầy đủ sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa
trên các loại tập rút gọn này. Mục đích nghiên cứu trước tiên là lựa chọn các
phương pháp phù hợp với lớp bài toán cần giải quyết, sau đó là so sánh, đánh giá
các phương pháp theo các tiêu chuẩn khác nhau. Dựa trên các kết quả này, vấn đề
nghiên cứu tiếp theo là tìm kiếm một phương pháp mới hiệu quả hơn các phương
pháp đã có theo các tiêu chuẩn đánh giá được chọn.

Bố cục của luận án gồm phần mở đầu và năm 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ề mô hình tập thô truyền thống, mô hình tập thô mở rộng dựa trên quan hệ dung sai
và cơ sở dữ liệu quan hệ. Chương 1 cũng trình bày 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 trên bảng quyết định
nhất quán trong chương 5.
Các đóng góp chính của luận án được trình bày trong chương 2, chương 3,
chương 4 và chương 5.
Chương 2 trình bày kết quả nghiên cứu về mối liên hệ giữa các loại tập rút gọn
của các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ và sự thay đổi
giá trị các độ đo đánh giá hiệu năng tập luật quyết định dựa trên các loại tập rút gọn
này. Trên cơ sở đó, chương 2 phân loại các phương pháp rút gọn thuộc tính trong
5
bảng quyết định không nhất quán thành 3 nhóm, lựa chọn nhóm phương pháp phù
hợp với lớp bài toán cần giải quyết và đánh giá các phương pháp trong 3 nhóm dựa
trên hai tiêu chuẩn: số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp
thuật toán tìm tập rút gọn
Chương 3 trình bày phương pháp xây dựng một metric trên họ các tri thức
trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn. Sử
dụng metric được xây dựng, chương 3 đề xuất một phương pháp mới rút gọn thuộc
tính trong bảng quyết định đầy đủ. Dựa trên lý thuyết, thực nghiệm và dựa trên kết
quả nghiên cứu của chương 2, chương 3 chứng minh phương pháp sử dụng metric
hiệu quả hơn các phương pháp khác trên cả hai tiêu chuẩn đánh giá: số lượng thuộc
tính tập rút gọn của phương pháp và độ phức tạp thuật toán tìm tập rút gọn.
Chương 4 trình bày phương pháp xây dựng một metric trên họ các phủ trong hệ
thông tin không đầy đủ dựa trên entropy Liang mở rộng. Sử dụng metric được xây dựng,
chương 4 đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy
đủ. Bằng lý thuyết và thực nghiệm, chương 4 chứng minh phương pháp sử dụng metric
hiệu quả hơn phương pháp sử dụng độ đo lượng thông tin và phương pháp sử dụng ma
trận dung sai theo tiêu chuẩn đánh giá độ phức tạp thuật toán tìm tập rút gọn.

∏
với
a
V
là tập giá trị của thuộc tính
a A∈
;
f
là hàm thông tin, với mọi
a A∈
và
u U∈
hàm f cho giá trị
( )
, ∈
a
f u a V
.
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
{ }
1 2
, , ,

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
8

là như nhau (viết
/ /U P U Q=
),
khi và chỉ khi
[ ] [ ]
,
P Q
u U u u∀ ∈ =
.
2) Phân hoạch
/U P
mịn hơn phân hoạch
/U Q
(viết
/ /U P U Qp
) khi và chỉ
khi
[ ] [ ]
,
P Q
u U u u
∀ ∈ ⊆
.
Tính chất 1.1 [43] Xét hệ thông tin
( )
, , ,IS U A V f=
và
,P Q A⊆
.
1) Nếu

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?
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à lượt là
BX
và
BX
, được xác định như sau:
[ ]
{ }
,
B
BX u U u X= ∈ ⊆
[ ]
{ }
.
B
BX u U u 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 vào tập

POS D BX
∈
=
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
v U∈
mà
( ) ( )
u B v B=
ta đều có
( ) ( )
u D v D=
. Nói cách khác,
[ ] [ ]
{ }
( )
B
D
B
POS D u U u u= ∈ ⊆
.
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.
Bảng 1.1. Bảng thông tin về bệnh cúm
U Đau đầu Thân nhiệt Cảm cúm
u
1

/U
{Thân nhiệt} =
{ } { } { }
{ }
1 4 2 5 7 3 6 8
, , , , , , ,u u u u u u u u

/U
{Cảm cúm} =
{ } { }
{ }
1 4 5 8 2 3 6 7
, , , , , , ,u u u u u u u u

/U
{Đau đầu, Cảm cúm} =
{ } { } { } { }
{ }
1 2 3 4 5 8 6 7
, , , , , , ,u u u u u u u u
Như vậy, các bệnh nhân
2 3
,u u
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à:
{ } { } { } { } { } { }
1 2 3 4 5 7 6 8
, , , , , , ,u u u u u u u u
.

,BX u u=
;
{ }
2 2 3
,BX u u=
,
( ) { }
1 2 3 4
/
( ) , , ,
B
X U D
POS D BX u u u u
∈
= =
U
.
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≠

( ) ( )
, ,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
( )
C
POS D U=
. Trong trường hợp bảng không nhất quán thì
( )
C
POS 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ữ
11
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ư

= ∪
và tập thuộc tính
R C⊆
. Nếu
1)
( ) ( )
R C
POS D POS D=
2)
{ }
, ( ) ( )
C
R r
r R POS D POS D
−
∀ ∈ ≠
thì R là một tập rút gọn của C dựa trên miền dương.
Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu
( )
PRED C
là họ tất cả các tập rút gọn Pawlak của C. Khi đó
( )
( )
R PRED C
PCORE C R
∈
=
I
.
Định nghĩa 1.5. Cho bảng quyết định

u
1
Có Có Có Bình thường Không
u
2
Có Có Có Cao Có
u
3
Có Có Có Rất cao Có
u
4
Có Không Có Bình thường Không
u
5
Có Khô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
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

=
, là một ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các
thuộc tính được xác định như sau
{ }
( ) ( ) ( ) ( ),
( ) ( ) .
i j i j
i j
i j
c C u c u c if u D u D
m
if u D u D

∈ ≠ ≠

=

∅ =


13
Định nghĩa 1.7. [11, 19] (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= ∪
,
( )
i j
n n
M m

×
=
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
{ }
( )
i j
C c m− ∩ ≠ ∅
với mọi
i j
m ≠ ∅
. Ngược lại, c được gọi là cần thiết. 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 ma trận phân biệt và
được ký hiệu là
( )
SCORE C
. Theo [19],
( )
( )
R SRED C
SCORE C R
∈
=
I
.
1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai
Trong phần này, chúng tôi trình bày các khái niệm cơ bản về mô hình tập thô mở
rộng trong hệ thông tin không đầy đủ dựa trên quan hệ dung sai do Marzena

( )
SIM P
không phải là quan hệ tương đương vì chúng có tính phản
xạ, đối xứng nhưng không có tính bắc cầu và được gọi là quan hệ dung sai (tolerance
relation), hay quan hệ tương tự (similarity relation) trên U. Theo [23],
( ) { }
( )
a P
SIM P SIM a
∈
= I
.
Gọi
( )
P
S u
là tập
( ) ( )
{ }
,v U u v SIM P∈ ∈
.
( )
P
S u
là tập lớn nhất các đối tượng
không có khả năng phân biệt được với u trên tập thuộc tính P, còn gọi là một lớp
dung sai 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 SIM P

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
( ) ( )
,
P Q
u U S u S u∀ ∈ =
.
2)
( )
/U SIM P
mịn hơn
( )
/U SIM P
(viết
( ) ( )
/ /U SIM P U SIM Qp
) khi
và chỉ khi


1) Nếu
P Q A⊆ ⊆
thì
( ) ( )
⊆
Q P
S u S u
với
∀ ∈
u U
.
15
2) Nếu
P Q A⊆ ⊆
thì
( ) ( )
/ /U SIM Q U SIM Pp
.
3) Nếu
,P Q A⊆
thì
( ) ( ) ( )
P Q P Q
S u S u S u
∪
= ∩
với
∀ ∈u U
.

với
1 2 3 4 5 6
{ , , , , , }U u u u u u u=
,
1 2 3 4
{ , , , }A a a a a=
với a
1
(Đơn giá), a
2
(Km đã đi), a
3
(Kích thước), a
4
(Tốc độ tối đa).
Bảng 1.3. Bảng thông tin về các xe hơi
Ô tô Đơn giá Km đã đi Kích thước 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

5 4 5 6
( ) { , , }
A
S u u u u=
,
6 2 5 6
( ) { , , }
A
S u u u u=
.
Với
{ }
3 4
,P a a=
ta có
1 2 3 4 5 6
/ ( ) { ( ), ( ), ( ), ( ), ( ), ( )}
P P P P P P
U SIM P S u S u S u S u S u S u=
, với
1 2 1 2 6 3 3 4 5 4 5 6
( ) ( ) { , , }, ( ) { }, ( ) ( ) { , , }
P P P P P
S u S u u u u S u u S u S u u u u
= = = = =
,
6 1 2 4 5 6
( ) { , , , , }
P
S u u u u u u