Clusterização de trajetórias multiaspecto usando árvores de decisão

Abstract

O crescente aumento e popularização de dispositivos móveis com tecnologia GPS promoveu um grande volume de dados ao permitir a captura da movimentação dos usuários ou objetos em sequências de pontos no espaço e no tempo definindo o conceito de trajetórias do objeto móvel. Estes dados espaço-temporais estão presentes em diversos problemas cotidianos, como questões sobre aquecimento global, mobilidade urbana, desastres naturais, migrações humanas e animais, e despertam um grande interesse da comunidade científica. O advento da Internet das Coisas, objetos com sensores embarcados que coletam inúmeras informações como temperatura, poluição atmosférica e batimentos cardíacos, diversas características puderam ser agregadas às trajetórias, enriquecendo-as semanticamente e gerando uma nova abordagem denominada de trajetórias multiaspecto. À medida que se adicionam mais aspectos às trajetórias, mais completa é a representação real do movimento dos objetos, e mais útil e interessante são as informações que se podem inferir sobre objetos e lugares. Os dados dessas trajetórias multiaspecto podem conter informações importantes permitindo identificar, por exemplo, comportamentos e padrões recorrentes dos objetos, como também realizar previsões sobre tendências futuras. Uma técnica interessante para analisar as trajetórias é o agrupamento, que objetiva encontrar similaridades entre trajetórias ou objetos móveis gerando entendimento sobre essas semelhanças dado o cenário de trajetórias de diferentes objetos, ou de um mesmo objeto em momentos diferentes. O agrupamento de dados apresenta diversas aplicações, como exemplo, segmentação de mercado através do perfilamento de clientes, detecção de comportamentos anômalos em conjunto de dados de trajetórias, identificação de pontos importantes baseados em trajetórias de turistas em uma determinada cidade, identificação de atividades criminais ou fraudulentas, dentre outras. O interesse por análises de trajetórias é grande, no entanto, a maioria dos trabalhos dão pouca atenção à semântica. A alta dimensionalidade e heterogeneidade de trajetórias multiaspecto representa um grande desafio quanto à forma de tratar os dados das trajetórias, integrar toda informação em uma única representação de trajetória e extrair informações valiosas. Diante disso, este trabalho tem como objetivo utilizar árvores de decisão e aprendizado não-supervisionado para identificar agrupamentos naturais, que possuam um significado, em conjuntos de dados de trajetórias multiaspecto. Os grupos encontrados são avaliados com métricas de validação internas que permitem mensurar a coesão, a separabilidade e a qualidade dos agrupamentos obtidos e métricas de validação externas que utilizam referências externas para comparação e identificação da melhor forma de agrupar as trajetórias e assim determinar a utilidade e a validade dos resultados obtidos.

The increase and popularization of mobile devices with GPS technology promoted a large volume of data by allowing the capture of movement of users or objects in sequences of points in space and time, defining the concept of trajectories of moving objects. These spatiotemporal data are present in several daily problems, such as questions about global warming, urban mobility, natural disasters, human and animal migrations, and arouse great interest from the scientific community. The advent of the Internet of Things, objects with built-in sensors that collect numerous information such as temperature, air pollution and heartbeat, several characteristics could be added to the trajectories, enriching them semantically and generating a new approach called trajectories with multiple aspect. As more aspects are added to the trajectories, the more complete is the real representation of the movement of the objects, and the more useful and interesting is the information that can be inferred about objects and places. The data of these multi-aspect trajectories can contain important information allowing to identify, for example, recurring behaviors and patterns of objects, as well as to make predictions about future trends. An interesting technique for analyzing trajectories is clustering, which aims to find similarities between trajectories or moving objects, generating understanding of these similarities given the scenario of trajectories of different objects, or of the same object at different times. The clusterization of data presents several applications, such as, market segmentation through the profiling of customers, detection of anomalous behaviors in a set of trajectory data, identification of important points based on the trajectories of tourists in a given city, identification of criminal or fraudulent activities etc. The interest in trajectory analysis is great, however, most works pay little attention to semantics. The high dimensionality and heterogeneity of multi-aspect trajectories represent a major challenge as to how to handle the trajectory data, integrate all information in a single trajectory representation and extract valuable information. Therefore, the research aims to use decision trees and unsupervised learning to identify natural clusters, which have a meaning, in data sets of multi-aspect trajectories. The groups found are evaluated with internal validation metrics that allow measuring the cohesion, separability and quality of the obtained groupings and external validation metrics that use external references to compare and identify the best way to group trajectories and thus determine the usefulness and the validity of the results obtained.