modelos y métodos de clasificación.calonso/ingenieria conocimiento...asumimos modelo de...

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