Nghiên cứu cải tiến một số độ đo trong lý thuyết tập thô cho bảng quyết định không đầy đủ

 ISSN: 1859-2171 
e-ISSN: 2615-9562 
TNU Journal of Science and Technology 225(06): 200 - 204 
200  Email: jst@tnu.edu.vn 
NGHIÊN CỨU CẢI TIẾN MỘT SỐ ĐỘ ĐO TRONG LÝ THUYẾT TẬP THÔ 
CHO BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ 
Nguyễn Anh Tuấn 
Trường Cao đẳng Vĩnh Phúc 
TÓM TẮT 
Các phương pháp giảm bớt thuộc tính đều sử dụng các độ đo qua các lớp dung sai, như phương 
pháp sử dụng độ đo lượng thông tin (information quantity). Để giải quyết bài toán giảm bớt thuộc 
tính trực tiếp trên các bảng quyết định không đầy đủ và đánh giá sự thay đổi giá trị độ chắc chắn, 
độ nhất quán, độ hỗ trợ. Các độ đo này gặp khó khăn trong việc đánh giá tính hiệu quả (về khả 
năng phân lớp hay độ hỗ trợ của tập luật)... Trong bài báo này, tác giả cải tiến một số độ đo nhằm 
nâng cao hiệu năng trong lý thuyết tập thô cho bảng quyết định không đầy đủ và chứng minh tính 
đúng đắn của các độ đo đề xuất. 
Từ khóa: Lý thuyết tập thô, Độ đo, bảng quyết định không đầy đủ, nâng cao hiệu năng, Giảm bớt 
thuộc tính. 
Ngày nhận bài: 23/12/2019; Ngày hoàn thiện: 13/5/2020; Ngày đăng: 20/5/2020 
RESEARCH ON IMPROVING SOME MEASUREMENTS IN CRUDE 
THEORETICAL OF INCOMPLETE DECISION TABLES 
Nguyen Anh Tuan 
 Vinh Phuc College 
ABSTRACT 
Attribute reduction methods uses measurements by tolerance layers, such as the measurement of 
information quantity. To solve the problem of reducing attributes directly on the incomplete 
decision tables and assessing changes in the value of certainty, consistency, support. These 
measures have difficulty in assessing the effectiveness (in terms of the ability to classify or support 
the law set) ...In this paper, the author improved some measurements to improve performance in 
the crude theoretical for incomplete decision tables and proved the validity of the proposed 
measurements. 
Keywords: Tolerance Rough Set, measurements, incomplete decision tables, improve 
performance, attribute reduction. 
Received: 23/12/2019; Revised: 13/5/2020; Published: 20/5/2020 
Email: tuanna573@gmail.com 
Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 
 Email: jst@tnu.edu.vn 201 
