Capítulo 5 :

Análisis de resultados

5.1 Limitaciones

Todo sistema de aprendizaje lleva asociada una serie de limitaciones que restringen su ámbito de aplicación a problemas concretos, en los que los datos de entrada deben estar expresados de una forma característica y los resultados se ajustan a cierto formato.

Entre los lenguajes empleados por los sistemas de aprendizaje simbólico destaca la lógica de predicados de primer orden, pues su gran potencia descriptiva y su flexibilidad la hacen adecuada para describir, de una forma sencilla, estructuras y relaciones complejas existentes en gran número de problemas. Por ello, sistemas como FOIL y FZFOIL, que siguen el enfoque simbólico, inducen reglas que son adecuadas para describir soluciones complejas de problemas muy diversos. Sin embargo, hay que destacar dos limitaciones importantes en la utilización de la lógica de predicados en estos sistemas:

Por otro lado, existen limitaciones intrínsecas al propio algoritmo de inducción:

 

La extensión de la lógica de predicados hacia una lógica borrosa de predicados es un paso adelante en la flexibilidad y potencia descriptiva, tanto en la entrada de datos (mediante relaciones borrosas) como en la representación del conocimiento inducido (reglas borrosas). Esto aumenta el campo de aplicación de FZFOIL respecto de FOIL, especialmente al manejar conceptos borrosos, como los utilizados habitualmente por los humanos, ya que se facilita el modelado del problema y resulta más fácil de entender la solución del mismo (la definición del mismo). Sin embargo, existen otros tipos de incertidumbre, distintos de la borrosidad, que no se pueden representar en FZFOIL:

 

5.2 Ámbito de aplicación

Entre las aplicaciones más inmediatas de FZFOIL se encuentra la construcción de definiciones lógicas para relaciones de una BD, al igual que ocurre en FOIL. En FZFOIL se amplía el campo de aplicación al permitir manejar relaciones borrosas, es decir, puede ser aplicado tanto sobre las tradicionales BD relacionales como sobre BD relacionales borrosas.

La utilidad de esta aplicación cada vez es más evidente, dado el interés que están adquiriendo los sistemas de control borrosos, sistemas expertos borrosos, etc.

Por otro lado, también resulta interesante simplemente para analizar datos y extraer conocimiento de los mismos. La utilización de la lógica borrosa de predicados en FZFOIL facilita la comprensión del conocimiento inducido, al manejar relaciones borrosas, más parecidas a los conceptos utilizados en lenguaje natural.

Aunque la introducción de la lógica borrosa en FZFOIL aumenta la complejidad de la búsqueda, resulta aplicable no sólo sobre pequeños conjuntos de entrenamiento, sino también sobre un conjunto voluminoso de datos reales, como se muestra a continuación.

5.3 Ejemplo de aplicación sobre datos reales: Proyecto SEIC

En este apartado se presentan algunos resultados obtenidos por FZFOIL en el Proyecto SEIC (Servicio de Información Ciudadana, PC-183), dentro de la línea de "Acciones Especiales PASO", gestionada por el C.D.T.I. y cofinanciada por la Unión Europea y el Ministerio de Industria de España. Este proyecto ha estado coordinado por EnWare, S.A., y en él han participado también, además del DIT, el Consorcio Regional de Transportes de Madrid, el Colegio Oficial de Farmacéuticos de Madrid y Genasys II Spain.

El proyecto SEIC ha servido como motor y campo de pruebas para nuestro sistema FZFOIL, al aportar no sólo un objetivo concreto (aunque no el principal) para el desarrollo del trabajo realizado, sino también una valiosa fuente de datos reales, con los que evaluar los resultados de manera más objetiva.

El objetivo del proyecto SEIC consiste en la construcción de un sistema de información de carácter general, orientado a los ciudadanos, que podrán acceder al mismo a través de unos puestos de información ciudadana (PICs) situados en la vía pública, normalmente en estaciones de Metro o en lugares de interés turístico. La información que se ofrecerá inicialmente será sobre transportes públicos y sobre farmacias, aunque, virtualmente, podrá extenderse a otros tipos de información.

Dentro del proyecto existen diferentes módulos, para cubrir los diferentes requisitos del mismo: base de datos sobre transportes, datos sobre farmacias, comunicaciones entre el módulo central y los PICs, sistema de alarmas, interfaz gráfica, etc. La participación del Departamento de Ingeniería de Sistemas Telemáticos (DIT) se centró en uno de los módulos, denominado Módulo de Usos y Demandas, situado funcionalmente como un elemento anexo al conjunto, que no afecta directamente al funcionamiento general, pero que puede aportar información muy valiosa sobre el sistema.

El objetivo de este Módulo de Usos y Demandas es bastante genérico y, a la vez, ambicioso. Se pretende que analice de un modo inteligente las consultas realizadas por los usuarios desde los PICs. De este análisis se pueden extraer conclusiones (conocimiento) sobre posibles patrones de comportamiento por parte de los usuarios, relaciones entre diferentes entidades (averías, fallos en las comunicaciones, consultas, momento del día, etc.) o cualquier otra información de interés, tanto para los suministradores de las bases de datos (Consorcio de Transportes de Madrid y Colegio de Farmacéuticos de Madrid) como para la empresa que se encargue del mantenimiento y explotación del sistema.

Desde un principio se confió en la posibilidad de aplicar el trabajo que se estaba desarrollando para esta Tesis, dentro del Módulo de Usos y Demandas del SEIC.

Por su propia naturaleza, para realizar pruebas exhaustivas en el Módulo de Usos y Demandas se requiere un volumen de datos grande que, por otro lado, no podrá recopilarse hasta que se construya el resto del sistema y se ponga en funcionamiento. Es decir, la calidad y relevancia de las reglas inducidas sólo se podrá valorar tras meses de pruebas de campo del sistema SEIC.

Por fortuna, el Consorcio Regional de Transportes de Madrid nos proporcionó desde el principio varios ficheros de datos, recopilados durante los meses de Julio a Noviembre de 1994 en diferentes puntos de Madrid, dentro del proyecto SIT (Sistema de Información de Transportes), precursor del actual SEIC. Estos datos representan diferentes características de las consultas que se realizaron en varios PICs, y con ellos se han podido realizar diferentes pruebas del sistema descrito en esta Tesis.

