Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-07-12T13:16:29Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) tese_doutorado_amilcar-07-2016_versao-cd (1).pdf: 2101060 bytes, checksum: 21d268c59ad60238bce0cde073e6f3cd (MD5) / Made available in DSpace on 2017-07-12T13:16:29Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) tese_doutorado_amilcar-07-2016_versao-cd (1).pdf: 2101060 bytes, checksum: 21d268c59ad60238bce0cde073e6f3cd (MD5) Previous issue date: 2016-03-10 / A popularização de tecnologias de captura de dados geolocalizados aumentou a quantidade de dados de trajetórias disponível para análise. Trajetórias de objetos móveis são geradas a partir das posições de um objeto que se move durante um certo intervalo de tempo no espaço geográfico. Para diversas aplicações é necessário que as trajetórias sejam divididas em partições menores, denominadas segmentos, que representam algum comportamento relevante para a aplicação. A literatura reporta diversos trabalhos que propõem a segmentação de trajetórias. Entretanto, pouco se discute a respeito de quais algoritmos são mais adequados para um domínio ou quais valores de parâmetros de entrada fazem com que um algoritmo obtenha o melhor desempenho neste mesmo domínio. A grande maioria dos algoritmos de segmentação de trajetórias utiliza critérios pré-definidos para realizar esta tarefa. Poucos trabalhos procuram utilizar critérios nos quais não se sabe a priori que tipos de segmentos são gerados, sendo esta questão pouco explorada na literatura. Outra questão em aberto é o uso de exemplos para induzir um algoritmo de segmentação a encontrar segmentos semelhantes a estes exemplos em outras trajetórias. Esta proposta de tese objetiva resolver estas questões. Primeiro, são propostos os métodos GEnetic Algorithm based on Roc analysis (GEAR) e o Iterated F-Race for Trajectory Segmentation Algorithms (I/F-Race-TSA), que são métodos para auxiliar na escolha da melhor configuração (i.e. valores de parâmetros de entrada) de algoritmos de segmentação de trajetórias. Segundo, é proposto o Greedy Randomized Adaptive Search Procedure for Unsupervised Trajectory Segmentation (GRASP-UTS), com o objetivo de resolver o problema de segmentação de trajetórias quando o critério de segmentação não é previamente definido. Por último, propomos o GRASP for Semi-supervised Trajectory Segmentation (GRASP-SemTS). O GRASP-SemTS usa exemplos para induzir a tarefa de segmentação a encontrar segmentos semelhantes em outras trajetórias. Foram conduzidos experimentos com os métodos e algoritmos propostos para domínios distintos e para trajetórias reais de objetos móveis. Os resultados mostraram que ambos os métodos GEAR e I/F-Race-TSA foram capazes de calibrar automaticamente os parâmetros de entrada de algoritmos de segmentação de trajetórias para um dado domínio de aplicação. Os algoritmos GRASP-UTS e GRASP-SemTS obtiveram melhor desempenho quando comparados a outros algoritmos de segmentação de trajetórias da literatura contribuindo assim com importantes resultados para a área. / The popularization of technologies for geolocated data increased the amount of trajectory data available for analysis. Moving objects’ trajectories are generated from the positions of an object that moves in the geographical space during a certain amount of time. For many applications, it is necessary to partition trajectories into smaller pieces, named segments, which represent a relevant behavior to the application point of view. The literature reports many studies that propose trajectory segmentation approaches. However, there is a lack of discussions about which algorithm is more likely to be applied in a domain or which values of its input parameters obtain the best performance in the domain. Most algorithms for trajectory segmentation use pre-defined criteria to perform this task. Only few works make use of criteria where the characteristics of the segment are not known a priori and this topic is not well explored in the literature. Another open question is how to use a small amount of labeled segments to induce a segmentation algorithm in order to find such kind of behaviors into unseen trajectories. This thesis proposal aims to solve these questions. First, we propose the GEnetic Algorithm based on Roc analysis (GEAR) and the Iterated F-Race for Trajectory Segmentation Algorithms (I/F-RaceTSA), which are methods that are able to find the best configuration (i.e. input parameter values) of algorithms for trajectory segmentation. Second, we propose a Greedy Randomized Adaptive Search Procedure for Unsupervised Trajectory Segmentation (GRASP-UTS) aiming to solve the trajectory segmentation problem when the criteria is not determined a priori. Last, we propose the GRASP for Semi-supervised Trajectory Segmentation (RGRASP-SemTS). The GRASP-SemTS solves the problem of using a small amount of labeled data to induce the trajectory segmentation algorithm to find such behaviors into unseen trajectories. Experiments were conducted with the methods and algorithms algorithms using real world trajectory data. Results showed that GEAR and I/F-Race-TSA are capable of finding automatically the input parameter values for a domain. The GRASP-UTS and GRASP-SemTS obtained a better performance when compared to other segmentation algorithms from literature, contributing with important results for this field.

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

