Temporal pattern mining in dynamic environments [Elektronische Ressource] / von Andreas D. Lattner

Andreas D. Lattner

Sujets

• Informatik

Informations

• Publié par: universitat_bremen
• Publié le: 01 janvier 2007
• Nombre de lectures: 41
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Temporal Pattern Mining in
Dynamic Environments
von Andreas D. Lattner
Dissertation
zur Erlangung des Grades eines Doktors der
Ingenieurwissenschaften
– Dr.-Ing. –
Vorgelegt im Fachbereich 3 (Mathematik & Informatik)
der Universitat Bremen¨
im M¨arz 2007Datum des Promotionskolloquiums: 30. Mai 2007
Gutachter: Prof. Dr. Otthein Herzog (Universitat Bremen)¨
Prof. Dr. Stefan Wrobel (Universit¨at Bonn)Acknowledgment
First of all, I would like to thank my doctoral advisor Prof. Dr. Otthein Herzog for his
continuous support while I have been writing this dissertation. His motivating and
inspiring – usually also challenging – comments in our meetings have been extremely
valuable to improve this work and to accelerate the progress. I am very grateful that
he gave me the opportunity and the support in conducting my research.
I would also like to express my gratitude to Prof. Dr. Stefan Wrobel, not only
for evaluating my thesis, but also for the kind invitation to the Fraunhofer IAIS
in Sankt Augustin for presenting my work and the many helpful comments and for
fruitful discussions with him and his colleagues.
Furthermore, I want to thank my (partly former) colleagues from the Artificial
Intelligence Research Group (AG-KI) at the Universitat Bremen for many exciting¨
discussions about their as well as my research. Especially, I would like to thank
Prof. Dr. Ingo J. Timm (now working at the Johann Wolfgang Goethe-Universitat,¨
Frankfurt am Main) and Prof. Dr. Holger Wache (University of Applied Sciences
Northwestern Switzerland, Olten, Switzerland) for the scientific discussions, their
support with Prolog, and many motivating words during the ups and downs of a
PhD student. I am also very grateful to my other colleagues for giving many valuable
comments on my work and for proof-reading parts of my dissertation. In alphabetical
order I would like to thank Hanna Bauerdick, Jan D. Gehrke, Dr. Bj¨orn Gottfried,
Dr. Peter Knirsch (Theoretical Computer Science Research Group, Universitat Bre-¨
men), and J¨orn Witte. I would also like to thank Dr. Andrea Miene (Faserinstitut
Bremen e.V.) for providing the RoboCup 2D simulation league matches analyzed
in her dissertation. My special thanks go to Dr. Thomas Wagner for mental and
physical support – in the form of continuous supply of caffeinated liquids – sharing
the room with me in the final phase of my dissertation. I would also like to thank
Dr. Tom Wetjen (BASF, Ludwigshafen) for sharing his knowledge how to nicely
Apresent algorithms with LT X.E
I want to express my deep gratitude to the Virtual Werder 3D team, namely
Carsten Rachuy, Arne Stahlbock, PD Dr. Ubbo Visser, and Tobias Warden, for
their great effort in our RoboCup project. Special thanks go to Carsten Rachuy for
extending the SeqDraw program and to Tobias Warden for the implementation of
the FactProducer which have been used in this dissertation.
iiiiv Acknowledgment
There are many people scattered around the world who supported me while writ-
ing this thesis. I would like to express my gratitude to Prof. Dr. Frank H¨oppner
(Fachhochschule Braunschweig / Wolfenbuttel)¨ for interesting discussions about sup-
port computations. I also would like to thank Dr. Jan Struyf (Declarative Languages
and Artificial Intelligence research group of the Katholieke Universiteit Leuven, Bel-
gium) for his support w.r.t. ACE/WARMR as well as his colleagues Dr. Hendrik
Blockeel and Dr. Luc Dehaspe for providing ACE. I am also very grateful to Dr.
Terrance Swift (State University of New York at Stony Brook, USA) for his imme-
diate help with XSB Prolog. Furthermore, I would like to thank Dr. Guido Cervone
(George Mason University, Fairfax, VA, USA) for great scientific discussions during
our various journeys through Europe and America.
Last but not least, I would like to thank my friends and family for all their
support and understanding during this challenging period of my life. They have
convinced me that there are many other problems and pleasures beyond scientific
ones. I am deeply indebted to Mine Hartog for her unlimited, sacrificial support in
every sense and I want to thank her for the permanent warmth she has been giving
to me.
Bremen, March 2007
Andreas D. LattnerContents
1 Introduction 1
1.1 GoalandResearchQuestions ...................... 3
1.2 ClassificationofthisStudy ........................ 4
1.3 OverviewoftheWork .......................... 5
2 Preliminaries and Requirement Analysis 7
2.1 Basics ................................... 7
2.1.1 Machine Learning and Data Mining............... 7
2.1.2 AgentsinDynamicEnvironments ................ 11
2.2 Scenarios.................................. 13
2.2.1 RoboCup3DSimulationLeague................. 13
2.2.2 Typical Soccer Situations .................... 15
2.3 Problem Description ........................... 17
2.4 Requirements ............................... 20
2.4.1 Representational Issues...................... 20
2.4.2 GenerationofaQualitativeAbstraction ............ 23
2.4.3 Pattern Matching ......................... 24
2.4.4 SearchforFrequentPatterns................... 25
2.4.5 SituationPrediction ....................... 26
2.4.6 PredictionRuleEvaluation.................... 26
3 State of the Art 27
3.1 Learning Approaches ........................... 27
3.1.1 Supervised Inductive Logic Programming . . .......... 28
3.1.2 Frequent Pattern Mining and Association Rule Mining .... 32
3.1.3 Similarity-based Approaches ................... 47
3.1.4 Reinforcement Learning ..................... 51
3.1.5 Probability-based Approaches .................. 55
3.1.6 ArtificialNeuralNetworks .................... 58
3.2 Representation of Dynamic Scenes 60
3.2.1 QualitativeRepresentationsofSpaceandTime ........ 61
vvi CONTENTS
3.2.2 Formalisms for Representing Actions, Events, and Time.... 64
3.2.3 Approaches to Motion Description and Applications...... 67
3.3 Discussion ................................. 73
4 MiTemP: Mining Temporal Patterns 79
4.1 Basic Definitions ............................. 79
4.2 TemporalRelations ............................ 94
4.3 Support Computation .......................... 97
4.3.1 Discussion of Variants for Support Computation ........ 98
4.3.2 Pattern Matching .........................102
4.3.3 Support and Frequency Definition................104
4.4 GeneralizationsandSpecializationsofPatterns.............105
4.5 Pattern Mining ..............................111
4.5.1 OptimalRefinementOperator ..................111
4.5.2 Application of Knowledge ....................119
4.5.3 Temporal Pattern Mining Algorithms . . . ...........124
4.5.4 Complexity Examination .....................132
4.6 Mining Temporal Patterns with WARMR ...............136
4.6.1 Learning Task Definition in WARMR . . .136
4.6.2 Transformation of the Learning Task . . . ...........137
4.6.3 Sample Representation ......................140
4.6.4 Discussion .............................143
5 Prediction Rule Generation 145
5.1 FromPatternstoPredictionRules ...................145
5.2 EvaluationofPredictionRules151
5.3 Application of Prediction Rules .....................154
6 Evaluation 157
6.1 A Simple Example ............................158
6.2 ExperimentswithSyntheticData ....................162
6.3 ComparisonofWARMRandMiTemP .................174
6.4 Learning Prediction Rules from RoboCup Matches . . ........182
6.5 Discussion .................................189
7 Summary and Perspective 191
Bibliography 197
A Symbols 215CONTENTS vii
B Evaluation Data on the DVD 217
B.1 Simple Example..............................217
B.2 SyntheticData217
B.2.1 Varying Minimal Frequency ...................218
B.2.2 VaryingNumberofConcepts ..................219
B.2.3 VaryingNumberofInstances219
B.2.4 VaryingPatternSizes.......................220
B.2.5 Varying Number of Predicate Templates . ...........220
B.2.6 VaryingNumberofPredicates221
B.2.7 Varying Window Size222
B.3 ComparisonofWARMRandMiTemP .................222
B.4 RoboCupExperiments ..........................223
B.5 2DSimulationLeague223
B.6 3DSimulationLeague224
Index 229viii CONTENTSList of Figures
2.1 Agentarchitecture ............................ 11
2.2 Learning agent (adapted from [RN03, p. 53]).............. 12
2.3 RoboCup3Dsimulationleague ..................... 14
2.4 Kick effector of an agent in the RoboCup 3D simulation league.... 14
2.5 Illustration of an attack in a RoboCup soccer match . . ........ 15
2.6 Exemplary illustration with validity intervals 16
2.7 E of a pattern ................... 18
2.8 Sliding window for pattern matching .................. 24
3.1 Example of a learned first-order decision tree.............. 31
3.2 Allen’s temporal relations [All83] .................... 61
3.3 Freksa’s semi-interval relationships [Fre92a]............... 62
3.4 Example for qualitative distance and direction classes . ........ 63
3.5 Region Connection Calculus (RCC-8) [RCC92]............. 63
3.6 Freksa’sorientationgrid[Fre92b] 64
3.7 Conditions for stacking x on y [AF94].................. 67
3.8 Threshold-basedandmonotonicity-basedsegmentation[Mie04].... 72
4.1 Illustration of a concept hierarchy .................... 81
4.2 I o