Một số vấn đề về phụ thuộc hàm và phụ thuộc hàm xấp xỉ trong lý thuyết tập thô và ứng dụng vào bài toán rút gọn thuộc tính

Y 
 
→ Z => S 
X 
Y 
 [t]


ÀM
ẽ xét các tính chất 

Y. 
 [t]
 U 
2, t
0
Y
& t.X = t’.X 
 X 
3, t
8.
 
 X 
165
4, t5
 Y
→ Y. 
ì t.Y = 
X. D
→ Z
, t6, 
ễ 
166
t’.X thì t.Y = t’.Y và vì S 
S 
tính ch
Tính ch
suy ra S 
ta có S 
ch
2 
Ch
Gi
Tính ch
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
Ch
Vì S 
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
Ch
Theo tính ch
Tính ch
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
=> S 
Ch
Vì S 
ất 2 ta có S
Tính ch
Với m
=>
Ch
Theo tính ch
Theo gi
Theo gi
Theo tính ch
Theo tính ch
Bổ đề 6.
Ch
- Đi
Để chứng minh U/X = U/XY ta sẽ chứng minh 
 t
Theo tính ch
Theo b
Vậy 
- Đi
ứng minh:
ả sử t.X = t’.X ta phải chứng minh t.Z = t’.Z. Thật vậ
X → Z đpcm.
ứng minh:
ất 3 ta có S 
ứng minh:
ứng minh:
 S 
ứng minh: 
ứng minh:
ều kiện cần giả sử S 
U ta có

ều kiện đủ giả sử U/X = U/XY.
ất 5. 
XZ 
X 
ọi bộ bốn tập thuộc tính X, Y, Z, V nếu S 
ả thiết ta có 
ả thiết ta có 
ổ đề 3 ta có [t]
 t 
N. B. Tư
ất 4. 
X → Y n
XZ 
→ Y
ất 6. 
XZ 
→ Y n
ất 7. 
X → XYZV
 Cho h
S 
 U [t]
Tính t
Tính m
ất 1 ta có S 
→ Y v
 Tính c
→ YV
Tính Tích l
ất 1 ta có 
ất 3
ất 6 cộng hai vế của (*) & (**)
 [t]
ất cộng hai vế (tính chất 6) ta có
ờng, N. B. Quảng, “Một số vấn đề về phụ thuộc h
\V đpcm.
YZ
 ta có 
ệ thông tin S = (U, A ); X, Y 
X → Y khi v
XY 
X
ựa bắc cầu
ên theo tính ch
XZ 
ở rộng trái, thu hẹp 
à ti
ên theo tính ch
 → YV theo tính ch
 [t]
S 
S 
S 
 = [t]
→ V đpcm. 
ếp tục theo tính chất 1 ta lại có S 
ộng đầy đủ 
X, M
 X 
 X 
 X 
X 
XY
ũy
→ Y
→ X
→ XY
 [t]
 => U/X = U/XY.
XZ 
à ch
 X 
ặt khác theo giả thiết & tính phản xạ của phụ thuộc h
XY
→ X, theo gi
ất 2 ta có S 
S 
S 
S 
S 
ỉ khi U/X = U/XY 
→ Y, ta ch
. 
 Y 
ất 2 ta có S 
 X 
 X 
 Y 
 X 
→ Z n
ất 3 ta có S 
→ X (*)
→ Y (**)
→ ZV
→ ZV (***) 
Công ngh
ph
ứng minh U/X = U/XY.
ải
 & (***) ta có S 
ả thiết ta có S 
XZ 
 
ệ thông tin & C
ên n
X 
XZ 
→ YZ, v
A. Khi đó
 t
ếu t.Y = t’.Y th
→Y & S 
→ YZ v
XZ 
U, 
y vì S 
X→
X→Y &
→ YV đpcm.
[t]
Y =>S 
Y 
ì S
 X 
X 
àm  rút g
YZ 
à vì S
→ Y
→ Y &
=[t]
ơ s
 X 
X 
\
 S 
X → XYZV đpcm.
XY. 
ở toán học cho tin học
→ Y n
→ V => S 
→ Y theo tính ch
V => theo tính ch
Z 
Z 
 Th
