Autor(es):
Oliveira, João Ricardo Leite Mota 
Data: 2013
Identificador Persistente: http://hdl.handle.net/1822/29459
Origem: RepositóriUM - Universidade do Minho
Assunto(s): Clustering; Density-based clustering; Spatio-temporal data; Distance function; Spatio-temporal clustering
Descrição
Dissertação de mestrado em Engenharia e Gestão de Sistemas de Informação 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.
