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.