Comparación de Modelos Basados en Técnicas de Aprendizaje (página 2)

3.       El tercer capítulo muestra los resultados obtenidos de la aplicación de AD y HC a los dos experimentos escogidos: evaluación de flujo y evaluación de conectividad de un sistema modelado a través de un grafo.

4.       Y para finalizar el cuarto capítulo contiene las conclusiones de la investigación.

CAPÍTULO 1

Confiabilidad

1.1. Generalidades

La palabra confiabilidad tiene una definición técnica precisa: "Confiabilidad es la probabilidad de que un dispositivo realice adecuadamente su función prevista a lo largo del tiempo, cuando opera en el entorno para el que ha sido diseñado [1]. Es decir, la confiabilidad es una medida para describir el desempeño de los sistemas. El  objetivo principal se dirige a lograr una mayor comprensión de las fallas, para la identificación de las mejoras que pueden introducirse en el diseño de los mismos [2].

1.2. Confiabilidad de una red

En la mayoría de los casos un sistema puede ser expresado a través Diagrama de Bloque de Confiabilidad (Reliability Block Diagram o RBD) [3]. En él los componentes están representados por medio de bloques, y sus interconexiones muestran la dependencia operacional del sistema entre sus componentes. En esta representación, las fallas y la operación de cada uno de los componentes se suponen independientes, lo que implica que la falla de uno no afectará el comportamiento de ningún otro, pero si podría o no afectar el funcionamiento del sistema. El sistema de la Figura 1.1, muestra un ejemplo de RBD.

Figura 1.1 Modelo RDB

El  RDB llevado a un sistema de red se representa en la siguiente figura:

Figura 1.2 Modelo RDB representado como una red

La red está conformada por enlaces y nodos, donde un enlace simboliza un componente del sistema y los nodos la unión de los mismos. Existe un nodo origen (s) que se caracteriza por no tener enlaces que llegan a él, y un nodo destino (t) que no tiene enlaces que salen de él. La falla de un componente implica inutilizar el enlace que lo representa.

Para la evaluación de la confiabilidad de una red [4], se han propuesto varios métodos que suponen que el funcionamiento de todos los elementos de algún camino entre (s) y (t), asegura la operatividad del sistema (criterio de continuidad).

Sin embargo, en varias situaciones tales como las redes de telecomunicaciones [6] [7], de computación y de transporte, la conectividad por si misma no es una condición suficiente para asegurar la confiabilidad. En estos casos, el éxito del funcionamiento requiere garantizar un flujo dado, lo cual depende de la capacidad de los elementos involucrados. Así, el funcionamiento de una red es satisfactorio si es posible transmitir con éxito el flujo requerido del nodo origen (s) al nodo destino (t) [8] (criterio de capacidad).

Obtener el universo de datos que definen el comportamiento de un sistema, en muchos casos se transforma en un problema, es por ello que a partir de una muestra de esos datos se genera una aproximación de la Expresión de Confiabilidad (EAC) [9] de una red [10] [11]. Existen muchos métodos que producen una expresión analítica de una función booleana [12] cuyos operadores no son lineales y por lo general son difíciles de entender [17]. Una posible solución a este problema consiste en adoptar métodos de generación de reglas[14] los cuales se fundamentan en un tipo particular de técnicas de clasificación que generan un juego de reglas inteligibles que describen la función booleana a ser reconstruida [15]. Normalmente, las reglas generadas por estos métodos de clasificación toman la forma "if-then", por ejemplo, si X es verdadera y Y es falsa, entonces decimos que el sistema está operativo [16]

En este trabajo de investigación se estudian dos métodos pertenecientes a la familia de generación de reglas, Árboles de decisión y Hamming Clustering. A partir de éstos se produce una EAC para la red utilizada como caso de estudio, al aplicar el criterio de continuidad y de capacidad. 

Se parte entonces de que los componentes del sistema tienen dos estados, operación y falla, y la falla de algún componente es un evento independiente. El estado Xi del i-ésimo componente está definido como:

 (1.1)

El estado de un sistema que contiene n componentes se representa por el vector X

X = (X1, X2, …, Xn)

Para establecer si la red está en estado operativo o fallado, se define la Función de Evaluación (FE):

(1.2)

Para el cálculo de la FE en el criterio de conectividad se propone el procedimiento de búsqueda profunda [Anexo A] y para el criterio de capacidad, la FE puede ser dada por el algoritmo de flujo-máximo corte-mínimo [Anexo B].

En un sistema de n componentes, el comportamiento del sistema completo se describe por la función de estructura FES [1]. La FES es una expresión "booleana" que se representa como una suma de productos donde se incluyen el estado operativo de sus componentes Xi, o el estado fallado  .

Tomando como ejemplo el ejemplo RDB de la Figura 1.1, donde sus componentes y estados están mostrados en la Tabla 1.1. La expresión de la suma de productos para la FES de la red se obtiene por inspección directa,

FES(X) = X1X2 + X1X3

Tabla 1.1 Estados del sistema de la red mostrada en la Fig 1.1

Para facilitar la obtención de la EC correspondiente, la expresión de la FES se convierte en una expresión de términos mutuamente excluyentes, por ejemplo utilizando el algoritmo KDH88 [18]. La FES equivalente, luego de aplicar el procedimiento, queda: 

.

Utilizado el hecho que E(Xi)=Pi , la EC para la red se obtiene sustituyendo cada Xi  con su correspondiente probabilidad Pi y cada complemento  con la probabilidad Qi= 1- Pi

Por consiguiente, la EC para este sistema está dada por:

P1P2 + P1Q2P3.

En este trabajo de investigación se propone una metodología para la obtención de la expresión de confiabilidad, basada en la búsqueda de una función aproximada de la misma, a través de técnicas de aprendizaje automatizado.

1.3. Aprendizaje Automatizado

