dit antonio j. gómez flechosodit.upm.es/~anto/slides/980205/defensa.pdf · ♦mejoras de foil para...

34
Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 1 5 Febrero 1998 Antonio J. Gómez Flechoso dit UPM dit DEPARTAMENTO DE INGENIERÍA DE SISTEMAS TELEMÁTICOS ESCUELA TÉCNICA SUPERIOR DE INGENIEROS DE TELECOMUNICACIÓN UNIVERSIDAD POLITÉCNICA DE MADRID INDUCCIÓN DE CONOCIMIENTO CON INCERTIDUMBRE EN BASES DE DATOS RELACIONALES BORROSAS TESIS DOCTORAL Autor: Antonio José Gómez Flechoso Director: Gregorio Fernández Fernández Madrid, 1998

Upload: truongcong

Post on 20-Jan-2019

219 views

Category:

Documents


0 download

TRANSCRIPT

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 15 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

DEPARTAMENTO DE INGENIERÍA DE SISTEMAS TELEMÁTICOS

ESCUELA TÉCNICA SUPERIOR DEINGENIEROS DETELECOMUNICACIÓN

UNIVERSIDAD POLITÉCNICA DE MADRID

INDUCCIÓN DE CONOCIMIENTO CON

INCERTIDUMBRE EN BASES DEDATOS

RELACIONALES BORROSAS

TESISDOCTORAL

Autor: Antonio José Gómez FlechosoDirector: Gregorio Fernández Fernández

Madrid, 1998

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 25 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

ÍNDICE

❒ Introducción: Necesidades y objetivos

❒ FOIL

❒ Mejoras de FOIL sobre BD

❒ Extensión de FOIL hacia la lógica borrosa: FZFOIL

❒ Ejemplo de aplicación: proyecto SEIC

❒ Conclusiones y futuras líneas de investigación

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 35 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

NECESIDADES YOBJETIVOS

❒ Necesidades:

♦ Análisis inteligente de datos→ minería de datos, ILP

♦ Evaluar calidad del propio conocimiento→ medidas de incertidumbre

❒ Objetivos:

♦ Mejoras de FOIL para aplicarlo sobre BD:

• Corrección de errores de evaluación

• Conocimiento de base (relaciones intensionales)

♦ Extensiones hacia lógica borrosa de primer orden:

• Entrada: relaciones borrosas

• Salida:definiciones con incertidumbre (literales borrosos y medida de precisión)

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 45 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

ESTADO DEL ARTE (1)

❒ FOIL: First Order Inductive Learner ([Quinlan, 90])

♦ Búsqueda por especialización en grafos refinados

♦ Aplicable sobre BD relacionales

♦ Definición lógica de relación objetivo, formada por cláusulas de Horn

p(V1, ..., Vk) :- L1, L2, ..., Ln

❒ Algunas definiciones preliminares

♦ Satisfacción de L = q(V1, ..., Vn): |=t (L) ⇔ <t(V1), ... t(Vn)> ∈ Q

♦ Conjunto cubierto por C = [L0 :- L1, ... Ln]: Tc(C) = {t | |=t(L1∧...∧Ln)}

♦ Consistencia: C consistente ⇔ (∀t ∈ T−) (¬ |=t(L1∧...∧Ln))

♦ Completitud: C completa ⇔ (∀t ∈ T+) (|=t(L1∧...∧Ln))

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 55 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

ESTADO DEL ARTE (2)

❒ FOIL: Algoritmo

Clausula& construyeC(TR,T-,p, ...);

C:= p;

repetir

Li = buscaAntecedente();

Ci =Ci-1 ∨ ¬Li; /*nuevo antec*/

Ti+1 = actualizarT(Ti, Li);

hasta consistente(Ci);

return Ci;

Bucle interno: cláusulaconsistenteBucle externo: definicióncompleta

Definicion& FOIL (T+,T-, p, q1, q2...);

D0:= FALSE;

TC0 = ∅;

repetir

Clausula C = construyeC();

Di = Di-1 ∨ C; /* nueva cláusula */

TCi = TC

