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

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

Tabla 3.3 Matriz de confusión para
datos de prueba – Caso conectividad

Medidas de sensibilidad, especificidad y precisión
y número de reglas generadas

Utilizando los datos generados en la matriz de
confusión  para los datos de entrenamiento (Tabla 3.2) y de
prueba (Tabla 3.3) se obtienen las siguientes medidas:

* no excluyentes

Tabla 3.4 Medidas sensibilidad, especificidad y
precisión – Caso conectividad

Función EAC generada por el AD

El algoritmo de AD produce reglas
para ambos estados del sistema operativo y fallado. Las
reglas generadas por AD son mutuamente excluyentes, así, la
aproximación de la FES se consigue sumando
cada una de las reglas que corresponden al estado operativo del
sistema. Para la determinación de la EAC se aplica el
siguiente procedimiento:

Supongamos la siguiente regla:

(Si X8=1 y
X10=1 y X20=1
entonces Sistema =1) genera el siguiente término:

Regla =
X8X10X20

Llevando el término a probabilidades se tiene:

E(X8
X10 X20)
= E(X8)
E(X10)
E(X2)

Para el caso de X8

E(X8)=
X8P +
X8(1-P) = 1 P8 + 0
P8 = P8

Directamente podemos decir que:

P8P10P20

Por consiguiente se tiene:

      EAC =
P8P10P20
+
P3Q7P8P9P12Q15P19Q20P21
+
Q7P8Q9P12Q15P19Q20P21
+

Q7P8Q12Q15P17P19Q20P21
+
P8P10P13Q15Q19Q20P21
+
P8Q10P11P12P13Q15Q19Q20P21
+
P7P8Q10P11Q12P13Q15Q19Q20P21
+
P8P12Q13P14Q15Q19Q20P21
+
P7P8P19Q20Q21 
+
P1P2P4Q7P8P19Q20Q21 
+
Q1P2P4P6Q7P8P19Q20Q21 
+
P1P2P4P8P18Q19Q20Q21 
+
P1P2Q4P7P8P18Q19Q20Q21 
+
Q8P15P17P21
+
P1P2P4P5Q8P13P15P16P17Q21 
+
P1P2P4Q8Q13P15P16P17Q21 
+
P1P2P4Q8P15Q16P17P19Q21 
+
P1P2P4Q8Q15P17P18
+
P1P2P4P5Q8Q15P17Q18P19
+
Q1P2P4P6Q8Q15P17P19
+
Q1P2P4P6Q8Q15P17Q19P20
+
P1P2P4Q8Q17P18
+
P1P2P4P5Q8Q17Q18P19
+
P1P2Q3P4Q5Q8Q17Q18P19
+
Q1P2P4P6Q8Q17P19
+
Q1P2P4P6Q8P9P11Q17Q19+  
Q1P2P4P6Q8P9Q11P13Q17Q19 
+
P7P8Q15P19Q20P21
+
P1P2P7P8Q9Q10Q12Q15Q19P20
+
P2P4Q7P8P9Q10Q12P20Q21 
+
Q7P8Q10Q12P15Q16P17P20P21
+
P7P8Q9Q10P12Q15Q19P20
+
Q7P8Q10Q12P15P16P20P21
+
P7P8Q9Q10P15Q19P20
+
P7P8Q9Q10P19P20
+
P7P8P9Q10P20
+
Q7P8Q10P11P12P20
+
P8P15P17Q20P21
+P8P15P16Q17Q20P21
+
P8P14P15Q16Q17Q20P21
+
Q7P8Q10Q11P12P14P20P21
+
P7P8Q14P15Q16Q17P19Q20P21
+
P5Q7P8Q10Q11P12Q14P20P21
+
Q7P8P11Q14P15Q16Q17Q20P21

Función de estructura FES generada por el
HC

La ejecución de HC genera las reglas de una sola
clase:

Para el caso de Y=1, cada producto lógico
corresponde a un camino mínimo. Es interesante hacer notar
que las 16 reglas extraídas para el estado operativo del
sistema, corresponden a caminos mínimos de la red.

