Dissertations / Theses on the topic 'Spatio-temporal trajectories'

La croissance rapide et la complexité de nombreuses villes contemporaines offrent de nombreux défis de recherche pour les scientifiques à la recherche d'une meilleure compréhension des mobilités qui se produisent dans l'espace et dans le temps. A l’heure où de très grandes séries de données de trajectoires en milieu urbain sont disponibles grâce à profusion de nombreux capteurs de positionnement et de services de nombreuses et nouvelles opportunités de recherche et d’application nous sont offertes. Cependant, une bonne intégration de ces données de mobilité nécessite encore l'élaboration de cadres méthodologiques et conceptuels tout comme la mise en oeuvre de bases de données spatio-temporelles qui offriront les capacités appropriées de représentation et de manipulation des données. La recherche développée dans cette thèse introduit une modélisation conceptuelle et une approche de gestion de base de données spatio-temporelles pour représenter et analyser des trajectoires humaines dans des espaces urbains. Le modèle considère les dimensions spatiales, temporelles et sémantiques afin de tenir compte de l’ensemble des propriétés issues des informations de mobilité. Plusieurs abstractions de données de mobilité et des outils de manipulation de données sont développés et expérimentés à partir d’une large base de données de trajectoires disponibles dans la ville de Pékin. L'intérêt de l'approche est double: il montre d’une part que de larges ensembles de données de mobilité peuvent être intégrés au sein de SGBD spatiotemporels extensibles; d’autre part des outils de manipulation et d’interrogation spécifiques peuvent être dérivés à partir de fonctions intégrées au sein d’un langage d’interrogation. Le potentiel de l’approche est illustré par une série d’interrogations qui montrent comment à partir d’une large base de données de trajectoires quelques patrons de déplacements peuvent être obtenus
Massive trajectory datasets generated in modern cities generate not only novel research opportunities but also important methodological challenges for academics and decision-makers searching for a better understanding of travel patterns in space and time. This PhD research is oriented towards the conceptual and GIS-based modeling of human displacements derived from large sets of urban trajectories. The motivation behind this study originates from the necessity to search for and explore travel patterns that emerge from citizens acting in the city. Our research introduces a conceptual modelling framework whose objective is to integrate and analyze human displacements within a GIS-based practical solution. The framework combines conceptual and logical models that represent travel trajectories of citizens moving in a given city. The whole approach has been implemented in a geographical database system, experimented in the context of transportation data, and enriched by a series of query interface manipulations and specific functions that illustrate the potential of our whole framework for urban studies. The whole framework has been experimented on top of the Geolife project and large trajectories datasets available in the city of Beijing. Overall, the findings are twofold: first, it appears that our modelling framework can appropriately act as an extensible geographical database support for the integration of large trajectory datasets; second the approach shows that several emerging human displacements can be explored from the manipulation of large urban trajectories

Por causa da grande quantidade de dados de trajetórias producidos por dispositivos móveis, existe um aumento crescente das necessidades de mecanismos para extrair conhecimento a partir desses dados. A maioria dos trabalhos existentes focam nas propriedades geometricas das trajetorias, mas recentemente surgiu o conceito de trajetórias semânticas, nas quais a informação da geografia por baixo da trajetória é integrada aos pontos da trajetória. Nesse novo conceito, trajetórias são observadas como um conjunto de stops e moves, onde stops são as partes mais importantes da trajetória. Os stops e moves são computados pela intersecção das trajetórias com o conjunto de objetos geográficos dados pelo usuário. Nessa dissertação será apresentada uma solução alternativa a descoberta de stops, com a capacidade de achar lugares de interesse que não são esperados pelo usuário. A solução proposta é um método de clusterização espaço-temporal, baseado na velocidade, para ser aplicado em uma trajetória. Foram comparadas duas abordagens diferentes com experimentos baseados em dados reais e mostrado que a computação de stops usando o conceito de velocidade pode ser interessante para várias applicações.
Because of the large amount of trajectory data produced by mobile devices, there is an increasing need for mechanisms to extract knowledge from this data. Most existing works have focused on the geometric properties of trajectories, but recently emerged the concepts of semantic trajectories, in which the background geographic information is integrated to trajectory sample points. In this new concept, trajectories are observed as a set of stops and moves, where stops are the most important parts of the trajectory. Stops and moves have been computed by testing the intersection of trajectories with a set of geographic objects given by the user. In this dissertation we present an alternative solution with the capability of finding interesting places that are not expected by the user. The proposed solution is a spatio-temporal clustering method, based on speed, to work with single trajectories. We compare the two different approaches with experiments on real data and show that the computation of stops using the concept of speed can be interesting for several applications.

