Partial covers and inhibitory decision rules

Pawel Delimata*, Mikhail Ju Moshkov, Andrzej Skowron, Zbigniew Suraj

*Corresponding author for this work

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

Abstract

In this chapter, we consider algorithms for construction of partial inhibitory decision rules and some bounds on the length such rules. These investigations are based on the use of known results for partial covers. We show that: • Under some natural assumptions on the class NP, the greedy algorithm is close to the best polynomial approximate algorithms for the minimization of the length of partial inhibitory decision rules. • Based on an information received during the greedy algorithm work, it is possible to obtain nontrivial lower and upper bounds on the minimal length of partial inhibitory decision rules. • For the most part of randomly generated binary decision tables, greedy algorithm constructs simple partial inhibitory decision rules with relatively high accuracy. In particular, some theoretical results confirm the following 0.5-hypothesis for inhibitory decision rules: for the most part of decision tables for each row during each step the greedy algorithm chooses an attribute that separates from the considered row at least one-half of rows that should be separated. Similar results can be obtained for partial inhibitory association rules over information systems. To this end, it is enough to fix an arbitrary attribute a i of the information system as the decision attribute and study inhibitory association rules with the right-hand side of the kind ai ≠ c as inhibitory decision rules over the obtained decision system (decision table).

Original languageEnglish (US)
Title of host publicationInhibitory Rules in Data Analysis
Subtitle of host publicationA Rough Set Approach
Pages43-62
Number of pages20
Volume163
DOIs
StatePublished - 2009
Externally publishedYes

Publication series

NameStudies in Computational Intelligence
Volume163
ISSN (Print)1860-949X

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Partial covers and inhibitory decision rules'. Together they form a unique fingerprint.

Cite this