Thuật toán nhanh tính toán tập thuộc tính lõi của bảng quyết định dựa vào vùng dương

52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
1 
THUẬT TOÁN NHANH TÍNH TOÁN TẬP THUỘC TÍNH LÕI 
CỦA BẢNG QUYẾT ĐỊNH DỰA VÀO VÙNG DƢƠNG 
 – ) 
Phạm Quang Dũng (Trường Cao đẳng Giao thông vận tải) 
Tóm tắt 
Tính toán tập (thuộc tính) lõi của bảng quyết định là một nội dung nghiên cứu quan trọng của lý 
thuyết tập thô. Một số học giả đã xây dựng thuật toán tính toán tập lõi dựa vào vùng dương và sử dụng ma 
trận phân biệt. Độ phức tạp của thuật toán này là 
2
O C U . Bài báo này nhằm trình bày một thuật toán 
mới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phân 
biệt đơn giản hóa và tập lõi tương ứng. Chúng tôi chứng minh rằng tập lõi này tương đương với tập lõi xác 
định thông qua ma trận phân biệt nguyên thủy. Vì việc xác định phân hoạch U/C là chìa khóa để tính toán 
ma trận phân biệt đơn giản hóa, một thuật toán nhanh tính U/C được thiết kế sử dụng thuật sắp thứ tự theo 
cơ số. Độ phức tạp của thuật toán là O C U . Sử dụng thuật toán nhanh xác định U/C và ma trận phân 
biệt đơn giản hóa, một thuật toán mới xác định tập lõi dựa vào vùng dương được xây dựng. Độ phức tạp của 
thuật toán mới này được giảm thiểu và là 
'
osax O C / ,pm U U C O C U . 
Từ khóa: Tập thô, Vùng dương, Ma trận phân biệt đơn giản hóa, Tập lõi, Độ phức tạp. 
Mở đầu 
Lý thuyết tập thô [1], do Pawlak đề xuất năm 
1982, là một công cụ toán học mới để xử lý thông 
tin không chính xác, không chắc chắn hay tri thức 
mờ. Đến nay, lý thuyết tập thô đã và đang được 
ứng dụng rộng rãi trong nhiều lĩnh vực: trí tuệ 
nhân tạo, nhận dạng mẫu, khai phá tri thức và 
khám phá thông minh các luật quyết định. 
Tính toán tập (thuộc tính) lõi của bảng quyết 
định là một nội dung nghiên cứu quan trọng của lý 
thuyết tập thô. Cho đến nay, nhiều tác giả đã 
nghiên cứu đưa ra các thuật toán khác nhau tính 
toán tập lõi, trong đó có các thuật toán dựa vào 
vùng dương và sử dụng ma trận phân biệt. Trong 
[3], Hu đã đề xuất một thuật toán tính toán tập lõi 
dựa vào ma trận phân biệt với độ phức tạp là 
2
O C U . 
Trong bài này, để giảm thiểu độ phức tạp của 
thuật toán tính toán tập lõi, trước tiên chúng tôi 
đưa ra định nghĩa về ma trận phân biệt đơn giản 
hóa và định nghĩa tập lõi tương ứng. Chúng tôi 
chứng minh rằng tập lõi này tương đương với tập 
lõi xác định thông qua ma trận phân biệt nguyên 
thủy. Vì việc xác định phân hoạch U/C là bước 
chính trong quá trình tính toán ma trận phân biệt 
đơn giản hóa, một thuật toán nhanh tính U/C được 
thiết kế sử dụng thuật sắp thứ tự theo cơ số. Độ 
phức tạp của thuật toán là O C U . Sử dụng 
thuật toán nhanh xác định U/C, ma trận phân biệt 
đơn giản hóa, một thuật toán mới xác định tập lõi 
dựa vào vùng dương được xây dựng. Độ phức tạp 
của thuật toán mới này được giảm xuống là 
'
osax O C / ,pm U U C O C U , 
trong đó 
'
ospU là tập các đại diện của các lớp 
tương đương sinh bởi phân hoạch U/C. 
I.Ma trận phân biệt đơn giản hóa dựa vào vùng 
dƣơng. 
Định nghĩa 2.1. [1]. Bảng quyết định là một bộ tứ 
, , , ,S U C D V f , trong đó 1 2, ,..., nU x x x 
là tập các đối tượng, 1 2, ,..., rC c c c là tập các 
thuộc tính điều kiện, D là tập các thuộc tính quyết 
định, C D ; a
a C D
V V , trong đó aV là 
miền giá trị của thuộc tính a; 
: ( )f U C D V là hàm thông tin cho biết 
giá trị của mỗi thuộc tính tại mỗi đối tượng, nghĩa 
là , , , aa C D x U f x a V . 
Mỗi tập con thuộc tính P C D xác định 
một quan hệ nhị phân, gọi là quan hệ không phân 
biệt IND P :
, | , , ,IND P x y U U a P f x a f y a (1) 
52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
2 
Dễ thấy, IND P là quan hệ tương đương. Ta 
ký hiệu phân hoạch của U sinh bởi IND P là 
/U IND P hoặc ngắn gọn hơn là /U P . Mỗi 
tập con 
| , , ,
p
x y U a P f x a f y a
trong /U P là một lớp tương đương. 
Định nghĩa 2.2. [1]. Cho bảng quyết định 
, , , ,S U C D V f , X U và tập con thuộc 
tính R C D . Tập 
_ | / ,i i iR X R R U R R X được gọi 
là xấp xỉ dưới của X theo R. 
Định nghĩa 2.3. [1]. Cho bảng quyết định 
, , , ,S U C D V f Giả sử 
1 2/ , ,..., kU D D D D , 
1 2/ , ,..., mU C C C C . Tập cPOS D xác 
định theo công thức
/
_
i
c i
D U D
POS D C D 
được gọi là vùng dương của D theo C. Nếu 
CPOS D U thì S được gọi là bảng quyết định 
nhất quán, trường hợp ngược lại là không nhất quán. 
Định lý 2.1. Cho bảng quyết định 
, , , ,S U C D V f , ta có 
/ / 1
C
X U C X D
POS D X
. 
Chứng minh: Suy ra trực tiếp từ Định nghĩa 2.3. 
Định nghĩa 2.4. Cho bảng quyết định 
, , , ,S U C D V f . Giả sử 
1 2
' ' '...
tC i i ic c c
POS D x x x   (theo 
Định lý 2.1),trong đó 
1 2
' ' ' ', ,...,
ti i i
x x x U và 
' / 1
si C
x D 1,2,...,s t . Ký hiệu 
1 2
' ' ' '
os , ,..., tp i i iU x x x , 
' ' '
osneg pU U U . Khi đó 
' ' , , , ,S U C D V f được gọi là bảng quyết định 
đơn giản hóa. 
' ' '
1 2/ , ,..., mc c c
U C x x x , 
' ' ' '
1 2, ,..., mU x x x và 
Định nghĩa 2.5. [4]. Cho bảng quyết định 
, , , ,S U C D V f . Với thuộc tính c C , nếu 
C C c
POS D POS D thì c được gọi là 
không cần thiết trong S, ngược lại c là cần thiết. 
Tập tất cả các thuộc tính cần thiết trong S được gọi 
là tập lõi, ký hiệu là ( )Core C . 
Định nghĩa 2.6. [4]. Cho bảng quyết định 
, , , ,S U C D V f và tập thuộc tính P C . 
Nếu mọi c P là cần thiết trong S thì P được 
gọi là độc lập. 
Định nghĩa 2.7. [4]. Cho bảng quyết định 
, , , ,S U C D V f . Tập thuộc tính R C được 
gọi là một rút gọn của tập thuộc tính điều kiện C 
nếu R là độc lập và ( ) ( )R CPOS D POS D . Nói 
cách khác, R là rút gọn nếu nó là tập tối tiểu thỏa 
mãn ( ) ( )R CPOS D POS D . 
Định lý 2.2. [4]. Cho bảng quyết định 
, , , ,S U C D V f . Gọi Red C là tập tất cả 
các rút gọn của C, ta có 
( )

