LỜI CAM ĐOAN
Nghiên cứu sinh
i
Tôi xin cam đoan luận án này là công trình
nghiên cứu của riêng tôi. Các kết quả được viết chung
với các tác giả khác đều được sự đồng ý của các đồng
tác giả trước khi đưa vào luận án. Các kết quả được
trình bày trong luận án là mới, các số liệu là trung thực
và chưa từng được ai công bố trong các công trình nào
khác./.
LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình của PGS.TS
Nguyễn Bá Tường, người mà từ đó tác giả đã học được nhiều điều quí giá. Tác giả
cũng đã nhận được sự hướng dẫn và sự quan tâm giúp đỡ về nhiều mặt, cùng với
những đòi hỏi nghiêm khắc của PGS.TS Hà Quang Thụy. Tác giả xin bày tỏ lòng
biết ơn sâu sắc và chân thành tới những người Thầy đã giúp tác giả hoàn thành
những mục tiêu đặt ra của luận án.
Tác giả xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học
thuộc: Học viện Kỹ thuật Quân sự, Trường Đại học Công nghệ (đặc biệt là Phòng
Thí nghiệm Công nghệ Tri thức - KTLab) - Đại học Quốc gia Hà Nội, Trường Đại
học Kinh tế Kỹ thuật Công nghiệp đã giúp đỡ về chuyên môn và tạo điều kiện thuận
lợi cho tác giả trong suốt thời gian học tập và nghiên cứu.
Tác giả cũng xin bày tỏ lòng biết ơn đến các bạn đồng nghiệp đã giúp đỡ và có
những trao đổi, chia sẻ những kinh nghiệm về chuyên môn, có nhiều ý kiến đóng
góp quý báu cho tác giả trong quá trình nghiên cứu.
Tác giả mãi biết ơn những người thân, đặc biệt là chồng và các con, đã luôn
chia sẻ mọi khó khăn và là chỗ dựa vững chắc về tinh thần và tạo mọi điều kiện cho
tác giả trong suốt thời gian hoàn thành luận án.
ii
MỤC LỤC
LỜI CẢM ƠN ii

2.3.1. Tập rút gọn trong hệ thông tin (bảng quyết định) giá trị tập 36
2.3.2. Ma trận phân biệt 36
2.3.3. Rút gọn thuộc tính sử dụng đối tượng đại diện 38
2.4. Kết luận 40
Chương 3. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP SỬ DỤNG
HÀM PHÂN BIỆT THEO BẢNG PHÂN BIỆT NGẪU NHIÊN 42
3.1. Cơ sở lý thuyết 42
3.1.1. Hàm phân biệt mở rộng 42
3.1.2. Bảng phân biệt ngẫu nhiên 44
3.1.3. Bảng ngẫu nhiên dung sai 49
3.1.4. Dàn giá trị thuộc tính 54
3.2. Thuật toán tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập 57
3.2.1. Thuật toán 3.1. tìm tập rút gọn thuộc tính GMDSDT 57
3.2.2. Độ phức tạp thuật toán GMDSDT 58
Chứng minh tính đúng của thuật toán GMDSDT 58
3.2.3. Ví dụ minh họa 59
3.3. Thực nghiệm thuật toán GMDSDT 62
3.3.1. Cài đặt thuật toán 62
3.3.2. Chuẩn bị số liệu thực nghiệm 62
3.3.3. Thi hành thực nghiệm thuật toán 62
3.4. Thuật toán tìm tập xấp xỉ trong hệ thông tin giá trị tập 65
3.4.1. Đặt vấn đề 65
3.4.2. Thuật toán tìm tập xấp xỉ dưới và xấp xỉ trên VASDT 66
3.4.3. Độ phức tạp của thuật toán VASDT 67
3.4.4. Ví dụ minh họa thuật toán tìm tập xấp xỉ 67
3.5. Kết luận 69
iv
Chương 4. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP SỬ DỤNG
HÀM PHÂN BIỆT THEO MA TRẬN PHÂN BIỆT MỞ RỘNG 70
4.1. Chọn mẫu đại diện cho bài toán tìm tập rút gọn 70

