Fundamenta Informaticae · 2009 · 15 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsData MiningKnowledge RepresentationApproximation AlgorithmsExpert SystemsFrequent Pattern MiningGreedy AlgorithmsRule-based RepresentationText MiningApproximate Frequent Pattern MiningAssociation Rule LearningAssociation Rule MiningGreedy ApproximationGreedy HeuristicsPolynomial-time AlgorithmsRule ExtractionRule Mining
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.
15
Modeling by shortest data description
J. Rissanen · Automatica · 1978 · 6K citations
Zdzisław Pawlak, Andrzej Skowron · Information Sciences · 2006 · 2.1K citations · Full text
Mining quantitative association rules in large relational tables
Ramakrishnan Srikant, Rakesh Agrawal · 1996 · 1.5K citations · Full text