Un modelo de clustering temporal

Un modelo de Clustering Temporal
Tesis de Grado Ingeniería en Informática

Facultad de Ingeniería Universidad de Buenos Aires

TESISTA: María Daniela Navas Padrón 75.626 mnavas@mnavas.com.ar DIRECTOR: Prof. Dr. Juan M. Ale

Octubre 2004

Resumen
Clustering consiste en particionar el conjunto de datos en colecciones de objetos de manera que dentro de cada partición los objetos sean“similares” entre sí, y a su vez se “diferencien” de los objetos contenidos en otras particiones. En la literatura han sido propuestos muchos algoritmos para realizar el proceso de clustering, pero la mayoría de ellos tiene un enfoque estático, por lo tanto, estas soluciones no pueden ser aplicadas correctamente para datos más complejos, como colecciones de objetos espacio-temporales. En muchos casos,la información guardada en las bases de datos tiene una naturaleza espacial dinámica: además de tener datos espaciales, a menudo se asocian los mismos con información temporal, como marcas de tiempo (time-stamp) ,manejo de versiones, fechas o rango de fechas.

En el presente trabajo se propone un método de Clustering Temporal que realiza el proceso de clustering sólo teniendo en cuenta losatributos espaciales o “no temporales”, para distintos momentos de tiempo (dato aportado por los atributos temporales). Esto nos permite ver cómo varían los clusters durante el transcurso del tiempo, observar la trayectoria de los objetos, y obtener distintas estadísticas sobre el movimiento de clusters y objetos, que no se podrían obtener aplicando un algoritmo de clustering estándar.

AbstractClustering consists in partitioning a data group into object collections in a way that inside each partition the objects are "similar" between them, and at the same time they could be "differentiated" from the objects contained by another partitions. In the literature a lot of algorithms have been proposed to make the clustering process, but most of them have a static point of view, so they cannot beused correctly for more complex data, as spatial - temporal object collections. In many situations, the information stored at data bases has a dynamic spatial structure, as time stamps, version management, dates or date ranges.

In the present work a Temporal Clustering method is proposed which uses the clustering method only taking into account the spatial or “no temporal” attributes, fordifferent portions of time (information given by the temporal attributes). This allows us to see how the clusters modify with the time, determine the trajectory of the objects, and obtain different statistics about cluster and object movements, which could not be obtained by using a standard clustering algorithm.

María Daniela Navas Padrón: 75.626

Un modelo de Clustering Temporal Octubre 2004Indice
1 Introducción __________________________________________________ 5 1.1 Clustering 5 1.2 Clustering Temporal____________________________________________ 5 1.3 Contribución __________________________________________________ 6 1.4 Algoritmos de Clustering ________________________________________ 6
1.4.1 1.4.2 1.4.3 1.4.4 Algoritmos de Particionamiento (Partitioning Algorithms)________________________ 7 Algoritmos Jerárquicos (Hieralchical Algorithms) ______________________________ 7 Algoritmos Basados en Densidad (Density-Based Algorithms)____________________ 7 Algoritmos Basados en Grillas (Grid-Based Algorithms)_________________________ 8

1.5 Elección del algoritmo adecuado __________________________________ 8 1.6 Objetivo de la Tesis____________________________________________ 9 1.7 Estructura de la Tesis __________________________________________ 9 2 Trabajos Relacionados ________________________________________ 11 3 Modelo Temporal _____________________________________________ 13 3.1 Modelos temporales de datos ___________________________________ 13
3.1.1 Combinación y Eliminación de Información repetida___________________________ 14

3.2 Distintos esquemas...