TÀI LIỆU THAM KHẢO 106
vi
DANH MỤC CÁC THUẬT NGỮ
Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh
Bảng ngẫu nhiên dựa trên quan hệ dung sai Tolerance Based Contingency Table
Bảng phân biệt Contingency Table
Bảng quyết định Decision Table
Bảng quyết định giá trị tập Set valued Decision Information System
Hàm phân biệt Discernibility Function
Hệ thông tin Information System
Hệ thông tin đầy đủ Complete Information System
Hệ thông tin giá trị tập Set valued Information System
Hệ thông tin không nhất quán Inconsistent Information System
Ma trận không phân biệt được Indiscernibility Matrix
Quan hệ dung sai Tolerance Relation
Quan hệ không phân biệt được Indiscernibility Relation
Rút gọn thuộc tính Attribute Reduction
Tập lõi Core
Tập rút gọn Reduct
Tập thô Rough Set
Xấp xỉ dưới Lower Approximation
Xấp xỉ trên Upper Approximation
vii
BẢNG KÝ HIỆU, TỪ VIẾT TẮT
Ký hiệu, từ viết tắt Diễn giải
( )
, , ,S U A V f
=
Hệ thông tin
( )

IND B
/U B
Phân hoạch của
U
sinh bởi tập thuộc tính
B
( )
COVER U
Tập 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
BX
B −
xấp xỉ dưới của
X
trong hệ thông tin
BX
B
−
xấp xỉ trên của
X
trong hệ thông tin
( )
B

Miền biên của X trong hệ thông tin giá trị tập
( )
B
T
NEG X
Miền ngoài của X trong hệ thông tin giá trị tập
( )
B
T
POS X
Miền dương của X trong hệ thông tin giá trị tập
B
CT
Bảng ngẫu nhiên của tập thuộc tính B
B
TCT
Bảng ngẫu nhiên dựa trên quan hệ dung sai
của tập thuộc tính B
DT
M
Ma trận phân biệt
( )discern A
Hàm phân biệt
viii
P
IS
Hệ thông tin giá trị tập đại diện
P
DS
Bảng quyết định giá trị tập đại diện