La recherche développée dans cette thèse introduit une approche qualitative pour représenter et raisonner à partir d'entités spatiales dans un espace géographique à deux dimensions. Les patrons de mouvements entre entités dynamiques sont catégorisés à partir d'un modèle qualitatif de relations topologiques entre une ligne orientée et une région, et de relations d'orientation entre deux lignes orientées, respectivement. Les mouvements qualitatifs sont dérivés à partir de relations spatio-temporelles qui caractérisent des entités dynamiques conceptualisées comme des points ou des régions dans un espace à deux dimensions. Cette architecture de raisonnement permet de dériver des configurations de mouvements basiques dérivées à partir d'entités statiques et dynamiques. L'approche est complétée par une qualification de ces configurations à partir d'expressions du langage naturel. Les compositions de mouvements sont étudiées tout comme les transitions possibles dans des cas de données incomplètes. Les tables de compositions sont également explorées et permettent d'étendre les possibilités de raisonnement. Le modèle est expérimenté dans le contexte de l'analyse de trajectoires aériennes et maritimes
The research developed in this thesis introduces a qualitative approach for representing and reasoning on moving entities in a two-dimensional geographical space. Movement patterns of moving entities are categorized based on a series of qualitative spatial models of topological relations between a directed line and a region, and orientation relations between two directed lines, respectively. Qualitative movements are derived from the spatio-temporal relations that characterize moving entities conceptualized as either points or regions in a two-dimensional space. Such a spatio-temporal framework supports the derivation of the basic movement configurations inferred from moving and static entities. The approach is complemented by a tentative qualification of the possible natural language expressions of the primitive movements identified. Complex movements can be represented by a composition of these primitive movements. The notion of conceptual transition that favors the exploration of possible trajectories in the case of incomplete knowledge configurations is introduced and explored.Composition tables are also studied and provide additional reasoning capabilities. The whole approach is applied to the analysis of flight patterns and maritime trajectories

This project was a step forward in applying statistical methods and models to provide new insights for more informed decision-making at large spatial scales. The model has been designed to address complicated effects of ecological processes that govern the state of populations and uncertainties inherent in large spatio-temporal datasets. Specifically, the thesis contributes to better understanding and management of the Great Barrier Reef.

Alors que la continuité du bâti ne suffit plus pour appréhender l’espace urbain d’aujourd’hui,la discontinuité du tissu urbain est devenue une clé de compréhension de la ville contemporaine et de sonprocessus de formation. Elle suscite l'intérêt des chercheurs, d'autant plus que le déploiement des systèmesd'information géographique offre de nouvelles perspectives de mesure des formes urbaines. Mais, si lestravaux en écologie du paysage ou en géographie permettent de mesurer l'émergence de ces formesdiscontinues, il nous semble important de nous intéresser aux fondements économiques de l'urbanisationdiscontinue qui commencent à faire l’objet de travaux empiriques en économie. La constitution d’une grillede lecture de l’urbanisation discontinue nous permet de comprendre de manière concomitante la formationdes espaces périurbains et les formes de développement de l’habitat à l’échelle parcellaire. Cette rechercheest appliquée au Limousin sur la période 1950-2009. Le prisme de la discontinuité nous apporte un éclairagesur les trajectoires de développement résidentiel des communes de cette région. La construction d’une basede données spatio-temporelles nous offre la possibilité de lire ces trajectoires à partir de l’association demesures de dispersion géographique et de dispersion morphologique de l’habitat. À partir de ces mesuresde dispersion, nous abordons l’articulation des logiques fonctionnelles et morphologiques du développementrésidentiel grâce à la construction d’une base de données multithématiques. Pour comprendre les schémasde localisation des ménages, nous analysons plus particulièrement les problématiques de la production deslogements, de l’interaction entre structure foncière et régulation publique à l’échelle des communes et del’influence des aménités et désaménités des espaces urbains et ruraux sur la dispersion de l’habitat
While understanding urban areas through continuity of developed land reached its limits,discontinuity of urban fabrics has become a key to understand today's cities and their shaping dynamics. Itraises researchers’ interest especially as GIS development gives new opportunities to measure urbanpatterns. While researches in landscape ecology or geography allow to measure discontinuous patterns, itseems to be important to focus on their economic foundations which are a matter for recent empiricalresearches in economy. The construction of an analytical grid of discontinuous urban patterns allows tounderstand simultaneously peri-urban development and patterns of residential development at the parcellevel. This research is applied to the Limousin region on the 1950-2009 period. The focus on discontinuousurban patterns sheds light on residential trajectories of the Limousin region's communes. The proposal of aspatio-temporal data base allows to understand these trajectories through combined measures of geographical dispersion and morphological dispersion. With these measures, we broach the link betweenfunctional and morphological dynamics thanks to a multitheme data base. To understand household locationand residential dispersion, we analyze the issue of housing production, the interaction between property andpublic regulation at the scale of communes, the influence of amenities and desamenities of urban and ruralspaces

