Revisión de técnicas de agrupamiento de minería de datos espaciales en un SIG

Enviado por gigarcia

ABSTRACT

Spatial data mining is the discovery of interesting relationships and characteristics that may exist implicitly in spatial databases. Knowledge discovery in databases (KDD) is also an important task in spatial databases since both, the number and the size of such databases are rapidly growing.The goal of this survey is to provide a comprehensive review of different clustering techniques in data mining. Clustering is a division of data into groups of similar objects. Each group, called cluster, consists of objects that are similar between themselves and dissimilar to objects of other groups. Data modeling puts clustering in a historical perspective rooted in mathematics, statistics, and numerical analysis. To this end, this paper has also an aditional contribution. We propose a new clustering method called CLARQ, whose aim is to identify spatial structures that may be present in the data. Experimental results shown that, when compared with existing clustering methods, CLARQ is very efficient and effective.

Keywords: Spatial Data Mining, clustering, cluster, partitioning, data mining, unsupervised learning, descriptive learning, exploratory data analysis, hierarchical clustering, probabilistic clustering, k-means, mineria de datos espaciales, bases de datos espaciales

1. INTRODUCCIÓN

La identificación de patrones comunes, asociaciones, reglas generales y nuevo conocimiento es hoy en día una actividad investigativa de gran interés (Fayyad et al, 1996). Utilizando algoritmos de minería de datos en una base de datos de un conocido supermercado, se encontró que el 80% de los médicos varones que con tarjeta compran artículos para dama en la ultima semana de abril o la primera de mayo (Kennedy et al., 1998).

Esta información será muy útil para orientar y dirigir la publicidad que se incorporará en su estado de cuenta, sin tener que imprimir publicidad sobrante o enviarla a otros que no exhiben ese comportamiento. De esta forma la minería de datos y la minería de datos espaciales revelan patrones o asociaciones que usualmente eran desconocidas (Holsheimer y Siebes, 1994). A estas técnicas se le han denominado también Descubrimiento de Conocimiento en Bases de Datos (Knowledge Discovery in Databases, KDD).

Investigadores y grandes compañías, en muchos campos han mostrado gran interés en la Minería de Datos y además han desarrollado diversos paquetes de software para llevar a cabo esta tarea (Piatetsky-Shapiro y Frawley, 1991). Hasta el momento la minería de datos y los SIG han existido como dos tecnologías separadas, cada una con sus propios métodos y enfoques para la visualización y análisis de datos. Particularmente, la mayoría del software SIG comercial tiene sólo una funcionalidad de análisis espacial muy básica (Bosque et al., 1994). Muchos son confinados al análisis de despliegues estadístico, como histogramas o diagramas de pie.

Actualmente, el proceso de integración de estas dos tecnologías ha sido crítico, ya que varias entidades privadas y gubernamentales con grandes bases de datos espaciales empiezan a descubrir el enorme potencial de la información encubierta en esas bases de datos geográficas.

2. TIPOS DE CONOCIMIENTO EN BASES DE DATOS

Las bases de datos espaciales se utilizan normalmente para guardar una variedad de información dependiendo del dominio de la aplicación elegida (Holsheimer y Siebes, 1994). Una base de datos espacial o geográfica constituye un continuo espacio-temporal en el cual las propiedades de un lugar particular se explican en términos de las propiedades de sus vecinos (Silberchatz, et al., 2001). De allí la gran importancia de las relaciones espaciales en el proceso de análisis. Los aspectos temporales para los datos espaciales son también un punto central pero muy raramente se toman en cuenta. En las bases de datos espaciales existen diferentes tipos de conocimiento (ver figura 1):