Para Y=0,  estado fallado del sistema, el
algoritmo genera reglas que pueden corresponder a cortes
mínimos [32]. En este ejemplo se producen 49 reglas y 41 de
ellas corresponden a cortes mínimos.

En ambos casos las reglas generadas por el algoritmo son no
excluyentes.

Cada término de la aproximación de la
FES(X) representa un camino
mínimo desde el nodo origen al nodo destino, como es
representada a continuación:

X15 X17
X21+ X7 X8
X19+ X8 X10
X20+ X8 X12
X14 X21+ X7
X8 X9
X20+

X8 X10
X13 X21 +
X8 X15 X16
X21+ X8 X11
X12 X20+ X1
X2 X4
X18+

X2 X4 X6
X19+  X7
X8 X9 X13
X21+ X8 X11
X12 X13
X21+ X2 X4
X6 X9
X20+ X1 X2
X4 X5
X19+ X1 X2
X3 X7 X8
X18+ X2 X4
X6 X9 X13
X21

Para  obtener la EAC es necesario aplicar
un procedimiento adicional que convierte estas expresiones
lógicas a productos lógicos
excluyentes, utilizando el algoritmo KDH88 [18] y de esta manera,
de las 16 reglas no excluyentes extraídas por HC para
Y=1, se obtiene 80 productos lógicos
mutuamente excluyentes, correspondientes a 80 reglas.

Confiabilidad

Determinada las EAC por ambos algoritmos AD y HC, éstas
se usan para evaluar la confiabilidad de la red para diferentes
valores ri.
La Tabla 3.5 muestra los resultados a partir
de la EC y de la EAC,
obtenidas por ambos algoritmos y los respectivos errores
relativos.

Tabla 3.5 Confiabilidad de la red obtenida
usando EC y EAC – Caso conectividad

2.5.2. Evaluación de
capacidad

En el caso de evaluación de capacidad, la
red se considera operativa si al menos 100 unidades de flujo
pueden ser trasmitidas entre el nodo origen (s) y el nodo destino
(t).

El sistema se evalúa considerando que la falla ocurre,
cuando el flujo en el nodo destino es menor al requerido.

Al igual que el caso de evaluación de conectividad, la
EC se obtuvo usando el software "APACRO" [37], un procedimiento de
caminos compuestos y un algoritmo de flujo máximo y cortes
mínimos [Anexo B]. En este caso, se producen 43 caminos
válidos y la EC esta compuesta por  101
términos.

A través de una muestra aleatoria del espacio de estados,
se obtuvo un conjunto de 7500 datos diferentes. Los primeros
datos NT=5000, se usan para entrenar al
algoritmo que clasifica (AD y HC) y los
NE=2500 restantes para probar el
modelo generado por ambos
algoritmos.

2.5.2.1. Ejecución de los
Algoritmos AD y HC para el caso de Evaluación de
capacidad

Matriz de confusión para los datos de
entrenamiento

La matriz de confusión Tabla 3.6, se obtiene a partir de
los datos generados por ambos algoritmos, utilizando los 5000
datos de entrenamiento. 

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

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

Tabla 3.6 Matriz de confusión para datos
de entrenamiento – Caso capacidad

Matriz de confusión para los datos de
prueba

La matriz de confusión Tabla 3.7, se genera en ambos
algoritmos, utilizando los 2500 datos de prueba. 

En el caso del algoritmo de AD, 152 datos que corresponden a
la clase Y=1, estado operativo del sistema, fueron
clasificados correctamente, 13 fueron clasificados
incorrectamente, 2310 datos que corresponden a la clase
Y=0, estado fallado del sistema fueron clasificados
correctamente, 25 no.

Para el caso de HC, 160 datos que corresponden a la clase
Y=1, estado operativo del sistema, fueron
clasificados correctamente, 5 fueron clasificados
incorrectamente, 2318 datos que corresponden a la clase 
Y=0, estado fallado del sistema fueron clasificados
correctamente y 17 fueron clasificados incorrectamente.

Tabla 3.7 Matriz de confusión para datos
de prueba – Caso capacidad

