- Trang Chủ
- Cơ sở dữ liệu
- Phụ thuộc hàm trong hệ thống thông tin và các tính chất của xấp xỉ trên dựa vào hàm đóng
Xem mẫu
- ISSN 2354-0575
PHỤ THUỘC HÀM TRONG HỆ THỐNG THÔNG TIN
VÀ CÁC TÍNH CHẤT CỦA XẤP XỈ TRÊN DỰA VÀO HÀM ĐÓNG
Trịnh Thị Nhị, Nguyễn Bá Tường
Trường Đại học Sư phạm Kỹ thuật Hưng Yên
Ngày nhận: 11/5/2016
Ngày sửa chữa: 03/6/2016
Ngày xét duyệt: 20/6/2016
Tóm tắt:
Trong bài này chúng tôi trình bày một số tính chất của sự phụ thuộc của thuộc tính trong một hệ
thống thông tin. Chúng tôi đã đề xuất lập biểu đồ đóng và từ đó chỉ ra một số tính chất và công thức xấp xỉ
trên cho một hệ thống thông tin.
Đồng thời, trong bài viết này chúng tôi đã chỉ ra được hệ thống thông tin đơn trị và hệ thống thông
tin đa trị xác định.
Từ khóa: Phụ thuộc hàm, hệ thống thông tin, xấp xỉ trên, hàm đóng, hệ quyết định.
Mở đầu Quan hệ IND (B) 3 U # U được gọi là quan
Trong [15, 16] chúng ta đã biết rằng, mỗi hệ bất khả phân biệt trên U nếu với mọi cặp đối
quan hệ là một hệ thống thông tin theo định nghĩa tượng u, u’ 3 U thì uIND(B)u’ khi và chỉ khi a(u)
của Z.Pawlak [2]. Tuy nhiên, mỗi hệ thống thông tin = a(u’) với mọi a ! B.
trong [2] có thể không là quan hệ như trong [15, 16]. Dễ dàng thấy rằng quan hệ IND(B) là quan hệ
Vì vậy khái niệm phụ thuộc hàm được định tương đương trên U. Phân hoạch U / IND (B) = U / B
nghĩa như trong [15, 16] nói chung không thể dùng là phân hoạch tương đương.
trong hệ thống thông tin. Trong bài này, chúng tôi Chú ý: Chúng ta sẽ ký hiệu U/B là phân
trình bày khái nịệm phụ thuộc hàm dựa vào quan hoạch của U/IND(B) và U/B = {[o]B: o ! U} là các
hệ bất khả phân biệt. Từ định nghĩa phụ thuộc hàm, nhóm tương đương. Với [o]B là nhóm các đối tương
chúng tôi nêu một số tính chất liên quan. Trong bài quan hệ với nhau.
viết chúng tôi cũng nêu định nghĩa hàm đóng và
từ tính chất hàm đóng, chúng tôi có đẳng thức kép Định nghĩa 3. Xấp xỉ của tập hợp
giữa các tập xấp xỉ trên và một số tính chất của xấp Cho hệ thống thông tin đơn trị S = (U, A); B
xỉ trên. 3 A; X 3 U.
Xấp xỉ dưới của X, ứng với phân hoạch U/B,
1. Một số khái niệm cơ bản ký hiệu XB và XB = , { [o]B: o ! U và [o] 3 X}.
Định nghĩa 1. Hệ thống thông tin Xấp xỉ trên của X, ứng với phân hoạch U/B,
Hệ thống thông tin (information system) là ký hiệu XB và XB = , { [o]B: o ! U và [o]B + X ≠ z }.
S = (U, A); trong đó U là tập hữu hạn khác rỗng các
đối tượng; A là tập hữu hạn khác rỗng các thuộc Định nghĩa 4. Hệ quyết định
tính. Mỗi thuộc tính a ! A, Va là tập giá trị của a và Hệ quyết định là hệ thống thông tin S mà
u ! U, a(u) là giá trị của u tại thuộc tính a. trong tập thuộc tính A có tập thuộc tính quyết định D.
Chú ý: Nếu 6a ! A, 6u ! U a(u) chỉ có Vậy hệ quyết định T = (U, A); trong đó
một giá trị thì S = (U, A) là hệ tin đơn trị, ngược A = C , D; C + D ! z . Tập C được gọi là tập
lại S = (U, A) gọi là hệ tin đa trị hay hệ tin giá trị thuộc tính điều kiện, D là thuộc tính quyết định.
tập (set-value information system). Trong bài viết Ví dụ:
này chúng tôi chỉ xét các hệ thống thông tin xác Bảng 1. Hệ quyết định đơn trị
định đầy đủ, nghĩa là các hệ thống thông tin mà mọi U Mã Thân Ho Sốt Ho có Kết
thuộc tính luôn có giá trị (tập giá trị) xác định. Bệnh nhiệt đờm luận
Ví dụ, Bảng 1 là hệ thống thông tin đơn trị, nhân
Bảng 2 là hệ thống thông tin đa trị. u1 1 40 Nhiều Cao Không Viêm
họng
Định nghĩa 2. Quan hệ bất khả phân biệt
u2 2 37 Ít Thấp Không Bình
Cho hệ thống thông tin đơn trị S = (U, A), thường
B 3 A.
Khoa học & Công nghệ - Số 10/Tháng 6 - 2016 Journal of Science and Technology 69
- ISSN 2354-0575
u3 3 40 Nhiều Cao Không Viêm 2.2. Tính mở rộng hai vế:
họng Nếu B → B’ thì BC → B’C
2.3. Tính bắc cầu:
u4 4 41 Nhiều Cao Có Viêm
phổi Nếu B → B’ và B’ → C thì B → C
cấp 2.4. Tính tựa bắc cầu:
Nếu B → B’ và B’C → C’ thì BC → C’
u5 5 38 Không Thấp Không Bình
thường 2.5. Tính mở rộng trái thu hẹp phải:
Nếu B → B’ thì BC → B’ \ C’
u6 6 38 Không Thấp Không Bình 2.6. Tính cộng đầy đủ:
thường
Nếu B → C và B’ → C’ thì BC → B’C’
u7 7 38 Không Thấp Không Bình 2.7. Tính tích lũy:
thường Nếu B → C và C → B’C’ thì B → BB’C’
Chú ý: Trong Cơ sở dữ liệu, BC là hợp của hai tập B
Bảng 2. Hệ quyết định đa trị và C hay BC = B , C.
U Mã Học Học vị Chuyên Ngoại Kết
NV Hàm ngành ngữ luận Định nghĩa 6. Hàm đóng
u1 1 PGS TS Cơ khí {Anh, Giảng Cho U là tập bất kỳ, P(U) là họ các tập con
Pháp} viên của U.
cao Hàm f: P(U) → P(U) là hàm đóng nếu f thỏa
cấp mãn 3 điều kiện sau:
u2 2 PGS TS CNTT {Nga, Giảng (1) Tính phản xạ: 6 X ! P(U) X 3 f(X)
Anh, viên (2) Tính đồng biến: 6 X, Y ! P(U) nếu X 3 Y thì
Pháp} cao f(X) 3 f(Y)
cấp (3) Tính lũy đẳng; 6 X ! P(U) f(f(X)) = f(X)
u3 3 GS TS Cơ khí {Nga} Giảng
viên 3. Một số tính chất của hàm đóng
cao 3.1. Hàm đóng của hợp các tập chứa hợp của các
cấp hàm đóng
u4 4 GS TSKH Điện tử {Nga, Giảng 6 X, Y ! P(U) f(XY) 4 f(X)f(Y).
Anh} viên 3.2. Hàm đóng của giao hai tập được chứa trong
cao giao các hàm đóng của hai tập đó
cấp 6 X, Y ! P(U) f(X + Y) 3 f(X) + f(Y)
u5 5 PGS TS Điện tử {Anh, Giảng 3.3. Đẳng thức
Pháp} viên 6 X, Y ! P(U) f(XY) = f(f(X)Y) và f(XY) = f(Xf(Y)).
cao 3.4. Đẳng thức kép
cấp 6 X, Y ! P(U) f(XY) = f(f(X)Y) = f(Xf(Y)) = f(f(X)
u6 6 0 Ths Điện tử {Pháp} 0 f(Y)).
u7 7 GS TS CNTT {Nga} Giảng 4. Một số tính chất của xấp xỉ trên
viên Cho hệ thống thông tin đơn trị và đầy đủ S =
cao (U, A); B 3 A.
cấp
Trên P(U) ta xây dựng hàm f: P(U) → P(U)
Chú ý: Trong hệ quyết định đa trị 6o ! U o [D] chỉ xác đinh như sau:
có một giá trị. 6 X ! P(U) f(X) = XB
Ta dễ dàng thấy rằng f là hàm đóng vì f thỏa
Định nghĩa 5. Phụ thuộc hàm trong hệ thống ba điều kiện của hàm đóng, đó là tính phản xạ: X 3
thông tin XB, tính đồng biến: nếu X 3 Y thì XB 3 YB, tính lũy
Cho hệ thống thông tin đơn trị S = (U, A); đẳng: XB = XBB
B, B’ 3 A; Ta nói B xác định phụ thuộc hàm B’, Theo các tính chất của hàm đóng ta có các
ký hiệu B → B’ nếu và chỉ nếu IND(B) 3 IND(B’). tính chất của xấp xỉ trên như sau
1. 6 X, Y ! P(U) (XY)B 4 XBYB
2. Một số tính chất của phụ thuộc hàm 2. 6 X, Y ! P(U) (X + Y)B 3 XB + YB
2.1. Tính phản xạ: 3. 6 X, Y ! P(U) (XY)B = (XBY)B
6 B 3 A thì B → B và nếu B’ 3 B thì B 4. 6 X, Y ! P(U) (XY)B = (XYB)B
→ B’. 5. 6 X, Y ! P(U) (XY)B = (XBY)B =(XYB)B = (XBYB)B
70 Khoa học & Công nghệ - Số 10/Tháng 6 - 2016 Journal of Science and Technology
- ISSN 2354-0575
Định nghĩa 7. Vùng dương của hai tập thuộc tính POS (B, B ') = ' (Ei ) P .
B, B’ Ei ! E
Cho hệ thống thông tin đơn trị S = (U, A), Chứng minh: Tính chất 3 được suy trực tiếp
B, B’ 3 A. từ định nghĩa vùng dương và xấp xỉ dưới.
Vùng dương của B và B’, ký kệu POS(B,B’)
và POS(B,B’) = , {[o]B: [o]B 3 [o]B’ & o ! U}. Tính chất 4. Số các nhóm đối tượng liên quan
đến các tập thuộc tính
Định nghĩa 8. Phụ thuộc hàm với độ phụ thuộc Cho hệ thống thông tin S = (U, A).
k(B, B’) Nếu B và B' là hai tập thuộc tính thỏa mãn B
Cho hệ thống thông tin S = (U, A), B, B’ 3 A. 3 B' thì card(U / B) # card(U / B').
Tập B’ được gọi là phụ thuộc hàm độ k(B,B’) Chứng minh: Vì mỗi nhóm của U/B’ là một
k (B, B ')
vào B, ký hiệu B B’ nếu nhóm con của U/B nên số nhóm của U/B không thể
Card (POS (B, B ') vượt quá số nhóm của U/B’.
k (B, B ') = Card (U)
Định lý 1. Cho hệ thống thông tin S = (U, A), B, B’ Tính chất 5. Sự đồng biến của hàm độ đo phụ thuộc
3 A. Cho hệ quyết định T = (U, C , D) . Hàm
B
1
B’ khi và chỉ khi IND(B) 3 IND(B). k(B,D): 2C " [0, 1] với 2C là họ các tập con của C
Chứng minh: Card (POS (B, D)
1 và k (B, D) = Card (U) là hàm đồng biến.
Giả sử B B’ => k(B,B’) = 1 =>
POS(B,B’) = , {[o]B: [o]B 3 [o]B’ & o ! U} = U Chứng minh: Để chứng minh tính chất 5, ta chỉ
=> IND(B) 3 IND(B”). cần chứng minh với mọi cặp tập thuộc tính điều kiện
Tương tự giả sử IND(B) 3 IND(B”) ta dễ dàng B, B' mà B 3 B' thì POS (B, D) 3 POS (B ', D) .
1
thử lại rằng POS(B,B’) = U và khi đó B B’.
Lấy o ! POS(B,D) khi đó [o]B 3 [o]D. Mặt
khác vì B 3 B' nên theo tính chất 1 ta có [o]B’ 3 [o]B.
5. Một số tính chất cơ bản của vùng dương
Vậy [o]B’ 3 [o]D hay o ! POS( B' ,D).
Tính chất 1. Sự bao nhau của các nhóm trên các
tập thuộc tính bao nhau Tính chất 6. Cho hệ quyết định T = (U, C , D) .
Cho hệ thống thông tin S = (U, A). Nếu
Nếu đặt w(c) = k({c}, D) là trọng số của thuộc tính
B 3 B ' 3 A thì mọi o ! U ta luôn có [o]B’ 3 [o]B.
Chứng minh: Lấy o ' ! [o] B ' khi đó vì o' và c ! C và w (B) = k (B, D) là trọng số của tập thuộc
o giống nhau (bất khả phân biệt) trên B' và B 3 B' tính B(B 3 C) thì w(c) # w(B) với mọi c ! B.
nên o và o' giống nhau trên B hay o ' ! [o] B nên Chứng minh tính chất 6 suy từ tính chất 5.
[o]B’ 3 [o]B.
4. Kết luận
Tính chất 2. Cho hệ thống thông tin S = (U, A). Trong bài viết này chúng tôi đã giới thiệu
Với mọi o ! U thì o ! POS(B, B' ) khi và chỉ khi một sốTrong bài viết này, chúng tôi đã giới thiệu
[o]B 3 [o]B’. một số nghiên cứu, tính chất có tính hệ thống, cơ
Chứng minh: tính chất 2 được suy trực tiếp bản của vùng dương, độ phụ thuộc, ràng buộc của
từ định nghĩa vùng dương. các tập thuộc tính trong hệ thống thông tin. Đồng
thời trong bài viết này, chúng tôi cũng đã nêu được
Tính chất 3. Biểu diễn vùng dương qua xấp xỉ dưới một số tính chất quan trọng, cơ bản của khái niệm
Nếu đặt E = U / B = {E1, E2,..., Ek}; phụ thuộc hàm trong hệ thống thông tin. Trong bài
AprE = (U, E) và P = U / B' = {P1, P2,..., Pl}; viết các tính chất và một số công thức liên quan đến
AprP = (U, P) thì POS (B, B ') = ' (Pj ) E và xấp xỉ trên đã được đề cập tới.
Pj ! P
Tài liệu tham khảo
[1]. Guangming Lang, Quingguo Li, Data Compression of Dynamic Set-valued Inforrmation
Systems, ArXiv: 1209.6509v1 [cs.IT] 28 Sep 2012
[2]. Pawlak Z. (1991), Rough sets: Theoretical Aspects of Reasoning About Data, Kluwer Aca-
demic Publishers.
[3]. Pawlak Z. (1998), “Rough Set Theory and its Applications in Data Analysis”, Cybernetics and
systems 29, pp. 661-688.
Khoa học & Công nghệ - Số 10/Tháng 6 - 2016 Journal of Science and Technology 71
- ISSN 2354-0575
[4]. Qian Y.H. and Liang J.Y. (2006), “Combination Entropy and Combination Granulation in
Incomplete Information System”, RSKT 2006, pp. 184-190.
[5]. Qian Y.H. and Liang J.Y. (2008), “New Method for Measuring Uncertainty in Incomplete
Information Systems”, International Journal of Uncertainty, Fuzziness and Knowledge-Based
Systems.
[6]. Qian Y.H., Liang J.Y. and Dang C.Y. (2009), “Knowledge Structure, Knowledge Granulation
and Knowledge Distance in a Knowledge Base”, International Journal of Approximate Reasoning
50, pp. 174-188.
[7]. Qian Y.H., Liang J.Y., Dang C.Y., Wang F. and Xu W. (2007), “Knowledge Distance in
Information Systems”, Journal of Systems Science and Systems Engineering, Vol. 16, pp. 434-449.
[8]. Qian Y.H., Liang J.Y., Li D.Y., Zhang H.Y. and Dang C.Y. (2008), “Measures of Evaluating the
Decision Performace of a Decision Table in Rough Set Theory”, Information Sciences, Vol.178,
pp.181-202.
[9]. R.López de Mántaras, A Distance-based Attribute Selection Measure for Decision Tree
Induction, Machine Learning Vol. 6 (1991) 81-92.
[10]. Simovici D. A. and Jaroszewicz S. (2006), “A New Metric Splitting Criterion for Decision
Trees”, International Journal of Parallel Emergent and Distributed Systems, Vol. 21 (4), pp. 239-256.
[11]. Simovici D. A., Jaroszewicz S. (2003), “Generalized Conditional Entropy and Decision Trees”,
Proceeding of EGC, Lyon, France, pp. 369-380.
[12]. Sun L., Xu J.C and Cao X.Z (2009), “Decision Table Reduction Method Based on New
Conditional Entropy for Rough Set Theory”, International Workshop on Intelligent Systems and
Applications, pp. 1-4.
[13]. Thi V.D. (1986), “Minimal Keys and Antikeys”, Acta Cybernetica 7, 4, pp. 361-371.
[14]. Vu Duc Thi, Nguyen Long Giang (2011), “A Method to Construct Decision Table from Relation
Scheme”, Cybernetics and Information Technologies, Sofia, Bulgarian Academy of Sciences,
Volume 11, No 3, 32-41.
[15]. J.D.Ullman (1998), “Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức”, NXB Thống kê.
[16]. Nguyễn Bá Tường (2011), “Cơ sở dữ liệu quan hệ và ứng dụng”, NXB Thông tin và truyền
thông.
DEPENDENCES ATTRIBUTES OF INFORMATION SYSTEMS
AND PROPERTIES OF UPPER APPROXIMATION BASED CLOSE FUNCCTION
Abstract:
This paper investigates some properties of dependence attributes in information systems. In the
paper we have been proposed a closed mapping and consequently we have showed some properties and
formulas of upper approximation.
Furthermore, it has been shown that single information system and set-value information system
determine each other.
Keywords: Dependence attribute, information system, upper approximation, decision system, close function.
72 Khoa học & Công nghệ - Số 10/Tháng 6 - 2016 Journal of Science and Technology
nguon tai.lieu . vn