Conocimiento evidente SQL (Structured Query Language): La consulta enunciada con SQL es motivada por una hipótesis muy concreta. Las aplicaciones y los reportes generados de una base de datos en línea, asumen que es la información necesaria para la administración cotidiana de la actividad de negocio y que sólo de manera esporádica se requerirá de otra información.
Conocimiento multidimensional OLAP (On-Line Analytical Processing): El procesamiento analítico en línea OLAP es una forma de organizar datos para que se ajusten al modo que tienen los usuarios de analizarlos y administrarlos, de modo que la creación de los informes necesarios sea un proceso más fácil y más rápido. Cuando se crea un cubo OLAP a partir de una consulta, el conjunto de registros planos se convierte en una jerarquía estructurada, o cubo, que permite que los informes traten el nivel de detalle deseado. También se predefinen los valores de resumen de los informes que aceleran el proceso de cálculo de los mismos.
Conocimiento oculto (Knowledge Discovery on Databases, KDD): KDD es el nombre con que se conoce de forma global al proceso de extracción de conocimiento de bases de datos y como parte del proceso se encuentra el data mining. El Descubrimiento de Conocimiento en Bases de Datos es el proceso de identificación de patrones válidos, potencialmente útiles y comprensibles en los datos (Fayyad et al. 1996). El objetivo es la extracción de conocimiento de los datos, en el contexto de las bases de datos de gran tamaño. KDD es un proceso multidisciplinario que encierra: conocimiento, aprendizaje, bases de datos, estadística, sistemas expertos y representación gráfica, entre otros.

Figura 1. Tipos de conocimiento en bases de datos espaciales

3. MINERÍA DE DATOS ESPACIALES, MDE

La minería de datos espaciales (MDE) es el descubrimiento de conocimiento implícito y previamente desconocido en base de datos espaciales. La MDE se refiere a la extracción del conocimiento, de las relaciones espaciales, o de otros patrones interesantes almacenados no explícitamente en bases de datos espaciales. La MDE exige una integración de los datos que minan con tecnologías espaciales (Cabena et al. 1998). Puede ser utilizada para entender datos espaciales, descubriendo relaciones espaciales y relaciones entre los datos espaciales y no espaciales, construyendo bases de conocimiento espaciales, reorganizando preguntas y optimizando las bases de datas espaciales (Pineda et al. 1998).

Se espera que tenga usos amplios en sistemas de información geográfica, geo-marketing, detección remota, exploración de imágenes en bases de datos, proyección de imágenes médicas, navegación, control de tráfico, estudios ambientales, y muchas otras áreas donde se utilizan los datos espaciales.

El conocimiento a ser descubierto en los datos espaciales puede ser de varios tipos, como características representativas, estructuras o agrupamientos, asociaciones espaciales, solamente por mencionar algunos.

4. ARQUITECTURA DE UN SISTEMA DE MDE

Un sistema de MDE está configurado por la siguiente arquitectura (ver figura 2):

Base de datos: Puede ser de tipo base de datos normal, data warehouse, hoja de cálculo u otra clase de repositorio. A estos datos se le aplican técnicas de limpieza e integración.
Servidor de bases de datos: Utilizado para obtener la información relevante según el proceso de minería de datos.

Figura 2. Arquitectura de un Sistema Típico de Minería de Datos. (Tomada de Han and Kamber, 2001)

Base de conocimiento: Conocimiento del dominio para guiar la búsqueda y evaluar los patrones. Se tienen en cuenta las creencias de los datos. Los umbrales de evaluación y el conocimiento previo.
Algoritmo de minería de datos: Modular para realizar distintos tipos de análisis: Caracterización, Asociación, Clasificación, Análisis de grupos, Evolución (en espacio o tiempo) y Análisis de desviaciones.
Módulo de evaluación: Mide que tan interesante es un patrón. Interactúa con el algoritmo de Minería de Datos para guiar la búsqueda hacia patrones interesantes.
Interfaz gráfica: Interacción con el usuario. Elección de la tarea de minería de datos. Provee información para enfocar la búsqueda. Ayuda a evaluar los patrones. Explora los patrones encontrados y la base de datos original. Visualiza los patrones en distintas formas.

5. MÉTODOS DE MDE

Los métodos de MDE son aplicados para extraer conocimiento interesante y regular. Estos métodos pueden ser usados para entender los datos espaciales, descubrir relaciones entre datos espaciales y no espaciales, reorganizar los datos en bases de datos espaciales y determinar sus características generales de manera simple y concisa (Michalski et al. 1998).