With the development of technologies such as Global Navigation Satellite Systems (GNSS), mobile computing, and Information and Communication Technology (ICT) the procedure of sampling positional data has lately been significantly simplified.  This enables the aggregation of large amounts of moving objects data (i.e. trajectories) containing potential information about the moving objects. Within Knowledge Discovery in Databases (KDD), automated processes for realization of this information, called trajectory data mining, have been implemented.   The objectives of this study is to examine 1) how trajectory data mining tasks are defined at an abstract level, 2) what type of information it is possible to extract from trajectory data, 3) what solutions trajectory data mining tools implement for different tasks, 4) how tools uses visualization, and 5) what the limiting aspects of input data are how those limitations are treated. The topic, trajectory data mining, is examined in a literature review, in which a large number of academic papers found trough googling were screened to find relevant information given the above stated objectives.   The literature research found that there are several challenges along the process arriving at profitable knowledge about moving objects. For example, the discrete modelling of movements as polylines is associated with an inherent uncertainty since the location between two sampled positions is unknown.  To reduce this uncertainty and prepare raw data for mining, data often needs to be processed in some way. The nature of pre-processing depends on sampling rate and accuracy properties of raw in-data as well as the requirements formulated by the specific mining method. Also a major challenge is to define relevant knowledge and effective methods for extracting this from the data. Furthermore are conveying results from mining to users an important function. Presenting results in an informative way, both at the level of individual trajectories and sets of trajectories, is a vital but far from trivial task, for which visualization is an effective approach.   Abstractly defined instructions for data mining are formally denoted as tasks. There are four main categories of mining tasks: 1) managing uncertainty, 2) extrapolation, 3) anomaly detection, and 4) pattern detection. The recitation of tasks within this study provides a basis for an assessment of tools used for the execution of these tasks. To arrive at profitable results the dimensions of comparison are selected with the intention to cover the essential parts of the knowledge discovery process. The measures to appraise this are chosen to make results correctly reflect the 1) sophistication, 2) user friendliness, and 3) flexibility of tools. The focus within this thesis is freely available tools, for which the range is proven to be very small and fragmented. The selection of tools found and reported on are: MoveMine 2.0, MinUS, GeT_Move and M-Atlas.   The tools are reviewed entirely through utilizing documentation of the tools. The performance of tools is proved to vary along all dimensional measures except visualization and graphical user interface which all tools provide. Overall the systems preform well considering user-friendliness, somewhat good considering sophistication and poorly considering flexibility. However, since the range of tasks, which tools intend to solve, overall is varying it might not be appropriate to compare the tools in term of better or worse.   This thesis further provides some theoretical insights for users regarding requirements on their knowledge, both concerning the technical aspects of tools and about the nature of the moving objects. Furthermore is the future of trajectory data mining in form of constraints on information extraction as well as requirements for development of tools discussed, where a more robust open source solution is emphasised. Finally, this thesis can altogether be regarded to provide material for guidance in what trajectory mining tools to use depending on application. Work to complement this thesis through comparing the actual performance of tools, when using them, is desirable. / I och med utvecklingen av tekniker så som Global Navigation Satellite systems (GNSS), mobile computing och Information and Communication Technology (ICT) har tillvägagångsätt för insamling av positionsdata drastiskt förenklats. Denna utveckling har möjliggjort för insamlandet av stora mängder data från rörliga objekt (i.e. trajecotries)(sv: rörelsebanor), innehållande potentiell information om dessa rörliga objekt. Inom Knowledge Discovery in Databases (KDD)(sv: kunskapsanskaffning i databaser) tillämpas automatiserade processer för att realisera sådan information, som kallas trajectory data mining (sv: utvinning från rörelsebanedata).   Denna studie ämnar undersöka 1) hur trajectory data mining tasks (sv: utvinning från rörelsebanedata uppgifter) är definierade på en abstrakt nivå, 2) vilken typ av information som är möjlig att utvinna ur rörelsebanedata, 3) vilka lösningar trajectory data ming tools (sv: verktyg för datautvinning från rörelsebanedata) implementerar för olika uppgifter, 4) hur verktyg använder visualisering, och 5) vilka de begränsande aspekterna av input-data är och hur dessa begränsningar hanteras. Ämnet utvinning från rörelsebanedata undersöks genom en litteraturgranskning, i vilken ett stort antal och akademiska rapporter hittade genom googling granskas för att finna relevant information givet de ovan nämnda frågeställningarna.   Litteraturgranskningen visade att processen som leder upp till en användbar kunskap om rörliga objekt innehåller dock flera utmaningar. Till exempel är modelleringen av rörelser som polygontåg associerad med en inbyggd osäkerhet eftersom positionen för objekt mellan två inmätningar är okänd. För att reducera denna osäkerhet och förbereda rådata för extraktion måste ofta datan processeras på något sätt. Karaktären av förprocessering avgörs av insamlingsfrekvens och exakthetsegenskaper hos rå indata tillsammans med de krav som ställs av de specifika datautvinningsmetoderna. En betydande utmaning är också att definiera relevant kunskap och effektiva metoder för att utvinna denna från data. Vidare är förmedlandet av resultat från utvinnande till användare en viktig funktion. Att presentera resultat på ett informativt sätt, både på en nivå av enskilda rörelsebanor men och grupper av rörelsebanor är en vital men långt ifrån trivial uppgift, för vilken visualisering är ett effektivt tillvägagångsätt.   Abstrakt definierade instruktioner för dataextraktion är formellt betecknade som uppgifter. Det finns fyra huvudkategorier av uppgifter: 1) hantering av osäkerhet, 2) extrapolation, 3) anomalidetektion, and 4) mönsterdetektion. Sammanfattningen av uppgifter som ges i denna rapport utgör ett fundament för en utvärdering av verktyg, vilka används för utförandet av uppgifter. För att landa i ett givande resultat har jämförelsegrunderna för verktygen valts med intentionen att täcka de viktigaste delarna av processen för att förvärva kunskap. Måtten för att utvärdera detta valdes för att reflektera 1) sofistikering, 2) användarvänlighet, och 3) flexibiliteten hos verktygen. Fokuset inom denna studie har varit verktyg som är gratis tillgängliga, för vilka utbudet har visat sig vara litet och fragmenterat. Selektionen av verktyg som hittats och utvärderats var: MoveMine 2.0, MinUS, GeT_Move and M-Atlas.   Verktygen utvärderades helt och hållet baserat på tillgänglig dokumentation av verktygen.  Prestationen av verktygen visade sig variera längs alla jämförelsegrunder utom visualisering och grafiskt gränssnitt som alla verktyg tillhandahöll. Överlag presterade systemen väl gällande användarvänlighet, någorlunda bra gällande sofistikering och dåligt gällande flexibilitet. Hursomhelst, eftersom uppgifterna som verktygen avser att lösa varierar är det inte relevant att värdera dem mot varandra gällande denna aspekt.   Detta arbete tillhandahåller vidare några teoretiska insikter för användare gällande krav som ställs på deras kunskap, både gällande de tekniska aspekterna av verktygen och rörliga objekts beskaffenhet. Vidare diskuteras framtiden för utvinning från rörelsebanedata i form av begränsningar på informationsutvinning och krav för utvecklingen av verktyg, där en mer robust open source lösning betonas. Sammantaget kan detta arbete anses tillhandahålla material för vägledning i vad för verktyg för datautvinning från rörelsebanedata som kan användas beroende på användningsområde. Arbete för att komplettera denna rapport genom utvärdering av verktygens prestation utifrån användning av dem är önskvärt.