A continuación se describe el formato de los datos disponibles y los pasos de selección, preprocesado y transformación previos a la inducción de conocimiento (minería de datos), dentro del proceso global de KDD. También se presentan algunos de los resultados obtenidos alimentando el Módulo de Usos y Demandas con estos datos, así como algunas conclusiones derivadas de la interpretación y evaluación de los resultados.

5.3.1 Datos de entrada disponibles

El volumen de datos disponible (del proyecto SIT) corresponde a más de 40000 consultas, cada una de ellas caracterizada por 14 atributos, como se verá a continuación.

Estos ficheros de datos de entrada (de nombre XXXM.dat) vienen ordenados por el PIC en el que se han generado (XXX) y el mes (M) correspondiente. Existen datos de 8 diferentes localizaciones de PICs:

Tabla 5-1: Ubicación de los Puntos de Información Ciudadana

Nombre del PIC (XXX)

Localización del PIC

 

ALO

metro Alonso Martínez

ATC

metro Atocha Renfe

CAL

metro Callao

AVA

metro Avenida América

COR

El Corte Inglés de Princesa

CUA

metro Cuatro Caminos

PCA

metro Plaza Castilla

SOL

metro Sol

y de los meses de Julio a Noviembre de 1994:

Tabla 5-2: Meses en que se realizaron las consultas en el SIT

valor M

Mes

J

Julio

A

Agosto

S

Septiembre

O

Octubre

N

Noviembre

Dentro de cada fichero, los datos tienen un formato plano, correspondiendo cada línea a una única consulta. Dentro de cada línea, cada uno de los atributos se almacena en una columna fija, del siguiente modo:

Tabla 5-3: Formato de los ficheros históricos del SIT

Columna

Dato

1-2

día del mes (1-31)

3-4

mes (1-12)

5-8

año

9-10

día de semana (1-7) [1=domingo, ..., 7=sabado]

11-12

hora inicio de consulta (0-24)

13-14

minutos inicio consulta (0-59)

15-17

código de pantalla, especificar origen:

P01 = desde aquí (in situ)

P02 = calle o edificio singular

P03 = cruce de calles

P04 = estación de metro

18-21

duración de la consulta (segundos)

22-29

reservado

30-32

código de pantalla, especificar destino:

P05 = hasta aquí

P06 = calle o edificio singular

P07 = cruce de calles

P08 = estación de metro

33-44

reservado

45-47

código de pantalla, cambiar fecha/hora:

P09 = no cambiar

P10 = cambiar

48-59

reservado

60-62

código de pantalla, limitar modo:

P11 = todos los modos

P12 = sólo autobús

P13 = sólo metro

63-74

reservado

75-77

código de pantalla, criterio de camino:

P14 = camino óptimo (coste generalizado, tiempo ponderado y tarifa convertida en tiempo)

P15 = minimizar transbordos

P16 = minimizar tiempo

78-89

reservado

Para trabajar con estos datos iniciales del SIT es necesario preprocesarlos y transformarlos, para convertirlos a formato relacional, en diferentes tablas que puedan ser manejadas por el algoritmo de aprendizaje.

5.3.2 Selección y preprocesado

A partir de los ficheros de datos de partida, se pueden identificar los siguientes dominios, para los diferentes atributos:

Se han suprimido algunos atributos existentes en los ficheros originales, dada su irrelevancia para nuestro módulo inductivo. Así, por ejemplo, se ha eliminado el año de cada consulta, ya que todas se realizaron en 1994.

En algunas de las pruebas realizadas se han introducido dominios borrosos nuevos, generados a partir de algunos de los dominios originales. En concreto, se ha introducido borrosidad en los valores de Hora_día y los de Duración, del siguiente modo ( See Subconjuntos borrosos para Hora_día y See Subconjuntos borrosos para Duración ):

 

Figura 5-1: Subconjuntos borrosos para Hora_día

 

Figura 5-2: Subconjuntos borrosos para Duración

 

Dado el volumen de datos disponible, es conveniente aplicar técnicas de muestreo sobre los mismos. Para obtener los resultados mostrados en el apartado 5.3.4 se utilizó una muestra aleatoria con el 5% del total de consultas existentes. Esta muestra se mantuvo constante en todas las pruebas realizadas.

5.3.3 Transformación de los datos

Las relaciones construidas a partir de los datos iniciales son las siguientes (con los atributos indicados):

 

En las pruebas realizadas con datos borrosos se han introducido tres relaciones nuevas, una para cada uno de los valores borrosos definidos en el dominio Hora_día_borrosa:

 

Mediante el uso de relaciones intensionales ( apartado 4.3.5 ) se ofrece la posibilidad de que el operador introduzca conocimiento de base en el sistema. Estas relaciones intensionales permiten seleccionar el subconjunto de datos para el que se desea inducir una descripción lógica (en sí mismas, también pueden considerarse como descripciones lógicas). Por ejemplo, para seleccionar las "consultas que tuvieron lugar en la estación de metro Sol durante el mes de Noviembre" se puede introducir la relación intensional:

Estas relaciones intensionales se introducen en un fichero ascii, pudiendo coexistir varias. Al generarse la BD relacional (conjunto de entrenamiento para nuestro algoritmo), se añaden al final de la misma, detrás de las relaciones extensionales definidas anteriormente.

5.3.4 Resultados

A continuación se muestran diferentes resultados obtenidos a partir de los datos del SIT, con la versión actual de FZFOIL. Para la obtención de los mismos se ha utilizado una estación de trabajo SUN Ultra-1, con sistema operativo Solaris 2.5. El tiempo de ejecución máximo para cada ejemplo se ha fijado en 60 minutos (si en ese tiempo no se llega a una definición consistente y completa, se para la ejecución en el punto en que se encuentre y se muestran los resultados, sin aplicar ningún mecanismo de poda de definiciones).

En todos los ejemplos se ha utilizado la función Interés* para evaluación de literales.

 

Se han seleccionado 6 relaciones objetivo diferentes, introducidas mediante relaciones intensionales 1 . Para cada una de ellas se han construido dos ejemplos, uno con relaciones ordinarias (caso a, en los siguientes apartados) y otro con relaciones ordinarias y borrosas (caso b), lo que hace un total de 12 ejemplos.

La selección, preprocesado y transformación de los datos de partida ha sido igual para todos los ejemplos, tal como se explica en los apartados anteriores. Las únicas diferencias entre ellos son, por tanto, la relación objetivo seleccionada y la existencia o no de relaciones borrosas (dependiendo de si se trata de un ejemplo de tipo b o del tipo a respectivamente).

 

