Khai phá dữ liệu trên hệ thông tin đa trị

Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
103 
KHAI PHÁ DỮ LIỆU TRÊN HỆ THÔNG TIN ĐA TRỊ 
Phùng Thị Thu Hiền* 
Trường Đại học Kinh tế Kỹ thuật Công nghiệp 
TÓM TẮT 
Dựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu, trong bài báo này tác giả đề xuất phương 
pháp lựa chọn tập đối tượng đại diện, gọi tắt là mẫu đại diện, từ tập đối tượng ban đầu cho bài toán 
tìm tập thuộc tính tối ưu của hệ thông tin đa trị. Tác giả chứng minh tập thuộc tính tối ưu trên tập 
đối tượng ban đầu và tập thuộc tính tối ưu trên mẫu đại diện là tương đương, từ đó khẳng định tính 
đúng đắn của phương pháp. Vì kích thước mẫu đại diện nhỏ hơn kích thước tập đối tượng ban đầu 
nên thời gian thực hiện các thuật toán tìm tập thuộc tính tối ưu trên mẫu đại diện giảm thiểu đáng 
kể. Kích thước mẫu đại diện được chọn lớn hay nhỏ phụ thuộc vào đặc thù mỗi hệ thông tin đa trị 
trong thực tế. Đồng thời bài báo trình bày phương pháp khai phá luật xếp thứ tự bằng cách chuyển 
đổi hệ thông tin đơn trị xếp thứ tự thành hệ thông tin đơn trị nhị phân và áp dụng các kỹ thuật sinh 
luật trong lý thuyết tập thô trên hệ thông tin đơn trị nhị phân thu được. 
Từ khóa: Hệ thông tin đa trị, tập thô, tập thuộc tính tối ưu, quan hệ dung sai 
MỞ ĐẦU* 
Lý thuyết tập thô truyền thống do Pawlak [1], 
[2] đề xuất được xây dựng dựa trên quan hệ 
tương đương nhằm giải quyết bài toán tìm tập 
thuộc tính tối ưu và sinh luật quyết định trên 
các hệ thông tin đơn trị. Trong các bài toán 
thực tế, giá trị một đối tượng tại một thuộc 
tính trên hệ thông tin có thể là một tập hợp 
nhiều giá trị. 
Trên cả hệ thông tin đơn trị và hệ thông tin đa 
trị, tìm tập thuộc tính tối ưu là bài toán quan 
trọng nhất, đã và đang thu hút sự quan tâm 
của cộng đồng nghiên cứu về tập thô. Với bài 
toán tìm tập thuộc tính tối ưu, vấn đề đang 
được các nhà nghiên cứu quan tâm hàng đầu 
là xây dựng các phương pháp pháp nhằm tối 
ưu thời gian thực hiện các thuật toán, nhờ đó 
có thể áp dụng trên các hệ thông tin kích 
thước lớn. Trên hệ thông tin đơn trị, cho đến 
nay nhiều phương pháp tìm tập thuộc tính tối 
ưu đã được công bố [3], tuy nhiên các phương 
pháp này đều thực hiện trên tập đối tượng ban 
đầu. Trên hệ thông tin đa trị, các công trình 
nghiên cứu [4], [5], [6] đã đề xuất giải pháp 
nén dữ liệu với mục đích thu nhỏ kích thước 
tập dữ liệu ban đầu nhằm giảm thiểu thời gian 
thực hiện các thuật toán. 
*
 Tel: 0914 770070, Email: Thuhiencn1@gmail.com 
Bài báo này tác giả đề xuất phương pháp lựa 
chọn tập đối tượng đại diện, gọi tắt là mẫu đại 
diện, từ tập đối tượng ban đầu cho bài toán 
tìm tập thuộc tính tối ưu của hệ thông tin đa 
trị, và trình bày phương pháp khai phá luật 
xếp thứ tự. 
Cấu trúc bài báo như sau. Phần 2 trình bày 
một số khái niệm cơ bản và một số kết quả 
trên hệ thông tin đa trị và phương pháp khai 
phá luật xếp thứ tự trên hệ thông đơn trị. Phần 
3 đề xuất phương pháp chọn mẫu đại diện 
trên hệ thông tin đa trị. Phần 4 là kết luận và 
định hướng nghiên cứu tiếp theo 
CÁC KHÁI NIỆM CƠ BẢN 
Hệ thông tin đa trị 
Hệ thông tin đa trị [7], [8] là một bộ bốn 
 , , ,IS U AT V f trong đó U là tập hữu hạn, 
