Algorithms with a Classifier for Mining Positive and Negative Association Rules

Mining association rules and especially the negative ones has received a lot of attention. A set of algorithms for finding both positive and negative association rules (NAR) in databases is presented. A variant of the Apriori, is achieved using support and confidence 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 rules, the measure of correlation in terms of conditional and marginal probability along with contingency tables can provide a solution. Negative associations from CNR are used for substitution of items in market basket analysis. A Binary Tree Rules Construction (BTRC) method has been developed to discover rules that belong to GNAR, when both one or more negative and positive rules exist. The BTRC produces nested subtrees in each computation process from disjoint sets. It is based on successive partitioning of the events of observing a sequence with a certain number of positive and negative items. BTRC can work iteratively or recursively during or after Apriori phases. Depending on the height of the tree, a set of formulas is developed. The process has two parts; the external and the internal. Correctness of the process and formulas is proved via set theory. A parallel algorithm has also been created. Finally, an associative classifier, based on positive and negative rules discovered, is developed. A theorem can guarantee classification. The complexity of the proposed algorithms is examined. Simulation results are provided.