Bảng 3.5. Tập rút gọn của Thuật toán GMDSDT 65
Bảng 3.6. Bảng quyết định giá trị tập gồm 4 cột thuộc tính điều kiện và cột 67
Bảng 4.1. Bảng quyết định giá trị tập 74
Bảng 4.2. Hệ thông tin giá trị tập đại diện từ Bảng 4.1 75
Bảng 4.3. Bảng quyết định giá trị tập đại diện từ Bảng 4.1 80
Bảng 4.4. Bảng quyết định giá trị tập khi bổ sung 90
x
DANH MỤC HÌNH VẼ
Hình 3.1. Cấu trúc dàn của bảng quyết định giá trị tập 56
Hình 3.2. Minh họa các thuật toán tìm tập rút gọn 63
64
Hình 3.3. Minh họa thuật toán sử dụng hàm phân biệt 64
Bảng 4.5. Kết quả thực hiện Thuật toán RGDSDT và Thuật toán GMDSDT 101
xi
MỞ ĐẦU
Tính cấp thiết của đề tài
Lý thuyết tập thô được Zdzislaw Pawlak đề xuất vào năm 1982 [36, 38] mở ra
một tiếp cận mới về tính không chắc chắn (uncertainty). Xuất phát điểm của lý
thuyết tập thô là khái niệm hệ thông tin (information system) được sử dụng để biểu
diễn dữ liệu có được về miền ứng dụng. Một hệ thông tin [35] là một bộ bốn
( )
, , ,S U A V f
=
bao gồm một tập (vũ trụ) gồm hữu hạn các đối tượng
U
( )U ≠ ∅
,
một tập hữu hạn các thuộc tính
A
của các đối tượng (

mẫu (pattern recognition), lý thuyết bộ phận-toàn bộ (mereology), phát hiện tri thức
(knowledge discovery), phân tích quyết định (decision analysis), và các hệ chuyên
gia (expert systems) [7, 38, 40, 42, 55, 56, 58]. Trong thời đại kinh tế tri thức hiện
nay, tầm quan trọng của các lĩnh vực nghiên cứu trên đây ngày càng được nâng cao,
tương ứng, lý thuyết tập thô ngày càng thu hút sự quan tâm của cộng đồng hàn lâm
- công nghiệp. Hiệp hội tập thô thế giới (The International Rough Set Society -
IRSS
1
) đã được thành lập từ năm 2005. IRSS bao gồm một số hiệp hội thành viên
2
,
trong đó Hiệp hội Tập thô và Tính toán mềm Trung Quốc (Rough Set and Soft
Computing Society, Chinese Association for AI
3
) là một hiệp hội thành viên điển
hình nhất. Trong lời tựa Kỷ yếu Hội nghị khoa học thế giới về Tập thô và Các mô
hình hệ thống thông minh mới nổi năm 2007 (The International Conference on
Rough Sets and Emerging Intelligent Systems Paradigms: RSEISP 2007) tưởng nhớ
GS. Zdzislaw Pawlak, Marzena Kryszkiewicz, và các cộng sự cho biết có hơn 4000
ấn phẩm khoa học về tập thô đã được công bố tới thời điểm đó. Lý thuyết tập thô và
lý thuyết tập mờ (Fuzzy Set Theory) do Zadeh L.A. đề xuất năm 1965 [72] là hai lý
thuyết điển hình nhất về các mô hình biểu diễn tính không chắc chắn [22, 37].
Việc mở rộng lý thuyết tập thô nhằm làm cho các khái niệm và mô hình biểu
diễn tri thức dựa trên lý thuyết tập thô ngày càng phù hợp với miền ứng dụng cũng
ngày càng được mở rộng [24, 37, 42, 43, 54]. Theo Andrzej Skowron và cộng sự,
2013 [54], cộng đồng nghiên cứu quan tâm đặc biệt tới các tiếp cận mở rộng lý
thuyết tập thô dựa trên tính tương tự (hay dung sai; similarity/tolerance based rough
sets), tập thô dựa trên quan hệ nhị phân (binary relation based rough sets), tập thô
lân cận và phủ (neighborhood and covering rough sets), tập thô trội (dominance
based rough sets), kết hợp tập thô và tập mờ (hybridization of rough sets and fuzzy

tiềm ẩn trong dữ liệu; (ii) xác định tập dữ liệu tối ưu (rút gọn dữ liệu: data
reduction hay ngắn gọn là reduction) và ước lượng tính quan trọng dữ liệu; (iii) sinh
các tập luật quyết định từ dữ liệu; (iv) hình thức hóa tính dễ hiểu; (v) giải thích đơn
giản hóa các kết quả thu được; và (vi) làm phù hợp nhiều thuật toán của nó để xử lý
song song. Rút gọn thuộc tính (attribute reduction), một thành phần chủ chốt của
rút gọn dữ liệu, là một trong những bài toán ứng dụng quan trọng nhất của lý thuyết
tập thô.
Mục tiêu của rút gọn thuộc tính trong hệ thông tin là tìm ra tập nhỏ nhất các
thuộc tính để phân tích dữ liệu mà vẫn giữ được hiệu năng (hoặc hầu hết hiệu năng)
như tập toàn bộ các thuộc tính [70]. Rút gọn thuộc tính vừa làm giảm khối lượng xử
3
lý dữ liệu do chỉ phải thao tác trên một khối lượng dữ liệu nhỏ hơn, vừa làm cho kết
quả thu được trở nên cô đọng và dễ hiểu hơn.
Theo Yiyu Yao và Yan Zhao [70], hai mô hình rút gọn thuộc tính trong lý
thuyết tập thô là mô hình Pawlak và mô hình xác suất. Tồn tại các phương pháp rút
gọn thuộc tính điển hình theo hai mô hình này là các phương pháp dựa trên miền
dương [13, 31, 46, 57], các phương pháp sử dụng ma trận phân biệt [12, 47, 50, 68,
71], các phương pháp sử dụng các phép toán đại số quan hệ [21], các phương pháp
sử dụng entropy thông tin [29, 59, 60, 61, 63, 67, 68], các phương pháp sử dụng các
độ đo, điển hình là độ đo trong tính toán hạt (granular computing) [6, 14, 15, 28,
53, 75], các phương pháp tích hợp lý thuyết tập thô với lý thuyết tập mờ [22, 24].
Trong hệ thông tin giá trị tập, các phương pháp tìm tập rút gọn thuộc tính
được hình thành dựa trên quan hệ dung sai [15, 51]. Theo hướng tiếp cận mô hình
quan hệ dung sai, một số kết quả nghiên cứu đáng chú ý về rút gọn thuộc tính trên
bảng quyết định giá trị tập được công bố trong [8, 27, 44, 45, 64, 65, 66].
Trên thế giới, một số luận án tiến sỹ về rút gọn thuộc tính theo lý thuyết tập
thô đã được công bố. Dale E. Nelson, 2001 [32] trình bày nghiên cứu rút gọn thuộc
tính dựa trên khái niệm tập rút gọn và tập nhân để lựa chọn thuộc tính phân lớp mục
tiêu rada, bao gồm việc đề xuất một phương pháp và một thuật toán độ phức tạp đa
thức lựa chọn tập con thuộc tính thích hợp. Richard Jensen, 2005 [22] phát triển các

nghiên cứu chính sau đây:
 Một nghiên cứu khái quát về lý thuyết tập thô, tập trung vào lý thuyết hệ
thông tin giá trị tập.
 Một nghiên cứu khái quát các tiếp cận điển hình rút gọn thuộc tính trong hệ
thông tin và hệ thông tin giá trị tập.
 Nghiên cứu một số mô hình, kỹ thuật rút gọn thuộc tính trong hệ thông tin
giá trị tập, trên cơ sở đó đề xuất một số thuật toán rút gọn thuộc tính trong hệ thông
tin giá trị tập.
5
Đối sánh các nội dung nghiên cứu được trình bày trên đây với nội dung
nghiên cứu của các luận án tiến sỹ trong và ngoài nước đã được giới thiệu, luận án
này có những điểm khác biệt.
Mục tiêu nghiên cứu của luận án là hoàn thành các nội dung nghiên cứu
chính nêu trên để giải đáp các câu hỏi nghiên cứu. Luận án tập trung nghiên cứu bài
toán rút gọn thuộc tính trong các phiên bản hệ thống thông tin được quan tâm và đề
xuất được các thuật toán rút gọn thuộc tính mới. Mục tiêu cơ bản trên đây được cụ
thể hóa bằng các mục tiêu cụ thể sau đâu. Thứ nhất, cung cấp được một khái quát
song đủ toàn diện về lý thuyết tập thô trong phạm vi xem xét bài toán rút gọn thuộc
tính. Thứ hai, cung cấp được một khảo sát các phương pháp điển hình giải quyết bài
toán rút gọn thuộc tính trong lý thuyết tập thô và lý thuyết tập thô giá trị tập. Thứ
ba, đề xuất được các thuật toán tìm tập rút gọn thuộc tính dựa trên khái niệm bảng
quyết định giá trị tập.
Đối tượng nghiên cứu của luận án là bài toán rút gọn thuộc tính trong bảng
quyết định giá trị tập như đã trình bày theo các vấn đề nghiên cứu của luận án.
Phạm vi nghiên cứu của luận án được giới hạn ở bài toán rút gọn thuộc tính
trong bước tiền xử lý số liệu.
Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và có sử dụng
phương pháp nghiên cứu thực nghiệm.
Luận án có các đóng góp chính sau đây:
1. Cung cấp một kết quả nghiên cứu khái quát về lý thuyết tập thô, lý thuyết

khai phá dữ liệu. Các kết quả nghiên cứu này được công bố trong công trình số 2.
5. Trong lý thuyết tập thông truyền thống, Skowron và Rauszer [52] đã đưa ra
khái niệm ma trận phân biệt và hàm phân biệt để tìm tập rút gọn. Dựa trên cách tiếp
cận này, luận án đề xuất hai cấu trúc dữ liệu mới là hàm phân biệt mở rộng và ma
trận phân biệt mở rộng trong bảng quyết định giá trị tập. Hai cấu trúc dữ liệu mới
này là công cụ để xây dựng thuật toán tìm tập rút gọn trên bảng quyết định giá trị
tập. Theo đó, Chương 4 đưa ra phương pháp thứ hai tìm tập rút gọn thuộc tính, cụ
thể luận án đề xuất ba thuật toán mới tìm tập rút gọn thuộc tính (RGDSDT:
heuristic algorithm to find a Reduct based on Generalized Discernibility function in
Set-valued Decision Table, RSDTAAS: extended algorithm to find a Reduct in Set-
valued Decision Table when Adding an Attribute Set, RSDTDAS: extended
algorithm to find a Reduct in Set-valued Decision Table when Deleting an Attribute
7
Set) khi bổ sung và loại bỏ tập thuộc tính trong bảng quyết định giá trị tập, đánh giá
độ phức tạp của từng thuật toán. Các kết quả nghiên cứu này được công bố trong
công trình số 3.
Bố cục của luận án gồm phần mở đầu và bốn chương nội dung (như trình bày
ở trên), phần kết luận và danh mục các tài liệu tham khảo.
8
Chương 1. LÝ THUYẾT TẬP THÔ VÀ CÁC MỞ RỘNG
Chương này được bắt đầu bằng việc giới thiệu các khái niệm cơ bản về hệ
thông tin, tập thô, bảng quyết định được Zdzislaw Pawlak đề xuất vào năm 1982
[36, 38, 54], các tính chất cơ bản của chúng, cùng một số khái niệm liên quan. Tiếp
theo, một mở rộng của hệ thông tin là hệ thông tin giá trị tập (Set-valued
Information System, còn được gọi là "hệ thông tin đa trị": Multi-valued Information
System) [15] cùng các khái niệm liên quan được trình bày. Đây là những kiến thức
nền tảng liên quan tới bài toán rút gọn thuộc tính trong hệ thông tin giá trị tập được
trình bày trong các chương tiếp theo.
1.1. Hệ thông tin và tập thô
1.1.1. Hệ thông tin

.
Với mỗi
,u U a A
∈ ∈
, dùng ký hiệu
( )
u a
thay cho
( )
,f u a
để biểu thị giá trị
của đối tượng u tại thuộc tính a; rõ ràng là
( )
a
u a V∈
với mọi
.Uu
∈
Với một tập con
các thuộc tính
{ }
1 2
, , ,
k
B b b b A= ⊆
, ký hiệu bộ các giá trị {
( )
i
u b
|b

{u , , u }U
=
.
Tập các thuộc tính
A
=
{Độ tuổi, Số buổi, Thi đậu}.
Tập giá trị của thuộc tính độ tuổi, số buổi và thi đậu là:
V
Độ tuổi
={16-30, 31-45, 46-60}
V
Số buổi
={0, 1-25, 26-49, 50}
V
Thi đậu
={Không, Có}.
Hàm
f
được biểu thị bằng giá trị tương ứng tại điểm giao của mỗi hàng-đối
tượng với mỗi cột-thuộc tính, ví dụ,
1
( ,f u
độ tuổi) = (16 - 30),
2
( ,f u
số buổi) = 0.
Bảng 1.1. Một ví dụ về hệ thông tin
U Độ tuổi Số buổi Thi đậu
u

{ }
( ) ( , ) | ( ) ( ), .IND B u v U U u a v a a B= ∈ × = ∀ ∈
IND(B) được gọi là quan hệ không phân biệt được (Indiscernibility Relation).
Rõ ràng, IND(B) 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 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
10
U, ký hiệu là U/IND(B) hay U/B. Ký hiệu lớp tương đương trong phân hoạch U/B
chứa đối tượng u là [u]
B
, khi đó [u]
B
={v
∈
U|(u,v)∈ IND(B)}.
Nguyen Sinh Hoa và Nguyen Hung Son [19] trình bày một thuật toán xác
định các lớp tương đương theo quan hệ IND(B) theo thứ tự "từ điển" <
B
trên các
vector tập giá trị thuộc tính trong B và sắp xếp tập đối tượng U theo thứ tự từ điển
<
B
. Thứ tự từ điển <
B

được xác định nhờ các quan hệ thứ tự trên V
a
,

1
}}
/U
{Thi đậu} = {{u
2
, u
3
, u
5
, u
7
}, {u
1
, u
4
, u
6
}}.
Với B = {Độ tuổi, Số buổi, Thi đậu}, phân hoạch U sinh bởi B là
{ } { } { } { } { }
{ }
1 2 3 4 5 7 6
/ , , },{ , , , }U B u u u u u u u=
. Lưu ý rằng, thứ tự các lớp tương đương
thuộc
/U B
tìm được theo thuật toán 1.1 là {{u
2
}, {u
6

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
( )
, , ,S U A V f
=
và
,P Q A

U [36, 38]. Trong [35], Zdzislaw Pawlak đề xuất một ngôn ngữ hỏi (Query Language)
trong hệ thông tin và ngữ nghĩa của một biểu thức (term) trong ngôn ngữ hỏi nói trên. Tác
giả đưa ra khái niệm "tập mô tả được" (Describable Set) theo S là một tập con đối tượng
là ngữ nghĩa của một biểu thức trong ngôn ngữ hỏi nói trên. Với một tập mô tả được X,
biểu thức t tương ứng (trong ngôn ngữ hỏi) được sử dụng để "mô tả" nó. Tác giả chỉ ra
rằng một tập mô tả được hoặc là tập rỗng hoặc là tổng của một số nào đó các tập sơ cấp
(Elementary Set), trong đó tập sơ cấp chính là lớp tương đương theo quan hệ IND(A).
Điều đó có nghĩa là các lớp tương đương theo quan hệ IND(A) (các tập sơ cấp) là điểm
xuất phát trong cách thức mô tả các tập con
X U⊆
. Nếu mọi lớp tương đương theo quan
hệ IND(A) có duy nhất một đối tượng thì mọi tập con
X U⊆
đều là tập mô tả được. Tuy
nhiên, trong trường hợp tổng quát, một tập
X U⊆
có thể mô tả được hoặc không. Trong
trường hợp X không là tập mô tả được thì cần chỉ ra cách thức mô tả "xấp xỉ" nó. Trong
[36], Zdzislaw Pawlak dùng cặp hai tập mô tả được là tập xấp xỉ dưới của X (
)X(Apr
A
hay
)X(Apr
) và tập xấp xỉ trên của X (
)X(Apr
A
hay
)X(Apr
) để biểu diễn tập X. Tập xấp xỉ
dưới của X là hợp của tất cả các tập sơ cấp được chứa trong X, tập xấp xỉ trên là là hợp của

= ∈ ⊆
[ ]
{ }
.
B
BX u U u X
= ∈ ∩ ≠ ∅
Tập xấp xỉ dưới
BX
bao gồm tất cả các đối tượng thuộc U chắc chắn thuộc
vào X, còn tập xấp xỉ trên
BX
bao gồm các đối tượng thuộc U có khả năng thuộc
vào X dựa vào tập thuộc tính B. Thêm nữa, B-miền biên của X là tập
( )
B
BN X BX BX= −
và B-miền ngoài của X là tập
.U BX
−
Rõ ràng là B-miền biên của X là tập chứa các đối tượng không chắc chắn
thuộc X và cũng không chắc chắn 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 tương đương theo phân
hoạch U/B, các xấp xỉ trên và xấp xỉ dưới của X có thể viết lại như sau:
{ }
/BX Y U B Y X= ∪ ∈ ⊆
,
{ }
/ .BX Y U B Y X= ∪ ∈ ∩ ≠ ∅
Tương tự như trường hợp tập A gồm toàn bộ các thuộc tính [36], khi

∈
=
U
.
13
Rõ ràng là POS
B
(D)={u| ∀v
∈
U: u(B)= v(B) ⇒ u(D)= v(D)}
hay cũng vậy,
[ ] [ ]
{ }
( )
B
D
B
POS D u U u u
= ∈ ⊆
.
Trên cơ sở đó chúng ta 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.2. Xác định xấp xỉ dưới, xấp xỉ trên [19]
Đầu vào: Hệ thông tin
( )
, , ,S U A V f
=
, tập thuộc tính

:
B
j
BX BX X= ∪
Nếu
B
j
X X∩ ≠ ∅
thì
:
B
j
BX BX X= ∪
end.
Thuật toán 1.2 có độ phức tạp là
O(k | U | log | U |)
, trong đó |B| ≤|A|=k [19].
Ví dụ 1.3. Xét hệ thông tin cho ở Bảng 1.1.
Giả sử, chọn B = {Độ tuổi, số buổi} ;
{ }
3 4 5
, , .X u u u
=
Ta có
1 2 3 4 5
/ { , , , , }
P P P P P
U P X X X X X
=


Khi đó:
{ }
3 1 6
{X }= ,
P
BX u u
=
và
{ }
3 4 3 4 5 6
{X , X }= , , , .
P P
BX u u u u=

Vì
BX BX
≠
nên ta có X là tập thô.
Ví dụ 1.4. Xét hệ thông tin cho ở Bảng 1.1.
Các lớp không phân biệt được bởi B = {Độ tuổi, số buổi} là:
14