khác rỗng được gọi là tập vũ trụ hoặc tập các 
đối tượng; AT là tập là hữu hạn khác rỗng các 
thuộc tính; f là hàm thông tin, 
: 2 Vf U A là ánh xạ tương ứng mỗi cặp 
(u,a) tới một tập giá trị thuộc V. 
Bài báo quy ước viết tắt , , ,IS U AT V f là 
 ,IS U AT . 
Ký hiệu giá trị của thuộc tính a AT tại đối 
tượng u U là a u , khi đó mỗi tập con 
thuộc tính A AT xác định một quan hệ 
tương đương: 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
104 
 , ,IND A u v U U a A a u a v  
Định nghĩa 2.1.[7]. Quan hệ dung sai trong 
hệ thông tin đa trị 
Cho hệ thông tin đa trị ,IS U AT . Với 
mỗi tập con thuộc tính B AT , quan hệ 
 , , ( )BS u v U U b B u b v b   
 là một quan hệ dung sai và được gọi là quan 
hệ dung sai tương ứng với B. Rõ ràng là 
B AT  : B b
b B
S S
  . 
Đặt   | ( , )
B
BS
u v U u v S thì  
BS
u được 
gọi là một lớp dung sai tương ứng với quan hệ 
SB. Ký hiệu   / |
B
B S
U S u u U biểu diễn 
tập tất cả các lớp dung sai tương ứng với quan 
hệ SB, khi đó / BU S hình thành một phủ của U 
vì các lớp dung sai trong / BU S có thể giao 
nhau và [ ] .
BSu U
u U
 Rõ ràng là nếu C B 
thì    
B CS S
u u với mọi u U . 
Tương tự trong hệ thông tin không đầy đủ [9], 
với hệ thông tin đa trị ,IS U AT , tập thuộc 
tính R AT được gọi là tập thuộc tính tối ưu 
của IS nếu 
R ATS S và , B ATB R S S  , 
điều này tương đương với R ATS u S u 
với mọi u U và B R  tồn tại u U sao 
cho B ATS u S u . 
Hệ quyết định đa trị là hệ thống gồm các 
thành phần  ,DS U AT d  trong đó AT 
là các thuộc tính điều kiện và d là thuộc tính 
quyết định, với giả thiết d u chứa một giá 
trị với mọi u U . 
Với u U , ( ) ( )AT ATu d v v S u được 
gọi là hàm quyết định suy rộng của đối tượng 
u trên tập thuộc tính AT. 
Nếu | ( ) | 1AT u với mọi u U thì DS là 
nhất quán, trái lại DS là không nhất quán. 
Từ A a
a A
S S
  , theo định nghĩa hàm quyết 
định suy rộng ta suy ra AT AT
a AT
u u
   
với mọi u U . 
Nếu B A thì từ A BS u S u ta dễ dàng 
suy ra A Bu u   với mọi u U . 
Tương tự hệ quyết định không đầy đủ [9], 
với hệ quyết định đa trị  ,DS U AT d  , 
tập thuộc tính R AT được gọi là tập thuộc 
tính tối ưu của DS nếu ( ) ( )R ATu u  với 
mọi u U và B R  tồn tại u U sao cho 
 B ATu u  . 
Hệ thông tin đơn trị xếp thứ tự 
Hệ thông tin đơn trị IIS là hệ thống gồm 
các thành phần ( , , , )T U A D F G  với: 
 1 2, ,..., nU x x x là tập hữu hạn khác rỗng 
các đối tượng; A D là tập hữu hạn khác 
rỗng các thuộc tính; 1 2, ,..., pA a a a là tập 
các thuộc tính điều kiện; 1 2, ,..., pD d d d 
là tập các thuộc tính quyết định, và 
A D  ; k k kF f |U V ,k p , f ( x ) là 
giá trị của ak trên kx U, V là miền giá trị 
của ak , ak A; 
  k' k' k'G g |U V , k' p ,g x là giá trị 