Existen cinco grupos de métodos de MDE:

Métodos basados en generalización. Los cuales requieren la implementación de jerarquías de conceptos, en el caso de las bases de datos espaciales estas jerarquías pueden ser temáticas o espaciales. Una jerarquía temática puede ser ejemplificada al generalizar mango y piña a frutas. Una jerarquía espacial puede ser ejemplificada generalizando varios puntos en un mapa como una región y un grupo de regiones como un país.
Métodos de reconocimiento de patrones. Estos pueden ser usados para realizar reconocimientos y categorizaciones automáticas de fotografías, imágenes y textos, entre otros.
Métodos que usan agrupamiento. Consisten en crear agrupaciones o asociaciones de datos, cuando en estos existan nociones de similaridad (por ejemplo, distancia Euclidiana). Clustering es el proceso de agrupar datos en grupos o clusters de tal forma que los objetos de un cluster tengan una similaridad alta entre ellos, y baja con objetos de otros clusters.
Métodos explorando asociaciones espaciales. Permiten descubrir reglas de asociaciones espaciales, es decir, reglas que asocien uno o más objetos espaciales con otro u otros objetos espaciales (X -Y (c%)), donde X y Y son un conjunto de predicados espaciales o no espaciales y c% es la confianza de la regla. Su aplicación está en bases de datos grandes, donde puede existir una gran cantidad de asociaciones entre los objetos, pero la mayoría de ellos serán aplicables solamente a un pequeño número de objetos, teniendo en cuenta que la confianza de la regla puede ser baja.
Métodos que utilizan aproximación y agregación. Descubren conocimiento en base a las características representativas del conjunto de datos. La proximidad agregada es la medida de proximidad del sistema de puntos en el grupo en base a una característica en comparación con el límite del grupo y el límite de una característica. Las consultas de proximidad solicitan objetos que se hallen cerca de una posición específica

En figura 3 se observa la clasificación de los métodos de minería de datos espaciales:

Figura 3. Métodos para el descubrimiento de conocimiento en BDE. Tomado de J. Adhikary, 2001

6. ALGORITMOS DE AGRUPAMIENTO

En los últimos 30 años, los análisis de agrupamientos (cluster) se han aplicado fuertemente a muchas áreas tales como la medicina (clasificación de enfermedades,), química (agrupamiento de compuestos), estudios sociales (clasificación de estadísticas), entre otros.

Su principal objetivo es identificar estructuras o subclases de los objetos en las bases de datos espaciales y que tengan algún sentido. La ventaja principal de usar esta técnica es que las estructuras o los agrupamientos interesantes se pueden encontrar directamente en los datos sin tener ningún conocimiento de fondo.

A pesar de que no existe una definición general de un agrupamiento, se han desarrollado algoritmos que encuentran diferentes clases de clusteres: esféricos, lineales, irregulares, entre otros. Motivados por su amplia gama de aplicaciones los investigadores han desarrollado técnicas para agrupar datos de diferentes tipos: binarios, nominales y otras clases de variables discretas, variables continuas, similaridades y disimilaridades. En Kaufman y Rousseeuw, 1990 se discute y analiza con más detalle las anteriores definiciones.

6. 1 Divisiones de Algoritmos de agrupamiento

Existen tres divisiones principales de algoritmos de agrupamiento: el agrupamiento particional, agrupamientos jerárquico y agrupamiento basado en localidades (figura 4). El agrupamiento particional (Partitional), desarrolla una partición de los datos tal que los objetos en un grupo son más similares a algunos que ellos a los objetos en otros grupos (Kennedy et al., 1998). Este método construye k particiones de los datos, donde cada partición representa un grupo o cluster. Cada grupo tiene al menos un elemento y cada elemento pertenece a un solo grupo.