Para cada ejemplo se muestra:

 

  1. Consultas en las que se desea minimizar el tiempo
  2. La relación objetivo utilizada para estos ejemplos corresponde a la siguiente relación intensional:

    I_min_tiempo(Id_consulta)

    min_tiempo(X):-

    rest_optim(X,Y),

    =_const(Y,Min_tiempo).

     

    Definición construida sólo con relaciones ordinarias.

    El tiempo de ejecución finaliza durante la construcción de la tercera cláusula (C3), que no llega a ser consistente. Resulta, por tanto, una definición incompleta e inconsistente, que puede describirse como 2 :

    "El 20.17% de las consultas en las que se quiere minimizar el tiempo del viaje cumplen:

    • el identificador de la consulta coincide con la hora en que se realiza la consulta;
    • o bien se realiza en Agosto, el identificador coincide con la hora de una segunda consulta realizada un Viernes de Octubre y existe una tercera que se realiza también en Octubre y el mismo día de la semana y hora que la primera;
    • o bien, con un 61% de probabilidad, se realizan desde el metro de Sol para ir desde un origen que no es una estación de metro a un destino que tampoco es una estación de metro".

    Las cláusulas de Horn construidas son:

    [C1] {9.910 bits} [694.00/1694.00]Æ [1.00/1.00]

    min_tiempo ( A ) :-

    cuando ( A B C A ).

    [C2] {61.163 bits} [693.00/1693.00]Æ [4.00/4.00]

    min_tiempo ( A ) :-

    cuando ( B C D A ),

    =_const ( C Octubre ),

    =_const ( D Viernes ),

    cuando ( E C F G ),

    cuando ( A H F G ),

    =_const ( H Agosto ).

    [C3] {52.547 bits} [689.00/1689.00]Æ [135.00/220.00]

    min_tiempo ( A ) :-

    realizada_en ( A B ),

    =_const ( B Sol ),

    origen ( A C ),

    ¬ =_const ( C Metro ),

    origen ( D C ),

    destino ( A E ),

    ¬ =_const ( E Metro ),

    destino ( D F )...

    Los valores de los parámetros a comparar son los siguientes:

    LDI = 121.035 bits

    k-completitud = 140 / 694 = 20.17% k-completitud / LDI = 0.0017

    k-consistencia = 140 / 225 = 62.22% k-consistencia / LDI = 0.0051

     

    Definición construida con relaciones borrosas:

    La definición parcialmente construida consta, en este caso de una única cláusula, inconsistente e incompleta, que puede interpretarse como:

    "El 49.90% de las consultas en las que se quiere minimizar el tiempo del viaje cumplen que, con un 44.81% de probabilidad, se realizaron por la tarde un día que no era Viernes".

    [C1] {17.062 bits} [694.00/1694.00]Æ [346.28/772.71]

    min_tiempo ( A ) :-

    cuando_tarde ( A B C ),

    ¬ =_const ( C Viernes )...

    LDI = 17.062 bits

    k-completitud = 346.28 / 694 = 49.90% k-completitud / LDI = 0.0293

    k-consistencia = 346.28 / 772.71 = 44.81% k-consistencia / LDI = 0.0263

     

  3. Consultas en las que se desea minimizar el número de transbordos
  4. Relación intensional objetivo:

    I_min_transbordos(Id_consulta)

    min_transbordos(X):-

    rest_optim(X,Y),

    =_const(Y,Min_transbordos).

     

    Definición construida con relaciones ordinarias:

    La definición parcialmente construida consta, en este caso, de cuatro cláusulas, que pueden interpretarse del siguiente modo:

    "El 58.45% de las consultas en las que se quiere minimizar el número de transbordos cumplen:

    • no se realizan ni en el metro de Alonso Martínez, ni en el Corte Inglés de Princesa, ni en el metro de Avenida de América, y el origen de la consulta es una estación de Metro;
    • o bien, no se realizan ni en el metro de Sol ni en el de Cuatro Caminos y el origen de la consulta es una estación de metro;
    • o bien, no se realizan ni en el metro de Alonso Martínez, ni en el Corte Inglés de Princesa, ni en el metro de Avenida de América, ni en el de Sol, el origen es una calle o edificio singular y es distinto de su destino;
    • o bien, con un 51% de probabilidad, no se realizan ni en el metro de Alonso Martínez, ni en el Corte Inglés de Princesa, ni en el metro de Avenida de América, el origen no es un cruce de calles y el destino es distinto del origen":

    [C1] {36.203 bits} [1119.00/2049.00]Æ [217.00/217.00]

    min_transbordos ( A ) :-

    realizada_en ( A B ),

    ¬ =_const ( B Al_Martínez ),

    ¬ =_const ( B CI_Princesa ),

    ¬ =_const ( B Av_América ),

    origen ( A C ),

    =_const ( C Metro ).

    [C2] {31.087 bits} [902.00/1832.00]Æ [88.00/88.00]

    min_transbordos ( A ) :-

    realizada_en ( A B ),

    ¬ =_const ( B Sol ),

    ¬ =_const ( B C_Caminos ),

    origen ( A C ),

    =_const ( C Metro ).

    [C3] {46.703 bits} [814.00/1744.00]Æ [50.00/52.00]

    min_transbordos ( A ) :-

    realizada_en ( A B ),

    ¬ =_const ( B Al_Martínez ),

    ¬ =_const ( B CI_Princesa ),

    ¬ =_const ( B Av_América ),

    ¬ =_const ( B Sol ),

    origen ( A C ),

    ¬ destino ( A C ),

    =_const ( C Calle_Edif_singular ).

    [C4] {42.003 bits} [764.00/1692.00]Æ [299.00/542.00]

    min_transbordos ( A ) :-

    realizada_en ( A B ),

    ¬ =_const ( B Al_Martínez ),

    ¬ =_const ( B CI_Princesa ),

    ¬ =_const ( B Av_América ),

    origen ( A C ),

    ¬ destino ( A C ),

    ¬ =_const ( C Cruce )...

    LDI = 151.411 bits

    k-completitud = 654 / 1119 = 58.45% k-completitud / LDI =0.0039

    k-consistencia = 654 / 899 = 72.75% k-consistencia / LDI = 0.0048

     

    Definición construida con relaciones borrosas:

    De nuevo resulta una definición más sencilla para el caso de relaciones borrosas:

    "El 24.43% de las consultas en las que se quiere minimizar el número de transbordos se realizan (con una probabilidad del 62.54%) por la mañana, un día que no es Martes ni en Octubre ni en Julio".

    [C1] {31.291 bits} [1119.00/2049.00]Æ [273.35/437.05]

    min_transbordos ( A ) :-

    cuando_mañana ( A B C ),

    ¬ =_const ( B Octubre ),

    ¬ =_const ( C Martes ),

    ¬ =_const ( B Julio )...

    LDI = 31.291 bits

    k-completitud = 273.35 / 1119 = 24.43% k-completitud / LDI = 0.0078

    k-consistencia = 273.35 / 437.05 = 62.54% k-consistencia / LDI = 0.0200

     

  5. Consultas en las que se desea usar sólo el autobús
  6. Relación intensional objetivo:

    I_sólo_bus(Id_consulta)

    sólo_bus(X):-

    rest_tte(X,Y),

    =_const(Y,Sólo_bus).

     

    Definición construida con relaciones ordinarias:

    [C1] {38.016 bits} [232.00/1232.00]Æ [6.00/12.00]

    sólo_bus ( A ) :-

    realizada_en ( A B ),

    =_const ( B CI_Princesa ),

    origen ( A C ),

    ¬ =_const ( C Calle_Edif_singular ),

    ¬ =_const ( C Aquí ),

    ¬ destino ( A C )...

    LDI = 38.016 bits

    k-completitud = 6 / 232 = 2.59% k-completitud / LDI = 0.0007

    k-consistencia = 6 / 12 = 50.00% k-consistencia / LDI = 0.0131

     

    Definición construida con relaciones borrosas:

    [C1] {31.291 bits} [232.00/1232.00]Æ [92.83/405.23]

    sólo_bus ( A ) :-

    cuando_tarde ( A B C ),

    ¬ =_const ( B Noviembre ),

    ¬ =_const ( C Domingo ),

    ¬ =_const ( C Miércoles )...

    LDI = 31.291 bits

    k-completitud = 92.83 / 232 = 40.01% k-completitud / LDI = 0.0128

    k-consistencia = 92.83 / 405.23 = 22.91% k-consistencia / LDI = 0.0073

     

  7. Consultas realizadas en Alonso Martínez, en las que se desea minimizar el tiempo del viaje
  8. Relación intensional objetivo:

    I_alonso_mintiempo(Id_consulta)

    alonso_mintiempo(X):-

    realizada_en(X, Y),

    =_const(Y, Al_Martínez),

    rest_optim(X, Z),

    =_const(Z, Min_tiempo).

     

    Definición construida con relaciones ordinarias:

    [C1] {18.195 bits} [70.00/1070.00]Æ [8.00/13.00]

    alonso_mintiempo ( A ) :-

    cuando ( B C D A ),

    =_const ( D Lunes )...

    LDI = 18.195 bits

    k-completitud = 8 / 70 = 11.43% k-completitud / LDI = 0.0063

    k-consistencia = 8 / 13 = 61.54% k-consistencia / LDI = 0.0338

     

    Definición construida con relaciones borrosas:

    [C1] {65.925 bits} [70.00/1070.00]Æ [38.34/331.05]

    alonso_mintiempo ( A ) :-

    cuando ( A B C D ),

    ¬ =_const ( B Julio ),

    ¬ cuando_noche ( A B C ),

    ¬ =_const ( C Martes ),

    ¬ =_const ( C Lunes ),

    ¬ =_const ( B Agosto ),

    ¬ =_const ( C Domingo ),

    ¬ =_const ( C Jueves )...

    LDI = 65.925 bits

    k-completitud = 38.34 / 70 = 54.77% k-completitud / LDI = 0.0083

    k-consistencia = 38.34 / 331.05 = 11.58% k-consistencia / LDI = 0.0018

     

  9. Consultas en las que se desea minimizar el número de transbordos, usando sólo el autobús.
  10. Relaciones intensionales 3 :

    I_bus_mintransbordos(Id_consulta)

    bus_mintransbordos(X):-

    rest_tte(X, Y),

    =_const(Y, Sólo_bus),

    rest_optim(X, Z),

    =_const(Z, Min_transbordos).

    *I_sólo_bus(Id_consulta)

    sólo_bus(X):-

    rest_tte(X,Y),

    =_const(Y,Solo_bus).

    *I_min_transbordos(Id_consulta)

    min_transbordos(X):-

    rest_optim(X,Y),

    =_const(Y,Min_transbordos).

     

    Definición construida con relaciones ordinarias.

    En este caso se obtiene una definición consistente y completa, formada por una única cláusula, que utiliza una de las relaciones intensionales como antecedente: "todas las consultas realizadas en las que se desea utilizar sólo el autobús, quieren también minimizar el número de transbordos".

    [C1] {4.907 bits} [232.00/1232.00]Æ [232.00/232.00]

    bus_mintransbordos ( A ) :-

    sólo_bus ( A ).

    LDI = 4.907 bits

    k-completitud = 232 / 232 = 100% k-completitud / LDI = 0.2038

    k-consistencia = 232 / 232 = 100% k-consistencia / LDI = 0.2038

     

    Definición construida con relaciones borrosas.

    La definición inducida en el caso de tener relaciones borrosas es la misma que en el caso de sólo relaciones ordinarias, ya que se obtiene una definición consistente y completa sin necesidad de utilizar literales borrosos:

    [C1] {5.392 bits} [232.00/1232.00]Æ [232.00/232.00]

    bus_mintransbordos ( A ) :-

    sólo_bus ( A ).

    La LDI calculada para la definición en este caso borroso es mayor que la calculada en el caso a, aunque ambas definiciones son iguales. Esto se debe a que la longitud de codificación de los literales depende del número de relaciones en la BD ( apartado 4.3.2.9 ), y en los ejemplos de tipo b se están considerando 6 relaciones borrosas más que en los ejemplos de tipo a (sin relaciones borrosas).

    LDI = 5.392 bits

    k-completitud = 232 / 232 = 100% k-completitud / LDI = 0.1854

    k-consistencia = 232 / 232 = 100% k-consistencia / LDI = 0.1854

     

  11. Consultas referentes al viernes por la tarde:
  12. Relación intensional objetivo usada con relaciones ordinarias:

    I_viernes_tarde(Id_consulta)

    viernes_tarde(X):-

    cuando(X, Y, Z, W),

    =_const(Z, Viernes),

    >_const(W, 13),

    ¬ >_const(W, 21).

    Relación intensional objetivo usada con relaciones borrosas:

    I_viernes_tarde(Id_consulta)

    viernes_tarde(a):-

    cuando_tarde(a, b, c),

    =_const(c, Viernes).

     

    Definición construida con relaciones ordinarias:

    [C1] {53.234 bits} [172.00/1166.00]Æ [2.00/2.00]

    viernes_tarde ( A ) :-

    cuando ( B C D A ),

    cuando ( A C E F ),

    cuando ( F G E H ),

    cuando ( H C I J ).

    [C2] {61.952 bits} [170.00/1164.00]Æ [50.00/196.00]

    viernes_tarde ( A ) :-

    realizada_en ( A B ),

    ¬ =_const ( B At_renfe ),

    ¬ =_const ( B P_Castilla ),

    origen ( A C ),

    ¬ =_const ( C Cruce ),

    origen ( D C ),

    ¬ realizada_en ( D B ),

    destino ( A C ),

    ¬ =_const ( B Av_América ),

    ¬ =_const ( B Callao )...

    LDI = 114.186 bits

    k-completitud = 52 / 172 = 30.23% k-completitud / LDI =0.0026

    k-consistencia = 52 / 198 = 26.26% k-consistencia / LDI = 0.0023

     

    Definición construida con relaciones borrosas:

    [C1] {9.155 bits} [166.66/1203.00]Æ [166.66/678.59]

    viernes_tarde ( A ) :-

    cuando_tarde ( A B C )...

    LDI = 9.155 bits

    k-completitud = 166.66 / 166.66 = 100% k-completitud / LDI =0.1095

    k-consistencia = 166.66 / 678.59 = 24.56% k-consistencia / LDI = 0.0269

     