của dk’ trên k'x U, V là miền giá trị của 
k'd , k'd D; 
Nếu miền giá trị của một thuộc tính được xếp 
theo ưu tiên tăng dần hoặc giảm dần thì thuộc 
tính đó gọi là một tiêu thức. 
Định nghĩa 2.2. [10] Một hệ thông tin đơn trị 
được gọi là xếp thứ tự ( OIIS ) nếu tất cả các 
thuộc tính điều kiện là các tiêu thức. 
Giả sử rằng một quan hệ xếp thứ tự  a được 
định nghĩa trên miền giá trị của một tiêu thức 
a A; x  a y có nghĩ là x ít nhất tốt bằng y 
đối với tiêu thức a, hay x trội hơn y. Không 
mất tính tổng quát, ta xét thuộc tính điều kiện 
và quyết định có miền giá trị số và theo ưu 
tiên tăng dần, nghĩa là aV R (R là tập số 
thực). Với , ,a A x y U , ta định nghĩa 
( , ) ( , ).x y f x a f y a f 
Với một tập con thuộc tính B  A, ta định 
nghĩa , ,B ax y a B x y  f f có nghĩa là 
x trội hơn y đối với tất cả các thuộc tính trong 
B, ta ký hiệu yxRB
. Do vậy, hệ thông tin đơn 
trị xếp thứ tự theo ưu tiên tăng dần được biểu 
diễn T ( , , , )U A D F G  . 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
105 
Cho T ( , , , )U A D F G  là hệ thông tin 
đơn trị xếp thứ tự, với B  A, ký hiệu: 
 , ( ) ( ),i j l i l j lBR x x U U f x f x a B  (1) 
 , ( ) ( ), (2)i j m i m j mDR x x U U g x g x d D  
 2

BR và 

DR được gọi là quan hệ trội của 
hệ thông tin T . Nếu ta biểu diễn 
  | ,i j j i BBx x U x x R
f
 | ( ) ( ),j l j l i lx U f x f x a B  
  | ,i j j i DDx x U x x R
f
 | ( ) ( ),j ml j m i mx U g x g x d D  
Thì ta thu được các tính chất sau đây của 
quan hệ trội: 
Tính chất 2.1 [10] Cho 
AR là quan hệ trội 
(1) 
AR không phải là quan hệ tương đương, 
vì chúng có tính phản xạ, bắc cầu nhưng 
không đối xứng. 
(2) Nếu B A thì B AR R
  f . 
(3) Nếu B A thì    x x
B A

f f
. 
(4) Nếu  x xj i A 
f
 thì  x xj i AA  
f f
 và 
    x x : x x .i j j iA AA  
ff f
 (5)  x xj i AA 
f f
 nếu và chỉ nếu 
 ( , ) ( , ) .i jf x a f x a a A  
(6)   | ;AT x x U  
f
 tạo thành một bao 
phủ của U. 
Với X U và A  T , xấp xỉ trên và xấp xỉ 
dưới của X đối với quan hệ trội 

AR được định 
nghĩa như sau: 
   ;A AR X x U x X 
ff 
   A AR X x U x X  
ff ; 
Các tập xấp xỉ trên quan hệ trội cũng có một 
số đặc tính tương tự như các tập xấp xỉ trên 
quan hệ tương đương trong lý thuyết tập thô 
truyền thống. 
Khai phá luật xếp thứ tự 
Mục tiêu của bài toán khai phá dữ liệu trên hệ 
thông tin đơn trị xếp thứ tự là tìm kiếm các 
luật xếp thứ tự về mặt ngữ nghĩa trên miền 
giá trị các thuộc tính. 
Trong một OIS, một biểu thức nguyên tố trên 
thuộc tính a được định nghĩa ,a f hoặc 
 ,a p . Với tập thuộc tính BA, một biểu 