1. Giới thiệu 
Trong lý thuyết tập thô, lựa chọn một số tính 
năng quan trọng để quyết định có giảm bớt 
hay không là hết sức cần thiết. Giảm bớt các 
đối tượng là một quá trình để tìm tập hợp con 
tối ưu của các thuộc tính, giữ lại những thuộc 
tính quan trọng để đưa ra những quyết định 
chính xác nhất. Hầu hết các thuật toán giảm 
bớt các đối tượng đều dựa vào thông tin được 
thu thập từ miền dương [1]. Các phương pháp 
giảm bớt thuộc tính đều sử dụng các độ đo 
qua các lớp dung sai, như phương pháp sử 
dụng độ đo lượng thông tin [2]. Giảm bớt các 
thuộc tính dựa trên lý thuyết tập thô có chứa 
dữ liệu về các đối tượng đặc trưng bởi tập hợp 
các thuộc tính hữu hạn. Đối với một hệ thống 
thông tin, nếu các thuộc tính điều kiện và 
thuộc tính quyết định là khác nhau, thì nó 
được gọi là một hệ thống quyết định. 
Mục đích của việc giảm bớt các thuộc tính là 
loại bỏ các thuộc tính dư thừa nhằm nâng cao 
tính hiệu quả của các thuật toán. J. Dai và các 
cộng sự [3] xây dựng độ đo lượng thông tin 
tăng thêm mờ (fuzzy gain ratio) dựa trên 
entropy mờ và xây dựng thuật toán 
GAIN_RATION_AS_FRS tìm tập giảm bớt 
sử dụng lượng thông tin tăng thêm mờ. Thực 
nghiệm trên một số bộ dữ liệu mẫu cho thấy, 
độ chính xác phân lớp của các thuật toán 
FSCE, GAIN_RATION_AS_FRS cao hơn độ 
chính xác của các thuật toán sử dụng Entropy, 
lượng thông tin tăng thêm (gain ratio) theo 
tiếp cận thô truyền thống. 
Trong thực tế, có nhiều cách giảm bớt cho 
một bảng quyết định, tuy nhiên mức giảm tối 
thiểu là NP-hard [4]. Do đó, có nhiều tác giả 
đề xuất những phương pháp khác nhau để làm 
giảm thuộc tính trong lý thuyết tập thô như: 
dựa trên miền dương, dựa trên ma trận, dựa 
trên độ đo entropy, tính toán hạt, dựa trên độ 
đo khoảng cách... 
Trong bài báo này, tác giả nghiên cứu cải tiến 
cải tiến một số độ đo trong lý thuyết tập thô 
cho bảng quyết định không đầy đủ, nhằm 
đánh giá các phương pháp theo tiêu chuẩn 
khả năng phân lớp của tập rút gọn. 
Cấu trúc bài báo như sau: Phần I Giới thiệu; 
Phần II: Cơ sở toán học; Phần III: Cải tiến độ 
đo để nâng cao hiệu năng trong bảng quyết 
định không đầy đủ. Phần IV: Kết luận và tài 
liệu tham khảo. 
2. Cơ sở toán học 
2.1.Định nghĩa hệ thông tin[5] 
Hệ thông tin là 𝐼𝑆 = (𝑈, 𝐴) trong đó 𝑈 là tập 
hữu hạn, khác rỗng các đối tượng; 𝐴 là tập 
hữu hạn, khác rỗng các thuộc tính. Với mọi 
𝑢 𝑈 , 𝑎 𝐴 ký hiệu giá trị thuộc tính 𝑎 tại 
đối tượng 𝑢 là 𝑎 (𝑢) thay vì (𝑢, 𝑎). 
Nếu 𝐵 = {𝑏1, 𝑏2,  , 𝑏𝑛}  A là một tập con 
các thuộc tính thì ký hiệu bộ các giá trị 𝑏𝑖(𝑢) 
bởi 𝐵(𝑢). 
Như vậy, nếu 𝑢 và 𝑣 là hai đối tượng, thì 
𝐵 (𝑢) = 𝐵 (𝑣) nếu 𝑏𝑖(𝑢) = 𝑏𝑖(𝑣) với mọi 
 =1, . . ., 𝑛. 
Xét hệ thông tin 𝐼𝑆 = (𝑈, 𝐴). Mỗi tập con các 
thuộc tính 𝑃  𝐴 xác định một quan hệ hai 
ngôi trên 𝑈, ký hiệu là 𝐼𝑁𝐷 (𝑃) , xác định 
bởi: 
𝐼𝑁𝐷 (𝑃) = (𝑢 𝑣) 𝑈 𝑈|𝑎 𝑃 , 𝑎 (𝑢) =
 𝑎 (𝑣). 