Una de las tareas más desafiantes en la ciencia de la computación es construir máquinas o programas de computadoras que sean capaces de aprender [19]. El aprendizaje automatizado no sólo se encarga de obtener el conocimiento, sino también de la forma en que éste se representa. A continuación se definen tres conceptos básicos bajo este contexto [20]:

Conjunto de datos: Se distinguen dos tipos, el conjunto de entrenamiento y el conjunto de prueba.

Modelo: o clasificador, es una conexión entre las variables que son dadas y las que se van a predecir. Usualmente las variables que se van a predecir denominadas variables dependientes y las restantes, variables independientes.

Aprendiz: (en ingles "learner"): es cualquier procedimiento utilizado para construir un modelo. En esta investigación estos procedimientos se limitan a programas de computación o algoritmos para construir un modelo a partir del conjunto de datos de entrenamiento.

Desde el punto de vista técnico, el aprendizaje se define como el proceso mediante el cual un sistema mejora y adquiere destreza en la ejecución de sus tareas, y tiene la capacidad de poseer inferencia inductiva sobre éstas [20]. Un modelo de aprendizaje puede caracterizarse por dos cuerpos de información: ambiente y base de conocimiento, y por dos procedimientos: elemento de aprendizaje (aprendiz) y elemento de ejecución (programa de computación), tal y como se representa en la Figura 1.3 [21]:

Figura 1.3 Modelo de aprendizaje

La tarea del elemento de aprendizaje es disminuir la diferencia entre el nivel de la información suministrada por el ambiente y el nivel de la información suministrada por el elemento de ejecución. Esta información puede ser registrada en la base de conocimientos para futuras consultas.

En el aprendizaje inductivo, la acción más importante es promover al modelo para obtener un alto nivel en la exactitud de su predicción. Aplicada esta premisa al aprendizaje automatizado, el objetivo es alcanzar un modelo que sea capaz de predecir con precisión el valor de su función Y, a partir de un conjunto de datos, definidos como vector X, donde los valores se seleccionan de manera aleatoria a partir de todo el espacio de la muestra.

Esto sería trivial si el valor de Y a predecir, estuviese contenido en el conjunto de datos utilizados para entrenar el modelo. La preocupación principal se refiere, a que el modelo también sea capaz de predecir los valores de Y, a partir de los ejemplos que no estuvieron contemplados en el conjunto de datos de entrenamiento.

Existen tres tipos de aprendizaje inductivo [22]:

·         El aprendizaje supervisado: a el aprendiz se le suministra un conjunto de datos de entrenamiento de la forma (Xi,Y), donde Y representa la variable que queremos predecir, y Xi es un vector de valores que constituyen las características relevantes que van a ayudar a determinar el valor de Y. El objetivo del aprendizaje supervisado es obtener una representación general de la función  Y, a partir del vector  X = (X1, X2, …, Xn). El aprendiz debe construir un modelo Y = F(X), de la función no conocida F, que permita predecir los valores de Y. Un modelo inducido siempre se refiere como una hipótesis [23]. En este tipo de aprendizaje existen tres tipos de problemas: los de clasificación, los de regresión y los de predicción.

·         El aprendizaje no supervisado: el aprendiz utiliza un conjunto de ejemplos de entrenamiento, pero cada ejemplo consiste solo en el vector X, y no incluye el valor de Y. El objetivo de este tipo de aprendizaje, es construir un modelo que registre todas las incidencias que se presenten en el conjunto de datos de entrenamiento. La naturaleza de los modelos construidos para los algoritmos basados en aprendizaje no supervisado, varía de un método a otro, ya que pueden, a partir de la data de entrenamiento, dar como resultado una estimación de una función de probabilidad, una estructura o una característica.

·         El aprendizaje reforzado: involucra una tarea intermedia entre el aprendizaje supervisado y el no supervisado. Opera en un ambiente dinámico, y puede tomar acciones que influyen en el ambiente.  Esto permite que el aprendiz aumente su conocimiento, basado en la interacción con el ambiente, y tiene como objetivo que continué aprendiendo.

Esta investigación está orientada a la aplicación de dos métodos,  con base en el aprendizaje supervisado, empleados en problemas de clasificación. El objetivo es obtener un conjunto de reglas a partir de los datos de entrenamiento, de fácil interpretación, las cuales se transforman  finalmente, en una Expresión Aproximada de Confiabilidad (EAC).

2.       CAPÍTULO 2

Algoritmos de aprendizaje automatizado y generación de reglas

2.1. Generalidades

El primer método objeto del análisis comparativo de esta investigación, es un método clásico dentro del AM,  denominado "Árbol de Decisión" (AD) [24]. Este es un método que consiste en dividir de manera recursiva el conjunto de datos de entrenamiento, en función del estado de cada componente del sistema (Operativo o Fallado) y cuyo resultado puede ser expresado como reglas del tipo "If-then".

El segundo método se denomina "Hamming Clustering" (HC) [25]: un método reciente de generación de reglas, el cual consiste en la creación de grupos o "clusters" del conjunto de entrenamiento que pertenecen a una misma clase (Operación/Falla), utilizando como criterio de agrupamiento la "Distancia de Hamming".

2.2. Árboles de decisión:

Los Árboles de decisión (AD), también denominados árboles de clasificación o de identificación, sirven, como su propio nombre lo indica, para resolver problemas de clasificación  y es el método de aprendizaje inductivo supervisado [26] mayormente utilizado, estos se destacan por su sencillez, su dominio de aplicación no está restringido a un ámbito concreto, sino que pueden ser utilizados en diversas áreas de aplicaciones [27].

Los AD cuentan con  una estructura que representa un conjunto de decisiones y usa estrategias de "divides y vencerás" [20] para la búsqueda de una solución. Esto significa que ataca un problema complejo dividiéndolo en problemas sencillos y recursivamente va aplicando la misma estrategia para cada uno de los sub-problemas [28]. La estructura de un AD tal y como se describe como:

• Nodo hoja: el cual indica una clase
• Nodo de decisión: el cual especifica una evaluación del valor de un atributo, a través de una rama y un sub-árbol, para cada posible resultado de la evaluación.

Figura 2.1 Ejemplo de un AD.

La figura anterior, Figura 2.1, es un árbol el cual tiene dos posibles salidas en cada nodo de decisión. En este ejemplo X1 y X2 representan los nodos de decisión y C1 y C2 representan las clases.

Existen varios tipos de AD [29]:

• Según el tipo de Prueba:

-          Multi-variable: Probando atributos de los parámetros de entrada al mismo tiempo

-          Univariable: cuando se prueba solo un atributo.

• Según los resultados:

-          Cuando durante la prueba pueden darse dos o más resultados. Así, si todas las pruebas tienen dos posibles resultados, entonces tenemos un árbol binario.

• Según las características o atributos:

-          Categóricas

-          Numéricas

• Según el número de clases:

-          Si tenemos dos clases y los datos de entrada son binarios, el árbol implementa una función booleana y se denomina AD booleano

A efecto de esta investigación, la información aquí referida se limitará a la última clasificación, AD booleano.

Un AD booleano produce una función de la Forma Normal Disyuntiva (FND) [10], el AD se va construyendo hacia abajo: cada nodo está asociado con un componente de la red, cuyo estado es examinado. Cada nodo comienza con dos ramas, que corresponden a los dos estados disponibles en cada componente. Cada nodo terminal o nodo-hoja está asociado con una clase, la cual determina el estado de la red: operativa, fallada.

Por convención, la rama que corresponde al estado fallado del componente, se posiciona a la izquierda y la rama que corresponde al estado operativo a la derecha, según se muestra en la Figura 2.2.

Figura 2.2 Convenciones en un AD

Cuando se hace una nueva evaluación, el algoritmo chequea si el componente X1 está operativo o fallado. Si el estado es fallado, se selecciona la rama izquierda y se concluye el caso C1. Si X1 está operativo, se hace una evaluación en el componente X2, si está operativo, se concluye el caso C1 y si está fallado, concluye el caso C2 [30].

Formalmente, un AD es un grafo acíclico, donde los arcos tienen una sola dirección y los ciclos no están permitidos. Se comienza con un nodo y la dirección del grafo no puede regresar al mismo nodo. Cada uno de estos nodos están etiquetados con una clase y se asocian con los estados de los componentes que generan una rama para cada posible resultado [31].

Durante la construcción de un AD a partir de un conjunto de datos, es lógico tratar de obtener el árbol más pequeño, es decir, con el menor número de nodos posibles que perfectamente clasifique el conjunto de datos de entrenamiento. Debido a la elevada cantidad de tiempo y recursos que demanda la ejecución de los algoritmos para la construcción de los AD con datos reales, se hace prácticamente imposible la construcción del todos los posibles AD, para luego seleccionar el mínimo, lo que se convierte en un problema "NP-Completo" [24]. Por esta razón los algoritmos recurren a la heurística para la búsqueda exploratoria del AD, la cual se ejecuta localmente a través del método de búsqueda anticipada de un paso  ("one-step look-ahead") [41].

Esta estrategia de búsqueda en escalada sin retroceso ("hill-climbing without backtraking") [41], tiene sus desventajas, ya que incrementa en cada paso la complejidad del AD, haciéndolo susceptible a riesgos de convergencia. Esto significa que se puede conseguir una solución local óptima, que no corresponde a la solución global óptima.

Una de las características más importantes de los AD, es que pueden ser transformados fácilmente en un conjunto de reglas, convirtiendo cada camino del árbol en una regla, como se explica seguidamente:

• Los nodos internos del árbol y su respectiva rama se convierten en la condición de la regla ("if-part")

• Las hojas de los nodos se convierten en la consecuencia de la regla ("then-part")

En el caso de la Figura 2.2, las reglas generadas a partir del AD corresponden a dos reglas asociadas al nodo C1  y una sola regla en el nodo C2.

De esto se deduce que un AD produce un conjunto de reglas de decisión mutuamente excluyentes. La condición en la ("if-part") está conectada a través de una operación AND, a pesar de que las diferentes reglas están agrupadas en una estructura if-then-else.

2.2.1. Construcción del árbol

La construcción de un AD se realiza mediante un algoritmo que, utiliza la partición recursiva del conjunto de datos de entrenamiento y está  basado  en:

ü       Inicialmente toma un conjunto de ejemplos (el conjunto de datos de entrenamiento T ). Si todos los ejemplos en T pertenecen a una clase C entonces el AD es una hoja que identifica a la clase C.

ü       Considera todas las posibles pruebas que dividan a T en dos o más sub-conjuntos, y califica cada prueba de acuerdo con qué tan bien separa el conjunto de datos.

ü       Escoge la prueba que logre la mejor calificación.

ü       Divide el conjunto de datos en sub-conjuntos y ejecuta de nuevo este proceso de  manera recursiva para cada sub-conjunto.

La manera de construir un AD de forma descendente y recursiva es de donde proviene el origen del acrónimo TDIDT "Top-down Induction of decision tree" [31], que se utiliza para referirse a la familia completa de algoritmos de construcción de AD.

Cuando se escoge un nodo, se considera el sub-conjunto de datos de entrenamiento que pertenece a cada clase (operativo o fallado). Si todos los datos pertenecen a una clase o se verifica alguna "regla de parada", entonces el nodo se convierte en una hoja del árbol. Si no se convierte en un nodo hoja, se repite el procedimiento a cada sub-conjunto, hasta conseguir un nodo hoja.

2.2.2.       Reglas de división [32]