ì t.Z = t’.Z => 
YZ 
XZ 
→ V 
→ V n
ật vậy theo bổ đề 
ọn 
→ V n
→ Y 
S 
thu
ên n
ên theo tính 
Y 
ộc tính.
ếu t.X = 
XZ 
ên theo 
\ V
→ ZV 
àm ta có
→ V.
ất 3 
ất 3 
”
Nghiên c
Tạp chí Nghi
[t]
Y. Tuy nhiên trong r
X 
mãn X 
card(POS(XZ, YZ))/Card(U) 
YZ ch
3. RÚT G
thu
độ phụ thuộc, độ quan trọng của thuộc tính dựa tr
heuris
tính quy
Vì U/X = U/XY nên 
XY 
Trong đ
→ Y m
Gọi T = (
Định nghĩa 14. 
Chúng ta g
Rõ ràng r
Định lý 1.
Ch
Để chứng minh (2) ta sẽ tính U
Dễ thấy rằng nếu [t]
Từ đây suy ra 
Từ chứng minh của định lý 1 ta có thuật toán tính độ chắc chắn c(X → Y).
Thu
Input H
Output c( X 
Algorithm
1.
2.
3.
4.
Định nghĩa 15. 
Chúng ta nói ph
Bổ đề 7.
Ch
Theo b
Tron
ộc từ Định nghĩa 14. Ph
Định nghĩa 16. 
= [t’]
→ Y. Nói cách khác T 
ứng minh: 
ật toán 1.
ứng minh:
ắc chắn trong S đpcm. 
g ph
tic tìm t
ứu khoa học công nghệ 
XY
à ch
UT: = 
Tính U/X, U/Y
For each t 
c( X 
ổ đề 3 ta có POS(X,Y) 
ỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ PHỤ THUỘC 
ết định D v
ên c
 => [t]
ịnh nghĩa 12 ở tr
ỉ S’ con của S thoả m
U
ọi 
ằng 0 
 Cho h
ệ thông tin S = (U, A) & X, Y 
→ Y): = 
 N
ần n
ập rút gọn dựa tr
ứu KH&CN 
T, A) là h
đ
c( X 
k(X 
U
→ Y)
∅ 
ếu X → Y chắc chắn trong S th
ày, chúng tôi xây d
X
Cho h
ộ chắc chắn

ệ thông tin S = (U, A ); X, Y 
T = 
c(X
 Tính 

Cho h
ụ thuộc h
[2] Cho h
ào t
[t]Y
→ Y) = 
 c( X 
→ Y) = c(X → Y). 
X 

→Y)=card(U
 U if [t]
|
U
ập thuộc tính điều kiện C đ
 = [t’]
ất nhiều tr
ệ thông tin con cực đại (chứa nhiều bộ nhất) của S = (U, A) thỏa 
ệ thông tin S = (U, A ); X, Y 

( X 
U
T
ệ thông tin S = (U, A ); X, Y
quân s
 
ên chúng ta đ
→ Y) 
 [t]
{ [t]
X 
|
àm X 
ương pháp bao g
t 
X[t’]
 của phụ thuộc h
U|
U
Y thì [t]
X: [t]
→ Y).

≥ card(POS(X, Y))/card(U) = c(X → Y) ≥ minc => XZ → 
ên đ
ệ quyết định T = (U, C
ự, Số
 U 
Y
ãn ph
 X 
|
T
. 
 1 và n
T. Gi
T
 [t]
→ Y 

ộ quan trọng của thuộc tính.
 => [t]
ư
→ Y
X 
X 
)/card(U)=card(POS(X,Y))/card(U)=k(X
Y then U
 POS(XZ, YZ) và theo đ
ựng ph
 60, 4
[t]
ã nêu 
ờng hợp S không thỏa m
ụ thuộc h
ếu 
ả sử U/X = {[t]
 U
 [t]
ch
X 
Y = [t’]
c
T. Như v
Y 

T
ắc chắn trong S 
ương pháp rút g
- 20
= [t]
đ
àm X 
( X 
với [t]
 A.
 = U
ì XZ 
ồm các b
19 
XY
Y 
ịnh nghĩa S thỏa m
àm X 
(4)
→ Y) = 1 th

(5)
T 
ư
 =>
= > S 
→ Y trong S l
 A. Khi đó ta có 
ậy 
Y 
[t]
→ YZ ch
ên đ
ợc định nghĩa

→ Y. 

X: t
 U/Y } = POS(X, Y)
X 
 
ước: định nghĩa tập rút gọn dựa tr
ộ phụ thuộc v

t, t’
 A. 
U}; U/Y={ [t]
A. Cho ngư
n
 D ), đ

X → Y
ì S 
ếu c(X → Y) 
ắc chắn trong S.
ịnh lý 1 ta có c(XZ → YZ) = 
ọn thuộc tính sử dụng độ phụ 
 U n
ộ phụ thuộc của tập thuộc 
ãn ph
à 
 X 
ỡng minc 
ếu [t]
ãn ph
→ Y. 
à đ
ụ thuộc h
Y: t 
≥ 
ề xuất thuật toán 
X
ụ thuộc h

→Y).
minc.
 = [t’]
 U}.
 
àm X 
[0, 1].
167
X 
=> 
→ 
àm 
ên 
Công nghệ thông tin & Cơ sở toán học cho tin học 
N. B. Tường, N. B. Quảng, “Một số vấn đề về phụ thuộc hàm  rút gọn thuộc tính.” 168 
 
 ,
C
POS C D
D
U
  
Theo Định nghĩa 14, dễ thấy rằng      C D k C D c C D     
Định nghĩa 17. Cho hệ quyết định  ,T U C D  , tập thuộc tính R C được gọi là 
tập rút gọn của C nếu thỏa mãn 
1)    R CD D  
2)      , CR rr R D D    
Dễ thấy rằng, tập rút gọn bởi Định nghĩa 17 tương đương với tập rút gọn miền dương 
bởi Định nghĩa 14. 
Định nghĩa 18. Cho bảng quyết định  ,T U C D  với B C và b C B  . Độ 
quan trọng của thuộc tính b đối với B được định nghĩa bởi 
       B BB bSIG b D D   