[pt] Ônibus, equipados com dispositivos GPS ativos que transmitem continuamente a sua posição, podem ser entendidos como sensores móveis de trânsito. De fato, as trajetórias dos ônibus fornecem uma fonte de dados útil para analisar o trânsito na rede de ônibus de uma cidade, dado que as autoridades de trânsito da cidade disponibilizem as trajetórias de forma aberta, oportuna e contínua. Neste contexto, esta tese propõe uma abordagem que usa os dados de GPS dos ônibus para analisar e monitorar a rede de ônibus de uma cidade. Ela combina algoritmos de grafos, técnicas de mineração de dados geoespaciais e métodos estatísticos. A principal contribuição desta tese é uma definição detalhada de operações e algoritmos para analisar e monitorar o tráfego na rede de ônibus, especificamente: (1) modelagem, análise e segmentaçãoda rede de ônibus; (2) mineração do conjunto de dados de trajetória de ônibus para descobrir padrões de tráfego; (3) detecção de anomalias de trânsito, classificação de acordo com sua gravidade, e avaliação do seu impacto; (4) manutenção e comparação de diferentes versões da rede de ônibus e dos seus padrões de tráfego para ajudar os planejadores urbanos a avaliar as mudanças. Uma segunda contribuição é a descrição de experimentos realizados para a rede de ônibus da Cidade do Rio de Janeiro, utilizando trajetórias de ônibus correspondentes ao período de junho de 2014 até fevereiro de 2017, disponibilizadas pela Prefeitura do Rio de Janeiro. Os resultados obtidos corroboram a utilidade da abordagem proposta para analisar e monitorar a rede de ônibus de uma cidade, o que pode ajudar os gestores do trânsito e as autoridades municipais a melhorar os planos de controle de trânsito e de mobilidade urbana. / [en] Buses, equipped with active GPS devices that continuously transmit their position, can be understood as mobile traffic sensors. Indeed, bus trajectories provide a useful data source for analyzing traffic in the bus network of a city, if the city traffic authority makes the bus trajectories available openly, timely and in a continuous way. In this context, this thesis proposes a bus GPS data-driven approach for analyzing and monitoring the bus network of a city. It combines graph algorithms, geospatial data mining techniques and statistical methods. The major contribution of this thesis is a detailed discussion of key operations and algorithms for modeling, analyzing and monitoring bus network traffic, specifically: (1) modelling, analyzing, and segmentation of the bus network; (2) mining the bus trajectory dataset to uncover traffic patterns; (3) detecting traffic anomalies, classifying them according to their severity, and estimating their impact; (4) maintaining and comparing different versions of the bus network and traffic patterns to help urban planners assess changes. Another contribution is the description of experiments conducted for the bus network of the City of Rio de Janeiro, using bus trajectories obtained from June 2014 to February 2017, which have been made available by the City Hall of Rio de Janeiro. The results obtained corroborate the usefulness of the proposed approach for analyzing and monitoring the bus network of a city, which may help traffic managers and city authorities improve traffic control and urban mobility plans.