Medidas de sensibilidad, especificidad y precisión
y número de reglas generadas

Utilizando los datos generados en la matriz de confusión
para los datos de entrenamiento (Tabla 3.6) y de prueba (Tabla
3.7), se obtienen las siguientes medidas:

* no excluyentes

Tabla 3.8 Medidas sensibilidad, especificidad y
precisión – Caso capacidad

Función EAC generada por el AD

Para este experimento al igual que el anterior, el algoritmo
de AD produce reglas para ambos estados del sistema operativo y
fallado. Las reglas de AD en este caso también son
excluyentes, por lo tanto la aproximación de la
FES se determina directamente sumando cada una de
las reglas que corresponden al estado operativo del sistema, y
finalmente aplicando el mismo procedimiento explicado en el caso
de conectividad se tiene:

     EAC  =
P2 P4 P6 P8
P12 P19 P20 +P1
P2 P4 P6 Q8
P15 P17 Q18 P21
+

Q1 P2 P4 Q6
P8 P17 P19 P20
P21 +P1 P2 P4
Q8 P15 P17 P18
P21 +

Q1 P2 P4 Q6
P7 P8 Q9 P17
P19Q20 P21 +P1
P2 P4 P6 P8
P18 Q19 P20 +

P1 P2 P4 Q6
P8 P10 P18 Q19
P20 +P1 P2 P4
Q6 P8 P9 Q10
P12 P18 Q19 P20
+

P1 P2 P4 P8
P13 P18 Q19 Q20
P21 +P1 P2 P4
P8 Q13 P17 P18
Q19 Q20 P21 +

Q4 P7 P8 P15
P17 P19 Q20 P21
+Q1 P2 P4 P8
P9 P17 P18 Q19
P20 P21 +

Q1 P2 P4 P8
Q9 P13 P17 P18
Q19 P20 P21 +Q4
P7 P8 Q10 Q14
P15 P17 P20 P21
+

Q4 P7 P8
P9Q10P14 P15
P17 Q19 P20 P21+
Q4P7P8Q10
P14P15 P17P19
P20 P21+

P2 P4 P6 P8
P9 P13 Q18 Q19
P20 P21 + Q4 P8
P10 P15 P17 P20
P21 +

Q2 P4 P7 P8
P15 P17 P19 P21
+Q2 P4 P7 P8
P15P17 Q19 P20
P21 +

Q2 P4 Q7 P8
P10 P15 P17 P20
P21 + P1 P2 P4
P5 Q6 Q8 P15
P17 Q18 P19 P21
+

P1 P2 P4 Q5
Q6P7 P8 P15
Q18 P19 + Q2P4
Q7 P8 Q10 P11
P12 P15 P17 P20
P21 +

P2 P4P6 P8
Q10 P15 P19Q20
P21 + P1 P2 P4
P6 P7 P8 P18
P19 Q20 Q21 +

P2 P4 P6 P8
P10 P19 Q20 P21 +
P1 P2 P4 Q6
P7 P8 P18 P19
+

P1 P2 P4Q6
Q7 P8 P18 P19
P20 +P1 P2 P4
Q6 Q7 P8 P18
P19 Q20 P21 +

Q1 P2 P4 P6
Q8 P15 P17 P19
P21 +P2 P4 P6
P8 Q10 Q12 P15
P19 P20 P21 +

P1 P2 P4 P5
Q6 P8 P9 Q 18
P19 +
P1P2P4P5Q6P8Q9P17Q18
P19 +

P2P4P6P8Q10Q12
P19P20
+P1P2P4P5Q6P8Q9Q11
P14Q17 Q18 P19
+

P2 P4 P6 P7
P8 P10 Q15
P19Q20P21

Función de Estructura generada por el
HC

El procedimiento de entrenamiento en HC caso capacidad, para
el estado operativo del
sistema, se producen 25 términos, de los cuales  21
corresponden a caminos mínimos, mientras el conjunto de
reglas generadas para el estado del sistema fallado incluye 39
cortes mínimos.

Al igual que el caso de conectividad el algoritmo no genera
las reglas de manera excluyente, la aproximación de la
FES(X) se representa a continuación:

FES(X) =
X7X8X15X17X19X21+X8X10X15X17X20X21+

X1X2X4X15X17X18X21+X2X4X6X8X10X19X20+

X8X11X12X15X17X20X21
+
X1X2X4X8X13X18X21+

X1X2X4X8X10X18X20
+
X7X8X9X15X17X20X21+

X2X4X6X15X17X19X21+X1X2X4X7X8X18X19+

X2X4X6X8X10X19X21+X2X4X6X8X9X12X20X21+

X2X4X6X8X11X13X18X21+X2X4X6X9X15X17X20X21+

X1X2X3X4X5X8X12X20+X1X2X4X7X8X9X18X20+

X1X2X4X5X8X16X19X21+X1X2X4X5X8X10X19X20+

X2X4X6X7X8X9X19X21+
X1X2X4X5X15X17X19X21+

X2X4X6X8X9X15X20X21

Está expresión se lleva a la forma mutuamente
excluyente y se obtiene la EAC, para ello al igual
que el caso anterior es necesario aplicar un procedimiento
adicional y de esta manera, de las 25 reglas no excluyentes
extraídas por HC para Y=1, se obtiene 69
lógicos correspondientes a 22 mutuamente excluyentes.

Confiabilidad

La siguiente tabla muestra la confiabilidad del sistema,
evaluando la EC y la EAC obtenidas por ambos modelos, para distintos
valores de ri.

Tabla 3.9 Confiabilidad de la red obtenida usando EC y EAC –
Caso capacidad

2.6.      
Análisis de resultados

Basándonos en los resultados obtenidos en ambos experimentos, se realiza una
comparación entre AD y HC y se analizan ciertos aspectos
según los siguientes criterios:

• La clasificación de los datos de entrenamiento y
  prueba.
• El número de reglas y tipos de reglas generadas.

La clasificación de los datos de entrenamiento y
prueba

Para los datos de entrenamiento y prueba, se muestra en la
Tabla 3.10 el porcentaje en que se equivoca el modelo generado
por ambos algoritmos clasificando los datos.

ü       En el caso del
algoritmo de AD, los datos de entrenamiento en ambos
experimentos no alcanzan el 1% de error y para los datos de
prueba, el máximo es el 2%.

ü       En el caso de
HC, en los datos de entrenamiento, el modelo no se equivoca,
siempre hace la clasificación de la manera correcta y para
los datos de prueba, el máximo sólo llega al 0.25%.

Tabla 3.10 Porcentaje de datos mal
clasificados

El número de reglas y tipos de reglas
generadas

La siguiente tabla muestra el número de reglas generadas
por los dos algoritmos comparados en ambos experimentos. Se
observa que el AD genera mayor número de reglas que HC.

Tabla 3.11 Reglas generadas

CAPÍTULO 4

Conclusiones

Este trabajo de investigación se basó
principalmente en la comparación de dos métodos de generación
de reglas, para la obtención de la Expresión Aproximada
de Confiabilidad (EAC) de una red. Para tal fin se utilizaron dos
algoritmos fundamentados en el aprendizaje automatizado,
denominados Árbol de Decisión (AD) y Hamming Clustering
(HC).

Los resultados obtenidos en ambos casos fueron los
siguientes:

En cuanto a las Reglas:

El AD extrae las reglas en forma excluyente, lo cual permite
obtener directamente la aproximación de la FES, que
corresponde a la suma de cada una de las reglas generadas por el
algoritmo y posteriormente aplicando un procedimiento se obtiene
la EAC.

El HC requiere que las reglas generadas sean convertidas a la
forma excluyente para obtener la EAC.

De los resultados se puede concluir que para la obtención
de la EAC, el método más directo es
el AD, debido a que genera directamente reglas excluyentes. El
método HC no genera reglas excluyentes, pero proporciona
información interesante que
puede ser utilizada para propósitos diferentes al de esta
investigación en particular, como es el caso de la
obtención de caminos mínimos y cortes mínimos de
una red.

Datos de Entrenamiento y datos de Prueba:

En cuanto a la clasificación de los datos de
entrenamiento y de prueba, ambos algoritmos presentaron muy
buenos resultado, en donde AD fue superado por HC.

Con base en los resultados ya expuestos, se deduce que los dos
métodos utilizados, tanto Árbol de Decisión (AD)
como Hamming Clustering (HC), basados en el aprendizaje de máquinas, aportan resultados
confiables para la construcción de una EAC a
partir de una pequeña muestra de datos, observándose
que las mejores aproximaciones se obtienen con HC, a pesar de que
las reglas obtenidas con este método son no excluyentes.

Finalmente se recomienda el uso del algoritmo de "Hamming
Clustering" para la obtención de los cortes mínimos de
una red, variando el tamaño de muestra de los datos, ya que
en el experimento presentado en esta investigación, para el
caso de continuidad, con solo 3000 datos de entrenamiento y
prueba, se obtuvieron 41 cortes mínimos y para el caso de
capacidad a partir de 7500 datos, se obtuvieron 39 cortes
mínimos

REFERENCIAS

[1] Joel A. Nachlas, FIABILIDAD. Ingeniería de Sistemas,
Primera Edición: Noviembre –
1995. www.uoc.edu/in3/emath/docs/Fiab_1.pdf

[2] Claudio M. Rocco S, Marco Muselli, Empirical Models Based
On Machine Learning Techniques for Determining Approximate
Reliability Expressions, Reliability Engineering and System
Safety, 2004, 83/3, pp 301-307.

[3] M.O. Ball (1986), Computational complexity of network
reliability analysis, IEEE Transactions on Reliability., R-35
(3).

www.isr.umd.edu/People/faculty/Ball.html

[4] Jogesh K. Muppala, Ricardo M. Fricks, and Kishor S.
Trivedi, Techniques for system dependability evaluation,
Department of Computer Science. The Hong Kong University of
Science and Technology.

http://shannon.ee.duke.edu/availabilitymodeling/papers.htm

[5] T. C. Hu, M. T. Shing, P. A. Tucker, Minimum Cuts in a
Network, School of Engineering, UCSD, La Jolla, CA 92093, 20 Apr
2000.

http://citeseer.ist.psu.edu/168282.html

[6] K. K. Aggarwal, Y. C. Chopra, J. S. Bajwa, Capacity
Consideration in Reliability Analysis of Communication Systems,
IEEE Trans on Reliability, Vol. 31, No. 2, Jun. 1982

[7] S. Rai, S. Soh, A Computer Approach for Reliability
Evaluation of Telecommunication Networks with Heterogeneous
Link-Capacities, IEEE Trans on Reliability, Vol. 40, No. 4, Oct.
1991

[8] L. M. Goldschlager,  R. A. Shaw and J. Staples. The
maximum flow problem for P. Computer Science 21, 105-111,
1982.

http://www.mpi-sb.mpg.de/cgi-bin/author?KKBGoldschlagerxxLMKKE+Goldschlager,-L.-M.

[9] Tongdan Jin & David W. Coit, Network reliability
estimates using linear and Quadratic unreliability of minimal
cuts.

http://www.rci.rutgers.edu/~coit/pubs.htm

[10] Vitaly G. Schetinin and Anatoly I. Brazhnikov, Diagnostic
Rule Extraction Using Neural Networks, Penza State
University,  2000. www.dcs.ex.ac.uk/people/vschetin/p3.pdf

[11] Mark Craven & Jude Shavlik, Rule extraction: Where we
go from here?, University of Wisconsin Machine Learning Research
Group Working Paper 99-1, 1999.

http://citeseer.ist.psu.edu/283343.html

[12] Peter Hamener & Yves Crama, Boolean function Theory,
Algorithms, Applications, Chapter 1.

http://www.maths.lse.ac.uk/Personal/martin/cdambflearn.pdf

[13] Lawrence O. Hall, Nitesh Chawla and Kevin W. Bowyer,

Decision tree learning on very large data sets. Department of
Computer Science and Engineering, ENB 118, University of South
Florida.

http://seraphim.csee.usf.edu/~hall/smc98.pdf