𝐼𝑁𝐷 (𝑃) là quan hệ P- không phân biệt được. 
Thấy rằng 𝐼𝑁𝐷 (𝑃) là một quan hệ tương 
đương trên 𝑈. Nếu (𝑢, 𝑣) 𝐼𝑁𝐷 (𝑃) thì hai 
đối tượng 𝑢 và 𝑣 không phân biệt được bởi 
các thuộc tính trong P. Quan hệ tương đương 
𝐼𝑁𝐷 (𝑃) xác định một phân hoạch trên 𝑈, ký 
hiệu là 𝑈 /𝐼𝑁𝐷 (𝑃) hay 𝑈 /𝑃 . Ký hiệu lớp 
tương đương trong phân hoạch 𝑈 /𝑃 chứa đối 
tượng 𝑢 là [𝑢]𝑝, khi đó: [𝑢]𝑝 = {𝑣 𝑈 |(𝑢, 𝑣) 
 𝐼𝑁𝐷 (𝑃). 
2.2 Đặt bài toán 
Cho bảng quyết định không đầy đủ 𝐼𝐷𝑆 =
{(𝑈, 𝐴  {𝑏})}, với 𝑈 = {𝑥1, 𝑥2,  , 𝑥𝑛}. 
Giả sử 
𝑈
𝑆𝐼𝑀 (𝐴)
= {𝑆𝐴(𝑥1), 𝑆𝐴(𝑥2),  𝑆𝐴(𝑥𝑛) } 
và 
𝑈
 {𝑏}
= {(𝑉1), (𝑉2),  (𝑉𝑚) }. với 
Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 
202  Email: jst@tnu.edu.vn 
 𝑆𝐴(𝑢𝑖) ϵ 
𝑈
𝑆𝐼𝑀 (𝐴)
 ; 
 𝑉𝑗 ϵ 
𝑈
 {𝑏}
 và 𝑆𝐴(𝑢𝑖)  𝑉𝑗 ≠ . 
Ký hiệu 𝑑𝑒𝑠 (𝑆𝐴(𝑢𝑖)) 𝑣à 𝑑𝑒𝑠(𝑉𝑗) lần lượt là 
các mô tả của lớp dung sai 𝑆𝐴(𝑢𝑖) và lớp 
tương đương 𝑉𝑗 . 
𝑍𝑖𝑗 : 𝑑𝑒𝑠 (𝑆𝐴(𝑢𝑖)) → 𝑑𝑒𝑠(𝑉𝑗) (1) 
 𝑍𝑖𝑗 = 𝑆𝐴(𝑢𝑖)  
𝑉𝑗
𝑆𝐴(𝑢𝑖)
 (2) 
𝑠(𝑍𝑖𝑗 ) =
|𝑆𝐴(𝑢𝑖)  𝑉𝑗| 
|𝑈|
 (3) 
(𝑍𝑖𝑗 ) =
|𝑆𝐴(𝑢𝑖)  𝑉𝑗| 
|𝑉𝑗|
 (4) 
Giả sử: 
𝐹 = 
𝑈
 {𝑏}
= {(𝑉1), (𝑉2),  (𝑉𝑚) } 
 (5) 
là một phân lớp của 𝑈 theo b, độ chính xác của 
phân lớp F theo 𝐴, ký hiệu là 𝐴( 𝐹) , [6]: 
 𝐴( 𝐹) = 
∑ |𝐴𝑉𝑖|𝑉𝑖 ϵ 
𝑈
{𝑏}
 ∑ |𝐴𝑉𝑖|𝑉𝑖 ϵ 
𝑈
{𝑏}
 (6) 
Giả sử : IDS = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1, 𝑥2,  , 𝑥𝑛} và tập luật 𝑅𝑒𝑑 
𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑋𝑖) → 𝑑𝑒𝑠(𝑉𝑗) với 𝑋𝑖 𝑀𝐶𝐴; 𝑉𝑗 
𝑈
 {𝑏}
 , 𝑖 = 1  𝑛, 𝑗 = 1  𝑚. (7) 
Khi đó: 
Độ chắc chắn của IDS: 
𝛼(𝐼𝐷𝑆) = 
1
𝑚
∑
1
𝑁𝑖
𝑚
𝑖=1
∑
|𝑋𝑖  𝑉𝑗 |
|𝑋𝑖 |
𝑁𝑖
𝑗=1
 (8) 
 Độ nhất quán 𝛽 của IDS: 
𝛽(𝐼𝐷𝑆) = 
1
𝑚
∑ [1 −
4
|𝑋𝑖|
∑|𝑋𝑖  𝑉𝑗 |
𝑁𝑖
𝑗=1
𝜇(𝑍𝑖𝑗 )(1 − 𝜇(𝑍𝑖𝑗 ))]
𝑚
𝑖=1
 (9) 
Độ hỗ trợ 𝛾 của IDS: 
𝛾(𝐼𝐷𝑆) = ∑
|𝑉𝑗 |
𝑁𝑖|𝑈|
𝑛
𝑗=1
 ∑
|𝑋𝑘  𝑉𝑗 |
|𝑈|
𝑁𝑗
𝑘=1
 (10) 
3. Cải tiến độ đo trong lý thuyết tập thô cho bảng quyết định không đầy đủ 
Giả sử ta có : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1, 𝑥2,  , 𝑥𝑛} và tập luật 𝑅𝑒𝑑 
𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑋𝑖) → 𝑑𝑒𝑠(𝑉𝑗) với 𝑋𝑖 𝑀𝐶𝐴; 𝑉𝑗 
𝑈
 {𝑏}
 , 𝑖 = 1  𝑛, 𝑗 = 1  𝑚. 
3.1. Cải tiến các độ đo 
Độ chắc chắn của IDS: 
𝛼(𝐼𝐷𝑆) = 
1
𝑛
∑
1
𝑁𝑖
𝑛
𝑖=1
∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐴(𝑢𝑖)|
𝑁𝑖
𝑗=1
 (11) 
