An efficient algorithm for Pawlak reduction based on simplified discernibility matrix

Zhang-yan Xu (), Bing-ru Yang, Wen-bin Qian and Wen-hao Shu
Additional contact information
Zhang-yan Xu: Guangxi Normal University
Bing-ru Yang: Beijing University of Science and Technology
Wen-bin Qian: Beijing University of Science and Technology
Wen-hao Shu: Guangxi Normal University

Fuzzy Information and Engineering, 2010, vol. 2, issue 4, 433-443

Abstract: Abstract Since the definition of attribute reduction based on classic discernibility matrix differs from that of it based on positive region, a new simplified discernibility matrix and the corresponding definition of attribute reduction were proposed. At the same time, it proves that the proposed definition is identical to its definition based on positive region. For computing simplified discernibility matrix, the indiscernibility relation, which is also called equivalence relation, should usually be calculated at first, so a new algorithm for computing equivalence relation was designed with radix sorting, whose temporal complexity is O(|C||U|). Furthermore, an efficient attribute reduction algorithm is proposed, whose temporal complexity and spatial complexity are cut down to max(O(|C|2|U′ pos ||U′|,O(|U||C|)) and max(O(|C||U′ pos ||U′|,O(|U|)) respectively. At last, an example is used to illustrate efficiency of the new algorithms.

Keywords: Rough set; Discernibility matrix; Simplified discernibility matrix; Attribute reduction; Complexity (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12543-010-0061-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:fuzinf:v:2:y:2010:i:4:d:10.1007_s12543-010-0061-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/12543

DOI: 10.1007/s12543-010-0061-6

Access Statistics for this article

More articles in Fuzzy Information and Engineering from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().