UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 1

Técnicas de Métodos Relacionales y Estructurales basadas en procedimientos relacionales

Mervy Villanueva Mogrovejo

Edgar Álvarez Valdez

Ana María Condori

at_ti_cus19@hotmail.com

edgar_45_3@hotmail.com

merry_c_v @hotmail.com

UNIVERSIDAD JOSE CARLOS MARIATEGUI SEDE ILO

RESUMEN

Data mining a lo largo de la historia ha sido llamado de distintas

maneras. A partir de los años sesenta los estadísticos utilizaban el

termino de data fishing (pesca de datos) o data dredging (filtración

de datos) con la idea de encontrar correlaciones sin una hipótesis

previa en bases de datos con ruido.

Uno de los aspectos que se debe tener claro en el proceso KDD es

distinguir entre una tarea y un método de minería de datos, existen

una serie delimitada de tareas descriptivas y predictivas las cuales

requieren métodos, técnicas o algoritmos, en este paper de

investigación tocaremos solamente todo lo que concierne a los

métodos relacionales y estructurales como por ejemplo

Programación lógica inductiva (ILP por sus siglas en ingles),

Aprendizaje basado en grafos, Modelos probabilísticos

relacionales, Aproximaciones relacionales basadas en

distancia, Arboles de decisión relacionales, Reglas de

asociación relacionales, Inducción de programas lógico-

funcionales., los cuales favorecerán a un trabajo más organizado y

sistematizado durante el análisis y al validar los resultados todo esto

evaluando en sí que técnicas usar para el análisis respectivo.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 2

Palabras Claves: métodos relacionales y estructurales,

programación lógica inductiva, aprendizaje basado en grafos,

modelos probabilísticos relacionales, aproximaciones relacionales

basadas en distancia, arboles de decisión relacionales, reglas de

asociación relacionales, Inducción de programas lógico-funcionales

Summary:

Data mining throughout history it has been called in different ways.

From the sixties that the statistical used the term data fishing data)

or data dredging (data leakage) with the idea of finding correlations

without a previous hypothesis in databases with noise.

One of the aspects that should be very clear in the KDD process is to

distinguish between a task and a method of data mining, there are a

defined series of descriptive and predictive tasks which require

methods, techniques or algorithms, in this research paper stringed

instruments only everything that affects the relational and structural

methods As for example inductive logic programming (ILP by its

acronym in English), learning based on graphs, probabilistic

relational models, approximations based on relational distance,

relational decision trees, association rules relational, induction

programs of logical-functional., which will be good for a work more

organized and systematized during the analysis and to validate the

results all this evaluating if what techniques to use for analysis.

Key Words: Relational and structural methods, inductive logic

programming, learning based on graphs, probabilistic relational

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 3

models, approximations based on relational distance, relational

decision trees, association rules relational, logical induction

programs-functional

1. INTRODUCCION

Una de las partes de mayor variedad dentro de la obtención de

conocimiento a partir de bases de datos es la que corresponde

a las técnicas de minerías de datos, esto debido a muchas

características que pueden influir a la hora de tomar la

decisión, como el objetivo del proyecto, los tipos de variables

que influyen en este, limpieza de los mismos, entre muchos

otros que existen. Para esto se lleva a cabo un proceso de

extracción de conocimiento como se puede observar en la

Figura 1.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 4

Figura 1. PROCESO KDD

Como se mencionó anteriormente hay que tener claro que los

conceptos de tarea y método de minería de datos, las tareas de

DM se conforman en 2 grandes grupos:

Predictivas: tratan de problemas y tareas en los que hay

que predecir uno o más valores para uno o más ejemplos.

Dependiendo de cómo se ha la correspondencia entre los

ejemplos como por ejemplo :

Clasificación(discrimi

nación)

Clasificación

suave

Estimación de

probabilidad

CategorizaciónPreferencias o

priorizaciónRegresión

Descriptivas: Buscan describir los datos existentes,

algunas tareas descriptivas más delimitadas:

Agrupamient

o

Correlaciones y

Factorizaciones

Reglas de