[pt] Em ambientes dinâmicos, os modelos de dados tendem a ter desempenho insatisfatório uma vez que a distribuição subjacente dos dados muda. Este fenômeno é conhecido como Concept Drift. Em relação a este tema, muito esforço tem sido direcionado ao desenvolvimento de métodos capazes de detectar tais fenômenos com antecedência suficiente para que os modelos possam se adaptar. No entanto, explicar o que levou ao drift e entender suas consequências ao modelo têm sido pouco explorado pela academia. Tais informações podem mudar completamente a forma como adaptamos os modelos. Esta dissertação apresenta uma nova abordagem, chamada Detector de Drift Interpretável, que vai além da identificação de desvios nos dados. Ele aproveita a estrutura das árvores de decisão para prover um entendimento completo de um drift, ou seja, suas principais causas, as regiões afetadas do modelo e sua severidade. / [en] In a dynamic environment, models tend to perform poorly once the underlying distribution shifts. This phenomenon is known as Concept Drift. In the last decade, considerable research effort has been directed towards developing methods capable of detecting such phenomena early enough so that models can adapt. However, not so much consideration is given to explain the drift, and such information can completely change the handling and understanding of the underlying cause. This dissertation presents a novel approach, called Interpretable Drift Detector, that goes beyond identifying drifts in data. It harnesses decision trees’ structure to provide a thorough understanding of a drift, i.e., its principal causes, the affected regions of a tree model, and its severity. Moreover, besides all information it provides, our method also outperforms benchmark drift detection methods in terms of falsepositive rates and true-positive rates across several different datasets available in the literature.