Pivot-based approaches for Movelets and MASTERMovelets optimizations

Abstract

A mineração de dados de trajetórias se tornou um importante tópico de pesquisa nos últimos anos em função do grande volume de dados de movimento coletados das mais diversas fontes e formatos. Em especial, temos a classificação, que visa a identificação da classe que produziu uma determinada trajetória. Os trabalhos deste escopo são focados na extração dos melhores atributos para descrever as classes, ou das subtrajetórias relevantes que sejam capazes de caracterizar as trajetórias em uma classe. Inicialmente as trajetórias eram representadas pela posição de um objeto em movimento no espaço ao longo do tempo, as chamadas trajetórias brutas, e os trabalhos em classificação de trajetórias brutas extraíam características numéricas baseadas em fórmulas matemáticas que utilizavam a informação espaço-temporal. Contudo, com o barateamento e disseminação dos sensores e das redes sociais presentes nos dispositivos móveis, as trajetórias puderam ser enriquecidas com mais dados, produzindo as chamadas trajetórias múltiaspecto. A classificação deste novo tipo de dado de trajetória ainda está nos primórdios, e alguns trabalhos da literatura utilizam técnicas de mineração de texto para extrair as características da dimensão semântica das trajetórias, enquanto outros trabalhos se baseiam na extração das subtrajetórias relevantes. As técnicas Movelets e MASTERMovelets são baseadas na extração das subtrajetórias relevantes, as movelets, e têm superado os outros trabalhos da literatura tanto em classificação de trajetórias brutas quanto multiaspecto. A capacidade destas técnicas de lidar com múltiplas e diferentes subtrajetórias e suas dimensões as torna inviáveis para grandes conjuntos de dados, uma vez que exploram e avaliam exaustivamente todas as subtrajetórias possíveis. Neste trabalho, são propostos os métodos MASTER-Pivots e SUPER-Pivots, que são estratégias para reduzir a geração de subtrajetórias para ambas as técnicas Movelets e MASTERMovelets, a fim de acelerar seus processos, mantendo a acurácia da classificação. O MASTER-Pivots é um método não supervisionado que limita o tamanho e o local a partir do qual as movelets são extraídas. Ele baseia-se na identificação dos pontos pivô, que são os melhores movelets de tamanho um, e na limitação da extracção dos movelets apenas a partir dos pontos pivô e dos seus pontos vizinhos que são diretamente alcançáveis. O SUPER-Pivots é uma estratégia supervisionada que consiste em identificar os SUPER-Pivots, que são as subtrajetórias e seu número de dimensões que ocorreram mais frequentemente nas trajetórias de uma determinada classe, e em extrair as movelets apenas dos SUPER-Pivots. Ambos os métodos foram avaliados através de uma série de experimentos, onde apresentamos uma extensa avaliação e comparação experimental que reúne nove técnicas do estado da arte e seis conjuntos de dados conhecidos e disponíveis ao público. Os MASTER-Pivots e SUPER-Pivots foram avaliados considerando o número de subtrajetórias geradas, sua escalabilidade e a acurácia em classificação, onde o primeiro reduziu o tempo de processamento com relação ao MASTERMovelets em mais de 70% em todos os conjuntos de dados, enquanto o segundo reduziu em pelo menos 80% em qualquer conjunto de dados. Todos os códigos e resultados utilizados neste trabalho são fornecidos como um benchmark, com o objetivo de facilitar a análise e comparação das técnicas de classificação de trajetórias.

Abstract: Trajectory data mining has become an important research topic in the last few years, specially the trajectory classification, which aims to identify which class of moving object produced a given trajectory. The works in this scope are focused on extracting the best set of features to describe the classes, or the relevant subtrajectories that are capable of characterizing the trajectories in a class. Initially the trajectories were represented by the position of a moving object in space through time, the so-called raw trajectories. The works in raw trajectory classification extracted numeric features based on the spatio-temporal information. Moreover, with the cheapness and dissemination of sensors and the social media present in smartphones, the trajectories could be enriched with more data, producing the multiple aspect trajectories. The classification in this new type of trajectory data is still in the early days, and some works of the literature use techniques of text mining to extract the features from the semantic information of trajectories while other works are based on extracting the relevant subtrajectories. The Movelets and MASTERMovelets techniques are based on extracting the relevant subtrajectories, or movelets, and have surpassed the other works in the literature for both raw and multiple aspect trajectory classification, once they can handle multiple and different subtrajectories and their dimensions, but are unfeasible for highly dimensional and large datasets, as they exhaustively explore and evaluate all possible subtrajectories. In this work we propose the methods MASTER-Pivots and SUPER-Pivots, that are strategies for reducing the generation of subtrajectories of both Movelets and MASTERMovelets techniques, in order to speed up their processes while maintaining classification accuracy. The MASTER-Pivots is an unsupervised method that limits the size and the place from where the movelets are extracted. It is based on identifying the pivot points, which are the best movelets of size one, and by limiting the extraction of movelets from only the pivot points and their directly reachable neighbour points. The SUPER-Pivots is a supervised strategy that consists on identifying the SUPER-pivots, which are the subtrajectories that occurred more in the trajectories of a given class, and by extracting the SUPER-pivots only. We also present an extensive experimental evaluation and comparison that ensembles nine state of the art techniques and six well known and publicly available data sets. The MASTER-Pivots and SUPER-Pivots were evaluated considering the number of generated subtrajectories, the scalability behavior, and the accuracy, where the first one reduced the processing time w.r.t. MASTERMovelets in more than 70% in all datasets, while the latter reduced in at least 80% in any dataset. Every code and result used in this thesis is provided as a benchmark, aiming to facilitate further analysis and comparison of trajectory classification techniques.