Una regla que divida el conjunto de datos de entrenamiento en al menos dos sub-conjuntos no vacíos conducirá a la construcción de un AD. Sin embargo se deberá considerar que, el objetivo del proceso de construcción de un AD, es obtener un árbol que haga una buena estimación a la hora de hacer las predicciones.

La selección del nodo raíz del AD, se hará mediante alguna heurística, que viene a desempeñar un papel esencial en la construcción del árbol, ya que intenta favorecer las divisiones que mejor discriminan unas clases de otras.

Ejemplos muy conocidos de estas heurísticas son [33]:

ü       Medidas de la diferencia entre el nodo padre y el sub-conjunto de división, sobre alguna función de proporción de clases, como por ejemplo la entropía.

ü       Medidas de la diferencia entre el nodo padre y el sub-conjunto de división sobre alguna función de proporción de clases, dado por una distancia o por un ángulo.

ü       Medidas estadísticas de independencia, como la Chi Cuadrado, entre la proporción de clases y el sub-conjunto de división.

En esta investigación el método a usar para la construcción del AD es el C4.5, una versión mejorada del ID3, desarrollado por Quinlan [29]. El costo computacional del AD es O(n log2 n) donde n es el número de enlaces que componen la red.

Sea P el número de estados en que el sistema opera y N el número de estados en que el sistema falla, los cuales están contenidos en el conjunto de datos de entrenamiento. La información esperada se define por la siguiente expresión:

       (2.1)

Si se selecciona el componente A con k diferentes valores, se define el valor esperado de la información contenida A como:

                                         (2.2)

Donde Pi y Ni son los números de instancias para cada clase en el sub-árbol asociado con la partición basada en los valores del atributo A. Para  nuestro caso k es 2, correspondiente a los dos estados (operación y falla) de los componentes del sistema en estudio. La ganancia de información lograda es [33]:

Ganancia(A,P,N) =–                (2.3)

La heurística selecciona aquel componente con la máxima ganancia de información.

2.2.3.Ejemplo

Considere el sistema mostrado en Figura 1.1 y la Tabla 1.1 del capítulo anterior, en la cual se listan los estados para cada componente con el correspondiente estado del sistema.

Hay tres estados de operación (P=3)  y cinco estados fallados (N=5), para el conjunto propuesto. A partir de los estados podemos obtener la información esperada:

Para cada uno de los componentes se tiene:

Componente X1

Para X1=0 hay cero estados en operación P=0 y cuatro estados fallados N=4 y para X1=1, hay tres estados en operación P=3 y un estado fallado N=1, de aquí:

Por lo tanto se obtiene:

Ganancia(X1, 3,5) =I(3,5)-=0.954434-0.405639=0.548795

Componente X2

Para X2=0, hay un estado en operación P=1 y tres estados fallados N=3 y para X2=1 hay dos estados en operación P=2 y dos estados fallados N=2, a partir de esto se tiene:

Ganacia(X2,3,5)= 0.954434-0.905639=0.048795

Componente X3

Para X3=0, se tiene un estado del sistema operativo P=1 y tres estados fallados N=3 y para X3=1 hay dos estados en operación P=2 y dos estados fallados N=2, a partir de esto se tiene:

Ganancia(X3,3,5)=0.954434-0.0.905639=0.048795

En resumen se obtiene la Tabla 2.0, mostrada a continuación:

Tabla 2.0 Ganancia de la Información

Como X1 obtiene la mayor ganancia (0.548795) de información, es el primer componente a ser considerado para la primera selección como nodo raíz.

Se puede observar que el sub-conjunto de ejemplos obtenidos para X1=0 contiene solamente estados fallados, de allí se puede obtener la siguiente regla, "If X1=0 then Y=0".

Para X1=1 el proceso se repite, considerando que el sub-conjunto contiene tres estados del sistema en operación y un estado del sistema fallado, como se muestra en la Tabla 2.1

Tabla 2.1   Estados para X2 y X3

Se realiza el mismo proceso para X2  y X3. En ese caso se obtiene:

Ganancia(X2,3,1) = Ganancia(X3,3,1) = 0.311278

En consecuencia a este resultado es indiferente escoger el componente 2 o el componente 3 como siguiente nodo.

El árbol generado por el algoritmo anterior queda entonces reflejado en la Figura 2.3: X1  fue el componente escogido como nodo raíz, el cual tiene la mayor ganancia (ver Tabla 2.0, Ganancia de la información) y corresponde a un corte mínimo y posteriormente fue escogido X2 y por último X3

Figura 2.3 AD generado por el algoritmo.

2.2.4. Post-poda [43]

Una vez construido el AD, las reglas de poda o post-poda, tienen como objetivo eliminar los subárboles que no contribuyen significativamente o no agregan valor a la clasificación [20]. De hecho, el método recursivo de construcción de AD continúa dividiendo el conjunto de entrenamiento hasta encontrar un nodo hoja o nodo puro [34]. En muchos casos el resultado suele ser un árbol muy complejo, que "sobre ajusta" los datos del conjunto de entrenamiento, efecto conocido en inglés con el término "overfitting". Esto constituye un problema y afecta al modelo de clasificación generado.

La post-poda se suele aplicar después de construir el árbol completo para simplificarlo, eliminando un sub-árbol completo a favor de una única hoja, o sustituyendo un sub-árbol por una de sus ramas más usada.

Uno de los métodos de post-poda más usado, está basado en dos medidas de errores [35]:

• La medida del error estático corresponde al número de  clasificaciones erradas, considerando que todos los datos que llegan al nodo se clasifican con la clase que más se repite en ese nodo. El error relativo de un nodo Xi viene dado por , donde C es la clase más preferida en ese nodo.
• La medida del error acumulado corresponde a la suma de las clasificaciones erradas de todos los subárboles del nodo en evaluación.

