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

more interesting kinds of patterns. These specialized framework may use differ-
ent types of interestingness measures, model negative rules, or use constraint-based
frameworks to determine more relevant patterns.

2.1 Frequent Pattern Mining with the Traditional Support

Framework

The support framework is designed to determine patterns for which the raw frequency
is greater than a minimum threshold. Although this is a simplistic way of defining
frequent patterns, this model has an algorithmically convenient property, which is
referred to as the level-wise property. The level-wise property of frequent pattern min-
ing is algorithmically crucial because it enables the design of a bottom-up approach
to exploring the space of frequent patterns. In other words, a ( k 1)-pattern may not

be frequent when any of its subsets is not frequent. This is a crucial observation that
is used by virtually all the efficient frequent pattern mining algorithms.
Since the problem of frequent pattern mining was first proposed, numerous al-
gorithms have been proposed in order to make the solutions to the problem more
efficient. This area of research is so popular that an annual workshop FIMI was de-
voted to implementations of frequent pattern mining for a few years. This site [ 77 ]
is now organized as a repository, where many efficient implementations of frequent
pattern mining are available. The techniques for frequent pattern mining started with
Apriori -like join-based methods. In these algorithms, candidate itemsets are gener-
ated in increasing order of itemset size. The generation in increasing order of itemset
size is referred to as level-wise exploration . These itemsets are then tested against
the underlying transaction database and the frequent ones satisfying the minimum
support constraint are retained for further exploration. Eventually, it was realized that
these Apriori -like methods could be more systematically explored as enumeration
trees . This structure will be explained in detail in Chap. 2, and provides a method-
ology to perform systematic and non-redundant frequent pattern exploration. The
enumeration tree provides a more flexible framework for frequent itemset mining
because the tree can be explored in a variety of different strategies such as depth-
first, breadth-first, or other hybrid strategies [ 13 ]. One property of the breadth-first
strategy is that level-wise pruning can be used, which is not possible with other
strategies. Nevertheless, strategies such as depth-first search have other advantages,
especially for maximal pattern mining. This observation for the case of maximal
pattern mining was first stated in [ 12 ]. This is because long patterns are discovered
early, and they can be used for downward closure-based pruning of large parts of
the enumeration tree that are already known to be frequent. It should be pointed out,
that for the case where all frequent patterns are mined, the order of exploration of an
enumeration tree does not affect the number of candidates that are explored because
the size of the enumeration tree is fixed.

+