Modelos y métodos de clasificación.
Clasificación jerárquica
Contenidos
1. Clasificación jerárquica.
2. Eliminación jerárquica.
3. Clasificación jerárquica mediante generación guiada por datos.
4. Diseño e Implementación de un modelo de clasificación simbólica.
2
1. Clasificación jerárquica
3
4
Clasificación jerárquica
También clasificación heurística
Variante clasificación simple
Modelo de recubrimiento
Jerarquía de abstracción de datos
Jerarquía de refinamiento de soluciones
Jerarquía de abstracción de datos
Abstracción Cualitativa:
“recuento leucocitario de 2500” se abstrae a “recuento leucocitario bajo”
Abstracción por Definición:
“recuento leucocitario bajo” se abstrae a “Leucopenia”, pues así se define la Leucopenia
Abstracción por Generalización:
“Leucopenia” se abstrae a “Inmunodepresión”, pues la Leucopenia es un tipo de inmunodepresión
Otras
Combinar dos sensores en un único dato.
Valor máximo de un conjunto de datos.
En general cualquier preprocesamiento de los datos originales (datos “crudos” o raw data).
5
Jerarquía de refinamiento de soluciones
Dotar al espacio de soluciones de estructura.
Añadiendo, si es necesario, clases abstractas.
Permita manipular clases de soluciones, que se van refinando.
6
SUBTIPO
Refinamiento
SUBTIPO
Refinamiento
SUBTIPO
Refinamiento
Enfermedades específicas
Datos del paciente
Espacio de datos Espacio de soluciones
Abstracciones del paciente
Huésped Inmunocomprometido
Inmunodepresión
Leucopenia
Recuento Leucocitario bajo
Recuento Leucocitario < 2.500
GENERALIZACIÓN
DEFINICIÓN
CUALITATIVA
GENERALIZACIÓN
CAUSA Clases de enfermedades
Bacteria que coloniza territorios
no estériles
Abstracción
Bacteria que coloniza
el tracto GI
Enterobacterias
Equiparación
Infección por E. Coli
Ejemplo clasificación jerárquica(I): MYCIN
8
Ejemplo clasificación jerárquica(II): MYCIN
SI (1) se dispone de un análisis de sangre,
(2) el recuento leucocitario es menor que 2,500
ENTONCES (3) las siguientes bacterias podrían estar causando
la infección: E. Coli (.75), Pseudonomas-aeuroginosis (.5),
Klebsiella-pneumoniae (.5).
Modelo de recubrimiento
<D, S, C+, C-, OBS>, siendo:
D, Espacio de Datos Abstractos, un conjunto finito de datos {D1, D2,... ...,Dk}.
S, Espacio de Soluciones, un conjunto finito de soluciones {S1, S2,... ...Sm} o candidatos.
C+, C-, son Relaciones de Recubrimiento, C+SxD, C-
SxD, con C+ C- =.
OBS el conjunto de valores que toman los datos Di de D.
Donde:
El espacio de datos, D, está formado por datos abstractos.
OBS: sobre los datos abstractos.
El espacio de soluciones, S, incluye soluciones abstractas y soluciones refinadas (concretas).
9
Jerarquía de soluciones
H, relaciones que definen la jerarquía de soluciones, HSxS.
Si (S1, S2)H, S2 es hijo de S1
En principio, sin ninguna restricción.
10
11
Modelo gráfico clasificación jerárquica
AD5
AD4
R1
D1
D2
D3
Datos sin procesar
S1
Datos
Abstractos
Soluciones
Abstractas
R2 R3 R4
AD2
AD1 AD3
S2
D4
R7
S3
S4
S5
S6
S7
D5
D6
D7
R8 R5
AD6
R6
Espacio de datos Espacio de soluciones
Soluciones
Refinadas
Elementos de H
Elementos de C+
Elementos de C-
Etapas de Abstracción
El proceso de abstracción de datos no forma parte del modelo.
La jerarquía de soluciones no forma parte del modelo.
Ambos son necesarios para solucionar un problema.
2. Eliminación jerárquica
12
Eliminación jerárquica
Se denomina eliminación jerárquica al proceso de eliminar los descendientes de una solución abstracta cuando esta no es consistente.
Mayor eficacia computacional del proceso de refinamiento de soluciones.
Condición necesaria
El conjunto de tuplas de las relaciones de recubrimiento de una subclase son una extensión de las tuplas de su clase padre:
Si la tupla (Sj, Di) pertenece a C+ (C-), la tupla (Sk Di) ha de pertenecer a C+ (C-) para todo Sk hijo de Sj
13
Modelo de eliminación jerárquica (I) (por recubrimiento)
<D, S, C+, C-, OBS> y H, siendo:
<D, S, C+, C-, OBS> un modelos de recubrimiento.
H, relaciones que definen la jerarquía de soluciones, HSxS.
El modelo de recubrimiento es, formalmente, el mismo. Pero su semántica es diferente.
Si la tupla (Sj, Di) pertenece a C+ (C-), la tupla (Sk Di) también pertenecer a C+ (C-) para todo Sk / (Sj, Sk)H
Economía de la representación: la tupla (Sk Di) no se incluye en la definición del modelo (similar a la herencia de propiedades).
14
15
Modelo gráfico clasificación jerárquica (sin eliminación jerárquica)
AD5
AD4
R1
D1
D2
D3
Datos sin procesar
S1
Datos
Abstractos
Soluciones
Abstractas
R2 R3 R4
AD2
AD1 AD3
S2
D4
R7
S3
S4
S5
S6
S7
D5
D6
D7
R8 R5
AD6
R6
Espacio de datos Espacio de soluciones
Soluciones
Refinadas
16
Modelo gráfico eliminación jerárquica
AD5
AD4
R1
D1
D2
D3
Datos sin procesar
S1
Datos
Abstractos
Soluciones
Abstractas
R2 R3 R4
AD2
AD1 AD3
S2
D4
R7
S3
S4
S5
S6
S7
D5
D6
D7
R8 R5
AD6
R6
Espacio de datos Espacio de soluciones
Soluciones
Refinadas
Consistencia, inconsistencia y explicación
Los mismos conceptos que en clasificación simple.
Pero si una solución abstracta es inconsistente, todos su sucesores son inconsistentes
17
18
Ejemplo
OBS:<1, ?, ?, ?, ?, ?, ?>
Consistente con todas las clases: S1 es consistente.
OBS: <0, ?, ?, ?, ?, ?, ?>
Inconsistente con todas las clases: S1 es inconsistente.
OBS: <1, 0, ?, ?, ?, ?, ?>
Inconsistente con S2 y sus sucesores.
Consistente con S1, S3 y sus sucesores.
19
Ejemplo
Espacio de soluciones
Datos
Abstractos
Soluciones
Abstractas
Espacio de datos
OBS-1 OBS-2 OBS-3
1
?
?
?
?
?
?
0
?
?
?
?
?
?
1
0
?
?
?
?
?
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
S7
D5
D6
D7
Soluciones
Refinadas
CAN-1
e
c
c
c
c
c
c
CAN-2
r
r
r
r
r
r
r
CAN-3
e
r
c
r
r
c
c
3. Clasificación jerárquica mediante generación guiada por datos
20
Clasificación jerárquica y obtención de observaciones
Asumimos modelo de eliminación jerárquica.
Estrategia sencilla y efectiva de obtener nuevas observaciones:
buscar aquellas observaciones que nos permiten seguir refinando los candidatos consistentes de más alto nivel.
Ejemplo
OBS:<1, 0, 1, ?, ?, ?, ?>
Consistentes: S1 y S3.
No necesitamos observaciones D4 y D5.
Basta observar D6 y D7 para obtener la clasificación.
21
Clasificación jerárquica mediante generación guiada por datos
Parte de conjunto reducido de observaciones obtenidas por Monitor.
Abstrae las observaciones con Abstraer.
Genera candidatos más abstractos con GenerarNuevosCandidatos.
Solicita nuevas observaciones, Obtener, para refinar candidatos, hasta llegar a nodos terminales.
Si las nuevas observaciones son consistentes con candidatos abstractos no considerados, se repite el proceso.
22
Clasificación jerárquica mediante generación guiada por datos
El método se basa en las siguientes suposiciones:
Disponemos de los procedimientos, Monitor, Obtener Abstraer y GenerarNuevosCandidatos
El espacio de datos se organiza jerárquicamente facilitando la abstracción de datos.
Las soluciones se organizan en una jerarquía de refinamiento que divide las clases de soluciones.
En cada nivel del espacio de soluciones existe un conjunto de datos que permite discriminar entre ellas. Es posible obtener dichos datos.
Candidatos simples.
23
24
Método de generación guiada por datos
1. Soluciones
2. OBSdistinguidas Monitor( )
3. OBS Abstraer(OBSdistinguidas)
4. Si OBS Entonces
5. Mientras se puedan generar nuevos candidatos raíz hacer
6. Candidatos GenerarNuevosCandidatosRaiz(OBS)
7. Soluciones ProbarDiscriminar(Candidatos) Soluciones
8. Mientras sea posible refinar candidatos hacer
9. Soluciones Soluciones – {Candidato_a_refinar}
10. Candidatos hijos de Candidato_a_refinar en la jerarquía de
soluciones
11. Soluciones PorbarDiscriminar(Candidatos) Soluciones
12. Fin Mientras
13. Fin Mientras
14. Fin Si
15. Devolver(Soluciones)
25
Obtener nuevas observaciones para discriminar entre candidatos
1. ProbarDiscriminar(Candidatos)
2. NuevasSoluciones
3. Obtener OBSadicionales, observaciones necesarias para discriminar entre las
hipótesis de Candidatos
4. NuevasObservaciones Abstraer(OBSadicionales)
5. OBS Nuevas observaciones OBS
6. Para cada Candidato Candidatos hacer
7. Si Prueba(Candidato) Entonces NuevasSoluciones NuevasSoluciones
Candidato
8. Fin Si
9. Fin Para
10. Devolver(NuevasSoluciones)
Ejemplo: OBS iniciales
26
Espacio de soluciones Espacio de datos
OBS
1
(0)
(1)
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS distinguida ya abstraída
OBS aún no solicitadas
Ejemplo: GenerarCandidatosRaíz
27
Espacio de soluciones Espacio de datos
OBS
1
(0)
(1)
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS distinguida ya abstraída
OBS aún no solicitadas
1ª solución
Ejemplo: refinar
28
Espacio de soluciones Espacio de datos
OBS
1
(0)
(1)
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS distinguida ya abstraída
OBS aún no solicitadas
1ª solución
Refinar
Ejemplo: ProbarDiscriminar
29
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
Candidatos
Nuevas Observaciones
Ejemplo: ProbarDiscriminar
30
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
Nuevas Observaciones
Ejemplo: seguir refinando
31
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
(0)
(1) S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
refinar
Ejemplo: ProbarDiscriminar
32
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
Candidatos
Nuevas Observaciones
Ejemplo: ProbarDiscriminar
33
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
3ª solución
Nuevas Observaciones
Ejemplo: generar candidato raíz
34
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
3ª solución
4ª solución
Ejemplo: seguir refinando
35
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
(0)
(0)
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
3ª solución
4ª solución
refinar
Ejemplo: ProbarDiscriminar
36
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
0
0
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
3ª solución
4ª solución
Candidatos Nuevas Observaciones
Ejemplo: ProbarDiscriminar
37
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
0
0
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
OBS aún no solicitadas
1ª solución
2ª solución
3ª solución
4ª solución
5ª solución Nuevas Observaciones
Ejemplo: Soluciones
38
Espacio de soluciones Espacio de datos
OBS
1
0
1
(0)
(1)
0
1 S7
S8
S9
S10
D8
D9
0
0
D1
D2
D3
S1
S2
D4
S3
S4
S5
S6
D5
D6
D7
Soluciones: S1, S3, S7, S8, S10.
Abstractas: S1, S3, S8.
Concretas:S7, S10.
Todas ellas son explicaciones.
4. Diseño e Implementación de un modelo de clasificación simbólica
39
Diseño e Implementación de un modelo de clasificación simbólica
Tradicionalmente
Sistema de producción.
Sin formular explícitamente el modelo de recubrimiento.
Distinguir:
Nivel del conocimiento:
Modelo del conocimiento independiente de la implementación.
Nivel simbólico:
Lenguajes de representación.
40
Nivel del conocimiento y clasificación jerárquica
Descrito en el nivel del conocimiento
Conocimiento del dominio:
Modelo de clasificación por recubrimiento.
Jerarquías de abstracción y refinamiento.
Conocimiento estratégico
Métodos.
41
Diseño e Implementación
Cualquiera, que respete especificaciones nivel del conocimiento.
Sistemas de producción
El modelo de recubrimiento se representa fácilmente mediante reglas.
Método: sólo si el motor de inferencias es suficientemente flexible.
Sistemas de producción en el análisis
De utilidad para desarrollar y probar el modelo de recubrimiento.
42
Ejemplo de codificación
43
Fragmento de
modelo de recubrimiento
D1
D2
D3
S1
S2
S3
SI D1=1
ENTONCES S1
SI S1, D2=0
ENTONCES S2
SI S1, D3=1
ENTONCES S3
Codificación mediante
reglas de producción
Dirección de encadenamiento
Representación del modelo de recubrimiento: indiferente.
Método de generación guiada por datos: más simple hacia atrás.
Idéntica solicitud de observaciones si único candidato raíz.
44
Herramientas
CLIPS
C, C++, dominio público.
clipsrules.sourceforge.net
Jess
Java, licencias comerciales, académicas.
www.jesrule.com
G2
Tiempo real, licencia comercial.
www.gensym.com.
45