[14] Chris Mayer, Rule Induction Using 1-R and Quinlan"s Tree
to Rules Method, CSE 591 – Data Mining, 29 January
2002.

http://www.public.asu.edu/~huanliu/DM02/paper-present.html

[15] Zhi-Hua Zhou, Yuan Jiang and Shi-Fu Chen, Extracting
Symbolic Rules from Trained, Neural Network Ensembles, National
Laboratory for Novel Software, Technology, Nanjing University,
Nanjing.

http://citeseer.ist.psu.edu/503264.html

[16] Tom M. Mitchell, Machine Learning, Carnegie Mellon
University, Mc Graw Hill, 1997, Capítulo 3 Decision Tree
Learning

[17] Erlendur S Porsteinsson, A Non-linear operators,
2000.

http://www.maximal-usa.com/xmps/html/node9.html

[18] K. D. Heidtmann: Smaller Sums of Disjoint Products by
Subproducts Inversion, IEEE Trans on Reliability, Vol. 38, No. 4,
Aug. 1989

[19] Nathalie Japkowicz, Supervised versus Unsupervised
Binary-Learning, by Feedforward Neural Networks, , Faculty
of Computer Science, DalTech/Dalhousie University.

http://citeseer.ist.psu.edu/311444.html

[20] J.M. Portela da Gama, Combining Classification
Algorithms, PhD. Thesis, Faculdade de Ciências da
Universidade do Porto, 1999.

http://citeseer.ist.psu.edu/246549.html

[21] Vladimir Estival Castro, A first introduction to the
world of machine learning. The University of Newcastle,
Australia, 2001.

http://www.cit.gu.edu.au/~s2130677/teaching/KDD.d/lect04-new.pdf

[22] Nils J. Nilsson, "Introduction to Machine Learning",
Chapter 1, Robotics Laboratory, Department of Computer Science,
Stanford University 1996.

http://robotics.stanford.edu/people/nilsson/mlbook.html

[23] Mark W. Craven ,Extracting comprehensible models from
trained neural networks, Thesis, chapter 1, University of
Wisconsin Madison 1996.

http://www.cs.wisc.edu/~shavlik/abstracts/craven.thesis.abstract.html

[24] Gregorio Hernández Peñalver, Complejidad y
Grafos, Facultad de Informática UPM. 2000.
http://www.dma.eui.upm.es/MatDis/Seminario2/ComplejGrafos.PDF

[25] M. Muselli, D. Liberati, Hamming Clustering: A New
approach to Rule extraction, Genova, Italia

www.ieiit.cnr.it/~muselli/papers/soco99.pdf

[26] Paul Davidsson, Learning Characteristic Decision Trees,
Department of Computer Science, Lund University, Box 118, S-221
00 Lund, Sweden http://citeseer.ist.psu.edu/9343.html

[27] Sreerama K. Murthy, Automatic Construction of Decision
trees from Data: A Multi-Disciplinary Survey, Siemens Corporate
Research, Princeton, NJ 08540, USA

http://www-courses.cs.uiuc.edu/~cs491han/papers/98murthy.pdf

[28] Luís Fernando Raínho, Alves Torgo, Inductive
learning of tree-based regression models, Tesis de doctorado,
Departamento de Ciencia de Computadores.
Faculdade de Ciências da Universidade do Porto,
Septiembre

http://citeseer.ist.psu.edu/505941.html

[29] J.R. Quinlan, Programs for machine learning, Morgan
Kaufmann Publishers, 1993.

http://www.cse.unsw.edu.au/~quinlan/

[30] K. Mock, Lecture Notes on Machine Learning,

www.math.uaa.alaska.edu/ ~afkjm/

[31] Eduardo Morales, Inducción de Árboles
de Decisión TDIDT,
http://dns1.mor.itesm.mx/~emorales/Cursos/KDD/node27.html

[32] Jianxiu Hao , James B. Orlin, A faster algorithm for
finding the minimum cut in a directed graph, Journal of
Algorithms, v.17 n.3, p.424-446, Nov. 1994

www.informatik.uni-trier.de/~ley/db/journals/jal/jal17.html