5.3.5 Comparación de resultados

La comparación la realizaremos a partir de los cinco parámetros calculados para cada ejemplo:

Puede observarse que, para este conjunto de ejemplos, la longitud de descripción intensional tiende a ser mayor en el caso de sólo relaciones ordinarias (hasta 12.5 veces mayor en el ejemplo 6), aunque en algunos casos ocurre lo contrario 4 (ejemplo 4). En media, con las definiciones borrosas se ha conseguido un ahorro de más del 60% del total de bits.

Esto se traduce en descripciones borrosas más cortas y, por tanto, más fáciles de entender.

Tabla 5-5: Comparación del valor de k-completitud

 

caso A (relaciones ordinarias)

 

caso B

(relaciones ordinarias y borrosas)

Relación:

 

k-compl(A) / k-compl(B)

Ejemplo 1

0.2017

0.4990

0.40

Ejemplo 2

0.5845

0.2443

2.39

Ejemplo 3

0.0259

0.4001

0.06

Ejemplo 4

0.1143

0.5477

0.21

Ejemplo 5

1.0000

1.0000

1.00

Ejemplo 6

0.3023

1.0000

0.30

El máximo valor de k-completitud (para el que se satisface la condición de k-completitud) es, normalmente mayor en el caso B (definiciones borrosas), aunque con algunas excepciones (ejemplo 2). Esto puede interpretarse como que las descripciones borrosas son más generales que las construidas sólo con relaciones ordinarias.