También, crea una partición inicial e iteran hasta un criterio de paro. Los más populares utilizan k-medias y k-medioides (por ejemplo, PAM, CLARA y CLARANS). El agrupamiento jerárquico (hierarchical), combina grupos pequeños en grupos grandes, o particiona los grupos grandes. En el agrupamiento basado en localidades (locality-based), los objetos del grupo se basan en las relaciones locales, y por consiguiente la base de datos puede examinarse en un paso.

6.2 Clasificación de los algoritmos de agrupamiento.

Se habla de algoritmos directos, constructivos o heurísticos cuando no optimizan ninguna función criterio. Si usan una función criterio a optimizar se habla de algoritmos indirectos o por optimización(Ester et al. 1996).

Por otro lado, según la filosofía empleada para la construcción de agrupamientos se distinguen: algoritmos aglomerativos o incrementales (bottom-up) los cuales parten de patrones aislados y tienden a unir agrupamientos de acuerdo a algún umbral fijado (por ejemplo, AGNES). Los algoritmos divisivos o decrementales (top-down) se generan a partir de agrupamientos ya establecidos y tienden a crear nuevos agrupamientos más homogéneos. (por ejemplo, DIANA). Por su parte los algoritmos mixtos como su nombre indica, incorporan procesos de creación y mezcla de nuevos agrupamientos.

Figura 4. División de algoritmos de agrupamiento en un MDE

Existen otros métodos de agrupamiento; Los métodos basados en densidades en los que se agrupan objetos mientras su densidad (número de objetos) en la "vecindad" este dentro de un cierto umbral (por ejemplo, DBSCAN, DENCLUE). Lo métodos basados en celdas en los cuales se divide el espacio en celdas a diferentes niveles (por ejemplo, STING, CLIQUE); y los métodos basados en modelos donde se debe encontrar un modelo para cada cluster que mejor ajuste los datos de ese grupo (por ejemplo, COBWEB, AutoClass).

7. TÉCNICAS DE MDE BASADAS EN AGRUPAMIENTOS

El clustering o agrupamiento es el proceso de particionar un conjunto de datos (u objetos) en un conjunto de subclases significativas llamadas grupos (clusters). Un grupo es una colección de objetos de datos que son similares a otros y así pueden ser tratados colectivamente como un grupo.

El agrupamiento es una forma de clasificación no supervisada en la que, a diferencia de la supervisada, no se conocen las etiquetas de las clases (no hay clases predefinidas) y puede que tampoco se conozca el número de grupos.

Un buen método de agrupamiento produce grupos de alta calidad en los cuales la similaridad intra-clases (esto es, dentro del grupo) es alta y la similaridad inter-clase (entre las clases) es baja. La medida de similaridad se define usualmente por proximidad en un espacio multidimensional. A continuación se presentan los algoritmos de agrupamiento PAM, CLARA desarrollados por Kaufman y Rousseeuw, CLARANS desarrollado por Ng y Han, 2002 basado en los dos primeros, SD CLARANS, NSD CLARANS Y CLARQ desarrollado en Colombia por el autor.

7.1 PAM (Partitioning Around Medoides)

El algoritmo PAM fue desarrollado por Kaufman y Rousseeuw. En éste se asume que existen n objetos, y que para encontrar K clusters (agrupamientos), se determina un objeto representativo para cada agrupación. Tal objeto representativo, es un punto centralmente localizado dentro de un grupo, denominado medoide. Después de seleccionar los medoides de K, el algoritmo intenta analizar todos los pares posibles de objetos, tales que, cada objeto no seleccionado es agrupado con el medoide más similar (Son et al., 2000). La calidad de la medida de agrupamiento se calcula para cada combinación.

La mejor opción de puntos en una iteración, se elige como los medoides para la iteración siguiente (figura 5). El coste de una sola iteración es O(K(n-K)²). Por lo tanto el computo es ineficaz para los valores grandes de n y de K.

Figura 5. Algoritmo PAM Tomado de Son et al. 2000.

7.2 CLARA (Clustering Large Applications).