Cette thèse présente un cadre de travail d'analyse de trajectoires contenant une phase de prétraitement et un processus d’extraction de trajectoires d’objets mobiles. Le cadre offre des fonctions visuelles reflétant le comportement d'évolution des motifs de trajectoires. L'originalité de l’approche est d’allier extraction de motifs fréquents, extraction de motifs émergents et analyse formelle de concepts pour analyser les trajectoires. A partir des données de trajectoires, les méthodes proposées détectent et caractérisent les comportements d'évolution des motifs. Trois contributions sont proposées : Une méthode d'analyse des trajectoires, basée sur les concepts formels fréquents, est utilisée pour détecter les différents comportements d’évolution de trajectoires dans le temps. Ces comportements sont “latents”, "emerging", "decreasing", "lost" et "jumping". Ils caractérisent la dynamique de la mobilité par rapport à l'espace urbain et le temps. Les comportements détectés sont visualisés sur des cartes générées automatiquement à différents niveaux spatio-temporels pour affiner l'analyse de la mobilité dans une zone donnée de la ville. Une deuxième méthode basée sur l'extraction de concepts formels séquentiels fréquents a également été proposée pour exploiter la direction des mouvements dans la détection de l'évolution. Enfin, une méthode de prédiction basée sur les chaînes de Markov est présentée pour prévoir le comportement d’évolution dans la future période pour une région. Ces trois méthodes sont évaluées sur ensembles de données réelles . Les résultats expérimentaux obtenus sur ces données valident la pertinence de la proposition et l'utilité des cartes produites
This dissertation presents a trajectory analysis framework, which includes both a preprocessing phase and trajectory mining process. Furthermore, the framework offers visual functions that reflect trajectory patterns evolution behavior. The originality of the mining process is to leverage frequent emergent pattern mining and formal concept analysis for moving objects trajectories. These methods detect and characterize pattern evolution behaviors bound to time in trajectory data. Three contributions are proposed: (1) a method for analyzing trajectories based on frequent formal concepts is used to detect different trajectory patterns evolution over time. These behaviors are "latent", "emerging", "decreasing", "lost" and "jumping". They characterize the dynamics of mobility related to urban spaces and time. The detected behaviors are automatically visualized on generated maps with different spatio-temporal levels to refine the analysis of mobility in a given area of the city, (2) a second trajectory analysis framework that is based on sequential concept lattice extraction is also proposed to exploit the movement direction in the evolution detection process, and (3) prediction method based on Markov chain is presented to predict the evolution behavior in the future period for a region. These three methods are evaluated on two real-world datasets. The obtained experimental results from these data show the relevance of the proposal and the utility of the generated maps

