Association rules are an intuitive descriptive paradigm that has been used extensively in different application domains with the purpose to identify the regularities and correlation in a set of observed objects. However, association rules’ statistical measures (support and confidence) have been criticized because in some cases they have shown to fail in their primary goal: that is to select the most relevant and significant association rules. In this chapter the authors propose a new model that replaces the support measure. The new model, like support, is a tool for the identification of reliable rules and is used also to reduce the traversal of the itemsets’ search space. The proposed model adopts new criteria in order to establish the reliability of the information extracted from the database. These criteria are based on Bayes’ Theorem and on an estimate of the probability density function of each itemset. According to our criteria, the information that we have obtained from the database on an itemset is reliable if and only if the confidence interval of the estimated probability is low compared with the most likely value of it. We will see how this method can be computed in an approximate but satisfactory way, with the same algorithms that are usually adopted to select itemsets on support threshold.
TopIntroduction
The search for association rules in data mining has the aim of identifying the phenomena that are recurrent in a data set. The solution of this problem finds application in many fields, such as analysis of basket data of supermarkets, failures in telecommunication networks, medical test results, lexical features of texts, and so on. The extraction of association rules from very large databases has been solved by researchers in many different ways and the proposed solutions are embedded in as many powerful algorithms.
An association rule X →Y is a pair of two sets of items (called itemsets), X and Y, which are often found together in a given collection of data. For instance, the association rule {milk, coffee} → {bread, sugar} extracted from the market basket domain, has the intuitive meaning that a customer purchasing milk and coffee together is likely to also purchase bread and sugar.
The validity of an association rule has been based on two measures: the support, the percentage of transactions of the database containing both X and Y; and the confidence, the percentage of the transactions in which Y occurs relative only to those transactions in which also X occurs.
For instance, with reference to the above example, a value of 2% of support and a value of 15% of confidence would mean that in 2% of all the transactions, customers buy together milk, coffee, bread and sugar, and that the 15% of the transactions in which customers have bought together milk and coffee contain also bread and sugar. In the original application domain of market basket analysis, support meant that only the association rules with decision making value were extracted.
Association rules are intuitive, and constitute a powerful and versatile conceptual tool that have been applied recently also to new types of problems, such as collaborative recommender systems for e-commerce (Lin, Alvarez & Ruiz, 2002), intrusion detection (Lee, Stolfo & Mok, 1998) and are extended to discover quasi-equivalent media objects in a distributed information system with the purpose of reducing the number of objects traversed by the queries (Shyu, Chen & Kashyap, 1999). However, in almost all the new and real-life applications the support-confidence framework reveals some limits. As a result, if itemsets are not validated by a statistical approach, non-significant itemsets could be extracted by frequent itemset algorithms and in turn non-significant rules. These problems are discussed in more detail in the section on related work.
Furthermore, Liu, Hsu & Ma (1999) provide evidence of the rare item problem consisting of the fact that the support-threshold constraint discards potentially meaningful association rules between items with low support. We can conclude that a unique value of support is not realistic: the various items present very different probability density distributions.
In this chapter we present a new statistical model whose purpose is to give a solid basis to the extraction of relevant itemsets from the database. In particular it provides a lower bound of the values of probability of occurrence of itemsets that can be observed in a given database. At the same time the new statistical model proposed, as any other model for data mining, must be implemented efficiently and allow pruning of the itemsets’ search-space, which is one of the original motivations for the adoption of the support measure.
The new model allows for the replacement of the minimum support threshold imposed as a requirement by the user. According to the new model we are allowed to judge the relevance of the information obtained from the database with a criterion based on the Bayes’ Theorem. This one allows us to make an estimate of the probability distribution function of an itemset (a priori probability) starting from the set of observations obtained by the database (a posteriori probability). The adopted criterion is very simple. We consider the probability of an itemset to be a random variable, and make an estimate of this probability on the basis of the observations (obtained a posteriori) from the database. If the most likely value of probability of occurrence of an itemset in the database is comparable with the error in this estimate we can conclude that the probability estimation is not reliable.