Extracting relevant information about reduct sets from data tables

Mikhail Moshkov, Andrzej Skowron, Zbigniew Suraj

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

4 Scopus citations

Abstract

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
Pages200-211
Number of pages12
DOIs
StatePublished - Dec 1 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

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint

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

Cite this