Cette thèse présente un cadre de travail d'analyse de trajectoires contenant une phase de prétraitement et un processus d’extraction de trajectoires d’objets mobiles. Le cadre offre des fonctions visuelles reflétant le comportement d'évolution des motifs de trajectoires. L'originalité de l’approche est d’allier extraction de motifs fréquents, extraction de motifs émergents et analyse formelle de concepts pour analyser les trajectoires. A partir des données de trajectoires, les méthodes proposées détectent et caractérisent les comportements d'évolution des motifs. Trois contributions sont proposées : Une méthode d'analyse des trajectoires, basée sur les concepts formels fréquents, est utilisée pour détecter les différents comportements d’évolution de trajectoires dans le temps. Ces comportements sont “latents”, "emerging", "decreasing", "lost" et "jumping". Ils caractérisent la dynamique de la mobilité par rapport à l'espace urbain et le temps. Les comportements détectés sont visualisés sur des cartes générées automatiquement à différents niveaux spatio-temporels pour affiner l'analyse de la mobilité dans une zone donnée de la ville. Une deuxième méthode basée sur l'extraction de concepts formels séquentiels fréquents a également été proposée pour exploiter la direction des mouvements dans la détection de l'évolution. Enfin, une méthode de prédiction basée sur les chaînes de Markov est présentée pour prévoir le comportement d’évolution dans la future période pour une région. Ces trois méthodes sont évaluées sur ensembles de données réelles . Les résultats expérimentaux obtenus sur ces données valident la pertinence de la proposition et l'utilité des cartes produites
This dissertation presents a trajectory analysis framework, which includes both a preprocessing phase and trajectory mining process. Furthermore, the framework offers visual functions that reflect trajectory patterns evolution behavior. The originality of the mining process is to leverage frequent emergent pattern mining and formal concept analysis for moving objects trajectories. These methods detect and characterize pattern evolution behaviors bound to time in trajectory data. Three contributions are proposed: (1) a method for analyzing trajectories based on frequent formal concepts is used to detect different trajectory patterns evolution over time. These behaviors are "latent", "emerging", "decreasing", "lost" and "jumping". They characterize the dynamics of mobility related to urban spaces and time. The detected behaviors are automatically visualized on generated maps with different spatio-temporal levels to refine the analysis of mobility in a given area of the city, (2) a second trajectory analysis framework that is based on sequential concept lattice extraction is also proposed to exploit the movement direction in the evolution detection process, and (3) prediction method based on Markov chain is presented to predict the evolution behavior in the future period for a region. These three methods are evaluated on two real-world datasets. The obtained experimental results from these data show the relevance of the proposal and the utility of the generated maps

Les dernières années, la taille des collections vidéo a connu une forte augmentation. La recherche et la navigation efficaces dans des telles collections demande une indexation avec des termes pertinents, ce qui nous amène au sujet de cette thèse, l'indexation sémantique des vidéos. Dans ce contexte, le modèle Sac de Mots (BoW), utilisant souvent des caractéristiques SIFT ou SURF, donne de bons résultats sur les images statiques. Notre première contribution est d'améliorer les résultats des descripteurs SIFT/SURF BoW sur les vidéos en pré-traitant les vidéos avec un modèle de rétine humaine, ce qui rend les descripteurs SIFT/SURF BoW plus robustes aux dégradations vidéo et qui leurs donne une sensitivité à l'information spatio-temporelle. Notre deuxième contribution est un ensemble de descripteurs BoW basés sur les trajectoires. Ceux-ci apportent une information de mouvement et contribuent vers une description plus riche des vidéos. Notre troisième contribution, motivée par la disponibilité de descripteurs complémentaires, est une fusion tardive qui détermine automatiquement comment combiner un grand ensemble de descripteurs et améliore significativement la précision moyenne des concepts détectés. Toutes ces approches sont validées sur les bases vidéo du challenge TRECVid, dont le but est la détection de concepts sémantiques visuels dans un contenu multimédia très riche et non contrôlé.