Si el error acumulado es mayor o igual al error estático, entonces el nodo es remplazado por la hoja correspondiente a la clase que más se repite en el nodo..2.5.Pre – poda

La simplificación de un árbol durante su construcción se denomina pre-poda y está basada en reglas que detienen la construcción del AD, con la finalidad de evitar el crecimiento de ramas que no agregan valor a la exactitud de la predicción del árbol [20]. Por lo general este tipo de reglas tratan de predecir si se debe seguir construyendo el árbol o no.

En la pre-poda, se define una hoja a la que se le puede asignar una distribución de probabilidades o se selecciona la clase (operativo o fallado) obtenida con mayor frecuencia por el algoritmo. Se ha demostrado empíricamente que esta última técnica es la más apropiada para minimizar el error de clasificación [33].

En el ejemplo desarrollado en la sección 2.2.3, es evidente que ni los nodos ni las ramas pueden ser removidos del AD mostrado en la Figura 2.3. Debido a esto, la fase de poda para el AD generado previamente no tiene ningún efecto, ya que perfectamente éste representa todas las configuraciones, mostradas en la Tabla 1.1 del capítulo 1.

2.3.          Hamming Clustering

El algoritmo denominado Hamming Clustering (HC) [37], es una nueva técnica para inducción de reglas en problemas de clasificación. Los resultados teóricos aseguran que HC tiene un costo computacional polinomial de , donde n es la dimensión del espacio de entrada, número de enlaces en la red, s es el tamaño del conjunto de entrenamiento y c es el número de componentes del sistema [36]. Las reglas generadas por este método van a conformar los términos de la aproximación de la FES del sistema de red en estudio.

2.3.1. Procedimiento de HC

Sea S un conjunto de datos de entrenamiento que contiene s ejemplos (Xj,Yj), j=1,…,s, asociado a un problema de clasificación binaria [36] [37]. El patrón de entrada Xj tiene n componentes booleanos, denotados con Xji, para i=1,….,n. Los valores enteros 0 y 1 serán utilizados en lo sucesivo para denotar los dos estados binarios, 1 como operativo y 0 como fallado. Esta definición permite señalar que el patrón de entrada está dado por , ubicados en los vértices de un hiper-cubo n-dimensional centrado en el origen del espacio [38].

Para simplificar la notación, un vector binario se representa por una cadena de caracteres con los siguientes símbolos "+" y "-", correspondiente a 1 y 0 respectivamente; de esa forma la siguiente cadena de caracteres "- – + -"se refiere al vector (0,0,1,0).

De igual manera, se asocia una función booleana a este problema de clasificación de la siguiente manera:, a partir del valor de esta función   se subdividen los vértices del hiper-cubo  en dos sub-conjuntos y , de acuerdo con las siguientes expresiones:

A partir de estas expresiones  y

El conjunto de datos de entrenamiento  se divide en dos sub-conjuntos  y  [36]:

De lo anterior se obtiene

La principal característica de HC es generar un conjunto de reglas consistentes, que resuman el comportamiento de la aproximación de la FES en un tiempo computacional razonable.

El algoritmo HC procede por patrones, donde una muestra de un conjunto de datos de entrenamiento se escoge de manera aleatoria en cada iteración y uno o más grupos o "clusters" se generan en el espacio de entrada y luego se asignan a una misma clase. Este método puede trabajar a partir de muestras que pertenecen a diferentes clases, lo que hace que la generación de reglas esté basada en un tipo de aprendizaje competitivo.

La siguiente definición juega un rol básico para la determinación de los "clusters", sea In  el conjunto {1,2,…,n} de los primeros enteros positivos.

Sea el patrón de entrada y un conjunto de subíndices de sus componentes con el tamaño . El conjunto viene dado por:

 para todo

Y se le llama cubo-l o cubo simple con vértice X  y generador L.

Los elementos escogidos del conjunto Cl (X,L) son exactamente 2l y se colocan en los vértices de un hiper-cubo l-dimensional en el espacio de entrada. En particular, se obtiene la siguiente relación:

 ,                 

A todo cubo-l Cl (X,L) puede asociársele una operación AND que da como resultado 1, sólo cuando los patrones de entrada contenidos en Cl(X,L) le son presentados. Esto es suficiente, para ejecutar el producto lógico de los componentes que tienen los índices , posiblemente precedidos por la operación NOT si Xi=0.

Esta propiedad se explota por HC, para obtener como resultado el conjunto de reglas. Durante el proceso de entrenamiento los cubos en el espacio de entrada se generan empleando los vértices como muestras aleatorias escogidas en el conjunto de datos de entrenamiento.

El correspondiente generador L, se determina adoptando el criterio apropiado que tiende a mejorar la habilidad de generalización. De esta manera, se construyen dos conjuntos de cubos C+ y C-, los cuales aproximan los conjuntos H+ y H- asociados a la función booleana desconocida .

La aproximación que hace el método de HC está basada en una propiedad presente en muchos problemas de clasificación de la vida real: mientras más pequeña es la distancia de "Hamming" entre dos patrones de entrada, es mayor la probabilidad de que pertenezcan a la misma clase. La distancia de "Hamming" es el número de bits que difieren en las dos cadenas X y Z y el cálculo viene dado por:

                        2.5

De acuerdo con la definición si X= "01101" y Z= "11001", entonces dH(X,Z)=2.

El algoritmo HC agrupa cadenas binarias que pertenecen a la misma clase y están cerca unas de otras, de acuerdo con esta distancia.

