Spatio-temporal SNN : integrating time and space in the clustering process

Abstract

Spatio-temporal clustering is a new subfield of data mining that is increasingly gaining scientific attention due to the technical advances of location-based or environmental devices that register position, time and, in some cases, other semantic attributes. This process intends to group objects based in their spatial and temporal similarity helping to discover interesting patterns and correlations in large datasets. One of the main challenges of this area is that there are different types of spatio-temporal data and there is no general approach to treat all these types. Another challenge still unresolved is the ability to integrate several dimensions in the clustering process with a general-purpose approach. Moreover, it was also possible to verify that few works address their implementations under the SNN (Shared Nearest Neighbour) algorithm, which gives the opportunity to propose an innovative extension of this particular algorithm. This work intends to implement in the SNN clustering algorithm the ability to deal with spatio-temporal data allowing the integration of space, time and one or more semantic attributes in the clustering process. In this document, background knowledge about clustering, spatial clustering and spatio-temporal clustering are presented along with a summary of the main approaches followed to cluster spatio-temporal data with different clustering algorithms. Based on those approaches, and in the analysis of their advantages and disadvantages, the boundaries of this work are defined in order to incorporate the space, time and semantic attribute dimensions in the SNN algorithm and thus propose the 4D+SNN approach. The results presented in this work are very promising as the approach proposed is able to identify interesting patterns on spatio-temporal data. Concretely, it can identify clusters taking into account simultaneously the spatial and temporal dimension and it also has good results when adding one or more semantic attributes.

O clustering espaço-temporal é uma nova área do data mining que está a ganhar crescente atenção por parte da comunidade científica devido aos avanços tecnológicos dos dispositivos de localização ou monitorização ambiental que registam posição, tempo e, em alguns casos, outros atributos semânticos. Este processo pretende agrupar objectos segundo as suas similaridades espaciais e temporais ajudando assim a descobrir padrões interessantes e correlações em grandes conjuntos de dados. Um dos grandes desafios nesta área é a existência de vários tipos de dados espaço-temporais e não existe uma abordagem geral para tratar todos estes tipos. Outro desafio ainda por resolver é a capacidade para integrar várias dimensões no processo de clustering com uma abordagem geral. Além disso, foi possível verificar que poucos trabalhos de investigação usam o algoritmo SNN (Shared Nearest Neighbour) nas suas implementações o que dá a oportunidade para propor uma extensão inovadora para este algoritmo em particular. Este trabalho pretende implementar no algoritmo de clustering SNN a capacidade para lidar com dados espaço-temporais permitindo assim a integração do espaço, tempo e um ou mais atributos semânticos no processo de clustering. Neste documento, serão apresentados alguns conceitos sobre clustering, clustering espacial e clustering espaço-temporal assim como um resumo das principais abordagens usadas para fazer o clustering de dados espaço-temporais com algoritmos de clustering diferentes. Baseado nestas abordagens e na análise das suas vantagens e desvantagens, serão definidos os limites deste trabalho de modo a incorporar as dimensões espaço, tempo e atributo semântico no algoritmo SNN e, assim, propor a abordagem 4D+SNN. Os resultados apresentados neste trabalho são bastante promissores pois a abordagem proposta é capaz de identificar padrões interessantes em dados espaço-temporais. Concretamente, consegue identificar clusters tendo em consideração simultaneamente as dimensões espaço e tempo e também obtém bons resultados quando adicionando um ou mais atributos semânticos.