Dans ce travail, nous développons des méthodes statistiques pour modéliser la progression de la Maladie de Parkinson (MP) à partir de données répétées. La progression de la MP, très hétérogène, est complexe à modéliser. Pour mieux comprendre la progression des maladies neurodégénératives, des études effectuent un suivi de patients dans le temps, avec une batterie de tests à chaque visite. Ces données permettent d’étudier les différents types de progression par analyse statistique. Dans une première partie, nous modélisons la progression de marqueurs scalaires de la maladie de Parkinson. Nous nous basons sur un modèle longitudinal, le modèle longitudinal spatiotemporel. Nous proposons de gérer les valeurs manquantes, ainsi que de modéliser la progression jointe de marqueurs de différentes natures, comme les scores cliniques, ou les marqueurs extraits de l’imagerie. Avec ce modèle, nous nous concentrons d'abord sur la modélisation des symptômes moteurs précoces dans la MP. Puis nous étudions l'hétérogénéité de la MP, avec un accent sur les troubles du sommeil. Dans une seconde partie indépendante, nous étudions la modélisation de données longitudinales provenant de l'imagerie. Nous proposons d'utiliser un réseau de neurone comme méthode de réduction de dimension afin de construire un système de coordonnées spatiotemporel de progression de la maladie. Nous tirons parti de la flexibilité des réseaux de neurones pour modéliser la progression de données multimodales. Enfin, en supposant la monotonicité des marqueurs au cours du temps, nous nous appuyons sur l’ordre des visites plutôt que l’âge des patients pour modéliser plus finement la variabilité temporelle de nos données
In this work, we developed statistical methods to model disease progression from patient’s repeated measurements, with a focus on Parkinson’s Disease (PD). A key challenge lies in the inherent heterogeneity of PD across patients, to the extent that PD is now suspected to encompass multiple subtypes or motor phenotypes. To gain insights on disease progression, research studies propose to gather a broad range of marker measurements, at multiple timepoints for each patients. These data allow to investigate the disease’s patterns of progression via statistical modeling. In a first part, we modeled the progression of scalar markers of PD. We extended on a disease progression model, namely the longitudinal spatiotemporal model. We then proposed to address data missingness, and to model the joint progression of markers of different nature, such as clinical scores, and scalar measurements extracted on imaging modalities. With this method, we modeled early motor progression in PD, and, in a second work, the heterogeneity of idiopathic PD progression, with a focus on sleep symptoms. In a second, independent, part of the manuscript, we tackled the longitudinal modeling of medical images. For these higher dimensionality data, Deep Learning is often used, but mostly in cross sectional setups, ignoring the possible inner dynamics. We proposed to leverage Deep Learning as a dimensionality reduction tool to build a spatiotemporal coordinate system of disease progression. We first took advantage of this flexibility to handle multimodal data. Then we leveraged the self-supervision induced by assuming monotonicity over time, to offer higher flexibility in modeling temporal variability

