Greedy algorithm for construction of partial association rules

Mikhail Moshkov, Marcin Piliszczuk, Beata Zielosko

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

Original languageEnglish (US)
Pages (from-to)259-277
Number of pages19
JournalFundamenta Informaticae
Volume92
Issue number3
DOIs
StatePublished - Jul 31 2009

Keywords

  • Association rules
  • Greedy algorithm
  • Information systems
  • Rough sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Greedy algorithm for construction of partial association rules'. Together they form a unique fingerprint.

Cite this