B Red C
Core C B . 
Định nghĩa 2.8. Cho bảng quyết định 
, , , ,S U C D V f . ' ', , , ,S U C D V f là 
bảng quyết định đơn giản hóa từ S. Ma trận 
' '
'
2 i j
M m với các phần tử i jm xác định bởi: 
 (2) 
được gọi là ma trận phân biệt đơn giản hóa dựa 
vào vùng dương. 
' ' ' ' ' ' ' '
'
posi
/ , , , nÕu vµ chØ nÕu x hoÆc x thuéc ;
 , , , x , , nÕu vµ thuéc U
 trong tr­êng hîp ng­îc l¹i
'
i j i j pos
i j i j j i j
a a C f x a f x a U
m f x a f x a f D f x D x x
(2) 
Định nghĩa 2.9. Cho bảng quyết định 
, , , ,S U C D V f và ma trận phân biệt được 
đơn giản hóa dựa vào vùng dương ' '
'
2 i j
M m 
Khi đó, SDCore C được gọi là tập lõi của '
2M , 
trong đó 
' ' ' '
'
2| , ,i j i jSDCore C a a C m a m M 
52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
3 
Định lý 2.2. Cho bảng quyết định 
, , , ,S U C D V f , ta có:
SDCore C Core C . 
Chứng minh: Với bất kỳ a SDCore C tồn tại 
'
ix và 
'
jx sao cho ' 'i jm a . Theo định nghĩa 
2.8, cả '
ix và 
'
jx đều thuộc 
'
ospU , hoặc một trong 
các phần tử này thuộc 
'
ospU còn phần kia thuộc 
'
negU . Nếu cả 
'
ix và 
'
jx đều thuộc 
'
ospU thì 
' ' '
i j iC C C a
x x x ( do 'i Cx và 
'
j C
x 
là không thể phân biệt được trừ phi sử dụng thuộc 
tính a.), trong khi 
' ', ,i jf x D f x D , do đó 
' '
i i C aC C
x x POS D . Mặt khác do 
' 'i i CC Cx x POS D , ta có 
CC a
POS D POS D , nên theo Bổ đề 2.1, 
a Core C . Nếu một trong '
ix và 
'
jx thuộc 
'
ospU , thì phần tử còn lại sẽ thuộc 
'
negU . Giả sử 
' '
i posx U và 
' '
j negx U , ta có 
' ' '
i j iC C C a
x x x . Vì ' 'j negx U nên 
' 'i i C aC Cx x POS D , do đó 
'
i C aC
x POS D . Mặt khác, vì 
'
i CC
x POS D nên CC aPOS POS D . 
Theo Bổ đề 2.1, ta có a Core C . Vì a được 
lựa chọn bất kỳ, ta có SDCore C Core C . 
Với bất kỳ a Core C , theo Bổ đề 2.1, đều có 
C C a
POS D POS D . Do vậy, tồn tại 
' '
ix posU sao cho 
'
i C aC a
x POS D . 
Suy ra, sẽ có ít nhất một đối tượng '
i
x thỏa mãn 
' ' ' ' ' ',i i j i jC a C
x x x x x U và 
' ', ,i jf x D f x D . Vì 
' '
j i C
x x , ta có 
' ', ,i jf x a f x a . Lại vì 
' '
j j C a
x x , do 
đó 
' ', , -i jf x b f x b b C a . Nếu 
' '
j negx U , theo Định nghĩa 2.7, ta có ' 'i jm a . 
Còn nếu 
' '
j posx U , thì vì 
' ', ,i jf x D f x D , 
theo Định nghĩa 2.7, ta có ' 'i jm a . Do đó, 
a SDCore C . Vì a được lựa chọn tùy ý, suy 
ra SDCore C Core C . 
II.Thuật toán nhanh tính bảng quyết định đơn 
giản hóa. 
Chìa khóa để lập được bảng quyết định đơn giản 
hóa là việc xác định phân hoạch U/C. Độ phức tạp 
của thuật toán thông thường xác định U/C là 
2
O C U . Để làm giảm thiểu hơn nữa độ phức 
tạp, trong bài báo này, chúng tôi sử dụng ý tưởng 
của thuật sắp xếp theo cơ số. Bằng cách này, độ 
phức tạp của thuật toán xác định U/C được giảm 
xuống là O C U . 
1. Thuật toán 1: Tính bảng quyết định đơn giản 
hóa 
Đầu vào: Bảng quyết định , , , ,S U C D V f , 
1 2, ,..., nU x x x , 1 2, ,..., rC c c c 
Đầu ra: 
' '
os , p negU U . 
Bước 1: Tìm giá trị cực đại iM và giá trị cực tiểu 
i
m của hàm , 1,2,...,j if x c j n với mỗi 
1,2,...,ic i r . 
Bước 2: Lưu lần lượt các đối tượng 1 2x , ,..., nx x 
theo thứ tự tĩnh ban đầu và tạo con trỏ đầu bảng 
trỏ đến 1x .Bước 3: for (i =1, i < r+1, i ++)3.1. 
“Sắp xếp” lần thứ i: xây dựng 1i iM m hàng 
đợi rỗng. Đặt kfront và kend 
0,1,..., i ik M m tương ứng là con trỏ đầu và 
con trỏ cuối của hàng đợi thứ k. Theo thứ tự, phân 
bổ mỗi đối tượng x U của dãy tĩnh ban đầu vào 
hàng đợi thứ , i if x c m . 
2. “Gom lớp” lần thứ i: Cho con trỏ đầu trỏ đến 
con trỏ đầu của hàng đợi khác rỗng đầu tiên, chỉnh 
52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
4 
sửa lại con trỏ cuối của mỗi hàng đợi khác rỗng 
sao cho nó trỏ đến đối tượng đầu tiên của hàng đợi 
khác rỗng tiếp theo. 
Bước 4: Giả sử dãy thu được sau bước 3 là 
' ' '
1 2, ,..., nx x x ; 
'
11; ;tt B x 
' ' '
-1
for 2, 1,
 if , , , 1,2,..., ;j i j i i t t j