It is now possible to track moving entities such as humans, animals, or vehicles at relatively high sampling-rates, over long durations of time. This produces large, detailed spatio-temporal trajectories that contain millions of geographic positions and timestamps. These large spatio-temporal trajectories capture the potentially-interesting behaviours of individual entities; they are prime candidates for data mining and knowledge discovery. However, within the trajectory data mining and knowledge discovery process I have identified four challenges that hinder the discovery of succinct and semantically meaningful trajectory patterns: spatial uncertainty, trajectory complexity, pattern complexity, and semantic meaning. The first challenge, spatial uncertainty, is present in many GPS trajectories. As the global positioning technology used to record trajectories is not entirely accurate, it produces noisy recordings for various reasons: antenna quality, satellite availability, and multi-path errors, inclusively. This extra noisiness in the data makes trajectories more difficult to efficiently mine; it increases the likelihood of discovering false patterns, also, potentially, masking real patterns. The second challenge, trajectory complexity, refers to the large size and redundancy that is now typical due to the high sampling-rate and long-duration of real-world trajectory data collection. High sampling-rates and long durations are both effective techniques to increase the likelihood of capturing more patterns. I expect that trajectories will be sampled at increasingly higher rates, over longer durations, especially due to the low cost of storage and advances in battery technology. Decreasing the sampling-rate or duration is not an ideal solution because it arbitrarily reduces the amount of information captured. Unsimplified, however, these large trajectories do significantly slow down and complicate the mining process; as we mine increasingly larger trajectory datasets a solution is increasingly important. Pattern complexity is the third challenge, and occurs because many existing trajectory data mining approaches produce pattern outputs that are not succinct or easily interpretable. In fact, the pattern outputs are sometimes so large they can overload the user and make knowledge discovery overly time consuming. Typically, to make sense of such trajectory patterns a human operator is required to use their expertise to further filter the results or manually select key patterns to represent supposed general trends. Ideally, mined trajectory patterns should be succinct enough that any post-processing by a human operator would needlessly discard information: if additional processing is required to aid pattern interpretation, that processing is far better suited as a step in the mining process. Semantic meaning refers to the inherent absence of any contextual information present in raw spatio-temporal trajectories; it is the fourth challenge. Typically, raw spatio-temporal trajectories only record the geographic location with a time-stamp. Mining these raw spatio-temporal trajectories alone, limits the type of discoverable patterns. To uncover knowledge beyond pure movement patterns, extra contextual information that is semantically meaningful, in the application domain, is required. Each type of semantic information that could be inferred or combined with trajectories, presents a unique challenge. Overall, the aim of this thesis is to investigate solutions to these four challenges to ultimately produce succinct and semantically meaningful trajectory patterns. To do so I divided the thesis into four parts and in each part I addressed some combination of these four challenges at various stages in the trajectory data mining and knowledge discovery process. In the first, I investigated a pre-processing solution that addresses the challenge of trajectory complexity. Specifically, I introduced a framework to create spatio-temporal trajectory simplification approaches. Using this framework I created several spatio-temporal simplification algorithms based on well-known poly-line simplification techniques, evaluating them using multiple real-world trajectory datasets. The results indicated that a number of the simplification algorithms produced were both efficient and effective at reducing the trajectory complexity of the tested real-world trajectories. Second, I investigated a sequential pattern mining approach that addresses all four challenges in the context of vehicle trajectories. They were chosen for this section because they are simpler to process: they are constrained, in that they only travel underlying road networks. In this approach, I map-matched several real-world vehicle trajectory datasets onto road networks, thus removing their spatial uncertainty, reducing their complexity, and transforming them into a series of semantically meaningful street names. When using traditional sequential pattern mining approaches, mining these large, yet highly redundant sequences produced far too many patterns; meaningful interpretation became impossible. Thus, to overcome the challenge of pattern complexity I mined the sequences using an algorithm I created called DC-SPAN. DC-SPAN mines a highly succinct, but lossy, set of contiguous patterns where the user can control the sub-sequence redundancy of the pattern output. Experiment results on real-world bus trajectories showed that compared to existing contiguous sequential pattern mining approaches DC-SPAN was able to achieve as much a 98% compression in its pattern output while trading off only a 20% increase in lossiness. The results of this section were promising, but ultimately, largely specific to the vehicle trajectory domain. In the third part I introduced a pre-processing approach called POSMIT. POSMIT annotates each spatio-temporal entry, in a trajectory, with a semantic label indicating whether the entity was stopping or moving within that recording. This semantic stop/move label is a step towards the challenge of enriching raw trajectories with semantic meaning because it can be used to infer further semantic information later in the trajectory data mining process. For example, an extended subsequence of stopping entries occurring inside a restaurant may indicate that the tracked entity was dining. Existing stop/move classification approaches are based on geographic and clustering-based concepts. These approaches definitively label each entry as a stop or a move, meaning that the accuracy of the resulting classification is strongly linked to the user's ability to estimate the required parameters. Conversely, POSMIT computes the probability that a given entry is stopping; then, stopping entries with probabilities below a user-specified threshold are filtered out and become moves. Unlike existing approaches, this feature of POSMIT allows users to tend the result towards having less false-positive stop classifications, which is important in applications like data mining where false-positives can lead to false patterns. The experiment results on real-world ground-truth stop/move annotated trajectories revealed that, compared to the existing approaches that were tested, POSMIT achieved a higher classification accuracy while also being more robust in parameter selection. Finally, I used several concepts from the previous sections, both directly and indirectly, and introduced STOSEM: an overall semantic trajectory data mining approach that addresses all four of the identified challenges. STOSEM begins by using POSMIT to enrich each trajectory with stop/move information. Then, STOSEM proceeds to cluster these stop/move annotated trajectories into sequences of extended stop episodes. Clustering the individual recordings into stop episodes greatly reduces the raw trajectory complexity, neatly handling the problem of spatial uncertainty by representing many stopping entries within a single stop radius. After the stop episode formulation STOSEM then incorporates a repository of real-world places. This addresses the challenge of semantic meaning: all nearby real-world places are associated with relevant stop episodes to build a list of candidate places where the stop may have actually occurred. STOSEM, then, proceeds to match each sequence of stop episodes to its likely sequence of visited real-world places, using a probabilistic place-matching algorithm. In general, STOSEM's steps, as described thus far, essentially transform each raw trajectory into a discrete, succinct, and human readable series of place visitations that describe the journey of each tracked individual. This transformation makes data mining simple because this sequence of places is an ideal input for traditional frequent itemset and sequential pattern mining algorithms while remaining succinct enough to avoid the issue of pattern complexity. To evaluate the efficiency and effectiveness of STOSEM I performed quantitative experiments using real-world and synthetic datasets. Some key findings from the quantitative experiments include: that the stop episode clustering is an effective simplification technique that preserves semantic meaning; that the proposed probabilistic place-matching approach was more accurate than the non-probabilistic approaches I tested. Additionally, to empirically test the applicability of STOSEM I performed a case study using a real-world human trajectory dataset called Geolife. The case study revealed that mining these place visitations, using traditional frequent itemset and sequential pattern mining algorithms, produced succinct and semantic trajectory pattern output. A key finding from the patterns was the existence of certain kinds of participants, such as University attendees and Microsoft employees: both specific participant demographics reported by the original Geolife researchers. Another key finding was the observed behaviours of certain kinds of participants, based on their visitations. For example, some participants seemingly revealed their University attendance timetables through their collected trajectories. These kinds of results, extracted neatly from raw spatio-temporal trajectories are very encouraging and motivate us to extend this approach to future works. This technique could also uncover move episodes between extended stops; they could then be classified into the likely mode of transport being used (i.e. car, bus, walking etc.). Overall, this study produced several approaches that addressed the challenges of spatial uncertainty, trajectory complexity, pattern complexity, and semantic meaning across multiple real-world trajectory data mining problems. In particular, my cumulative work on STOSEM addresses all challenges, producing succinct and semantically meaningful patterns for real-world human trajectory datasets.

