Mining Association Rules

Introduction

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):

• 1.

  Based on the types of values handled in the rule:

  • a.

    Boolean (crisp) association rules: the association is between the presence or absence of items. Rule (1) is an example of such a Boolean association rule.

  • b.

    Quantitative association rules: the rules describe associations between quantitative items or attributes. Here the attribute values are partitioned into intervals. An example of such rule is the following:

    
    (2)

  • c.

    Categorical association rules: the attributes referred by rules are categorical, such as occupation or sex. An example of such a rule is the following:

    
    (3)

• 2.

  Based on the number of data dimension involved in the rule:

  • a.

    Single-dimensional rules: the items or attributes from rules refer only one dimension. An example of such rule is the following:

    
    (4)