Finding rough and fuzzy-rough set reducts with SAT

Richard Jensen, Andrew Tuson, Qiang Shen

Research output: Contribution to journalArticlepeer-review

60 Citations (SciVal)
267 Downloads (Pure)


Feature selection refers to the problem of selecting those input features that are most predictive of a given outcome; a problem encountered in many areas such as machine learning, pattern recognition and signal processing. In particular, solution to this has found successful application in tasks that involve datasets containing huge numbers of features (in the order of tens of thousands), which would otherwise be impossible to process further. Recent examples include text processing and web content classification. Rough set theory has been used as such a dataset pre-processor with much success, but current methods are inadequate at finding globally minimal reductions, the smallest sets of features possible. This paper proposes a technique that considers this problem from a propositional satisfiability perspective. In this framework, globally minimal subsets can be located and verified.
Original languageEnglish
Pages (from-to)100-120
Number of pages21
JournalInformation Sciences
Early online date10 Aug 2013
Publication statusPublished - 10 Jan 2014


  • Rough set theory
  • Fuzzy rough set theory
  • Feature selection
  • Boolean satisfiability


Dive into the research topics of 'Finding rough and fuzzy-rough set reducts with SAT'. Together they form a unique fingerprint.

Cite this