Visual data analysis in air traffic management [Elektronische Ressource] / von Frank Rehm

Sujets

• Informatik
• Handel

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2007
• Nombre de lectures: 30
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

VisualDataAnalysisin
AirTrafficManagement
Dissertation
zurErlangungdesakademischenGrades
Doktoringenieur(Dr.-Ing.)
angenommendurchdieFakultätfürInformatik
derOtto-von-Guericke-UniversitätMagdeburg
vonFRANK REHM,M.Sc.
geborenam25. März1976inDresden
Gutachter:
Prof. Dr. RudolfKruse
Prof. Dr. FrankKlawonn
Prof. Dr. KarlNachtigall
Magdeburg,den12.Februar2007Zusammenfassung
In nahezu allen Bereichen von Handel, Dienstleistung, Industrie und For-
schungwerdengroße MengenvonDatengesammelt.DerGrunddafürliegt
meistindemWunsch,dasVerhaltenvonKundenzuverstehensowietechni-
scheodernatürlichePhänomenebeschreibenbzw.vorhersagenzukönnen.
Neben der Größe solcher Datensätze, die eine Analyse ohne Unterstüt-
zung von Computern unmöglich macht, stellt die Anzahl der Attribute, die
ein Datenobjekt beschreiben, eine Herausforderung dar. WährendDatenob-
jekte,diedurchzweioderdreiAttributebeschriebensind,einfachgraphisch
dargestelltwerdenkönnen,istdieVisualisierunghoch-dimensionalerDaten
–alsoDaten,diedurchsehrvieleAttributebeschriebenwerden–nichttrivi-
al.
Das Forschungsgebiet Data Mining umfasst die Entwicklung geeigneter
Methoden zur Datenaufbereitung und Datenanalyse vor dem Hindergrund
wachsender Datenbanken mit komplexen Datensätzen. Diese Arbeit liefert
einen Beitrag auf dem Gebiet der Methodenentwicklung zur Dimensions-
reduktion und Ausreißererkennung. Ein wesentlicher Beitrag besteht in der
Visualisierung komplexer Daten, sowie der Visualisierung von Ergebnissen
verbreiteterstatistischerAnalysemethoden,wieClusteringoderFuzzy-Klas-
sifikatoren.
AmBeispielderAnalysevonFlug-undWetterdatenvomFlughafenFrank-
furt wird deutlich, welche Stärken und welche Grenzen die in dieser Arbeit
vorgestelltenMethodencharakterisieren.IndiesemBeispielsollderEinfluss
desWettersaufdieFlugzeitankommenderFlugzeuge amFrankfurter Flug-
hafen bestimmt werden. Dadurch soll die Vorhersage von Flugzeiten mög-
lichwerden,wasdie Optimierung verschiedenerAbläufe amFlughafenzu-
lässt.Abstract
Almost all branches of commerce, industry andresearch put great efforts in
collectingdatawiththeobjectivetodescribeandpredictcustomerbehaviour
orbothtechnicalandnaturalphenomena.
Besides the size of such data sets, which make manual analysis impracti-
cal, data analysis becomes challenging due to a large number of attributes
describing a data object. Whereas a graphical representation of data objects
that are describedbymeansoftwo or three attributes canbe realizedeasily,
the visualization of high-dimensional data – data that is described through
manyattributes–isnottrivial.
Thedataminingresearchareacomprisesthedevelopmentofsuitabletech-
niquesfordatapreprocessinganddataanalysistocopewiththeproblemof
aggrandizingdatabasesincludingcomplexdatasets. Thisthesiscontributes
to the domain of methodology development, dimensionality reduction and
outliertreatment. Anothermajorfocusissetonthevisualizationofcomplex
data as well as the visualization of complex results obtained from common
dataminingtechniques,e.g. clusteringandfuzzyclassifiers.
The characteristics of the proposed techniques become evident on the ex-
ampleofthe analysisofflightdataandweatherdatameasuredatFrankfurt
Airport. The objective of this application is the research of weather factors
thataffect theflightdurationofaircraft approaching Frankfurt Airport. Un-
derstanding the interrelationship between weather and flight duration per-
mitstheoptimizationofvariousprocessesattherespective airportandmay
savetimeandmoneyofcustomersandcompanies.Contents
1 Introduction 1
1.1 DataMiningandVisualization . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 ImprovingAirTrafficManagementwithDataMining . . . . . . . . . . 4
1.3 DataPresentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 DataPreprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Multidimensional Scaling and Data Navigation 11
2.1 Sammon’sMapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 ModernMultidimensionalScaling . . . . . . . . . . . . . . . . . . . . . 13
2.3 MDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15polar
2.3.1 DataPreprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 ApproximationofMDS . . . . . . . . . . . . . . . . . . . . . 18polar
2.3.3 AGreedyAlgorithmfortheApproximationofMDS . . . . 19polar
2.3.4 RelativeMDS . . . . . . . . . . . . . . . . . . . . . . . . . . . 20polar
2.3.5 WeightedMDS . . . . . . . . . . . . . . . . . . . . . . . . . . 21polar
2.3.6 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.7 VisualizingWeatherDatawithMDS . . . . . . . . . . . . . 27polar
2.4 POLARMAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 AGreedyAlgorithmfortheApproximationofPOLARMAP . . 30
2.4.2 GeneralizationofPOLARMAP . . . . . . . . . . . . . . . . . . . 32
2.4.3 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.4 VisualizingWeatherDatawithPOLARMAP . . . . . . . . . . . 41
2.5 Density-BasedMappings . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.1 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.6 NavigationThroughHigh-DimensionalData . . . . . . . . . . . . . . . 49
2.6.1 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 50Contents
3 Fuzzy Clustering and Cluster Visualization 55
3.1 Fuzzyc-meansClustering . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 PossibilisticClustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 FuzzyClusteringwithOutliers . . . . . . . . . . . . . . . . . . . . . . . 59
3.4 NoiseClustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.5 NoiseClusteringBasedOutlierDetection . . . . . . . . . . . . . . . . . 61
3.5.1 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.6 ClusterValidity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.7 VisualValidationofClusteringResults . . . . . . . . . . . . . . . . . . . 69
3.8 VisualizingSingleClusters . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.8.1 ImplementationAspects . . . . . . . . . . . . . . . . . . . . . . . 81
3.8.2 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.8.3 Discovering Weather Clusters Impacting Air Traffic Manage-
ment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.9 Prototype-BasedOutlierDetection . . . . . . . . . . . . . . . . . . . . . 88
3.9.1 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.9.2 EliminatingOutlyingWeatherData . . . . . . . . . . . . . . . . 92
4 Fuzzy Classification Rules 93
4.1 RuleClassificationVisualization . . . . . . . . . . . . . . . . . . . . . . 94
4.1.1 IllustrativeExamples . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.1.2 Visualization of Classification Rules for Flight Duration Pre-
dictionBasedonWeatherData . . . . . . . . . . . . . . . . . . . 99
5 Conclusions 105
List of Figures 109
List of Algorithms 113
A Mappings of the Weather Data 115
Bibliography 119
Index 1311 Introduction
Nowadays, data collecting is practiced in almost every domain of business
and science. Data mining or knowledge discovery is the hidden agendabe-
hindthisprocess. Ideally,onewouldinputallthecollecteddataintoablack
box which outputs all the knowledge that comprehends the data. Unfor-
tunately, this is not available until now. Indeed, the process of knowledge
extraction is all but trivial. First problems arise when experiments or mea-
surements produce data of low quality. Data mining algorithms must thus
beabletodealwithuncertaintyorimprecision.
Mostclassicaldataminingmethodsexpectahomogeneousinput. Inmany
modernapplications,however,thedatatobeanalyzedcomefromheteroge-
neous information sources. We certainly cannot expect to find data mining
algorithmsthataregenerallyapplicabletoallkindsofinformationsources.
Due to his excellent capability of visual pattern recognition, a human can
easily group data into clusters or classify different phenomena simply by
viewingthemonasheetofpaperoronacomputerscreen. Thishypothesizes
admittedly that the nature of the problem representation is 3-dimensional
at most. However, the problems we focus in this work are naturally high-
dimensional in a virtual feature space and thusly not analyzable directly by
viewingonly.
On the one hand, the issue of this work will be the visualization of prob-
lems that can be represented in a high-dimensional feature space. But we
will also provide some improvements to common techniques that mine in-
formationfromsuchlikedata.
12 1 Introduction
1.1 Data Mining and Visualization
The analysis of collected data is not a new activity. Statisticians have been
defining mathematical descriptions of data for many years. Research work
instatisticalanalysis,patternrecognitionandmachinelearningallcontribute
to data mining. Often the available data comprise only a sample from the
complete population. The aim may be to generalize from the sample to the<