Mining Positive and Negative Association Rules

Abstract—Mining association rules and especially the negative ones has received a lot of attention and has been proved to be useful in the real world. In this work, a set of algorithms for finding both positive and negative association rules (NAR) in databases is presented. A variant of the Apriori, traditional association rules algorithm, is achieved using support and confidence in order to discover two types of NAR; the confined negative association rules (CNR), and the generalized negative association rules (GNAR). For the CNR, where only one negative rule exists among positive ones, the negative rule can be discovered by applying the measure of correlation in terms of the conditional and marginal probability along with the contingency tables. This measure is also used for finding positive rules in the case of branches of itemsets. The negative associations of CNR can be used for substitution of items in market basket analysis. A method of Binary Tree Rules Construction (BTRC) has been developed for the discovery of rules that belong to GNAR, when one or more negative rules along with positive ones exist. In each computation process from disjoint sets, the BTRC produces nested subtrees in order to find the NAR. BTRC is based on successive partitioning of the events of observing a sequence with a certain number of positive and negative items. A set of formulas depending on the height of the tree has been developed. The process can be divided into two parts; the external and the internal subtree process. Keywords—Association Rules, negative rules, conditional probability I