asociación

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 5

Dependencias

Funcionales

Detección de

valores e

instancias

anómalas

Cada una de las tareas mencionadas requieren métodos,

técnicas o algoritmos para resolverlas, como:

Este trabajo se enfoca propiamente a la técnica de métodos

relacionales y estructurales, que es una técnica bastante

expresiva y que maneja los datos de manera estructural,

permitiendo obtener patrones de relaciones y recursivos. Otra

característica de este es que permite definir el conocimiento

previo en forma de reglas. Es considerado como una de los

modelos de mayor compresibilidad entre toda la variedad que

existe.

Relacionales y estructurales

Algebraicas y estadisticas Bayesianas

Basadas en conteos de frecuencias y

tablas de contingencia

Arboles de decisión y sistemas de

aprendizaje de reglas

redes neuronales artificiales

Núcleo y máquinas de soporte vectorial

Estocásticas y difusas

casos, en densidad o distancia

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 6

El objetivo de los métodos de minería de datos es extraer conocimiento de grandes volúmenes de datos.

Ejemplo Sencillo:

Si se usa un sistema de aprendizaje atributo – valor podríamos descubrir algunos patrones.

SI Duración (Curso)

Si Duración (Curso) <15 ENTONCES Seminario (Curso)

Pero no se podrían obtener patrones complejos que involucren registros de ambas tablas, por ejemplo quien es el profesor del estudiante. Para patrones complejos se usan los métodos RDM (relation data mining) o una relación universal.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 7

2. Programación Lógica y Base de datos

La programación lógica es un paradigma de programación que surgió en los años 70s y fue idea de Colmerauer Kowalski de que la lógica de primer orden, o un subconjunto de ella podrían usarse como lenguaje de programación.

La programación lógica tiene como fundamento la lógica de las cláusulas de Horn1:

B <- A1, A2, ..., An

Podía tener una o varias condiciones A1, A2, ..., An, pero con una única conclusión B1. Por lo que si A1, A2, ..., An son ciertas, se puede inferir que B1 es cierta. Horn también demostró que cualquier problema que pueda expresarse en forma lógica clausal se puede transformar en un conjunto de «cláusulas de Horn2».

Así, el ejemplo anterior de la paternidad, que presentaba ambigüedad, se debía haber escrito de la forma:

Hijo (Luis, Fernando, María)

Hijo (Beatriz, Esteban, Teresa)

Padre (Y) <- hijo (X, Y, Z)

Madre (Z) <- hijo (X, Y, Z)

NOTA: Indica el primer aserto que Luis es hijo de Fernando y María; y el segundo, que Beatriz es hija de Esteban y Teresa. Las reglas lógicas señalan que si X es hijo de Y y Z, entonces Y es el padre y Z es la madre.

Por lo que a la pregunta (cuestión lógica):

? Padre (X)El sistema responderá:

Y a la pregunta: ? Madre (X) El sistema responderá:

1 Alfred Horn, un lógico alemán, quién en 1951 llegó a la conclusión que para realizar una inferencia correcta y así eliminar las ambigüedades, las cláusulas sólo debían de tener una conclusión2

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 8

> X= Fernando, Esteban > X= María, Teresa

3. Programación Lógica Inductiva

Este tipo de programación está basada en el paradigma lógico.

Según

(Hernández, Ramírez, & Ferri, Métodos relacionales y

estructurales, 2004), el método ILP se define como “la

inferencia de una teoría P (un programa lógico) desde una

evidencia E”. Para llegar a este punto se necesita una teoría de

conocimiento, que es otro programa lógico.

Lo interesante del ILP es que es la vía contraria la

programación lógica: mientras que este utiliza reglas para

obtener y encontrar hechos, la ILP utiliza hechos para

encontrar reglas, es decir, la programación lógica es un

proceso deductivo, mientras que la ILP es un proceso

inductivo.

El ILP se puede definir semánticamente de la siguiente forma:

(FIGURA 2).

Figura 2: Formas semánticas ILP

Dónde: el símbolo representa la consecuencia lógica

