zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Báo cáo khoa học

Báo cáo khoa học: " RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH DỰA VÀO HỌ PHỦ TẬP THÔ"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:6

Báo xấu

144
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP -khó. Lý do chính là do s tổ hợp các thuộc tính. ự Trong bài báo này, chúng tôi ề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự đ phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: " RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH DỰA VÀO HỌ PHỦ TẬP THÔ"

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH DỰA VÀO HỌ PHỦ TẬP THÔ ON THE ATTRIBUTE REDUCTION OF DECISION SYSTEMS BASED ON A FAMILY OF COVERING ROUGH SETS Nguyễn Đức Thuần Nguyễn Xuân Huy Trường Đại học Nha Trang Viện Công nghệ thông tin, Hà Nội TÓM T ẮT Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP -khó. Lý do chính là do s tổ hợp các thuộc tính. ự Trong bài báo này, chúng tôi ề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự đ phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định phủ nhất quán và không nhất quán. Độ phức tạp của giải thuật là O(|∆||U| ). Trong phần cuối bài báo chúng tôi 2 trình bày một ví dụ minh họa thể hiện hiệu năng của giải thuật. ABSTRACT Attribute reduction is an important issue in the rough set theory. It has been proved that finding the minimal reduction of an information system is a NP-hard problem, so is finding the minimal reduction of an incomplete information system. The main reason for this problem is caused by a combination of attributes. In this paper, we theoretically study an attribute reduction algorithm. This is based on the results given by Chen Degang and his colleages in the consistent and inconsistent covering decision system. The time complexity of this algorithm is O(|∆||U| ). At the end of this paper an illustrative example is also provided to show the 2 application potential of the algorithm. 1. Giới thiệu Bài toán rút gọn tập thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán này thuộc lớp NP -khó [3].Vì vậy, đôi khi người ta chỉ tìm một rút gọn (nhằm thu gọn kích thước của hệ thống thông tin ). Trong bài báo này, chúng tôi đ xuất một ề thuật toán tìm một rút gọn tối thiểu tập thuộc tính ứng với một họ phủ quyết định tập thô. Độ phức tạp của thuật toán là O(|∆||U|2), tương đương với các thuật toán tìm một rút gọn tập thuộc tính trong lý thuyết tập thô cổ điển. 2. Các khái niệm cơ sở Phủ tập thô và suy dẫn phủ Cho U là một tập vũ trụ, C là một họ các tập con khác rỗng của U. C được gọi là một phủ của U nếu ∪C = U.Với C = {C 1 , C 2 ,..,C n } là một phủ của U. Với mọi x∈U, đặt C x =∩{C j : C j ∈ C, x∈C j }. Cov(C) = {C x : x∈U} cũng là một phủ của U. Chúng ta gọi là một phủ suy dẫn của C. Khái niệm phủ suy dẫn của một họ phủ tập thô cũng được định nghĩa tương tự: Cho ∆ = { C i : i=1,..m} là một họ phủ của U. Với mọi x∈U, đặt ∆ x =∩{C ix : 64
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 C ix ∈ Cov(Ci ), x ∈C ix } thì Cov(∆)= {∆ x : x ∈U} cũng là một phủ của U. Chúng ta gọi nó là một phủ suy dẫn của ∆. Với mỗi X ⊆ U, xấp xỉ dưới và xấp xỉ trên của X tương ứng với Cov(∆) được định ngh ĩa như sau: ∆( X ) =∪{∆ x : ∆ x ⊆ X }, ∆( X ) = ∪{∆ x : ∆ x ∩ X ≠ ∅} 3. Rút gọn tập thuộc tính của các hệ thống quyết định nhất quán và không nhất quán Gọi ∆ = { C i : i=1,..m} là một họ phủ của U, D là thuộc tính quyết định, U/D là một phân hoạch trên U. Nếu ∀x∈U, ∃Dj ∈U/D mà ∆ x ⊆ D j , thì hệ quyết định (U, ∆,D) được gọi là hệ quyết định nhất quán và ký hiệu Cov(∆)≤ U/D. Ngược lại, (U,∆,D) được gọi là hệ quyết định không nhất quán. Miền dương của D ứng với ∆ được định nghĩa: POS ∆= ∆( X )  ( D) X ∈U / D Một phủ không cần thiết của một họ phủ ứng với hệ quyết định nhất quán, không nhất quán lần lượt cũng được xác định: Cho (U,∆,D={d}) là một hệ quyết định nhất quán. Với C i ∈∆, nếu Cov( ∆-{C i }) ≤ U/D, thì C i thuộc ∆ được nói là không cần thiết đối với D, ngược lại C i được nói là cần thiết đối với D. Tập P ⊆ ∆ thỏa Cov(P) ≤ U/D, nếu mọi phần tử thuộc P là cần thiết, có nghĩa là ∀C i ∈P, Cov(∆-{C i }) ≤ U/D là sai, thì P được gọi là một rút gọn của D. Rút gọn của một hệ quyết định nhất quán là một tập tối thiểu các thuộc tính điều kiện đảm bảo chắc chắn các luật quyết định là nhất quán. Giả sử U là một tập vũ trụ hữu hạn và ∆ = {C i : i=1,..m} là một họ các phủ của U, C i ∈∆, D là một thuộc tính quyết định tương ứng với ∆ trên U và d: U → V d là hàm quyết định được định nghĩa d(x) = [x] D . (U,∆,D) là một hệ quyết định phủ không nhất quán khi POS ∆ (D)≠U. Nếu POS ∆ (D)=POS ∆-{Ci} (D), thì C i là quan hệ trong ∆ không cần thiết đối với D. Ngược lại, C i là quan hệ cần thiết đối với D. 4. Thuật toán rút gọn tập thuộc tính ứng với họ phủ tập thô Nhận xét 3.1. Từ định nghĩa của đại lượng ∆x. Với D = {d}, d(x) là một hàm quyết định d: U → V d xác định từ tập vũ trụ U vào tập giá trị V d . Ta có các kết quả sau: - Với mỗi xi, xj ∈U, nếu ∆xi ⊆ ∆xj, thì d(xi) = d([xi] D ) = d(∆xi) = d(∆xj) = d(xj) = d([xj] D ). - Nếu d(∆xi) ≠ d(∆xj), thì ∆xi ∩ ∆xj = ∅, có nghĩa là ∆xi ⊄ ∆xj và ∆xj ⊄ ∆xi. Từ nhận xét trên và các kết quả trong [4], chúng tôi chứng minh được 2 định lý sau: Định lý 3.1. Cho (U,∆,D={d}) là một hệ quyết định phủ, P ⊆ ∆, chúng ta có: a. (U,∆,D={d}) là một hệ quyết định phủ nhất quán khi thỏa: 65
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 ∆ x ∩ [ x ]D ∑ =U ∆x x∈U b. Giả sử Cov( ∆)≤ U/D, C i ∈∆, C i là không cần thiết, có nghĩa là Cov(∆-{C i }) ≤ U/D khi và chỉ khi ∑ ∑ (∆ ∩ ∆ xj ) ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) = 0 xi xi∈U xj∈U ở đây, Cov(∆-{C i })={P x: x∈U}, Cov(∆)={∆ x : x ∈U} Chứng minh: a. Từ định nghĩa của một hệ quyết định nhất quán, rõ ràng với mỗi x∈U, ∆ x ⊆ [x] D luôn luôn đúng, vì vậy chúng ta có: ∆ x ∩ [ x]D = ∆ x có nghĩa là: ∆ x ∩ [ x ]D ∑ =U ∆x x∈U b. Nếu đặt Cov(∆-{C i })=Cov(P)={P x: x∈U}, Cov(∆)={∆ x : x ∈U} Theo [4](định lý 4.5) P là 1 rút gọn hay C i là không cần thiết nếu với mọi cặp x i , x j ∈U thỏa d(∆ xi )≠ d(∆ xj ) ta có quan hệ giữa x i , x j ứng với ∆ tương đương với quan hệ của chúng đối với P, nghĩa là ∆ xi ⊄ ∆ xj and ∆ xj ⊄ ∆ xi ⇔ P xi ⊄ P xj , P xj ⊄ P xi . Theo nhận xét 3.1, d(∆ xi )≠ d(∆ xj )⇒ (∆xi∩∆xj)=∅, khi đó ta cũng có (P xi ∩P xj )= ∅, nên (∆ xi ∩ (∆ xj ) ∪ ( Pxi ∩ Pxj ) =0 -Nếu x i , x j ∈U thỏa d(∆ xi )=d(∆ xj )⇒ d (∆xi ) − d (∆xj ) = Nói khác hơn, khi C i không 0. cần thiết ta có: ∑ ∑ (∆ ∩ ∆ xj ) ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) = 0 (đ.p.cm) xi xi∈U xj∈U Định lý 3.2. Cho (U,∆,D={d}) là m hệ quyết định không nhất quán. P ⊆ ∆, ột POS P (D)= POS ∆ (D) nếu và chỉ nếu∀x i ∈U, ta có  ∆ xi ∩ [ xi ]D Pxi ∩ [ xi ]D  ∑ − =0 ∆ xi Pxi   xi∈U Chứng minh: Đây là k quả trực tiếp từ 3 tính chất của đị nh lý 5.2 trong [4]. Từ điều kiện ∀x i ∈U, ∆x i ết ⊆[x i] D ⇔ P xi ⊆[x i] D có nghĩa là ∀x i ∈U, ∆xi ∩ [x]D = ⇔ Pxi ∩ [x]D = . Nói khác ∆xi Pxi hơn ta có điều phải chứng minh. 5. Thuật toán rút gọn thuộc tính của họ quyết định phủ tập thô Input: Cho hệ quyết định phủ S = (U,∆,D={d}). Output: Một rút gọn thuộc tính RD of ∆. 66
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 Method: ∆ x ∩ [ x ]D Bước 1: Tính CI = ∑ ∆x x∈U Bước 2: If CI = |U| {S là một hệ quyết định nhất quán } thì đến bước 3, ngược lại đến bước 5. Bước 3: Tính ∆ x , d(∆ x ), ∀x∈U. Bước 4: Begin for each C i ∈∆ do if ∑ ∑ (∆ ∩ ∆ xj ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) = 0 xi xi∈U xj∈U {ở đây ∆ - {C i }= {Px: x∈U}} then ∆:= ∆ - {C i }; Endfor; goto Bước 6. End; Bước 5: Begin for each C i ∈∆ do if  ∆ xi ∩ [ xi ]D Pxi ∩ [ xi ]D  ∑ − =0 ∆ xi Pxi   xi∈U then ∆:= ∆ - {C i };{ở đây ∆ - {C i }= {Px: x∈U}} Endfor; End; Bước 6: RD= ∆; thuật toán kết thúc. Thuật toán này có độ phức tạp là đa thức theo |U|. Thật vậy, Ở bước 1, độ phức tạp tính CI là O(|U|). Bước 2, độ phức tạp là O(1). Bước 3, độ phức tạp là O(|U|). Bước 4, độ phức tạp tính ∑∑() là O(|U|2), do đó độ phức tạp của bước này là O(|∆||U|2), vì i=1..|∆|.Bước 5, tương tự độ phức tạp ở bước 3, độ phức tạp là O(|∆||U|2). Bước 6, độ phức tạp O(1). Vì vậy, độ phức tạp của cả giải thuật là O(|∆||U|2) (ở đây chúng ta bỏ qua thời gian tính ∆xi, Pxi, với i= 1..|∆|). 6. Ví dụ minh họa Bước 1: Giả sử U = {x 1 , x 2 ,.., x 9 }, ∆ = {C i , i=1..4}, và C 1 ={{x 1 ,x 2 ,x 4 ,x 5 ,x 7 ,x 8 },{x 2 ,x 3 ,x 5 ,x 6 ,x 8 ,x 9 }}, C 2 ={{x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 },{x 4 ,x 5 ,x 6 ,x 7 ,x 8 ,x 9 }}, 67
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 C 3 ={{x 1 ,x 2 ,x 3 },{x 4 ,x 5 ,x 6 ,x 7 ,x 8 ,x 9 },{x 5 ,x 6 ,x 8 ,x 9 }}, C 4 ={{x 1 ,x 2 ,x 4 ,x 5 },{x 2 ,x 3 ,x 5 ,x 6 },{x 4 ,x 5 ,x 7 ,x 8 },{x 5 ,x 6 ,x 8 ,x 9 }} U/D={{x 1 ,x 2 ,x 3 }, {x 4 ,x 5 ,x 6 }, {x 7 ,x 8 ,x 9 }} CI = 9 ⇒ S là một hệ nhất quán. Bước 2: P - {C 1 }, Tính P 1 ,.., P 9 ∑ ∑ (∆ ∩ ∆ xj ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) = 0 xi xi∈U xj∈U ∆=∆ - {C 1 }={C 2 ,C 3 ,C 4 }. C 1 là không cần thiết, loại bỏ Bước 3: P=∆ - {C 2 }, Tính P 1 ,.., P 9 ∑ ∑ (∆ ∩ ∆ xj ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) = 0 xi xi∈U xj∈U ∆=∆ - {C 2 }= {C 3 ,C 4 }. C 2 là không cần thiết, loại bỏ Bước 4: P= ∆ - {C 3 }, Tính P 1 ,.., P 9 ∑ ∑ (∆ ∩ ∆ xj ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) ≠ 0 xi xi∈U xj∈U (bởi vì chúng ta có thể thấy:(∆ 1 ∩∆ 4 )=∅, nhưng (P 1 ∩P 4 )≠∅, |d(∆ 1 )-d(∆ 4 )|≠0) C 3 là cần thiết, không thể loại bỏ, ∆={C 3 ,C 4 }. Bước 5: P= ∆ - {C 4 }, Tính P 1 ,.., P 9 ∑ ∑ (∆ ∩ ∆ xj ∪ ( Pxi ∩ Pxj ) d (∆ xi ) − d (∆ xj ) ≠ 0 xi xi∈U xj∈U (bởi vì chúng ta có thể thấy:(∆ 6 ∩∆ 7 )=∅, nhưng (P 6 ∩P 7 )≠∅, |d(∆ 6 )-d(∆ 7 )|≠0) C 4 là cần thiết, không thể loại bỏ, ∆={C 3 ,C 4 }. Bước 6: RD= {C3,C4} là một rút gọn họ phủ tập thô. Ứng với rút gọn này 2 thuộc tính tương ứng với C1, C2 bị loại bỏ. 7. Kết luận Trong bài báo này, chúng tôi đ xuất một thuật toán rút gọn tập thuộc tính dựa ề vào một họ phủ quyết định tập thô. Nó dựa trên các một số kết quả của Chen Degang và các cộng sự. Độ phức tạp của giải thuật là O(| ∆||U|2). So sánh với các kết quả của thuật toán của Chen Degang, kết quả chúng tôi có được là hoàn toàn tương thích. Trong thời gian đến, chúng tôi sẽ cài đặt thử nghiệm trên các tập dữ liệu UCI nhằm có thể đánh giá chi tiết hơn TÀI LIỆU THAM KHẢO [1] William Zhu, Fei-Yue Wang, Reduction and axiomization of covering generalized rough sets, Information Sciences,152 (2003) 217-230. 68
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009 [2] Eric C.C.Tsang, Degang Chen, John W.T.Lee, Daniel S.Yeung, On The Upper Approximations of covering generalized Rough sets, Proceeding of the Third International Conference on Machine Learning and Cybernetic, Shanghai, 26-29 August 2004. [3] Guo-Ying Wang, Jun Zhao, Jiu-Jiang An, Yu Wu, Theoretical Study on Attribute Reduction of Rough set Theory: Comparision of Algebra and Information Views, Proceedings of Third IEEE International Conference on Cognitive Informatics (ICCI’ 04), 0-7695-2190-8/04. [4] Cheng Degang, Wang Changzhong, Hu Quinghua, A new approach to attribute reduction of consistent and inconsistent covering rough sets, Information Sciences,177 (2007) 3500- 3518. 69

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.26: Bộ 320 Luận Văn Thạc Sĩ Y Học

320 tài liệu

1247 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.