j j n j
f x c f x c c C i r B B x
'
t else t=t+1;B ;jx 
Bước 5: 
' '; ;pos negU U 
 for (i=1, i < t+1, i++) 
 if ( , ) ( , ) ,
i
f x D f y D x y B lấy 
đối tượng đầu tiên của iB nhập vào 
'
ospU ; 
 else lấy đối tượng đầu tiên của iB nhập 
vào 
'
negU ; 
Độ phức tạp của thuật toán 1 là: O C U . 
III.Thuật toán Nhanh tính toán tập lõi 
Theo Định nghĩa 2.7., Định nghĩa 2.8., Định lý 
2.2. và Thuật toán 1, ta có thể thiết kế một thuật 
toán sau đây cho việc tính toán tập lõi dựa vào 
vùng dương. 
1.Thuật toán 2: Thuật toán cho việc tính toán 
tập lõi 
Đầu vào: Bảng quyết định , , , ,S U C D V f , 
1 2, ,..., nU x x x , 1 2, ,..., rC c c c 
Đầu ra: Core(C) 
Sử dụng Thuật toán 1 tính bảng quyết định đơn 
giản hóa, thu được: 
' '
1 2 1 2, ,..., ; , ,..., ;pos s neg sU y y y U z z z 
Cho ( ) ;core C 
 for 1, ,i i s i 
 for 1, 1,j j s j 
 if , ,i jf y D f y D 
 { ; 0;B flag 
 for 1, 1,k k r k 
 { if , ,i k j kf y c f y c 
 { ; ; kB B c flag } 
 if (flag > 1) break; 
 } 
 if (flag = = 1) 
 core(C) = core(C) B ; 
 } 
 for 1, 1,i i s i 
 for 1, 1,j i j t j 
 { ; 0;B flag 
 for 1, 1,k k r k 
 { if , ,i k j kf y c f z c 
 { ;kB B c flag } 
 if (flag >1) break ; 
 } 
 if ( flag==1) 
 ( ) ( ) ;core C core C B 
 } 