Tabla 5-6: Comparación del valor de k-consistencia

 

caso A (relaciones ordinarias)

 

caso B

(relaciones ordinarias y borrosas)

Relación:

 

k-consis(A) / k-consis(B)

Ejemplo 1

0.6220

0.4481

1.39

Ejemplo 2

0.7275

0.6254

1.16

Ejemplo 3

0.5000

0.2291

2.18

Ejemplo 4

0.6154

0.1158

5.31

Ejemplo 5

1.0000

1.0000

1.00

Ejemplo 6

0.2626

0.2456

1.07

El máximo valor de k-consistencia (para el que se satisface la condición de k-consistencia) es, en los ejemplos anteriores, siempre mayor para el caso A (sólo relaciones ordinarias). Esto se traduce en unas definiciones borrosas menos precisas que las construidas sólo con relaciones ordinarias.

Tabla 5-7: Comparación de valores de k-completitud y k-consistencia por unidad de LDI

 

k-completitud / LDI

k-consistencia / LDI

 

caso A (relaciones ordinarias)

 

caso B

(relaciones ordinarias y borrosas)

caso A (relaciones ordinarias)

 

caso B

(relaciones ordinarias y borrosas)

Ejemplo 1

0.0017

0.0293

0.0051

0.0263

Ejemplo 2

0.0039

0.0078

0.0048

0.0200

Ejemplo 3

0.0007

0.0128

0.0132

0.0073

Ejemplo 4

0.0063

0.0083

0.0338

0.0018

Ejemplo 5

0.2038

0.1854

0.2038

0.1854

Ejemplo 6

0.0026

0.1095

0.0023

0.0269

Al comparar los valores de k-completitud y k-consistencia por unidad de LDI, se observa que, en los ejemplos considerados:

Este resultado puede interpretarse como que, para longitudes de descripción fijas, las definiciones borrosas son más completas y, algunas veces, más consistentes que las definiciones ordinarias. O dicho de otro modo, las definiciones borrosas generalizan mejor los conceptos y, en ocasiones, son también más precisas que las definiciones sin relaciones borrosas.

5.4 Análisis de la complejidad

La complejidad asociada a la inducción de una definición lógica viene determinada por la búsqueda de los literales que constituyen sus cláusulas. A su vez, esta búsqueda depende de:

Ambos valores vienen determinados por factores como el grado de las relaciones existentes en la BD, el predicado elegido como objetivo o la longitud de la cláusula resultante.

Para realizar un estudio formal de la complejidad de FOIL, utilizaremos el enfoque seguido por [Pazzani y Kibler, 92] , en el que descomponen el coste de la búsqueda de un nuevo antecedente Li en una cláusula en construcción Ci-1 con u variables, en el producto de dos parámetros:

El coste resultante para la búsqueda del antecedente i-ésimo Li, en una cláusula, será el producto de ambos parámetros:

Coste(Li) = CT CE[EC. 5.1]