i-1 ∪ TC(C)

hasta completa(Di);

return Di;

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 65 Febrero 1998

Antonio J. Gómez FlechosodUd

usula en construcción)

s

e Rissanen)

itPMit

ESTADO DEL ARTE (3)

FOIL: Heurísticos

♦ Para evaluar literales:

Ganancia(Li) = Ni++ ⋅ (Info(Ti) - Info(Ti+1))

siendo: Info(Ti) = −log2(Ni+/(Ni

+ + Ni-))

♦ Para buscar literales:

• Li debe tener al menos una variable existente (en la clá

• Restricción de argumentos de Li en definiciones recursiva

• Uso de “literales determinados”

• Poda alpha-beta para simplificar la búsqueda

• Definiciones inconsistentes y/o incompletas (principio d

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 75 Febrero 1998

Antonio J. Gómez FlechosodUd

ALES (1)-

i

Ti+1b

04

nancia es igual

itPMit

ANÁLISIS DE FOIL: EVALUACIÓN LITER

Err or I: Ganancia insensible a TC

+p1+p2 +p3

−n1 −n2

Ti

Ti+1a

TCi-1 = [P :- L1,..., Li-1]

+p1’

+p1’’

+p2’

+p2’’

−n2’

−n1’

Lia

Ci = [P :- L1,..., Lia]

Info(Ti) = 0.737

Ganancia(Lia) = 0.304

Info(Ti+1a) = 0.585

Ni++ = 2

Interés(Lia) = −0.408

Lib

Ci = [P :- L1,..., Lib]

Info(Ti+1b) = 0.585

Ni++ = 2

+p1+p2 +p3

−n1 −n2

+p1’

+p1’’

+p2

+p2’’

−n1’’

−n1’

Ganancia(Lib) = 0.3

Interés(Lib) = 0.167

2 tuplas + y 2 tuplas− satisfacen Lia

2 tuplas + y 1 tupla− satisfacen Lib

sin embargo, Ga

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 85 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

ANÁLISIS DE FOIL: EVALUACIÓN LITERALES (2)

Err or II: Ganancia no proporcional a TC+

+p1+p2 +p3

−n1 −n2

Ti

Ti+1a

Ti

Ti+1b

Ci-1 = [P :- L1,..., Li-1]

+p1’

+p1’’’ −n1’

+p1’’

+p1iv)

Lia

Ci = [P :- L1,..., Lia]

Info(Ti) = 0.737

Ganancia(Lia) = 0.415

Info(Ti+1a) = 0.322

Ni++ = 1

Interés(Lia) = −0.167

Lib

Ci = [P :- L1,..., Lib]

Info(Ti+1b) = 0.585

Ni++ = 2

+p1+p2 +p3

−n1 −n2

+p1’

−n1’+p2’

Ganancia(Lib) = 0.304

Interés(Lib) = 0.167

1 tupla + y 1 tupla− satisfacen Lia

2 tuplas + y 1 tupla− satisfacen Lib

pero Ganancia(Lai) es mayor

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 95 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

EVALUACIÓN DE LITERALES: SOLUCIÓN (1)

Medida de interés (RI)(Piatetsky-Shapiro,89)

SeaA → B una regla lógica

Entonces N ≡ tamaño conjunto entrenamiento (nº tuplas)

NA, NB ≡ nº tuplas satisfacen condición A, B

NA∧Β ≡ nº tuplas satisfacen condición A∧B

Requisitos de RI:

• A y B independientes⇒ RI = 0

• NA, NB ↓ ⇒ RI ↑

• NA∧B ↑ ⇒ RI ↑

RI1 NA B∧ NA NB⋅( ) N⁄–=

RI2NA B∧ NA NB⋅( ) N⁄–

NA NB 1 NA N⁄–( ) 1 NB N⁄–( )⋅ ⋅ ⋅----------------------------------------------------------------------------------------------=

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 105 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

EVALUACIÓN DE LITERALES: SOLUCIÓN (2)

Interés = RI para evaluar literales

Ci ≡ [P:- L1,...Li ≡ A → B]

A ≡ Li

B ≡ P:-L1,...Li-1

N = Ni+ + Ni

-

NA = Ni++ + Ni

-+

NB = Ni+

NA∧B = Ni++

Interés = f(Ni+, Ni

-, Ni++, Ni

-+) usa Ni-+ ⇒ no error I

Interés mide dependencia entre NA y NB ⇒ no error II

Ci ↔ P∨¬(L1∧¬L2 ∧...∧¬Li-1∧¬Li)

↔ ...

↔ Li → (L1 ∧ L2 ∧ ... ∧ Li-1 → P)

{

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 115 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

ANÁLISIS DE FOIL: EVALUACIÓN LITERALES (3)

Err or III: Ar gumentos no representan a TC+

C0 = [P :- TRUE]

Info(T1) = 0.737

L2a

C2a = [P :- L1, L2a]

Info(T3) = 0

N2++ = 3

L1

C1 = [P :- L1]

Info(T2) = 0.222

N1++ = 3

L2b

C2b = [P :- L1, L2b]

Info(T3) = 0

N2++ = 3

+p1+p2

+p3

−n2

−n1

+p1’

+p2’

+p2’’

+p3’ +p3’’+p3’’’

−n1’

+p3’

+p3’’’

+p3’’

T1

T2

T3a

Ganancia(L2a) = 0.667

Interés(L2a) = 0.354

Interés*(L2a) = 0.333

+p1+p2

+p3

−n2

−n1

+p1’

+p2’

+p2’’

+p3’ +p3’’+p3’’’

−n1’

+p1’

+p2’

+p3’’

T1

T2

T3b

Ganancia(L2b) = 0.667

Interés(L2b) = 0.354

Interés*(L2b) = 1.000

L1,L2a cubre 1 tupla + en T1

L1,L2b cubre 3 tuplas + en T1

sin embargo, Ganancia es igual

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 125 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

EVALUACIÓN DE LITERALES: SOLUCIÓN (3)

Interés* = Interés + conjuntos proyectados

Li

T1

Ti Ti+1

T1[i]

T1[i+1]

Ni+ = Ti

+Ni

− = Ti−

Ni[i+1]+ = Ti

[i+1]+Ni

[i+1]− = Ti[i+1]−

T1[i] = TC(Ci-1) ⊆ T1

1) T1[i] = conj. entrenamiento para Li

2) Aplicar Interés sobre T1[i] Interés* soluciona errores I, II y III⇒

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 135 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