Dissertation submitted in partial fulfilment of the requirements for the degree of Master of Science in Geospatial Technologies
The increasing frequency of use location-acquisition technology like the Global Positioning System is leading to the collection of large spatio-temporal datasets. The prospect of discovering usable knowledge about movement behavior, which encourages for the discovery of interesting relationships and characteristics users that may exist implicitly in spatial databases. Therefore spatial data mining is emerging as a novel area of research. In this study, the experiments were conducted following the Knowledge Discovery in Database process model. The Knowledge Discovery in Database process model starts from selection of the datasets. The GPS trajectory dataset for this research collected from Microsoft Research Asia Geolife project. After taking the data, it has been preprocessed. The major preprocessing activities include:  Fill in missed values and remove outliers;  Resolve inconsistencies, integration of data that contains both labeled and unlabeled datasets,  Dimensionality reduction, size reduction and data transformation activity like discretization tasks were done for this study. A total of 4,273 trajectory dataset are used for training the models. For validating the performance of the selected model a separate 1,018 records are used as a testing set. For building a spatiotemporal model of this study the K-nearest Neighbors (KNN), decision tree and Bayes algorithms have been tasted as supervised approach. The model that was created using 10-fold cross validation with K value 11 and other default parameter values showed the best classification accuracy. The model has a prediction accuracy of 98.5% on the training datasets and 93.12% on the test dataset to classify the new instances as bike, bus, car, subway, train and walk classes. The findings of this study have shown that the spatiotemporal data mining methods help to classify user mobility transportation modes. Future research directions are forwarded to come up an applicable system in the area of the study.

