Mining Association Rules

Mining Association Rules

Mihai Gabroveanu (University of Craiova, Romania)
DOI: 10.4018/978-1-60566-402-6.ch027
OnDemand PDF Download:
$30.00
List Price: $37.50

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.
Chapter Preview
Top

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:

popcornbeer [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)

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.

Complete Chapter List

Search this Book:
Reset