jueves, 17 de julio de 2008

Inferencia Utilizando Distribución Conjunta Completa


Para este trabajo hemos elegido el tema de las infecciones respiratorias agudas (IRAS), específicamente la neumonía en los niños, considerando las siguientes variables:
  • Factor Respiratorio (FR), esta variable puede tomar tres valores {>40, >50, >60}.
  • Edad, esta variable puede tomar 2 valores {2-11 meses, 1-4años}
  • Disnea (D), esta variable es de tipo booleana {true, false}
  • Estertores Crepitantes (EC), esta variable es de tipo booleana {true, false}
  • Murmullo Vesicular(MV), esta variable es de tipo booleana {true, false}
  • Tos (T), esta variable es de tipo booleana {true, false}
  • Sibilancia (S), esta variable es de tipo booleana {true, false}
  • Cianosis (C), esta variable es de tipo booleana {true, false}

Todas estas variables las hemos obtenido de un Estudio sobre signos y síntomas indicadores de neumonía en la infancia y su utilización en programas de control de infecciones respiratoriasagudas (IRA), el cual lo pueden encontrar aquí. Con este estudio pudimos también obtener la tabla de distribución conjunta completa, la cual se muestra a continuación(por cuestiones de espacio ha quedado dividida en tres partes):







La implementación se realizó de dos formas:
  1. En la primera forma se decidió considerar la siguiente estructura:
    Estructura{ FR de tipo Byte
    D de tipo boolean
    T de tipo boolean
    EC de tipo boolean
    MV de tipo boolean
    S de tipo Boolean
    C de tipo boolean
    Edad de tipo string
    Valor de tipo double}

    A partir de esta estructura se crea una matriz, de manera que cada una de las celdas de la tabla, de distribución conjunta completa, tiene la forma de dicha estructura.
    Esta forma de trabajar trajo varios problemas pues para calcular un tipo de probabilidad como por ejemplo: P (FR ^ D), la codificación es tediosa, es decir se tenia que redundar demasiado en el código (no permitía simplificar el proceso).
    De todas maneras se logro implementar las probabilidades, pero con demasiadas líneas de código.
  2. En la segunda forma ya no se ha considerado una estructura como en el primer caso, sino más bien una matriz de n x 17, donde ‘n’ es el número de celdas que existe en la tabla de distribución conjunta completa.


Así por ejemplo para la primera celda la fila uno de la matriz será:


Como podemos ver cada fila de la matriz es una codificación en binario, en donde el valor es 1 si la variable ocurre, sino es 0.

Realizando este tipo de implementación se pudo simplificar todo el trabajo hecho en la primera forma, pues ya se sabía explícitamente que por ejemplo a FR>40 le corresponde el número 12, y por tanto para calcular su probabilidad, lo que hacemos es mantener fija la columna 12 de la matriz y el resto variar.
Por tanto la mejor manera de implementar este problema es usando una codificación binaria para cada celda de la tabla de distribución conjunta completa.

lunes, 14 de julio de 2008

Problema de Satisfacción de Restricciones (PSR)

Para conocer un poco sobre PSR puedes ver las diapositivas del curso aquí

En esta oportunidad hemos implementado un algoritmo Algoritmo para PSR que utiliza heurística de grado, heurística MVR y forward checking para el problema de coloración de mapas.

El problema de coloración de mapas ha sido simplificado a colorear un grafo, donde los nodos representan a los lugares del mapa y los arcos representan a las restricciones.
Inicialmente hemos usado un dominio de tres colores, lo que traía como consecuencia de que existan soluciones inconsistentes y por tanto el grafo no era coloreado. Debido a este problema se considero usar un dominio con cuatro colores, por la existencia del teorema de los cuatro colores, para el coloreado de grafos, el cual dice que todo grafo puede ser coloreado con a lo mas 4 colores.
Aplicando este cambio donde el dominio es ahora cuatro colores, entonces nuestro programa debe colorear cualquier grafo, es decir la solución siempre es consistente


A continuación se muestra algunas imagenes del programa.
En este caso el coloreado se realiza con un dominio de 3 colores, la solución es consistente.

Al igual que en el caso anterior el dominio es de 3 colores, pero la solución no se encuentra, es decir es inconsistente.

En este caso se usa un dominio de 4 colores, como se dijo antes el grafo debe ser coloreado( encuenrta solución)