Búsqueda dinámica de patrones sobre trayectorias

Abstract

Hoy en día existen diversas fuentes de datos móviles tales como redes inalámbricas, GPS, y otras, que nos permiten recolectar las ubicaciones geográficas de objetos de manera constante generando grandes colecciones de datos. Estos datos pueden ser usados para generar trayectorias de objetos, donde una trayectoria es una secuencia de segmentos de líneas representando el movimiento continuo de un objeto entre dos instantes de tiempo. Existen aplicaciones de minería de datos que permiten obtener patrones de trayectorias de objetos, es decir, encontrar comportamientos similares que siguen las trayectorias. Estos patrones son útiles, por ejemplo, para decidir sobre planificación urbana, analizar congestión vehicular, comprender migración de animales, estudiar comportamiento de fenómenos naturales como huracanes, etc. En esta tesis se presenta un nuevo concepto de trayectoria agregada y se presentan algoritmos para obtenerlas de manera dinámica. Una trayectoria agregada corresponde a una nueva trayectoria que se obtiene a partir de un conjunto de trayectorias que siguen un patrón similar de comportamiento. Una trayectoria agregada no solo muestra el patrón de comportamiento, sino que además, nos indica la densidad de ese patrón. El procesamiento para obtener una trayectoria agregada se realiza en dos fases: (i) obtención de clústeres o grupos de segmentos de trayectorias diferentes y (ii) agregación de clústeres similares. En esta tesis proponemos aplicar un procesamiento de obtención de clústeres que permita capturar relaciones entre sub-segmentos de segmentos de trayectorias que los algoritmos comunes de la literatura. Además, nuestros algoritmos calculan trayectorias de manera dinámica, a diferencia de otros algoritmos de búsqueda de patrones sobre trayectorias que realizan el procesamiento de manera estática. Es decir, el proceso de construcción de trayectorias agregadas se adapta a medida que se procesan nuevas trayectorias y no es necesario procesar todo el conjunto de trayectorias desde cero si nuevas trayectorias son consideradas en la búsqueda de la trayectoria agregada. Finalmente, a diferencia de otras propuestas no solo se considera la cercanía espacial de trayectorias, sino que además la cercanía temporal. La evaluación experimental realizada comparando resultados en el estado de arte muestra que los algoritmos propuestos son eficaces en el cómputo de trayectorias agregadas.