La diferencia entre los algoritmos de PAM y CLARA es que el último esta basado en el muestreo, solamente una pequeña porción del total de datos se elige, mientras que un representante de los datos y los medoides se elige de esta muestra usando PAM.

La idea es que si la muestra se selecciona al azar, después representa correctamente el conjunto total de datos y por lo tanto, los objetos representativos (medoides) elegidos, serán similares como si se eligiera del conjunto total de datos (WEISS y INDURKHYA, 1998). CLARA dibuja muestras múltiples y realiza mejores agrupamientos. CLARA puede ocuparse de datos más grandes que PAM. La complejidad de cada iteración ahora se convierte O(KS² + K(n-K)), donde S es el tamaño de la muestra. PAM busca los mejores medoides de K entre un conjunto total de datos, mientras que CLARA busca los mejores medoides de K entre la muestra seleccionada del conjunto total de datos.

7.3 CLARANS (Clustering Large Applications based on RANdomized Search)

CLARANS, mezcla de PAM y CLARA, fue desarrollado por NG R. y HAN J. 2002, para el análisis de agrupamientos. CLARANS dibuja una muestra con una cierta aleatoriedad en cada paso de la búsqueda. El proceso de agrupamiento se puede presentar como buscar un gráfico donde la solución es cada nodo potencial, es decir, un sistema de medoides de K.

El agrupamiento obtenido después de sustituir un solo medoide se denomina el vecino de agrupamiento actual. El número de vecinos que se manejarán aleatoriamente son restringidos por el máximo vecino del parámetro. Si encuentran a un vecino mejor CLARANS se mueve al nodo del vecino y el proceso comienza otra vez; si no el agrupamiento actual produce un grado óptimo local.

Si se encuentra en el grado óptimo local CLARANS comienza con un nuevo nodo aleatoriamente seleccionado, en búsqueda para un nuevo grado óptimo local. El número de los grados óptimos locales que se buscarán también es limitado por el parámetro de números locales.

7.4 CLARQ (Clustering Large Applications based on Quadrant analysis)

El algoritmo CLARQ fue desarrollado por García, 2003, quién propone usar un análisis previo de la estructura de los datos mediante un análisis de cuadrantes de los puntos a analizar, el autor propone una forma de realizar cálculos solamente en aquellos pares de objetos que puedan mejorar la calidad del agrupamiento, en lugar de realizar un chequeo de todos los pares de objetos tal y como se realiza en los algoritmos anteriores.

El análisis de cuadrantes es una técnica de estadísticas espaciales para el análisis de fenómenos de datos geográficos de tipo punto (mapas puntuales). Las URG (uniform regular grids) o cuadrantes son el caso más simple de estructura en el modelo de datos raster: el terreno se "recubre" con un mosaico de teselas cuadradas que representan la unidad de información elemental donde cada tesela posee el valor medio de la zona cubierta para la variable correspondiente.

El análisis requiere la imposición de grillas de igual tamaño (cuadrantes) sobre los puntos para estimar el grado de aleatoriedad en su distribución. Si los puntos están uniformemente distribuidos, se espera que cada cuadrante contenga el mismo número de puntos. La prueba del chi-cuadrado X2 para la bondad del ajuste de la hipótesis de que no existe diferencias entre el número de puntos de cada cuadrante, está dada como:

X2 = å i (Oi – Ei)2/Ei

Donde O es el número de puntos observados y es la frecuencia de cuadrantes con un número igual de puntos. E es el número de puntos esperados y es el total de puntos datos (x) dividido por el núemro de cuadrantes (m). La aletoriedad espacial en el patrón de distribución de los puntos se estima utilizando la distribución de Poisson. Se asume que si x puntos existen en un área con m subáreas de igual tamaño (cuadrantes), la probabilidad P(x) de que x puntos están en una de esas subáreas es:

P(x) = [e-m mx] / x!

Donde x, el numero esperado de puntos en cada cuadrante no debe ser menos de 5. El número esperado de cuadrantes que contienen x puntos es calculado entonces por:

E(x) = P(x)*m

