Abstract
During the last years the amount of data stored in databases has grown very fast. Data mining, also known as knowledge discovery in databases, represents the discovery process of potentially useful hidden knowledge or relations among data from large databases. An important task in the data mining process is the discovery of the association rules. An association rule describes an interesting relationship between different attributes. There are different kinds of association rules: Boolean (crisp) association rules, quantitative association rules, fuzzy association rules, etc. In this chapter, we present the basic concepts of Boolean and the fuzzy association rules, and describe the methods used to discover the association rules by presenting the most important algorithms.
TopIntroduction
The progress of Information Technology has determined companies to record a large quantity of information in huge databases. Due to the fact that a lot of useful knowledge is hidden in these databases, the companies need to extract this knowledge in order to help the decision-making process.
Data mining, also known as knowledge discovery in databases (Chen, Han, & Yu, 1996), provides efficient automated techniques for discovering potentially useful, hidden knowledge or relations among data from large databases. Data mining functions include classification, clustering, prediction, regression, and link analysis (associations), etc.
Mining association rules represent an unsupervised data mining method that allows identifying interesting associations, correlations between items, and frequent patterns from large transactional databases. This problem was first introduced by Agrawal et al. in (Agrawal, Imielinski, & Swami, 1993).
The original motivation for searching association rules came from the need to analyze the market-basket data that stores items purchased on a per-transaction basis, in order to identify customer behaviors by finding different items often purchased together. A typical example of an association rule has the following statement:
popcorn ⇒ beer [support = 7%, confidence = 74%] (1)
This rule expresses a relation between popcorn and beer namely “customers who purchase popcorn also purchase beer in the same transaction”. The support and confidence are two measures used to show the rule interestingness. The support of 7% for rule presented above states that popcorn and beer appeared together in 7% of all recorded transactions. The confidence measure describes the chance that there is beer in a transaction provided that there is also popcorn. In this case, 74% of all transactions involving popcorn also involved beer.
Such rules provide a source of information for retailers to develop marketing strategies, catalog design and store layout. Thus, the company can decide that items frequently purchased together to be placed in proximity in order to encourage the sale of such items together. Other strategy is placing the items frequently purchased together at opposite ends of the store in order to attract customers that purchase such items to pick up other items along the way.
The association rules can be categorized in different ways as follows (Han & Kamber, 2006):
Key Terms in this Chapter
Support: A quality measure used to reflect the usefulness of discovered rules. The support of association rule is defined as the proportion/percentage of transactions that contains both X and Y (the probability of both X and Y cooccurring in transactions)
Strong Association Rule: An association rule having support and confidence greater than or equal to a user-specified minimum support threshold and respectively a minimum confidence threshold.
Data Mining: The process of nontrivial extraction of implicit, previously unknown and potentially useful information (such as knowledge rules, constraints, regularities) from data in databases.
Association Rule: An implication of the form, means that transactions including X will include Y as well, with a high probability.
Itemset: A collection of items. For example, all items bought by one customer during one visit to a department store.
Apriori Alorithm: The seminal algorithm for mining frequent itemsets for Boolean association rules based on Apriori property
Frequent Itemset: An itemset with support is greater than or equal to minimum support threshold
Confidence: A quality measure that indicates the strength or the reliability of the associations detected. The confidence of association rule is defined as the proportion (percentage) of transactions containing X that also contain Y (conditional probability of occurring Y given X).
Association Rules Mining: The finding strong association rules.
Market Basket Analysis: Analysis of customer habits by searching for the set of items that are frequently purchased together.