Page 280 -

3:20
Page 243
2011/6/1
#1
HAN 13-ch06-243-278-9780123814791

6
Mining Frequent Patterns,

Associations, and Correlations:

Basic Concepts and Methods

Imagine that you are a sales manager at AllElectronics, and you are talking to a customer who
recently bought a PC and a digital camera from the store. What should you recommend
to her next? Information about which products are frequently purchased by your cus-
tomers following their purchases of a PC and a digital camera in sequence would be
very helpful in making your recommendation. Frequent patterns and association rules
are the knowledge that you want to mine in such a scenario.
Frequent patterns are patterns (e.g., itemsets, subsequences, or substructures) that
appear frequently in a data set. For example, a set of items, such as milk and bread, that
appear frequently together in a transaction data set is a frequent itemset. A subsequence,
such as buying first a PC, then a digital camera, and then a memory card, if it occurs fre-
quently in a shopping history database, is a (frequent) sequential pattern. A substructure
can refer to different structural forms, such as subgraphs, subtrees, or sublattices, which
may be combined with itemsets or subsequences. If a substructure occurs frequently, it is
called a (frequent) structured pattern. Finding frequent patterns plays an essential role in
mining associations, correlations, and many other interesting relationships among data.
Moreover, it helps in data classification, clustering, and other data mining tasks. Thus,
frequent pattern mining has become an important data mining task and a focused theme
in data mining research.
In this chapter, we introduce the basic concepts of frequent patterns, associations, and
correlations (Section 6.1) and study how they can be mined efficiently (Section 6.2). We
also discuss how to judge whether the patterns found are interesting (Section 6.3). In
Chapter 7, we extend our discussion to advanced methods of frequent pattern mining,
which mine more complex forms of frequent patterns and consider user preferences or
constraints to speed up the mining process.

6.1 Basic Concepts

Frequent pattern mining searches for recurring relationships in a given data set. This
section introduces the basic concepts of frequent pattern mining for the discovery of

Data Mining: Concepts and Techniques 243
c
2012 Elsevier Inc. All rights reserved.