Un concepto básico en el procedimiento seguido por HC es la definición de "cluster", el cual corresponde a una colección de todas las cadenas binarias que tiene el mismo valor fijo en el sub-conjunto de componentes. Como ejemplo tenemos las siguientes cadenas binarias [2] "01001", "01101", "01101" y "01101" que forman un "cluster" ya que todas ellas tienen el valor 1, 0 y 1 en el segundo, el cuarto y el quinto componente respectivamente. Este "cluster" es usualmente escrito de la manera "*1*01", remplazando el símbolo "no importa" (don"t care) ("*") en la posición en donde los valores varían, de esto se dice entonces que el "cluster" "*1*01" "cubre" las cuatro cadenas binarias mostradas anteriormente.

Cada "cluster" puede estar asociado con un producto lógico a partir de los componentes de X, que definen el estado operativo del sistema. Por ejemplo el "cluster" "*1*01" corresponde al producto lógico , siendo  el complemento de X4. La función booleana deseada se puede construir generando una colección valida de clusters para las cadenas binarias pertenecientes a la clase seleccionada. Esta colección es consistente, sí ninguno de los "cluster" incluyen cadenas binarias que pertenezcan al conjunto de datos de entrenamiento asociados a la clase opuesta.

2.3.2. Descripción del algoritmo

El procedimiento empleado por HC consiste en los cuatro pasos siguientes:

Hamming Clustering

1.-      Se escoge un ejemplo (X,Y) de manera aleatoria del conjunto de datos de entrenamiento S.

2.-      Se construye un "cluster" de puntos incluyendo X y se asocia a la clase Y.

3.-      Se remueve el ejemplo (X,Y) del conjunto de datos de entrenamiento. Si la construcción no ha sido completada, es decir, si en la muestra de de datos de entrenamiento aún hay datos que no están representados por el conjunto de "clusters" construidos, se va al paso 1.

4.-      Se simplifica el conjunto de "cluster" generados y se construye la correspondiente función booleana.

Figura 2.4 Algoritmo HC

Una vez que el ejemplo (X,Y) se selecciona del conjunto de datos de entrenamiento, de manera aleatoria en el paso 1, se genera un "cluster" de puntos y se asocia a la clase Y. La única consideración que se debe cumplir para la construcción de este "cluster", es que no debe contener cadenas que pertenezcan a los ejemplos del conjunto de datos de entrenamiento que tengan la clase opuesta, es decir de 1-Y. Como sugiere el principio de Parsimonia de Occam"s Razor [39], mientras más pequeña es la expresión de la suma de productos de la función booleana, el tiempo para la obtención de resultados es menor. Esto lleva a preferir "clusters" que cubran, tanto como sea posible, el tamaño del conjunto de datos de entrenamiento de la clase Y, y que las cadenas binarias contengan más símbolos del tipo "no importa".

De cualquier manera, la búsqueda de un "cluster" óptimo lleva a la solución de un problema NP-completo [24], y para evitar esto existen dos procedimientos:

ü       El método para la generación de cubos en HC y

ü       El método de generación de cubos con el criterio del cubo más grande.

A efectos de está investigación sólo se tomo en cuenta el segundo método indicado.

El núcleo computacional de HC está dado por la generación de los "clusters" con un vértice en el patrón de entrada X, seleccionado en el paso 1 del algoritmo mostrado en la Figura 2.4. Suponiendo , y ya que C+ y C- se construyen en forma incremental, la separación de los datos entre una clase y otra se mantiene si el cubo-l Cl(X,L) generado en la iteración en curso satisface las siguientes dos condiciones:

, ,

para cada                                                 (2.5)

Las condiciones anteriores no son excluyentes, de hecho, si C- no es vacío, cada cubo  tiene elementos comunes con . Para evitar chequeos redundantes de consistencia, se consideran los conjuntos  y, que contienen los patrones de entrada que cubren los "clusters" contenidos en C+ y C- :

Sea  y, el sub-conjunto de  y . Este sub-conjunto no se solapa con los elementos de C+ y C- respectivamente,

La condición (2.5) puede ser fácilmente escrita en términos de  y

,                             (2.6)

El procedimiento empleado por HC para la generación de un cubo con un vértice en , es descrito en la Figura 2.5 donde se denota Xj, para j+1,….., , el j-ésimo elemento del conjunto , y con , j=+1,…., +, los cubos incluidos en

Método para la generación de cubos en HC

1.       Se calcula la y la distancia de "Hamming" dj, para j=1,..,, entre X y los patrones . Sea  el sub-conjunto de In que contiene los subíndices dj, de los componentes de X que difieren en Xj.

                   , para j=1,.., .

2.       Se calcula la , la distancia de "Hamming" dj, para cada  j=+1,..,+, entre X y los cubos . Sea  el sub-conjunto de   In Kj conteniendo los índices dj de los componentes X que difieren en uj.

      ,    

      para j= +1,…., +

3.  Se extrae el sub-conjunto  tal que  para cada

 j= +1,…., +. El cubo-l  Cl(X,L) satisface la condición (2.4)

Figura 2.5 Método para la generación de cubos en HC

En el paso 1, se calcula la distancia de "Hamming" dj entre el patrón de entrada X previamente escogido y los elementos de . El conjunto  , con j=1,.., , contiene los índices de los componentes que difieren entre X y .

Una actividad similar se ejecuta en el paso 2, para obtener la distancia de "Hamming" dj, para j=+1,..,+, entre X y los cubos .

El conjunto asociado a los índices de  están directamente determinados por los valores enteros tomados en para todos los .

La construcción de un cubo-l Cl(X,L), verificando las condiciones expresadas en (2.6), se ejecuta en el paso 3 y se encuentra un generador L el cual satisface la siguiente condición:

 para cada j=+1,..,+,                                         (2.7)

La veracidad de la aproximación se asegura a través del siguiente teorema [37]

Teorema: El cubo-l Cl(X,L), con , verifica la condición  (2.6), sí y solo sí, el generador L es tal que  para cada j=+1,..,+.

Como una consecuencia de la expresión (2.7), si un conjunto  contiene sólo un elemento, ese índice debe ser incluido en el generador L del cubo a ser construido. La amplia libertad en la escogencia de este generador, permite definir criterios adicionales que influyen en la habilidad de generalización del conjunto de reglas resultantes.

Para esta investigación se ha seleccionado, la técnica de "Máximo Cubrimiento" (MC) sobre el cubo [36], descrito en el algoritmo de la Figura 2.6, donde se observa que de manera iterada se incluye el símbolo de "no importa" en la posición donde la distancia de "Hamming" es mayor, a partir del conjunto de datos de entrenamiento que pertenecen a la clase Y, y a su vez, evita cubrir los ejemplos de entrenamiento que están asociados con la clase opuesta.

Generación de "clusters"con el criterio de máximo cubrimiento sobre el cubo

1. Se construyen los conjuntos , conteniendo los índices de los componentes que difieren en X y en los elementos :

         , para  j+1,..,r+

            Sea L=0 y l=0.

2. Sea J el conjunto de los índices  tal que se genera (l+1)-cubos y satisfaga la condición  para cada j=+1,..,+   Si J=0  la construcción del cubo-l Cl(X,L) es concluida.

3. Se encuentra , el cual está incluido en el número más grande de conjuntos  asociado con el patrón de salida . Se adiciona i a L y se hace l=l+1 , ir al paso 2.

Figura 2.6 Generación de "clusters" criterio de máximo cubrimiento

A través de la repetición de los pasos 1 y 2 de HC de la Figura 2.4, se construyen dos conjuntos de cubos C+ y C-, que generalmente contienen elementos redundantes que pueden ser removidos sin ningún cambio en el comportamiento del conjunto de reglas resultantes. De esta manera, una fase de poda puede ser útil para optimizar la complejidad de la forma final.

Si se aplica HC a la red representada en la Figura 1.1 (Modelo RDB),  y se toman los datos de la Tabla 1.1 (Estados del sistema de la red), referenciados en el Capítulo 1, se obtiene la siguiente información:

2.3.3. Ejemplo

Primera iteración

Se tiene que  y

Entonces  y

Se escoge un  por ejemplo X1="+ – +" y se calcula , de donde se obtiene:

,  y se deduce J={2,3}, ya que 2 está incluido en todos los , es extraído y se dice que L={3}, de esto se obtiene el primer cubo-l Cl(X,L) = C1 = ("+ – +", 3) = "+ * +" se recalcula y se alcanza el primer elemento de C+.

Segunda iteración

Se escoge de nuevo un  X2="+ + -" y se calcula , se obtiene:

,         y se deduce J={3}, y se dice que L={3}, se obtiene el segundo cubo-l Cl(X,L)=, se recalcula y se alcanza el segundo elemento de C+.

Con se logra el criterio de parada del algoritmo y del conjunto de "clusters" generados se construye la correspondiente FES.

2.3.4. Poda del conjunto de "clusters"

Por lo general la repetición de los pasos 1, 2 y 3 de la Figura 2.4 lleva a obtener redundancia en el número de "clusters" escogidos. Simplificando este proceso, se puede mejorar la exactitud en la predicción de la función booleana, utilizando algoritmos de poda para reducir la complejidad en el resultado de la expresión de suma de productos, así como se aplican en los métodos de árboles de decisión. En la siguiente definición, se describe  el proceso de poda:

Definición: El conjunto Q esta dado por:

Este conjunto será llamado conjunto de cubrimiento del cubo-l Cl(X,L). El número q del patrón de entrada contenido en Q será nombrado cubrimiento de Cl(X,L).

Para minimizar el número de reglas generadas por HC, se selecciona de C+ y C- un conjunto reducido de "clusters"que satisfagan todos los pares de entradas-salidas, contenidas en el conjunto de entrenamiento  . Para este fin se escogen los cubos que tengan un máximo de cubrimiento, para lo cual se utilizan dos reglas diferentes en la programación de este algoritmo: la poda mínima y umbral de poda (para este caso se hará referencia sólo a la poda mínima).

En la poda mínima, la manera más sencilla y efectiva de reducir el tamaño de C+ y C- es encontrar el número mínimo de cubos que clasifican correctamente todos los patrones de entrada en S. El  procedimiento consiste en extraer los cubos conformados por "clusters" que cubren el máximo número de ejemplos de los datos de entrenamiento en S, y en la próxima iteración sólo se consideran aquellos "clusters" que no fueron seleccionados en los cubos anteriores.

En el siguiente capítulo se muestran los resultados obtenidos de la aplicación de los algoritmos AD y HC a partir de dos experimentos seleccionados: evaluación de capacidad y evaluación de conectividad. Estos resultados generarán una EAC para cada experimento por cada uno de los algoritmos, para posteriormente proceder a su evaluación y así determinar que tan buena es la aproximación a partir de la comparación directa con la EC del sistema en estudio.

CAPÍTULO 3

EXPERIMENTOS

2.4.    Generalidades

El propósito en este Capítulo, es obtener una Expresión Aproximada de Confiabilidad (EAC) permite evaluar la confiabilidad del sistema, entre el nodo origen (s) y el nodo destino (t). Cada enlace tiene una confiabilidad ri y una capacidad de 100 unidades de la red en estudio.

La red mostrada en la Figura 3.1 ha sido tomada como ejemplo para obtener la EAC a partir de los dos métodos de clasificación descritos en el capítulo anterior (AD y HC). Para cada método se obtiene una EAC por cada criterio definido, el de continuidad y el de capacidad.

Figura 3.1 Red para caso de prueba [40]

Para aplicar los métodos de clasificación (AD o HC), a efecto de generar una EAC, en primer lugar, es necesario encontrar un conjunto de datos (X,Y), donde Y = FE(X). Parte de estos datos son  usados en la etapa de entrenamiento, y el restante en la evaluación del conjunto de reglas generadas.

Se define el tamaño de la muestra ND, comprendido por dos subconjunto de datos, NT como los datos de entrenamiento y NE los de prueba, es decir ND=NT+NE. Cada dato de entrenamiento o prueba está representado por X=(X1, X2, ….,Xn), donde n es el número de enlaces que contiene la red.  Para la red tomada como caso de prueba (figura 3.1), el número de enlaces corresponde a 21.

La muestra se selecciona de la siguiente manera:

1.       Por cada Xi del vector X se toma un valor aleatorio a partir de una distribución uniforme (0,1).

2.       Si el valor obtenido está comprendido entre 0 y 0.5 se le asigna a la variable Xi el valor 0, y si está comprendido entre 0.5 y 1 se le asigna el valor 1.

3.       Este proceso se repite para cada uno de los 21 componentes del vector X.

4.       Finalmente una vez obtenido el vector X, para saber si el estado del sistema está operativo o fallado, evalúa  la FE(X).  Para el criterio de conectividad se usa el procedimiento de búsqueda profunda [Anexo A] y para el criterio de capacidad, se usa el algoritmo de flujo-máximo corte-mínimo [Anexo B].

Una vez obtenido el primer dato de la muestra, se repiten los pasos 1,2,3 y 4 ND veces.

La relación entre NT y NE, en cuanto al número de datos, se define con la proporción NT = 2NE, según sugerencia de Torgo [16].

Los NT datos se usan para conformar el conjunto de entrenamiento, y los de NE, para evaluar el comportamiento del modelo.

Con los NT  datos se entrena al algoritmo. Este genera la aproximación de la FES(X) ó modelo para cada criterio (continuidad y capacidad) y posteriormente es probado con los NE  datos.

Finalmente obtenidos los resultados de los algoritmos, estos se evalúan de acuerdo con un estándar que depende de tres medidas: sensibilidad, especificidad y exactitud.

Los resultados en la evaluación del modelo se muestran en la Tabla 3.1 y se define cada una de las variables contenidas en estas tres medidas.

Tabla 3.1 Matriz de confusión

Las definición de estas variables es:

• VP corresponde al número de ejemplos que pertenecen a la clase Y=1, es decir, estado operativo del sistema clasificados correctamente.
• FN corresponde al número de ejemplos que pertenecen a la clase Y=0, es decir, estado fallado del sistema clasificados incorrectamente.
• FP corresponde al número de ejemplos que pertenecen a la clase Y=1, es decir, estado operativo del sistema clasificados incorrectamente.
• VN corresponde al número de ejemplos que pertenecen a la clase Y=0, es decir, estado fallado del sistema clasificados correctamente.

La Medida de Sensibilidad: Es la probabilidad de clasificar correctamente un dato de la muestra que pertenece al estado operativo del sistema.

La Medida de Especificidad: Es la probabilidad de clasificar correctamente, un dato de la muestra que pertenece al estado fallado del sistema.

La Medida de Precisión: Da una evaluación general del modelo.

Altos valores de estas tres medidas definen un alto nivel de confianza del modelo generado por el algoritmo

2.5.        Experimentos

2.5.1. Evaluación de Conectividad

En el caso de la evaluación de conectividad, la red se considera operativa sí al menos hay un camino entre el nodo origen (s) y el nodo destino (t).

La EC se obtuvo usando el software "APACRO" [41], que determina el conjunto de caminos mínimos. Para la red en estudio, se encontraron 18 caminos mínimos y a partir de éstos, se generó la EC con 105 términos.

El espacio de los estados viene dado por 221 posibles valores, que corresponden a los 21 enlaces que conforman la red, y a los 2 posibles estados que puede tomar esta; operativo o fallado. De los 2.097.152 estados, resultado de 221, se generó, de manera aleatoria, un conjunto de 3000 diferentes pares (X,Y), X=(X1,…X21).

Los primeros NT=2000 pares, se utilizan para entrenar al algoritmo que clasifica  (AD y HC) y los NE=1000 pares restantes se utilizan para probar los modelos generados por cada uno de los métodos de clasificación.

2.5.1.1. Ejecuciones de los Algoritmos AD y HC para el caso de Evaluación de Conectividad

El primer paso consiste en entrenar los Algoritmos de AD y HC a partir de los datos seleccionados para tal fin. Posteriormente se generan el conjunto de reglas para ser evaludas  con los datos de prueba.

De esta evaluación se obtuvo:

ü       La matriz de confusión,

ü       Las medidas de sensibilidad, especificidad y precisión calculadas a partir de la matriz de confusión,

ü       Un conjunto de reglas y,

ü       La confiabilidad del sistema a partir del modelo generado por cada uno de los algoritmos.

Matriz de confusión para los datos de entrenamiento

La matriz de confusión mostrada en la Tabla 3.2., se genera a partir de resultados dados por ambos algoritmos, utilizando los 2000 datos de entrenamiento. 

En el caso del algoritmo de AD, 936 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y 9 fueron clasificados incorrectamente. Los 1047 datos que corresponden a la clase Y=0, estado fallado del sistema, fueron clasificados correctamente y 8 no.

Para el caso de HC, 945 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y ninguno fue clasificado incorrectamente. Los 1055 datos que corresponden a la clase  Y=0, estado fallado del sistema, fueron clasificados correctamente y ninguno fue clasificado incorrectamente.

Tabla 3.2 Matriz de confusión para datos de entrenamiento – Caso conectividad

Matriz de confusión para los datos de prueba

La matriz de confusión mostrada en la Tabla 3.3 se genera para ambos algoritmos, utilizando los 1000 datos de prueba. 

En el caso del algoritmo de AD, 432 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y 20 fueron clasificados incorrectamente. Los 528 datos que corresponden a la clase Y=0, estado fallado del sistema fueron clasificados correctamente y 20 no.