dit antonio j. gómez flechosodit.upm.es/~anto/slides/980205/defensa.pdf · ♦mejoras de foil para...
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