thức trên B trong OIS được định nghĩa 
Ba  e(a), với e(a) là một biểu thức nguyên 
tố trên a. Tập các biểu thức trên B trong OIS 
ký hiệu là E(B). Các biểu thức kết nối với 
nhau bởi các toán tử logic như  và , tuy 
nhiên, để đơn giản, ta chỉ dùng . 
Xét các cặp đối tượng trong OIS, tập vũ trụ 
 
 
( , ) |
( , ) | , ,
U U U U x x x U
x y x y U x y
Ký hiệu tập m() bao gồm tất cả các cặp đối 
tượng thỏa mãn biểu thức , ta có: 
m(a,  ) = {(x, y) )( UU  fa(x)  fa(y)} 
m(a, ) = {(x, y) )( UU  fa(x) fa(y)}, 
m(
A 

a
e(a)) = ( ( )).
a A
m e a
 
Một cặp đối tượng x, y thỏa mãn biểu thức , 
viết là ,x y ╞ , nếu thứ tự xác định bởi biểu 
thức  là ,x y . Với tập biểu thức E(A), họ 
 ( ) | ( )m E A   tạo thành một phân 
hoạch của 
 )( UU , ký hiệu là P(A). Mỗi 
cặp đối tượng thỏa mãn một và chỉ một biểu 
thức trong E(A). 
Định nghĩa 2.3. Cho ( , , , )T U A D F G  là 
hệ thông tin đơn trị xếp thứ tự. Xét hai tập 
thuộc tính ,B C A D  . 
Với hai biểu thức E B và  E C , một 
luật xếp thứ tự đọc là “Nếu  thì ”, ký hiệu 
  . Biểu thức  gọi là tiền tố (vế trái) của 
luật, biểu thức  gọi là hậu tố (vế phải) của luật. 
Một luật xếp thứ tự diễn tả thứ tự các đối 
tượng trên tập thuộc tính B xác định thứ tự 
các đối tượng trên tập thuộc tính C . 
Ví dụ, một luật xếp thứ tự: 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
106 
 , , ,a b c f p f . 
được diễn giải 
    yxyxyx cba    . 
Nghĩa là, với hai đối tương x và y tùy ý, nếu x 
xếp trên y đối với thuộc tính a, và x xếp dưới 
y đối với thuộc tính b thì x xếp trên y đối với 
thuộc tính c. 
Định nghĩa 2.4. Độ chính xác và độ bao phủ 
của một luật xếp thứ tự,  , được định 
nghĩa như sau [3], [11]: 
Độ chính xác ( ) = 
m
m
 

 (3) 
Độ bao phủ ( ) = 
m
m
 


 (4) 
Với biểu diễn lực lượng của tập hợp. 
Độ chính xác ( ) là độ đo về sự đúng 
đắn của luật, và độ bao phủ ( ) là độ đo 
về tính ứng dụng của luật. Một luật có độ bao 
phủ cao ngụ ý rằng luật thỏa mãn tiêu thức 
xếp thứ tự của nhiều cặp đối tượng. Độ chính 
xác và độ bao phủ không độc lập với nhau, 
chúng đều liên quan đến số lượng 
)(  m . Một luật có độ bao phủ cao hơn 
có thể có độ chính xác thấp hơn và một luật 
có độ chính xác cao hơn có thể có độ bao phủ 
thấp hơn. 
Để khai phá luật xếp thứ tự từ bảng thông tin 
đơn trị xếp thứ tự, ta sử dụng cách tiếp cận lý 
thuyết tập thô. Từ bảng thông tin đơn trị xếp 
thứ tự, ta xây dựng bảng thông tin nhị phân. 
Trong bảng thông tin nhị phân, ta xét tất cả 
các cặp đối tượng thuộc tích đề các U × U. 
Hàm chuyển được định nghĩa như sau: 
 
 
1,
,
0,
a
a
a
x y
I x y
x y
f
p
 (5) 
Các biểu diễn luật trên bảng thông tin xếp thứ tự 
được chuyển đổi thành các biểu diễn luật trên 
bảng thông tin nhị phân. Ví dụ:  yx a 
được chuyển thành , 1.aI x y Trong quá 
trình chuyển đổi, ta không xét các cặp đối 
tượng (x, x). 
Trong bảng thông tin nhị phân, ta định nghĩa 
một quan hệ tương đương EB đối với tập con 
thuộc tính B A : 
( , ) ( ', ') ( ) ( , ) ( ', ')B a ax y E x y a B I x y I x y  . 
Thuộc tính phân lớp xếp thứ tự o D phân 
hoạch các cặp đối tượng thành hai lớp rời 
nhau Clo và Cl1. Xấp xỉ trên và xấp xỉ dưới 
của Cli 1,2i trên tập thuộc tính B được 
xác định như sau: 
 , , ,i iB Bapr Cl x y x y Cl   
 , , ,i iB Bapr Cl x y x y Cl o   
với ,
B
x y là lớp tương đương chứa ( , )x y 
theo quan hệ tương đương EB. 
Với mỗi lớp tương đương 
B
x,y iapr Cl , 
ta có thể rút ra một luật xếp thứ tự chắc chắn 
như sau: s( , ) s( )iBDe x y De Cl . 
Với s( , )
B
De x y và es( )iD Cl biểu diễn 
mô tả của các lớp tương đương tương ứng. 
Với mỗi thuộc tính xếp thứ tự ,a B ta có thể 
lấy một biểu thức nguyên tố trong 
 s( , ) : ( , )
B
De x y a f nếu , 1aI x y , và 
 ,a p nếu , 0aI x y . Sự kết hợp của các 
biểu thức nguyên tố như vậy s( , )
B
De x y . 
Des(Cli) biểu diễn một trong hai biểu thức 
nguyên tố đối với thứ tự phân lớp: ,o f nếu 
1i và ,a p nếu 0.i 
CHỌN MẪU ĐẠI DIỆN TRÊN HỆ THÔNG 
TIN ĐA TRỊ 
Chọn mẫu đại diện thực chất là bước tiền xử lý 
dữ liệu trước khi thực hiện các thuật toán tìm 
tập thuộc tính tối ưu. Thay vì tìm tập thuộc 
tính tối ưu trên toàn bộ tập đối tượng ban đầu, 
chúng tôi tìm tập thuộc tính tối ưu trên tập đối 
tượng đại diện (chúng tôi gọi là mẫu đại diện) 
và chứng minh bằng lý thuyết tập thuộc tính 
tối ưu thu được từ mẫu đại diện tương đương 
với tập thuộc tính tối ưu thu được từ tập đối 
tượng ban đầu. Vì kích cỡ mẫu đại diện nhỏ 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
107 
hơn nhiều so với kích cỡ tập dữ liệu ban đầu 
nên thời gian thực hiện thuật toán tìm tập thuộc 
tính tối ưu trên mẫu đại diện giảm thiểu đáng 
kể. Mẫu đại diện bao gồm các đối tượng đại 
diện, mỗi đối tượng đại diện được lựa chọn 
như sau: 
Xét hệ thông tin đa trị ,IS U AT , trước hết 
chúng tôi phân hoạch tập đối tượng U ban đầu 
trên tập thuộc tính AT thành các lớp tương 
đương. 
Hai đối tượng ,u v U thuộc cùng một lớp 
tương đương nếu   a aS u S v với mọi 
a AT . 
Với mỗi lớp tương đương, chúng tôi chọn ra 
một đối tượng đại diện cho lớp tương đương 
đó, không mất tính chất tổng quát, chúng tôi 
chọn đối tượng đầu tiên làm đại diện. Tập các 
đối tượng đại diện là mẫu đại diện được chọn. 
Thuật toán chọn mẫu đại diện của hệ thông 
tin đa trị được mô tả như sau: 
Thuật toán 1. Chọn mẫu đại diện của hệ 
thông tin đa trị. 
Đầu vào: Hệ thông tin đa trị ban đầu 
 ,IS U AT với 1,..., nU u u , 
 1,..., mAT a a . 
Đầu ra: Hệ thông tin đa trị mẫu 
 ,P PIS U AT với PU U là một mẫu đại 
diện. 
Bước 1: Đặt 
PU  ; 
Bước 2: Với mỗi , 1..ia AT i m , tính phân 
hoạch     / ii aU a u u U 
với      i ii a aau v U S u S v . 
Bước 3: Tính phân hoạch 
  / ATU AT u u U với 
          1 1
...
m i
m
AT a a ai
u u u u
    . 
Giả sử 1/ ,..., kU AT X X và 
 
1
,...,
li i i
X u u với 1..i k . 
Bước 4: Với mọi /iX U AT , 1..i k , đặt 
 
1
:P P iU U u  ; 
Bước 5: Return ,P PIS U AT ; 
Ví dụ 1. Cho hệ thông tin đa trị như (bảng 1) 
Bảng 1. Hệ thông tin đa trị 
U 
1a 2a 3a 4a 
1u 
{1} { 1} {1} {0} 
2u {0} {0, 1} {1} {0} 
3u {0, 1} {0, 1} {0} {1} 
4u {1} {0, 1} {1} {1} 
5u {0, 1} {0, 1} {1} {1} 
6u {0} {1} {1} {0, 1} 
7u {0, 1} {1} {0} {0, 1} 
8u {0} {1} {1} {0} 
9u {0, 1} {0, 1} {0} {1} 
Ta có: 
   1 11 4 1 3 4 5 7 9, , , , ,a aS u S u u u u u u u , 
     1 1 1 13 5 7 9a a a aS u S u S u S u U , 
    
 
1 1 1
2 6 8
2 3 5 6 7 8 9, , , , , ,
a a a
S u S u S u
u u u u u u u
Do đó: 
     1 1 4 2 6 8 3 5 7 9/ , , , , , , , ,U a u u u u u u u u u 
Tính toán tương tự, ta có 2/U a U , 
    3 1 2 4 5 6 8 3 7 9/ , , , , , , , ,U a u u u u u u u u u , 
     4 1 2 8 3 4 5 9 6 7/ , , , , , , , ,U a u u u u u u u u u 
Từ đó ta có 
    
   
1 2 8 3 9 4
5 6 7
, , , , , ,
/
, ,
u u u u u u
U AT
u u u
  
 
 
Tập đối tượng đại diện được chọn là 
 1 2 3 4 5 6 7, , , , , ,PU u u u u u u u và hệ thông tin đa trị 
đại diện ,P PIS U AT được chọn ở Bảng 2. 
Đánh giá độ phức tạp thuật toán: 
Giả sử k là số thuộc tính điều kiện, n là số đối 
tượng. Xét Bước 2, với mỗi 1ia A,i ..m , 
độ phức tạp  ,iaS u u U là O( n )
2 , độ 
phức tạp để tính phân hoạch / iU a là 
O( nlog n ) . Do đó, độ phức tạp của Bước 2 là 
O( kn )2 . Độ phức tạp của Bước 3 khi bước 2 
đã được tính là O( n ) . Độ phức tạp của bước 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
108 
 4 là O( nlog n ) . Do đó, độ phức tạp của 
Thuật toán là O( kn )2 . 
Bảng 2. Hệ thông tin đa trị mẫu từ Bảng 1 
U 
1a 2a 3a 4a 
1u 
{1} { 1} {1} {0} 
2u 
{0} {0, 1} {1} {0} 
3u 
{0, 1} {0, 1} {0} {1} 
4u 
{1} {0, 1} {1} {1} 
5u 
{0, 1} {0, 1} {1} {1} 
6u 
{0} {1} {1} {0, 1} 
7u 
{0, 1} {1} {0} {0, 1} 
Thực nghiệm minh họa thuật toán 
Môi trường thực nghiệm là máy tính PC với 
cấu hình Pentium dual core 2.13 GHz CPU, 
1GB bộ nhớ RAM, sử dụng hệ điều hành 
Windows XP Professional. Việc thực nghiệm 
Thuật toán 1 được thực hiện trên bộ số liệu 
tập giá trị được chuyển đổi từ bộ số liệu trong 
kho dữ liệu [12]. Với mỗi bộ số liệu, giả sử 
U là số đối tượng, A là số thuộc tính điều 
kiện. Các thuộc tính điều kiện được đánh số 
thứ tự từ 1 đến A . 
Cho hệ thông tin đa trị ban đầu 
 ,IS U AT và hệ thông tin đa trị mẫu 
 ,P PIS U AT , trước hết bài báo chứng 
minh bổ đề sau: 
Bổ đề 1. Nếu pu U là một đối tượng đại 
diện được chọn trên ,IS U AT sao cho 
 B p AT pS u S u với B AT thì ta cũng 
có B p AT pS u S u trên ,P PIS U AT 
với p pu U . 
Chứng minh. Trên ,IS U AT , giả sử 
 AT p p
AT
S u u X  , khi đó với mọi 
p
AT
u u ta đều có AT AT pS u S u . 
Từ B p AT pS u S u suy ra 
 B p AT pS u S u Y  . Xét đối tượng bất kỳ 
y Y , vì AT py S u nên ATy S u với 
mọi p
AT
u u , do đó ATS y không chứa u 
với mọi p
AT
u u , nghĩa là trên 
 ,P PIS U AT , AT pS y không chứa pu 
với py là đối tượng đại diện của lớp tương 
đương chứa y trên ,IS U AT (i). 
Mặt khác, từ giả thiết 
 AT p p
AT
S u u X  , với x X thì 
 ATx S u với mọi p ATu u , hay ATS x 
chứa u với mọi p
AT
u u . Với đối tượng y 
được xét ở trên rõ ràng p
AT
y u , giả sử 
 
AT
y x với x X khi đó AT ATS y S x 
và ATS y chứa u với mọi p ATu u , nghĩa 
là trên ,P PIS U AT , AT pS y chứa pu 
với py là đối tượng đại diện của lớp tương 
đương chứa y, điều này mâu thuẫn với (i). Do 
đó  
AT
y x với mọi x X . 
Với giả thiết AT p p
AT
S u u X  thì trên 
 ,P PIS U AT , AT p p pS u u X  với 
pX là tập các đối tượng đại diện của các đối 
tượng thuộc X. Với giả thiết 
 B p AT pS u S u Y  và kết quả chứng 
minh y Y ,  
AT
y x với mọi x X thì trên 
 ,P PIS U AT , B p p p pS u u X Y   
với p py Y và py là đối tượng đại diện của 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
109 
y Y . Do đó ta kết luận trên ,P PIS U AT , 
 B p AT pS u S u , (đpcm) 
Từ kết quả của Bổ đề 1, tác giả chứng minh 
rằng tập thuộc tính tối ưu của hệ thông tin đa 
trị ban đầu và tập thuộc tính tối ưu của hệ 
thông tin đa trị mẫu là như nhau. 
Giả sử R AT là tập thuộc tính tối ưu của hệ 
thông tin đa trị ban đầu ,IS U AT , khi đó 
 R ATS u S u với mọi u U và B R  
tồn tại u U sao cho B ATS u S u . 
a) Từ R ATS u S u với mọi u U trên 
 ,IS U AT dễ dàng suy ra 
 R p AT pS u S u với mọi p Pu U trên 
 ,P PIS U AT . 