Se tiene que buscar hipótesis completas, que cubran todos los ejemplos positivos y ninguno de los negativos, para esto se utiliza los métodos top-Down y bottom-up.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 9

3.1.Subsunción θ

Uno de los mayores problemas del ILP es que pueden surgir

muchas teorías a partir de los eventos o hechos analizados, de

los cuales, muchos de esto pueden ser más generales que

otros, lo que puede provocar una verdadera confusión de cuál

es la teoría que más nos sirve para nuestro propósito final. La

θ-subsunción nos permite indicar si una regla es más general

que otra, y por lo tanto, considerarla como una regla más

confiable o que va a abarcar un mayor grupo de datos en una

misma regla. Esto es importante a la hora de utilizar métodos

top Down o bottom-up para obtener las reglas.

3.2. Método TOP DOWN

Este es una de los métodos que se utiliza en la técnica ILP. La

idea es ir buscando las hipótesis o cláusulas que cubran los

ejemplos positivos de una forma especializada, es decir,

comenzando desde la cláusula más general y van buscando

clausulas más específicas que cubran lo esperado.

Alguno de los sistemas que utilizan este método son FOIL y

FILP.

Los programas van creando las cláusulas de una en una,

usando la especialización.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 10

Figura 3: Método Top Down

3.3. Método Bottom Down

Contrario al método top-Down, el método bottom-up parte de

las clausulas más específicas para ir obteniendo las clausulas

más generales, buscando así todas las reglas posibles que

cubran el problema.

Algunos operadores clásicos de generalización de cláusulas

tenemos:

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 11

• Eliminación de condiciones.

• Transformación de constantes en variables.

• Transformación de conjunciones en disyunciones.

Pero el ILP ha desarrollado sus propios operadores para llegar

a este propósito.

Los dos operadores más importantes son los siguientes:

Generalización menos general de dos clausulas: Este

operador busca la generalización menos general que

cubra dos clausulas, es decir, de las clausulas simples, se

busca la que sea la más específica, pero que a la vez, sea

general para ambas.

Resolución inversa: este operador lo que hace es

invertir los pasos de resolución. Los que hace es si se

tiene una clausula y su resultado, se busca otra cláusula

que puede llegar a tener el mismo resultado. Lo

interesante de este operador es que puede utilizar

predicados que no existen en el grupo original de

predicados, permitiendo que la búsqueda sea menos

sesgada.

3.4. Bias inductivas de programación lógica inductiva

Un bias inductivo es cualquier información que influye en el

aprendizaje inductivo desde ejemplos. Uno de los problemas de

los ejemplos de aprendizaje es que puede llegar a ser muy

ineficiente, en especial, en cuestión de tiempo.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 12

En ILP hay 3 tipos:

Bias del lenguaje :

Busca que el algoritmo de inducción mejore

por medio de la reducción del espacio de la

hipótesis.

Bias de búsqueda:

Reduce el espacio de búsqueda, explorando

solo parcialmente todo el espacio disponible.

Criterio de parada:

Indica parámetros o condiciones de paradas.

3.5. ILP y Recursividad

La recursividad es una herramienta que es muy útil a la hora

de que las hipótesis de aprendizajes sean muchos mejores, ya

que pueden encontrar

Patrones que no se ven a primer nivel de datos de ejemplos.

Sin embargo, para el ILP, este ha sido uno de los problemas

por resolver más grandes. Actualmente los ILPs pueden

resolver sistemas recursivos sencillos, pero se quedan muy

cortos a la hora de sistemas recursivos más complejos.

4. Programación lógica inductiva y minería de datos

Como muchos otros métodos y técnicas de minería de datos, el

ILP se puede utilizar para dos propósitos, ya sea predictiva

(para aprender la definición de un predicado) o descriptiva,

que nos permite aprender patrones generales

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 13

4.1. Aproximación Directa

Este tipo de aproximación utiliza tanto técnicas predictivas

como descriptivas trabajando directamente sobre la base de

datos, aunque muchas veces es necesario un pre

procesamiento inicial.