Độ nhất quán 𝛽 của IDS: 
Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 
 Email: jst@tnu.edu.vn 203 
𝛽(𝐼𝐷𝑆) = 
1
𝑛 − 1
∑ [
1
𝑁𝑖
∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐴(𝑢𝑖)|
𝑁𝑖
𝑗=1
]
𝑛
𝑖=1
−
1
𝑛 − 1
 (12) 
Độ hỗ trợ 𝛾 của IDS: 
𝛾(𝐼𝐷𝑆) = 
1
𝑛
∑ ∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
𝑛
𝑚
𝑗=1
𝑛
𝑖=1
 (13) 
Ký hiệu 𝑁𝑖 là số luật quyết định (số lớp quyết định) sinh bởi lớp dung sai 𝑆𝐴 (𝑢𝑖 ) . 
Ta có: 
 (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 nếu 𝜇(𝑍𝑖𝑗 ) = 1 với ∀ 𝑍𝑖𝑗 𝑅𝑒𝑑, nghĩa là 𝐼𝐷𝑆 nhất 
quán, và (𝐼𝐷𝑆) nhỏ nhất là : 
1
𝑛
 nếu 𝑁𝑖 = 𝑛 , nghĩa là 𝑚 = 𝑈 và 𝑆𝐴(𝑢𝑖) = 𝑈 với mọi 𝑢𝑖 𝑈 . 
 (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 khi (𝐼𝐷𝑆 đạt giá trị lớn nhất là 1 và  (𝐼𝐷𝑆 nhỏ nhất là 0 khi 
 (𝐼𝐷𝑆) đạt giá trị nhỏ nhất là 
1
𝑛
 . 
 (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 nếu 𝑆𝐴(𝑢𝑖) = 𝑈 với mọi 𝑢𝑖 𝑈.  (𝐼𝐷𝑆) nhỏ nhất là 
1
𝑛
 nếu 
𝑆𝐴(𝑢𝑖)= 𝑢𝑖 với mọi 𝑢𝑖 𝑈. 
3.2. Chứng minh tính đúng đắn độ đo đề xuất 
Giả sử : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})}, 𝐼𝐷𝑆′ = {(𝑈, 𝐵  {𝑏})}, với 𝑈 = {𝑥1, 𝑥2,  , 𝑥𝑛} và tập luật 𝑅𝑒𝑑 
𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑆𝐴(𝑢𝑖)) → 𝑑𝑒𝑠(𝑉𝑗) 
với 𝑆𝐴(𝑢𝑖) 
𝑈
𝑆𝐼𝑀 (𝐴)
 ; 𝑉𝑗 
𝑈
 {𝑏}
 , 𝑖 = 1  𝑛, 𝑗 = 1  𝑚. 
Nếu B  A thì (𝐼𝐷𝑆) ≥ (𝐼𝐷𝑆′) ; 𝛽 (𝐼𝐷𝑆) ≥ 𝛽 (𝐼𝐷𝑆′) ; 𝛾 (𝐼𝐷𝑆) ≤ 𝛾(𝐼𝐷𝑆′) 
+ Độ chắc chắn của IDS 
Giả sử 𝑁𝑖(𝐴), 𝑁𝑖(𝐵) tương ứng là số luật quyết định sinh bởi lớp dung sai: 𝑆𝐴(𝑢𝑖) và 𝑆𝐵(𝑢𝑖). Nếu 
B  A thì 𝑆𝐴(𝑢𝑖)  𝑆𝐵(𝑢𝑖) với mọi 𝑢𝑖 𝑈. 
Cho nên ta có thể suy ra: 𝑁𝑖(𝐴) ≤ 𝑁𝑖(𝐵). 
Từ đó ta có: 
𝛼(𝐼𝐷𝑆) = 
1
𝑛
∑
1
𝑁𝑖
𝑛
𝑖=1
∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐴(𝑢𝑖)|
𝑁𝑖
𝑗=1
= 
1
𝑛
∑
1
𝑁𝑖(𝐴)
𝑛
𝑖=1
≥
1
𝑛
∑
1
𝑁𝑖(𝐴)
𝑛
𝑖=1
= 
1
𝑛
∑
1
𝑁𝑖(𝐵)
𝑛
𝑖=1
 ∑
|𝑆𝐵(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐵(𝑢𝑖)|
𝑁𝑖(𝐵)
𝑗=1
= (𝐼𝐷𝑆′) 
Do đó: (𝐼𝐷𝑆) ≥ (𝐼𝐷𝑆′) (Điều phải chứng minh) 
+ Độ nhất quán 𝛽 của IDS: 
Ta có: 
Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 
204  Email: jst@tnu.edu.vn 
𝛽(𝐼𝐷𝑆) = 
1
𝑛 − 1
∑ [
1
𝑁𝑖
∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐴(𝑢𝑖)|
𝑁𝑖
𝑗=1
]
𝑛
𝑖=1
−
1
𝑛 − 1
=
1
𝑛 − 1
(∑
1
𝑁𝑖(𝐴)
𝑛
𝑖=1
−
1
𝑛 − 1
) ≥
1
𝑛 − 1
(∑
1
𝑁𝑖(𝐴)
𝑛
𝑖=1
−
1
𝑛 − 1
) 
= 
1
𝑛 − 1
(∑
1
𝑁𝑖(𝐵)
𝑛
𝑖=1
− 
1
𝑛 − 1
) ∑ (
|𝑆𝐵(𝑢𝑖) 𝑉𝑗 |
|𝑆𝐵(𝑢𝑖)|
𝑁𝑖(𝐵)
𝑗=1
−
1
𝑛 − 1
)
= 𝛽 (𝐼𝐷𝑆′) 
Do đó: 𝛽 (𝐼𝐷𝑆) ≥ 𝛽 (𝐼𝐷𝑆′) (Điều phải chứng minh) 
+ Độ hỗ trợ 𝛾 của IDS: 
𝛾(𝐼𝐷𝑆) = 
1
𝑛
∑ ∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
𝑛
𝑚
𝑗=1
𝑛
𝑖=1
 Nếu B  A thì 𝑆𝐴(𝑢𝑖)  𝑆𝐵(𝑢𝑖) với mọi 𝑢𝑖 𝑈. 
Ta có 𝑆𝐴(𝑢𝑖)  𝑉𝑗  𝑆𝐵(𝑢𝑖) 𝑉𝑗 với mọi 𝑢𝑖 𝑈, 𝑉𝑗 
𝑈
 {𝑏}
 |𝑆𝐴(𝑢𝑖) 𝑉𝑗 | ≤ |𝑆𝐵(𝑢𝑖) 𝑉𝑗 | 
1
𝑛
∑ ∑
|𝑆𝐴(𝑢𝑖) 𝑉𝑗 |
𝑛
𝑚
𝑗=1
𝑛
𝑖=1
≤ 
1
𝑛
∑ ∑
|𝑆𝐵(𝑢𝑖) 𝑉𝑗 |
𝑛
𝑚
𝑗=1
𝑛
𝑖=1
 𝛾 (𝐼𝐷𝑆) ≤ 𝛾(𝐼𝐷𝑆′) Điều phải chứng minh 
4. Kết luận 
Trong bài báo này, tác giả đã nghiên cứu cải 
tiến một số độ đo và chứng minh tính đúng 
đắn, từ đó có thể lựa chọn nhóm phương pháp 
cho phù hợp và tiến thành thử nghiệm đánh 
giá sự thay đổi của các độ đo cải tiến trên 
bảng quyết định không đầy đủ. Trên cơ sở đó, 
lựa chọn và đánh giá các phương pháp giảm 
bớt thuộc tính dựa trên tiêu chuẩn độ hỗ trợ 
của tập luật. 
TÀI LIỆU THAM KHẢO/ REFERENCES 
[1]. Y. H. Qian, J. Y. Liang, W. Pedrycz, and C. 
Y. Dang, “Positive approximation: an 
accelerator for attribute reduction in rough set 
theory,” Artif. Intell, vol. 174, pp. 597-618, 
2010. 
[2]. J. Y. Liang and Y. H. Qian, “Information 
granules and entropy theory in information 
systems,” Information Sciences, vol. 51, pp. 
1-18, 2008. 
[3]. J. Dai, and Q. Xu, “Attribute selection base on 
information gain ratio in fuzzy rough set 
theory with application to tumor 
classification,” Applied Soft Computing, vol. 
13, no. 2013, pp. 211-211, 2013. 
[4]. A. Skowron, and C. Rauszer, The 
discernibility matrices and functions in 
information systems. Intelligent Decision 
Support, 1992. 
[5]. Y. Leung, and D. Y. Li, “Maximal consistent 
block technique for rule acquisition in 
incomplete information systems,” Information 
Sciences, vol. 153, pp. 85-106, 2003. 
[6]. J. Y. Liang and Y. H. Qian, “Information 
granules and entropy theory in information 
systems,” Information Sciences, vol. 51, pp. 
1-18, 2008.