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

clustering classification and outlier analysis [ 38 , 45 - 48 ]. Many trajectory analysis
problems can be approximately transformed to sequential pattern mining with the
use of appropriate transformations. Algorithms for spatiotemporal pattern mining
are discussed in Chap. 12.

4.3 Frequent Patterns in Graphs and Structured Data

Many kinds of chemical and biological data, XML data, software program traces,
and Web browsing behaviors can be represented as structured graphs. In these cases,
frequent pattern mining is very useful for making inferences in such data. This is
because frequent structural patterns provide important insights about the graphs.
For example, specific chemical structures result in particular properties, specific
program structures result in software bugs, and so on. Such patterns can even be
used for clustering and classification of graphs![ 14 , 73 ].
A variety of methods for structural frequent pattern mining are discussed in [ 41 ,
69 - 71 , 72 ]. A major problem in the context of graphs is the problem of isomorphism ,
because of which there are multiple ways to match two graphs. An Apriori -like
algorithm can be developed for graph pattern mining. However, because of the
complexity of graphs and and also because of issues related to isomorphism, the
algorithms are more complex. For example, in an Apriori -like algorithm, pairs of
graphs can be joined in multiple ways. Pairs of graphs can be joined when they have
( k − 1) edges in common. Furthermore, either

kind of join between a pair of graphs can have multiple results. The counting process
is also more challenging because of isomorphism. Pattern mining in graphs becomes
especially challenging when the graphs are large, and the isomorphism problem
becomes significant. Another particularly difficult case is the streaming scenario
[ 16 ] where one has to determine dense patterns in the graphs stream. Typically, these
problems cannot be solved exactly, and approximations are required.
Frequent pattern mining in graphs has numerous applications. In some cases, these
methods can be used in order to perform classification and clustering of structured
data [ 14 , 73 ]. Graph patterns are used for chemical and biological data analysis, and
software bug detection in computer programs. Methods for finding frequent patterns
in graphs are discussed in Chap. 13. The applications of graph pattern mining are
discussed in Chap. 18.

1) nodes in common, or they have ( k −

4.4 Frequent Pattern Mining with Uncertain Data

Uncertain or probabilistic data has become increasingly common over the last few
years, as methods have been designed in order to collect data with very low qual-
ity. The attribute values in such data sets are probabilistic , which implies that the
values are represented as probability distributions. Numerous algorithms have been