abstract: With the rapid development of mobile sensing technologies like GPS, RFID, sensors in smartphones, etc., capturing position data in the form of trajectories has become easy. Moving object trajectory analysis is a growing area of interest these days owing to its applications in various domains such as marketing, security, traffic monitoring and management, etc. To better understand movement behaviors from the raw mobility data, this doctoral work provides analytic models for analyzing trajectory data. As a first contribution, a model is developed to detect changes in trajectories with time. If the taxis moving in a city are viewed as sensors that provide real time information of the traffic in the city, a change in these trajectories with time can reveal that the road network has changed. To detect changes, trajectories are modeled with a Hidden Markov Model (HMM). A modified training algorithm, for parameter estimation in HMM, called m-BaumWelch, is used to develop likelihood estimates under assumed changes and used to detect changes in trajectory data with time. Data from vehicles are used to test the method for change detection. Secondly, sequential pattern mining is used to develop a model to detect changes in frequent patterns occurring in trajectory data. The aim is to answer two questions: Are the frequent patterns still frequent in the new data? If they are frequent, has the time interval distribution in the pattern changed? Two different approaches are considered for change detection, frequency-based approach and distribution-based approach. The methods are illustrated with vehicle trajectory data. Finally, a model is developed for clustering and outlier detection in semantic trajectories. A challenge with clustering semantic trajectories is that both numeric and categorical attributes are present. Another problem to be addressed while clustering is that trajectories can be of different lengths and also have missing values. A tree-based ensemble is used to address these problems. The approach is extended to outlier detection in semantic trajectories.
Dissertation/Thesis
Ph.D. Industrial Engineering 2012

Dissertation submitted in partial fulfilment of the requirements for the Degree of Master of Science in Geospatial Technologies
As a newly proliferating study area, knowledge discovery from trajectories has attracted more and more researchers from different background. However, there is, until now, no theoretical framework for researchers gaining a systematic view of the researches going on. The complexity of spatial and temporal information along with their combination is producing numerous spatio-temporal patterns. In addition, it is very probable that a pattern may have different definition and mining methodology for researchers from different background, such as Geographic Information Science, Data Mining, Database, and Computational Geometry. How to systematically define these patterns, so that the whole community can make better use of previous research? This paper is trying to tackle with this challenge by three steps. First, the input trajectory data is classified; second, taxonomy of spatio-temporal patterns is developed from data mining point of view; lastly, the spatio-temporal patterns appeared on the previous publications are discussed and put into the theoretical framework. In this way, researchers can easily find needed methodology to mining specific pattern in this framework; also the algorithms needing to be developed can be identified for further research. Under the guidance of this framework, an application to a real data set from Starkey Project is performed. Two questions are answers by applying data mining algorithms. First is where the elks would like to stay in the whole range, and the second is whether there are corridors among these regions of interest.

abstract: In today's world, unprecedented amounts of data of individual mobile objects have become more available due to advances in location aware technologies and services. Studying the spatio-temporal patterns, processes, and behavior of mobile objects is an important issue for extracting useful information and knowledge about mobile phenomena. Potential applications across a wide range of fields include urban and transportation planning, Location-Based Services, and logistics. This research is designed to contribute to the existing state-of-the-art in tracking and modeling mobile objects, specifically targeting three challenges in investigating spatio-temporal patterns and processes; 1) a lack of space-time analysis tools; 2) a lack of studies about empirical data analysis and context awareness of mobile objects; and 3) a lack of studies about how to evaluate and test agent-based models of complex mobile phenomena. Three studies are proposed to investigate these challenges; the first study develops an integrated data analysis toolkit for exploration of spatio-temporal patterns and processes of mobile objects; the second study investigates two movement behaviors, 1) theoretical random walks and 2) human movements in urban space collected by GPS; and, the third study contributes to the research challenge of evaluating the form and fit of Agent-Based Models of human movement in urban space. The main contribution of this work is the conceptualization and implementation of a Geographic Knowledge Discovery approach for extracting high-level knowledge from low-level datasets about mobile objects. This allows better understanding of space-time patterns and processes of mobile objects by revealing their complex movement behaviors, interactions, and collective behaviors. In detail, this research proposes a novel analytical framework that integrates time geography, trajectory data mining, and 3D volume visualization. In addition, a toolkit that utilizes the framework is developed and used for investigating theoretical and empirical datasets about mobile objects. The results showed that the framework and the toolkit demonstrate a great capability to identify and visualize clusters of various movement behaviors in space and time.
Dissertation/Thesis
Ph.D. Geography 2011