Análise espacial de grandes quantidades de dados de movimento usando técnicas de clustering baseadas em densidade

Abstract

A análise de entidades em movimento, representados através de Moving Point Objects (MPO), é útil nas mais variadas áreas, desde o estudo de migrações de animais, até ao estudo do comportamento de multidões. Grandes quantidades de dados sobre movimento continuam a ser recolhidas utilizando tecnologias como o Global Gositioning Systems (GPS) e informação geográfica voluntária baseado na Internet. Um grande desafio no estudo de dados sobre movimento é o tamanho cada vez mais avultado das bases de dados que são passiveis de serem analisadas. Para analisar grandes quantidades de dados, com o objetivo de identificar padrões ou tendências nos mesmos, podem ser utilizados algoritmo de clustering. Estes podem ser de diferentes tipos. Dentre os mesmos, e dadas as características dos dados a analisar, foram selecionados os algoritmos baseados em densidade de pontos. Os algoritmos de clustering cujos resultados se têm mostrado mais satisfatórios, como o “sheared nearest neighbour”, tendem a não ser aplicáveis a bases de dados massivas, devido à sua complexidade ser quadrática, o que apresenta custos em termos de tempo de execução. Este trabalho propõe-se a identificar e avaliar alternativas que possam ser adotadas no sentido de diminuir a complexidade e consequentemente o tempo de execução do algoritmo. A otimizações identificadas e implementadas baseiam-se na redução muito significativa do número de cálculos de proximidade necessários para definir as listas de vizinhos mais próximos de cada ponto. Isto foi conseguido através da divisão dos pontos, através das suas coordenadas espaciais, por uma matriz, e comparando os pontos de cada célula dessa matriz com os pontos de células vizinhas. Foram atingidos resultados relevantes quando se tornou possível reduzir o tamanho dessas células sem nenhuma restrição ao nível da ocorrência de erros de clustering. O algoritmo resultante foi implementado numa ferramenta preparada para facilitar a análise de dados sobre movimento, e permitir o uso da estratégia desenvolvida neste trabalho noutros fins, diferentes do uso do algoritmo SNN.

The analysis of bodies in motion, represented through Moving Point Objects (MPO), is useful in various areas, from the study of migrations of animals up to the study of behavior of crowds. Large amounts of movement data continue to be collected using technologies such as Global Gositioning Systems (GPS) and geographic information-based voluntary Internet. A major challenge in the study of movement data is the increasingly large size of databases that are ready for analysis. To analyze large amounts of data in order to identify patterns or trends in them, a clustering algorithm can be used. These can be of different types. Among them, and given the characteristics of the data to be analyzed, density-based algorithms were selected. The clustering algorithms whose results have proved most satisfactory, as the "sheared nearest neighbor", tend not to be applicable to massive data bases because of their quadratic complexity, which has costs in terms of runtime. This study proposes to identify and evaluate alternatives that can be adopted to reduce the complexity and thus the running time of the algorithm. The optimizations identified and implemented are based on the significant reduction in the number of calculations needed to determine the nearest neighbors lists of each point. This was accomplished by dividing points through their spatial coordinates, into a matrix, and comparing the points of each cell of this array points to neighboring cells. Significant results were achieved when it became possible to reduce the size of these cells without any restriction in terms of the occurrence of errors in clustering. The resulting algorithm has been implemented in a tool equipped to facilitate analysis of movement data, and enable the use of the strategy developed in this work for other purposes, different from the use of SNN algorithm.