EVALUACIÓN DE LITERALES: EJEMPLO

a1 a2 a3 a4

b1 b2 b3 b4

c1 c3c2 c5c4

d1 d2 d4d3

a1 a2 a3 a4

b1 b2 b3 b4

c1 c3c2 c5c4

d1 d2 d4d3

Relación “padre_de” Relación “jefe_de”

Relaciones:enfermo = <b3>, <b4>, <c3>, <c4>, <c5>, <d2>, <d3>, <d4>padre_de = <a1,b1>, <a1,b2>, <a2,b1>, <a2,b2>, <b1,c1>, <b1, c2>, ...jefe_de = <a1,b1>, <b1,c1>, <c1,d1>, <c2,d1>, <a2,b2>, <a3,b2>, <a4,b3>, ...fumador = <b3>, <b4>, <d2>barbudo = <a3>, <b3>, <b4>, <c1>, <c2>, <c4>, <d1>, <d2>

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 145 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

EVALUACIÓN DE LITERALES: RESULTADOS

♦ Regla inducida por FOIL:

enfermo(A):- jefe_de(B,A), enfermo(B), ¬fumador(B)enfermo(A):- fumador(A)enfermo(A):- jefe_de(B,A), enfermo(B), padre_de(B,A)(consistente peroincompleta: no cubre 2 tuplas⊕)

♦ Regla inducida modificando FOIL con función Interés:

enfermo(A):- padre_de(B,A), barbudo(B), fumador(A)enfermo(A):- padre_de(B,A), enfermo(B)(consistente y completa, perocompleja)

