Extracting relevant information about reduct sets from data tables

Mikhail Ju Moshkov, Andrzej Skowron, Zbigniew Suraj

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations


The direct searching for relevant reducts in the set of all reducts of a given data table can be often computationally infeasible, especially for large data tables. Hence, there is a need for developing efficient methods for extracting relevant information about reducts from data tables which could help us to perform efficiently the inducing process of the high quality data models such as rule based classifiers. Such relevant information could help, e.g., to reduce the dimensionality of the attribute set. We discuss methods for generating relevant information about reduct sets from information systems or decision tables. In particular, we consider a binary relation on attributes satisfied for two given attributes if and only if there is no reduct consisting them both. Moreover, we prove that for any fixed natural k, there exists a polynomial in time algorithm which for a given decision table T and given k conditional attributes recognizes if there exists a decision reduct of T covering these k attributes. We also present a list of problems related to the discussed issues. The reported results create a step toward construction of a software library reducing the searching costs for relevant reducts.

Original languageEnglish (US)
Title of host publicationTransactions on Rough Sets IX
Number of pages12
StatePublished - 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5390 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • Decision reducts
  • Decision tables
  • Geometry of reducts
  • Rough sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Extracting relevant information about reduct sets from data tables'. Together they form a unique fingerprint.

Cite this