Temporal Pattern Mining in Dynamic Environments Andreas D. Lattner

Temporal Pattern Mining in
Dynamic Environments
Andreas D. Lattner
Dynamic scenes with many different objects and interrelations changing over time demand complex representations. The
identification of frequent patterns and prediction rules in such scenes would be very valuable as associations in the data could
be discovered or a system’s performance could even be improved by utilizing the new information in the behavior decision
process. In this work, a novel approach to temporal pattern mining in dynamic environments has been proposed.
Many domains feature a dynamic characteristic and it would be
useful to learn temporal patterns, e.g., in logistics, sports, and
medicine. In the logistics domain, for instance, there might be
many different kinds of objects like different transport vehicles
(e.g., trucks, ships, or planes), different actors or organizations
(e.g., storages, transport companies, manufacturers), highways
or tracks, reloading points, etc. Different events can occur like
traffic jams, weather events, break down of a transport vehicle,
or delay of some goods. It would be valuable to identify repeating patterns that lead to certain situations in order to predict a
traffic jam or a delay and initiate some counter-actions in order
to avoid financial loss or penalty payments. Such a pattern could
be, for instance: If the traffic density is medium and increasing
on highway X on a Friday afternoon and the weather is rainy, it
is likely that there will follow a traffic jam on highway Y.
In the requirements analysis, different demands on representation formalisms for dynamic scenes as well as for patterns to
be mined from dynamic scenes have been identified from a soccer scenario of the RoboCup simulation league. Among other
demands the representation of objects and relations and the temporal validity of these relations have been detected to be crucial.
As various actions and events in dynamic scenes can occur concurrently, it is important that the representation also supports
this concurrency. A comprehensive investigation of the state of
the art has led to a number of relevant approaches covering parts
of the requirements. Particularly of interest were the approaches
dealing with association rule mining, especially extensions for sequential, temporal, or relational data. WARMR [3] can be used
to mine relational association rules but has no direct means to
represent the temporal dimension. The work of Höppner [5]
which addresses rule learning from interval-based temporal data
uses interval relations in order to represent temporal interrelations among states in the input data. A third relevant approach
by Lee [6] allows for mining first-order sequential rules but does
not support concurrently occurring intervals of relations.
Mining Temporal Patterns
Based on the defined requirements and on the analyzed approaches, the temporal pattern mining approach MiTemP has
been developed. It can mine temporal patterns from time intervalbased relational data and additional conceptual information about
objects and their interrelations in dynamic scenes. The relevant
concepts of the approach have been defined formally. Besides
formal definitions of dynamic scenes and their schemata as well
as definitions for patterns and prediction rules, a partial order
has been defined for the generalization relation between patterns. Following ideas of Lee [6], an optimal refinement operator
has been defined that guarantees a complete and non-redundant
generation of frequent patterns from the given representation.
In the conceptual chapter of this thesis, it has also been shown
how WARMR can be used in order to mine temporal patterns
albeit it generates many redundant ones.
The pattern mining approach is based on the association
rule mining algorithm Apriori [1]. It starts with the most general
(empty) pattern and successively performs refinement operations
to those patterns that still exceed the minimal frequency threshold. Five refinement operations have been set up: lengthening,
temporal refinement, unification, concept refinement, and instantiation. Concept restrictions can represent the information
that specific variables can only be bound to instances of certain
concepts in the concept hierarchy.
In order to represent temporal relations in patterns, a new
concise set of mutual exclusive and jointly exhaustive interval relations has been set up by combining ideas from Allen’s
and Freksa’s interval relations [2, 4]. For the interval relations
(before/after, older/younger & contemporary, head-to-head), a
composition table and an temporal reasoning algorithm has been
set up. The reason for the new set of interval relations was to
reduce complexity and to focus on important relations for prediction rules. However, the set of interval relations can be easily
replaced without changing the mining algorithm, e.g., by using
Allen’s interval relations [2].
It can easily happen that a huge number of patterns is generated. Therefore, different means to restrict the relevant pattern
space have been introduced. It is possible to disable single refinement types (e.g., no instantiation) or to restrict the maximal
refinement level. If it is known before mining that only certain
patterns with some predicates are of interest, a bias can be set
up consisting of partial conjunctive patterns. If such a bias is
defined, the patterns that are inconsistent with this bias are filtered out during pattern mining. Another way to reduce the
number of patterns is a selection of patterns to be refined at
each refinement level. In the MiTemP implementation, a random selection of n patterns can be done before the refinement
is performed.
Fig. 1 illustrates the time interval-based dynamic scene rep-
developed temporal pattern mining approach as well as the prediction rule generation. Using soccer matches from the 2D and
3D simulation league, prediction rules with average accuracies
of 70.18% and 63.46% on unseen data could be generated. Of
course, it is possible to filter out prediction rules with higher
accuracies (by increasing the minimal confidence).
The advantage of MiTemP in comparison to WARMR has
been shown; bringing in the knowledge about temporal relations
and concepts can reduce the number of patterns to be generated
(and checked during pattern matching) significantly. In an example, WARMR has generated more than 42000 patterns while
MiTemP has only created 7280 at refinement level seven.
Figure 1: Pattern and prediction rule generation
resentation and the pattern generation and matching. The area
marked by the dashed rectangle represents a sliding time window; matches of temporal patterns are restricted to fit into such
time window with a given extent.
Prediction Rule Generation
In order to utilize the identified frequent patterns for prediction,
an algorithm for prediction rule generation has been introduced.
Prediction rules are like other association rules with the restriction that the consequence of the rule must be past the precondition. As it has been shown in this thesis, this has the advantage
of only linear effort w.r.t. the conjunctive pattern size. Due to
the anti-monotonicity property of the frequency, the prediction
rule generation procedure can even be stopped if the minimal
confidence value cannot be reached any more. Thus, an efficient
method for creating prediction rules from temporal patterns has
been introduced. An example for a prediction rule is:
((pass(X, Y ), pass(Y, X)
score(X)), {(1, 2, bef ore), (1, 3,
bef ore), (2, 3, bef ore)}, {(X, object), (Y, object)}).
This prediction rule says that after X passed to Y and Y
passed to X, X will score (temporal restrictions are represented
by the indices of predicate pairs and interval relations). The
conceptual restriction {(X, object), (Y, object)} says that X and
Y must be instances of the concept object.
Furthermore, different criteria for the evaluation of prediction rules have been set up: frequency, confidence, information
value (J-measure), predicate preference, size, and specifity. The
different criteria are put together by a weighted sum to an overall evaluation value. If certain aspects should not be considered
in the measure, the corresponding weights can be set to zero.
I would like to thank my doctoral advisor Prof. Dr. Otthein
Herzog for his continuous support and his motivating as well
as inspiring comments while I have been writing this dissertation. I would also like to express my gratitude to Prof. Dr.
Stefan Wrobel for many helpful comments and the evaluation
of the thesis as the second referee. Furthermore, I want to
thank my (partly former) colleagues from the Artificial Intelligence Research Group (AG-KI) at the Universität Bremen for
many exciting discussions about their as well as my research.
Dr. Andreas D. Lattner
Johann Wolfgang Goethe-Universität (FB 12)
Information Systems and Simulation
P.O. Box 11 19 32, D-60054 Frankfurt am Main
E-mail: [email protected]
The learning approach has been implemented in XSB Prolog.
The evaluation consists of four parts: a simple example for illustration purposes, a number of experiments with synthetical
data, a comparison of WARMR and MiTemP, and the generation of prediction rules from RoboCup soccer matches. The
experiments have shown the successful implementation of the
R. Agrawal and R. Srikant. Fast algorithms for mining association
rules. In Proceedings of the 20th International Conference on
Very Large Data Bases, p. 487-499, September 1994.
J. F. Allen. Maintaining knowledge about temporal intervals.
Communications of the ACM, 26(11):832-843, November 1983.
L. Dehaspe and H. Toivonen. Discovery of frequent DATALOG patterns. Data Mining and Knowledge Discovery, 3(1):7-36,
March 1999.
C. Freksa. Temporal reasoning based on semi-intervals. Artificial
Intelligence, 54(1-2):199-227, 1992.
F. Höppner. Knowledge Discovery from Sequential Data. PhD
thesis, Technische Universität Braunschweig, 2003.
S. D. Lee. Constrained Mining of Patterns in Large Databases.
PhD thesis, Albert-Ludwigs-Universität Freiburg, 2006.
Andreas D. Lattner studied computer science at the Universität Bremen. Afterwards
he joined the Center for Computing Technologies (TZI, Universität Bremen) where he
received a doctor’s degree in 2007. He is now
working at the chair for Information Systems
and Simulation, Universität Frankfurt. His
research interests include machine learning,
temporal pattern mining, and multi-agent