[33] J. C. Cubero "Árboles de Decisión", 1998,

 http://elvex.ugr.es/etexts/spanish/proyecto/cap6.pdf

[34] Lic. Ana María Teresa Lucca , Elementos de lógica y matemática discreta
www.ing.unp.edu.ar/asignaturas/elymd

[35] Machine Learning,
http://www.cse.unsw.edu.au/~cs9416/ml/trees,

[36] M. Muselli, D. Liberati, Binary Rule Generation via
Hamming Clustering, IEEE Transaction on Knowledge and Data
Engineering, 2002, pp. 1258-1268

[37] M. Muselli, D. Liberati, Training digital circuits with
Hamming Clustering, IEEE Transaction on circuit and Systems:
Fundamental Theory and Applications, vol 47, pp. 513-527,
2000

[38] Oswin Aichholzer, 1996. Clustering the hypercube,

 http://www.igi.tugraz.at/oaich/publications.html

[39] Occam"s Razor, http://skepdic.com/occam.html

[40] Yoo Y. D., Deo N. "A comparison of algorithm for terminal
-Pair reliability",  IEEE Transaction on reliability, Vol.
37, No. 2, June 1988.

[41] "APACRO" Software para análisis de confiabilidad
en redes. DIOC Facultad de Ingeniería, UCV, Junio
2002.

[42] Exhaustive Search Methods

http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/ExhaustiveSearch.html

[43] The Ford-Fulkerson algorithm,

 http://www.isye.gatech.edu/~chayakritc/maximalflow.doc

Anexo A

Búsqueda profunda

Este tipo de búsqueda exhaustiva [42], se denomina
búsqueda profunda ya que, previamente a considerar otro
camino, el grafo es examinado a profundidad.

Cuando la búsqueda ha alcanzado el nivel mas bajo del
grafo y no se ha llegado al nodo destino, entonces, se extiende
la búsqueda a otras enlaces del grafo que inicialmente
fueron ignoradas. Para realizar esto, se regresa al nivel
anterior y se explora cualquier alternativa restante a este
nivel, repitiendo este método sucesivamente. Este
procedimiento de retroceso repetitivo garantiza que todas las
posibilidades sean sistemáticamente y exhaustivamente
examinadas.

La búsqueda profunda en un grafo se hace de arriba hacia
abajo y de izquierda a derecha.

Primero se examina el nodo origen, luego el nodo izquierdo del
nodo origen, posteriormente, el hijo izquierdo del nodo y
así sucesivamente, cuando no hay opciones se regresa al nodo
anterior del lado derecho y se repite el proceso de nuevo.

Ejemplo

El nodo donde se inicia la búsqueda es etiquetado como
(s), una vez posicionado sobre éste se comienza la
búsqueda del nodo destino, definido como nodo (t).

1.       Se arranca la
búsqueda desde el nodo origen (s), tal y como se muestra en
la siguiente figura, ubicado sobre éste el siguiente nodo a
explorar, es el que se encuentra más a la izquierda y que
aún no ha sido explorado.

2.       El nodo encontrado es
el nodo (1), se evalúa para comprobar si es el nodo destino,
si no lo es, se explorara el siguiente nodo que se encuentra
más a la izquierda.

3.       El nodo encontrado es
el nodo (5), se evalúa para comprobar si es el nodo destino,
si no lo es, se explorara el siguiente nodo que se encuentra
más a la izquierda.

4.       El nodo encontrado es
el nodo (6), se evalúa para comprobar si es el nodo destino,
si no lo es, se explorara el siguiente nodo que se encuentra
más a la izquierda, pero ningún nodo es encontrado,
éste es marcado y se devuelve al nodo anterior.

5.       Ubicados sobre el nodo
(5), el siguiente nodo a explorar, es el nodo que se encuentre
más a la izquierda, el cual corresponde al nodo (1), pero
éste ya ha sido explorado, por lo tanto se va al siguiente
nodo que se encuentra más a la izquierda, el cual
corresponde al nodo (2)

6.       Ubicados sobre el nodo
(2), el siguiente nodo a explorar, es el nodo que se encuentre
más a la izquierda y que no ha sido explorado, el cual
corresponde al nodo (3).