Para estudiar la complejidad del nuevo sistema FZFOIL seguiremos un proceso paralelo, en el que se calcularán los correspondientes valores CT y CE, y se compararán con los obtenidos para FOIL.

5.4.1 Complejidad de FOIL

5.4.1.1 Coste Teórico

Como ya se ha definido, el coste teórico (CT) mide el tamaño del espacio de búsqueda, expresado en número de literales.

Para cada literal que se añade a una cláusula existe un espacio de búsqueda diferente. Supongamos que queremos añadir un nuevo antecedente Li a una cláusula en la que existen u variables diferentes. ¿Cuántos candidatos deberemos evaluar hasta elegir Li?

  • Para cada predicado qm, asociado a una relación Qm de la BD, se generarán, en el espacio de búsqueda, cierto número de literales afirmativos diferentes (dependiendo del grado m de Qm y del número u de variables existentes en la cláusula) que denominaremos:
  • NumLit(m,u) = número de literales  afirmativos que existen por cada predicado qm de grado m de la BD, candidatos a ser antecedentes de una cláusula en construcción con u variables usadas.

  • Si en la BD existen
  • NumPr(m) = número de predicados de grado m (un predicado para cada relación de grado m de la BD)

    y denominamos

    MaxG = máximo grado de las relaciones de la BD

    podemos obtener ya una expresión para el tamaño del espacio de búsqueda o coste teórico:

    CT = 2 [EC. 5.2]

    El factor 2 de esta expresión se debe a que por cada literal afirmativo se considera otro literal negativo.

En la tabla 5-8 se muestran algunos valores de NumLit(m,u) que, como se ve, crecen rápidamente tanto con el grado m del predicado candidato como con el número u de variables usadas en la cláusula.

Tabla 5-8: Algunos valores de NumLit(m,u)

 

 

u

 

 

1

2

3

4

5

6

7

 

1

1

2

3

4

5

6

7

 

2

3

8

15

24

35

48

63

m

3

10

32

72

136

230

360

532

 

4

37

136

357

784

1525

2712

4501

 

5

151

622

1863

4684

10375

20826

38647

 

6

674

3060

10278

29168

72810

163764

338030

La expresión exacta de NumLit(m,u) no es sencilla (véase apartado B.2 ), pero se puede acotar fácilmente por su valor máximo, para cualquier predicado de la BD, durante la búsqueda de cualquier antecedente de la cláusula. Si denominamos

    TotalPr al número de relaciones de la BD

    MaxG al máximo grado de las relaciones existentes

    MaxU al número máximo de variables diferentes que pueden ser usadas en cualquier cláusula en construcción

tendremos, en el caso peor, que todos los predicados de la BD son de grado MaxG y que la cláusula en construcción tienen MaxU variables diferentes. En este caso el número de literales afirmativos para cada relación sería

    NumLit(MaxG, MaxU)

y por ello

    CTmax = 2 TotalPr NumLit(MaxG, MaxU)[EC. 5.3]

Como todos los candidatos deben tener, al menos, una variable usada, un literal de grado máximo podrá usar, como mucho, MaxG-1 variables nuevas, por lo que los diferentes literales generados para un predicado de grado MaxG serán variaciones de MaxG variables elegidas entre MaxU+MaxG-1 posibles (aunque no todas las variaciones de variables nuevas son diferentes):

NumLit(MaxG, MaxU) £ (MaxU + MaxG - 1)MaxG[EC. 5.4]

De este modo, se puede obtener una cota superior para el valor de CT asociado a la búsqueda de un literal Li:

CT £ 2 TotalPr (MaxU + MaxG -1)MaxG[EC. 5.5]

Se pueden deducir varias conclusiones de esta expresión:

  • El CT máximo crece aproximadamente de forma lineal con el número de predicados de la BD.
  • El CT máximo crece polinómicamente con el número de variables usadas en la cláusula.
  • El CT máximo crece exponencialmente con el grado de los predicados de la BD.

El mayor valor de CT se alcanza durante la construcción de las cláusulas más largas de una definición (midiendo la longitud por el número de variables que utiliza), especialmente cuando los literales candidatos usan predicados de grado alto. Por ejemplo, en una BD con los predicados lista, vacía y componentes, cuyos grados son 1, 1 y 3 respectivamente, los valores de CT durante la construcción de la regla:

    lista(X1) :- vacía(X1)

    lista(X1) :- componentes(X1, V2, V3), lista(V3)

son (según [EC. 5.2] y tabla 5-8 ):

  • para el primer literal de cualquiera de las dos cláusulas:
  • CT = 2 (2 1 + 1 10) = 24 literales evaluados

  • para el segundo literal (lista(V3)) de la segunda cláusula:
  • CT = 2 (2 3 + 1 72) = 156 literales evaluados

Por tanto, el CT asociado a la construcción de una definición D (número de literales evaluados durante la construcción de sus cláusulas) se puede aproximar por el CT asociado a la búsqueda del último literal de la cláusula más larga, suponiendo que los únicos predicados de la BD son los de mayor grado:

    CTD ª 2 NumPr(MaxG) NumLit(MaxG, MaxV) [EC. 5.6]

    CTD £ 2 NumPr(MaxG) (MaxV + MaxG - 1)MaxG[EC. 5.7]

siendo

    NumPr(MaxG) el número de predicados de la BD con grado MaxG (máximo)

    MaxV el mayor número de variables distintas que existen en alguna de las cláusulas de la definición, excluyendo las introducidas por el último antecedente

En el ejemplo anterior, la aproximación [EC. 5.6] daría CTD ª 2 72 = 144 literales, mientras que el valor real es CTD = 24 + 24 + 156 = 204.

5.4.1.2 Coste de Evaluación

Una vez obtenido el tamaño del espacio de búsqueda de literales, se puede calcular el Coste de Evaluación (CE), asociado a la evaluación de cada literal candidato. El CE dependerá del tamaño Ni del conjunto intermedio de tuplas Ti que se considera para la selección del literal Li de una cláusula.

