Abstract: So far, most of association rule minings have considered about positive association rules based on frequent itemsets in databases [1, 4, 5, 7] , but they have not considered the problem of mining negative association rules correlated with frequent and infrequent itemsets. Negative association rule mining is much more difficult than positive association rule mining because it needs infrequent itemsets, and only the rare association rule mining which is a kind of negative association rule minings has been studied. This paper presents a mathematical model to mine positive and negative association rules precisely, for which in a point of view that negation of a frequent itemset is an infrequent itemset, we make clear the importance of the problem of mining negative association rules based on certain infrequent itemsets and study on what conditions infrequent itemsets of interest should satisfy for negative association rules. Keywords: negative association rule, itemset of interest, mining of negative association rules Apriori, a traditional association rule mining algorithm, was first proposed in 1993 [5] .The Apriori algorithm scans database multiple times, extracts a large number of possible frequent itemsets, and generates association rules. This repeated candidate generation-test approach can impose large computational overheads on a computer when the number of frequent itemsets is very large. To overcome this difficulty, a novel frequent pattern mining model based on an FP-tree was proposed in 2000 [7] . FP-growth algorithm based on the FP-tree was known by many people later and was widely used. And an OPUS-search was also proposed in 2000 [7] , which reduces the search space on basis of interrelationships among itemsets. Experiments showed that the model based on FP-tree and the OPUS-search were more efficient than the Apriori algorithm and its derivatives. By the way, some itemsets pruned in the algorithms of mining frequent patterns might be useful for mining negative association rules. That is, in spite of the fact that frequent itemsets are not contained in any association rules, they should not be pruned. These frequent itemsets might be as helpful as ever to mining negative association rules. So the existing pruning techniques have not come true to mine negative association rules. Recently, many researches have been done in the area of rare pattern mining [2, 3] . Principally, there are two types of researches such as level-wise and tree-based, like that of current frequent pattern mining. More recently, a new approach of list structure was proposed [6] . MS-Apriori, Rarity, ARIMA, AfRIM and Apriori-Inverse are 5 algorithms of mining rare itemsets [3] . Note that rare association rule such as ¬A→¬C is only a kind of negative association rules, meanwhile any clear definition of all possible negative association rules have not given. And, there are much more infrequent itemsets for negative association rules than frequent itemsets(almost double) and the size of the search space may be exponential [3, 6] . It has not been studied what conditions infrequent itemsets satisfy could be useful to generate negative association rules. 1
We gave the definitions of positive and negative itemsets of interest in REF .
Itemsets of interest for negative association rules
ArXiv
ArXiv
Computer Science