Muchas veces se trabaja sobre bases de datos relacionales,

cuyo primer paso es el de transformar los datos a un formato

textual que entienda el ILP. Esto puede ser muy difícil ya que

muchos lenguajes lógicos no utilizan tipificación de variables,

algo que si existe en los lenguajes relacionales.

Cuando ya se tiene el sistema traducido, se dispone de

especificar las tareas.

Muchos sistemas solo pueden realizar una tarea a la vez. Si el

propósito es predictivo, se debe indicar cuál es el predicado

principal. Si el propósito es descriptivo, se debe indicar el

atributo o argumento clave.

4.2. Aproximación mediante proposicionalizacion

Lo que muchos sistemas hacen, es una combinación de los dos.

Basados en una base de datos relacional, se obtiene los datos

necesarios y se transforman a un sistema proposicional

(atributo-valor) y a partir de aquí se aplica algoritmos basados

en este tipo de minería de datos. Cuando se obtienen los

resultados, se transforman de nuevo a un método relacional.

Muchas veces esto es preferible ya que los métodos

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 14

proposicionales pueden ser mucho más veloces o devolver

valores numéricos más precisos que los relacionales.

4.3. Base de datos Inductivas

Una base de datos inductiva es una base de datos en la que se

almacenan los patrones inducidos por alguna técnica de

minería de datos, y puede ser interrogado usando lenguajes de

consulta

5. Otros métodos relacionales y estructurales

Existen otros métodos, que aunque menos estudiados que el

ILP, también son útiles para sistemas relacionales y

estructurales.

5.1. Aprendizaje basado en grafos

Hay muchas áreas, como son la química por medio de

moléculas, o sistemas de transportes, donde la estructura de

datos más adecuada de ser analizada es por medio de grafos.

La idea de este método es el de representar las evidencias en

forma de grafo.

Teniendo la evidencia deseada transformada en una

representación de grafos, se dispone de encontrar el o los

subgrafos que generalizan o que permita encontrar la hipótesis

o el patrón deseado.

Representación de una evidencia positiva con notación de

grafos: (Figura 4)

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 15

Figura 4: Evidencia positiva notación de

grafos

Para encontrar el subgrafo patrón, se puede utilizar alguna de

las siguientes técnicas:

•Aproximación basada en búsqueda voraz: buscan

encontrar la solución óptima en cada paso. Si en un paso se ve

que la solución óptima es mejor que la encontrada

anteriormente, esta pasa a ser la nueva solución óptima, en

caso contrario, se deja la solución óptima encontrada

anteriormente.

• Aproximación basada en ILP: Se puede utilizar ILP para

este método, ya que muchas veces uno puede representar los

grafos en representación de primer orden, así como tener

conocimiento de base almacenado previamente para poder

resolver problemas de forma más rápida.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 16

• Aproximación basada en bases de datos inductivas:

Simplemente se almacena los subgrafos encontrados en una

base de datos inductivas para luego ser utilizados.

• Aproximación basada en la teoría de grafos: Básicamente

lo que se pretende con este tipo de aproximación es el de

iniciar con grafos comunes, iniciando con alguno que tenga

solo un vértice, y luego ir aumentando los vértices, para ir

encontrando los patrones requeridos.

• Aproximación basada en funciones de núcleo: Más que

trabajar sobre el grafo en sí, realmente este utiliza la

información de los enlaces y de los vértices, para encontrar un

origen en común (núcleo) entre los distintos grafos a analizar.

5.2. Modelos probabilísticos relacionales

Este modelo es una extensión de las redes bayesianas, que en

lugar de utilizar el lenguaje de Horn para este propósito, utiliza

el lenguaje relacional para su utilización. Lo que hace es que

van asignando probabilidades de que una relación ocurre, y

después, utilizando los valores de entradas, permite clasificar o

describir las relaciones más comunes existentes.

5.3. Aproximaciones relacionales basadas en distancia

Este método va analizando los predicados de ejemplos que se

tienen y luego se va estudiando la distancia a distintos niveles,

donde el nivel inicial o cero son los predicados originales, luego

