Discovering relevant subtrajectories for multidimensional trajectory classification

Abstract

Estamos vivendo a era do rastreamento do movimento de pessoas e de outros objetos móveis, em que uma grande quantidade de informação sobre a rotina diária das nossas vidas é coletada e armazenada em diferentes locais e formatos. Esses dados de movimento são chamados de trajetórias, e consistem em um dado complexo que envolve as dimensões espaço (onde o objeto está), tempo (quando), e em alguns casos semântica (o quê ou como faz). Mais recentemente, trajetórias estão sendo representadas por múltiplos aspectos, os quais permitem analisar o movimento do objeto móvel sob diferentes pontos de vista, como as interações em redes sociais ou a sequência de meios de transporte utilizados pelo objeto móvel. No entanto, analisar esse novo tipo de dado para descobrir padrões de movimentação é ainda uma questão de pesquisa em aberto. Uma das tarefas de descoberta de padrões mais importantes em Mineração de Dados é a classificação, que consiste em criar modelos matemáticos preditivos a partir de dados e usar esses modelos para predizer situações futuras. Classificação de Trajetórias é uma tarefa muito complexa, pois esses modelos devem ser construídos a partir de dados sequenciais envolvendo as dimensões de espaço, de tempo e, mais recentemente, semânticas. Nos últimos anos a classificação de trajetórias tem sido aplicada em problemas reais, considerando apenas as dimensões espaço e tempo, ou atributos criados a partir dessas dimensões, como velocidade e aceleração. No entanto, esses métodos não suportam trajetórias com dimensões além de espaço e tempo, como as provenientes de redes sociais, que envolvem diversas informações semânticas do movimento de um indivíduo. Como consequência, novos métodos para classificação de trajetórias são necessários para lidar com esse novo tipo de dado. Nesse sentido, o maior desafio consiste em identificar as partes de uma trajetória, chamadas de subtrajetórias, que melhor representam o movimento de indivíduos de uma classe em um problema de classificação. Nesta tese são propostos dois novos métodos para encontrar automaticamente as subtrajetórias mais relevantes de um conjunto de dados de trajetórias em um problema de classificação, sem a necessidade de passagem de parâmetros. O primeiro método, Movelets, utiliza uma abordagem baseada em distância entre subtrajetórias que considera todas as dimensões da trajetória de forma conjunta. Esse método é mais apropriado para problemas de classificação de trajetórias brutas, representadas apenas pelas dimensões espaço e tempo. O segundo método, MasterMovelets, encontra as subtrajetórias mais relevantes e a melhor combinação de dimensões para cada subtrajetória, o que torna o método robusto para classificação de trajetórias com múltiplos aspectos. Os métodos propostos foram avaliados experimentalmente com conjuntos de dados reais de trajetórias. Os modelos preditivos construídos usando Movelets apresentaram melhor qualidade preditiva em relação aos métodos estado da arte, em quatro problemas clássicos classificação de trajetórias brutas, são eles: classificação de animais, de furações, de caminhões e de movimentação de pessoas (GeoLife). O método MasterMovelets foi avaliado em problemas de classificação de trajetórias com múltiplos aspectos, provenientes de bases de dados de check-ins de três redes sociais, Gowalla, Brightkite e Foursquare. Os modelos construídos também apresentaram melhor qualidade preditiva em relação aos métodos existentes. Os resultados alcançados indicam que os métodos propostos superaram o estado da arte e são eficientes para classificação de trajetórias com múltiplos aspectos e promissores para a classificação de dados sequenciais multidimensionais.<br>

Abstract: We are witnessing the era of movement tracking and mining, where huge volumes of data about our daily lives are being collected and stored in several sources and formats. These data are stored in the form of trajectories, that consist of a complex data type that involves space and time dimensions, and in some cases also semantic dimensions. More recently, trajectories can be represented by multiple aspects, leading to the analysis of the object movement from different points of view, such as the social network interactions, the sequence of transportation means used by the object on his/her movement, etc. However, analyze this type of data for knowledge discovery is an open research area. Classification is a Data Mining task that consists of learning models from a dataset and use these models to classify new samples. Trajectory classification is a very complex task, because the pattern discovery involves space, time, semantics, and sequences. In the last few years trajectory classification has been applied to many real problems, basically considering the dimensions of space and time or attributes inferred from these dimensions, like speed, acceleration, and turning angle. With the explosion of social media data and the advances in the semantic enrichment of mobility data, a new type of trajectory data has emerged, and the trajectory spatio-temporal points have now multiple and heterogeneous semantic dimensions. By semantic dimensions we mean any type of information that is neither spatial nor temporal. As a consequence, new classification methods are needed to deal with this new type of data. The main challenge is how to automatically explore, combine, and select the data dimensions and to discover the subtrajectories that better discriminate the class. In this thesis we define the concept of multiple aspect trajectory and we propose two new parameter-free methods for extracting the most relevant subtrajectories for trajectory classification. The first method, called Movelets, uses a distance-based approach that considers all dimensions together to find the most relevant subtrajectories. This method is very robust for classification of raw trajectories, which include only space and time dimensions, although it also works for multiple aspect trajectories. The second method, called MasterMovelets, also finds the most relevant subtrajectories, but considering multiple and heterogeneous dimensions. This method automatically explores trajectory dimensions and finds the best dimension combination of subtrajectories, which makes it robust for high dimensional trajectory data. Experimental results show that Movelets outperforms state-of-the-art methods for raw trajectory classification and MasterMovelets outperforms existing methods to classify multiple aspect trajectories, indicating that our proposals are effective and are very promising for multidimensional sequence data classification.