♦ Regla inducida modificando FOIL con función Interés*:

enfermo(A):- padre_de(B,A), enfermo(B)enfermo(A):- fumador(A)(consistente, completa y sencilla)

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 155 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

LÓGICA BORROSA Y MUNDO REAL

❒ Complejidad del mundo real = volumen + incertidumbre ⇒ Compromisoinformación / incertidumbre

♦ Conceptos humanos≈ conjuntos borrosos [Zadeh,65]

♦ Lenguaje humano impreciso (incompatibilidad precisión / significación)

❒ Lógica borrosa [Zadeh,75] (isomorfa con conjuntos borrosos)

♦ Necesaria para inferencias imprecisas

♦ Método natural de representar el mundo real

❒ Sistemas expertos borrosos, BD relacionales borrosas, etc

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 165 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

LÓGICA BORROSA DE PRIMER ORDEN

❒ Lógica borrosa de proposiciones formal

❒ ¿Lógica borrosa de predicados?

♦ Sintaxis de lógica de predicados

♦ ¿Semántica?

• Conjunto valores de verdad: V = [0, 1]

• Satisfacción en gradoσ: =iA(S, σ)⇔ E(S, A, i)= σ

• Calif. borrosos de verdad: “verdadero”, “muy verdadero”, “algo falso”,...

S’ = “S es V”; =iA(S’, σV) ⇔ σV = V(σ)

• Calif. borrosos de prob. (“muy probable”, “poco probable”,...): S’ = “Pro(S) es P”

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 175 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

INDUCCIÓN DE CONOCIMIENTO CON INCERTIDUMBRE

❒ Salida:

♦ Probabilidad: asignable a una regla a partir de conj. entrenamiento o de prueba

(ID3, C4.5, etc), aplicable en sistemas de ILP

❒ Entrada

♦ Incertidumbre en antecedentes: puede ser un atributo más (lógica “0+”)

♦ Incertidumbre en relaciones: ¿?

• No hay sistemas que induzcan reglas borrosas en ILP

• Borrosidad en valor de los atributos≠ Borrosidad en relaciones

Ej: enfermo(A) :- MUY_fumador(A)

Ej: amigos(A,B) :- amigos(A,C), MUY_amigos(C,B)

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 185 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

FZFOIL: FUZZYFIRSTORDERINDUCTIVELEARNER

Definiciones

❒ Signo borroso de una tupla:SB(t) =µP(t) ∈ [0, 1]

❒ Conjunto entrenamiento: T = T + ∪ T − ∪ T ∼

❒ t satisface L en gradoσ: =t(L, σ)⇔ µQ(t) = σ

❒ Cláusula C =p(X1,...,Xk):-L1,...,Ln cubre t en gradoσ ⇔ |=t (L1∧...∧Ln, σ)

❒ Conjunto cubierto por C: TC(C) = {< t, σ >}

♦ Condición de k-cobertura:σ = µTC(C)(t) ≥ k · SB(t)

❒ Condición de consistencia borrosa:(∀t ∈ T) (SB(t)≥ µTC(C)(t))

♦ Condición de k-consistencia

❒ Condición de completitud borrosa:(∀t ∈ T) ( µTC(C)(t) ≥ SB(t))

♦ Condición de k-completitud

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 195 Febrero 1998

Antonio J. Gómez FlechosodUd

struyeC(TR,T-,k,p, ...)

caAntecedente();

∨ ¬Li; /*nuevo antec*/

actualizarT(T1[i] , Li);

oyectarT(T1, T1[i+1]);

sistente(Ci, k);

usulak-consistenteB.

De

ret

itPMit

FZFOIL

AlgoritmoClausula& con

C:= p;

repetir

Li = bus

Ci =Ci-1

T1[i+1] =

TC = pr

hasta k-con

return Ci;

B. interno: clá externo: definiciónk-completa

finicion& FZFOIL (T+,T-,T~,k,p,...)

D0:= FALSE;

TC0 = ∅;

repetir

Clausula C = construyeC();

Di = Di-1 ∨ C; /* nueva cláusula */

TCi = TC