el nivel 1 son los predicados relacionados directamente con los

predicados del nivel cero y así va sucesivamente hasta llegar a

las relaciones más profundas

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 17

5.4. Arboles de decision relacionales

Son similares a los arboles de decision proposicionales, pero

cambiando el sistema de valor/atributo con el de expresiones

de un lenguaje relacional. (FIGURA 5)

FIGURA 5: Ejemplo de árbol de decision

relacional

5.5. Inducción de programas lógico-funcionales

En la programación lógica las funciones deben tratarse

artificialmente a través de predicados con un argumento más

que representa el resultado de la función. (Predicado

(entrada1, entrada2, entrada3, entrada N, salida)).

Los ejemplos de minería se caracterizan por usar solo ejemplos

positivos mientras que muchos sistemas de ILP requieren de

presencia de ejemplos negativos.

Usar lenguajes lógicos funcionales (IFLP(inductive functional

logic programming)) para la representación del conocimiento

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 18

nos permite disponer de las ventajas como: la presencia de

variables lógicas propias de la programación lógica.

Las disponibilidad de utilizar información de tipos y de definir

funciones, propias de la programación funcional.

6. Conclusiones

• Los métodos relacionales y estructurales son más útiles para

problemas donde existe una gran variedad de estructuras y

relación entre ellas, como análisis de moléculas.

• El método de programación lógica inductiva es el método

más estudiado y utilizado dentro de todo el conjunto de

métodos.

• Normalmente se utiliza alguna regla o dato para permitir

definir cuando una hipótesis es la que se busca o no. Esta regla

busca encontrar la generalización de las mismas y es llamada

con el nombre de θ-subsunción

• Hay dos formas de utilizar el ILP: el top-Down y el bottom-up.

• Varios métodos muchas veces utilizan la combinación de dos

o más metodologías para encontrar una solución al problema,

explotando de mejor forma las características de cada una

• El ILP tiene actualmente serios problemas a la hora de

considerar recursividad entre estructuras y relaciones.

• La gran mayoría de estos métodos se basan en paradigmas

lógicos, explotando fuertemente las características de este

paradigma.

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 19

7. Referencias y Linkografia

Por Francisco Jose Correa Zabala , Departamento de

Sistemas e Informatica y Computacion , Universidad

Politecnica de Valencia, Tesis para Optar el título de doctor

en Informatica., Julio del 2002

http://www.dsic.upv.es/docs/bib-dig/tesis/etd-10272003-

01496/principal.pdf

Descripcion en VHDL de arquitecturas para implementar el

algoritmo CORDIC, proyecto de investigación para optar el

título de Ingeniero Informatico

http://sedici.unlp.edu.ar/bitstream/handle/10915/3835/

Documento_completo.pdf?sequence=15

Enciclopedia Didactica LeeColima.com.Mx

La Cláusula de Horn – Programacion Logica

UNIVERSIDAD JOSE CARLOS MARIATEGUIIngeniería de Sistemas e Informática Sistemas de Información II 20

http://leecolima.net/2012_a/leecolima.no-ip.org/2012/

leediccionario.dll8503.html?&pase=94761&art_frace=La

%20cl%E1usula%20de%20Horn%20-%20programaci%F3n

%20L%F3gica%20Fue%20Alfred%20Horn,%20un%20l

%F3gico%20alem%E1n,%20qui%E9n%20en

%201951%20lleg%F3%20a%20l

Por Mercerdes Ramirez, Caracas 30 de Julio 2003

Base de datos

http://www.monografias.com/trabajos14/basededatos/

basededatos.shtml

Por Andrey Garbanzo Vargas, Tarea 1 Base de datos II ,

Centro Interuniversitario de Alajuela, provincia de Costa

Rica, 09 de Octubre del 2011

http://es.scribd.com/doc/68122945/Metodos-relacionales-y-

estructurales

Por GA Osorio Zuluaga - 2009, Apuntes de mineria de datos,

http://www.bdigital.unal.edu.co/2037/2/

germanaugustoosoriozuluaga_Parte2.pdf