Dễ thấy rằng   0BSIG b  . Độ quan trọng  BSIG b đặc trưng cho chất lượng phân 
lớp của thuộc tính b đối với tập thuộc tính quyết định D và được sử dụng làm tiêu chuẩn 
lựa chọn thuộc tính cho thuật toán heuristic tìm tập rút gọn. 
Phần tiếp theo, chúng tôi trình bày thuật toán heuristic tìm một tập rút gọn. Ý tưởng 
của thuật toán là xuất phát từ tập rỗng :R  , lần lượt bổ sung vào R các thuộc tính có 
độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. 
Thuật toán ADAR (Attribute Dependency based Attribute Reduction). Thuật toán 
heuristic tìm một tập rút gọn sử dụng độ phụ thuộc. 
Đầu vào: Bảng quyết định  ,T U C D  
Đầu ra: Một tập rút gọn R . 
1. :R   ; 
// Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất 
2. While    R CD D  do 
3. Begin 
4. Với mỗi a C R  tính        R RR aSIG a D D   ; 
5. Chọn ma C R  sao cho     R m R
a C R
SIG a Max SIG a
 
 ; 
6. 
  : mR R a 
; 
7. End; 
 // Loại bỏ các thuộc tính dư thừa trong R nếu có 
8. Với mỗi a R 
9. Begin 
10. Tính 
   R a D  ; 
11. If 
     CR a D D   then  :R R a  ; 
12. End; 
13. Return R; 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 169
Giả sử  D d , dễ thấy độ phức tạp thời gian của thuật toán ADAR là  2 2O C U 
với C là số thuộc tính điều kiện, U là số đối tượng. 
4. KẾT LUẬN 
Chúng tôi đã giới thiệu một số nghiên cứu, tính chất đặc biệt, hữu ích, có tính hệ thống, 
cơ bản của các khái niệm liên quan đến hệ thông tin S =(U, A), phụ thuộc hàm, phụ thuộc 
hàm xấp xỉ, độ chắc chắn của phụ thuộc hàm dựa trên nền lý thuyết tập thô. Đặc biệt trong 
bài viết chúng tôi đã tự nêu và chứng minh chặt chẽ một định lý, 7 bổ đề và 7 tính chất của 
khái niệm phụ thuộc hàm trong hệ thông tin. Trong bài viết chúng tôi cũng đã nêu một thuật 
toán tìm độ chắc chắn của phụ thuộc hàm. Chúng tôi nghiên cứu về vùng dương, ràng buộc 
của các tập thuộc tính trong hệ tin, hệ quyết định, trên cơ sở đó xây dựng một thuật toán 
heuristic tìm tập rút gọn của bảng quyết định sử dụng độ phụ thuộc của thuộc tính. 
TÀI LIỆU THAM KHẢO 
[1] Chen, D., Cui, D., Wang, C., Wang, Z. "A Rough Set-Based Hierarchical clustering 
Algorithm for categorical Data". International Journal of Information Technology, 
Vol. 12, No.3, 2006, pp 149-159. 
[2] Han, J., Hu,X., Lin, T.Y. "Feature Subset Selection Based on Relative Dependency 
between Attributes". Rough Sets and Current Trends in Computing 2004, pp 176-185. 
[3] Yan-Yong Guan, Hong-Kai Wang. "Set-value information systems". Information 
Science, vol 176, 2006, pp 2507-2525. 
[4] Z. Pawlak (1991). "Rough sets: theoretical aspect of reasoning about data". 
[5] Nguyễn Bá Tường. "Cơ sở dữ liệu quan hệ và ứng dụng". Nhà xuất bản Thông Tin và 
Truyền Thông, 2011. 
ABSTRACT 
FUNCTIONAL DEPENDENCIES AND APPROXIMATE FUNCTIONAL 
DEPENDENCIES IN ROUGH SETS THEORY AND APPLICATION IN 
ATTRIBUTE REDUCTION PROBLEM. 
In this paper, we present some concepts and properties related to the S = (U, A) 
information system, dependence, approximation, positive region in the set theory. 
On this basis, the basis for further study of the properties of the positive region, the 
constraints between attributes and, in particular, between the conditional properties 
in the decision system are the premise of the algorithms. Finally, we propose a 
dependency based attribute reduction algorithm in decision tables. 
Keywords: Partition; Relation; Approximation; Rough sets; Functional dependency; Dependency 
approximation; Reduct. 
Nhận bài ngày 30 tháng 11năm 2018 
Hoàn thiện ngày 24 tháng 3 năm 2019 
Chấp nhận đăng ngày 16 tháng 4 năm 2019 
Địa chỉ: 1 Đại học SP kỹ thuật Hưng Yên; 
2 Đại học Kiến trúc Hà Nội. 
* Email: quangnb1@gmail.com.