b) Không mất tính tổng quát, giả sử B R và 
tồn tại u U sao cho B ATS u S u trên 
 ,IS U AT 
Nếu u là đối tượng đại diện được chọn thì 
pu u và B ATS u S u trên ,IS U AT , 
theo Bổ đề 1 thì B p AT pS u S u trên 
 ,P PIS U AT (i). 
Nếu u không phải đối tượng đại diện thì trên 
 ,IS U AT , giả sử pu là đối tượng đại diện 
của lớp tương đương p
AT
u chứa u và pu , 
khi đó  p ATATu u . Do B R AT  nên 
từ  p ATATu u
 ta cũng suy ra  p BBu u
 . 
Từ  p ATATu u ta có    iip aa
u u 
với mọi 
ia AT , theo cách xây dựng phân 
hoạch ta có   i ipa aS u S u với mọi 
ia AT , do đó 
   
1 1i i
m m
AT p p ATa a
i i
S u S u S u S u
   . 
Từ  p BBu u , bằng cách tương tự ta suy 
ra B p BS u S u . Theo giả thiết, 
 B ATS u S u nên ta thu được 
 B p AT pS u S u trên ,IS U AT , theo 
Bổ đề 1 thì ta cũng có B p AT pS u S u trên 
 ,P PIS U AT (ii) 