El valor que se retorna del chi-cuadrado X2 es chequeado contra el valor crítico X2 del disponible en cualquier tabla estadística estándar (df = m-2) para validar la anterior hipótesis. Esta técnica se ha probado con éxito la estimación de distribución de especies en ecología y distribución de fenómenos de puntos en geografía (García, 2003).

8. CONCLUSIONES

Con la presentación de herramientas de minería de datos espaciales este trabajo propone varios métodos para el descubrimiento de conocimiento en bases de datos espaciales muy grandes. Estos métodos combinan las áreas ya maduras de la ingeniería de sistemas como el aprendizaje de máquinas, bases de datos y estadística con áreas de la heurística.

Se demostró que la minería de datos espaciales es un campo de investigación promisorio con amplias aplicaciones en SIG, sensores remotos, visión robótica, entre otros.

A pesar de que este campo es muy joven, se estudiaron varias técnicas y algoritmos para descubrir conocimiento en bases de datos espaciales. En el estudio de los métodos existentes para minería de datos espaciales de la presente tesis se mencionaron cada una de las fortalezas y debilidades de los métodos. Esto permitió observar cuales serían las futuras direcciones y sugerencias para hacer investigación en minería de datos espaciales.

Existe una variedad de tópicos no explorados y problemas que hacen atractivo el campo de investigación en descubrimiento de conocimiento en bases de datos espaciales. Por ejemplo, faltan refinar los algoritmos de agrupamiento cuando se trabaja con mapas de polígonos.

9. BIBLIOGRAFÍA

BOSQUE J., GARCÍA E. & SALADO Mª J. (1994) Sistemas de Información Geográfica: Prácticas con PC ARCINFO e IDRISI. Editorial Addison-Wesley Iberoamericana y Ra-ma.

CABENA P., HADJINIAN P., STADLER R., VERHEES J. & ZANASI A. (1998) Discovering Data Mining. Prentice Hall.

ESTER M., KRIEGEL H.-P., SANDER J. & XU X. (1996) A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with noise. Published in Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining.

FAYYAD U.M., PIATETSKY-SHAPIRO G., SMYTH P. & UTHURUSAMY, R. (1996) Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press.

GARCÍA G. I. (2003) CLARQ, Un método para el análisis eficiente de grandes bases de datos espaciales. GIGACOL Geomatics Engineering Laboratory. (en preparación).

HOLSHEIMER M. y SIEBES A. (1994) Data mining: The search for knowledge in databases. In CWI Technical Report CS-R9406, Amsterdam, The Netherlands.

KENNEDY R. L., LEE Y., VAN ROY B., REED C. D. & LIPPMAN R.P. (1998) Solving Data Mining Problems Through Pattern Recognition. Prentice Hall.

MICHALSKI R. S., BRATKO I. & KUBAT M. (1998) Machine Learning and Data Mining, John Wiley & Sons.

NG R. & HAN J. (2002) CLARANS: A Method for Clustering Objects for Spatial Data Mining., Member, IEEE Computer Society. IEEE Transactions on knowledge and Data Engineering, vol. 14, no. 5, september/october.

PIATETSKY-SHAPIRO G. & FRAWLEY W. J. (1991) Knowledge Discovery in Databases. AAAI/MIT Press.

PINEDA L., VEGA J. & DORADO A. (1998) Evaluación y Selección de una Técnica de Minería de Datos.. Facultad de Ingeniería Pontificia Universidad Javeriana.

SILBERCHATZ A., KATH H. & SUDARSHAN S. (2001). Fundamentos de Bases de datos. Tercera Edición.

SON E. J., IN-SOO K., KIM, T. W. & LI, K. (2000). A Spatial Data Mining Method by Clustering Analysis. Information System and Engineering Laboratory, Department of Computer Science, Pusan National University.

WEISS S. M. & INDURKHYA N. (1998). Predictive Data Mining, Morgan Kaufmann Publishers.

Autor:

Ing. MSc. Gustavo Iván García

GIGACOL Geomatics Engineering Laboratory

http://www.gigacol.com

Bogotá, Colombia