- Abstract
- Tipos de conocimiento en bases de
datos - Minería de datos
espaciales MDE - Arquitectura de un sistema
MDE - Métodos de un
MDE - Algoritmos de
agrupamiento - Técnicas de MDE basadas
en agrupamientos - Conclusiones
- Bibliografía
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
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.
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
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).
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.
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
Bogotá, Colombia