Như vậy, cả hai trường hợp (i) và (ii) ta đều 
có B p AT pS u S u trên ,P PIS U AT , từ 
đó kết luận tồn tại B R sao cho 
 B p AT pS u S u . Từ a) và b) theo định 
nghĩa ta có R AT là một tập thuộc tính tối 
ưu của hệ thông tin đa trị mẫu 
 ,P PIS U AT . 
KẾT LUẬN 
Bài báo đã đề xuất thuật toán chọn mẫu đại 
diện trong hệ thông tin đa trị sử dụng lý 
thuyết tập thô. Đồng thời bài báo trình bày 
khai phá các luật xếp thứ tự bằng phương 
pháp chuyển đổi hệ thông tin đơn trị xếp thứ 
tự thành hệ thông tin nhị phân, từ đó áp dụng 
các kỹ thuật khai phá luật sử dụng lý thuyết 
tập thô truyền thống. Định hướng nghiên cứu 
tiếp theo là đề xuất các phương pháp tìm tập 
thuộc tính tối ưu hiệu quả trên hệ quyết định 
đa trị. 
TÀI LIỆU THAM KHẢO 
1. Pawlak Z., Rough sets, International Journal of 
Information and Computer Sciences, 11(5), 1982, 
pp. 341-356. 
2. Pawlak Z., Rough sets: Theoretical Aspects of 
Reasoning About Data, Kluwer Aca-demic 
Publishers, 1991. 
3. S. Tsumoto, Modelling medical diagnostic rules 
based on rough sets, Rough Sets and Current 
Trends in Computing, Lecture Notes in Artificial 
Intelligence, 1424, Springer-Verlag, Berlin, pp. 
475-482, 1998. 
4. Lang G. M., Lia Q. G., Data compression of 
dynamic set-valued information systems, CoRR 
abs/1209.6509, 2012. 
5. Wang C. Z., Chen D. G., Wuc C., Hu Q. H., 
Data compression with homomorphism in 
covering information systems, International 
Journal of Approximate Reasoning 52, 2011, pp. 
519–525. 
6. Wang C. Z., Wua C. X., Chenb D. G., Duc W. 
J., Some properties of relation information 
Phùng Thị Thu Hiền Tạp chí KHOA HỌC & CÔNG NGHỆ 185(09): 103 - 110 
110 
systems under homomorphisms, Applied 
Mathematics Letters 21, 2008, pp. 940–945. 
7. Guan Y. Y., Wang H. K, Set-valued information 
systems, Information Sciences 176, 2006, pp. 
2507–2525. 
8. Qian Y. H., Dang C. Y., Liang J. Y., Tang D. 
W., Set-valued ordered information systems, 
Information Sciences 179, 2009, pp. 2809-2832. 
9. Kryszkiewicz M., Rough set approach to 
incomplete information systems, Information 
Science, Vol. 112, 1998, pp. 39-49. 
10. W.X. Zhang, W.Z. Wu, J.Y. Liang, D.Y.Li, 
Theory Method of Rough sets, Science Press, 
Beijing, 2001. 
11. Y.Y. Yao, N. Zhong, An analysis of quantita-
tive measures associated with rules, Proceedings 
of PAKDD’99, 479-488, 1999 
12. The UCI machine learning repository, 
SUMMARY 
DATA MINING ON SET- VALUED INFORMATION SYSTEMS 
Phung Thi Thu Hien
*
 University of Economic and Technical Industries 
Based on the idea of minimizing the original data set, in this paper, we propose a method of 
selecting representative object set from initial object set to the solve optimal set of attributes 
problem in set-valued information systems. We demonstrate that the optimal set of attributes on 
the original objects and the optimal set of attributes on the representative one are equivalent, 
therefore we confirm the correctness of the method. Because the representative sample size is 
smaller than the original object’s size, the execution time of algorithms for finding the optimal 
attribute set on the representative sample is significantly reduced. Representative sample size is 
large or small depending on the specificity of each real-time information system. At the same time, 
the article presents the method of exploring ordinal law by converting ordinal monopole 
information system into binary monopole information system and applying the law biotechnology 
technique in the systematic set theory based on the binary monotherapy obtained. 
Keywords: Set-valued information system, rough set, the optimal set of attributes, tolerance 
relation. 
Ngày nhận bài: 30/7/2018; Ngày phản biện: 5/8/2018; Ngày duyệt đăng: 16/9/2018 
*
 Tel: 0914 770070, Email: Thuhiencn1@gmail.com