Diagnosis de sistemas dinámicos mediante el aprendizaje de modelos proposicionales
Full text
Diagnosis de Sistemas Dinámicos Mediante el Aprendizaje de Modelos Proposicionales Departamento de Lenguajes y Sistemas Informáticos Memoria de la Tesis Doctoral para optar al grado de Doctor en Informática por la por la Universidad de Sevilla presentada por D. Pedro J. Abad Herrera Directores: D. Rafael Martínez Gasca D. Juan A. Ortega Ramírez Sevilla, 2007
ii
Don Rafael Martínez y Don Juan A. Ortega, Profesores Titulares de Universidad adscritos al área de Lenguajes y Sistemas Informáticos, CERTIFICAN QUE Don Pedro J. Abad Herrera, Ingeniero Informático por la Universidad de Sevilla, ha realizado bajo nuestra supervisión el proyecto de investigación titulado: Diagnosis de Sistemas Dinámicos Mediante el Aprendizaje de Modelos Proposicionales Una vez revisado, autorizamos la presentación del mismo como Tesis Doctoral en la Universidad de Sevilla y estimamos oportuna su presentación al tribunal que habrá de valorarlo Fdo. Pedro J. Abad Herrera Fdo. Rafael Martínez Fdo. Juan A. Ortega Doctorando Profesores Titulares de Universidad Área de Lenguajes y Sistemas Informáticos Sevilla, 2007 iii
iv
Tesis Doctoral parcialmente subvencionada por la Comisión Interministerial de Ciencia y Tecnología con los Proyectos DPI2006-15476-C02-00 y TSI2006-13390-C02-02. v
A Lola vi
Agradecimientos Voy a intentar expresar, en breves palabras, mi enorme agradecimiento a aquellas personas que han ayudado en el desarrollo de la presente Tesis. Por supuesto, a mis padres, que me han dado la oportunidad de recorrer el largo camino que hasta aquí conduce con generosidad y sacricio. A mis directores de Tesis, Rafael y Juan, por mostrar su conanza en mi para sacar adelante este trabajo, y por su apoyo y empuje en todo momento. Sin duda, a lo largo de estos años hemos forjado una muy buena relación profesional, y lo que es más importante, también personal. A mi compañero Antonio, por tantísimo trabajo conjunto y tantos años de camino recorrido juntos. A Pepe, puesto que su punto de vista siempre es una nueva opción. A Juan y Juanma, por su colaboración desinteresada y tantas horas de consultas soportadas con el mejor de los ánimos. A todos aquellos compañeros y amigos que han mostrado su interés por la evolución del presente trabajo, y me han animado y apoyado. Finalmente, a mi mujer, Lola, porque sin su ayuda, apoyo y comprensión los desánimos y dudas hubiesen supuesto un escollo insalvable. Y como no, a mi hijo Jaime, por tantos 'papa ahora no puede'. Sinceramente, gracias a todos. Pedro J. Abad vii
viii
Índice general Lista de tablas xv Lista de guras xix Lista de algoritmos xxi 1. Introducción 1 1.1. Generalidades.............................. 2 1.2. Objetivos de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. MarcodelaTesis............................ 4 1.4. Estructura de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Planteamiento del Problema 9 2.1. Antecedentes .............................. 9 2.2. Diagnosis de Sistemas Dinámicos . . . . . . . . . . . . . . . . . . . 12 2.2.1. Diagnosis de sistemas dinámicos basado en estados versus basado en simulación . . . . . . . . . . . . . . . . . . . . . . 14 2.3. Hipótesis para la solución del problema . . . . . . . . . . . . . . . . 16 3. Técnicas de Diagnosis Automática 19 3.1. Diagnosis basada en conocimiento . . . . . . . . . . . . . . . . . . . 20 3.2. Diagnosis basada en casos . . . . . . . . . . . . . . . . . . . . . . . 22 3.3. Diagnosis basada en modelos . . . . . . . . . . . . . . . . . . . . . . 26 3.3.1. Comunidades FDI y DX . . . . . . . . . . . . . . . . . . . . 28 3.3.2. El problema del modelado . . . . . . . . . . . . . . . . . . . 30 3.3.3. Niveles de abstracción en el modelado . . . . . . . . . . . . . 31 3.3.4. Relaciones Causa-Efecto . . . . . . . . . . . . . . . . . . . . 32 ix
xvi
Lista de guras 2.1. Fase O-line de la metodología general . . . . . . . . . . . . . . . . 17 2.2. Fase On-line de la metodología general . . . . . . . . . . . . . . . . 18 3.1. Técnicas para la diagnosis automática . . . . . . . . . . . . . . . . . 19 3.2. Jerarquía de diagnostico . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3. Metodología de la Diagnosis Basada en Modelos . . . . . . . . . . . 26 3.4. Detección de discrepancias . . . . . . . . . . . . . . . . . . . . . . . 38 3.5. Solución de un problema CSP . . . . . . . . . . . . . . . . . . . . . 40 3.6. Diagnosis mediante clasicación automática . . . . . . . . . . . . . 45 4.1. Interdisciplinariedad en el proceso de KDD ............. 56 4.2. Fases del proceso de KDD ....................... 57 4.3. Regresión de Y sobre X ........................ 69 4.4. Ejemplo de Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.5. Ejemplo de árbol de decisión . . . . . . . . . . . . . . . . . . . . . 74 4.6. Cortes realizados según el criterio de partición . . . . . . . . . . . . 74 4.7. Estructura de una red neuronal . . . . . . . . . . . . . . . . . . . . 77 5.1. Procedimiento de clasicación . . . . . . . . . . . . . . . . . . . . . 86 5.2. Ejemplo de diagrama ROC . . . . . . . . . . . . . . . . . . . . . . 95 5.3. Esquema general de Stacking . . . . . . . . . . . . . . . . . . . . . 97 5.4. Esquema general de Cascading . . . . . . . . . . . . . . . . . . . . 98 6.1. Fase O-line de la metodología general . . . . . . . . . . . . . . . . 104 6.2. Fase on-line de la metodología general . . . . . . . . . . . . . . . . 105 6.3. Distintos transitorios de un sistema . . . . . . . . . . . . . . . . . . 106 6.4. Distintas variables observables de un sistema . . . . . . . . . . . . . 108 xvii
6.5. Trayectorias semejantes de distintos comportamientos a diferente altura ..................................113 6.6. Alcance del estado estacionario bajo diferentes fallos . . . . . . . . . 116 6.7. Aproximación de una trayectoria mediante segmentos . . . . . . . . 120 6.8. Comportamientos de un sistema de 2 º orden.............125 6.9. Especicaciones de un sistema de 2 º orden..............127 6.10. Representación del nodo que clasica las clases Clase1 y Clase2 . . 133 6.11. Multiclasicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.12. Evaluación de la Multiclasicación . . . . . . . . . . . . . . . . . . 135 6.13. Trayectorias no diagnosticables entre si . . . . . . . . . . . . . . . . 139 6.14. Inclusión del etiquetado múltiple en la metodología base . . . . . . 141 6.15. Inclusión de la clasicación binaria en la metodología base . . . . . 144 6.16. Evaluación de la clasicación binaria . . . . . . . . . . . . . . . . . 144 6.17. Conjuntos de trayectorias separables . . . . . . . . . . . . . . . . . 147 6.18. Conjuntos de trayectorias separables . . . . . . . . . . . . . . . . . 148 6.19. Selección del instante y valor de clasicación . . . . . . . . . . . . . 152 7.1. Lazo de Control de un motor eléctrico . . . . . . . . . . . . . . . . 155 7.2. Modelado mediante diagrama de Forrester . . . . . . . . . . . . . . 156 7.3. ComportamientoOK..........................158 7.4. Comportamiento Cm Alta . . . . . . . . . . . . . . . . . . . . . . . 159 7.5. Comportamiento Cc Baja . . . . . . . . . . . . . . . . . . . . . . . 159 7.6. Comportamiento Cc Alta vs Cm Alta . . . . . . . . . . . . . . . . . 159 7.7. Lazodecontrol .............................168 7.8. Modelo en Simulink r delsistema...................169 7.9. Modelo en Simulink r delmotorDC .................169 7.10. Circuito equivalente del motor de continua . . . . . . . . . . . . . . 170 7.11. Señales para la operación de Chopper .................171 7.12. Modelo Simulink r del sistema con el fallo de 1 fase . . . . . . . . . 174 7.13. Evolución de las variables observables del sistema . . . . . . . . . . 175 7.14. Herramienta C5.0 r ...........................178 7.15. Diagrama de bloques del sistema . . . . . . . . . . . . . . . . . . . 180 7.16.Sistemareal...............................181 7.17. Herramienta que automatiza el tratamiento . . . . . . . . . . . . . . 184 xviii
7.18. Diagnosis on-line del comportamiento correcto . . . . . . . . . . . . 187 7.19. Diagnosis on-line delfalloF4 .....................187 7.20. Herramienta para la generación de reglas con DISETRA . . . . . . 189 7.21. Diagnosis On-Line delfalloF2.....................192 A.1. Diagrama de bloques . . . . . . . . . . . . . . . . . . . . . . . . . . 199 A.2. Motor ALECOP AL 506; 220V/0.61 KW . . . . . . . . . . . . . . . 200 A.3. Diagrama del circuito desarrollado . . . . . . . . . . . . . . . . . . . 201 A.4. Circuito desarrollado . . . . . . . . . . . . . . . . . . . . . . . . . . 202 A.5. Alguna de las posibilidades de la herramienta Geredisis .......204 A.6. Panel de Control de la aplicación Labview para la recogida de datos 205 A.7. Diagrama de bloques de la aplicación Labview para la recogida de datos...................................206 A.8. Panel de Control de la aplicación Labview para el diagnóstico . . . 207 xix
xx
Lista de algoritmos 6.1. Algoritmo para la recogida de información . . . . . . . . . . . . . . 110 6.2. Algoritmo de segmentación de ventana deslizante . . . . . . . . . . 120 6.3. Algoritmo de normalización . . . . . . . . . . . . . . . . . . . . . . 122 6.4. Algoritmo de etiquetado múltiple . . . . . . . . . . . . . . . . . . . 141 6.5. Algoritmo de búsqueda de conjuntos de trayectorias totalmente separables .................................150 6.6. Algoritmo de búsqueda de conjuntos de trayectorias separables individualmente y no separables . . . . . . . . . . . . . . . . . . . . . 151 xxi
xxii
Capítulo 1 Introducción La detección y la diagnosis del funcionamiento anómalo de mecanismos y procesos son importantes desde el punto de vista estratégico de las empresas, debido a las demandas económicas y de conservación del medio ambiente que se requieren para permanecer en los mercados competitivos. En parte esto conduce a que sea un campo de investigación muy activo. Los fallos producidos en los componentes y procesos pueden provocar paradas indeseables y deterioro de los sistemas, con el consiguiente aumento de costos y la disminución de la producción. Por tanto para mantener los sistemas en niveles de seguridad, producción y abilidad deseados se necesita desarrollar mecanismos que permitan la detección y diagnosis de esos fallos que se producen en los sistemas. Por su parte, el campo de la minería de datos 1 ha proporcionado en los últimos años una gran diversidad de técnicas informáticas, que son capaces de extraer, de forma automática, información relevante de grandes volúmenes de información almacenada. Dichas técnicas pueden descubrir, por ejemplo, el modelo de funcionamiento de un sistema partiendo de los datos de funcionamiento almacenados de dicho sistema. El presente proyecto de tesis se centra en la aplicación de técnicas de minería de datos para obtener diagnosticadores de fallos de sistemas dinámicos, que sean poco costosos computacionalmente, rápidos y capaces de trabajar en condiciones de monitorización on-line . 1 del inglés data mining 1
2 1.1. Generalidades 1.1. Generalidades Entendemos por detección de fallos la tarea de determinar, a partir de las observaciones realizadas, cuándo existe un funcionamiento incorrecto del sistema sujeto a observación, y por diagnosis de fallos cuáles son las causas de ese comportamiento incorrecto. El concepto de Diagnóstico es muy amplio y cubre prácticamente todos los aspectos de la vida cotidiana: medicina, dispositivos electrónicos, procesos químicos, economía, ecosistemas, etc. En el presente trabajo nos centraremos en el campo de diagnosis de los dispositivos físicos, y más concretamente de las actividades industriales, especícamente en sistemas dinámicos. Los principales objetivos de los sistemas de diagnóstico para los sistemas industriales serán: Evitar situaciones de riesgo, tanto para los seres humanos como para el entorno ambiental donde se desarrolla dicho proceso industrial. Ayudar al personal de control en el análisis de la información que generan los dispositivos de medida. Mejorar la calidad del producto nal mediante la detección de fallos en el proceso o en el producto. Facilitar la optimización de la marcha del proceso, mediante la detección de fallos que pueden propagarse a otros componentes del sistema o generar productos defectuosos. Para mejorar y agilizar el proceso de detección de fallos y su posterior diagnóstico es importante que dichos procesos sean rápidos y ecientes, y es necesario para ello automatizar el diagnóstico, entendiendo como tal la utilización de los ordenadores para reducir o eliminar la intervención humana en el proceso de diagnosis. En el entorno de los procesos industriales, la monitorización debe representar un el reejo del sistema y de las desviaciones que se producen del comportamiento esperado. La diagnosis permite identicar las partes que fallan. Generalmente los sistemas de diagnosis integran la monitorización (suponemos que los sensores
Capítulo 1. Introducción 3 funcionan correctamente) y la diagnosis (detección e identicación de fallos). La diagnosis de fallos determina por qué un sistema diseñado correctamente no esta funcionado como se esperaba. La explicación de dicho comportamiento erróneo, a partir de una observación determinada, es la principal tarea de la diagnosis de fallos. 1.2. Objetivos de la Tesis El campo de la diagnosis de fallos es un campo de investigación vigente y con un fuerte crecimiento desde hace algún tiempo, debido a las fuertes necesidades que desde diversos campos de la ciencia y la ingeniería surgen cada día. El objetivo fundamental que ha orientado la realización de los trabajos que se incluyen en esta memoria ha sido la denición de una metodología, que de una forma automática pueda generar clasicadores de sistemas dinámicos que puedan trabajar on-line , y que puedan evaluar el comportamiento del sistema a diagnosticar con unos requerimientos computacionales muy contenidos. Para conseguir dicho objetivo, nos hemos centrado en las técnicas de KDD 2 , y más concretamente en la clasicación automática . Dentro de dicha técnica, los árboles de decisión son una forma de representar el conocimiento que requiere poca capacidad de almacenamiento, y cuya evaluación puede ser realizada sin grandes exigencias computacionales en muy poco tiempo. Todo ello los hace ideales para conseguir el objetivo pretendido. Los modelos generados son comprensibles , ya que pueden ser interpretados por los seres humanos y proposicionales , al aprender de una única tabla sin relacionar más de una la o atributo cada vez [Hernández Orallo et al. , 2004]. En la búsqueda de dicho objetivo, se han adaptado las fases del proceso de KDD a la metodología diseñada con el n de obtener los resultados deseados. Durante esta adaptación, han surgido diversas necesidades, cuya solución se constituye en objetivos parciales. Uno de los primeros problemas que hay que solventar es el manejo de grandes cantidades de información provenientes de las lecturas de los sensores del sistema a diagnosticar. Para ello se propone la reducción de la información no relevante 2 Knowledge Discovery Databases
10 2.1. Antecedentes Depuración de Software. [Sabin et al. , 1995; Wotawa, 1996; R. et al. , 2002; Chen and Wotawa, 2006] Sistemas biológicos, que se pueden considerar como procesos biológicos en el ámbito industrial o ecosistemas. [Struss and Heller, 1999; Davids et al. , 2006] Por otra parte la diagnosis puede ser realizada en tres tipos de sistemas distintos, cada uno de ellos con sus propias características: Sistemas estáticos, entendiendo como tales aquéllos cuyas salidas dependen únicamente de las entradas y de algunos parámetros constantes del sistema. No dependen del tiempo en su evolución, como pueden ser la diagnosis de componentes electrónicos. [de Kleer et al. , 1992; Yvan et al. , 2005]. Sistemas dinámicos, entendiendo como tales aquéllos sistemas donde existe una evolución temporal, y el fallo de algún componente del sistema provoca que su evolución temporal sea diferente. En estos sistemas la salida del sistema depende las variables de entrada, los parámetros del sistema y el instante en el que se encuentre, lo que conforma el estado del sistema. El comportamiento del sistema puede entonces ser descrito en términos de evolución de un estado a otro. [Struss, 1997; Liu et al. , 2006]. Sistemas híbridos. (Discrete Event System). Los sistemas híbridos son sistemas dinámicos complejos, cuyo comportamiento se modela como un sistema híbrido. Los modelos híbridos presentan tanto comportamientos discretos como continuos. Son representados típicamente como una secuencia de trozos de comportamiento continuo intercalados con transiciones discretas. Cada periodo de comportamiento continuo representa lo que se llama modo del sistema. Las transiciones entre modos dan como resultado cambios en el comportamiento continuo del sistema así como el vector de estado que inicializa el comportamiento en el nuevo modo. Las transiciones discretas son modeladas como autómatas de estados nitos, lógica temporal, funciones de cambio o algún otro sistema de transición. El comportamiento continuo dentro de un modo del sistema se modela con ecuaciones diferenciales y algebraicas u otros métodos. [McIlraith et al. , 1999; García et al. , 2005].
Capítulo 2. Planteamiento del Problema 11 Cuando hablamos además de sistemas dinámicos, es necesario tener en cuenta que debido a la dinámica del sistema los fallos que se pueden detectar son de tres tipos: Fallos abruptos, entendiendo como tal el fallo que se produce de forma instantánea en un momento dado, y a partir de ese instante permanece presente en el sistema en la misma magnitud. Fallos incipientes, que son aquéllos fallos que, normalmente debido al desgaste de algún componente del sistema, comienza como un fallo de magnitud pequeña y va evolucionando en el tiempo a una magnitud mayor, hasta alcanzar un máximo. Fallos intermitentes, que son los fallos que se producen en el sistema de forma intermitente, remitiendo tras un tiempo y volviendo a producirse pasado un periodo de tiempo. Son los más difíciles de detectar y constituye uno de los principales problemas abiertos en el campo de la diagnosis de sistemas dinámicos. Esta distinción no ocurre en los sistemas estáticos debido a que en ellos no existe dependencia del tiempo, con cual el fallo está o no presente en el momento de la detección. Dependiendo del momento de detección del fallo los sistemas de diagnóstico pueden ser: OFF-LINE , que se produce cuando los requisitos de tiempos entre la ocurrencia del fallo y la detección del mismo no son considerados importantes. En estos casos el diagnosticador puede ser ejecutado a voluntad, sin necesidad de que esté continuamente diagnosticando el sistema. En [Struss et al. , 1997] lo encontramos aplicado a la diagnosis del circuito hidráulico del ABS de un vehículo. ON-LINE o diagnosis a bordo, donde el sistema de diagnóstico debe reaccionar rápidamente ante las anomalías, y ejecutarse con prontitud en función de interpretar dichas anomalías y, en su caso, tomar las acciones de recuperación oportunas. En estos casos el sistema está continuamente siendo monitorizado y diagnosticado ante la posibilidad de un fallo. En [Cascio et al. , 1999]se
12 2.2. Diagnosis de Sistemas Dinámicos presenta el uso de la diagnosis basada en modelos y el modelado cualitativo para realizar diagnosis a bordo en el campo de la automoción, concretamente en el sistema de alimentación de combustible Common Rail . En [Hutter and Dearden, 2003]se presentan algoritmos cuya eciencia permite realizar diagnosis on-line en sistemas con poca capacidad de cómputo. Según la forma en la que se realicen las tareas que conforman el proceso de diagnosis tendremos: Diagnosis centralizada. Hablamos de diagnosis centralizada cuando las tareas que se realizan durante el proceso de diagnosis se llevan a cabo de forma secuencial, es decir, no se comienza una tarea hasta que no se naliza la precedente. Este es el caso de la mayoría de las propuesta de diagnosis hasta la actualidad. Diagnosis distribuida. En este tipo de diagnosis las tareas que conforman el proceso de diagnosis se realizan en paralelo siempre que sea posible. De esta forma los resultados se obtienen con mayor prontitud, debido al ahorro de tiempo que supone la realización de tareas simultáneamente. Por contra se hace necesario disponer de más de una unidad de procesamiento para la realización de la diagnosis, con lo cual aumenta el coste de la misma. 2.2. Diagnosis de Sistemas Dinámicos Como se ha comentado con anterioridad la diagnosis puede ser aplicada tanto a sistemas estáticos como a sistemas dinámicos. En un primer momento los esfuerzos estuvieron enfocados en la diagnosis de sistemas estáticos, debido a su menor complejidad, y a partir de esas primeras técnicas, desarrolladas para los sistemas estáticos, se extendió su aplicación a los sistemas dinámicos. La característica común a este tipo de sistemas es su comportamiento dinámico, donde el tiempo es un factor muy importante a tener en cuenta, y donde la dinámica de los síntomas puede ser comparable a la del propio proceso, de tal forma que no se detectará de la misma forma una pequeña fuga de un tanque que la obstrucción total de una válvula.
Capítulo 2. Planteamiento del Problema 13 Los sistemas dinámicos en general y los procesos continuos en particular disponen de una serie de restricciones que los hacen diferentes desde el punto de vista de la diagnosis: Es necesario vigilar la evolución temporal del proceso y comprobar su consistencia con el estado, o conjunto de estados, obtenidos a partir de la simulación de los modelos. Los modelos han de incluir controladores en lazo cerrado. La presencia de controladores pueden compensar los fallos, que se manifestarían de forma intermitente. La dinámica de los sistemas los lleva a moverse a estados estacionarios a través de estados transitorios. El deterioro progresivo de un sistema donde no se haya diagnosticado a tiempo un fallo puede provocar fallos posteriores, con lo cual es necesario imponer restricciones temporales en cuanto al tiempo disponible para diagnosticar este tipo de sistemas. De todo lo anterior podemos obtener las siguientes conclusiones: Se necesita dotar al sistema de diagnóstico de capacidades adicionales para la inclusión del tiempo. El diagnóstico es más costoso desde el punto de vista computacional, debido a la complejidad adicional que supone la dinámica del sistema, lo que lleva en ciertos casos a la necesidad de realizar simulaciones temporales. Es muy importante seleccionar los puntos de medida. Los fallos pueden depender temporalmente unos de otros. La diagnosis de un sistema dinámico debe ser una tarea incremental. Consideraremos pues sistemas dinámicos aquéllos cuyo comportamiento depende del tiempo, y en especial a los que tienen estados, donde existe una acumulación de energía o información de estados anteriores que condiciona la respuesta ante los estímulos actuales.
14 2.2. Diagnosis de Sistemas Dinámicos 2.2.1. Diagnosis de sistemas dinámicos basado en estados versus basado en simulación Una de las discusiones más signicativas que se han observado en los últimos años versa sobre si es suciente, para llevar a cabo la diagnosis de los sistemas dinámicos, considerar únicamente los estados del sistema, e ignorar lo que sucede entre ellos, o es mejor realizar la simulación del sistema para tener en cuenta los cambios entre estados. En el primer caso, la diagnosis basada en estados , sólo se razona sobre los estados simples del sistema, sin tener en cuenta los cambios de estado, mientras que en el segundo caso, la diagnosis basada en simulación , el comportamiento del sistema se trata de forma continua, tanto en los estados como en las transiciones entre ellas. La diagnosis de sistemas dinámicos requiere comprobar la consistencia de las observaciones sobre el tiempo de los comportamientos modelados para el sistema. Una solución sencilla es simular incrementalmente el modelo a medida que las observaciones cambian, para predecir los estados sucesores inmediatos (diagnosis basada en la simulación) usada en [Dvorak and Kuipers, 1989]. La diagnosis basada en estados [Dressler, 1996]evita la simulación y genera la diagnosis apoyándose en la consistencia de los estados observados y el modelo solamente. [Malik and Struss, 1996]establecen una condición necesaria y suciente para la equivalencia entre diagnosis basada en estado y simulación sin dar prueba de ello. [Struss, 1997]presenta más tarde que si el sistema se modela con restricciones de estados y CID constraints , que son reglas generales acerca de la continuidad, integración y derivadas, entonces la diagnosis basada en comprobar el estado y la simulación conducen a diagnosis equivalentes. Mas especícamente, puesto que la aproximación basada en estados no usa la relación entre x and dx/dt , y ambas x y dx/dt deberían ser observables para tener bastante redundancia en la tarea de diagnosis. Algunas veces ambas x and dx/dt no son modeladas en el modelo de simulación o no pueden medirse ambas como variables físicas. Ciertos trabajos introducen pseudo-variables para describir el comportamiento dinámico y proporcionar la redundancia suciente para el diagnóstico del sistema dinámico. En la diagnosis basada en estados, la relación entre el paso de tiempo no se considera, por ejemplo, no se calcula dx/dt a partir de x , o si ambas x y dx/dt son conocidas, se ignora la relación entre ellas.
Capítulo 2. Planteamiento del Problema 15 Los defensores de la propuesta basada en estados [Malik and Struss, 1996; Dressler, 1996],arguyen que la simulación numérica no es aplicable si sólo tenemos información parcial o cualitativa del sistema y sus condiciones iniciales. En estos casos la simulación puede llegar a ser muy compleja, debido a la ambigüedad existente en el conjunto de predicciones de comportamiento. En esos casos la diagnosis basada en estados puede alcanzar buenos resultados sin la necesidad de recurrir a la simulación numérica o cualitativa. En concreto en [Malik and Struss, 1996]se presenta una aproximación basada en consistencia y centrada en los estados del sistema para realizar la diagnosis de un sistema dinámico. Otra aproximación tal como la de [Dressler, 1996]evita la simulación y genera candidatos de diagnostico basados en comprobar la consistencia del modelo con los estados observados solamente (como opuesto a los comportamientos observados, o sea a la secuencia de estados), sin embargo falta un análisis formal de sus precondiciones y de sus consecuencias. En [Struss, 1997]se presentan los fundamentos de las diagnosis basada en modelos para sistemas dinámicos. En este trabajo se discuten los fundamentos teóricos y los aspectos prácticos de la aplicación de la diagnosis basada en modelos (particularmente la diagnosis basada en consistencia) para sistemas dinámicos. La mayoría de las aproximaciones presentadas requieren la simulación del sistema a ser diagnosticado. En este trabajo se presentan las condiciones para evitar el paso de la simulación, que es con frecuencia prohibitivo y costoso. Una vez que se tuviese la simulación, habría que realizar una comprobación entre la satisfacción del comportamiento y el esperado en ese instante de tiempo. Esta idea subyace en varias aproximaciones (MIMIC [Dvorak and Kuipers, 1989]) y se mantiene, incluso, cuando la simulación es cualitativa y al haber muchos resultados ambiguos, para identicar el fallo se requiere la simulación de muchos escenarios de fallos. Un trabajo posterior [Panati and Drupé, 2000]presenta unos resultados opuestos a los presentados [Malik and Struss, 1996; Struss, 1997]para el mismo ejemplo, mostrando que la simulación puede ser útil para restringir el uso de posibles diagnósticos. También discute como los resultados de la simulación basada en estados en contextos diferentes no produce los mismos resultados y muestra como se puede razonar a partir de la causalidad del sistema y usando la simulación. No obstante reconoce la mayor eciencia de la aproximación basada en estados, al no tener que
16 2.3. Hipótesis para la solución del problema realizar la búsqueda en el espacio de estados, aunque en [Panati et al. , 2000]se muestra que el uso de dependencias causales en la simulación puede hacer factible dicha búsqueda. 2.3. Hipótesis para la solución del problema Existen un gran variedad de técnicas aplicadas al campo de la diagnosis. Concretamente en la línea que nos ocupa, la diagnosis de sistemas dinámicos, se han presentado una gran variedad de aproximaciones, desde muy distintos puntos de vista. Quizás, el área más profusamente usada ha sida la diagnosis basada en modelos. En el Capítulo 3 se hace una revisión de todas estas aproximaciones. Nuestra solución se presenta como una metodología compuesta de dos fases claramente diferenciadas. La primera de las fases se desarrolla o-line , y es previa al proceso de diagnóstico propiamente dicho. En esta fase se parte de un conjunto de trayectorias generadas por el sistema a diagnosticar. Las trayectorias representan la evolución del sistema en el transitorio en el que se pretende diagnosticar el sistema. Las trayectorias podrán ser generadas mediante manipulación del propio sistema o, si esa opción no es posible, mediante simulaciones de un modelo representativo del sistema. Una vez capturadas, o generadas, dichas trayectorias serán almacenadas en una base de datos que contendrán las trayectorias recogidas junto con una etiqueta que indicará el estado en el que estaba el sistema cuando se generaron (algún fallo concreto o la ausencia de él). Estas trayectorias serán tratadas con objeto de reducir la dimensión de las mismas y añadir nuevos atributos que puedan ser representativos de los fallos que representan las trayectorias. Finalmente se aplicará algún método de clasicación automática que permita descubrir el modelo proposicional inherente a la información suministrada. Posteriormente, el modelo es validado y si se considera adecuado, se implanta como modulo de diagnóstico del sistema. De no considerarse válido el modelo proposicional, se procede a un ajuste de parámetros o una nueva captura de datos hasta conseguir la adecuación requerida.
Capítulo 2. Planteamiento del Problema 17 Sistema Real Modelo del Sistema Base de Datos Etiquetada Base de Datos Transformada Trayectoria + Etiqueta Limpieza y Tratamiento Validación Parámetros IMPLANTACIÓN MODELO PROPOSICIONAL Ajustar Parámetros Figura 2.1: Fase O-line de la metodología general
18 2.3. Hipótesis para la solución del problema Con esto nalizará la fase o-line , que tiene como resultado el modelo proposicional descubierto a partir de las trayectorias proporcionadas. En la gura 2.1 se muestran, de forma general, los pasos de dicha fase. Una vez conseguido el modelo proposicional, la fase on-line de la metodología se desarrolla mientras el sistema está siendo monitorizado, y es la fase de diagnosis propiamente dicha. Para alcanzar el diagnostico, tan sólo hay que evaluar la nueva observación con el modelo proposicional conseguido de la fase previa, tal como muestra la gura 2.2. Figura 2.2: Fase On-line de la metodología general En el capítulo 6 se describe en detalle la solución propuesta.
Capítulo 3 Técnicas de Diagnosis Automática A continuación expondremos las diferentes técnicas que se utilizan a la hora de realizar la diagnosis, según se represente el conocimiento que se tiene del sistema a diagnosticar. Dicha representación proporcionará la relación existente entre los síntomas observados y la diagnosis obtenida dependiendo de la representación utilizada. Diagnóstico Automático Basado en Aprendizaje Automático Basado en Conocimiento Basado en Modelos Basado en Casos Ingeniería de Control Inteligencia Artificial Figura 3.1: Técnicas para la diagnosis automática Desde el punto de vista de cómo podemos conocer la relación entre los síntomas observados y su diagnosis, como se representa en el sistema dicha relación y como se usa dicha representación para diagnosticar fallos; Balakrishnan y Honavar [Balakrishnan and Jonavar, 1998]distinguen las siguientes técnicas de diagnosis: Técnicas basadas en conocimiento. 19
26 3.3. Diagnosis basada en modelos 3.3. Diagnosis basada en modelos La diagnosis basada en modelos razona a partir de un modelo que representa de forma explícita el sistema a diagnosticar. Si el comportamiento de la situación observada no se ajusta a la estimación realizada por el modelo para dicha situación se concluye que hay un fallo, y en un análisis posterior de las diferencias se intenta identicar el componente concreto del fallo. En [Hamscher, 1991; Thomas, 2002] tenemos casos para esta técnica. La mayoría de las aproximaciones aparecidas en la última década para realizar diagnosis se han basado en el uso de modelos (DBM 2 ). Estos modelos se apoyan en el conocimiento del sistema a diagnosticar, que puede estar bien estructurado formalmente y de acuerdo con teorías bien conocidas o puede ser conocido a través de la experiencia de un experto y datos del sistema o proceso. También se presentan algunas veces combinación de ambos tipos de información. Sistema Diagnóstico Conducta Predicha Conducta Observada Modelo Discrepancia Figura 3.3: Metodología de la Diagnosis Basada en Modelos La DBM se basa en la comparación de las observaciones que se tienen sobre el funcionamiento de un dispositivo y las predicciones hechas por un modelo del dispositivo sobre su funcionamiento y se resume en la gura 3.3. Las observaciones indican como se comporta el dispositivo, mientras que el modelo nos dice como debería hacerlo si funcionase normalmente. Por tanto si existe una discrepancia entre las observaciones y las predicciones podemos concluir que el dispositivo no está trabajando correctamente. La información disponible para realizar las predicciones en la DBM será: Una descripción local del comportamiento correcto de cada componente. 2 Diagnosis Basada en Modelos
Capítulo 3. Técnicas de Diagnosis Automática 27 Una descripción de la estructura interna del sistema, es decir, la conexión existente entre cada componente del sistema. Un conjunto de observaciones, generalmente medidas. Cuando se detecta un síntoma, esto es, se produce una discrepancia entre lo observado y lo predicho, se deduce que alguno de los componentes involucrados en la predicción del valor discrepante de las observaciones funciona de forma incorrecta. La DBM es independiente del dispositivo, por lo que no es necesaria la acumulación de experiencia sobre un sistema para poder diagnosticarlo. La diagnosis mediante esta técnica se basa, pues, en un proceso iterativo consistente en: a. Generación de la hipótesis de diagnóstico. En este paso se enuncia el conjunto de componentes sospechosos en función de las discrepancias observadas. b. Comprobación de la hipótesis. Consistente en encontrar los candidatos a partir de los sospechosos. c. Discriminación de la hipótesis. Donde renaremos el conjunto de candidatos si tras la fase anterior existe más de uno. En el área de la Inteligencia Articial un trabajo pionero en este campo fue presentado con objeto de diagnosticar sistemas de componentes basándose en la estructura y su comportamiento [Davis, 1984]. Las primeras implementaciones para llevar a cabo diagnosis fueron DART [Genesereth, 1984]y GDE [DeKleer and Williams, 1987], que utilizaban diferentes mecanismos de inferencia para detectar los posibles fallos. Las formalizaciones de la diagnosis se presentan por [Reiter, 1987; de Kleer et al. , 1992], donde se propone una teoría general para el problema de explicar las discrepancias entre los comportamientos observados y correctos de los mecanismos. Apoyándose en ellas, la mayoría de las aproximaciones de diagnosis basadas en modelos para componentes caracterizan la diagnosis de un sistema como una colección de conjuntos mínimos de componentes fallando que explican los comportamientos observados (síntomas). De esto se deriva la importancia de disponer de un buen modelo para hacer diagnosis basada en modelos. Algunos métodos de diagnóstico usan modelos que requieren que los ingenieros desarrollen modelos de fallos además de desarrollar también el modelo de operación
28 3.3. Diagnosis basada en modelos normal . Construir modelos de fallos en un sistema es útil cuando los fallos son bien conocidos y fáciles de modelar, pero ello limita el sistema de diagnosis a fallos conocidos y no permite ningún tipo de error en el modelado. Una revisión de las aproximaciones acerca de la automatización de las tareas de diagnosis se puede encontrar en [Dressler and Struss, 1996]y para una discusión de las aplicaciones de la diagnosis basada en modelos se puede consultar [Console and Dressler, 1999]. La generalización de la diagnosis basada en la consistencia se ha propuesto para cubrir sistemas que contienen procesos y que cambian su estructura dinámicamente en [Heller and Struss, 2001]. Los sistemas de diagnostico basados en modelos han llegado a ser claramente exitosos y empiezan a aplicarse a problemas industriales. Muchos, si no la mayoría pueden ser considerados como una variante de General Diagnosis Engine(GDE) siguiendo el principio de diagnosis basada en consistencia [Dressler and Struss, 1996]. No hay que perder de vista de todas formas que razonar en base a un modelo tiene la limitación de que el modelo no es el dispositivo o el sistema, sino una abstracción del mismo, por lo que todos los modelos son necesariamente erróneos, debido a que pueden perder propiedades que sean básicas para el sistema. Por otra parte los modelos estarán condicionados según el n para el que sean construidos. Otra desventaja de esta técnica es que no es aplicable donde no se tenga un modelo del sistema a diagnosticar. En esos casos es más aconsejable recurrir a la diagnosis basada en casos o a las técnicas de aprendizaje automático. En [Travé- Massuyes and Milne, 1998]podemos encontrar los problemas con los que se encuentran estas técnicas al ser aplicados a problemas industriales. 3.3.1. Comunidades FDI y DX Desde hace más de una década se ha manifestado un interés creciente en la comunidad cientíca por la diagnosis de sistemas físicos. Dos comunidades cientí- cas diferentes han desarrollado dos aproximaciones diferentes. Por una parte la comunidad bajo el nombre de Identicación y Detección de Fallos (FDI) que utiliza técnicas procedentes de la teoría de control y análisis estadístico. De entre ellas pueden destacarse la estimación de estados [Frank, 1987], estimación de parámetros [Isermann, 1993]y la técnica de redundancia analítica [Gertler, 1991]. En los
Capítulo 3. Técnicas de Diagnosis Automática 29 últimos años han aparecido diferentes monografías sobre el tema [Frank., 1996], [Isermann, 1997]y[Patton et al. , 2000]. En esta última cita se reejan algunos de los trabajos desarrollados por la otra comunidad cientíca, que surgió más recientemente y que se basa principalmente en técnicas derivadas de la Inteligencia Articial, llamada DX. Dentro de esta comunidad (DX) y principalmente en la década de los 80 se produce una evolución de los sistemas expertos que hasta entonces llevaban a cabo la diagnosis de los sistemas a una nueva aproximación llamada diagnosis basada en modelos (DBM), [Reiter, 1987],[de Kleer et al. , 1992]. El motor de diagnosis general, GDE [DeKleer and Williams, 1987]determinó un marco de trabajo para la diagnosis, que subsecuentemente inuenciará casi todos los trabajos en el campo de la diagnosis basada en modelos. El dominio de aplicación principal de este tipo de diagnosis era sobre sistemas estáticos, esto es, sistemas que no evolucionaban en el tiempo. Los primeros trabajos que aparecen sobre sistemas que evolucionan en el tiempo extienden los algoritmos de los sistemas estáticos (GDE) y consideran QSIM [Kuipers, 1986]como herramienta para detectar los conictos en estos sistemas [Ng, 1990; 1991]. En trabajos posteriores se ha seguido utilizando QSIM y se ha mostrado [Dressler and Freitag, 1994]como ATMS 3 sirve como un elemento para tratar computacionalmente etiquetas temporales y permite integrarlas con las etiquetas lógicas. También se ha utilizado el conocimiento de las consecuencias de los diferentes modos de comportamiento de los componentes y un modelo de evolución de tales modos [Console et al. , 1994]. Puede encontrarse una caracterización general para la diagnosis basada en modelos teniendo en cuenta el tiempo en [Brusoni et al. , 1998]. Otras aproximaciones han usado los grafos causales para llevar a cabo la diagnosis [Bousson and Trave-Massuyes, 1992]y los grafos causales temporales [Mosterman, 1997]. Para una revisión de las técnicas desarrolladas en el área de la Inteligencia Articial puede consultarse [Price, 1999]. Las tendencias sobre la diagnosis basada en modelos y los retos en el futuro se recogen en [Console and Dressler, 1999]. El grupo IMALIA pretende aunar la terminología de ambos enfoques y encontrar las similitudes y complementariedades de cada uno. 3 Sistemas de mantenimiento de la razón
30 3.3. Diagnosis basada en modelos 3.3.2. El problema del modelado Para experimentación, análisis o diseño, las ciencias y la ingeniería siempre han necesitado representar el mundo real a través de modelos, que pueden ser usados como sustitutos del sistema físico con respecto a las características relevantes para la tarea a realizar. Un sistema físico puede ser visto desde distintas perspectivas según los fenómenos que tengan lugar en él. En particular debemos distinguir entre modelos estáticos y dinámicos. Si un sistema físico es considerado un conjunto de variables exógenas y un conjunto de variables endógenas , la evolución del estado del sistema, dado por los valores de las variables endógenas , es condicionado por el valor de las variables exógenas en el tiempo. Los modelos estáticos proporcionan una imagen de los estados de equilibrio del sistema, mientras que los modelos dinámicos dan también una descripción de los estados transitorios entre dos estados de equilibrio. El primer concepto clave de la Diagnosis Basada en Modelos es que el conocimiento acerca de la estructura interna y el comportamiento correcto de un 'artefacto' diseñado puede ser usada para diagnosticar dicho artefacto. La tarea básica de la diagnosis es, así pues, comparar el comportamiento observado del dispositivo con el comportamiento predicho, derivado del modelo del dispositivo, y detectar discrepancias entre ellos. Bajo la asunción de que el modelo es correcto, todas las discrepancias entre la observación y la predicción se toman como fallos del dispositivo. La Diagnosis Basada en Modelos permite realizar la diagnosis de esta forma basándose exclusivamente en: 1. La descripción de la estructura interna del dispositivo, usualmente una lista de los componentes usados y sus conexiones 2. Los modelos de comportamiento correcto de los componentes del dispositivo. 3. Las observaciones Esta aproximación comenzó con los programas INTER [Kleer, 1976]y SOPHIE [Brown et al. , 1982]para el diagnóstico de circuitos electrónicos y DART [Genesereth, 1982]y HT [Davis, 1990]para la diagnosis de circuitos digitales.
Capítulo 3. Técnicas de Diagnosis Automática 31 El segundo concepto clave de la Diagnosis Basada en Modelos se reere a las tres tareas fundamentales de la diagnosis: Generación de hipótesis, Comprobación de hipótesis y Discriminación de hipótesis. Reiter [Reiter, 1987]ofrece una teoría general de diagnosis basada en fundamentos lógicos: la diagnosis se dene como un conjunto de componentes, de tal forma que, la asunción de que uno de los componentes está fallando, junto con la asunción de que el resto de los componentes del sistema están funcionando correctamente, es consistente con la descripción del sistema y las observaciones. Posteriores trabajos incorporan también modelos de fallo, como por ejemplo SHERLOCK [Kleer and B. C. Williams, ]. El tercer concepto clave de la Diagnosis Basada en Modelos es que el modelado es la parte más dura para la DBM. La mayoría de los trabajos para formalizar el proceso de diagnosis y construir algoritmos de diagnosis asumen que se ha dado de antemano la descripción del sistema, tanto estructural como de comportamien- to. Cuando se empiezan a aplicar estas técnicas a problemas de la vida real es cuando queda evidente que el modelado es la parte más dura. Es evidente que el Razonamiento Cualitativo puede ofrecer conceptos y técnicas para abordar la tarea del modelado, lo cual explica los fuertes intercambios existentes entre ambas comunidades. 3.3.3. Niveles de abstracción en el modelado Dependiendo de los aspectos del sistema a diagnosticar el modelado del mismo puede llevarse a cabo mediante la descripción de diferentes aspectos del mismo, en función de la información que quiera ser representada y que resulte útil a la hora de abordar la tarea de diagnóstico. A continuación presentamos las abstracciones más habituales: Modelado según la estructura y la función. Por estructura entendemos la información acerca de las interconexiones de los elementos que conforman el sistema a modelar. Dicho de otra forma es la información que quedaría al eliminar todas las informaciones textuales de un esquema. Hay dos formas diferentes de organizar dicha información, la funcional y la física. La información funcional de un sistema nos proporciona la organización del sistema de acuerdo a como sus diferentes componentes interactúan, mientras que la física nos indica como están agrupados.
32 3.3. Diagnosis basada en modelos Modelado según el comportamiento. Por comportamiento entendemos la descripción de caja negra de un componente del sistema a modelar, es decir, como la información sale del componente en relación con la información que ha entrado en el mismo. Las técnicas para describir el comportamiento han sido muy variadas, y van desde simples reglas para mapear las entradas y salidas hasta las redes de Petri. Modelado híbrido. En este tipo de modelado se tienen en cuenta no solamente uno de los aspectos del sistema a modelar como los mencionados anteriormente, sino todos ellos o al menos más de uno. Así en [Davis, 1984]se presenta una forma de razonamiento enfocada a la diagnosis de circuitos electrónicos basada en la estructura y comportamiento de los mismos. 3.3.4. Relaciones Causa-Efecto Existen dos aproximaciones para representar las relaciones dentro de un modelo. La primera es la aproximación no causal, porque no es necesario representar la dirección especíca de la causalidad cuando se modela el sistema. La segunda es la aproximación causal, porque se basa en un modelo causal explícito, generalmente soportado por un grafo orientado [Travé-Massuyes et al. , 1993]. No obstante la denición de causalidad relacionado con los fenómenos físicos no parece estar muy clara, aunque la opinión general si parece estar de acuerdo en las tres propiedades siguientes: orden temporal, localidad y necesidad. [Kleer, 1990; Kleer and Brown, 1990b]. No causales Normalmente los ingenieros describen el comportamiento de un sistema en modo estacionario con un modelo algebraico simplicado de la forma F(X) = 0 , donde X es el vector de variables del modelo. Es posible obtener el comportamiento lineal del sistema en la cercanía de un punto de operación nominal X0 : [dF dX ]x0xdX = 0 (3.1) Los parámetros de este modelo lineal aparecen como derivadas parciales de F.
Capítulo 3. Técnicas de Diagnosis Automática 33 Causales La representación actual para representar la causalidad es un grafo orientado, llamado Grafo Causal, donde los nodos representan las variables del sistema y los arcos dirigidos las relaciones funcionales entre las variables. El análisis del sistema consiste en: 1. Identicar las variables relevantes para describir el sistema. 2. Representar sus dependencias causa-efecto como un grafo. 3. Identicar las correspondientes relaciones funcionales. 4. Propagar las inuencias a través del grafo. En la aproximación estática en contra de lo que ocurre en la dinámica, se asume que no hay retraso en la propagación de las inuencias. Híbridos La tarea de supervisión de un proceso físico que no es totalmente conocido signica tener que llevar a cabo distintas tareas que se solapan, como pueden ser predecir y rastrear el comportamiento del proceso, elegir las acciones correctivas adecuadas cuando el proceso no tiene un comportamiento correcto, estimar los comportamientos de las variables no medibles, etc. El sistema CA-EN [Bousson, 1993; Bousson and Travé-Massuyes, 1993], intenta mimetizar a un operador humano que realice dichas tareas, especialmente aquellas que son por lo general muy tediosas. CA-EN usa como base de tiempo un paso lógico jo. Dicho paso de tiempo es constante y se establece de acuerdo con la velocidad del proceso. Entre otras cosas esta escala temporal permite evaluar fácilmente la duración de los estados y los instantes de los eventos y ser síncronos con las observaciones provenientes, en tiempo real, del sistema [TravéMassuyes, 1992]. Dos aplicaciones de CA-EN aplicados al campo de la diagnosis son: BIOTECH [Steyer, 1991]Es un sistema experto en tiempo real aplicado a la monitorización y diagnosis de un proceso de fermentación. El sistema puede evaluar el estado del proceso desde el punto de vista biológico, detectando, de esta forma, comportamientos anormales y proporcionando avisos permanentes al operador sobre las operaciones a realizar para solucionar la situación crítica.
34 3.3. Diagnosis basada en modelos TIGER [Milne, 1992; Milne and Travé-Massuyes, 1993].] Tiene como propósito monitorizar y diagnosticar el funcionamiento de una turbina de gas. La herramienta usada es una versión más reciente de predictor CA-EN que la usada en BIOTECH, y que incluye más razonamiento numérico. 3.3.5. Representación del espacio de valores Modelado Cuantitativo En estos modelos el sistema es descrito mediante ecuaciones algebraicas que permiten la manipulación numérica del mismo. Estos modelos han sido y siguen siendo usados muy prolícamente dentro de la comunidad FDI, donde la mayoría de sus aproximaciones se basan en este tipo de modelos, como las ya comentadas estimación de estados o estimación de parámetros . Los modelos son ecuaciones diferenciales que describen las dependencias entre las señales de forma cuantitativa, como el modelo del espacio de estados: x=f(x, u, t) (3.2) y=g(x, u, t) (3.3) Los fallos son interpretados como señales de entrada externa o desviación de los parámetros. La tarea de diagnosis se solventa a través de la estimación del estado real o la estimación de los valores reales de los parámetros. Estas aproximaciones son útiles si las ecuaciones diferenciales 3.2 y 3.3 son conocidas y las señales son medidas cuantitativamente, es decir, sus valores son valores numéricos exactos El uso de los modelos cuantitativos, aplicados a la diagnosis, tiene una serie de inconvenientes, pues cuando son usados existe una complejidad del modelado y simulación, además de que si hay imprecisión o incertidumbre se necesita redenir el concepto de consistencia. Pero sin embargo, estos modelos pueden evitar el problema del bucle realimentado [Dressler and Struss, 1994]. Modelado Cualitativo La simulación cualitativa persigue derivar descripciones cualitativas del comportamiento a través del tiempo de un sistema a partir de un modelo general del
Capítulo 3. Técnicas de Diagnosis Automática 35 sistema. Aunque los algoritmos dieren en la forma de representar el comportamiento, todos se basan en las siguientes ideas: El dominio de las variables que representan parámetros físicos pueden ser divididos en un pequeño número de marcas e intervalos entre ellas que representan las distinciones cualitativas reales de la magnitud de la variable. Conocer la dirección de cambio de la variable, junto a su magnitud cualitativa, es con frecuencia suciente para determinar su evolución cualitativa. Para restringir el comportamiento de las variables es, a menudo, suciente con conocer algunas de sus propiedades, como puede ser la monotonía. El tiempo no es cuanticado a priori. Los puntos de tiempo vienen determinados por 'acontecimientos signicativos', como puede ser que una variable pase una de las marcas. Históricamente hay tres aproximaciones principales al modelado cualitativo y razonamiento sobre sistemas dinámicos: ENVISION [Kleer and Brown, 1990a] . Creado por De Kleer y Brown es la aproximación basada en componentes. La idea es desarrollar una versión cualitativa del campo de los sistemas dinámicos donde una situación física es vista como un dispositivo compuesto por componentes individuales conectados entre ellos. Se pretende desarrollar una librería de modelos de componentes, genéricas para un dominio dado, cada una con una descripción de comportamiento. Se acuña el termino envisioning para describir el proceso de inferir la descripción del comportamiento de un sistema en términos de sus estados permitidos, el valor de sus variables y la dirección de cambio de dichas variables. QSIM (Qualitative Simulation) [Kuipers, 1990] . Desarrollado por Kuipers es la aproximación basada en restricciones. El modelo cualitativo del sistema consiste en las variables que componen el sistema en un nivel dado de abstracción y las restricciones que relacionan las variables. Las principales características son la provisión de representación cualitativa para las cantidades, un algoritmo eciente de simulación cualitativa, un método para
42 3.3. Diagnosis basada en modelos Se han aplicado las redes de Bayes a la construcción de sistemas expertos de diagnosis en dominios donde es crucial un manejo coherente de la incertidumbre sobre el diagnóstico. Uno de los mayores factores de motivación para esta aplicación es que la extensión de los sistemas basados en reglas al ocuparse de la incertidumbre, como los factores de certeza, no puede dar una semántica clara a menos que se impongan limitaciones muy fuertes en la estructura de la base de conocimiento [Horvitz and Heckerman, 1986]. De la misma forma que los sistemas expertos basados en reglas, la mayoría de los sistemas de diagnóstico basado en redes de Bayes fueron construidos a mano por los expertos. En el campo de la diagnosis médica se han construido varias aplicaciones signicativas, por ejemplo [Heckerman et al. , 1992]. En [Srinivas, 1994; Darwiche, 1995]se usa la sinergia entre las técnicas de redes de Bayes y los métodos usados en diagnosis basada en modelos probabilísticos . Razonamiento basado en abducción La formalización de diagnosis usando modelos de dominio causal se conoce generalmente como diagnosis abductiva. Como típico ejemplo de este tipo de diagnosis tenemos a [Console et al. , 1989; Console and Torasso, 1991]en cuyas teorías de diagnosis abductiva el comportamiento normal o anormal de un sistema es modelado en términos de conocimiento causal con estados normales o anormales y resultados predichos. En esta teoría se distinguen dos tipos de conocimiento causal. En el primer tipo de conocimiento causal se asume que, cuando está presente un conjunto de fallos, deben estar presentes también todos los resultados asociados. A esta noción de causalidad se le llama causalidad fuerte . El segundo tipo de conocimiento causal, los resultados relacionados con la causalidad no necesariamente deben estar presentes cuando se presentan sus fallos asociados. Esta noción menos estricta de causalidad se conoce como causalidad débil , y representa las relaciones de dudosa imprecisión entre la causa y el efecto. Las relaciones de causalidad fuerte entre fallos, y entre fallos y resultados observables se denotan en la teoría de la diagnosis abductiva por una implicación lógica de la forma: d1∧.... ∧dn→d y
Capítulo 3. Técnicas de Diagnosis Automática 43 d1∧.... ∧dn→f que expresan que la ocurrencia combinada de los fallos d1, ..., dn provoca el fallo d y el resultado f . Los fallos d y los resultados f son representados como predicados lógicos. Una especicación causal C= (∆,Φ, R) se dene como un conjunto de literales de fallos ∆ , literales de resultados Φ y una colección de implicaciones lógicas R relacionando literales de fallos y de resultados de la forma que se ha visto anteriormente. Las implicaciones lógicas R son conocidas normalmente como axiomas de anormalidad , debido a que representan sólo el conocimiento causal de la anormalidad. Sea A= (C, E) un problema de diagnosis abductiva, donde C son implicaciones causales y E resultados observados, entonces el conjunto de fallos H⊆∆ se dice que es una diagnosis de A si y sólo si: 1. ∀f∈E:R∪H²f ( Condición de cobertura ) y 2. ∀f∈Ec:R∪H2¬f ( Condición de consistencia ) donde Ec , el conjunto de resultados observables se asume que está ausente, se dene en términos de E como sigue: Ec={¬f∈Φ|f∈/ E , f es un literal positivo } Esto signica que una diagnosis H debe predecir todos los resultados observados, pero no puede predecir los resultados que se asume que están ausentes. El correspondiente concepto de diagnosis se llama el concepto de diagnosis de causalidad fuerte (SC) y se dene como sigue: SCΣ,%|H(E) = (H si %|H(H) = E en otro caso u El concepto diagnosis que corresponde a la diagnosis abductiva con relaciones de causalidad débil se conoce como el concepto de diagnosis de causalidad débil y se denota por WC . Se dene como sigue: WCΣ,%|H(E) = (H si %|H(H)⊇E en otro caso u
44 3.4. Diagnosis mediante Aprendizaje Automático La diagnosis de causalidad débil considera todos los resultados observados, aunque no todos los resultados observables necesitan ser observados. La diagnosis abductiva ha sido utilizada en varios desarrollos como pueden ser [Poole et al. , 1987; Konolige, 1994; Poole, 1994]. 3.4. Diagnosis mediante Aprendizaje Automático Los métodos de aprendizaje y reconocimiento de patrones son muy útiles cuando se pretenden diagnosticar sistemas donde no se dispone del conocimiento estructural para relacionar los síntomas con los fallos. Desde este punto de vista, la tarea de diagnosis se entiende como la capacidad de diferenciar entre nf fallos diferentes Fj, j ∈ {1, ..., nf} , usando ns síntomas si, i ∈ {1, ..., ns} . Los fallos son representados mediante un vector de fallos F= [F1F2....Fn] y los síntomas mediante un vector de síntomas s= [s1s2....sns]T Los métodos de aprendizaje determinan experimentalmente mediante el entrenamiento previo, el fallo Fj en base al vector de síntomas de referencia sref . La comparación posterior con los síntomas observados s , determinará el fallo mediante la clasicación obtenida, tal como se muestra en la gura 3.6 Con estas técnicas, la diagnosis se consigue mediante la comparación de la evolución del sistema a diagnosticar con el conocimiento aprendido que se tiene del mismo, evaluando de esta forma el comportamiento del sistema. Para la adquisición del conocimiento se suele recurrir a experiencias previas almacenadas o a la simulación del comportamiento del sistema a diagnosticar. Dicho conocimiento puede dar lugar a un modelo explícito o no. Un ejemplo del primer caso es el aprendizaje simbólico. Como representación del segundo tenemos las técnicas con Redes Neuronales Articiales. Una de las grandes ventajas de las técnicas de Aprendizaje Automático es que evitan los problemas relacionados con el desarrollo de un modelo explícito de conocimiento o la obtención de algún tipo de modelo, requeridos por las aproximaciones basadas en conocimiento o basadas en casos, respectivamente. Por el contrario su gran inconveniente radica en la necesidad de un conjunto de datos de entrenamiento, normalmente extenso, que no suele estar disponible en los sistemas reales, por lo que es necesario acudir, con excesiva frecuencia, a simulaciones de los
Capítulo 3. Técnicas de Diagnosis Automática 45 Figura 3.6: Diagnosis mediante clasicación automática mismos [Balakrishnan and Jonavar, 1998]. Otra de las desventajas que presentan estos sistemas aplicados a la diagnosis es la imposibilidad de reconocer situaciones para los que no han sido entrenados. A continuación se revisarán las técnicas más habitualmente usadas para realizar diagnosis mediante el uso de aprendizaje automático. 3.4.1. Redes Neuronales Las redes neuronales realizan un mapeado no lineal entre las entradas y las salidas, consistente en interconectar neuronas distribuidas en capas. Las capas se conectan de tal forma, que las señales de las capas de entrada se propagan a través de la red. El comportamiento no lineal de una red neuronal viene determinado por la elección en la topología de la red, y el peso de conexión entre las neuronas. Las redes neuronales fueron los primeros sistemas de aprendizaje aplicados a la diagnosis, y su campo de aplicación es muy amplio, así como el tipo de red empleada para llevarla a cabo. De esta manera en [Pacheco et al. , 2001]podemos
46 3.4. Diagnosis mediante Aprendizaje Automático encontrar una red de tipo perceptrón multicapa para llevar a cabo la detección de fallos en los robots de soldadura de una factoría de automóviles o en [Saludes et al. , 2001]se usa una red de Kohonen o red Self Organising Map (SOM) para la detección de fallos en un grupo hidroeléctrico. En [Lennox et al. , 1998]se aplican las redes neuronales para capturar las características no lineales del proceso de vitricación que evita la perdida de líquido y proporciona un medio de almacenamiento seguro. El modelo obtenido por la red neuronal es capaz de detectar también el fallo inminente del recipiente usado en el mismo proceso de vitricación. En [Fuente, 2001]se exponen tres formas distintas de aplicar las Redes Neuronales Articiales al campo de la detección y diagnóstico de fallos. En primer lugar la red neuronal es empleada para identicar un modelo no lineal de una planta a partir de los datos de entrada-salida, usando posteriormente dicho modelo para la generación de residuos y la matriz de incidencias, usando de esta forma técnicas tradicionales de la comunidad FDI para llevar a cabo la diagnosis. En segundo lugar las redes neuronales son usadas como clasicador de información, de tal forma que a partir de los datos medidos del proceso se entrena la red para clasicar y diferenciar patrones de operación normales de la planta de patrones de operación con fallo. Para ello usa un ejemplo sobre un reactor químico donde induce los fallos que posteriormente se quieren diagnosticar para que la red neuronal aprenda a clasicarlos. La tercera aplicación que realiza de las redes neuronales en el campo de la detección y diagnóstico de fallos es estudiar el contenido en frecuencias de una señal representativa del proceso, que tiene información tanto de los fallos como de las perturbaciones y el ruido que afectan al proceso. Así pues la red debe aprender a clasicar patrones de fallos de los patrones de perturbación e intentar encontrar un modelo robusto. En [Samanta and Al-Balushi, 2003]se presenta una red neuronal para diagnosticar fallos en los cojinetes de elementos rodantes. Para ello se utiliza como entrada de la red la señal de vibración a través del tiempo, tanto para rodamientos defectuosos como válidos. En [Yang et al. , 2004]se usa una red neuronal para la diagnosis de fallos en motores eléctricos. En este caso se combinan las redes ART con las de Kohonen para conseguir el diagnóstico. Sin embargo, en [Kowalski and Orlowska-Kowalska, 2003]se combina el uso de un perceptrón multicapa con
Capítulo 3. Técnicas de Diagnosis Automática 47 una red SOM para alcanzar el diagnóstico en motores de inducción para fallos del estator, el rotor y los rodamientos. En [Vemuri and Polycarpou, 2004]se plantea el uso de una red neuronal para diagnosticar fallos en robots manipuladores y en [Power and Bahri, 2004]se describe un marco de diagnóstico y supervisión de fallos usando redes neuronales. Dicho marco es usado para implementar un sistema de detección de fallos que es capaz de determinar la localización exacta de los fallos y diagnosticarlos en una planta piloto. Esto son tan sólo algunos ejemplos de la diversidad de redes neuronales utilizadas en los muy diversos ámbitos del diagnóstico automático. Un análisis exhaustivo revelaría cientos de trabajos y aplicaciones que usan las redes neuronales para el diagnóstico, por sí mismas o en conjunción de otras técnicas. 3.4.2. Árboles de decisión Los árboles de decisión son modelos de clasicación secuencial que se construyen mediante la partición de la muestra inicial en varios subconjuntos descendientes a través de algún test lógico, conectándose los distintos nodos mediante ramas. El proceso de partición continúa hasta que se cumple una determinada condición de parada, dando lugar a un conjunto de nodos terminales (hojas). Además aprenden modelos sobre una única tabla de datos y que no establecen relaciones entre más de una la de la tabla a la vez ni sobre más de un atributo a la vez. A los modelos así generados se les conoce como modelos proposicionales [Hernández Orallo et al. , 2004]. En [Cascio et al. , 1999]se presenta un caso de aplicación de aprendizaje supervisado usando árboles de decisión aplicado a la diagnosis a bordo del sistema de inyección de combustible Common-Rail de un automóvil. La justicación expuesta para el uso de los árboles de decisión se fundamenta en que para la diagnosis on-board es mucho más eciente usar este tipo de tecnologías, que pueden ser fácilmente implementadas con pocas necesidades de memoria y cuyo tiempo de computación es muy bajo. En [Chen et al. , 2004]se usan los árboles de decisión para diagnosticar fallos en servidores de internet. Se recogen las propiedades de cada petición y se generan los árboles de decisión en base a los datos recogidos para localizar los fallos. El estudio
48 3.4. Diagnosis mediante Aprendizaje Automático presentado es evaluado comprobando peticiones del servidor eBay, demostrando la viabilidad de la técnica. En [Lee, 2005]se utilizan los árboles de decisión para diagnosticar el estado de un motor de inducción partiendo de las señales de vibración del motor. Estas señales de vibración son también la base para la aplicación de técnicas de aprendizaje en el diagnóstico de fallos en turbinas de vapor en [Zhao et al. , 2005] Los árboles de decisión han sido también ampliamente usados en la diagnosis médica, donde la cantidad de datos disponibles hace que las técnicas de aprendizaje sean especialmente atractivas. Así en [Vlahou et al. , 2003]se usa el algoritmo de clasicación comercial biomarker patterns software (BPS), que está basado en CART 5 para diagnosticar el cáncer de ovario, y en [Yahui et al. , 2007]se usan para la diagnosis del cáncer gástrico. 3.4.3. Máquinas de Soporte Vectorial Las máquinas de soporte vectorial [Vapnik, 1998]han demostrado ser una herramienta muy efectiva cuando se aplica a problemas de reconocimiento de patrones. La idea fundamental es encontrar un hiperplano que separe las clases del conjunto de entrenamiento. Para ello, aumentan la dimensionalidad del conjunto de entrada mediante una función núcleo que permite encontrar un discriminante lineal en el espacio dimensional ampliado. En los últimos años, han venido siendo ampliamente usadas en diferentes ámbitos, debido a su robustez y abilidad. En [He and Shi, 2002]se demuestra que las máquinas de soporte vectorial producen resultados más precisos que las redes neuronales cuando son aplicados a problemas de diagnóstico de fallos en válvulas de bombas recíprocas usando datos de vibración. Se usan transformaciones wavelet para preprocesar los datos de vibración, extraer información temporal y de frecuencia, y entonces se usan las SVM para clasicar los fallos. En [Ge et al. , 2004]también se compara el uso de las SVM con las redes neuronales. En este caso, la SVM se usa para la diagnosis de fallos en las operaciones de estampado de las planchas de metal. Demuestra mejores resultados, incluso con un conjunto de entrenamiento menor. 5 un conocido algoritmo para la construcción de árboles de decisión [Breiman et al. , 1984]
Capítulo 3. Técnicas de Diagnosis Automática 49 En [Saunders and Gammerman, 2000]se aplican las SVM a la diagnosis y reparación automática. Para ello utiliza los registros de logs de los entornos de manufacturación. Estos registros se usan para diversas tareas, como asistencia al control de stock y monitorización y mejora de los procesos productivos. Estos registros históricos son usados en este trabajo para reconocimiento de patrones que permitan determinar fallos y ayudar en la reparación. En [Ge et al. , 2004]se usan las SVM para diagnosticar los fallos en las soldaduras de planchas de metal. Los resultados obtenidos son comparados con los conseguidos por una red neuronal, mostrándose más efectiva la SVM incluso con menor número de casos de entrenamiento. En [Yuan and Chu, 2006]se usan las SVM para diagnosticar los fallos del rotor de una turbo-bomba. En este trabajo, se presenta un método para clasicar múltiples clases usando una clasicación uno contra todos y construyendo un árbol de clasicación binario compuesto por múltiples clasicadores binarios. 3.4.4. Otras técnicas Además de las técnicas de aprendizaje anteriormente mencionadas, existen otras técnicas de aprendizaje que, aunque en menor medida, también son aplicadas a la diagnosis. Además, se han publicado multitud de trabajos donde no sólo se recurre a una técnica concreta, sino a la combinación de varias de ellas. A modo de ejemplo, podemos citar algunos de estos trabajos. En [Simón et al. , 2001]podemos encontrar técnicas conexionistas combinadas con lógica borrosa y sistemas basados en conocimiento para llevar a cabo la diagnosis del glaucoma. Esta técnica transforma los parámetros que usa el oftalmólogo para llevar a cabo su diagnóstico en conjuntos borrosos, y recoge la información de uno de ellos, el campo visual, a partir de un sistema de clasicación basada en redes neuronales articiales. Todo este conocimiento se representa nalmente mediante hechos y reglas de producción. En [Aguado and Aguilar, 1999]encontramos un método de clasicación de autoaprendizaje, que trabaja con información cuantitativa y cualitativa que puede funcionar tanto en modo supervisado como no supervisado, aplicado a dos ejemplos, uno sobre datos reales de una planta piloto de dos tanques de agua interconectados, y el otro sobre un modelo que simula el comportamiento de una red
50 3.5. Problemas abiertos de comunicaciones. Este algoritmo está basado en el poder de generalización de la lógica borrosa [Zadeh, 1965]y la capacidad de interpolación de las conectivas lógicas híbridas [Piera, 1987]. En [S.O.T. Ogaji and Prober, 2005]se usa también la lógica borrosa para diagnosticar fallos en turbinas de gas. Los sistemas neuro-borrosos representan un conjunto de reglas borrosas puestas bajo la forma de una red neuronal con el objetivo de hacer uso del aprendizaje, adaptación y posibilidades de paralelismo ofrecidas por las redes neuronales. En [Calado et al. , 2001]se presenta una propuesta de uso de los sistemas neuroborrosos para la diagnosis de sistemas dinámicos. Las técnicas de combinación de clasicadores como el Boosting , han sido también aplicadas al campo de la diagnosis. Por ejemplo, en [Rodriguez and Alonso, 2002]se hace un estudio de la viabilidad de dichas técnicas. Para diagnosticar una planta generadora de potencia, en [Garcez et al. , 1997] se usa una extensión de C-IL2P que permite la implementación de programas lógicos en redes neuronales. Dicha extensión, posibilita que C-IL2P sea aplicable a problemas donde el conocimiento de fondo se representa en forma lógica. 3.5. Problemas abiertos A pesar de la diversidad de técnicas utilizadas y los diferentes enfoques que se aplican al campo de la diagnosis, existen aún una serie de problemas que no están totalmente resueltos o presentan un amplio campo de discusión. Entre ellos destacaremos los siguientes: La capacidad de aplicación de estas técnicas a sistemas más grandes o más complejos. Aunque muchas de las técnicas presentadas son novedosas y solucionan elegantemente el problema que plantean, no es menos cierto que en bastantes ocasiones dichas técnicas sólo han sido probadas con modelos o en pequeñas aplicaciones, sin tener en cuenta el problema que conllevaría trasladar dichas aproximaciones a sistemas más grandes y complejos, y sobre todo a problemas reales e industriales. El modelado del sistema. En cuanto al enfoque más prolícamente usado en el campo de la diagnosis, la Diagnosis Basada en Modelos, todas las propuestas se basan en la existencia de un modelo previo, pero nadie se plantea el
Capítulo 3. Técnicas de Diagnosis Automática 51 problema del modelado del sistema como una de las tareas más importantes y fundamentales en este tipo de aplicaciones. De hecho deberíamos seleccionar el modelo de acuerdo al costo computacional y exactitud requeridos según el tipo de sistema a diagnosticar. La dinámica de los fallos. Los fallos pueden cambiar dinámicamente, y nosotros podemos encarar el problema de modelar fallos intermitentes o aprovecharnos de la suposición de que no existen fallos intermitentes. Un fallo intermitente puede causar también una desviación permanente en el comportamiento del sistema donde un fallo permanente crearía síntomas sólo ocasionalmente. Por otra parte asumir la monotonía de un fallo incipiente supone una simplicación que no siempre nos podemos permitir. Diagnosis en tiempo real. El comportamiento cambiante en el tiempo de los sistemas, en conjunción con los requisitos para prevenir o minimizar el daño y el coste, pueden imponer restricciones sobre el tiempo disponible para realizar la diagnosis. Se necesita pues una arquitectura práctica de tiempo real que se guíe por el objetivo de tener una diagnosis útil (potencialmente renable) disponible en cualquier momento. Diagnosis y reparación. Los procesos reales de diagnóstico incluyen razonar y actuar así como la idea de restablecer el funcionamiento deseado. Pero todo lo que hemos venido discutiendo se centra en la idea de encontrar el fallo, no de repararlo. El hecho de que la diagnosis debería servir como tarea reparadora debe tener un impacto en el sistema de diagnóstico. Por ejemplo, no tiene ningún sentido gastar energías en distinguir dos fallos que necesitan la misma reparación. Las acciones de reparación podrían apoyar la localización del fallo (por ejemplo reemplazando un componente dañado o punteándolo mediante un cambio estructural), y necesitaríamos teorías y sistemas que integrasen ambas tareas. En este sentido, la automatización ( autonomic computing ) es un tema candente actualmente. La tecnología que automáticamente detecte y remedie los problemas es una tentadora perspectiva. Fallos estructurales. El concepto de diagnosis que hemos venido usando se centra en la conservación de la estructura original del sistema que se quiere
58 4.2. Fases del proceso del KDD diseñando estrategias para evitar ruido, valores incompletos, casos extremos (outliers), etc. 4. Transformación y reducción de los datos. Incluye la búsqueda de características útiles de los datos según sea el objetivo nal, la reducción del número de variables y la proyección de los datos sobre espacios de búsqueda en los que sea más fácil encontrar una solución. Este es un paso crítico dentro del proceso global, que requiere un buen conocimiento del problema y una buena intuición, y que, con frecuencia, marca la diferencia entre el éxito o el fracaso del proceso de KDD . 5. Selección del tipo de tarea y del conocimiento a obtener. Existen distintas estrategias para extraer conocimiento, dependiendo del objetivo nal del usuario: clasicación, asociación, agrupamiento, predicción de comportamientos, detección de desviaciones, etc. 6. Selección del algoritmo de minería de datos. Este paso es muy importante pues de él depende la obtención de resultados aceptables. 7. Análisis e interpretación del conocimiento extraído . Este análisis puede inducir la repetición del proceso, quizás con otros datos, otros algoritmos, otros objetivos y otras estrategias. La obtención de resultados aceptables está inuido por la existencia de medidas de interés del conocimiento (de tipo estadístico, en función de su sencillez, etc.), que permiten presentar únicamente el conocimiento útil. Además, la interpretación de estos resultados puede beneciarse de procesos de visualización. 8. Difusión y uso del nuevo conocimiento . El conocimiento se obtiene para realizar acciones, ya sea incorporándolo dentro de un sistema o simplemente para documentarlo y distribuirlo a las personas interesadas. En las siguientes secciones se analiza con mayor detalle cada una de estas etapas, ofreciendo los métodos que normalmente se utilizan en cada una de ellas.
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 59 4.3. Las fuentes de información Las primeras fases del KDD determinan que las fases sucesivas sean capaces de extraer conocimiento válido y útil a partir de la información original. En principio, los algoritmos de minería de datos no especican cuál debe ser el medio o soporte de los datos. Lo ideal es que el algoritmo sea capaz de aplicarse a cualquier tipo de almacenamiento de información. Puesto que actualmente existen varios sistemas de almacenamiento, la minería de datos, sobre todo a nivel comercial, está dedicando gran parte de su esfuerzo en la fase de selección de los datos para que sean compatibles con la mayoría de los tipos de almacenamiento de información. A continuación se detallan algunos de los más habituales: Ficheros planos. Actualmente es la fuente de información más común para los algoritmos de minería de datos. Normalmente son cheros de texto o binarios con una estructura conocida por el algoritmo. Bases de datos relacionales. Quizás sea el sistema de almacenamiento más extendido. Una base de datos relacional está formada por un conjunto de tablas bidimensionales relacionadas entre sí. Cada tabla, a su vez, está formada por las y columnas, donde las las representan objetos o relaciones entre objetos y las columnas muestran las características o atributos de dichos objetos. Los algoritmos de minería de datos que trabajan con bases de datos relacionales son más versátiles puesto que pueden utilizar el lenguaje SQL para la fase de limpieza, preprocesado, transformación y reducción de los datos. Data Warehouses. El Data Warehouse es una especie de punto focal que guarda en un único lugar toda la información útil proveniente de sistemas de producción y fuentes externas. Antes de cargarse en el Data Warehouse, la información debe extraerse, depurarse y prepararse, y una vez integrada, la información debe presentarse de manera comprensible para el usuario. Una denición de Data Warehouse, propuesta en [Inmon, 1992], podría ser la siguiente: colección de datos orientados al sistema, integrados, no volátiles e historiados, organizados para el apoyo de un proceso de ayuda a la decisión" .
60 4.3. Las fuentes de información El objetivo es lograr recomponer los datos disponibles para obtener una visión integrada y transversal a las distintas funciones de la empresa, una visión de negocio a través de distintos ejes de análisis y la visión agregada o detallada, adaptada a las necesidades. Bases de datos de transacciones. Son conjuntos de transacciones, generalmente representadas por el momento de realización, un identicador y un conjunto de objetos o items. En este caso, los registros pueden ser de tamaño variable, dependiendo del número de items que contengan. Es el tipo de almacenamiento con el que trabajan, generalmente, los algoritmos que extraen reglas de asociación. Bases de datos multimedia. Este tipo de bases de datos incluyen objetos multimedia como vídeo, imágenes y audio. Bases de datos espaciales. Son bases de datos en las que, además de la información habitual, se almacena información geográca como mapas, coordenadas regionales y globales, etc. Bases de datos temporales. Una base de datos temporal es aquella que puede contener datos históricos y datos actuales. Los datos temporales son una forma de representar hechos relacionados con el tiempo. World Wide Web. La Web es el sistema de almacenamiento de información más heterogéneo y dinámico que existe actualmente. De hecho, una disciplina en pleno auge es el web mining , que se centra en la extracción de conocimiento a partir de la información generada en la web. A continuación, se presentan una serie de deniciones relacionadas con los datos que permitirán aunar los conceptos que se utilizarán a lo largo de esta memoria de tesis. Denición 4.1. Dominio . Un dominio D es un conjunto de valores del mismo tipo. Los dominios se pueden clasicar en cuantitativos y categóricos. Los dominios cuantitativos son aquellos cuyos valores son numéricos y pueden ser, a su vez, discretos (valores enteros) o continuos (valores reales). Los dominios categóricos
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 61 son aquellos cuyos valores no son numéricos y pueden ser nominales (sin un orden en la secuencia) u ordinales (con orden en su secuencia). Denición 4.2. Atributo. Un atributo A es una característica de un ejemplo o caso que toma sus valores de un determinado dominio D . Denición 4.3. Clase. Una clase es un atributo especial, utilizado en aprendizaje supervisado, que sirve para categorizar o etiquetar cada uno de los casos con un valor perteneciente a su dominio. En aprendizaje supervisado, el dominio de la clase suele ser discreto. Denición 4.4. Ejemplo. Un ejemplo, también denominado caso o instancia, es cada uno de los elementos pertenecientes a un conjunto de datos C . De esta forma, un ejemplo e es un registro de la base de datos que toma sus valores de los dominios de los atributos de C . Denición 4.5. Conjunto de datos. Un conjunto de datos C es un subconjunto del producto cartesiano de los dominios de los atributos pertenecientes a dicho conjunto. Esto es, C ⊆ (D1× D2×...× Dm) , donde Di es el dominio del atributo Ai . Un conjunto de datos se caracteriza por el número m de atributos y el número de ejemplos o casos que contiene. Denición 4.6. Conjunto de entrenamiento. Un conjunto de entrenamiento es un subconjunto de un conjunto de datos que será utilizado como entrada en el algoritmo de aprendizaje automático. Normalmente se utiliza sólo una parte del conjunto de datos para obtener el conocimiento. Denición 4.7. Conjunto de prueba o test. Un conjunto de test es un subconjunto de un conjunto de datos que será utilizado para la evaluación del conocimiento inducido, como medida para determinar la abilidad del algoritmo empleado.
62 4.4. Limpieza, preprocesado y transformación de los datos 4.4. Limpieza, preprocesado y transformación de los datos Una vez seleccionadas las fuentes de información, éstas deben someterse a un proceso de limpieza y transformación en el que los datos son preparados, mediante diferentes técnicas, con el objeto de obtener nuevos conjuntos de datos a los que se puedan aplicar con garantía los algoritmos de minería de datos. Principalmente consiste en eliminar los datos erróneos o inconsistentes y los datos irrelevantes, aplicándoles el formato adecuado. De esta forma, durante estas etapas, los datos seleccionados se someten a tres tipos de técnicas: tratamiento de valores ausentes, eliminación de ruido y normalización de los datos. 4.4.1. Tratamiento de valores ausentes La inserción de datos en una base de datos es un proceso que puede realizarse de forma automática o manualmente. En esta introducción de la información es muy posible que, en el momento del proceso, se desconozcan algunos de los valores o no se recojan correctamente. En estas situaciones se suele asignar un elemento o símbolo para indicar que se trata de un valor desconocido. Es, por tanto, una misión del proceso de KDD establecer y aplicar unas técnicas que corrijan estas ausencias antes de aplicar el algoritmo de minería. La técnica más simple de tratamiento de valores ausentes consiste en eliminar las instancias donde alguno de los atributos que la componen incluya un valor ausente. Esta técnica, aunque muy simple, en la mayoría de las ocasiones no es la más aconsejable ya que conlleva una enorme perdida de información del resto de atributos de la instancia que sí disponen de valor. Una estrategia que soluciona la pérdida de instancias se basa en el uso de métodos estadísticos o heurísticos para determinar un posible valor para los atributos ausentes. En este sentido, las técnicas más conocidas son aquellas que utilizan la media para dominios cuantitativos, y la moda para dominios discretos, como estimadores para determinar los valores ausentes. Estas técnicas tienen un inconveniente si el número de valores ausentes de un atributo es muy elevado debido a que generarían el mismo valor para todas las ausencias. Para resolver ese proble-
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 63 ma, es necesario que los valores de la media y la moda sean generados a partir de diferentes subconjuntos de las instancias. 4.4.2. Traslación del dominio de los atributos La mayoría de los algoritmos de aprendizaje distinguen entre atributos continuos y discretos. En la resolución de ciertos problemas, los algoritmos de minería de datos requieren que el dominio de los atributos sea de un determinado tipo que, a veces, no coincide con en el que se encuentra almacenado en la base de datos. Así, muchos algoritmos de aprendizaje trabajan únicamente con atributos discretos, por lo que resulta necesario realizar una traslación del dominio original del atributo al dominio permitido por el algoritmo. Básicamente existen dos tipos de traslaciones: de atributos discretos a continuos, denominada numeración , y de atributos continuos a discretos, denominada discretización . Numeración La numeración consiste en la trasformación de un dominio no ordenado (discre- to) en un dominio ordenado (numérico). No suele ser un proceso frecuente, aunque existen muchos trabajos referentes a este campo. Algunos de los más signicativos pueden consultarse en [Breiman et al. , 1984] [Hampson and Volper, 1986] [Utgo and Brodley, 1990] [Van de Merckt, 1992] [Van de Merckt, 1993]. El método más simple para realizar la numeración de atributos discretos consiste en asignar un valor numérico creciente, en base a algún conocimiento sobre la realidad del atributo, a cada uno de los posibles valores del atributo. Este método, aunque es un método sencillo, presenta el inconveniente de que esta ordenación articial produzca posteriormente errores en la interpretación de los resultados. Discretización El proceso de discretización consiste en la traslación de un dominio numérico a un dominio discreto. Dicho de otra forma, se trata de encontrar puntos de corte que dividan el espacio de valores continuos en una serie de intervalos, pudiéndolos tratar, a partir de ese momento, como atributos discretos con un número nito
64 4.4. Limpieza, preprocesado y transformación de los datos de valores. Este proceso es bastante frecuente puesto que una gran mayoría de algoritmos de aprendizaje trabajan únicamente con dominios discretos. En general, los métodos de discretización suelen clasicarse en métodos de discretización supervisada y métodos de discretización no supervisada . Esta distinción se realiza dependiendo de si se utiliza o no información sobre las clases para agrupar los datos. Los métodos supervisados emplean información sobre la clase a la que pertenece cada caso del conjunto de entrenamiento a la hora de evaluar y escoger los puntos de corte que denen los intervalos en que quedan agrupados los valores numéricos. Los métodos no supervisados no tienen en cuenta esta información y utilizan la distribución de valores de un atributo continuo como única fuente de información. La forma más simple de discretización consiste en crear un número preestablecido de intervalos. Las técnicas más habituales dentro de la discretización no supervisada consisten en dividir el rango del atributo en k intervalos del mismo tamaño o amplitud ( Equiwidth , discretización de igual anchura), o bien asignar a cada intervalo el mismo número de valores ( Equidepth , discretización de igual frecuencia). En [Dougherty et al. , 1995]se repasan distintos métodos de discretización utilizados en inteligencia articial y aprendizaje automático. Por su parte, los métodos de discretización supervisada utilizan información discriminatoria de las instancias para determinar los puntos frontera. El discretizador 1R de Holte [Holte, 1993]es una variante supervisada de este tipo de métodos, que ajusta los límites de los intervalos en función de la clase a la que pertenezcan los casos del conjunto de entrenamiento. En [Liu and Setiono, 1995]se presenta un método estadístico, denominado Chi2 , que utiliza las frecuencias relativas de las clases entre intervalos adyacentes, de tal forma que si son muy similares es posible su fusión. La fórmula para calcular el valor de χ2 es P2 i=1 P|C| j=1 (Aij −Eij )2 Eij , donde Aij =RiCj n , siendo |C| el número de clases, Aij el número de instancias en el intervalo i con clase j , Eij la frecuencia esperada de Aij , Ri el número de instancias en el intervalo i, Cj el número de instancias de la clase j en los dos intervalos y n en número de instancias en los dos intervalos. La teoría de la información también ha originado la aparición de algunas técnicas de discretización, como el uso de la ganancia de información o del criterio de
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 65 proporción de ganancia en la construcción de árboles de decisión. El método de discretización supervisada de Fayyad e Irani [Fayyad and Irani, 1993], basado en el principio MDL de Rissanen [Rissanen, 1983], es un ejemplo destacado de este tipo de métodos. El algoritmo decide dónde colocar los cortes de los intervalos dependiendo de la entropía de la clase. El método se aplica recursivamente a los dos intervalos obtenidos tras cada división hasta satisfacer una condición de parada. En este caso, la condición de parada es el citado Principio de Longitud de Descripción Mínima. Una alternativa similar se presenta en [Catlett, 1991], pero en este caso el algoritmo termina cuando el número de ejemplos en un intervalo es sucientemente pequeño o cuando se han creado un número máximo de intervalos. 4.4.3. Selección de atributos relevantes La selección de atributos relevantes ( feature selection ) es un procedimiento fundamental durante el proceso de KDD para que el algoritmo de minería pueda realizar su función con mayor probabilidad de éxito. El objetivo general es reducir el conjunto de datos original, eliminando atributos con información redundante o irrelevante con el objetivo de facilitar el proceso de aprendizaje posterior. Por tanto, consiste en identicar y suprimir del conjunto de datos aquellos atributos con escasa o nula relevancia dentro del mismo. Existen diferentes enfoques para determinar la relevancia de atributos. Entre ellos se describen someramente el algoritmo RELIEFF y una técnica basada en el criterio de información mutua. RELIEFF El algoritmo RELIEFF, descrito en [Kononenko, 1994] [Kononenko and Simec, 1995], es una ampliación del algoritmo RELIEF, desarrollado por Kira y Rendell [Kira and Rendell, 1992]. La mejora del trabajo de Kononenko consiste en permitir valores ausentes y más de dos clases en el conjunto original. La relevancia de los atributos se determina analizando las instancias más cercanas. Así, dada una instancia, RELIEF busca a sus dos instancias más cercanas, una de la misma clase y otra de una clase diferente, y actualiza los pesos de los atributos involucrados dependiendo de si sus valores son iguales o no al ejemplo.
66 4.4. Limpieza, preprocesado y transformación de los datos La idea del algoritmo es favorecer los atributos que tengan valores diferentes en instancias parecidas de diferente clase y valores iguales en instancias parecidas de la misma clase. Técnicas basadas en el criterio de información mutua La técnica de selección de atributos relevantes basada en el criterio de información mutua [Cover and Thomas, 1991]tiene como objetivo determinar la relación entre los atributos y la clase, entendiendo el concepto de relación como la información que los primeros ofrece sobre el segundo. Así, aquellos atributos que no ofrezcan información de la clase podrían ser eliminados. I(Ai,C) = K X k J X j P(cj∧Ak i)P(cj∧Ak i) P(cj)P(Ak i) (4.1) Para ello, la información I , entre un atributo Ai y la clase C , puede calcularse mediante la ecuación 4.1, donde P(cj) es la probabilidad de que la clase C tome el valor j , P(Ak i) la probabilidad de que el atributo Ai tome el valor k , P(cj∧Ak i) la probabilidad de que ocurran los dos sucesos conjuntamente, K el número de valores distintos del atributo Ai y J el número de clases. Además, para determinar la información mutua entre atributos se genera una matriz donde la celda (i, j) almacena I(Ai,Aj) . Si para cualquier la i existe un elemento tal que ti,i =ti,j , entonces el atributo Aj es redundante con respecto al Ai y se puede eliminar. 4.4.4. Reducción de instancias Otro de los procedimientos fundamentales durante el proceso de KDD es la reducción de instancias del conjunto inicial. El problema de la reducción de instancias surge cuando las técnicas de minería de datos se ven incapaces de abordar el proceso de aprendizaje sobre un conjunto de datos con un elevado número de instancias. En general, el proceso de reducción consiste en encontrar un subconjunto S del conjunto inicial D que contenga el mismo conocimiento. Esto es, la técnica de reducción debe preservar el conocimiento del conjunto original de datos, de forma
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 67 que el algoritmo de minería pueda obtener lo mismos patrones desde el nuevo conjunto de datos. En función de cómo se realice el proceso de búsqueda del subconjunto S , las técnicas de reducción de instancias pueden clasicarse en: incrementales, decrementales y por lotes. La búsqueda incremental comienza con un subconjunto S vacío al que se le van añadiendo instancias del conjunto original de datos que cumplan un determinado criterio preestablecido. Algunos de los algoritmos incrementales más signicativos son el algoritmo de Hart, denominado CNN ( Condensed Nearest Neighbor )[Hart, 1967]y los algoritmos IBL2, IBL3, IBL4 e IBL5 ( Instance-Based Learning )[Aha et al. , 1991]. La búsqueda decremental comienza con el conjunto original de instancias ( S = D ), y se van eliminando de acuerdo a algún criterio establecido. Dentro del grupo de algoritmos decrementales están: RNN ( Reduced Nearest Neighbor )[Gates, 1972], ENN ( Edited Nearest Neighbor )[Wilson, 1972]y SNN ( Selective Nearest Neighbor )[Ritter et al. , 1975] [Lindenbaum et al. , 1999]. Por último, la búsqueda por lotes establece un criterio de reducción y analiza el conjunto de datos completo eliminando todas aquellas instancias que satisfacen dicho criterio. Las técnicas más comunes que utilizan esta estrategia de búsqueda son AENN ( All-kNN Edited Nearest Neighbor ) y UENN ( Unlimited Edited Nearest Neighbor )[Tomek, 1976]. 4.5. Minería de datos Una vez que los datos han sido preparados y, siguiendo la secuencia descrita para el proceso de KDD , la siguiente etapa del proceso es la minería de datos. En esta fase y en las sucesivas hay que tomar algunas decisiones importantes: 1. Elegir la técnica de minería de datos que se va aplicar. Esta elección depende, en gran medida, del tipo de conocimiento o patrón que se desea descubrir. 2. Elegir el algoritmo más apropiado para implementar dicha técnica. 3. Establecer los criterios de evaluación de los modelos obtenidos para mostrar únicamente la información útil y válida.
74 4.5. Minería de datos Al nal del proceso, los nodos del árbol quedan etiquetados con nombres de atributos, las ramas con los valores posibles para el atributo, y las hojas con las diferentes clases. Una vez se obtiene el árbol a partir del conjunto de entrenamiento, los ejemplos del test cuya clase se desconoce son clasicados recorriendo el árbol por aquellas ramas para las cuales los valores de sus atributos se cumplen hasta alcanzar una hoja. Figura 4.5: Ejemplo de árbol de decisión Figura 4.6: Cortes realizados según el criterio de partición La gura 4.5 se muestra un ejemplo de árbol de decisión para un conjunto de entrenamiento formado por dos atributos numéricos y dos clases, mientras que en la gura 4.6 se representa el conjunto de entrenamiento con los cortes utilizados para clasicar los ejemplos.
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 75 Los sistemas basados en árboles de decisión forman una familia llamada TDIDT ( Top-Down Induction of Decision Trees ), cuyo representante más conocido es C4.5 [Quinlan, 1993b], que permite clasicar ejemplos con atributos que toman valores continuos. La principal ventaja de esta representación son sus reducidos requisitos computacionales. Sin embargo cuando el número de atributos es elevado y para estos lo es también el dominio de valores, se vuelven difíciles de comprender. La construcción y clasicación de un árbol de decisión viene dada por: la función de selección, el criterio de parada y el algoritmo de podado. La función de selección es el criterio utilizado por el árbol para particionar el conjunto de entrenamiento, esto es, obtener los sucesivos subárboles que lo componen. Las mas utilizada es la ganancia de información media, que selecciona para cada partición el atributo que genera la reducción máxima de la entropía media. Otras medidas utilizadas son GINI y la ganancia de información normalizada. El criterio de parada determina cuando una partición se completa. Generalmente se llega a una hoja cuando todos los ejemplos del subconjunto que contiene pertenecen a la misma clase, pero no es el único criterio. El algoritmo de podado intenta prevenir el sobreajuste, que puede evitarse mediante un pre-podado o un post-podado donde el árbol ya esta totalmente construido. Algunas técnicas son el Error-Complexity , el error pesimista o el error mínimo. Las principales diferencias entre los distintos algoritmos de árboles de decisión radica en la elección de la función de selección y en la estrategia de podado. Los árboles de decisión son fáciles de usar, admiten atributos numéricos y categóricos, y tratan bien los atributos no signicativos, el ruido y los valores ausentes. Su principal ventaja es la comprensibilidad, y su peor cualidad la falta de precisión y que son inestables ante variaciones de la muestra. Técnicas relacionales, declarativas y estructurales Estas técnicas presentan los modelos mediante lenguajes declarativos, como los lógicos y funcionales. Estos métodos permiten descubrir patrones complejos,
76 4.5. Minería de datos haciendo uso de la estructura de los propios datos y las relaciones entre ellos. La técnica más representativa es la programación lógica inductiva (ILP 1 ). En 1990, Sthephen Muggleton dene la programación lógica inductiva como la intersección de la programación lógica y el aprendizaje inductivo [Muggleton, 1991]. En su formulación más simple, la tarea de la ILP consiste en aprender la denición de un predicado a partir de hechos que son ciertos para este predicado, hechos que son falsos para este predicado y la denición de otros predicados auxiliares que se pueden usar en el proceso de aprendizaje. Es decir, a partir de una base de datos de hechos y resultados esperados, que se dividen en verdaderos y falsos, un sistema ILP intenta crear un programa lógico que demuestre todos los resultados ciertos y ninguno de los falsos. Aunque la ILP es la aproximación más extendida, no es la única existente, y hay diversos métodos alternativos, como el aprendizaje basado en grafos [Washio and Motoda, 2003], los modelos relacionales probabilísticos [Koller and Pfeer, 1998], los árboles de decisión relacionales (como SCART [Kramer and Widmer, 2000]o las reglas de asociación relacionales [Dehaspe and Toivonen, 1999]. Las técnicas que usan estos lenguajes forman un conjunto denominado Minería de Datos Relacional . Son técnicas muy precisas, que permiten capturar patrones relacionales y recursivos y los modelos generados son comprensibles. Por contra, son difíciles de manejar y los métodos existentes no son muy ecientes. Redes neuronales articiales Los sistemas de aprendizaje basados en redes neuronales utilizan modelos matemáticos fundamentados en los conceptos del funcionamiento del sistema nervioso de los seres vivos [McCulloch and Pitts, 1943], mediante una simulación simple del proceso de aprendizaje de las neuronas del cerebro. Para ello, cada neurona es simulada mediante una unidad de cálculo que se conecta, mediante capas, con otras neuronas de tal forma que la salida de una es la entrada de otra. La primera capa se conoce como capa o vector de entrada ya que será la que tome los datos externos (el conjunto de datos) y la última capa se denomina capa o vector de salida, ya que ofrecerá los resultados del procesamiento. 1 del inglés Inductive Logic Programming
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 77 El resto de capas se denominan capas o vectores ocultos. En la gura 4.7 se ofrece una representación de una red neuronal. Figura 4.7: Estructura de una red neuronal En la práctica, para el diseño de la red neuronal es necesario decidir una serie de parámetros, como el número de unidades (neuronas), la interconexión entre ellas, el algoritmo de aprendizaje y la codicación de las entradas y salidas. Los distintos sistemas de redes neuronales existentes abordan diferentes tareas. Los más extendidos dentro de cada tipo son: las memorias asociativas, las redes de Hopeld, la máquina de Bolzman y la máquina de Cauchy, las redes de aprendizaje competitivo, las redes de Kohonen o mapas auto-organizados [Kohonen, 1982] [Kohonen, 1984]y las redes de resonancia adaptativa (ART) para tareas descriptivas, la red Adaline, el perceptrón multicapa [Rosenblatt, 1958]y la memoria asociativa bidireccional para tareas predictivas y las redes de función de base radial (RBF, Radial Basic Function )[Moody and Darken, 1989], que son modelos híbridos que tratan de aprovechar las ventajas de ambas estrategias. Obtienen en general precisiones muy altas cuando están bien ajustadas. Son muy precisas y capturan modelos no lineales, aunque son muy sensibles a valores anómalos, necesitan muchos ejemplos y suelen ser lentas además de generar modelos no comprensibles. Se necesita además cierta experiencia para ajustar el número de capas y nodos internos.
78 4.5. Minería de datos Máquinas de soporte vectorial Estas técnicas intentan maximizar el margen entre los grupos o clases formadas. Se basan para conseguirlo en transformaciones que aumentan la dimensionalidad. Las funciones usadas con tal n son denominadas funciones núcleo . Según la función núcleo usada y la forma de trabajar con el margen existen muy diversas opciones. Las maquinas de soporte vectorial pertenecen al grupo de los clasicadores lineales, puesto que inducen separadores lineales o hiperplanos en espacios de características de muy alta dimensionalidad. La idea que hay detrás de las SVM 2 es encontrar el hiperplano separador que está equidistante de los ejemplos más próximos de cada clase. De forma intuitiva, dicho hiperplano está situado en la posición más neutra posible con respecto a las clases representadas por el conjunto de datos, sin estar sesgado hacia ninguna de las clases. A nivel algorítmico, el aprendizaje de las SVM representa un problema de optimización con restricciones que puede ser resuelto usando técnicas de programación cuadrática (QP). Cuando las clases no son linealmente separables, el aprendizaje de separadores no lineales se consigue mediante una transformación no lineal del espacio de atributos de entrada en un espacio de características de dimensionalidad mucho mayor y donde sí existe separación lineal de las clases. Para trabajar de manera eciente en el espacio de características, sin necesidad de calcular explícitamente las transformaciones de los ejemplos de aprendizaje se recurre a las funciones núcleo , que permiten calcular el producto escalar de dos vectores en el espacio de características. Por tanto, un requisito básico para el éxito en el aprendizaje es la elección de una función núcleo adecuada, que reeje a priori el conocimiento del problema a tratar. Las maquinas de soporte vectorial permiten trabajar con datos de dimensiones grandes y proporcionan modelos muy precisos. El principal problema es la elección de la función núcleo, y que al transformar los atributos iniciales , los modelos generados no son comprensibles. 2 del inglés Support Vector Machine
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 79 Técnicas evolutivas y difusas Este tipo de técnicas forman, junto con las redes neuronales, el conjunto de técnicas conocidas como soft computing (que traducida sería algo así como computación exible). Están formados por los métodos genéticos, junto con las pertenencias difusas (fuzzy). La principal característica de los métodos de computación exible es su tolerancia a la imprecisión y a la incertidumbre, lo que permite que se adapten muy bien a entornos cambiantes. Puesto que las redes neuronales han sido tratadas de forma independiente en un apartado previo, nos ocuparemos de los otros dos pilares de la computación exible: los algoritmos evolutivos y la lógica difusa. La computación evolutiva la forman un conjunto de algoritmos estocásticos de búsqueda basados en abstracciones del proceso de evolución de Darwin . En este area se han presentado distintos modelos computacionales denominados algoritmos evolutivos: algoritmos genéticos, estrategias de evolución, programación evolutiva y programación genética. Dichos algoritmos tratan de modelar la evolución siguiendo tres características comunes: 1. Se usa el proceso de aprendizaje colectivo de una población de individuos 2. Los descendientes de los individuos se generan mediante procesos no determinísticos que tratan de modelar los procesos de mutación y cruce. La mutación representa la auto-replicación errónea de los los individuos, mientras el cruce representa el intercambio de material genético de dos o más individuos. 3. Se asigna una medida de calidad, llamada medida de adaptación o tness a cada individuo mediante el proceso de evaluación. El operador de selección favorece en el proceso de evolución a los mejores individuos. Una de las características importantes de los algoritmos evolutivos es que realizan una búsqueda global. Al trabajar con una población de soluciones candidatas en vez de con una individual y los operadores estocásticos reducen el riesgo que caer en un óptimo local. Por su parte, la lógica difusa [Zadeh, 1965]permite modelar conocimiento impreciso y cuantitativo así como transmitir, manejar incertidumbre y soportar el razonamiento humano de una forma natural.
80 4.5. Minería de datos Los sistemas basados en reglas que usan conjuntos difusos para describir el valor de sus variables se denominan sistemas basados en reglas difusas, donde los términos lingüísticos de las reglas son caracterizados mediante conjuntos difusos. En los conjuntos difusos, la función de pertenencia asigna a cada elemento un grado de pertenencia dentro del intervalo [0,1]. Esto permite representar conceptos con límites borrosos, mal denidos, pero con signicado denido de forma completa y precisa. El interés de la lógica difusa en la minería de datos se deriva de la utilidad de recoger la imprecisión y exibilidad de los límites a la hora de describir e identi- car los patrones. Tienen numerosos usos, pero se han usado frecuentemente en Agrupamiento [Turksen, 1998], clasicación [Janikow, 1998]y reglas de asociación [Chen and Wei, 2002]. Las técnicas evolutivas son bastante exibles, al poder cambiar el heurístico sin modicar el algoritmo. Por contra, su coste computacional en tiempo y almacenamiento suele ser muy altos. Con las técnicas difusas se puede conseguir gran precisión, debido a la exibilidad de las fronteras establecidas. Técnicas basadas en casos, vecindad y distancia Son métodos que se basan en medir la distancia al resto de elementos. Esto puede hacerse de forma directa o mediante el uso de funciones más complejas como las de densidad. La técnica de clasicación más popular basada en distancia es la de los vecinos más cercanos. En esta técnica, las instancias del conjunto de datos se almacenan en función de su similitud. Para clasicar una nueva instancia, se extraen aquellas más parecidas y se clasica la nueva en base a ellas. Así, el proceso de aprendizaje es trivial mientras que el proceso de clasicación es el que consume el mayor tiempo. Las técnicas para agrupamiento por distancias crean grupos o clusters de elementos ” próximos ” entre sí. Dependiendo de la estrategia utilizada a la hora de realizar el agrupamiento, estos algoritmos pueden ser clasicados en: Métodos basados en particiones. Construyen k particiones en los datos y cada partición representa un grupo o cluster. Estos métodos comienzan creando una única partición inicial e iteran hasta cumplir un criterio de
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 81 parada. Algunos de los algoritmos que siguen esta estrategia son: k -means, PAM ( Partitioning Around Medoids ), CLARA ( Clustering Large Applications ) y CLARANS ( Clustering large Applications based upon RANdomized Search ). Métodos jerárquicos. Los datos se agrupan de manera arborescente. Se dividen en aglomerativos y por división . El primero, también denominado bottom-up , empieza con un cluster por cada instancia del conjunto de datos y va uniendo los clusters más parecidos hasta obtener k clusters. El algoritmo AGNES ( Agglomerative Nesting )[Kaufman L., 1990]es un ejemplo de esta forma de agrupamiento. El segundo método, también denominado top-down , empieza con un único cluster para todas los instancias y lo va dividiendo en clusters más pequeños hasta obtener los k clusters deseados. Un ejemplo de método divisorio es el algoritmo DIANA ( Divisive Analysis )[Kaufman L., 1990]). Métodos basados en densidades. Establecen un nivel de vecindad y agrupan las instancias que pertenecen a ese nivel. DBSCAN ( Density-Based Spatial Clustering of Applications with Noise ) y DENCLUE ( DENsity-based CLUstEring )[Hinneburg and Keim, 1998]utilizan este método. Métodos basados en rejillas. Dividen el espacio de búsqueda en rejillas a diferentes niveles y utilizan esta división para agrupar las instancias. Entre los algoritmos que utilizan este método están STING ( STatistical INformation Grid )[Wang et al. , 1997]y CLIQUE ( Clustering In QUEst )[Agrawal et al. , 1998]. Métodos basados en modelos. Buscan modelos que se ajusten con las instancias de cada cluster, como por ejemplo EM ( Expectation Maximization ) [Dempster et al. , 1977]y AutoClass ( Automatic classication or clustering ) [Cheeseman and Stutz, 1996]. Un caso algo distinto, pero siguiendo la losofía de la similitud de instancias lo constituye el razonamiento basado en casos [Sycara et al. , 1991]. Parte de la misma losofía que los vecinos más cercanos, pero los ejemplos no son vectores de números reales, sino descripciones simbólicas más complejas que, por tanto, deben
82 4.6. Análisis e interpretación del conocimiento extraído Nombre Predictivo Descriptivo a b c d e Técnicas Estadísticas X X X X Técnicas Bayesianas X Árboles de Decisión X X X X Técnicas relacionales, declarativas y estructurales. X X Redes Neuronales X X X Máquinas de Soporte Vectorial X X X Técnicas evolutivas y Difusas X X X X X Técnicas basadas en casos, densidad o distancia X X X a) Clasicación; b) Regresión c) Agrupamiento d) Reglas Asociación e) Correlaciones Tabla 4.1: Relación entre tareas y métodos de Data Mining manejar reglas de vecindad o funciones de distancias más complejas. En la sección 3.2 se expusieron las principales características de estos sistemas. Todos estos métodos son fáciles de usar y ecientes para un número de ejemplos reducido. No tratan bien los atributos no signicativos y al no generar modelos, no generan conocimiento comprensible. Su precisión suele ser bastante buena. Estos son los métodos principales, aunque existen otros más especícos, dependiendo de la tarea seleccionada, y sobre todo una gran cantidad de híbridos que intentan maximizar las ventajas de cada método intentando minimizar sus puntos débiles. Aunque no es posible hacer una correlación de tareas con métodos concretos, la tabla 4.1 intenta ilustrar las principales aplicaciones de cada método. 4.6. Análisis e interpretación del conocimiento extraído El proceso de evaluación de los patrones o conocimiento inducido es el proceso clave para determinar la ecacia de un método de minería de datos con respecto a otros métodos. Para sistemas de clasicación, la medida más directa para determinar el rendimiento del algoritmo es la estimación del error. De tal forma, que
Capítulo 4. Extracción de Conocimiento a Partir de Bases de Datos 83 en estos sistemas, partiendo del modelo de clasicación inducido y un conjunto de instancias de clase conocida, si dicho modelo de clasicación asigna a una instancia la clase no esperada, éste es considerado un error. La estimación del error es la proporción de errores sobre este conjunto de instancias. Existen diversos métodos para estimar la probabilidad de error de un modelo, que serán abordados en el capítulo siguiente.
90 5.3. Técnicas para mejorar la precisión Para una nueva observación esto signica minimizar el coste esperado de una clasicación errónea. Primero consideremos el coste de aplicar la regla por defecto: asociar cualquier observación nueva a la clase Ad , asumiendo que d es la etiqueta de la clase. Cuando se toma la decisión Ad para todos los nuevos casos, para los casos de la clase Ai tenemos un coste c(i, d) con una probabilidad pi . De esta forma el coste esperado Cd de tomar la decisión Ad es: cd=X i pic(i, d) (5.3) En la práctica el coste de errar en la clasicación es muy difícil de obtener, incluso en casos en los que es muy claro la desigualdad existente entre las recompensas o penalizaciones por tomar una decisión correcta o incorrecta. La manera más habitual de expresar dichos costes es mediante la matriz de costes . Esta matriz representa los costes de todas las posibles combinaciones que se pueden dar entre la clase predicha y la real. Por tanto, para un problema de C clases, la matriz será de tamaño CxC . Cada celda representa el coste de errar, según la clasicación correcta y la predicha. 5.3. Técnicas para mejorar la precisión En aquellos problemas donde la separabilidad de las clases sea muy baja, la precisión obtenida por los métodos de clasicación podrán variar en función del método, pero serán en general peor que para clases más fácilmente separables. En estos casos, podemos usar una serie de métodos que nos permiten aumentar la precisión: Aumento de la dimensionalidad y/o creación de atributos. Generalmente al aumentar la dimensionalidad podemos denir separabilidad lineal o más sencilla al tener más dimensiones con las que denir el separador. Este es el caso de las máquinas de soporte vectorial. No obstante, existe también la posibilidad de combinar atributos para aprender conceptos que no pueden aprenderse con los atributos originales.
Capítulo 5. Características de la Clasicación Automática 91 Localidad. Existen problemas que globalmente son muy poco separables, pero que sin embargo pueden aproximarse mejor a un nivel más local. El problema que plantea esta opción es que podemos caer en el sobreajuste, al tratar un único problema global como la unión de una serie de problemas locales. Combinación de modelos y métodos. Consiste en crear modelos formados por la combinación de varios modelos. Este caso será tratado en las secciones 5.5 y 5.6. 5.4. Métodos para la evaluación de resultados Es de sobra conocido que si estimamos los porcentajes de error con el mismo conjunto de datos con los que se ha realizado la clasicación los resultados no son muy ables. Por una parte si permitimos un árbol de clasicación lo sucientemente complejo, es decir, con el suciente número de niveles y hojas, posiblemente podamos obtener una tasa de acierto del 100% sobre los mismos datos usados para generar las reglas. En la práctica estas estructuras tan complejas no clasican bien sobre datos distintos a los del entrenamiento, y este es uno de los principales problemas de 'sobreajustar' los datos. El fenómeno de sobreajuste es más preocupante aún cuando, sobre los datos de entrenamiento, es imposible obtener un porcentaje de acierto del 100% debido a la existencia de casos conictivos, aunque también es preocupante aunque esto no ocurra. Como regla general deberemos usar estructuras de clasi- cación simples para casos en los que los datos de entrenamiento contengan casos imposibles de clasicar correctamente, y dejar las estructuras más complejas para casos en los que la clasicación de los datos de entrenamiento es posible hacerla con el 100% de acierto. Entrenamiento y Test La idea básica es obtener unas reglas de clasicación a partir de un conjunto de datos de entrenamiento, y conocer el porcentaje de errores que se obtienen al clasicar un conjunto de datos distintos a los empleados para generar las reglas, y sobre los que no se conoce la clasicación correcta. Para realizar esto vamos a testar
92 5.4. Métodos para la evaluación de resultados las reglas con un conjunto de datos distintos a los de entrenamientos y sobre los que si se conoce la clasicación. Para poder hacer esto vamos a separar del conjunto de entrenamiento un subconjunto aleatorio (normalmente el 20 o 30% de casos) de casos que no serán usados en el entrenamiento y nos servirán posteriormente para realizar los tests. Hay una perdida de eciencia al no entrenar la clasicación con todos los casos disponibles, pero en bases de datos grandes tampoco supone mucho problema. Podremos usar este procedimiento cuando el número de casos sea mucho mayor de 1000 y podamos usar un conjunto de test de aproximadamente 1000 casos. Validación cruzada (Cross-validation) Para casos en los que el tamaño de los casos sea moderado el método empleado es el de validación cruzada [Lachenbruch and Mickey, 1968]. El método consiste en dividir los datos disponibles en subconjuntos. Cada subconjunto se predice con las reglas de clasicación obtenidas de los (m-1) subconjuntos restantes. De esta manera el error se calcula de forma imparcial y eciente. Finalmente se utilizan todos los datos para obtener las reglas denitivas. [Stone, 1974]describe los métodos de validación cruzada para dar estimaciones imparciales de la proporción del error. Una dicultad para usar el método de validación cruzada en métodos que requieren altos grados de tiempo de computación, como pueden ser las redes neuronales, es la repetición del entrenamiento para cada subconjunto, lo que puede producir tiempos de computación excesivos. Validación por secuencia (Bootstrap) La principal objeción impuesta al método de validación cruzada es que produce una estimación del error demasiado dispersa, ya que los intervalos de conanza para la tasa de error real son demasiado amplios. El procedimiento de validación cruzada produce un intervalo de conanza mucho más estrecho, pero el precio a pagar es que las tasas de error estimadas están optimizadas. Normalmente es preferible el uso de validación en secuencia cuando el tamaño de la base de datos es pequeño, mientras que para bases de datos más grandes es preferible el método
Capítulo 5. Características de la Clasicación Automática 93 de validación cruzada. El método consiste en analizar repetidamente subconjuntos de datos. Cada subconjunto se toma al azar con reemplazo a partir del original. [Efron, 1983]proporciona las siguientes propiedades de la validación por secuencia como un estimador de la tasa de error: Tomando un número de subconjuntos muy grande la varianza estadística en la media de la tasa de error es pequeña, y para ejemplos de tamaño pequeño esto signica que la validación por secuencia tendrá mucha menor varianza estadísticamente que la estimación por validación cruzada. La validación por secuencia y la validación cruzada son muy parecidas para ejemplos de tamaño grande y el porcentaje entre las dos estimaciones tiende a 1 cuando el tamaño del ejemplo tiende a innito. El tamaño efectivo del ejemplo viene determinado por el número en el grupo de clasicación más pequeño. En [Efron, 1983]se cita un ejemplo médico con 155 casos, pero el interés primario se centra en los 33 pacientes que mueren. Así pues el tamaño efectivo del ejemplo es de 33. Matriz de confusión Una matriz de confusión C es una matriz de m×m enteros que contienen el rendimiento de un clasicador ϕ , aplicado a los ejemplos de una base de datos. La entrada C(i, j) cuenta el número de realmente pertenecen a la clase i , pero que fueron clasicados por ϕ como pertenecientes a la clase j . C(i, j) = {e∈D|D(e) = i, Dϕ(e) = j} (5.4) Obviamente es deseable que los elementos de la diagonal principal tengan los valores tan grandes como sea posible. Las probabilidades se estiman fácilmente a partir de la matriz C dividiendo cada entrada por la suma de las las o columnas donde aparece la entrada. Pr[D(e) = i|Dϕ(e) = j] = C(i, j) Pm i=1 C(i, j) (5.5) Pr[Dϕ(e) = j|D(e) = i] = C(i, j) Pm j=1 C(i, j) (5.6)
94 5.4. Métodos para la evaluación de resultados Real Estimado TPR FPR FNR TNR Tabla 5.1: Matriz de Confusión Normalizada Pr[Dϕ(e) = D(e)] = Pm i=1 C(i, j) Pm j=1 Pm i=1 C(i, j) (5.7) La proporción de ejemplos correctamente clasicados se denomina exactitud de predicción (ecuación 5.7) y es sin duda la medida de rendimiento más popular en el área de aprendizaje automático. Análisis ROC Todas las técnicas anteriores evalúan la clasicación basándose en el porcentaje de error cometido, sin diferenciar en el tipo de error cometido, sin embargo, sabemos que los diferentes errores tienen costes muy dispares. Si se dispone de la matriz de costes, se podría adaptar el aprendizaje al contexto de coste determinado. Desgraciadamente, la matriz de costes no siempre está disponible. En estos casos, lo que se suele hacer es aprender un conjunto de clasicadores y seleccionar el que mejor se comporte para un contexto de coste determinado a posteriori. El análisis ROC (del inglés Receiver Operating Characteristic) provee herramientas para seleccionar el conjunto de clasicadores que tienen un comportamien- to óptimo en general, y evaluar los clasicadores de manera más independiente y completa que la precisión del error. Se utiliza para problemas de dos clases (clase positiva y negativa). Para este tipo de problemas utiliza un matriz de confusión normalizada, del tipo: Donde TPR es el porcentaje de positivos: TPR =TP(TP/FN) , FNR es el porcentaje de falsos negativos FNR =FN/(TP +FN) , FPR es el porcentaje de falsos positivos FPR =FP/(FP +TN) y TNR es el porcentaje de negativos TNR =TN/(FP +TN) . Siendo TP el número de positivos, TN el número de negativos, FP el número de falsos positivos y FN el número de falsos negativos. Lógicamente, TPR = 1 −FNR y FPR = 1 −TNR . Esto permite que con los ratios TPR y FPR se pueda construir el denominado espacio ROC , limitado por
Capítulo 5. Características de la Clasicación Automática 95 los puntos (0,0) y (1,1) . Habitualmente se usa el valor FPR para el eje de las x y el valor de TPR para el eje de las y . Representar un clasicador de esta forma en el espacio ROC permite que dado un conjunto de clasicadores, se pueden descartar los clasicadores que no caigan dentro de la supercie convexa formada por todos los clasicadores, junto con los puntos (0,1), (1,0) y (0,0). Por tanto, el mejor sistema de aprendizaje será aquel que produzca el conjunto de clasicadores con mayor area bajo la supercie convexa. Este área se denomina AUC (del inglés Area Under the ROC Curve). La gura 5.2 muestra un ejemplo de diagrama ROC. Los clasicadores B y E pueden ser descartados, según el análisis ROC. TPR FPR 0.0 0.0 1.0 1.0 A B C D E Figura 5.2: Ejemplo de diagrama ROC La principal limitación del análisis ROC es que sólo es fácilmente aplicable a problemas de dos clases. 5.5. Construcción de multiclasicadores En los últimos años, ha surgido un creciente interés por la combinación de clasicadores con el objeto de mejorar la precisión. Diettrich [Dietterich, 2000a], establece una taxonomía para la construcción de conjuntos de clasicadores: Manipulación de los datos de entrenamiento. Son métodos construyen varios clasicadores al aplicar el mismo algoritmo de aprendizaje a un conjunto diferente de datos de entrenamiento. Lo importante es establecer un mecanismo adecuado para seleccionar los subconjuntos de entrenamiento.
96 5.5. Construcción de multiclasicadores Manipulación de los atributos de entrada. Consiste en alterar el conjunto de atributos de entrada del algoritmo de aprendizaje. Manipulación de los datos de salida. Modican las clases de los ejemplos del conjunto de entrenamiento. Métodos aleatorios. Introducen componentes aleatorios en los procesos de aprendizaje. Los métodos para construcción de multiclasicadores más habituales son: Bagging. El termino bagging deriva de bootstrap aggregation, que es un mecanismo para generar subconjuntos de entrenamiento seleccionando aleatoriamente y con reemplazamiento (puede haber ejemplos repetidos) una muestra de m ejemplos de entrenamiento del conjunto original de entrenamiento, formado por m ejemplos. Podría esperarse que si usamos siempre el mismo algoritmo de aprendizaje, el modelo obtenido fuese similar en todos los casos, pero hay algoritmos de aprendizaje que son muy sensibles al conjun- to de entrenamiento, como por ejemplo los árboles de decisión. Puesto que obtenemos un conjunto de clasicadores, la nueva predicción se efectúa por votación mayoritaria. Boosting. El mecanismo se basa en la asignación de un peso a cada ejemplo del conjunto de entrenamiento. En cada iteración, el boosting aprende un modelo que minimiza la suma de los pesos de los ejemplos clasicados erróneamente. Los errores de cada iteración se usan para actualizar los pesos de los ejemplos del conjunto de entrenamiento, de forma que aumenta el peso de los ejemplos fallidos y decrementa el peso de los acertados. Existen muchas variantes del algoritmo básico de boosting, siendo el más popular AdaBoost [Freund and Schapire, 1996]. A diferencia de bagging, el algoritmo de boosting no realiza siempre las k iteraciones dado que considera un criterio de parada de acuerdo con el error obtenido. Randomization. Es un método multiclasicador basado en introducir componentes aleatorias en las decisiones internas del algoritmo de construcción de árboles de decisión. La idea consiste en seleccionar de forma aleatoria la
Capítulo 5. Características de la Clasicación Automática 97 partición donde continuar la construcción del árbol entre las veinte mejores particiones. Así pues, se obtiene un árbol distinto en cada iteración. En [Dietterich, 2000b]se encuentra una comparativa experimental de los métodos comentados. 5.6. Métodos híbridos Son métodos de aprendizaje formados por combinación de otros métodos de aprendizaje. Buscan combinar varios métodos de aprendizaje para aunar las ventajas de cada uno. Los más relevantes son: Stacking. Se basa en combinar los modelos generados por diferentes algoritmos de aprendizaje [Wolpert, 1992]. Puesto que cada método tiene una precisión distinta, la votación mayoritaria entre los resultados de los métodos no reeja el resultado óptimo. Una solución es introducir una fase de meta-aprendizaje en el modelo combinado. Con esto intentamos aprender la mejor manera de combinar los modelos base. En el meta-aprendizaje se recibe como entrada las predicciones de los modelos base junto con la clase del problema a aprender. La gura 5.3 muestra el esquema general del stacking [Hernández Orallo et al. , 2004]. DATOS Regresión Lineal Red neuronal SVM Árbol de decisión a1 a2 c0 a1 a2 c0 a1 a2 c0 C0 Cn C2 C1 PREDICCIÓN COMBINADA Figura 5.3: Esquema general de Stacking Cascading. Permite mejorar las características de los árboles de decisión mediante la incorporación de nuevas particiones basadas en otras técnicas de
98 5.6. Métodos híbridos aprendizaje. La idea consiste en usar otros métodos de aprendizaje sobre alguno de los atributos para crear nuevos atributos articiales. Estos nuevos atributos son usados también por el árbol de decisión para generar el modelo. La gura 5.4 muestra el esquema general del cascading [Hernández Orallo et al. , 2004]. DATOS Red neuronal Regresión lineal Árbol de decisión a1 a2 am a1 a2 am a1 a2 am a'n a'1 PREDICCIÓN Figura 5.4: Esquema general de Cascading
Capítulo 6 Diagnosis Mediante Aprendizaje de Modelos Proposicionales 6.1. Introducción La detección de fallos, e identicación de los componentes defectuosos, son tareas muy importantes desde el punto de vista estratégico para las empresas, debido a las demandas económicas y medioambientales que deben cumplir para ser competitivas en los mercados. Estas tareas se vuelven más complejas cuando los sistemas a diagnosticar son sistemas dinámicos. Estos sistemas son muy difíciles de diagnosticar debido al gran número de componentes que lo integran, la poca cantidad de variables observables de que disponen, y la presencia habitual de lazos de control que habitualmente ocultan la presencia de los fallos y hacen más difícil su identicación. Como ya se ha citado en el capítulo 3, existe una amplia variedad de técnicas, basadas en la Inteligencia Articial, que se han venido aplicando al campo de la diagnosis desde hace más de una década [Feng, 1992]: lógica borrosa [Khoo et al. , 2000; Garcia et al. , 2000], redes neuronales [Karpenko and Sepehri, 2002; Seker et al. , 2003], razonamiento basado en casos [Bregon et al. , 2006; Pous et al. , 2003], o conjuntos robustos [Tay and Shen, 2003], entre otras. En [Isermann, 2006] podemos encontrar una revisión de técnicas de diagnosis de fallos que usan métodos de clasicación. Muchos de dichos métodos se encuentran dentro de la diagnosis basada en modelos (Sección 3.3), que basan su diagnóstico en la evaluación de 99
106 6.3. Creación de la base de datos de trayectorias también efectuadas sobre la nueva observación. De esta forma, se generarán para la nueva observación aquellos atributos no presentes en las trayectorias originales. La evaluación de la observación, devolverá una etiqueta del conjunto B , que asociará la nueva observación a un comportamiento del sistema. Dicha etiqueta corresponderá con el diagnóstico del sistema. El proceso de evaluar el modelo deberá ser muy rápido, no necesitando gran capacidad de cómputo ni de almacenamiento. Esto permite que la diagnosis se pueda llevar a cabo en tiempo real, incluso para sistemas cuya frecuencia de muestreo es muy alta y que evolucionan muy rápidamente. Las pocas necesidades computacionales y de almacenamiento, permiten además que los costes en el equipamiento del sistema de diagnóstico sean muy contenidos. 6.3. Creación de la base de datos de trayectorias Partiendo del sistema a diagnosticar, la primera tarea que se debe realizar es seleccionar los estados transitorios que pretenden ser diagnosticados. Recordemos que la metodología se plantea únicamente para la diagnosis de sistemas dinámicos continuos en los estados transitorios, es decir, cuando el sistema necesita cambiar de un estado a otro. Es habitual que dichos cambios se deban a cambios en la consigna o en algún parámetro que regula el funcionamiento del sistema. Por tanto se deberá realizar una selección de los transitorios a diagnosticar, precisando el evento que provoca el cambio de estado. En la gura 6.3 se representan posibles transitorios para una determinada variable observable de un mismo sistema. Tiempo Magnitud Tiempo Magnitud Tiempo Magnitud Tiempo Magnitud Figura 6.3: Distintos transitorios de un sistema
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 107 Una vez seleccionados los transitorios, el siguiente paso será seleccionar los distintos fallos que se pretenden diagnosticar en cada uno de ellos. Los fallos pueden ser derivados de la misma causa para los diferentes transitorios, o pueden ser fallos diferentes para cada uno de ellos. Además, dependiendo de los componentes del sistema que fallen se podrán diagnosticar: Fallos simples: Cuando sólo falla un componente del sistema. Fallos múltiples: Cuando el fallo se deriva de más de un componente del sistema que falla al mismo tiempo. Puesto que los fallos que se pretenden diagnosticar deberán ser reproducidos de alguna forma, podemos realizar la diagnosis tanto de fallos simples como de fallos múltiples. A cada uno de los fallos que se quiera diagnosticar, independientemente de su tipo se le asignará una etiqueta, que será el identicador de dicho fallo durante todo el proceso. Finalmente, para poder realizar la recogida de la información se deberán seleccionar las variables observables del sistema con las que se pretende realizar el diagnóstico. A priori, puede resultar interesante capturar todas las variables observables del sistema, pero dependiendo de cada situación se seleccionarán todas o algún subconjunto de ellas. La gura 6.4 representa diferentes variables observables de un sistema. Las variables seleccionadas serán aquellas que deberán ser monitorizadas durante la fase de diagnóstico. Así pues, antes de comenzar la recogida de la información se necesitan jar: Transitorios durante los cuales el sistema va a ser diagnosticado. Fallos que pretenden ser diagnosticados. Variables observables del sistema que van a ser monitorizadas. Una vez jados los parámetros, se necesita conseguir una colección de trayectorias del sistema, tanto para el funcionamiento exento de fallos como para cada una de las situaciones de fallo. Habitualmente, obtener las trayectorias del sistema cuando este funciona correctamente no plantea ningún problema, pero la obtención de las trayectorias de fallo es otra cosa. Con este propósito, se plantean dos alternativas:
108 6.3. Creación de la base de datos de trayectorias Figura 6.4: Distintas variables observables de un sistema Cuando es posible manipular el sistema para provocar el fallo sin necesidad de dañar el sistema, se provoca el fallo y se recogen las trayectorias . Por supuesto, si el sistema forma parte de una línea de producción o es un subsistema de otro mayor, será necesario aislarlo para no afectar el entorno. Estos son, por ejemplo, los fallos que pueden ocurrir debido a la desconexión accidental de algún componente. También es posible provocar los fallos cuando el sistema a diagnosticar es un producto que va a ser producido en serie en grandes cantidades. En este caso, los fallos pueden ser provocados en algunos prototipos aunque dichos fallos destruyan el prototipo, siempre y cuando los costes lo permitan. De esta forma se obtendrían las trayectorias de fallo. El diagnosticador obtenido en este caso podría servir para todos los productos de la serie. Cuando el fallo no puede ser provocado en el sistema real (porque el sistema resultaría dañado, o sea imposible desconectarlo para realizar los ensayos), se deberá generar un modelo del sistema. Dicho modelo deberá representar dedignamente al sistema y ofrecer como salida los valores de todos los sensores del mismo. En este caso, las trayectorias de fallo no se obtendrían del sistema, sino de las simulaciones de los diferentes fallos en el modelo. Estas dos opciones no son excluyentes, y ambas pueden ser usadas a la vez.
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 109 Finalmente, se añadirá a cada trayectoria recogida la etiqueta representativa con el modo de fallo en que fue obtenida. De esta forma, cada trayectoria se ha transformado en una trayectoria etiquetada . Todas las trayectorias etiquetadas serán almacenadas en las bases de datos etiquetadas , que será el resultado nal de este paso. El número de trayectorias recogidas por cada situación de fallo, o la ausencia del mismo, deberá ser jado a priori. Obviamente, mientras más trayectorias se obtengan, se tendrá más información para inducir el modelo proposicional, aunque puede ocurrir que a partir de un determinado número de trayectorias , las trayectorias adicionales no aporten información signicativa. Además, se deberá tener en cuenta los factores que pueden alterar la evolución de una trayectoria dentro de un determinado comportamiento. Por ejemplo, la temperatura ambiental puede alterar la evolución de una variable del sistema dentro de un comportamiento especíco, produciendo trayectorias ligeramente distintas, a pesar de representar el mismo fallo. Estas situaciones se deberían tener en cuenta, variando, en la medida de lo posible, dichas condiciones para cubrir todo el rango de posibilidades dentro de un mismo comportamiento, obteniendo así un conjunto de trayectorias lo más heterogéneas posible para cada comportamiento. Habitualmente, habrá más de un sensor que monitorice distintos aspectos del sistema durante el transitorio tratado, por ejemplo, valores de presión y temperatura. Se recogerán por tanto las trayectorias de todos los sensores que ofrezcan información del sistema, almacenando las trayectorias etiquetadas en bases de datos etiquetadas por cada variable observable. El resultado nal de este paso será una base de datos etiquetada por cada variable observable del sistema, que contendrá una trayectoria etiquetada por cada situación obtenida con la evolución de dicha variable. El algoritmo 6.1 es el que se sigue para la obtención de la información. Finalmente, obtendremos una base de datos etiquetada por cada una de los transitorios seleccionados y cada una de las variables medidas.
110 6.4. Limpieza, preprocesado y tratamiento de trayectorias Algorithm Recogida_de_información() for t= 1 to total de transitorios a diagnosticar do for c= 1 to total de comportamientos a diagnosticar do for n= 1 to número de ensayos do if comportamiento c es reproducible then Reproducir el comportamiento c else Simular en el modelo el comportamiento c end if for v= 1 to total de variables observables do Recoger trayectoria de la variable v Añadir etiqueta del comportamiento c Almacenar la trayectoria etiquetada en la base de datos etiquetada de la variable v y transitorio t end for end for end for end for Algoritmo 6.1: Algoritmo para la recogida de información 6.4. Limpieza, preprocesado y tratamiento de trayectorias Las bases de datos etiquetadas , resultantes del paso previo, contienen todas las trayectorias recogidas directamente de los sensores. Muchas veces, dicha información es defectuosa, bien por la excesiva presencia de ruido, bien por alteraciones puntuales en la medida, o simplemente por la excesiva información no relevante que presenta. Además, a veces, la simple medida de los sensores no es signicativa para caracterizar el comportamiento del sistema. Por ejemplo, el instante en el que se alcanza el punto de operación, o la forma en que se llega a dicho punto, son más signicativas que la sucesión de valores obtenidos en sí mismos. El objetivo de este paso es doble, por una parte eliminar la gran cantidad de información no relevante presente en las trayectorias . Por ejemplo, en muchos sistemas la presencia de un controlador hace que todas las trayectorias sean muy
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 111 similares cuando se acercan al estado estacionario, independientemente de si hay fallo o no lo hay. Por otra parte, se pretende añadir a dichas trayectorias información no presente y que puede resultar muy útil a la hora de caracterizar su comportamiento. En este sentido, se aplicarán técnicas de limpieza y ltrado de la información, reducción de la dimensionalidad y creación de nuevas características que proporcionen posteriormente más precisión en el proceso de aprendizaje. 6.4.1. Tratamiento de los valores ausentes Una vez leídas las trayectorias , éstas deberían presentar el mismo número de medidas, que dependerán de la frecuencia de muestreo del sensor con las que se adquieren. Pueden existir ocasiones en las que dichas trayectorias presenten ausencias en determinados instantes. Esto es debido a que el sensor, por algún motivo, no ha recogido la medida en un determinado instante. Esto supondría un fallo del sensor. La trayectoria recogida no tendrá por tanto el mismo número de elementos que el resto, y por tanto no es comparable ni útil a la hora de generar el modelo. Existen diferentes alternativas, bien tratadas en la bibliografía, sobre las diferentes posibilidades de tratamiento de los valores ausentes. Las más habituales son: Ignorar la ausencia, lo que supondría asumir la trayectoria como correcta. Eliminar la trayectoria completa. Eliminar el valor ausente del resto de trayectorias . Reemplazar el valor ausente por un valor aproximado que puede ser calculado mediante algún método estadístico con respecto a la propia trayectoria o con respecto al resto de trayectorias . En el caso que nos ocupa el tratamiento seleccionado ante trayectorias con valores faltantes será el de la sustitución de la trayectoria que presente las ausencias por una nueva trayectoria . Esta decisión se justica por varios motivos:
112 6.4. Limpieza, preprocesado y tratamiento de trayectorias No es posible ignorar la ausencia, puesto que la trayectoria no sería comparable con el resto. La eliminación del valor ausente del resto de trayectorias podría suponer una perdida de información mucho mayor que la eliminación de la propia trayectoria . Además, se sabe que hay un valor o varios valores ausentes, pero no la posición de dichos valores. Es posible reemplazar la trayectoria anómala haciendo una nueva captura de datos desde el sistema o el modelo del mismo sin ningún tipo de perjuicio. La sustitución del valor ausente, por un valor aproximado, requeriría el conocimiento especíco del instante en el que se produce la pérdida, y lo único que se conoce es que faltan uno o más valores, pero no el instante de la pérdida. Por otra parte, cualquier sustitución del valor ausente supondría una aproximación no necesariamente válida. Es más, si el número de valores ausentes fuera lo sucientemente elevado supondría un problema en el sensor, y eso por si mismo es un fallo que se escapa del ámbito de aplicación de la metodología. Así pues, cada trayectoria que presente valores ausentes será sustituida por otra trayectoria válida perteneciente al mismo fallo y transitorio. 6.4.2. Escalado y traslación del dominio Hay ocasiones en las que puede resultar conveniente realizar una traslación del dominio de los atributos, bien de valores continuos a discretos o viceversa. En nuestro caso, las trayectorias están formadas por valores continuos de los atributos, que además tienen relación entre sí. Un atributo que precede a otro en la misma trayectoria es el valor de ese mismo atributo en el instante previo. Por tanto, la única traslación aplicable, que sería la discretización de alguno o todos los atributos no tiene sentido en el problema que nos ocupa. Por otra parte, el escalado de las trayectorias provocaría que dos trayectorias que tengan la misma forma (relación entre sus atributos) pero con magnitudes distintas pasasen a ser prácticamente iguales. Para nuestro problema, el escalado haría que se perdiese información, puesto que dos trayectorias semejantes con
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 113 diferentes escalas pueden representar dos situaciones distintas (distintos fallos, o un fallo con respecto a la situación correcta). Lo que hace diferentes a dichas trayectorias es, precisamente, la escala a la que están, e igualarlas supondría hacer ambigua la situación. La gura 6.5 representa dos trayectorias iguales a distinta escala que representan dos situaciones diferentes. Tiempo Magnitud Figura 6.5: Trayectorias semejantes de distintos comportamientos a diferente altura 6.4.3. Filtrado del ruido Habitualmente, las trayectorias recogidas desde los sensores suelen mostrar la presencia de ruido que alteran la medida real de la variable. Las técnicas de ltrado permiten eliminar parte de dicho ruido, aproximando la trayectoria leída a la original. Dependiendo del tipo de ltro empleado y los parámetros de ajuste del ltro, la señal original se verá alterada en mayor o menor medida. Las características que denen un ltro vienen determinadas por los siguientes conceptos: Función de transferencia Con independencia de la realización concreta del ltro (analógico, digital o mecánico) la forma de comportarse de un ltro se describe por su función de transferencia. Ésta determina la forma en que la señal aplicada cambia en amplitud y en fase al atravesar el ltro. La función de transferencia elegida tipica el ltro. Algunos ltros habituales son:
114 6.4. Limpieza, preprocesado y tratamiento de trayectorias Filtro de Butterworth, con una banda de paso suave y un corte agudo Filtro de Chevyshev, con un corte agudo pero con una banda de paso con ondulaciones Filtros elípticos o ltro de Cauer, que consiguen una zona de transición más abrupta que los anteriores a costa de oscilaciones en todas sus bandas Filtro de Bessel, que, en el caso de ser analógico, aseguran una variación de fase constante Se puede llegar a expresar matemáticamente la función de transferencia en forma de fracción mediante las transformaciones en frecuencia adecuadas. Se dice que los valores que hacen nulo el numerador son los ceros y los que hacen nulo el denominador son polos. H(f) = numerador(f) denominador(f) (6.4) El número de polos y ceros indica el orden del ltro y su valor determina las características del ltro, como su respuesta en frecuencia y su estabilidad. Orden El orden de un ltro describe el grado de aceptación o rechazo de frecuencias por arriba o por debajo, de la respectiva frecuencia de corte. Un ltro de primer orden, cuya frecuencia de corte sea igual a (F) , presentará una atenuación de 6dB a la primera octava (2F) , 12dB a la segunda octava (4F) , 18dB a la tercer octava (8F) y así sucesivamente. Uno de segundo orden tendría el doble de pendiente (representado en escala logarítmica). Esto se relaciona con los polos y ceros: los polos hacen que la pendiente suba con 20dB y los ceros que baje, de esta forma los polos y ceros pueden compensar su efecto. Para realizar ltros analógicos de órdenes más altos se suele realizar una conexión en serie de ltros de 1 o 2 orden debido a que a mayor orden el ltro se hace más complejo. Sin embargo, en el caso de ltros digitales es habitual obtener órdenes superiores a 100 .
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 115 Tipos de ltro Atendiendo a sus componentes constitutivos, naturaleza de las señales que tratan, respuesta en frecuencia y método de diseño, los ltros se clasican en los distintos grupos que a continuación se indica. Según respuesta frecuencia Tendremos: Filtro paso bajo: Es aquel que permite el paso de frecuencias bajas, desde frecuencia 0 o continua hasta una determinada. Presentan ceros a alta frecuencia y polos a bajas frecuencia. Filtro paso alto: Es el que permite el paso de frecuencias desde una frecuencia de corte determinada hacia arriba, sin que exista un límite superior especicado. Presentan ceros a bajas frecuencias y polos a altas frecuencias. Filtro paso banda: Son aquellos que permiten el paso de componentes frecuenciales contenidos en un determinado rango de frecuencias, comprendido entre una frecuencia de corte superior y otra inferior. Filtro elimina banda: Es el que diculta el paso de componentes frecuenciales contenidos en un determinado rango de frecuencias, comprendido entre una frecuencia de corte superior y otra inferior. Filtro multibanda: Es que presenta varios rangos de frecuencias en los cuales hay un comportamiento diferente. Filtro variable: Es aquel que puede cambiar sus márgenes de frecuencia. Filtros activos y pasivos Son: Filtro pasivo: Es el constituido únicamente por componentes pasivos como condensadores, bobinas y resistencias. Filtro activo: Es aquel que puede presentar ganancia en toda o parte de la señal de salida respecto a la de entrada. En su implementación se combinan elementos activos y pasivos. Siendo frecuente el uso de amplicadores operacionales, que permite obtener resonancia y un elevado factor Q sin el empleo de bobinas.
122 6.4. Limpieza, preprocesado y tratamiento de trayectorias Algorithm BD _ Normalizada = Normaliza( BD _ Base ) instantes ={} trayectoria = leer desde BD _ Base while ∃ trayectorias en BD _ Base do for s= 1 to total de segmentos de trayectoria do if instante_nalización_segmento( s ) ∈instantes then instantes =instantes S instante_nalización_segmento( s ) end if end for trayectoria = leer desde BD _ Base end while ir al comienzo de la BD _ Base trayectoria = leer desde BD _ Base while ∃ trayectorias en BD _ Base do for t= 1 to total de entradas de instantes do if @ valor( trayectoria ) para instantes(t) then genera nuevo valor para trayectoria en instantes(t) inserta el nuevo valor en trayectoria end if end for almacenar trayectoria en BD _ Normalizada trayectoria = leer desde BD _ Base end while Algoritmo 6.3: Algoritmo de normalización
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 123 canónica tenga el comienzo o nal de un segmento. En la segunda iteración, se generan nuevos segmentos para todos los instantes de tiempo recogidos en la iteración anterior y para todas las trayectorias que no tuvieran un comienzo o nal de segmento en dichos instantes de tiempo. Cada trayectoria normalizada se va almacenando para formar la base de datos normalizada . La generación de nuevos segmentos a partir de los ya existentes es una tarea fácil y rápida. Sólo es necesario aplicar la ecuación de la recta y=mx +n , se calculan m y n para el segmento actual y a partir de ellos se calcula el nuevo valor de y para el nuevo instante de tiempo x . El coste que se debe pagar por el proceso de normalización, es que la dimensión de la base de datos normalizada será siempre superior al de la base de datos canónica . Esto es inevitable, al tener que generar nuevos segmentos en puntos intermedios de segmentos ya existentes. No obstante la nueva base de datos normalizada consigue reducir la dimensión con respecto a la base de datos etiquetada original. Esto se hace posible debido a que al acercarse al estado estacionario, todas las trayectorias son muy similares, y por tanto el proceso consigue una reducción muy importante en esos casos. 6.4.5. Cálculo de nuevos atributos y valores relevantes Muchas veces, la información recogida directamente de los sensores es insu- ciente para diagnosticar el comportamiento del sistema. Existen una serie de valores relacionados con la trayectoria recogida por el sensor que pueden ser más signicativos desde el punto de vista de la diagnosis. A continuación expondremos algunos de ellos. Especicaciones de la respuesta temporal La respuesta en el tiempo de un sistema consiste de 2 partes: Respuesta transitoria: parte de la respuesta total que tiende a cero a medida que el tiempo tiende a innito. Respuesta estacionaria o permanente: parte de la respuesta total que no tiende a cero a medida que el tiempo tiende a innito.
124 6.4. Limpieza, preprocesado y tratamiento de trayectorias Se dene el orden de un sistema cuya función de transferencia es G(s) = n(s) d(s) (6.9) como el grado del polinomio denominador d(s) . Si el sistema que vamos a diagnosticar puede ser tratado como un sistema de segundo orden, existen algunas especicaciones que pueden ser muy útiles a la hora de caracterizar la trayectoria . Un sistema de segundo orden tiene como función de transferencia a la siguiente ecuación: Y(s) U(s)=ω2 n s2+ 2ξωns+ω2 n (6.10) donde: ωn es la frecuencia natural no amortiguada y ξ el coeciente de amortiguamiento. La respuesta del sistema depende de las raíces del denominador (polos del sistema). Para un sistema de segundo orden los polos se expresan como: −δωn±ωn√δ2−1 (6.11) Dependiendo del valor de δ podemos tener los siguientes 3 casos: 1. 0< δ < 1 , polos complejos conjugados en la parte izquierda del plano complejo. En este caso se dice que el sistema es subamortiguado. 2. δ= 1 , polo real repetido. Se dice que el sistema tiene amortiguamiento crítico. 3. δ > 1 , polos reales distintos. El sistema se dice sobreamortiguado. Tal como se observa en la gura 6.8 cuando δ= 0 las oscilaciones continuarán indenidamente. Para valores mayores de δ se obtiene un decaimiento más rápido de las oscilaciones, pero con un ascenso más lento de la respuesta. En el caso en el que δ= 1 , el sistema se torna críticamente amortiguado a tal punto que desaparecen las oscilaciones. Valores mayores de δ producen un sobreamortiguamiento del sistema. En la teoría de control, la caracterización de la respuesta temporal de un sistema se suele hacer mediante lo que se conoce como especicaciones del sistema. Las especicaciones más empleadas son:
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 125 Figura 6.8: Comportamientos de un sistema de 2 º orden Tiempo de retraso (delay time, td ). Es el tiempo necesario para que la respuesta alcance el 50% del valor nal. Tiempo de subida (rise time, tr ). tiempo requerido para que la respuesta crezca del 10% al 90% (sobreamortiguado), del 5% al 95%, o del 0 al 100% (subamortiguado) de su valor nal. tr=1 ωd tan−1·−√1−δ2 δ¸ (6.12) Tiempo de pico ( tp ): Es el tiempo que pasa hasta alcanzarse el primer pico de sobreimpulso. tp=π ωd (6.13) Sobreimpulso máximo ( Mp ): Máximo sobreimpulso es el valor pico máximo de la curva de respuesta medido desde la unidad.
126 6.4. Limpieza, preprocesado y tratamiento de trayectorias Mp=e−(δ/√1−δ2)π (6.14) Si el valor nal de la respuesta es diferente de 1, se utiliza el máximo sobreimpulso porcentual, que está dado por: Mp=e−(δ/√1−δ2)π×100 % (6.15) Tiempo de establecimiento ( ts ): tiempo requerido por la curva de respuesta para alcanzar y mantenerse dentro de determinado rango alrededor del valor nal, especicado en porcentaje absoluto del valor nal (se usa generalmente el 5% o el 2%). Criterio del 2% ts=4 δωn (6.16) Criterio del 5% ts=3 δωn (6.17) Tendencias Consideraremos la tendencia de una trayectoria como la forma en que dicha trayectoria evoluciona en el tiempo, independientemente de los valores absolutos con los que evolucione. Esto es, dos trayectorias que tiendan a subir en los primeros instantes de tiempo tendrán la misma tendencia en esos instantes, independientemente de los valores de la medida del sensor. Para poder usar dicha información en el proceso de diagnosis, necesitaremos añadir dicha información a la trayectoria , con objeto de que pueda ser usada posteriormente. Con este n, se realiza la siguientes denición: Denición 6.8. Comportamiento perfecto . La trayectoria que describe el sistema cuando todos sus componente funcionan de forma ideal, sin desviarse de sus valores nominales. En base a dicha denición podemos calcular las siguientes magnitudes:
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 127 Figura 6.9: Especicaciones de un sistema de 2 º orden Inclinación relativa (IR). Se calcula para cada uno de los elementos de la trayectoria . Determina el grado de inclinación con que la trayectoria llega a ese punto, independientemente de su posición absoluta. Con esto conocemos la pendiente que forma la recta que une dicho elemento con el elemento inmediatamente anterior. Será una medida de lo rápido que aumenta o disminuye la medida del sensor en dicho punto. Representa la derivada de la trayectoria en el punto en que se trata. Se calcula como: IR(i) = Vm[i]−Vm[i−1] ∆t (6.18) donde Vm[i] representa el valor de la trayectoria en el instante i .
128 6.4. Limpieza, preprocesado y tratamiento de trayectorias Cuando se realiza el cálculo de esta magnitud tras el proceso de segmentación de la trayectoria (sección 6.4.4, en realidad estamos obteniendo la pendiente del segmento a la que pertenece dicho elemento de la trayectoria . Distancia al comportamiento perfecto (DP). Se calcula para cada uno de los elementos de la trayectoria . Determina lo lejos o cerca que nos encontramos del comportamiento perfecto. Con esta magnitud se pretende obtener una medida de proximidad o alejamiento, del comportamiento actual, al comportamiento que tendría el sistema si todos los valores de las constantes de los componentes tomaran el valor central del rango en que se considera que el comportamiento del componente es correcto. Se calcula como: DP(i) = Vm[i]−Vmpf [i] (6.19) donde Vmpf [i] es el valor de Vm en el punto i para la trayectoria perfecta. Inclinación relativa a la trayectoria perfecta(IRP). Se calcula para cada uno de los elementos de la trayectoria . Determina la inclinación de acercamiento o alejamiento a la trayectoria perfecta. Esta medida proporciona, para cada uno de los puntos de la muestra seleccionada, la pendiente que tendrá, en cada punto, la trayectoria formada por los puntos que conforman la trayectoria de la distancia al comportamiento perfecto. Se dene como: IRP(i) = DP[i]−DP[i−1] ∆t (6.20) Cambios de tendencia. Se calcula para toda la trayectoria . Indica el número de veces que ha cambiado de signo la inclinación relativa de la trayectoria . Indica el grado de inestabilidad de la trayectoria . Una trayectoria con un valor alto en los cambios de tendencia, estará realizando una aproximación a la referencia de una forma mucho más inestable que otra con menor número de cambios de tendencia.
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 129 6.5. Generación del modelo proposicional El resultado de toda la etapa de tratamiento de las trayectorias es un conjunto de bases de datos normalizadas , que contienen trayectorias normalizadas de todos los comportamientos. Existe una base de datos normalizada por cada transitorio tratado y cada variable recogida. El paso previo a la generación del modelo proposicional es realizar la unión de todas las bases de datos normalizadas correspondientes al mismo transitorio en una única base de datos del transitorio . Denición 6.9. Base de datos del transitorio . Denotamos por Ntv la base de datos normalizada correspondientes al transitorio t y la variable v . Sea b un determinado comportamiento a diagnosticar, denotamos por ntvbi a la trayectoria normalizada correspondiente al transitorio t , variable s y comportamiento b obtenida en la captura i . Para el transitorio t la base de datos del transitorio T contiene la concatenación de todas las trayectorias del mismo comportamiento b con y la misma captura i de cada una de las bases de datos normalizadas de dicho transitorio. La Base de datos del transitorio contiene la concatenación de cada una de las trayectorias normalizadas correspondientes al mismo transitorio, pero a variables distintas. El último atributo de cada entrada resultante será la etiqueta representativa del comportamiento al que caracterizan. Una base de datos del transitorio es un tipo de base de datos transformada . La base de datos del transitorio cumple todas las condiciones para poder realizar aprendizaje automático a partir de la información que contiene. Puesto que se conoce la clase de cada una de las instancias de dicha base de datos (la etiqueta correspondiente al comportamiento), el aprendizaje supervisado es la técnica apropiada para extraer información a partir de dichos datos. La elección de la herramienta de clasicación usada viene determinada por diversos factores intrínsecos al problema que nos ocupa y a los objetivos que se pretenden conseguir. El modelo obtenido debería ser inteligible por los humanos, para poder así detectar cual es la causa que provoca el fallo y actuar en consecuencia.
130 6.5. Generación del modelo proposicional La representación del modelo debería poderse almacenar en poco espacio, lo que permitirá usar dispositivos especícos de coste limitado. La evaluación del modelo debería hacerse de forma muy rápida, lo que requeriría un coste computacional pequeño a la hora de evaluar una nueva observación. Por otra parte, un tiempo de evaluación elevado provocaría que los sistemas de dinámica muy rápida no pudiesen ser diagnosticados on-line . Todos estos condicionantes hacen que la herramienta de clasicación seleccionada sean los árboles de decisión . El motivo por el cual se han seleccionado los árboles de decisión es que el diagnóstico puede ser alcanzado en muy poco tiempo, debido al bajo coste computacional necesario para evaluar estos árboles y la poca necesidad de almacenamiento que tienen. Esto los hace ideales para diagnosticar sistemas de dinámica muy rápida, donde la frecuencia de muestreo es muy alta y los fallos evolucionan muy rápidamente. Esta simplicidad permite, además, que el mecanismo de diagnosis pueda ser implementado y almacenado con unos requisitos técnicos y económicos muy bajos. Por otra parte, los árboles de decisión trabajan muy bien con grandes cantidades de información, tanto si se trata de un gran número de atributos (dimensionalidad), como si se trata de una gran cantidad de ejemplos (cardinalidad). Además, son fáciles de usar, soportan bien la presencia de ruido, son tolerantes a la presencia de atributos no signicativos y poseen una representación simbólica. Por contra, aprenden peor y son menos precisos en el aprendizaje que otros métodos, aunque esto puede ser paliado mediante el uso de otras técnicas como el boosting o el bagging . Diversos trabajos han demostrado la validez de los árboles de decisión aplicados a la diagnosis [Abad et al. , 2002; 2005]. Los árboles de decisión son una forma de representar funciones discretas f(ω) de múltiples variables ω que pueden ser instanciados con diferentes valores reales. El valor de la función será la hoja del árbol, que para el caso que nos ocupa es un comportamiento del sistema. Este será el último paso de la fase o-line , que generará como resultado el árbol de decisión que servirá como módulo de diagnosis. La tabla 6.1 muestra un ejemplo de árbol de decisión. Puede observarse como las condiciones de los nodos se corresponden con valores de las trayectorias en distintos instantes de tiempo, mientras que las hojas del árbol están compuesta
Capítulo 6. Diagnosis Mediante Aprendizaje de Modelos Proposicionales 131 por la etiqueta del conjunto de fallos B , que caracteriza el comportamiento de la trayectoria para los valores de los nodos superiores. Así por ejemplo, val(4) representa el valor de la trayectoria en el instante 4, que será el primer valor seleccionado por el clasicador para asignar la clase. Tabla 6.1: Ejemplo de árbol de decisión Antes de seguir adelante con la generación del árbol, necesitamos dar algunas deniciones. Denición 6.10. Modelo proposicional . Es un árbol de decisión, o conjunto de árboles, obtenidos mediante clasicación de la base de datos del transitorio , de tal forma que dichas estructuras representen una función f:T→B .