El tamaño de cada conjunto intermedio de tuplas, para la búsqueda de los sucesivos literales antecedentes de una cláusula, depende de los literales seleccionados anteriormente (del predicado con el que se construyen y del número de variables nuevas que introducen). Para estimar el tamaño Ni de estos conjuntos Ti, [Pazzani y Kibler, 92] definen algunos conceptos:

  • Densidad de un predicado q: porcentaje de casos en los que el predicado se satisface
    • densidad(q) = £ 1[EC. 5.8]

    siendo

      P el número de tuplas que pertenecen a la relación Q

      N el número de tuplas que no pertenecen a Q

    Por ejemplo, para el predicado menor_que, definido sobre los pares de valores <a, b>, donde a y b pertenecen al dominio de los enteros del 1 al 10, valdrá densidad(menor_que) = 45/100 = 0.45

    Para un literal Li = q(V1, ..., Vm) que no introduzca variables nuevas, el tamaño del conjunto Ti+1 se podrá estimar como:

      Ni+1 ª Ni densidad(q)[EC. 5.9]

  • Potencia de un predicado: máximo número de tuplas que lo satisfacen cuando uno de sus atributos es constante y los demás variables.
  • Por ejemplo, para el predicado menor_que definido anteriormente, este valor será potencia(menor_que) = 9, y se alcanza para los literales: menor_que(1, V2) y menor_que(V1, 10).

    La potencia de un predicado q permite acotar el tamaño del nuevo Ti+1 generado por un literal Li=q(V1, ..., Vm) que introduce nuevas variables:

      Ni+1 £ Ni potencia(q)[EC. 5.10]

  • Potencia media de un predicado: número medio de tuplas que lo satisfacen cuando uno de sus atributos es constante y los demás son variables.
  • Por ejemplo, para el predicado menor_que definido anteriormente, la potencia media será potencia_med(menor_que) = 45/10 = 4.5 (aunque menor_que(1, V2) se satisface en 9 casos y menor_que(10, V2) nunca).

    Se puede estimar el tamaño Ni+1 del conjunto Ti+1, generado por un literal Li=q(V1,..., Vm) que introduzca nuevas variables:

      Ni+1 ª Ni potencia_med(q)[EC. 5.11]

  • Crecimiento máximo de un literal Li=q(V1,..., Vm): indica el máximo valor posible de la fracción Ni+1/Ni. Vendrá dado por el máximo valor posible de densidad (es decir, la unidad) cuando Li no introduzca variables nuevas, y por la potencia en caso contrario:
    • crec_máx(Li) = [EC. 5.12]

  • Crecimiento medio de un literal Li=q(V1,..., Vm): indica el valor medio de Ni+1/Ni. Dependerá de si Li utiliza sólo variables usadas o si introduce alguna variable nueva:
    • crec_med(Li) = [EC. 5.13]

Haciendo uso de las anteriores definiciones, podremos estimar el tamaño del conjunto de entrenamiento Ti (usado para la búsqueda de Li en una cláusula Ci-1) como:

    CE = Ni ª N1 [EC. 5.14]

y, en el caso peor, nunca superará:

    Ni £ N1 [EC. 5.15]

5.4.1.3 Conclusiones

El tamaño del espacio de búsqueda de literales determina el coste teórico, asociado a la búsqueda de un literal. Este espacio de búsqueda crece del siguiente modo:

  • Linealmente respecto del número de predicados de la BD.
  • Polinómicamente con el número de variables usadas en la cláusula.
  • Exponencialmente con el grado de los predicados de la BD.

El tamaño del conjunto de entrenamiento también puede crecer durante la construcción de una cláusula, pero su tamaño máximo vendrá dado por la potencia de los literales que introducen nuevas variables.

El coste asociado a la evaluación de todos los literales candidatos dependerá del tamaño del espacio de búsqueda y del tamaño del conjunto de entrenamiento.

En algunos casos, especialmente durante la construcción de cláusulas con muchas variables distintas, puede ser necesario explorar espacios de búsqueda muy grandes, resultando muy costosa una búsqueda exhaustiva. Aunque en FOIL se aplican algunos heurísticos de poda ( apartado 2.5.4.3 ), muchas veces no son suficientes para reducir la búsqueda de forma notable, por lo que resulta de interés el estudio de otros heurísticos de búsqueda más eficientes ( apartado 6.2.1.2 ).

5.4.2 Complejidad de FZFOIL

Para comparar la complejidad del algoritmo FZFOIL respecto de FOIL, nos fijaremos en los dos parámetros con que se midió la complejidad en FOIL:

5.4.2.1 Coste Teórico

Para calcular el coste teórico de FZFOIL, hay que distinguir entre literales ordinarios y borrosos:

  • Para cada predicado ordinario se generan los mismos literales que en FOIL, resultantes de las diferentes combinaciones de variables nuevas y usadas en sus atributos y de la utilización o no de la negación lógica. Por tanto, el coste teórico asociado a la búsqueda de literales ordinarios es el calculado por la expresión [EC. 5.2] .
  • Para los predicados borrosos es posible construir literales a través de la combinación de variables nuevas y usadas en sus atributos, así como aplicando diferentes etiquetas lingüísticas a cada uno de los literales resultantes. Por tanto, el coste teórico asociado a los literales borrosos es mayor que en el caso de los literales ordinarios (para cada literal sin etiqueta existen tantos literales borrosos como etiquetas lingüísticas se permitan).

Por tanto, la expresión para el coste teórico en FZFOIL es la siguiente:

    CT = 2 +[EC. 5.16]

    + NumEtiquetas

siendo

    NumPrOrdinarios(m) = número de predicados ordinarios de grado m (un predicado para cada relación ordinaria de grado m de la BD)

    NumPrBorrosos(m) = número de predicados borrosos de grado m (un predicado para cada relación borrosa de grado m de la BD)

    NumLit(m,u) = número de literales  sin calificador de verdad (sin negar y sin etiqueta lingüística) que pueden construirse por cada predicado de grado m de la BD, con un máximo de u variables usadas (véase apartado B.2 )

    MaxG = máximo grado de las relaciones de la BD

    NumEtiquetas = número de etiquetas lingüísticas a considerar para cada literal borroso.

Si denominamos CTFOIL al valor de CT obtenido en la expresión [EC. 5.2] , y CTFZFOIL al valor de CT obtenido para FZFOIL ( [EC. 5.16] ), se puede encontrar la siguiente relación entre ambas:

    [EC. 5.17]

     

Como el número de etiquetas lingüísticas (NumEtiquetas) que se consideran para cada literal borroso suele ser mayor que dos (el valor 2 correspondería a un literal afirmativo y a su negado), entonces, resulta que el coste teórico es superior en FZFOIL que en FOIL.

5.4.2.2 Coste de Evaluación

