SILVA, Ticiana Linhares Coelho da. Online clustering of trajectory data stream. 2016. 113 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Jairo Viana (jairo@ufc.br) on 2017-02-17T18:32:07Z
No. of bitstreams: 1
2016_tese_tlcsilva.pdf: 21709584 bytes, checksum: 1454aec7cf746b2ad56eda5865264deb (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-02-17T18:32:27Z (GMT) No. of bitstreams: 1
2016_tese_tlcsilva.pdf: 21709584 bytes, checksum: 1454aec7cf746b2ad56eda5865264deb (MD5) / Made available in DSpace on 2017-02-17T18:32:27Z (GMT). No. of bitstreams: 1
2016_tese_tlcsilva.pdf: 21709584 bytes, checksum: 1454aec7cf746b2ad56eda5865264deb (MD5)
Previous issue date: 2016 / Mining trajectory patterns allows characterizing movement behavior (i.e. congestion, flocks, swarms, leadership, among others), which leverages new applications and services. Movement tracking becomes ubiquitous in many applications, which raises great interests in trajectory data analysis and mining. Most existing approaches allow characterizing the past movements of the objects but not current patterns, because they use only historical trajectory data. Recent approaches for online clustering of moving objects location are restricted to instantaneous positions. Subsequently, they fail to capture moving objects' behavior over time. By continuously tracking moving objects' sub-trajectories at each time window, rather than just the last position, it becomes possible to gain insight on the current behavior, and potentially detect mobility patterns in real time. Real-time analysis of mobility data may offer novel tools to better understand ongoing city dynamics, as well as the detection of regularities and anomalies as they happen; all in all, this can represent an invaluable tool when tackling decision-making tasks. Among the possible patterns, in this thesis we mainly consider (sub)-trajectory clustering and its evolution. Discovering such patterns may help to re-engineer effectively the traffic within a city, or to promptly detect events at the city level (e.g., car accidents) as they happen. In the first line of investigation we tackle the problem of discovering and maintaining the density based clusters in trajectory data streams in Euclidean Space, despite the fact that most moving objects change their position over time. We propose CUTiS, an incremental algorithm to solve this problem, while tracking the evolution of the clusters as well as the membership of the moving objects to the clusters. Our experiments were conducted on two real datasets and the experiments show the efficiency and the effectiveness of our method comparing to two competitors DBSCAN and TraClus. As a second line of research, we aim at improving the efficiency of the CUTiS algorithm. In this way, we propose an indexing structure for sub-trajectory data based on a space-filling curve. This approach has the property of mapping a multidimensional space to one-dimensional space such that, for two objects that are close in the original space, there is a high probability that they will be close in the mapped target space. We take advantage of this property to optimize range queries from a moving object sub-trajectory on the incremental clustering algorithm. Our experiments were conducted on a real data set and they show the efficiency and the effectiveness of our method compared to our previous proposed CUTiS, DBSCAN and TraClus. As a third line, we investigate the same problem of sub-trajectory clustering discovery and maintenance on a Road Network since many moving objects move on the road network in real applications. We propose Net-CUTiS an incremental clustering algorithm for road network constraint movement. The efficiency and effectiveness of Net-CUTiS were compared using a real dataset with NETSCAN and DBSCAN. / A mineração de dados de trajetória permitem caracterizar o comportamento de movimento (isto é, congestionamento, flocks, swarms, leadership, entre outros padrões de movimento), impulsionando novas aplicações e serviços. O rastreamento de objetos móveis se torna onipresente em muitas aplicações, o que gera grande interesse na análise de dados de trajetória e na mineração destes dados. A maioria das abordagens permite detectar padrões de movimento em dados históricos de objetos, mas não padrões atuais. Abordagens recentes para clusterização online de objetos móveis se restringem a analisar posições instantâneas. Dessa forma, estes trabalhos não conseguem capturar o comportamento dos objetos em movimento ao longo do tempo. Ao monitorar continuamente as sub-trajetórias de objetos móveis em intervalos de tempo, ao invés de apenas a última posição, é possível obter uma visão sobre o comportamento atual e potencialmente detectar padrões de mobilidade em tempo real. A análise em tempo real dos dados de mobilidade pode oferecer conhecimento para entender melhor a dinâmica da cidade em curso, bem como a detecção de irregularidades e anomalias à medida que acontecem; Este estudo é relevante para tomada de decisão. Entre os possíveis padrões, nesta tese consideramos principalmente o agrupamento (clusterização) de sub-trajetórias e a evolução do movimento dos objetos. Descobrir esses padrões pode ajudar na re-engenharia do tráfego de grandes cidades, ou para detectar prontamente eventos (por exemplo, acidentes de carro, passeatas, entre outros) à medida que eles acontecem. Na primeira linha de investigação desta tese, abordamos o problema de descobrir e manter os clusters baseados em densidade utilizando streams de trajetórias no Espaço Euclidiano, levando em consideração que a maioria dos objetos em movimento muda de posição ao longo do tempo. Dessa forma, esta tese propõe o framework CUTiS (ClUstering Trajectory Stream), um algoritmo incremental para resolver este problema. CUTiS é capaz de monitorar a evolução dos padrões de movimento (clusters), bem como a adesão dos objetos em movimento aos padrões já existentes. Nossos experimentos foram conduzidos em dois conjuntos de dados reais e os experimentos mostram a eficiência e a eficácia do nosso método comparando a dois concorrentes DBSCAN e TraClus. Como segunda linha de pesquisa, esta tese teve como objetivo melhorar a eficiência do algoritmo CUTiS. Desta forma, foi proposto uma estrutura de indexação para dados de sub-trajetória com base em space filling curve. Esta abordagem tem a propriedade de mapear um espaço multidimensional para um espaço unidimensional tal que, para dois objetos que estão próximos no espaço original, existe uma alta probabilidade de que eles fiquem próximos no espaço alvo mapeado. Essa propriedade foi utilizada para otimizar range queries de uma sub-trajetória de um objeto no algoritmo de clusterização incremental. Nossos experimentos foram conduzidos em um conjunto de dados reais e eles mostram a eficiência e a eficácia do nosso método em comparação com a nossa proposta anterior CUTiS, e as abordagens DBSCAN e TraClus. Como terceira linha, investigamos o mesmo problema de descoberta e manutenção de clusters de sub-trajetórias em uma rede rodoviária, já que muitos objetos em movimento se movem na rede rodoviária em aplicações reais. Dessa forma, foi proposto como solução o Net-CUTiS, um algoritmo de clusterização incremental para sub-trajetórias de objetos com restrição de movimento em rede rodoviária. A eficiência e a eficácia do Net-CUTiS foram comparadas usando um conjunto de dados real com a abordagem NETSCAN e DBSCAN.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/22045 |
| Date | January 2016 |
| Creators | Silva, Ticiana Linhares Coelho da |
| Contributors | Bennis-Zeitouni, Karine, Macedo, José Antônio Fernandes de |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds