GeoCluster: Librería de algoritmos de agrupamiento para objetos geoespaciales

Beltrán Jorba, Javier
López Pellicer, Francisco Javier (dir.)

Universidad de Zaragoza, EINA, 2016
Departamento de Informática e Ingeniería de Sistemas, Área de Lenguajes y Sistemas Informáticos

Graduado en Ingeniería Informática

Resumen: Este trabajo consiste en el desarrollo de una librería que, a partir de una fuente de datos geoespaciales, sea capaz de generar conjuntos utilizando algoritmos de agrupamiento. En concreto, se ha implementado el algoritmo DBSCAN y varias versiones de K-Means. Como la información geoespacial es compleja y puede tener atributos de todo tipo, la librería incluye diversas distancias que se pueden utilizar en el proceso de agrupamiento. Se ha comprobado que la distancia de Hausdorff es la mejor opción para medir la lejanía entre las geometrías de los objetos geoespaciales, ya que éstas suelen ser polígonos. Para poder aprovechar al máximo la complejidad de los datos geoespaciales, se ha construido una distancia combinada que tiene en cuenta diversos criterios al formar los conjuntos. Esto permite agrupar ciudades en base a su localización y a su número de habitantes, al mismo tiempo. Una vez ejecutado el algoritmo, el usuario debería interpretar los resultados para entender qué significan los conjuntos generados. Para ayudarle en esta tarea, la librería anota los conjuntos. El proceso consiste en analizar la información textual de cada elemento, utilizando un nomenclátor, y extraer los términos más repetidos. Así las anotaciones consistirán en información que es común al conjunto. Como la tarea de anotación está sujeta a fallos (por ejemplo, ambigüedades en la información de los objetos), se ha desarrollado una técnica de validación de las anotaciones generadas. Consiste en recurrir a una base de datos de unidades administrativas globales, y utilizarla para comparar la geometría de cada elemento con la que corresponde a sus anotaciones. Una anotación se considerará válida si ambas geometrías son aproximadamente iguales. La librería construida gestiona la lectura de datos geoespaciales desde ficheros ESRI Shapefile y desde bases de datos MySQL. También permite almacenar las agrupaciones generadas en ficheros ESRI Shapefile y en bases de datos MySQL. Por último se han realizado una serie de experimentos con conjuntos de datos reales y sintéticos. Éstos se han utilizado para resolver problemas sencillos de carácter geográfico y para extraer conclusiones sobre los algoritmos y distancias desarrollados.

Tipo de Trabajo Académico: Trabajo Fin de Grado