La utilización de conjuntos proyectados de tuplas, tal como se hace con el heurístico Interés* en FZFOIL. permite, en algunos casos, no tener que evaluar cada literal Li con todas las tuplas del conjunto Ti. Esto es así porque los parámetros de evaluación se miden en el conjunto proyectado T1[i], en el que cada tupla puede tener varias extensiones en Ti. Si cualquiera de las extensiones de una tupla de T1[i] satisface un literal candidato Li, entonces no será necesario evaluar con el resto de extensiones de la misma tupla. Esta idea es aplicable sólo para literales ordinarios aplicados sobre conjuntos de tuplas no borrosas, pero no para literales y/o conjuntos de tuplas borrosas (la existencia de tuplas y/o relaciones borrosas obliga a evaluar con todas las tuplas, por lo que el CE es el indicado en la [EC. 5.14] ).

Por cada tupla de T1 existirán, en media,

tuplas expandidas en Ti, tal como se deduce de la expresión [EC. 5.14] .

En un conjunto de Ni tuplas, el número medio de tuplas que satisfacen un literal Li, construido con el predicado q, puede calcularse como el producto de la densidad de q ( [EC. 5.8] ) multiplicada por Ni:

    densidad(q) Ni

En el subconjunto de tuplas expandidas a partir de una concreta de T1, el literal Li será satisfecho, en media, por:

    densidad(q)

de estas tuplas. Por tanto, si se miden los parámetros de evaluación en el conjunto proyectado, bastará con que Li sea satisfecho por una de estas tuplas para que no sea necesario evaluar con las restantes tuplas expandidas de la misma tupla original.

El número medio de tuplas expandidas a partir de una misma tupla de T1, que deben usarse para evaluar un literal Li (construido con el predicado q) será (puede verse la demostración en el apartado B.3 ):

    [EC. 5.18]

Partiendo de un conjunto T1 con N1 tuplas, la evaluación de cada literal Li (con el predicado q) se realizará, en media, con un número de tuplas indicado por la siguiente expresión:

    [EC. 5.19]

Puede obtenerse una estimación del valor de CE medio a partir de la densidad media ponderada por el número de literales candidatos:

    densidad_med = [EC. 5.20]

donde

    qi representa un predicado de la BD

    Grado(qi) el grado del predicado qi

    NumLit(m,u) el número de literales que pueden construirse para un predicado de grado m con un máximo de u variables usadas ( apartado B.2 )

    densidad(qi) la densidad del predicado qi ( [EC. 5.8] )

    NumPrOrd el número de predicados no borrosos de la BD

Con lo que resulta:

    CE ª [EC. 5.21]

para la evaluación de cada literal candidato durante la búsqueda del antecedente i-ésimo de una cláusula en construcción, usando el heurístico Interés* con el conjunto proyectado T1[i].

 

El CE de FZFOIL para literales ordinarios sobre conjunto de tuplas no borrosas nunca puede ser mayor que el calculado para FOIL ( [EC. 5.14] ), ya que el caso peor es la evaluación de todas las tuplas (como ocurre en FOIL).

 

Para los literales borrosos (o sobre conjuntos de tuplas borrosas) es necesario evaluar con todas las tuplas, por lo que el coste de evaluación es el mismo que se calculó para FOIL ( [EC. 5.14] ). Esto es así porque el grado se satisfacción del literal candidato para una tupla proyectada (del conjunto T1[i]) vendrá dado por el máximo grado de satisfacción con todas las correspondientes tuplas expandidas (del conjunto Ti).

5.4.2.3 Conclusiones

El coste teórico (asociado al tamaño del espacio de búsqueda de literales) de FZFOIL es algo superior al obtenido en FOIL. El crecimiento de este CT se produce del siguiente modo:

  • Linealmente respecto del número de predicados de la BD.
  • Polinómicamente con el número de variables usadas en la cláusula.
  • Exponencialmente con el grado de los predicados de la BD.

La diferencia de CT entre FOIL y FZFOIL consiste en que, en FZFOIL, el factor de crecimiento lineal asociado al número de predicados ordinarios es menor que el asociado al número de predicados borrosos.

 

El máximo coste de evaluación posible para FZFOIL es el mismo que se calculó para FOIL, por tanto viene limitado por la potencia de los literales que introducen variables nuevas. En el caso particular de que el conjunto local de tuplas sea no borroso y se evalúen literales ordinarios, el coste de evaluación decrece con la densidad de los predicados de la BD.


1. En el caso de seleccionar como relación objetivo una relación definida intensionalmente, es necesario realizar pequeñas modificaciones en el fichero de entrada, para evitar que FZFOIL induzca la misma definición utilizada para construir la relación intensional.

Una forma de conseguirlo es prohibir como "constantes de la teoría" ( apartado C.3.1 ) todos los valores de los dominios utilizados en la construcción de la relación intensional objetivo.

2. Hay que hacer notar que sobre estas definiciones parcialmente construidas no se ha aplicado ningún mecanismo de poda de descripciones, ni ningún mecanismo para eliminar literales redundantes, por lo que no pueden considerarse como los resultados finales del FZFOIL. El objetivo de mostrar estos resultados parciales (después de 60 minutos de ejecución) es el de comparar el proceso de aprendizaje con y sin relaciones borrosas.

Si se ejecutase el algoritmo hasta el final, se aplicarían los mecanismos de poda y, posiblemente, el resultado sería que no existe ninguna definición suficientemente completa y consistente para muchas de estas relaciones objetivo.

3. En este ejemplo se utilizan tres relaciones intensionales pero sólo la primera es relación objetivo. Por tanto, para evitar definiciones infructuosas (tal como se indica en la nota 1. , a pie de página 101. ), basta con prohibir como constantes de la teoría los valores de los dominios utilizados en la construcción de dicha relación objetivo intensional: Id_consulta, Tipo_rest_tte y Tipo_rest_optim.

4. El ejemplo número 5 tiene una LDI algo mayor para el caso borroso, aunque, como ya se ha dicho, no se debe a que la definición borrosa que se construye sea más compleja (realmente es la misma), sino a que cambia la BD de entrada (se consideran 6 relaciones borrosas más).

Esta penalización en la LDI debida al número de relaciones de la BD se está aplicando en todos los ejemplos de tipo b (todos tienen 6 relaciones más que sus equivalentes de tipo a).

5. Con la excepción del ejemplo 5, tal como se explica en la nota a pie de pág. 110.