An Introduction to Frequent Pattern Mining - Frequent Pattern Mining - page 1

Chapter 1
An Introduction to Frequent Pattern Mining

Charu C. Aggarwal

Abstract The problem of frequent pattern mining has been widely studied in the
literature because of its numerous applications to a variety of data mining problems
such as clustering and classification. In addition, frequent pattern mining also has
numerous applications in diverse domains such as spatiotemporal data, software bug
detection, and biological data. The algorithmic aspects of frequent pattern mining
have been explored very widely. This chapter provides an overview of these methods,
as it relates to the organization of this topic.

Keywords Frequent pattern mining · Association rules

1 Introduction

The problem of frequent pattern mining is that of finding relationships among the
items in a database. The problem can be stated as follows.
Given a database with transactions T 1 ...T N , determine all patterns P that

are present in at least a fraction s of the transactions .
The fraction s is referred to as the minimum support . The parameter s can be
expressed either as an absolute number, or as a fraction of the total number of trans-
actions in the database. Each transaction T i can be considered a sparse binary vector,
or as a set of discrete values representing the identifiers of the binary attributes that
are instantiated to the value of 1. The problem was originally proposed in the context
of market basket data in order to find frequent groups of items that are bought together
[ 10 ]. Thus, in this scenario, each attribute corresponds to an item in a superstore, and
the binary value represents whether or not it is present in the transaction. Because
the problem was originally proposed, it has been applied to numerous other applica-
tions in the context of data mining, Web log mining, sequential pattern mining, and
software bug analysis.
In the original model of frequent pattern mining [ 10 ], the problem of finding
association rules has also been proposed which is closely related to that of frequent