7.       Ubicados sobre el nodo
(3), el siguiente nodo a explorar, es el nodo que se encuentre
más a la izquierda y que no ha sido explorado, el cual
corresponde al nodo (4).

8.       Ubicados sobre el nodo
(4), el siguiente nodo a explorar, es el nodo que se encuentre
más a la izquierda y que no ha sido explorado, el cual
corresponde al nodo (8).

9.       Ubicados sobre el nodo
(8), el siguiente nodo a explorar, es el nodo que se encuentre
más a la izquierda y que no ha sido explorado, el cual
corresponde al nodo (7).

10.   Ubicados sobre el nodo (7), el siguiente nodo
a explorar, es el nodo que se encuentre más a la izquierda y
que no ha sido explorado, nodo (t), el cual corresponde al nodo
destino

Anexo B

Flujo Máximo

El problema del flujo máximo [43] consiste en encontrar
la capacidad máxima requerida que puede ser transportada
desde un nodo origen (s) a un nodo destino (t),  tomando en
cuenta las restricciones de capacidad de cada enlace.

El Algoritmo de Ford-Fulkerson

Este método depende de tres términos: red residual,
camino aumentado y cortes. Estas ideas son esenciales para el
teorema de flujo máximo.

Red residual: Dada una red de flujo y su correspondiente
flujo, una red residual es aquella por cuyos enlaces pueden
admitir más flujo neto del que pueda ser transportado por
ellos, en un momento determinado.

Camino aumentado o trayectoria de aumento y cortes: Un camino
aumentado p es un camino desde (s) hasta (t) en la red residual.
La capacidad residual de p es la máxima cantidad de flujo
neto que se puede transportar a lo largo de los enlaces de p.
Esta cantidad máxima de flujo neto corresponde al
mínimo de las capacidades residuales de los enlaces, sobre
este camino.

Secuencia de Pasos:

1. Seleccione cualquier camino valido desde s a t.
2. Aplique el método de etiquetado para encontrar un
   camino aumentado desde (s) a (t). Incremente el flujo entre
   este camino. Repita el paso 2. Si tal camino aumentado no
   existe, el flujo actual es el óptimo.

Método de etiquetado

Paso 1

Fije e(s) =   +∞ y p(s) = s.

Paso 2

Seleccione un vértice etiquetado X el cual
no haya sido considerado.

Si no existe ningún vértice, entonces
deténgase, no hay caminos aumentados de (s) a (t).

Paso 3

Para cualquier enlace (X, Y) que vaya a un
vértice no etiquetado y, etiquete y con 
e(Y) = min { e(X), u(X,
Y)} y p(Y) = X donde
u(X,Y) es la capacidad límite en un enlace de
es la capacidad límite del enlace en la red residual.

Ejemplo:

Inicialmente, arranca el flujo en cero. La red residual es la
misma que la original.

Paso 1:

Camino aumentado: s – a – d – t

Flujo entre el camino aumentado = min {e(s), e(a), e(d), e(t)}
= min{ +∞, 6, 3, 3} = 3

Paso 2:

La red residual y las nuevas etiquetas son:

El camino aumentado es s – b – d – t y el flujo que puede ser
enviado entre ese camino es min{+∞, 8, 4, 4} = 4.

Entonces la red residual es:

El camino aumentado es s – b – c – t y el flujo que puede ser
enviado entre ese camino es min{+∞, 4, 2, 2} = 2.

Paso 3:

La red residual es:

No se puede etiquetar el nodo t. Esto significa que no hay
camino aumentado en la red y de esta manera no podemos
incrementar el flujo.

El flujo máximo es = 9

Los enlaces (a,d), (b,d) and (b,c) conforman el corte
mínimo con una capacidad de 9 ( = Flujo máximo).

Trabajo de Grado presentado ante la ilustre
Universidad Central de Venezuela para optar al
Título de Magister Scientiarum en Investigación de
Operaciones

Autora:
Ing. Sandra Bertaggia

Venezuela, Caracas, Mayo del 2004