Affiliations: Division of Mathematical and Computer Science and
Engineering, King Abdullah University of Science and Technology, P.O. Box 55455,
Jeddah 21534, Saudi Arabia. [email protected] | ING Bank Śl�ski S.A. 34, Sokolska St.,
Katowice 40-086, Poland. [email protected] | Institute of Computer Science, University of Silesia
39, B�dzińska St., Sosnowiec 41-200, Poland.
[email protected]
Note: []
Address for correspondence: Division of Mathematical and, Computer Science and Engineering, King Abdullah University
of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia
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.
Keywords: Rough sets, information systems, association rules, greedy algorithm
