Abstract
Data mining is a field encompassing study of the tools and techniques to assist humans in intelligently analyzing (mining) mountains of data. Data mining has found successful applications in many fields including sales and marketing, financial crime identification, portfolio management, medical diagnosis, manufacturing process management and health care improvement etc.. Data mining techniques can be classified as either descriptive or predictive techniques. Descriptive techniques summarize / characterize general properties of data, while predictive techniques construct a model from the historical data and use it to predict some characteristics of the future data. Association rule mining, sequence analysis and clustering are key descriptive data mining techniques, while classification and regression are predictive techniques. The objective of this article is to introduce the problem of association rule mining and describe some approaches to solve the problem.
TopBackground
Association rule mining, one of the fundamental techniques of data mining, aims to extract interesting correlations, frequent patterns or causal structures among sets of items in data.
An association rule is of the form X→ Y and indicates that the presence of items in the antecedent of rule (X) implies the presence of items in the consequent of rule (Y). For example, the rule {PC, Color Printer} → {computer table} implies that people who purchase a PC (personal computer) and a color printer also tend to purchase a computer table. These associations, however, are not based on the inherent characteristics of a domain (as in a functional dependency) but on the co-occurrence of data items in the dataset. Thus, association rule mining is a totally data driven technique.
Association rules have been successfully employed in numerous applications, some of which are listed below:
- 1.
Retail market analysis: Discovery of association rules in retail data has been applied in departmental stores for floor planning, stock planning, focused marketing campaigns for product awareness, product promotion and customer retention.
- 2.
Web association analysis: Association rules in web usage mining have been used to recommend related pages, discover web pages with common references, web pages with majority of same links (mirrors) and predictive caching. The knowledge is applied to improve web site design and speed up searches.
- 3.
Discovery of linked concepts: Words or sentences that appear frequently together in documents are called linked concepts. Association rules can be used to discover linked concepts which further lead to the discovery of plagiarized text and the development of ontologies etc..
The problem of association rule mining (ARM) was introduced by Agrawal et al. (1993). Large databases of retail transactions called the market basket databases, which accumulate in departmental stores provided the motivation of ARM. The basket corresponds to a physical retail transaction in a departmental store and consists of the set of items a customer buys. These transactions are recorded in a database called the transaction database. The goal is to analyze the buying habits of customers by finding associations between the different items that customers place in their “shopping baskets”. The discovered association rules can also be used by management to increase the effectiveness of advertising, marketing, inventory management and reduce the associated costs.
The authors in (Agrawal et al., 1993) worked on a boolean database of transactions. Each record corresponds to a customer basket and contains transaction identifier (TID), transaction details and a list of items bought in the transaction. The list of items is represented by a boolean vector with a one denoting presence of corresponding item in the transaction and zero marking the absence. Figure 1 shows the boolean database of five transactions and the corresponding transaction database.
Figure 1. Boolean database and corresponding transaction database
Key Terms in this Chapter
Data Mining: Extraction of interesting, non-trivial,implicit, previously unknown and potentially useful information or patterns from data in large databases.
Data Stream: A continuous flow of data from a data source, e.g., a sensor, stock ticker, monitoring device, etc. A data stream is characterized by its unbounded size.
Association Rule: An implication of the form X ? Y, in a transactional data base with parameters support (s) and confidence (c). X and Y are set of items, s is the fraction of transactions containing X?Y and c% of transactions containing X also contain Y.
Clustering: Data mining technique to partition data objects into a set of groups such that the intra group similarity is maximized and inter group similarity is minimized.
Descriptive Mining Technique: Data mining technique that induces a model describing the characteristics of data. These techniques are usually unsupervised and totally data driven.
Classifi cation: Data mining technique that constructs a model (classifier) from historical data (training data) and uses it to predict the category of unseen tuples.
Predictive Mining Technique: Data mining technique that induces a model from historical data in supervised manner, and uses the model to predict some characteristic of new data.