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Ô

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...
Nội dung trích xuất từ tài liệu:
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útgon 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ôngtin 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 2trì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 thatfinding the minimal reduction of an information system is a NP-hard problem, so is finding theminimal reduction of an incomplete information system. The main reason for this problem iscaused by a combination of attributes. In this paper, we theoretically study an attribute reductionalgorithm. This is based on the results given by Chen Degang and his colleages in theconsistent and inconsistent covering decision system. The time complexity of this algorithm isO(|∆||U| ). At the end of this paper an illustrative example is also provided to show the 2application 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ằmthu 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ậpthô. Độ 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útgọ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, đặtC 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 địnhnghĩ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).2009C 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 địnhngh ĩ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ấtquá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) đượcgọ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 / DMộ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ấtquá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útgọ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 đảmbả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 ...