Độ phức tạp của thuật toán 2 là:O U . 
IV.Ví dụ 
Trong mục này, ta minh họa tính hiệu quả của 
thuật toán mới thông qua một ví dụ. Xét bảng 
quyết định sau đây (Bảng 1): 
 a b c d D 
X1 2 1 2 1 0 
X2 2 2 2 1 1 
X3 2 1 2 1 0 
X4 2 3 2 3 0 
X5 2 2 2 1 1 
X6 3 1 2 1 0 
X7 1 2 3 2 2 
X8 4 3 1 2 3 
X9 3 1 2 1 1 
X10 1 2 3 2 2 
X11 3 1 2 1 1 
X12 4 3 1 2 3 
X13 4 3 4 2 1 
X14 1 2 3 2 3 
X15 4 3 4 2 2 
52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
5 
Bảng 1: Bảng quyết định 1 
Với 15 đối tượng của U, phân hoạch U/{a,b,c,d} được tính toán theo thuật toán 1. 
Tiến trình xử lý như sau: 
1. Đặt 1 2 3 4, , ,c a c b c c c d . Sau bước 1 của thuật toán 1 ta có: 
1 1 2 2 3 3 4 44, 1; 3, 1; 4, 1; 3, 1;M m M m M m M m 
2. Sau theo bước 2 của Thuật Toán 1( Tính toán bảng quyết định đơn giản hoá) thu được: 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; ;X X X X X X X X X X X X X X X 
3. Kết quả “sắp xếp” lần thứ 1 là: 
7 10 14 1 2 3 4 5
6 9 11 8 12 13 14
0 0 ; 1 1 ;
2 2 ; 3 3 ;
front X X X end front X X X X X end
front X X X end front X X X X end
4. Kết 
quả “gom lớp” lần thứ 1 là: 
7 10 14 1 2 3 4 5 6 9 11 8 12 13 15; ; ;X X X X X X X X X X X X X X X
5. Kết quả “sắp xếp” lần thứ 2 là: 
1 3 6 9 11 7 10 14 2 5
4 8 12 13 15
0 0 ; 1 1 ;
2 2 ;
front X X X X X end front X X X X X end
front X X X X X end
6. Kết quả “gom lớp” lần thứ 2 là: 
1 3 6 9 11 7 10 14 2 5 4 8 12 13 15; ; ;X X X X X X X X X X X X X X X
7. Kết quả “sắp xếp” lần thứ 3 là: 
8 12 1 3 6 9 11 2 5 4
7 10 14 13 15
0 0 ; 1 1 ;
2 2 ; 3 3 ;
front X X end front X X X X X X X X end
front X X X end front X X end
8. Kết quả “gom lớp” lần thứ 3 là: 
8 12 1 3 6 9 11 2 5 4 7 10 14 13 15; ; ;X X X X X X X X X X X X X X X
9. Kết quả “sắp xếp” lần thứ 4 là: 
1 3 6 9 11 2 5
8 12 7 10 14 13 15 4
0 0 ;
1 1 ; 2 2 ;
front X X X X X X X end
front X X X X X X X end front X end
10. Kết quả “gom lớp” lần thứ 4 là: 
1 3 6 9 11 2 5 8 12 7 10 14 13 15 4; ; ;X X X X X X X X X X X X X X X
11. Kết quả thu được sau bước 4 của thuật toán 1 là: 
1 3 6 9 11 2 5 8 12 7 10 14 13 15 4, , , , , , , , , , , , , , ;X X X X X X X X X X X X X X X 
12. Kết quả sau bước 5 của thuật toán 1 là:
' '
os 1 2 8 4 6 7 13, , , ; , , ;p negU X X X X U X X X 
13. Kết quả sau bước 2 của thuật toán 2 là: ;core C b 
14. Kết quả sau bước 3 của thuật toán 2 là: , , ;core C b a c 
V.Kết luận 
52(4): 3 - 12 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
6 
Cho đến nay, theo chúng tôi được biết, thuật toán hiện hành tốt nhất tính toán tập lõi của một bảng 
quyết định dựa vào vùng dương, sử dụng ma trận phân biệt có độ phức tạp là 
ax O C / log , Cm U C U O C U POS D . 
Trong bài báo này, chúng tôi đã trình bày một thuật toán mới có độ phức tạp thấp hơn. Dựa vào vùng 
dương, chúng tôi đã định nghĩa ma trận phân biệt đơn giản hóa và tập tập lõi tương ứng. Chúng tôi đã 
chứng minh được tập lõi này là tương đương với với tập lõi xác định thông qua ma trận phân biệt nguyên 
thủy (Đã chứng minh ở Định lý 2.2). Để xác định phân hoạch U/C, chìa khóa để tính toán ma trận phân 
biệt đơn giản hóa, một thuật toán nhanh đã được xây dựng, sử dụng thuật sắp thứ tự theo cơ số. Độ phức 
tạp của thuật toán này là O C U . 
Sử dụng thuật toán nhanh xác định U/C và ma trận phân biệt đơn giản hóa, một thuật toán mới xác 
định tập lõi dựa vào vùng dương được đề xuất. 
Độ phức tạp của thuật toán tính lõi mới này được giảm thiểu và là 
'
osax O C / ,pm U U C O C U . Tính hiệu quả của thuật toán cũng đã được minh họa thông qua 
một ví dụ cụ thể. 
Tài liệu tham khảo: 
[1].Z.Pawlak, “Rough Sets”, International Journal of Information and Computer Science, 1982, 11(5), pp.341-356. 
[2]. A.Skowron, C.Rauszer, “The Discernibility Matrices and Functions in Information Systems”, In: R.Slowinski, 
(eds.), Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory, 1992, pp. 
331-362. 
[3]. X H. Hu, N. Cercone, “Learning in Relational Databases: a Rough Set Approach”, Computational Intelligence, 
1995, 11(2), pp. 323-337. 
[4].D Y, Ye, Z J. Chen, “A New Difference Matrix and its Methods of Core Finding”, Chinese Journal of 
Electronics, 2002, 30(7), pp. 1086-1088. 
[5].J. Zhao, G Y. Wang, and Z F. Wu, “An Efficient Appoarch to Compute the Feature Core”, Mini-Micro Systems, 
2003, 24(11), pp. 1950-1953.