Xem mẫu
- Kỷ
K yếu Hội nghị KHCN Quốc giaa lần thứ XII về Nghiên cứu cơ bản
b và ứng dụng
g Công nghệ thôông tin (FAIR); H
Huế, ngày 07-08/6/2019
DOI:
D 10.15625//vap.2019.00068
VỀ MỘ
ỘT VẤN Đ
ĐỀ TƯƠ
ƠNG ĐƯƠ
ƠNG LIÊN
N QUAN ĐẾN TẬ
ẬP RÚT GỌN
G
TR
RONG BẢ
ẢNG QUYYẾT ĐỊNH
H
Vũ
V Đức Thi
Đại họcc quốc gia Hà nội
Email: vdthi@vnu.ed
v du.vn
TÓM
T TẮT: Hướ ớng khai phá dữ
ữ liệu xử dụng llí thuyết tập thô
ô đã được nhiều
u tác giả trên thhế giới nghiên ccứu và phát triển ứng dụng,
đã
đ đạt được nhiều kết quả khả quan, đặc biệt nnghiên cứu về các
c tập rút gọn trong bảng quyyết định.
Các
C tập rút gọn trong bảng quyyết định đã đượ ợc ứng dụng nh hiều trong thực tiễn. Bài báo n ày liên quan chhặt chẽ đến các tập rút gọn
trrong bảng quyếết định nhất quáán. Trong bài bbáo này, tác giả
ả nghiên cứu phhát triển những đặc trưng tổ hợ ợp của các tập rút gọn. Hệ
Sperner
S là một hệ
h tổ hợp đã đư ược nhiều nhà kkhoa học nghiên cứu và phát triển.
t Tác giả chhứng minh về vvấn đề tương đưương của họ
các
c tập rút gọn trong bảng quyyết định nhất quuán với hệ Sperrner. Trên cơ sở s này, chúng tta thu được cácc kết quả liên quuan đến các
đặc
đ trưng tổ hợpp của các tập rúút gọn.
Keywords:
K Sperrner system, redduct set, consisttent decision tab
ble.
Việc tìm
m kiếm các tậập rút gọn đónng vai trò quan n trọng trong việc xử lí thônng tin trên bảảng quyết định
h. Mục tiêu
của
c rút gọn thuuộc tính là loạại bỏ các thuộcc tính dư thừaa để tìm ra các thuộc tính cơơ bản phục vụ cho việc xử lí thông tin.
Về
V thực chất, việc
v rút gọn thhuộc tính là tììm tập con nhỏ nhất của tập p các thuộc tínnh để bảo toànn thông tin phân lớp trên
bảng
b quyết địnnh. Trong bài báo này, chúúng tôi chỉ đề cập tới các bảng
b quyết địnnh nhất quán. Trên thực tiễn, tùy theo
từ
ừng bài toán cụ
c thể, chúng ta có thể chuyyển bảng quyếết định không nhất quán vềề bảng quyết đđịnh nhất quán n. Mục tiêu
chính
c b này là trìnnh bày một kếết quả về tính tương đương
của bài báo g của họ các tậập rút gọn tronng bảng quyết định nhất
quán
q với hệ Spperner. Từ đó,, chúng ta nhậận được một số ố kết quả liên quan đến các đặc trưng tổ hhợp của các tậ ập rút gọn.
1. NHỮNG KHÁI
K NIỆM CƠ BẢN
Phần nàày cung cấp m
một số khái niệệm cơ bản đượ
ợc dùng trong
g bài báo. Các khái niệm nàyy có thể xem trong [1, 3,
4,
4 6].
Định nghĩa
n 1.1. Hệ thông tin là m
một bộ bốn S = ( U, A, V,, f ) trong đóó U là tập hữuu hạn, khác rỗ
ỗng các đối
ượng; A là tậập hữu hạn, khác rỗng cáác thuộc tính; V
tư V
a A
a với Va làà tập giá trị ccủa thuộc tính a A ;
f : U A Va là hàm thhông tin, a A, u U f u, a Va .
Với mọọi u U , a A , ta ký hhiệu giá trị th
huộc tính a tại đối tượng u là a u thay vì f u , a . Nếu
B b1 , b2 ,...., bk A làà một tập conn các thuộc tính thì ta ký hiệệu bộ các giá ttrị bi u bởi B u . Như vậy, nếu u
và
v v là hai đối tượng, thì ta vviết B u B v nếu bi u bi v với mọi i 1,..., k .
Định nghĩa
n 1.2. Bảnng quyết địnhh là một hệ thô
ông tin S = (U
U, A, V, f) vớới A= C D và C D . Bảng
quyết
q định S được
đ gọi là nhhất quán nếu D phụ thuộc hàm
h vào C, tứ
ức là với mọi u, v U , C u C v kéo theo
D u D v . Ngược lại tthì gọi là không
ng nhất quán haay mâu thuẫn. C được gọi là tậập thuộc tính đi
điều kiện và D là tập thuộc
tíính quyết định
Thông thường
t D = {d}} chứa một thuuộc tính
Định nghĩa
n D U, C D,V , f và tậpp thuộc tính
1.3. Choo bảng quyết địnnh nhất quán DS R C . R đượcc gọi là tập
rút
r gọn nếu:
- với mọi
m cặp đối tượ
ợng u, v thì R
R(u) = R(v) kéo
o theo D(u) = D(v)
m E là tập conn thực sự của R thì tồn tại cặp u, v để E(u) = E(v) không kééo theo D(u) = D(v)
- với mọi
- Vũ Đức Thi 535
Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu PRED C là họ tất cả các tập rút gọn
của C.
Cho R a1 ,..., an là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính ai có miền giá trị là D ai .
Quan hệ r trên R là tập các bộ h1 ,..., hm với h j : R D ai ,1 j m là một hàm sao cho
ai R
h j ai D ai .
Cho r h1 ,..., hm là một quan hệ trên tập thuộc tính R a1 ,..., an . Phụ thuộc hàm (PTH) trên R là một
dãy ký tự có dạng A B với A, B R. PTH A B thỏa mãn quan hệ r trên R nếu
h , h r a A h a h a b B h b h b . Đặt
i j i j i j Fr A, B : A, B R, A B là
họ đầy đủ các PTH thỏa mãn quan hệ r. Ký hiệu P R là tập các tập con của R. Cho F P R P R . Ta nói
rằng F là một họ f trên R nếu với mọi A, B, C , D R
1 A, A F .
2 A, B F , B, C F A, C F .
3 A, B F , A C , D B C , D F .
4 A, B F , C , D F A C , B D F .
Rõ ràng là Fr là một họ f trên R. Nếu F là một họ f trên R thì có một quan hệ r trên R sao cho Fr = F. Ký hiệu
F là tập tất cả các PTH được dẫn xuất từ F bằng việc áp dụng các quy tắc 1 4 .
Sơ đồ quan hệ (SĐQH) s là một cặp R, F với R là tập thuộc tính và F là tập các phụ thuộc hàm trên R. Ký
hiệu A a : A a F
, A
được gọi là bao đóng của A trên s. Dễ thấy A B F
khi và chỉ khi B A
. Tương tự ký hiệu Ar a : A a F
, A
r
được gọi là bao đóng của A trên quan hệ r.
Cho s R, F là SĐQH trên R, a R . Đặt
as A R: A a , B: B a B A . Khi đó, as
được gọi là họ các tập tối thiểu của thuộc tính a trên s. Tương tự, cho r là một quan hệ trên R và a R . Đặt
ar A R : A a , B : B a B A . Khi đó, r
a được gọi là họ các tập tối thiểu của thuộc
tính a trên r.
Gọi P R là một hệ Sperner trên R nếu với mọi A, B kéo theo A B . Dễ thấy Kas, Kar là các
hệ Sperner trên R. Với tập là một hệ Sperner trên R, ta định nghĩa tập 1 như sau:
1 A R : B B A và nếu A C B B C
Dễ thấy 1 cũng là một hệ Sperner trên R. Nếu là một hệ Sperner trên R đóng vai trò là tập các khóa tối
1
thiểu của quan hệ r (hoặc SĐQH s) thì là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là tập
các phản khóa. Nếu là một hệ Sperner trên R đóng vai trò là họ các tập tối thiểu của thuộc tính a trên r (hoặc trên
ar (hoặc as ), thì 1 ar (hoặc 1 as ) là họ tất cả các tập lớn nhất không
1 1
s), hay
phải là tập tối thiểu của thuộc tính a, được định nghĩa như sau [1] :
A R : A a F , A B B a F ,
1
r
a r r
A R : A a F , A B B a F .
1
s
a
- 536 VỀ MỘT VẤN ĐỀ TƯƠNG DƯƠNG LIÊN QUAN ĐẾN TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH
Chúng ta có thể thấy khái niệm tập tối thiểu của thuộc tính trên quan hệ r tương đương khái niệm tập rút gọn trong bảng
quyết định nhất quán.
2. KẾT QUẢ
Trong phần này, chúng tôi trình bày các kết quả của bài báo. Đầu tiên, chúng tôi trình bày một bổ đề cần thiết sau.
Bổ đề 2.1. [5] Cho bảng quyết định nhất quán DS U , C d , V , f với C c1 , c2 ,..., cn ,
U u1 , u2 ,..., um .
Xét quan hệ r u1 , u2 ,..., um trên tập thuộc tính R C d .
Đặt
r Eij :1 i j m với Eij a R : a ui a u j
Đặt
d A r : d A, B r : d B, A B .
d dr
1
Thì . Ở đây dr là họ các tập tối thiểu của thuộc tính d trên quan hệ r
Định lí 2.2. [2] Cho trước bảng quyết định DS = (U, C {d}, V, f) thì (Kdr) -1 là hệ Sperner trên C. Ngược lại
nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán DS = (U, C {d}, V, f) để K= (Kdr) -1
Trên cơ sở Định lí 2.2, nếu K là hệ Sperner trên C. Giả sử K = { A1,…,Am }. Chúng ta xây dựng bảng quyết
định DS = ( U, C {d}, V, f) như sau:
U = {u0, u1,…, um} với mọi c C : c(u0) = 0 và d(u0) = 0. Với mọi i, i = 1,… m và c là phần tử của C. Chúng
ta đặt c(ui) = 0 nếu c Ai. Ngược lại c(ui) = i. Đặt d(ui) = i. Với R = C {d}.
Có thể thấy K= (Kdr) -1 .
Sau đây, chúng tôi đưa ra một thuật toán từ một hệ Sperner bất kỳ tìm tập phản khóa của nó.
Thuật toán 2.3 [8] (Tìm tập phản khóa)
Vào: = ,…, là hệ Sperner trên R.
Ra:
Bước 1: Ta đặt = − : ∈ . Hiển nhiên = .
Bước q+1: (q < m). Ta giả thiết rằng = ∪ ,…, , ở đây ,…, chứa và =
∈ ∶ ⊈ . Đối với mỗi i (i = 1, ..., ) ta tìm các phản khóa của trên tương tự như . Kí pháp
chúng là , … , . Đặt = ∪ ∶ ∈ é ℎ ⊄ , 1 ≤ ≤ . 1 ≤ ≤ . Cuối cùng ta đặt
=
Định lý 2.4 [8]
Với mọi q (1 ≤ ≤ ), = ,…, có nghĩa là = .
Rõ ràng, K và là xác định duy nhất lẫn nhau và từ định nghĩa của có thể thấy thuật toán của chúng ta
không phụ thuộc vào thứ tự của dãy , … , . Đặt = ∪ ,…, và (1 ≤ ≤ − 1) là số các phần tử
.
Trên cơ sở này ta có:
Mệnh đề 2.5.
Độ phức tạp thời gian tồi nhất của Thuật toán 2.3 là Θ(| | ∑ . ).
− , nếu >
Ở đây: =
1 , ế =
- Vũ Đức Thi 537
Rõ ràng trong mỗi bước thuật toán ta có là hệ Sperner trên R. Ta biết rằng ([8]) kích thước của hệ Sperner
[ / ] [ / ]
bất kỳ trên R không vượt quá , ở đây n = | |. Có thể thấy xấp xỉ bằng 2 / /( . / ). Từ đó độ phức tạp
thời gian tồi nhất của thuật toán trên không nhiều hơn hàm số mũ theo n. Trong trường hợp mà ≤ (q= 1, ..., m-1),
| | | | |
dễ thấy rằng độ phức tạp thuật toán không lớn hơn Θ(| ). Như vậy, trong các trường hợp này độ phức tạp
của Thuật toán 2.3 tìm là đa thức theo | |, | |, à | |. Có thể thấy nếu số lượng các phần tử của K là nhỏ thì
Thuật toán 2.3 rất hiệu quả, nó chỉ đòi hỏi thời gian đa thức theo | |.
Dựa trên các kết quả đã trình bày ở trên, chúng tôi trình bày kết quả về sự tương đương giữa các họ tất cả các
tập rút gọn của một bảng quyết định nhất quán bất kỳ với các hệ Sperner.
Định lí 2.6. Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) thì PRED C (họ tất cả các tập
rút gọn của C) là hệ Sperner trên C. Ngược lại nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán
DS = (U, C ∪ {d}, V, f) để K= PRED (C).
Chứng minh: Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f). Có thể thấy, theo định nghĩa của
tập rút gọn, họ PRED (C) là hệ Sperner trên C.
Giả sử K = { A1,…,An } là một hệ Sperner trên C. Trên cơ sở thuật toán 2.3, từ K chúng ta xây dựng tập phản
khóa K-1 . Giả sử K-1 = { B1,...,Bm}. Chúng ta xây dựng bảng quyết định nhất quán DS = ( U, C∪{d}, V, f) như sau:
U = {u0, u1,…, um} với mọi c ∈ C : c(u0) = 0 và d(u0) = 0. Với mọi i, i = 1,…m và c là phần tử của C. Chúng ta
đặt c(ui) = 0 nếu c ∈ Bi. Ngược lại c(ui) = i. Đặt d(ui) = i. Với R = C ∪ {d}.
Trên cơ sở Bổ đề 2.1 và Định lí 2.2, chúng ta có K-1= (Kdr) -1 . Trên cơ sở này và dựa trên định nghĩa của hệ
Sperner, tập phản khóa và định nghĩa các tập rút gọn của bảng quyết định nhất quán, chúng ta có K = PRED (C). Kết
quả đã được chứng minh xong.
Trên cơ sở kết quả này, chúng ta có thể thấy ngay việc nghiên cứu họ tất cả các tập rút gọn của bảng quyết định
nhất quán DS = (U, C ∪ {d}, V, f) chính là nghiên cứu các hệ Sperner trên C. Hệ Sperner là hệ tổ hợp đã được nhiều
nhà khoa học trong lí thuyết tổ hợp trên thế giới nghiên cứu. Như vậy, nhiều đặc trưng tổ hợp của tập rút gọn sẽ được
sáng tỏ.
Trên cơ sở của Định lí 2.6 và Mệnh đề 2.5, chúng ta có ngay hệ quả sau:
Hệ quả 2.7. Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) thì PRED C (họ tất cả các tập
[ / ]
rút gọn của C) có lực lượng không vượt quá , ở đây n = |C|.
LỜI CẢM ƠN: Chúng tôi xin cảm ơn sự tài trợ của Đề tài “Nghiên cứu thiết kế xây dựng thiết bị tường lửa
chuyên dụng tích hợp kỹ thuật mật mã của ngành Cơ yếu” mã số 01/2018/ KCM.
TÀI LIỆU THAM KHẢO
[1] Demetrovics J., Thi V. D., Quang H. M., Anh N. V. (2018). An Method to reduc the size of consistent decision
tables. Acta Cybernetica V 23, pp. 1039- 1054
[2] Demetrovics J., Thi V. D., Duong T. H., Giang N. L. (2015). On the time complexity of the problem related to
reduct of consistent decision tables. SERDICA J. of computing. Bugarian Academy of Sciences V 9, N 2, pp. 101-
110
[3] Demetrovics J. and Thi V. D. (1995), “Some remarks on generating Armstrong and inferring functional
dependencies relation”, Acta Cybernetica 12, pp. 167-180.
[4] Nguyen Long Giang, Vu Duc Thi (2011), “Some Problems Concerning Condition Attributes and Reducts in
Decision Tables”, Proceeding of the Fifth National Symposium “Fundamental and Applied Information
Technology Research” (FAIR), Bien Hoa, Dong Nai, pp. 142-152.
[5] Nguyễn Long Giang, Vũ Đức Thi (2011), “Thuật toán tìm tất cả các rút gọn trong bảng quyết định”, Tạp chí Tin học và
Điều khiển học, T.27, S.3, tr. 199-205.
[6] Pawlak Z. (1991), “Rough sets: Theoretical Aspects of Reasoning About Data”, Kluwer Academic Publishers.
[7] Vũ Đức Thi (2018), “ Một vấn đề thuật toán liên quan đến tập rút gọn trong bảng quyết định nhất quán “. Kỷ yếu
hội nghị quốc gia về “ Nghiên cứu cơ bản và ứng dụng công nghệ thông tin” lần thứ XI, Hà Nội, tr. 150-157.
[8] Vu Duc Thi (1986), “ Minimal keys and antikeys “ Acta Cybernetica 7, 4, pp 361-371
- 538 VỀ MỘT VẤN ĐỀ TƯƠNG DƯƠNG LIÊN QUAN ĐẾN TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH
ON AN EQUIVALENCE PROBLEM RELATED TO THE REDUCT SET IN THE DECISION TABLE
Vu Duc Thi
ABSTRACT: The data mining using the theory of rough set was more of the authors in the world of research and development
applications, has achieved many positive results, particularly the study of reduction in the decision table. The reduct sets in
decision tables have been applied in practice. This paper is closely related to the reductions in the consistent decision table. In this
paper, the author of the study develops the combinational characteristics of reduct sets. The Sperner system is a combinational
system that has been researched and developed by many scientists. We show that the equivalence problem of reductions in the
consistent decision table with the Sperner system. On this basis, we obtain results concerning the combinational characteristics of
reduct sets.
Keywords: Sperner system, reduct set, consistent decision table.
nguon tai.lieu . vn