i-1 ∪ TC(C)

hasta k-completa(Di, k);

urn Di;

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 205 Febrero 1998

Antonio J. Gómez FlechosodUd

❒ conjuntos borrosos

NB =

NA = T1[i+1]

SB t( )t T1∈∑

1+ ] t( ))

❒ ado de pertenencia consiendo=t(L i, σ)

ísticas

❒ LGO( σ0.5), NO(1-σ),

itPMit

FZFOIL

Evaluación de literales

Función de evaluación basada en Interés*, adaptada a

N = T1

NA∩B = min SB t( ) µT1

i[,(t

∑{Conjuntos de entrenamiento

T1 ordinario; T i borrosos, construidos modificando grgrado de satisfacción (σ) de Li: = min { , σ},µTi 1+

t( ) µTit( )

FRINA B∧ NA NB⋅( ) N⁄–

NA NB 1 NA N⁄–( ) 1 NB N⁄–( )⋅ ⋅ ⋅----------------------------------------------------------------------------------------------=

Invención de literales: etiquetas lingü

En FZFOIL se utilizan etiquetas: MUY( σ2), ANO_MUY(1−σ2), NO_ALGO(1−σ0.5)

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 215 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

FZFOIL: Ejemplo

[D1] {8.951 bits} TC: [6.58/7.04]; TR: [0.12]

[C1] {7.953 bits} [6.70/19.00]-> [5.04/5.37]

enfermo (A) :-

padre_de (B A),

ALGO_enfermo (B).

[C2] {3.584 bits} [1.62/13.00]-> [1.54/1.67]

enfermo (A) :-

MUY_fumador (A).

*padre_de (persona,persona)

a1,b1

a2,b1

a1,b2

a2,b2

a3,b3

a3,b4

a4,b3

a4,b4

b1,c1

b1,c2

b2,c3

*jefe_de (persona,persona)

a1,b1

a2,b2

a2,b3

a3,b2

a3,b3

a4,b3

b1,c1

b2,c2

b3,c3

b4,c4

b4,c5

c1,d1

c2,d1

c2,d2

c2,d3

c4,d2

c4,d3

c5,d4

c2,d1

c3,d2

c3,d3

c3,d4

c4,d2

c4,d3

c4,d4

c5,d4

enfermo (persona)

b3 : 0.9

b4 : 0.72

c3 :0.9

c4 :0.8

c5 :0.88

d2 :0.9

d3 :0.85

d4 : 0.75

*fumador (persona)

b3 :0.95

b4 :0.8

d4 :0.75

*barbudo (persona)

a3 :0.4

a4 :0.7

b4 :0.88

c1 :0.9

*I_nieto_de(persona, persona)

nieto_de(A,B):-

padre_de(C,A), padre_de(B,C)

d2 :0.4

c1 :0.2

a2 :0.3

c2 :0.5

c4 :0.95

d1 :0.6

d2 :1

b2,c3

b2,c4

b3,c2

b3,c3

b3,c4

b4,c4

b4,c5

c1,d1

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 225 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

FZFOIL

Análisis de la complejidad

linealmente con nº predicados de BD

polinómicamente con nº variables de la cláusula

exponencialmente con grado de predicados de la BD{• CE máximo limitado por literales que introducen nuevas variables

• CT crece:

❒ En FOIL:

❒ Coste(Li) = CT ⋅ CE• Tamaño de espacio de búsqueda o coste teórico (CT)

• Tamaño del conjunto intermedio de tuplas o coste de evaluación (CE)

conjuntos borrosos: mismo CE que FOILconjuntos ordinarios: CE menor que en FOIL (conjuntos proyectados){

❒ En FZFOIL:• CT crece del mismo modo que en FOIL (algo más por etiquetas borrosas)

• CE

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 235 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (1)

❒ SEIC (Servicio de Información Ciudadana) “PASO, PC-183”

❒ Problema “Usos y Demandas”: Análisis inteligente de consultas de usuarios

❒ Datos de entrada: 40000 consultas, con 14 atributos:

• Ubicación de PIC (Alonso Martínez, Atocha Renfe, Callao, Av. América, etc)

• Mes: “Julio”, “Agosto”, “Septiembre”, “Octubre”, “Noviembre”

• Día del mes: [1 ... 31]

• Día de semana: “Lunes”, ..., “Domingo”

• Origen/destino: “Aquí”, “Calle”, “Cruce”, “Estación metro”

• Modo transporte: “Cualquiera”, “sólo bus”, “sólo metro”

• Criterio de camino: “Óptimo”, “mín. transbordos”, “mín. tiempo”,

• etc.

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 245 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (2)

❒ Selección y preprocesado: muestreo y 10 atributos ordinarios (2 borrosos)

❒ Transformación de los datos:

• 8 relaciones ordinarias:destino, origen, fecha, rest_tte, rest_optim, etc.

• 6 relaciones borrosas: cuando_mañana, cuando_tarde, cuando_noche,

duración_larga, duración_corta, duración_media

2 4 6 8 10 12 14 16 18 20 22 24 Hora_día

µ

1

0

Noche Mañana Tarde Noche

❒ Relaciones intensionales:

bus_mintransbordos(X):-

rest_tte(X,Y), Y=”solo_bus”, rest_optim(X,Z), Z=”min_transbordos”

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 255 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (3)

❒ Algunas definiciones borrosas:

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

min_tiempo ( A ) :-

cuando_tarde ( A B C ),

¬ =_const ( C Viernes )...

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

bus_mintransbordos ( A ) :-

sólo_bus ( A ).

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 265 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (4)

Comparación del valor de LDI

Ordinaria Borrosas

Ejemplo 1 121.035 bits 17.062 bits

Ejemplo 2 151.411 bits 31.291 bits

Ejemplo 3 38.016 bits 31.291 bits

Ejemplo 4 18.195 bits 65.925 bits

Ejemplo 5 4.907 bits 5.392 bits

Ejemplo 6 114.186 bits 9.155 bits

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 275 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (5)Comparación del valor de k-completitud

Ordinarias Borrosas

Ejemplo 1 0.2017 0.4990

Ejemplo 2 0.5845 0.2443

Ejemplo 3 0.0259 0.4001

Ejemplo 4 0.1143 0.5477

Ejemplo 5 1.0000 1.0000

Ejemplo 6 0.3023 1.0000

Comparación del valor de k-consistencia

Ordinaria Borrosas

Ejemplo 1 0.6220 0.4481

Ejemplo 2 0.7275 0.6254

Ejemplo 3 0.5000 0.2291

Ejemplo 4 0.6154 0.1158

Ejemplo 5 1.0000 1.0000

Ejemplo 6 0.2626 0.2456

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 285 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESULTADOS: PROYECTOSEIC (6)Comparación de k-completitud / LDI

Ordinarias Borrosas

Ejemplo 1 0.0017 0.0293

Ejemplo 2 0.0039 0.0078

Ejemplo 3 0.0007 0.0128

Ejemplo 4 0.0063 0.0083

Ejemplo 5 0.2038 0.1854

Ejemplo 6 0.0026 0.1095

Comparación de k-consistencia / LDI

Ordinaria Borrosas

Ejemplo 1 0.0051 0.0263

Ejemplo 2 0.0048 0.0200

Ejemplo 3 0.0132 0.0073

Ejemplo 4 0.0338 0.0018

Ejemplo 5 0.2038 0.1854

Ejemplo 6 0.0023 0.0269

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 295 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

RESUMEN

❒ Aportaciones de FZFOIL:

♦ Corrige errores de evaluación de literales de FOIL (función Interés*).

♦ Permite introducir conocimiento de base (relaciones intensionales).

♦ Aplicable sobre BD relacionales ordinarias y borrosas.

♦ Definiciones lógicas pueden ser borrosas (lógica borrosa de predicados). Ade-

más incluye otras medidas de incertidumbre: precisión borrosa.

❒ Resultados

♦ Mejora de resultados con relaciones borrosas y definiciones borrosas.

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 305 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

CONCLUSIONES

❒ Funciones basadas en medidas de interés mejoran la calidad de las reglasinducidas por FOIL y FZFOIL (corrigen algunos errores).

❒ La lógica borrosa facilita el modelado de datos de entrada y simplifica las defi-niciones lógicas inducidas.

❒ El coste computacional asociado a FZFOIL (con relaciones borrosas):

♦ El espacio de búsqueda crece un poco más (factor lineal, debido a etiquetas de

literales borrosos)

♦ El coste de evaluación no crece más (con relaciones ordinarias crecen menos,

gracias a los conjuntos proyectados)

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 315 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

FUTURAS LÍNEAS DE INVESTIGACIÓN

❒ Modificaciones en función Interés para cuantificar otros aspectos: compleji-dad de la regla, favorecer a ciertos predicados, etc.

❒ Nuevos algoritmos de búsqueda de descripciones, para evitar máximos localesy simplificar el espacio de búsqueda: algoritmos genéticos, por ejemplo.

❒ Ampliaciones en lenguaje de representación del conocimiento: uso de funcio-nes en lógica de predicados.

❒ Mayor flexibilidad en representación de incertidumbre: relaciones borrosasgeneralizadas (distribuciones de posibilidad, etiquetas lingüísticas, funciones,etc.)

❒ Mejoras en el proceso de inducción: formación de conceptos

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 325 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

+p1+p2 +p3

−n1 −n2

Ti

Ti+1a

Ti

Ti+1b

Ci-1 = [P :- L1,..., Li-1]

+p1’

+p1’’

+p2’

+p2’’

−n2’

−n1’

Lia

Ci = [P :- L1,..., Lia]

Info(Ti) = 0.737

Ganancia(Lia) = 0.304

Info(Ti+1a) = 0.585

Ni++ = 2

Interés(Lia) = −0.408

Lib

Ci = [P :- L1,..., Lib]

Info(Ti+1b) = 0.585

Ni++ = 2

+p1+p2 +p3

−n1 −n2

+p1’

+p1’’

+p2’

+p2’’

−n1’’

−n1’

Ganancia(Lib) = 0.304

Interés(Lib) = 0.167

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 335 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

+p1+p2 +p3

−n1 −n2

Ti

Ti+1a

Ti

Ti+1b

Ci-1 = [P :- L1,..., Li-1]

+p1’

+p1’’’ −n1’

+p1’’

+p1iv)

Lia

Ci = [P :- L1,..., Lia]

Info(Ti) = 0.737

Ganancia(Lia) = 0.415

Info(Ti+1a) = 0.322

Ni++ = 1

Interés(Lia) = −0.167

Lib

Ci = [P :- L1,..., Lib]

Info(Ti+1b) = 0.585

Ni++ = 2

+p1+p2 +p3

−n1 −n2

+p1’

−n1’

+p2’

Ganancia(Lib) = 0.304

Interés(Lib) = 0.167

Inducción de conocimiento con incertidumbre en BD relacionales borrosas. Pág. 345 Febrero 1998

Antonio J. Gómez FlechosoditUPMdit

C0 = [P :- TRUE]

Info(T1) = 0.737

L2a

C2a = [P :- L1, L2a]

Info(T3) = 0

N2++ = 3

L1

C1 = [P :- L1]

Info(T2) = 0.222

N1++ = 3

L2b

C2b = [P :- L1, L2b]

Info(T3) = 0

N2++ = 3

+p1+p2

+p3

−n2

−n1

+p1’

+p2’

+p2’’

+p3’ +p3’’+p3’’’

−n1’

+p3’

+p3’’’

+p3’’

T1

T2

T3a

Ganancia(L2a) = 0.667

Interés(L2a) = 0.354

Interés*(L2a) = 0.333

+p1+p2

+p3

−n2

−n1

+p1’

+p2’

+p2’’

+p3’ +p3’’+p3’’’

−n1’

+p1’

+p2’

+p3’’

T1

T2

T3b

Ganancia(L2b) = 0.667

Interés(L2b) = 0.354

Interés*(L2b) = 1.000