Research in association rules mining has initially concentrated in solving the obvious problem of finding positive association rules; that is rules among items that exist in the stored transactions. It was only several years after that the possibility of finding also negative association rules became especially appealing and was investigated. Nevertheless researchers based their assumptions regarding negative association rules on the absence of items from transactions. This assumption though besides being dubious, since it equated the absence of an item with a conflict or negative effect on the rest items, it also brought out a series of computational problems with the amount of possible patterns that had to be examined and analyzed. In this work we give an overview of the works having engaged with the subject until now and present a novel view for the definition of negative influence among items.
TopBackground
Association rule mining is still probably the prominent method for knowledge discovery in databases (KDD), among all other methods such as classification, clustering, sequential pattern discovery etc. The discovery of association relationships among items in a huge database has been known to be useful in various sectors such as telecommunications, banking, transport and particularly in retail. Also it has been applied to various data sets such as census data, text documents, transactional data, medical images and lately biological data. In fact any data type that is collected and constitutes a large database of “baskets”, each containing multiple “items” can fit this model. The prototypical application of association rules mining and probably until today the most extensively studied and popular one is the analysis of supermarket sales or basket data; hence the problem of finding association rules is often referred to as the “market-basket” problem. In this problem, we are given a set of items and a large collection of transactions which are subsets (baskets) of these items. The objective is to find relationships correlating various items within those baskets. More formally the specific task can be stated as follows:
Let I={i1, i2,…,in} be a set of items and D be a database organized in multiple transactions T where each transaction T∈D is a set of items such that T ⊆ I . An association rule is an implication of the form X→Y, where X, Y ⊆ I and X ∩ Y = ∅, and expresses the possibility that whenever we find a transaction that contains all items in X, then this transaction is likely to also contain all items in Y. Consequently X is called the body of the rule and Y the head. The validity and reliability of association rules is expressed usually by means of support and confidence, succored by other measures such as for example implication, lift etc. An example of such a rule is {cell_phone, hands_free→case (sup=70%, conf=90%)}, which means that 90% of the customers that buy a cell phone and a hands free device buy a cell phone case as well, whereas 70% of all our customers buy all these three things together.
The task of finding association rules was first formulated by Agrawal, Imielinski and Swami (1993). Since then there have been a series of works trying to improve various aspects such as the efficiency of Apriori based algorithms, implementation of new measures for finding strong – alternative rules, application of association rules framework into other domains etc. (for more details interested reader is referred to the work of Tan, Steinbach & Kumar, 2005).
On the other hand negative association rules have been initially either neglected or considered unimportant. It was not only but after several years since the first introduction of association rules that the problem of negative association rules was brought up. Also despite the fact that the existence and significance of negative association rules has been recognized for quite some time, comparably a very small percentage of researchers have engaged with it.