UNIVERSIDAD NACIONAL DE SAN AGUSTÍN
ESCUELA DE POSTGRADO.
UNIDAD DE POSTGRADO DE LA FACULTAD DE
INGENIERIA DE PRODUCCION Y SERVICIOS
RECONOCIMIENTO DE PATRONES MEDIANTE REDES
COMPLEJAS
Tesis presentada por el Magister en Ciencias de
Computación y Matemática Computacional: Juan
Carlos Gutiérrez Cáceres
Para optar el grado de Doctor en Ciencia de la Com-
putación.
Asesor: Dr. César Armando Beltrán Castañón
Octubre-2013

A mi familia por todo el
apoyo dado
Agradecimentos
A Dios a mi familia, a mis amigos que siempre estuvieron a mi lado. Juan
Carlos
i
Resumen
La detección de patrones no es una tarea trivial, especialmente cuando se tienen datos heterogé-
neos aún dentro de un dominio específico. En la literatura existe una diversidad de técnicas
para la detección y reconocimiento de patrones, es así que en los últimos años se ha tomado un
especial interés en la técnica de redes complejas, las cuales son representadas como grafos con
gran cantidad de nodos y patrones de conexión no triviales. Sin embargo, no se conoce el po-
tencial de esta estrategia, ni su aplicación a diversos problemas de reconocimiento de patrones,
especialmente si tendrá un comportamiento óptimo para ciertos dominios. En ese sentido, el
presente trabajo propone un modelo basado en redes complejas para el reconocimiento de pa-
trones, el cual ha sido aplicado exitosamente para el reconocimiento de series temporales y de
imágenes digitales. El modelo propuesto lleva a una representación de grafo mediante un algo-
ritmo de transformación, aplicado a series temporales, tomando en consideración el total de la
información, lo cual la diferencia de otras técnicas que extraen sólo parte de la misma. Para el
caso de imágenes, en la literatura se tiene antecedentes del uso separado de la representación
de contorno y del contenido de los objetos en análisis. Nuestro trabajo propone una repre-
sentación conjunta del contorno y el contenido. Como primer caso de estudio, se realizaron
experimentos con un conjunto de secuencias de sonido de vocablos, con el objeto de desarrol-
lar un reconocimiento de habla, siendo que nuestra propuesta consiguió reconocer el 99.44%
los diferentes vocablos probados. Para el reconocimiento de patrones, se experimentó con imá-
genes de la base de datos de parásitos de Helmintos, siendo que el mismo está constituido por 11
especies diferentes con una base de datos de 1036 imágenes, donde nuestra propuesta consiguió
el 98.74% de acierto. Estos resultados son muy superiores a los conseguidos por técnicas tradi-
cionales, lo cual nos indica que el uso de redes complejas para el reconocimiento de patrones
es una técnica muy promisoria, y con el presente trabajo se contribuye a enriquecer no solo la
literatura en el área, sino en la solución de aplicaciones prácticas como las experimentadas..
ii
Abstract
The detection of patterns is not a trivial task, especially when data are heterogeneous even within
a specific domain. In the literature there are a variety of techniques for the detection and pattern
recognition, so that in the last years there is particular interest in the complex networks technic,
which are represented as a graph with nodes and large quantity of patterns nontrivial connec-
tion. However, is not known the potential of this strategy nor its application to various pattern
recognition problems, especially if it will have an optimum performance for certain domains.
In that sense, this thesis proposes a model based on complex networks for pattern recognition,
which has been successfully applied to time series recognition and digital imaging. The pro-
posed model leads to graph representation by a transformation algorithm, applied to time series,
taking into consideration all information, which differentiates from other techniques that using
extracted only part of it. For the case of images, in the literature has a antecedent of use sepa-
rately from the contour representation and content analysis of the objects . Our work proposes
a joint representation of the contour and content analysis. As a first case study, experiments
were tested with a set of sound sequences of words, in order to develop a speech recognition,
being that our proposal achieved 99.44 % of recognize the different words tested. For pattern
recognition, experimented with images database Helminth parasites, being that consists of 11
different species with a database of 1036 images, where our proposal achieved 98.74 % success
rate. These results are much higher than those achieved by traditional techniques, which indi-
cates that the use of complex networks for pattern recognition is a very promising technique,
and the present work not only enriches the literature, but in solving practical applications as
experienced.
iii
Índice
1 Introducción 1
1.1 Contexto y motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Definición del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Redes complejas 6
2.1 Consideraciones iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Sistemas complejos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Red compleja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Estructura de las redes complejas . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Modelos de las redes complejas . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6.1 Redes aleatorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6.2 Redes mundo pequeño . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6.3 Redes libre de escalas . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Medidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7.1 Medidas relacionadas a la distancia . . . . . . . . . . . . . . . . . . . 16
2.7.2 Medidas relacionadas al agrupamiento y búsqueda de ciclos . . . . . . 18
2.7.3 Grado de distribución . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7.4 Medidas de centralidad . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Reconocimiento de patrones y redes complejas 21
3.1 Consideraciones iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Series temporales y redes complejas . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.1 Series temporales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Técnicas estadísticas para las series temporales . . . . . . . . . . . . . 23
3.2.3 Análisis de series temporales . . . . . . . . . . . . . . . . . . . . . . 25
3.2.4 Análisis de series temporales mediante representación por redes com-
plejas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.5 Problemática actual en la representación de las señales . . . . . . . . . 28
iv
3.3 Imágenes y redes complejas . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Textura de una imagen . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 Clasificación de texturas . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.3 Representación de texturas mediante redes complejas (Wesley, 2010)
(Backes, 2010) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.4 Contornos de una imagen . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.5 Métodos para detección de contornos . . . . . . . . . . . . . . . . . . 32
3.3.6 Creación de red compleja a partir de contornos . . . . . . . . . . . . . 32
3.3.7 Situación actual y problemática en la representación de imágenes . . . 33
3.4 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Método propuesto 35
4.1 Consideraciones iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Esquema general de la propuesta . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Propuesta para caracterizar series temporales mediante red compleja . . . . . . 37
4.3.1 Representación de la serie temporal por red compleja . . . . . . . . . . 38
4.3.2 Obtención del vector de características . . . . . . . . . . . . . . . . . . 41
4.4 Propuesta para la caracterización imágenes mediante redes complejas . . . . . 43
4.4.1 Representación de la imagen por red compleja . . . . . . . . . . . . . 43
4.4.2 Obtención del vector de características . . . . . . . . . . . . . . . . . . 46
4.5 Clasificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.1 Canonical discriminant analysis (CDA) . . . . . . . . . . . . . . . . . 48
4.5.2 Maquinas de vectores soporte (MVS) . . . . . . . . . . . . . . . . . . 49
4.6 Validación cruzada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.7 Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Resultados experimentales 54
5.1 Resultados de la aplicación para el reconocimiento de palabras . . . . . . . . . 54
5.1.1 Adquisición, Cuantificación y Muestreo . . . . . . . . . . . . . . . . . 56
5.1.2 Detección de inicio y fin . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.3 Extracción de características . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.4 Clasificación de las palabras habladas . . . . . . . . . . . . . . . . . . 58
5.2 Reconocimiento de parásitos helmintos . . . . . . . . . . . . . . . . . . . . . 61
5.2.1 Conjunto de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.2 Técnicas de extracción de características . . . . . . . . . . . . . . . . 67
5.2.3 Redes complejas para la clasificación de parásitos . . . . . . . . . . . . 74
5.2.4 Red compleja del modelo propuesto . . . . . . . . . . . . . . . . . . . 75
5.2.5 Clasificación de parásitos . . . . . . . . . . . . . . . . . . . . . . . . . 76
6 Conclusiones 85
6.1 Discusión sobre el modelos propuesto . . . . . . . . . . . . . . . . . . . . . . 85
6.2 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3 Recomendaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4 Trabajos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Referencias Bibliográficas 88
v
Lista de Figuras
2.1 Red de amigos de un colegio en los Estados Unidos: Dos personas están conec-
tadas si son amigos.Fuente: (Newman, 2003). . . . . . . . . . . . . . . . . . . 8
2.2 Red de contagios entre personas: Dos personas están conectadas si una contagió
de una enfermedad a la otra. Fuente:(http://www.orgnet.com). . . . . . . . . . 9
2.3 Red de contactos sexuales entre individuos: Dos personas están conectadas si
han tenido por lo menos una relación sexual.Fuente: (Keeling and Eames, 2005). 9
2.4 Red de proteínas: Dos proteínas están conectadas si participan en la misma
reacción química. Fuente: (Hidalgo, 2010) . . . . . . . . . . . . . . . . . . . . 10
2.5 Internet: Dos computadoras están conectadas si hay un cable que las conecta.Fuente:
(Watts and Strogatz, 1998b). . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Documentos en un sitio Web: Dos páginas web están conectadas si hay un
hipervínculo de una a la otra.Fuente: (Newman, 2003). . . . . . . . . . . . . . 11
2.7 Red regular cada nodo tiene el mismo numero de conexiones . . . . . . . . . . 14
2.8 (a)Grafo aleatorio de Red Erdos y Renyi (b) distribución de los grados . . . . . 14
2.9 Transición entre red aleatoria a red regular donde el caso intermedio es una red
de con características de pequeño mundo . . . . . . . . . . . . . . . . . . . . . 15
2.10 (a)Red libre de escala (b) Distribución de colectividad de los nodos . . . . . . . 16
3.1 representación de una imagen mediante una malla regular conectada con los 8
vecinos (Wesley, 2010). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Creación de diferentes redes a partir de la malla regular (Wesley, 2010). . . . . 31
3.3 Creación de diferentes redes a partir del contorno de una imagen. . . . . . . . . 33
4.1 Esquema general de la propuesta de reconocimiento de patrones mediante redes
complejas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Ejemplos de serie temporal correspondiente a la palabra uno. . . . . . . . . . 39
4.3 Ejemplos de serie temporal correspondiente a la palabra dos. . . . . . . . . . . 39
4.4 Ejemplos de redes complejas para diferentes valores de θ en la figura (a) el
valore de θ = 1, (b) el valor de θ = 5, (c) el valor de θ = 10, (d) el valor de
θ = 15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5 Imagen como una superficie 3D en diferentes ángulos. . . . . . . . . . . . . . 44
4.6 Representación de los vertices de una imagen del cerebro. . . . . . . . . . . . 45
4.7 Efecto de diferentes umbrales para establecer las aristas. . . . . . . . . . . . . 46
vi
4.8 Representación de diferentes texturas, se puede apreciar que las redes son difer-
entes, manteniéndose las diferencias entre las cuatro texturas diferentes . . . . . 47
4.9 Caso linealmente separable . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.10 Caso no linealmente separable . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1 Gráfica de las amplitudes de las palabras grabadas: En la figura(a) son nueve
palabras diferentes; el numero Uno, Dos, Tres, Cuatro, Cinco, Seis, Siete, Ocho
y Nueve; En la figura (b) Muestras de una misma palabra pueden ser vistas . . 55
5.2 Determinación de ventanas solapadas para la detección del inicio y fin de pal-
abra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3 Determinación de ventanas solapadas para la detección del inicio y fin de pal-
abra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4 Redes construidas para diferentes distancias . . . . . . . . . . . . . . . . . . . 59
5.5 Relación entre las diferentes variables canónicas . . . . . . . . . . . . . . . . . 60
5.6 Imágenes de la base de datos SADPI8 v2.0 . . . . . . . . . . . . . . . . . . . 64
5.7 Nombres de parásitos: 1) Ascaris 2) Uncinarias 3) Trichuris trichuria 4) Hy-
menolepis nana 5) Dyphillobothrium pacificum 6) Taenia solium 7) Fasciola
hepática 8) Enterobius vermicularis . . . . . . . . . . . . . . . . . . . . . . . 65
5.8 Muestra de imágenes de diferentes parasitos de la base de datos usada para la
clasificación de parásitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.9 Propuesta para la clasificación de los parásitos Helmintos . . . . . . . . . . . . 79
5.10 Contornos externos e internos de los diferentes parásitos . . . . . . . . . . . . 80
5.11 Imagen micrográfica del parásito también se puede ver su visualización en 3D,
y dos redes generadas para dos parametros distintos cuando la distancia vale 4
y cuando vale 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.12 Enterobius Vermiculares con problemas de transformaciones geométricas, se
puede ver que su vector de características para las diferentes transformaciones
geométricas son muy parecidas eso hace al método robusto ante problemas de
rotación y escala, (a) Reducida de tamaño al 50% del tamaño original, (b) Im-
agen Original, (c) Aumentada de tamaño al 150 %, (d) Imagen rotada y au-
mentada 150 %, (e) Imagen normal rotada, (f) Imagen rotada y disminuida de
tamaño . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.13 Análisis de las variables canónicas se pueden ver la combinación de la 8va
variable combinada con la 7ma, 6ta, 5ta, 4ta, 3ra, 2da, 1ra. Y 3ra combinada
con las variables 2da, 1ra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.14 Visualización de la variable 7ma con la 6ta, 5ta, 4ta, 2da, 1ra variable. También
vemos la 4ta y 3ra, 2da, 1ra. Además la 6ta combinada con 5ta, 4ta, 2da, 1ra
finalmente la 5ta variable combinada con 4ta, 3ra, 2da, 1ra . . . . . . . . . . . 84
vii
Lista de Tablas
5.1 Comparación de los resultados para diferentes parámetros del modelo propuesto. 61
5.2 Matriz de confusion, cons sus respectivos error por cada clase, usando SVM
con kernel lineal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Matriz de confusion, cons sus respectivos error por cada clase, usando SVM
con kernel polinomial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Cantidad de micrografías por especie y parásitos segmentados encontrados en
las micrografías . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Comparación de los resultados para diferentes parámetros del modelo propuesto. 77
5.6 Comparación de los resultados para diferentes parámetros del modelo propuesto. 77
5.7 Matriz de confusion, con sus respectivos error por cada clase de la clasificación
del método propuesto a los 8 especies de parásitos helmintos. . . . . . . . . . . 78
5.8 Matriz de confusion, cons sus respectivos error por cada clase, para el modelo
basado en contornos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
viii
CAPÍTULO
1
Introducción
1.1 Contexto y motivación
En la actualidad podemos apreciar diferentes tecnologías emergentes que nos ayudan a resolver
problemas reales, muchas de estas tecnologías son fruto de las denominadas ciencias comple-
jas, donde técnicas como la teoría del caos, redes complejas son utilizadas como una nueva
alternativa de solución a muchos problemas tradicionales e incluso en ingeniería (Costa et al.,
2007).
Una de estas tecnologías que esta tomando mucha importancia es el campo de las redes
complejas. Este area de investigación surge inicialmente por el interés de entender a las difer-
entes redes que existen en la naturaleza, por ejemplo el cerebro está compuesto de más de cien
mil millones de neuronas, se dice que cada neurona tiene entre diez mil a quince mil conexiones
(sinapsis), eso quiere decir que tenemos billones de sinapsis, es por ese motivo que el cerebro es
uno de las redes complejas mas representativas. Existen diferentes estudios han venido siendo
desarrollados sobre el cerebro, ya que en él se llevan a cabo una serie de actividades neuronales
y procesos cognitivos complejos, que el ser humano aun no consigue descifrar del todo (Boc-
caletti et al., 2006). Trabajos como el de Rubinov (Rubinov and Sporns, 2010) analiza el nivel
de conectividad del cerebro como una red compleja, mediante el uso de diferentes métricas las
cuales son muy usadas en el análisis de las redes en general.
1
1.1. CONTEXTO Y MOTIVACIÓN 2
Existen muchos fenómenos en la naturaleza que también pueden ser modelados como re-
des complejas, como por ejemplo: las redes biológicas (los enlaces de las proteínas), las redes
de comunicación física como internet, las redes sociales, las redes epidemiológicas, las redes
ecológicas, las redes de distribución eléctrica (Pagani and Aiello, 2013) etc; las redes se en-
cuentran en todas partes. Es por ese motivo que estudiar las redes complejas se ha convertido
un área de investigación activa, el cual esta inspirado por el análisis empírico de las redes del
mundo real (Ravasz and Barabási, 2003).
Al inicio, el estudio de las redes complejas estuvo encomendado principalmente a físicos e
estadísticos, pero fueron necesarios modelos matemáticos y otras herramientas más poderosas,
para poder entender y explicar las propiedades estructurales y dinámicas de las redes, y así se
fueron incrementandose otras áreas de investigación entre ellas: medicina, economía, biología,
y ahora la ciencia de la computación (Reijneveld et al., 2007), la cual permite implementar
herramientas para poder simular y realizar experimentos sobre diferentes modelos propuestos
Las redes en general poseen diferentes tamaños y complejidades y también tienen propiedades
de similares en su estructura, las que pueden ser modelados desde un contexto de teoría de
grafos, siendo representados en términos de nodos y aristas (conexiones entre nodos), con car-
acterísticas topológicas no triviales, es decir, donde la distribución de sus conexiones no son ni
regulares puros ni aleatorios (Boccaletti et al., 2006).
Hoy en día esta área de investigación está ayudando a resolver diferentes problemas, por
ejemplo en la representación de redes sociales tenemos el trabajo de (Marina and Carlos, 2010)
donde se modela la red social Twitter y se analiza su estructura y algunas propiedades de dicha
red, en el procesamiento de lenguaje (Pardo et al., 2006) lo uso para evaluar la calidad de
redacción de textos, en (Amancio et al., 2012) se usan las redes complejas para resumir textos,
también en el reconocimiento de patrones vemos que existen trabajos para modelar las series
temporales en grafos de tal manera que la dinámica de los sistemas pueden ser analizados desde
el punto de vista topológico, como lo hizo (Zhang and Small, 2006) el cual modelo los sistemas
dinámicos en redes complejas usando la correlación, otro trabajo modelo la actividad sísmica
de diferentes lugares de la tierra (Davidsen et al., 2005) (Ferreira et al., 2013).
Muchos han propuestos diferentes métodos de construcción de redes complejas a partir de
series temporales, trabajos como el de (Dellnitz et al., 2006) el cual está basado en la partición
del espacio de fase de un sistema dinámico en k conjuntos disjuntos, transformando las trayec-
torias en una secuencia de nodos usados para detectar las diferentes transiciones que una serie
temporal pueda tener, puesto que las series temporales reales pueden tener ruido entonces él usa
un umbral para poder realizar las particiones del espacio. También tenemos el trabajo de (Zhang
et al., 2008) que propuso modelar la red mediante el coeficiente de correlación en búsqueda de
ciclos pseudo periódicos. Otro trabajo muy usado es el de (Lacasa et al., 2008) que mediante
1.2. DEFINICIÓN DEL PROBLEMA 3
el concepto de visibilidad de estados crea la red compleja a partir de una serie temporal. Como
se pudo apreciar muchos trabajos están siendo desarrollados para estudiar las series temporales
desde el enfoque de redes complejas.
Las redes complejas también vienen siendo usadas para caracterizar imágenes de tal manera
que esta pueden detectar e identificar objetos dentro de las mismas, el trabajo que propone
(Fabricio, 2010) muestran aplicaciones en segmentación de imágenes , otros trabajos también
han sido desarrollados para poder como el de (Backes et al., 2010) que muestra el uso de la
textura para modelar una red y luego caracterizarla. También existen trabajos en los cuales la
forma de los objetos contenidos en una imagen son el punto principal para modelar la red como
lo muestra el trabajo de (Backes et al., 2009) el cual lo uso para clasificar hojas por su forma.
1.2 Definición del problema
El problema principal es representar un patron mediante una red compleja para posteriormente
caracterizarla y reconocerla, cuando quiere trabajar en esta area se tiene que considerar el tipo
de patron a tratar, ya que de una buena representación dependerá el éxito del reconocimiento,
el problema se complica desde el momento que se quiere trabajar con patrones de series tem-
porales (1D) e imágenes (2D). En ese sentido el modelo propuesto debe ser robusto ante estos
dos tipos de patrones.
En la actualidad existe muchas técnicas para modelamiento de redes complejas a partir de
series temporales, pero están principalmente orientadas a mantener ciertas propiedades de su
dinámica, mas no son propuestas para ser usadas en el reconocimiento de las mismas. Dichas
propuestas tienen diferentes problemas como: pérdida significativa de información, mientras
que otros son orientados a series específicas como series pseudo aleatorias, por otro lados ex-
isten métodos donde se busca una correlación de un segmento de ciclo que se esté repitiendo
en la señal, donde el problema principal es la dimensión del ciclo que se busca, otras técnicas
construyen redes según el grado de visibilidad entre los diferentes estados confundiendo series
determinísticas con series aleatorias.
Por otro lado cuando se quiere trabajar con imágenes, se necesita que el modelo mantenga
las propiedades que las imágenes, por ejemplo caracterizar la forma de los objetos así como la
textura que posee en un solo modelo ya que existen básicamente tendencias de varios autores
que usan las propiedades por separado, hay modelos orientados solo a la representación de la
forma de los objetos no tomando en cuenta la textura de la imagen, y también existen mode-
los que solo usan la propiedad de la textura dejando de lado la forma en ese sentido pierden
información inherente a la imagen por tratar por separado dichas características.
1.3. OBJETIVOS 4
En el capitulo 3 se presentara mayor detalle de las técnicas existentes tanto para series
temporales como para imágenes analizando detalladamente las ventajas y limitaciones de cada
propuesta.
1.3 Objetivos
El objetivo general de esta tesis es proponer un nuevo modelo de representación de red compleja
para el reconocimiento de patrones, específicamente para reconocimiento de palabras (1D) y
reconocimiento de imágenes (2D).
1.3.1 Objetivos específicos
• Proponer una forma de modelamiento de red compleja a partir de series temporales;
• Proponer un modelo de representación de red compleja a partir de imágenes;
• Seleccionar las medidas más adecuadas para las redes complejas creadas;
• Probar las técnicas en reconocimiento de palabras y en el reconocimiento de imágenes de
parásitos helmintos.
1.4 Estructura del documento
Este documento esta estructurado de a siguiente manera:
• En el capítulo 2 se presentan los conceptos básicos referentes a las redes complejas, donde
la teoría de grafos es una parte importante además de las medidas mas usadas serán de-
scritas
• En el capítulo 3 describiremos el estado del de las técnicas para modelar redes com-
plejas a partir de series temporales, comparando y analizando las ventajas y desventa-
jas de los modelos existentes, de igual manera se hará con los modelos existentes en el
reconocimiento de imágenes, analizando las limitaciones de los modelos actuales exis-
tentes.
• En el capítulo 4 se explicara la propuesta para el reconocimiento de patrones mediante re-
des complejas, acá se presentara el modelo propuesto y las ventajas que tiene con respecto
a otros modelos.
1.4. ESTRUCTURA DEL DOCUMENTO 5
• En el capítulo 5 Las pruebas y resultados de ambos casos de estudio serán presentadas
analizando las ventajas de las propuestas
• Finalmente las conclusiones, recomendaciones y trabajos futuros serán presentados
CAPÍTULO
2
Redes complejas
2.1 Consideraciones iniciales
Definir una red compleja no es sencillo, ya que por ser un campo emergente de investigación
es que esta intentando ordenarse según las diferentes investigaciones que se vienen realizando
actualmente no existe una definición formal ya que redes complejas están presentes en difer-
entes areas de investigación. Muchos fenómenos de la naturaleza se puede modelar como una
red, como las estructuras del cerebro, la proteína-proteína redes de interacción, las interacciones
sociales y el Internet y la WWW. Todos estos sistemas pueden ser representados en términos
de nodos y aristas que indican las conexiones entre los nodos. En Internet, por ejemplo, los
nodos representan los routers y las aristas representan las conexiones físicas entre ellos. De la
misma manera, en las redes de transporte, los nodos pueden representar a las ciudades y las
aristas representan las carreteras que los conectan. Estas aristas pueden tener pesos, que puede
representar el flujo de trafico en una autopista o una frecuencia en el caso de palabras pueden
corresponder a la ocurrencia dos palabras en un texto.
Una característica importante de estas redes es que no son aleatorias, pero tienen una ar-
quitectura estructurada. Todo eso se puede apreciar en la topología ya que son diferentes
topologías, por ejemplo las redes de interacción de proteína a proteína e de Internet, son pare-
cidas: siguen la ley de potencia, exhibiendo una estructura libre de escala. Por lo tanto, una
cuestión importante se plantea: ¿Cómo pueden los sistemas fundamentalmente diferentes como
6
2.2. SISTEMAS COMPLEJOS 7
las células y el Internet tener las mismas características topológicas subyacentes?. Encontrar las
leyes fundamentales que generan estas redes seria la respuesta a esta pregunta, por ese motivo
el modelado y la caracterización de ellos son los desafíos actuales en la investigación de redes
complejas.
2.2 Sistemas complejos
Como ocurre con gran parte de estudios científicos, no se puede definir los sistemas complejos
en un sólo enunciado, a continuación se enumeran las características, que para (Aldana and
Cluzel, 2003) son las más importantes:
• Los Sistemas Complejos, son sistemas que están compuestos por muchos elementos no
idénticos, conectados bajo diversas interacciones entre si.
• La complejidad se les atribuye a estos sistemas por que poseen propiedades no esperadas,
ya que presentan comportamientos emergentes, es decir, que emergen de las interacciones
de las partes del sistema.
• Cada parte tiene su propia estructura interna y cada uno tiene una función específica, por
ello para describir un sistema complejo hace falta no solo conocer el funcionamiento de
las partes sino conocer como se relacionan entre sí. Examinar una única neurona no es
suficiente para describir el cerebro.
• Lo que ocurra a una parte del sistema afecta de manera altamente no lineal a todo el
sistema. Ejemplos de sistemas complejos son los seres vivos y las sociedades.
2.3 Red compleja
Diversos sistemas están estructurados como elementos que se interrelacionan entre sí (Barabasi
and Crandall, 2003). Existen muchos sistemas físicos que son un ejemplo claro de estos ele-
mentos interrelacionados como internet, la red física mas grande del mundo. Este tipo de redes
hoy en día son ampliamente estudiados todo dado que el estudio de esta interacción puede en-
contrar comportamiento peculiares (Albert et al., 2000). El estudio de estas redes complejas se
enmarca dentro de los sistemas complejos.
Para poder entender una red compleja es importante recordar algunos conceptos sobre teoría
de grafos, es por ese motivo que en la siguiente sección se presentaran algunos conceptos nece-
sarios sobre grafos para poder caracterizar a estas redes. A lo largo del presente trabajo, se han
2.3. RED COMPLEJA 8
mencionado diferentes ejemplos de redes complejas a continuación comentaremos algo sobre
dichas redes las cuales se podrán ver en las siguientes figuras:
En la figura 2.1 se puede apreciar la red de amigos de un colegio en los Estados Unidos
donde 2 personas están conectadas si son amigos, puesto que esta red se armo preguntando a
los participantes si determinada persona es o no su amigo este podría responder que si mientras
que podría no ocurrir de forma inversa, ya que el otro participante podría decir que no lo es por
ese motivo este grafo es dirigido, los colores de los nodos representan las distintas razas que
existen entre los participantes, y la division entre la parte superior e inferior es realizada entre
colegio primario y secundarios (Newman, 2003).
Figura 2.1: Red de amigos de un colegio en los Estados Unidos: Dos personas están conectadas
si son amigos.Fuente: (Newman, 2003).
Funcionarios de salud pública realizan el seguimiento de contactos para trazar la propa-
gación de enfermedades infecciosas. La red que muestra en la figura 2.2 muestra la propagación
de una enfermedad infecciosa en el aire. El mapa fue creado a partir de datos reales de contacto
de la comunidad en la que el brote estaba sucediendo. Los nodos negros son personas con la
enfermedad clínica (y son potencialmente infecciosos), los nodos de color rosa representan a las
2.3. RED COMPLEJA 9
personas expuestas con la incubación de la infección y no son contagiosas, verde representan
las personas expuestas sin infección y no son contagiosas. Como se pudo apreciar es importante
el mapeo de una infección para poder realizar estudios de como una infección se propaga.
Figura 2.2: Red de contagios entre personas: Dos personas están conectadas si una contagió de
una enfermedad a la otra. Fuente:(http://www.orgnet.com).
De forma similar se pueden apreciar otros aspectos por ejemplo en la figura 2.3 en la cual
se puede apreciar los contactos sexuales entre personas este grafo fue generado de información
registrada de pacientes con VIH, donde una conexión significa que por lo menos esas dos per-
sonas tuvieron una relación sexual también se puede apreciar que existen nodos que son lo que
tienen mas conexiones siendo uno de ellos focos infecciosos.
Figura 2.3: Red de contactos sexuales entre individuos: Dos personas están conectadas si han
tenido por lo menos una relación sexual.Fuente: (Keeling and Eames, 2005).
Para cualquier compleja red es importante saber las propiedades de dicha red, y como es
que estas se generan, esos modelos se han usado para mapear la interacción de las proteínas que
2.3. RED COMPLEJA 10
conforman la levadura Saccharomyces cerevisiae. A nivel biológico también se pueden tener
redes como la que se aprecia en la figura 2.4 donde dos proteínas estas conectadas si participan
de la misma reacción química.
Figura 2.4: Red de proteínas: Dos proteínas están conectadas si participan en la misma reacción
química. Fuente: (Hidalgo, 2010)
El ejemplo de red mas grande es de internet donde se puede ver como las computadoras
pueden estar conectadas físicamente mediante un cable en la figura 2.5 podemos apreciar la
conexión física de Internet.
Figura 2.5: Internet: Dos computadoras están conectadas si hay un cable que las conecta.Fuente:
(Watts and Strogatz, 1998b).
En la figura 2.6 podemos ver las interconexiones de los hipervinculos entre páginas web,
dos páginas están conectadas si existe un hipervinculo que los une.
2.4. GRAFOS 11
Figura 2.6: Documentos en un sitio Web: Dos páginas web están conectadas si hay un hiper-
vínculo de una a la otra.Fuente: (Newman, 2003).
Como se pudo apreciar existen muchos trabajos en los cuales las redes complejas aparecen
como ejemplo de modelamiento, ya sea de fenómenos sociales, como biológicos, e incluso de
como el ser humano extendió sus redes en esta gran red denominada internet.
Para poder formalizar los diferentes conceptos de las redes complejas es necesario apoyarse en
conceptos matemáticos por ese motivo es que a continuación describiros algo de la teoría de
grafos ya que es la indicada para poder expresar de manera formal los conceptos sobre la teoría
de grafos.
2.4 Grafos
Las redes complejas en este contexto son representados por conjuntos de nodos denominados
vértices los cuales están conectados, esta conexión representa la interacción que se tiene entre
nodos los cuales son denominados aristas.
Un grafo G = (V,E) es un objeto abstracto formado por el conjunto de vértices V (nodos)
y el conjunto E de aristas (enlaces) que se unen (de conexión) en pares de vértices. El conjunto
de vértices y un conjunto aristas de un grafo G se denota por V (G) y E(G), respectivamente.
La cardinalidad de V por lo general, se denota por n, y la cardinalidad de E se denota por m. Si
dos vértices están unidos por una arista ellos son llamamos de adyacentes o también pueden ser
denominados como vecinos. Los Grafos pueden ser no dirigidos o dirigidos. En los grafos no
dirigidos, el orden de los vertices unidos por una arista no tienen un orden en particular la cual
es considera como simétrica. Una arista no dirigida uniendo los vértices u, v ∈ V se denota por
u, v = v, u. en grafos dirigidos, cada arista dirigida tiene un origen y un destino. Una arista con
2.5. ESTRUCTURA DE LAS REDES COMPLEJAS 12
origen u ∈ V y destino v ∈ V está representada por el par ordenado (u, v) el cual es distinto de
(v, u).
Llamaremos a todos los nodos que estén conectados directamente a un nodo vi como vecinos
de vi. El número ki vecinos del nodo vi (número de conexiones de vi) se denomina grado de
conectividad de vi.
En lo que corresponde a grafos existe el denominado grafo regular, el cual es aquel que en
todos los nodos tiene un mismo grado de conectividad, así un grafo irregular es aquel que posee
nodos con diferentes grados de conectividad. Un grafo altamente irregular es caracterizado por
el hecho de que cada uno de sus vértices o nodos es adyacente a vértices de grados diferentes
entre sí.
En ese sentido las redes complejas son definidas como redes cuyos vértices pueden presentar
diferentes grados entre si. Nótese que la definición indica que no necesariamente todos los
nodos deben estar conectados unos con otros, ni que todos los nodos deben tener conexiones,
es decir, pueden existir nodos aislados.
A continuación Franceshi (de Angelis André, 2005) hace hincapié en los siguientes algunos
puntos que son tomados en consideración para decir si una red es compleja o no, el tamaño de
la red no será determinante para la clasificación de la red en regular o compleja. En las redes
complejas no es prevista la existencia de conexiones. Las redes regulares son consideradas
casos particulares de redes complejas. Es decir, el conjunto de las redes complejas contiene al
subconjunto de las redes regulares. Es por ese motivo que es importante estudiar la estructura
de las mismas.
2.5 Estructura de las redes complejas
Dado que la red compleja esta formada de nodos y aristas es que el estudio de su estructura esta
relacionado a la interrelación que tienen estos elementos en la red, siendo el interés determinar
las propiedades estructurales de la red, estas propiedades se basan en el estudio de las siguientes
características:
La distribución de conexiones P (k): Es la probabilidad de que un nodo escogido al azar
tenga k conexiones. Por ejemplo, en una red de contactos sexuales P (k) es la probabilidad
de que una persona escogida al azar en una sociedad haya tenido k parejas sexuales distintas
a lo largo de su vida. El coeficiente de agregación C: Es la probabilidad de que dos nodos
conectados directamente a un tercer nodo, estén conectados entre sí. Por ejemplo, en una red
de amistades, es la probabilidad de que dos amigos sean ellos mismos amigos uno del otro. La
longitud mínima Lij entre dos nodos vi y vj : Es el número mínimo de “saltos” que se tienen
2.6. MODELOS DE LAS REDES COMPLEJAS 13
que dar para llegar de un nodo vi de la red a otro nodo vj de la red. La longitud promedio de la
red L: Es el promedio de las longitudes mínimas Lij entre todas las posibles parejas de nodos
(vi, vj) de la red. La distribución de tamaños de islas P (s): Es la probabilidad de que una isla
esté compuesta por s nodos. El tamaño de la isla más grande la que denotaremos por S∞. El
grado de un vértice es también importante: Aquellos nodos con un grado alto en relación de los
demás son llamados hubs, y su presencia en la red tiene una gran influencia en su estructura.
Una importante característica de las redes complejas es que no son aleatorias, si no al contrario
poseen una arquitectura estructurada.
Para Aldana (Aldana, 2006) el estudio general de las redes puede dividirse en dos campos
diferentes: Estructura y Dinámica. En el campo de estructural se está interesado en conocer
la distribución de las conexiones o vecinos, el coeficiente de agregación que es la probabilidad
de que dos nodos conectados a un tercer nodo, estén conectados entre si, también será posible
evaluar la longitud mínima entre dos nodos, longitud promedio, entre otros. Una vez que se sabe
de qué manera interactúan los nodos (propiedades estructurales) en la red, se hace necesario
estudiar sus propiedades dinámicas, como por ejemplo la propagación.
2.6 Modelos de las redes complejas
Antes de comenzar hablar de los diferentes modelos de redes complejas es importante tomar en
consideración a las redes regulares las cuales son uno de los modelos mas conocido de redes,
donde los vertices poseen un posición bien definida en el espacio euclideano y la distribución de
las aristas son distribuidas entre los vecinos topológicos de cada vértice. En la siguiente figura
2.7 podemos apreciar la topología de una red donde se puede apreciar que cada nodo tiene una
cantidad igual de conexiones, sobre la variación o diferencias con las redes regulares es que las
otras redes aumentan su complejidad en el estudio de la mismas por eso los siguientes modelos
difieren de una red regular en la complejidad de sus conexiones.
Existen varios modelos de redes complejas han sido propuestas algunos de esos modelos
son de gran interés es por eso que es importante estudiarlos se pueden diferenciar los siguientes
modelos:
1. Redes aleatorias
2. Redes mundo pequeño
3. Topología libre de escala
2.6. MODELOS DE LAS REDES COMPLEJAS 14
Figura 2.7: Red regular cada nodo tiene el mismo numero de conexiones
2.6.1 Redes aleatorias
Este tipo de redes fueron Erdos y Renyi (P. and A., 1959) los que propusieron una red de
este tipo, donde no existen criterios que privilegien las conexiones, las cuales están dadas por
simple probabilidad así la red es caracterizada por el numero de vertices n y la probabilidad de
conexión p entre los vertices, con un valor n y la conectividad media fija a la distribución de
Poison, la media de los caminos tienden a valores pequeños como se puede apreciar en la figura
2.8
Figura 2.8: (a)Grafo aleatorio de Red Erdos y Renyi (b) distribución de los grados
Las aplicaciones de este modelo son muy limitadas debido a que pocas redes reales se com-
portan tal (no son aleatorias), sin embargo existen aproximaciones en la teoría de redes com-
plejas en el campo de las redes sociales (redes de afiliación y grafos bipartitos). Una diferencia
clara entre las redes reales y las generadas por este modelo se distinguen en la distribuciones
de grado, que en el caso de las generadas por este modelo son poisonianas, mientras que en la
realidad tienden a ser más exponenciales. En las redes con distribuciones poisonianas se con-
2.6. MODELOS DE LAS REDES COMPLEJAS 15
centra la probabilidad en torno a un valor de k (grado del nodo) y decrece a una razón de 1/k
cuando se aleja del valor central. En las redes exponenciales no existe un valor preferente y la
probabilidad decae a lo largo del espectro de k a medida que éste crece.
2.6.2 Redes mundo pequeño
Watts et al (Watts and Strogatz, 1998a), observaron que en algunas redes del mundo real en-
contraron caminos cerrados con apenas 3 nodos los cuales son diferentes de la definición de
las redes aleatorias. Se observaron que dichas redes estaban altamente “clusterizada” al igual
que las redes regulares mientras que la distancia media entre cualquiera de las unidades que la
forman es mucho mas pequeña que en una red regular y muy cercana a una red completamente
aleatoria, pero hay que recordar que en una red aleatoria la clusterización es muy baja debido
precisamente a que no hay un grado de afinidad importante para establecer las conexiones. Y
esas eran precisamente las redes que normalmente habían sido consideradas por los físicos para
modelizar sistemas dinámicos complejos, o bien redes aleatorias o redes regulares. De esta
manera es que se introduce un modelo al que llamaron de “mundo pequeño”, es por ese motivo
que se necesita una manera diferente de crear redes para poder representar ese efecto real que
tenían ciertas redes, este tipo de redes tenían lo que se conoce como el efecto mundo pequeño
dado que a distancia de separación entre vertices crece en un regimen logarítmico. Es por ese
motivos que (Watts and Strogatz, 1998b) propusieron un modelo simple para crear redes con
características de tener valores bajos entre la distancia entre vertices. La siguiente figura 2.9
muestra la red de mundo pequeño.
Figura 2.9: Transición entre red aleatoria a red regular donde el caso intermedio es una red de
con características de pequeño mundo
2.6.3 Redes libre de escalas
Este tipo de redes son aquellas que presentan ciertos nodos que tienen la mayor concentración
de conexiones con los demás. (Barabási et al., 2000) propusieron la construcción de un modelo
2.7. MEDIDAS 16
donde existían ciertos vertices llamados referenciales los cuales tiene la característica de tener la
mayor cantidad de conexiones y el resto de vertices se caracterizan por tener pocas conexiones
normalmente están conectados con el otro tipo de vertices. En la siguiente figura 2.10 se puede
apreciar este tipo de redes:
Figura 2.10: (a)Red libre de escala (b) Distribución de colectividad de los nodos
Es importante notar que existen varios modelos de redes complejas porque ellas presentan
características que en cierta forma las hacen una distinta de la otra, estas características son
cuantificables (medibles) lo cual es importante para diferenciar un modelo de otro.
2.7 Medidas
Existen varias medias que pueden ser consideradas en la caracterización de las redes complejas,
varias de ellas están relacionadas ya que tienen características similares, por ejemplo tenemos
métricas relacionadas a la distancia, relacionadas a la búsqueda ciclos, grado de distribución de
nodos y correlación, redes con diferentes tipos de vertices, medidas de centralidad entre otras a
continuación presentaremos algunas medidas que son importantes para caracterizar una red.
2.7.1 Medidas relacionadas a la distancia
En diferentes casos es importante caracterizar a la red mediante medidas de distancia entre no-
dos, por ejemplo en aplicaciones de rutas cortas entre diferentes caminos, o ver grados promedio
de distancias de un nodo dado hacia todos los demás, existen algunas medidas que nos ayudan
a interpretar a la red en función de sus medidas (Costa et al., 2007).
2.7. MEDIDAS 17
2.7.1.1 Distancia promedio
Se puede definir una medida de la red calculando el valor medio de dij , conocida como la
distancia geodésica promedio:
1 ∑
` = dij (1)
N(N − 1)
i 6=j
Un problema con esta definición es que diverge si hay vértices no conectados en la red. Para
evitar este problema, sólo los pares de vértices conectados se incluyen en la suma. Esto evita
la divergencia, pero introduce una distorsión de las redes que tienen pares de vertices no rela-
cionados, ya que para estos casos esta medida mostrará un valor de distancia media bajo y seria
un error ya que esto se espera sólo para redes con un alto número de conexiones. Latora y Mar-
chiori (Latora and Marchiori, 2001) propusieron una medida estrechamente relacionado que se
llama eficiencia global:
1 ∑ 1
E = (2)
N(N − 1) d
6 ij
i=j
Esta medida cuantifica la eficiencia de envío de información entre un par de nodos de la red,
suponiendo que la eficiencia para el envío de información entre dos vértices i y j es proporcional
a la inversa de su distancia. El recíproco de la eficiencia global es la media armónica de las
distancias geodésicas:
1
h = (3)
E
La determinación de distancias más cortas en una red sólo es posible con la información global
sobre la estructura de la red. La distancia efectiva entre dos vértices en general es mayor que la
distancia más corta, y depende del algoritmo utilizado para recorrer la estructura de la red.
2.7.1.2 Vulnerabilidad
En redes como la World Wide Web, Internet, suministro de energía, etc es importante saber que
los componentes (vértices o aristas) son cruciales para su mejor funcionamiento. Los vértices
críticos de una red son considerados como los principales normalmente vértices con mayor
grado, sin embargo, hay situaciones en las que no necesariamente es el más vital para el fun-
cionamiento del sistema. Por ejemplo, todos los vértices de una red en forma de un árbol binario
tiene el mismo grado, por lo tanto no hay ningún centro, pero la desconexión de uno de los vér-
tices más cercano a la raíz y la raíz misma tiene un impacto mayor que la de los que cerca de
las hojas. Esto sugiere que las redes tienen una propiedad jerárquica, lo que significa que los
componentes más cruciales son aquellas en las posiciones más altas en la jerarquía.
Una manera de encontrar los componentes críticos de una red es mediante la búsqueda de
los vértices más vulnerables. La vulnerabilidad de un vértice se puede definir como la caída en
2.7. MEDIDAS 18
el rendimiento cuando el vértice y todos sus aristas se eliminan de la red:
E − Ei
Vi = (4)
E
donde E es la eficiencia global de la red y Ei es la eficiencia después de remover el vértice i. y
la medida de vulnerabilidad global de una red estará dada por:
V = maxVi (5)
i
2.7.2 Medidas relacionadas al agrupamiento y búsqueda de ciclos
Una de las características del modelo de Erdos-Rényi es que la estructura local de un vértice
tiende a ser como un árbol, donde la probabilidad de que existan ciclos en una red depende
del tamaño de la misma, entre mas cantidad de nodos mas probabilidad de existencia de ciclos
y agrupamientos. Cada vertice pose una cantidad asociada que mide el nivel de conectividad
entre sus vecinos el coeficiente es definido por:
2eu
Cu = (6)
ku(ku − 1)
donde eu representa el numero de conexiones compartidas entre los vecinos del vértice u, el
valor de este coeficiente varia entre [01]
2.7.2.1 Coeficiente de agrupamiento
Una forma de caracterizar la presencia de ciclos es a través del coeficiente de agrupamiento.
Dos coeficientes de agrupamiento diferentes se utilizan con frecuencia. La primera, también
conocida como transitividad (Newman, 2001), se basa en la siguiente definición:
3N4
C = (7)
N3
donde N4 es el número de triángulos en la red y N3 es el numero de conexiones triples. Esto
represente el coeficiente de consistencia para medir cuantos conjuntos de tres diferentes conec-
tados son diferentes de un triángulo. Un triángulo es un conjunto de tres vértices con aristas
entre cada par de vértices; un triple es un conjunto de tres vértices donde cada vértice se puede
llegar el uno del otro (directa o indirectamente), es decir, dos vértices debe estar adyacente a
otro vértice (el vértice central).
2.7. MEDIDAS 19
2.7.2.2 Coeficiente de ciclos
Kim y Kim (Kim and Kim, 2005) definen un coeficiente de ciclo para medir qué tan cíclica es
una red. El coeficiente cíclico local de un vértice i se define como la media de la inversa de los
tamaños de los más pequeños ciclos formado por vértice i y sus vecinos:
2 ∑ 1
Θi = aijaik (8)
ki(ki − 1) Sijk
j,k
donde Sijk es el tamaño de la menor ciclo que pasa a través de los vértices i, j, k. Hay que tener
en cuenta que si los vértices j y k se conectan, el más pequeño ciclo es un triángulo y Sijk = 3.
Si no hay ninguna arista que pasa por i, j y k, entonces estos vértices son tipo árbol Sijk =∞.
El coeficiente cíclico de una red es el promedio del coeficiente cíclico de todos sus vértices:
1 ∑
Θ = Θi (9)
N
i
2.7.3 Grado de distribución
la característica mas importante de un nodo es su conectividad, donde ki indica el numero de
conexiones establecida entre el vértice i y los demás, los vertices conectado con i son común-
mente llamados vecinos del vértice i normalmente se mide a una red con el promedio de conex-
iones de sus nodos ku, y esta dada por:
∑N1
ku = ki (10)
N
i=1
donde N representa el numero de nodos y ku el promedio de conexiones
2.7.3.1 Distribución de probabilidad del grado
La característica de los nodos de una red es un atributo importante es por ese motivo que a veces
es necesario saber cual es el máximo grado de un nodo o el mínimo valor
kmax = max ki (11)
2.8. CONSIDERACIONES FINALES 20
2.7.4 Medidas de centralidad
2.7.4.1 Excentricidad
Este tipo de medida es usada para resolver problemas de localización minimizando la maxima
distancia entre un nodo y cualquier otro nodo, y esta dado por:
eu = max{d(u, v) : v ∈ V } (12)
2.7.4.2 Centroides
Dado un grafo no dirigido G de n vértices. Para una par de vértices u y v, gu(v) denota el
número de vértices que están más cerca de u a v, que se gu(v) = |w ∈ V : d(u,w) < d(v, w)|
2.7.4.3 Cercanía
Puede darse el caso minimizar la sum∑a de las distancias de un vértice u ∈ V a cualquier otro
vértice en un grafo G = (V,E) como v∈V d(u, v)
2.8 Consideraciones Finales
La teoría de redes complejas cada día esta avanzando, generalmente nuevas medidas son adi-
cionadas a las ya existentes y las propiedades que estas tienen ayudan a caracterizar de mejor
manera las las redes complejas dado que esta pueden representar diferentes patrones como se-
ries temporales (señales 1D) e imágenes (señales 2D).
Es importante tener en cuenta que las medidas ayudan a caracterizar a las redes de tal manera
que también podrían servir para medir la semejanza entre redes diferentes, para así establecer
rasgos similares entre redes que representan a patrones semejantes.
CAPÍTULO
3
Reconocimiento de patrones y redes
complejas
3.1 Consideraciones iniciales
En este capitulo se explicaran las técnicas actuales para el reconocimiento de patrones mediante
redes complejas para poder explicar como estos son usados se tomaran dos casos de patrones
los cuales son series temporales e imágenes.
Para el caso de series temporales para redes complejas, se hará una comparación entre las
técnicas existentes para poder encontrar tanto ventajas como desventajas que estas puedan tener
y también se hará lo mismo para las aplicaciones relacionadas a imágenes, en este segundo
caso existen pocos trabajos de aplicación de redes complejas al procesamiento de imágenes
donde el grupo de investigación del instituto de Física de la Universidad de Sao Paulo Brasil
es uno de los principales gestores de aplicaciones en reconocimiento de imágenes mediante el
uso de redes complejas, grupo con el cual se pudo interactuar por eso se detallaran los modelos
creados por este grupo los cuales muestran la manera de como estas redes pueden ser usadas en
la clasificación de imágenes en general.
21
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 22
3.2 Series temporales y redes complejas
Observar la realidad no es mas que la manifestación de eventos que pueden ser complejos e
inciertos en el pasar del tiempo, a pesar que estos eventos no siempre son los mismos, ellos
tampoco son totalmente diferentes. Existe una semejanza y continuidad en ellas mismas que
permite generalizar eventos futuros a partir de eventos pasados. Cuando hablamos de una se-
cuencia de valores observados a lo largo del tiempo, y por tanto ordenados cronológicamente,
la denominamos en un sentido amplio serie temporal. Resulta difícil imaginar una rama de
la ciencia en la que no aparezcan datos que puedan ser considerados como series temporales.
Descubrir conocimiento a partir de series temporales es una de las cosas que el ser humano
intenta realizar para conocer mejor las regularidades de las variables observadas, así como la
comprensión del fenómeno que utiliza dichas variables. Dicho entendimiento de los diferentes
fenómenos pueden ayudarnos a realizar posibles predicciones de dichas series (Box et al., 1976).
Cuando el conocimiento exacto de las leyes que gobiernan un determinado fenómeno es
expresado a través de ecuaciones precisas, mediante la formulación de un modelo matemático
adecuado es posible poder predecir acontecimientos futuros de dicho evento. Anticipar el com-
portamiento futuro siempre despertó el interés en las mas diversas areas del conocimiento hu-
mano. Por ejemplo en finanzas, predecir un ratio es de vital importancia para un inversionista,
o predecir la precipitación es importante para los hidrólogos. Denominamos predicción a la
estimación de valores futuros de la variable en función del comportamiento pasado de la serie
(Salas and Delleur, 1980).
A veces obtener un modelo exacto de los diferentes fenómenos que deseamos predecir es
mas difícil de lo pensado, ya que en casos reales, es casi imposible considerar todas las vari-
ables que afectan dicho fenómeno. Lo cual hace no práctico el intentar modelar el fenómeno
a partir de las variables inmiscuidas. Sin embargo una alternativa diferente para poder realizar
una predicción, consiste en la investigación empírica de la serie temporal de la variable a ser
predecida, en búsqueda de la identificación de regularidades presentes en las observaciones de
la serie de interés. Entonces el desafío se enfoca en encontrar dichas regularidades las cuales
normalmente no son siempre evidentes, al contrario normalmente se encuentran enmascaradas
por el ruido en la serie temporal (Franses and Van Dijk, 2000).
Evidentemente aunque el valor futuro de una serie temporal no sea predecible con total
exactitud, para que tenga interés su estudio, el resultado tampoco puede ser completamente
aleatorio, existiendo alguna regularidad en cuanto a su comportamiento en el tiempo, lo que
hará posible su modelado y por ende hasta su predicción. La búsqueda de regularidades y de
patrones ha sido siempre una de las tareas básicas de la ciencia, y muchas veces se descubren
simetrías que sirven de fundamento para la predicción del comportamiento de los fenómenos,
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 23
incluso antes de que se entienda la razón o causa que justifica esa regularidad. Esto ocurre por
ejemplo con el sistema periódico de los elementos como lo describió (Chatfield, 2003).
Por lo tanto, si podemos encontrar patrones de regularidad en diferentes secciones de una
serie temporal, podremos también describirlas mediante modelos basados en distribuciones de
probabilidad. La secuencia ordenada de variables aleatorias X(t) y su distribución de probabil-
idad asociada, se denomina proceso estocástico. Un proceso estocástico es por tanto el modelo
matemático para una serie temporal (Box et al., 1976) que permitirá estudiarla y analizarla.
3.2.1 Series temporales
Una serie Temporal es un conjunto de observaciones ordenadas en el tiempo, que pueden rep-
resentar la evolución de una variable (económica, física, etc.) a lo largo de él. El objetivo del
análisis de una serie temporal es el conocimiento de su patrón de comportamiento, para así
prever su evolución futura, suponiendo que las condiciones no variarán.
Dado que no se trata de fenómenos deterministas, sino sujetos a una aleatoriedad, el estu-
dio del comportamiento pasado ayuda a inferir la estructura que permita predecir su compor-
tamiento futuro, pero es necesaria una gran cautela en la previsión debido a la inestabilidad del
modelo.
La particular forma de la información disponible de una serie cronológica (se dispone de
datos en periodos regulares de tiempo) hace que las técnicas habituales de inferencia estadística
no sean válidas para estos casos, ya que nos encontramos ante n muestras de tamaño 1 proce-
dentes de otras tantas poblaciones de características y distribuciones desconocidas (Liao et al.,
2005). Por eso formalizar el estudio de dichas series.
3.2.2 Técnicas estadísticas para las series temporales
Se llama Serie de Tiempo a un conjunto de mediciones de cierto fenómeno o experimento
registradas secuencialmente en el tiempo. Estas observaciones serán denotadas por (Keogh
et al., 2004):
{x(t1), x(t2), ..., x(tn) = t ∈ T ⊆ R} (1)
Con x(ti) el valor de la variable x en el instante ti. Si T = Z se dice que la serie de tiempo
es discreta y si T = R se dice que la serie de tiempo es continua. El primer paso en el análisis
de series de tiempo, consiste en graficar la serie. Esto va a permitir detectar las componentes
esenciales de la serie.
El gráfico de la serie permitirá detectar (Keogh et al., 2004):
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 24
• Outlier: Son puntos de la serie que se escapan de lo normal. Un outliers es una ob-
servación de la serie que corresponde a un comportamiento anormal del fenómeno (sin
incidencias futuras) o a un error de medición. Se debe determinar desde fuera si un punto
dado es outlier o no. Si se concluye que lo es, se debe omitir o reemplazar por otro valor
antes de analizar la serie. Por ejemplo, en un estudio de la producción diaria en una
fábrica.
• Tendencia: La tendencia representa el comportamiento predominante de la serie. Esta
puede ser definida vagamente como el cambio de la media a lo largo de un periodo.
• Variación estacional:La variación estacional representa un movimiento periódico de la
serie de tiempo. La duración de la unidad del periodo es generalmente menor que un año.
Puede ser un trimestre, un mes o un día, etc. Matemáticamente, podemos decir que la
serie representa variación estacional si existe un número s tal que: x(t) = x(t+ ks). Las
principales fuerzas que causan una variación estacional son las condiciones del tiempo.
Todos estos fenómenos presentan un comportamiento estacional (anual, semanal, etc.)
• Variaciones irregulares: Los movimientos irregulares (al azar) representan todos los tipos
de movimientos de una serie de tiempo que no sea tendencia, variaciones estacionales y
fluctuaciones cíclicas.
Un modelo clásico para una serie de tiempo, supone que una serie x(1), ..., x(n) puede ser
expresada como suma o producto de tres componentes: tendencia, estacionalidad y un término
de error aleatorio. Existen tres modelos de series de tiempos, que generalmente se aceptan
como buenas aproximaciones a las verdaderas relaciones, entre los componentes de los datos
observados.
1. Aditivo: X(t) = T (t) + E(t) + A(t)
2. Multiplicativo: X(t) = T (t)E(t)A(t)
3. Mixto: X(t) = T (t)E(t) + A(t)
dondeX(t) serie observada en instante t; T (t) componente de tendencia,E(t) es el componente
estacional y A(t) componente aleatoria (accidental). Una suposición usual es que A(t) sea una
componente aleatoria o ruido blanco con media cero y varianza constante. Un modelo aditivo
(1), es adecuado, por ejemplo, cuando E(t) no depende de otras componentes, como T (t), sí
por el contrario la estacionalidad varía con la tendencia, el modelo más adecuado es un modelo
multiplicativo (2). Es claro que el modelo multiplicativo puede ser transformado en aditivo
tomando logaritmos. El problema que se presenta es modelar adecuadamente las componentes
de la serie.
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 25
3.2.3 Análisis de series temporales
Normalmente, la mejor forma de comenzar a analizar los datos de una serie temporal es rep-
resentar las observaciones vs. el tiempo a fin de detectar tendencias, patrones, estacionarios, y
outliers. Si la variabilidad de la serie cambia con el tiempo, es conveniente aplicar una transfor-
mación a los datos que estabilice la varianza. Se suele utilizar una transformación logarítmica
o, en ocasiones, considerar el cambio porcentual de cada observación a la siguiente (en lugar de
las propias observaciones).
En el análisis de las series temporales se considera que las observaciones contienen: a) un
patrón sistemático, y b) un componente de error aleatorio al que llamaremos ruido. La mayoría
de las técnicas tienen como objetivo filtrar dicho ruido.
3.2.4 Análisis de series temporales mediante representación por redes
complejas
Para poder realizar una análisis desde el punto de vista de redes complejas primero es necesario
modelar las series temporales como redes complejas, existen varias propuestas para dicho mod-
elamiento a continuación se mostraran cada uno de ellos para finamente presentar las ventajas
y desventajas que cada modelo tiene.
Diferentes trabajos vienen analizando y comparando varias métodos trabajos como los de
(Zhang, 2007), (Wang, 2011), (Campanharo et al., 2011) esto permite entender la relación que
existen entre las propuestas que serán presentadas
3.2.4.1 Redes de transición
El concepto de la dinámica simbólica permite caracterizar las propiedades de un sistema dinámico
basado en una partición S1, ..., SK de su espacio de fases enK conjuntos disjuntos, produciendo
una transformación de toda trayectoria posible en una secuencia de símbolos abstractos. For-
malmente, la correcta aplicación de los conceptos de análisis simbólico de series de tiempo,
requieren la existencia de una partición que corresponde a una asignación única de secuencias
simbólicas para cada trayectoria del sistema. Se debe tener en cuenta que este requisito es gen-
eralmente violados en aplicaciones del mundo real debido a la presencia de ruido, sin embargo,
ni siquiera en las particiones de casos ideales (sin ruido) se puede estimar. Sin embargo, las
aplicaciones de análisis simbólico de series de tiempo han acaparado el interés considerable en
numerosas aplicaciones (Donner et al., 2008) (Donner et al., 2010).
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 26
El particionamiento del espacio de fases de un sistema dinámico puede ser utilizado para
transformar una serie de tiempo en una representación mediante red compleja. En el caso más
simple es posible identificar los diferentes conjuntos Si como vértices de una red y considerar
las probabilidades de transición para caracterizar las aristas estableciendo una probabilidad de
transición Pmin como un threshold a partir del cual se conectaran las aristas.
Esta manera de crear la red tiene una clara desventaja es que cuando existen variaciones
pequeñas en las amplitudes de la serie temporal al no superar el threshold Pmin se pierde la
información en consecuencia series con pequeñas variaciones serán representadas como redes
similares.
3.2.4.2 Redes de búsqueda de ciclos pseudo periódicos
En 2006, Zhang y pequeños (Zhang et al., 2008) sugirió el estudio de las características topológ-
icas de series de tiempo pseudoperiodicas a través de redes complejas. Esta propuesta considera,
los ciclos individuales como vértices de una red no dirigida, y la conectividad de los pares de
vértices ha sido establecido por el coeficiente de correlación de los ciclos de diferente longitud
o alternativamente, considerar la distancia del espacio de fases.
Un punto de la crítico a este método es que la definición de un ciclo no esta presente nece-
sariamente en sistemas oscilatorios complejos. En (Zhang et al., 2008), los autores consideraron
principalmente los osciladores no lineales en sus regímenes de fase coherente, sin embargo no
es claro cómo podría ser un ciclo definido de oscilaciones fase nocoherente, por ejemplo un
sistema caótico. Además, no es intuitivamente claro la forma de interpretar las correlaciones de
los ciclos, ya que los valores de las medidas correspondientes a la correlación no están exclusi-
vamente determinadas por la proximidad de las partes correspondientes de la trayectoria en el
espacio de fase, sino que dependen también de la elección concreta de muestreo. Esto podría
dar estimaciones bastante diferentes de coeficientes de correlación entre dos ciclos cercanos.
3.2.4.3 Redes correlacionadas
Una generalización del método anterior propuesto por Zhang pero a diferencia del anteriores
que solo se aplica a señales pseudo periódicas este modelo se puede aplicar a series de tiempo
sin evidentes componentes oscilatorios Yang y Yang (Yang and Yang, 2008) en este modelo se
define una dimensión de inmersión simple sobre una serie de tiempo arbitrario, y cada vértice
será representado por la dimensión de inmersión de la serie arbitraria a partir de la cual se puede
calcular el coeficiente de correlación de Pearson a partir del cual dos vértices serán conectados
si superan un threshold. Una dificultad de este método es determinar cuál es la dimensión de
3.2. SERIES TEMPORALES Y REDES COMPLEJAS 27
inmersión mas adecuada para representar la señal en una red compleja dado que no se conoce
mucho de la series puesto que es objeto de estudio (Marwan et al., 2009).
3.2.4.4 Redes según su visibilidad entre estados
Esta propuesta a diferencia de las demás considera como vértice a cada valor de la serie tem-
poral, eso quiere decir que se tendrá tantos vértices como valores tenga la serie temporal y
conectara dos nodos si estos son visibles entre si, eso quiere decir que entre dos estados no haya
un valor mayor al promedio de los dos estados de tal manera que se garantiza la visibilidad entre
estados. Esta propuesta tiene como principal desventaja de caracterizar mas las series aleatorias
y perder algunas de las propiedades de las series temporales caóticas (Lacasa et al., 2008).
3.2.4.5 Redes formadas por el vecino más cercano
Este método define un numero de k para establecer la relación entre dos nodos por lo tanto lo
primero que tiene que realizarse es un agrupamiento donde los vecinos más cercanos a cada es-
tado de la serie temporal, representaran un vértice y dos nodos estarán conectados si ellos están
dentro de la vecindad de un grupo ki, esta aproximación no diferenciara entre redes aleatorias y
caóticas dado que ambas aproximan el espacio de fases y la temporalidad no es considerada en
la conexión de la misma (Xu et al., 2008).
3.2.4.6 Redes Recurrentes
Otro modelo es propuesto por (Xu et al., 2008) el cual particiona el espacio de estados mediante
el uso de un retardo de tiempo dado y dimensión embebida, a continuación, se seleccionan un
número fijo de vecinos más cercanos conectar los nodos. Este modelo resalta las propiedades de
recurrencia de la serie de tiempo original. Similar a las propuestas a otras propuestas donde se
usan representaciones a través de plots de recurrencia. Una variación de esta idea es propuesta
por (Hirata et al., 2008) propone también el uso de plots de recurrencia a partir del cual crea
una matriz de distancias el cual sera considerado como la matriz de adyacencia además añade
pesos siendo este un grafo dirigido.
3.2.4.7 Otros Métodos
Otros métodos para la creación de redes complejas a partir de series temporales son menciona-
dos a continuación
3.3. IMÁGENES Y REDES COMPLEJAS 28
• Otra forma de crear redes complejas fueron propuestas en (Bialonski, 2012) donde anal-
iza diferentes aplicaciones en las cuales se modelan redes complejas, por ejemplo en
el análisis de series temporales que son capturadas de diferentes sensores siendo la red
modelada en función a la correlación que tengan las series temporales capturadas, se pre-
sentan aplicaciones en electro encefelogramas donde cada electrodo es un nodo en la red
y la correlación entre la serie temporal para diferentes intervalos de tiempo son usadas
para crear los enlaces de tal forma que se pueden tener diferentes redes complejas que
pueden ser analizadas.
• Una variación también es propuesta en (Luque et al., 2009) es cual es similar al modelo
basado en visibilidad la diferencia que la linea de vision usada es horizontal siendo esta
un caso particular del cuarto método.
3.2.5 Problemática actual en la representación de las señales
Para el primer método existe una perdida significativa de información, dado que existe un parti-
cionamiento del espacio de estados, el segundo método es bien definido en sistemas oscilatorios
(dado que busca ciclos repetitivos) pero no es muy bien definido para estados no coherentes
como el caos, para el tercer método también busca ciclos de forma arbitraria la desventaja es
determinar la dimensión de los ciclos que se están buscando, el cuarto caso caracteriza mas
las series temporales aleatorias, siendo que las caóticas pierden algunas de sus propiedades y
finalmente este ultimo método no distinguirá los sistemas determinista de los aleatorios
3.3 Imágenes y redes complejas
Una imagen puede ser definida como una función bi-dimensional f(x, y), donde x e y son coor-
denadas espaciales, y la amplitud de f en cualquier par de coordenadas se denomina intensidad
o nivel de gris de la imagen en el punto. Cuando x, y y los valores de la amplitud de f son todos
finitos, cantidades discretas, estaremos ante una imagen digital. El procesamiento de imágenes
digitales concierne al uso de la computadora en el procesamiento de imágenes. Note que una
imagen digital está compuesta de un número finito de elementos, cada uno de ellos teniendo
una particular localización y valor. Esos elementos se llaman elementos pictóricos, elementos
unidad de imagen o píxeles.
Diferentemente a los seres humanos, que están limitados a la banda visual del espectro elec-
tromagnético (EM), las máquinas de imagen cubren prácticamente todo el espectro EM, desde
los rayos gamma hasta las ondas de radio. Pueden trabajar también con imágenes generadas
3.3. IMÁGENES Y REDES COMPLEJAS 29
por fuentes que los humanos no están acostumbrados a asociar con imágenes. Estas fuentes
incluyen las imágenes ultrasónicas, la microscopía electrónica y las imágenes generadas por or-
denador. En definitiva, el procesamiento de imágenes digitales concierne a un amplio y variado
elenco de campos de aplicación. No existe un acuerdo unánime de cuáles son los tópicos que
cubre el Procesamiento de Imágenes Digitales y cuáles son sus interrelaciones con otras áreas
como Visión por Ordenador o Informática Gráfica.
Desde los años sesenta del siglo pasado, el procesamiento de imágenes digitales se ha con-
vertido gradualmente en una de las áreas de investigación científica más importantes. Sin em-
bargo, como cualquier algoritmo de procesamiento de imágenes requiere una vasta capacidad
de procesamiento, su desarrollo limitado ha estado en las manos de unos pocos expertos. Pero
con el desarrollo rápido de los ordenadores, muchas personas han ido apuntando su gran interés
por el procesamiento de imágenes. El desarrollo del procesamiento de imágenes está siendo
acelerado aún más con el rápido avance de las tecnologías relacionadas con la computación en
paralelo, la maximizada capacidad de memoria de los chips, y el sistema de visualización en
color de alta-resolución.
3.3.1 Textura de una imagen
La textura es un ente visual que describe cierto orden estructural o tendencia en los elemen-
tos presentes en una imagen. La figura que se muestra a continuación presenta cuatro tipos de
textura y su histograma representativo. Es una región macroscópica estructurada de la imagen
que presenta propiedades locales constantes, lentamente variables o aproximadamente periódi-
cas. Este orden local radica en la presencia repetida y no casual de partes Elementales que
tienen dimensión similar. Depende de la escala a la que se observa la imagen: la textura de
un píxel no está definida, hay que estudiar la vecindad de un grupo de píxeles. Dependiendo
del tamaño de vecindad elegido la textura puede ser diferente. Características: uniformidad,
densidad, tosquedad, aspereza, regularidad, linealidad, dirección, frecuencia, fase.
Para clasificar la textura se pueden utilizar diferentes técnicas como por ejemplo las redes
neuronales (son preferibles del tipo perceptrón multicapas por el elevado número de entradas
propias de la clasificación de las imágenes), de forma tal que se identifique la tendencia en
las tonalidades de grises presentes en la misma. Ello es, se define un área representativa en la
imagen que mejor describa la textura que se pretende clasificar y se utiliza la información de
los píxeles que la forman (y cierta región de interés) a la que se le asigna determinada clase que
la distinga de otros tipos de textura,
3.3. IMÁGENES Y REDES COMPLEJAS 30
3.3.2 Clasificación de texturas
Para clasificar texturas se pueden usar métodos (Parker, 2010):
• Métodos Estadísticos: La distribución espacial de valores de gris es una calidad que de-
fine la textura. Analizando la distribución espacial de los valores de gris, se computan
características locales de la textura.
• Métodos Geométricos: Consideran la textura compuesta por primitivas. Intentan describir
las primitivas y las reglas que gobiernan la organización espacial.
• Métodos basados en modelos: Se basan en la construcción de un modelo que describe la
textura. Se pueden utilizar para reconocer texturas o para sintetizarlas.
En el caso de representación de texturas mediante redes complejas tenemos algunos modelos
que presentan ventajas y limitaciones que a continuación se explicara.
3.3.3 Representación de texturas mediante redes complejas (Wesley, 2010)
(Backes, 2010)
La descripción de método de representación de la red compleja a partir de una imagen, es a
partir de una malla regular, donde los pixels de la imagen corresponden a los nodos de la malla
y sus aristas serán los 8 vecinos como puede apreciarse en la siguiente figura 3.3.
Figura 3.1: representación de una imagen mediante una malla regular conectada con los 8
vecinos (Wesley, 2010).
Para generar los diferentes modelos será considerado la distancia entre nodos de la malla
regular es decir se debe dar un radio de proximidad permitida para la generación de la red. eso
3.3. IMÁGENES Y REDES COMPLEJAS 31
significa que dos nodos de la red regular estarán conectados si la distancia entre los pixeles no
supera el valor del radio pre establecido.
Como segundo paso se tomara en consideración el valor de intensidad de imagen eso quiere
decir que la semejanza entre un pixel y otro se verá reflejado en el peso de conexión entre
los nodos de la red. Para un caso simple se puede usar simplemente el valor absoluto de la
diferencia entre intensidades de los pixeles vecinos ( en el grado son representados como dos
nodos vecinos ) el cual si no supera el umbral establecido la conexión se mantendría en caso
contrario esa conexión se rompe en ese sentido el grafo deja de ser regular y comienza a vol-
verse red compleja. Este umbral también ira cambiando generando diferentes modelos de redes
complejas
Figura 3.2: Creación de diferentes redes a partir de la malla regular (Wesley, 2010).
3.3.4 Contornos de una imagen
La detección de contorno es parte de un proceso de aislamiento (segmentación), que consiste
en la identificación de objetos dentro de una imagen. Como es usual, hay varias posibles defini-
ciones de un contorno, siendo cada una aplicable en distintas circunstancias. Una de las más
comunes y generales definiciones es el contorno es simplemente un cambio en el nivel de gris
que ocurre en una ubicación especifica. Cuanto mayor es el cambio de nivel, más fácil resulta
detectar el contorno, pero en el caso ideal cualquier cambio de nivel puede ser visto fácilmente.
3.3. IMÁGENES Y REDES COMPLEJAS 32
Una complicación en la detección de un contorno ocurre debido a la digitalización. Es poco
probable que una imagen sea muestreada de manera tal que todos los contornos correspondan
exactamente con un pixel del borde. Por lo general, el cambio de nivel puede extenderse sobre
varios pixeles. Y cuando eso ocurra la posición actual del contorno se considera como el centro
de la rampa que conecta el nivel bajo de gris con el nivel alto. Esta es una rampa sólo en el
mundo matemático, dado que después de que la imagen ha sido digitalizada (muestreada), la
rampa tiene una apariencia escalonada.
La segunda complicación es el clásico problema del ruido. Debido a una gran cantidad de
factores como la intensidad de la luz, el tipo de cámaras y lentes, el movimiento, la temperatura,
efectos atmosféricos, polvo y otros; difícilmente dos pixeles que correspondan precisamente al
mismo nivel de gris en la escena tengan el mismo nivel en la imagen. El ruido es un efecto
aleatorio, y es caracterizado sólo estadísticamente. El resultado del ruido en una imagen es
que produce variaciones aleatorias en el nivel de un pixel a otro, y entonces las líneas suaves y
rampas de los contornos ideales nunca son encontradas en las imágenes reales.
Por eso usar contornos para modelar redes complejas depende en su mayoría de métodos de
segmentación y métodos de detección de contornos.
3.3.5 Métodos para detección de contornos
La forma más simple de detectar un contorno es realizar primero una binarización de la imagen,
esta binarización puede ser realizada mediante un threholding, donde ante un valor umbral los
valores que excedan este umbral tomaran el valor de uno y el resto el valor de cero una vez
realizada este proceso, el siguiente paso es detectar las discontinuidades eso quiere decir buscar
los cambio de valores de 0 a 1 o viceversa de tal manera que se obtiene el contorno de la imagen.
El otro método de buscar discontinuidades es la correlación de la imagen con una máscara.
En este procedimiento se realiza el producto de los elementos de la máscara por el valor de
gris correspondiente a los pixels de la imagen encerrados por la máscara esta mascara puede
ser de diferentes formas normalmente es una máscara de tamaño 3x3 la cual puede representar
diferentes tipos de operadores como por ejemplo Roberts, Prewitt y Sobel.
3.3.6 Creación de red compleja a partir de contornos
Como se puede a preciar en la figura la forma de crear la red compleja es a partir de la distancia
entre los diferentes puntos del contorno es por ese motivo que es necesario primero extraer el
contorno de forma adecuada una vez extraído el contorno se procederá a dar diferentes valores
de radios de tal manera que dos nodos estarán conectados si la distancia entre cualquier par de
3.3. IMÁGENES Y REDES COMPLEJAS 33
nodos es menor que cierto valores predefinidos de tal manera que se tendrán varios modelos
de redes complejas para los diferentes umbrales dados, cada red creada caracterizara alguna
propiedad de la forma de la imagen.
Figura 3.3: Creación de diferentes redes a partir del contorno de una imagen.
3.3.7 Situación actual y problemática en la representación de imágenes
En el caso de las imágenes ya existen algunas propuestas para poder representar una imagen
mediante red compleja pero es importante notar que existen algunas deficiencias que se tiene
que detallar
• Los métodos actuales de construcción de la red son muy simples generan el grafo basados
en distancia dado por un radio predeterminado y analizan las propiedades de la imagen
por separado (forma y textura)
• La forma es considerada mediante los contornos creando redes en función a la detección
de los mismos pero cuando se detecta un contorno se olvidan aspectos como:
– Obviar puntos internos de la imagen (Geometría interna)
– Obvia textura del borde como se comento el borde no es un solo pixel sino general-
mente es una gran catidad de pixeles eso indica que un borde puede tener un especie
de textura del mismo.
• En cuanto al modelo que se basa en la textura se considera la semejanza de intensidades
de niveles de gris entre los pixeles, y esto por el contrario del método anterior:
3.4. CONSIDERACIONES FINALES 34
– Obvia contornos y estructuras internas lo que no es adecuado para una buena repre-
sentación de una imagen
3.4 Consideraciones finales
Como se puede ver existen diferentes maneras de construir redes complejas a partir de series
temporales, cabe resaltar que cada una de ellas tiene ventajas y desventajas en cuanto a su uso
en las diferentes aplicaciones que este pueda tener: Para el primer método existe una perdida
significativa de información, El segundo método es bien definido en sistemas oscilatorios pero
no es muy bien definido para estados no coherentes caos, para el tercer método la desventaja
es determinar la dimensión de los ciclos, el cuarto caso caracteriza mas las series temporales
aleatorias, siendo que las caóticas pierden algunas de sus propiedades, finalmente este ultimo
método no distinguirá los sistemas determinista de los aleatorios
Los métodos actuales de construcción de la red a partir de imágenes, son muy simples
generan el grafo basados en distancia (radio) en función a los contornos se crearan las redes
y por medio de la distancia dada por un radio distancia se enlazaran los puntos de la red este
método, obvia puntos internos (geometría interna), obvia textura interna y textura del borde, y
son dependientes de otros métodos como la detección de contornos. Cuando se usa la textura
se crean redes también basados en un radio de distancia solo que se usara el color como el
responsable de la conectividad, en ese sentido se obvia los contornos y estructuras internas del
objeto a analizar y son dependientes de la calidad de captura de imágenes (intensidades de color
bien definidas).
CAPÍTULO
4
Método propuesto
4.1 Consideraciones iniciales
A continuación se explicaran los modelos propuestos para poder realizar el reconocimiento de
patrones, la idea propuesta es genérica, en el sentido de que puede servir para representar pa-
trones unidimensionales como es el caso de las series temporales y bidimensionales para el caso
de images donde la misma idea es extendida de forma natural, de tal manera que los patrones
pueden ser tratados de la misma forma, no interesando la dimension a pesar que una serie tem-
poral y una imagen son diferentes en dimension, ambas corresponden a patrones comunes de
nuestro mundo.
4.2 Esquema general de la propuesta
Como se puede ver en la figura 4.1 se tiene un objeto de estudio el cual corresponde al patron
que se quiere reconocer, dado que son dos tipos de patrones que se reconocerán, este patron
puede ser una serie temporal o una imagen, según sea uno u otro patron es que se tratan por
separado, cabe aclararse que el uso de las redes complejas se usa únicamente para obtener el
vector de características, donde se ataca principalmente el problema de modelamiento de una
35
4.2. ESQUEMA GENERAL DE LA PROPUESTA 36
red a partir de un patron para luego usar alguna medida de redes complejas para poder realizar
la caracterización de la red en análisis:
Figura 4.1: Esquema general de la propuesta de reconocimiento de patrones mediante redes
complejas.
Si el patron fuese una señal temporal la dinámica de la misma es la característica mas im-
portante a conservar, además se debe tener en cuenta la temporalidad de los estados (existe un
orden dado por el tiempo). Si el caso fuese de una imagen la creación de la red sigue siendo
la misma ya que la diferencia con la serie temporal es que esta señal es de dos dimensiones,
cuando uno trata con este tipo de señal la ubicación de un estado depende de dos variables x, y
y no solo una como pasaba en el caso de una serie temporal, una imagen representa objetos que
quieren ser reconocidos donde normalmente las características que tienen estos objetos están
en función de la forma, siendo esta una característica importante para su reconocimiento. Otro
aspecto importante es la textura que posee el objeto, porque a pesar de tener objetos de formas
semejantes estos pueden tener texturas distintas, en ese sentido es importante tomar en cuenta
esta característica al momento de la representación.
La representación de los patrones mediante una red compleja deben tener en cuenta las car-
acterísticas que anteriormente se mencionaron, por eso las propuestas toman en cuenta esas
características al momento de proponer los modelos respectivos. En la propuesta considera el
preprocesamiento tanto para las series temporales como para las imágenes a diferencia de otras
técnicas propuestas que necesitan de una cantidad considerable de técnicas distintas de proce-
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 37
samiento, las que se usan en el sentido de hacer eficiente el manejo de las mismas, ya que una
seria temporal y una imagen normalmente tienen miles de elementos y como los modelos prop-
uestos consideran todos estos elementos es que se hace necesario una reducción de la misma,
pero esa reducción debe preservar las propiedades de cada una de las señales en el caso de las
imágenes es fácil de entender este aspecto ya que uno puede disminuir el tamaño de una ima-
gen disminuyendo la resolución del mismo, claro que existe un limite que para este caso el cual
dependería de la capacidad de memoria que puede soportar el computador pero hoy en día se
pueden procesar varias señales sin problemas, este aspecto solo afectaría a señales que tengan
una dimensionalidad muy grande.
El primer paso para trabajar con la propuesta es hacer representación de la señal como red
compleja para luego caracterizarla red mediante alguna medida de redes complejas que esta red
pueda tener, como se presente en el capituló 2 existen muchas medidas que las redes complejas
pueden tener, en ese sentido se probaron métricas que pueden ser usadas para la caracterización
adecuada del patron a reconocer medidas de grado de conectividad de una nodo obteniendo así
el vector de características.
Finalmente una vez obtenido el vector de características la etapa final implica el uso de
algún clasificador el cual en el caso de la propuesta se usa el support vector machine, pero hay
que tener en cuenta que al usar las redes complejas normalmente el vector de características
tiene una gran dimensionalidad, por eso es necesario hacer uso de técnicas de reducción de la
dimensionalidad como es el caso de esta propuesta que usa el Linear Discriminant Analysis
los detalles de cada una de las estabas se presentaran en las siguientes secciones donde se
describirán detalladamente cada una de las etapas.
4.3 Propuesta para caracterizar series temporales mediante
red compleja
Es importante notar que ya existen métodos que representan las series temporales como se men-
ciono en capítulos anteriores por ese motivo es importante mencionar algunos las diferencias a
las propuestas anteriores tienen al momento de la representación.
• A diferencia del modelo de redes de transición en el modelo propuesto no habrá parti-
cionamiento del espacio de estados, siendo cada valor de la amplitud de la honda el valor
utilizado directamente en el modelamiento del grafo
• En los modelos basados en visibilidad la conexión entre entre un nodo en la posibilidad
de trazar una linea directa entre uno u otro estado si hubiese un estado intermedio que ob-
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 38
staculice la linea simplemente no existe conexión en caso contrario existiría conexión en
ese sentido el modelo propuesto usa la distancia entre estados sin considarar la visibilidad
de los mismos.
• En relación a las redes de búsqueda de ciclos pseudo periódicos, la propuesta no busca
ciclos usa directamente las amplitudes y la distancia entre ellas para crear la Red
• En los métodos de redes correlacionadas se calculan coeficiente de correlación, nuestra
propuesta no calcula ningún tipo de correlación solo usa distancia euclidiana entre su
estados.
• En cuanto a las redes formadas por el vecino más cercano podría ser parecido la diferencia
principal es que no se restringe a k posibles estados se usa todos los que se encuentren a
una distancia dada.
4.3.1 Representación de la serie temporal por red compleja
Como se vio en el capitulo anterior una serie temporal es una secuencia de estados a lo largo del
tiempo en la siguiente figura 4.2 se puede apreciar un ejemplo de de serie temporal el cual cor-
responde una señal de voz correspondiente a la palabra uno, naturalmente uno puede apreciar
que es una secuencia de distintos estados donde la variable temporal debería definir la vecindad
que tiene un estado con el siguiente estados de la serie, esto es importante ya que el orden en el
cual están distribuidos esas secuencias son las que hacen que esa señal corresponda a la palabra
uno, si se tuviese otra secuencia de estados (otra serie con otro orden) esta correspondería a otra
palabra como se puede apreciar en la figura 4.3 donde se puede apreciar otra distribución de es-
tados, las cuales corresponden a la palabra dos, entonces podemos tener como punto importante
de una señal la secuencia de valores de la serie y cuando estos valores toman otro orden y otras
amplitudes esta debería corresponder a otro tipo de señal.
El modelo propuesto para construir la red sera el siguiente, sea X el conjunto de valores
correspondientes a la serie temporal el cual es un vector de X[x1, x2, ..., xi, ..., xN ] donde xi
corresponde al valor de cuantización de la serie temporal, otro valor importante en una serie
temporal corresponde a su ubicación temporal, por lo tanto el valor x1 corresponde a la posición
temporal t1, siendo que existe un vector de T donde T [t1, t2, ..., ti, ..., tN ] de tal manera que se
forma un par ordenado (xi, ti), de esta forma cada par ordenado corresponderán a puntos en el
espacio deX×T cada punto corresponderá a la posición de los vertices del grafo de nuestra red
compleja donde el grafo es G(V,A) siendo V los vertices formado por el conjunto de puntos
de la serie t√emporal y A las aristas, las cuales se crearan en función a la distancia euclidiana
d(v 2 2
i, vj) = (si − sj) + (ti − tj) entre un par de vertices, por lo tanto sera necesario definir
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 39
Figura 4.2: Ejemplos de serie temporal correspondiente a la palabra uno.
Figura 4.3: Ejemplos de serie temporal correspondiente a la palabra dos.
un valor umbral Θ, el cual esta formado por un conjunto de valores Θ[θ1, θ2, ..., θi, ...θM ] donde
θi corresponde a un valor umbral el cual sera usado para crear una arista entre dos vertices del
grafo G(V,A) donde cada nodo del grafo calculara la distancia euclidiana con todos los demás
nodos de la red, de tal manera que una arista si se cumple que la distancia entre un par de
vertices es menor o igual a un valor θi, dado que Θ es un conjunto deM valores es que existirán
M redes complejas.
En las siguientes figuras 4.4 se pueden ver ejemplos de construcción de redes complejas a
partir de un segmento de la serie temporal de la palabra uno, donde pueden observarse 4 figuras
correspondientes a 4 valores de θ distintos pudiéndose apreciar como el numero de conexiones
entre dos nodos aumenta a medida que el valor de θ aumenta.
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 40
Figura 4.4: Ejemplos de redes complejas para diferentes valores de θ en la figura (a) el valore
de θ = 1, (b) el valor de θ = 5, (c) el valor de θ = 10, (d) el valor de θ = 15.
Para poder calcular la distintas redes complejas es necesario calcular una matrizD deN×N
entre los diferentes vertices de la red tal manera que:
 
 d
 1,1 d1,2 ... d1,i ... d1,N 
 d2,1 d2,2 ... d2,i ... d 
2,N 
 . .
.. .. . . . ... ... .. 
D = 
.  (1)
 dj,1 dj,2 ... d 
 j,i ... dj,N
. . . . 
.. .. ... .. ... .. 
dN,1 dN,2 ... dN,i ... dN,N
donde di,j corresponde a la distancia euclidiana entre un par de vertices, dado que el tamaño
de dos series temporales de una misma palabra tienen en general tamaños distintos y los valores
de la cuantización son variados para una misma palabra hablada, es que se deberá hacer una
normalización en el tamaño de dicha serie, de tal manera que deberán ser colocados en un
rango entre valores entre [0, 1] para poder hacer esta normalización se realizara el siguiente
calculo:
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 41
D
D = (2)
maxdij
donde maxd corresponde al valor máximo de la matriz D de esa manera las distancias
ij
quedan normalizadas entre los valores [0, 1], dado que los valores ahora están normalizados
el valor del umbral θ tendrá también valores entre [0, 1]. Una vez que se tienen los valores
normalizados es mas fácil obtener las diferentes redes a partir de las cuales se obtendrá el
vector de características.
4.3.2 Obtención del vector de características
El modelo genera varias redes las cuales pueden ser representadas como matrices de adyacencia
y sobre las cuales se calcularan los diferentes vectores de características. Para obtener las
matrices de adyacencia A[A1, A2, ..., Ai, ..., AM ] siendo A el conjunto de matrices y Ai una
matriz de adyacencia para un determinado umbral, la cual se puede obtener con la siguiente
ecuación:
Ai = F (D, θi) (3)
donde Ai corresponde a la matriz resultante, D es la matriz de distancias, θ es el valor del
umbral y la función F y se calcula para cada valor de la matriz de distancias dij como se puede
ver en la siguiente ecuación 4:
{
1 si dij ≤ θi
aij = F (dij, θi) = (4)
0 si dij > θi
El resultado sera una matriz Aij de valores binarios, donde el valor de uno corresponde un
enlace entre el nodo i y el nodo j.
Una vez obtenidas las matrices de adyacencia, el siguiente paso es calcular los valores del
vector de características V [v1, v2, ..., vi, ..., vM ] donde vi se calcula usando el grado de un nodo
gi el cual es: ∑N
gi = aij (5)
j=1
siendo gi el grado del nodo i este es usado para calcular el grado promedio del grafo Ai, de
tal forma que el valor cada componente del vector de características vi es el valor promedio
conexiones de la red Ai como se puede ver en la siguiente ecuación 6:
4.3. PROPUESTA PARA CARACTERIZAR SERIES TEMPORALES MEDIANTE RED
COMPLEJA 42
N
1 ∑
vi = gi (6)
N
i=1
Una cosa que es interesante notar es que los valores de la matriz de adyacencia A1 tienen el
valor de 1 para las distancias menores e iguales que θ1, siendo que θ1 < θ2, entonces la matriz
A1 esta contenida en la matrizA2, este punto es importante ya que calcular una matriz para cada
valor de θi haría que el proceso sea pesado en el calculo de las matrices de adyacencia, además
considerando que las señales de sonido son generalmente de gran dimension lo cual haría que
el proceso de obtención de características sea mas pesado aun.
Por ese motivo para poder alivianar el calculo es que se utilizan algunas variables adicionales
las cuales ayudaran a aprovechar los cálculos de matrices anteriores para los valores promedios
de cada una de las matrices que conforman el vector de características. Dado que los valores de
θi se deben incrementar es que existe una constante δθ que hará que el valor de θ2 = θ1 + δθ,
entonces si el valor de incremento fuese δθ = 0.1 y el valor de θ1 = 0.1 considerando que el
valor de θM = 1 siendo este el máximo posible entonces se tentarían 10 valores distintos.
Entonces el modelo usa este valor para multiplicarlo con todos los valores de la matriz de
distancias normalizadas obteniéndose un nuevo valor D′ = pM × Dq el cual tendrá como
máximo valor de M y los posibles valores que esta matriz tendrá numeros enteros entre [1,M ],
además el tamaño del vector de características es M en ese sentido para poder disminuir el
numero de cálculos la nueva matriz de distancias se recorrerá una sola vez y los valores de
esta matriz dij corresponderán a la posición del vector de características de tal manera que se
irán acumulando, asi el resultado correspondería ana especie de histograma de la matriz de
distan∑cias. Finalmente sobre ese histograma se calculara el valor acumulado siendo el valor de
v′i = M
j=1 vi. Por ejemplo si M = 3 y tuviésemos la siguiente matriz D′:
 
 1 2 3
′ 
D = 3 3 3  (7)
2 2 3
Y el vector de características de valores acumulados quedaría como resultado V = [1, 3, 5],
de esta manera el tiempo de calculo del vector de características disminuye significativamente
y hace factible que el modelo pueda ser aplicado en problemas reales.
Hay que notar que para poder representar una señal en general es importante considerar los
estados o valores que componen la señal ya se 1D o dos 2D cada señal tiene sus peculiaridades
y valores a resaltar y preservar en ese sentido tanto el modelo para series temporales como para
imágenes son parecidos a continuación explicaremos la propuesta para imágenes.
4.4. PROPUESTA PARA LA CARACTERIZACIÓN IMÁGENES MEDIANTE REDES
COMPLEJAS 43
4.4 Propuesta para la caracterización imágenes mediante re-
des complejas
Una imagen captura diversos aspectos que corresponden a una escena, cuando la imagen cap-
turada corresponde a un objeto de interés, es importante caracterizarlo por ese motivo, para
poder representarlo es importante considerar algunos aspectos:
• Considerar la forma: el cual es usado para diferenciar la morfología entre uno u otro
objeto, como es el caso de las figuras geométricas.
• Considerar la textura: La imagen de un objeto normalmente es una una composición de
las distribuciones de intensidad del color además de otros objetos y cuando estos objetos
que los componen y estos son repetitivos, o periódicos, o aleatorios todos estos aspectos
se consideran al evaluar una textura.
• Considerar los niveles de intensidad (color): el color es una percepción visual además los
objetos normalmente tienen un color que lo caracteriza por eso esta característica tiene
que ser considerada.
4.4.1 Representación de la imagen por red compleja
El modelo considerara cada aspecto al momento de representarse como una red, dado que una
imagen puede ser representada como una función f(x, y) donde x y y corresponden a las posi-
ciones de los distintos pixels los cuales están distribuidos como una matriz las cuales tienen
asociados niveles de intensidad en cada posición x, y en consecuencia una imagen puede ser
vista como una superficie en 3D como se puede ver en la siguiente figura 4.5.
En el modelo propuesto, un vértice de la red es el punto P (x, y, I) donde x y y son las
posiciones de los diferentes pixels que los componen e I corresponde al nivel de intensidad,
y se usara la distancia euclidiana entre los vertices para definir las aristas al igual que en la
representación de series temporales, con la diferencia que este tiene un parámetro mas que es la
intensidad, en la siguiente figura 4.6 se puede ver la imagen tomográfica de un cerebro, además
se puede ver la visualización 3D de la misma y finalmente los vertices que corresponden a las
posiciones de cada pixel, se puede notar que esta es una imagen de resolución baja para poder
apreciar las posiciones de los vertices continuos es que se muestra en un espacio mayor como
se puede apreciar claramente en la figura 4.6:
Para poder determinar las aristas se usara el calculo de la distancia entre cada nodo, para el
caso de las imágenes se usara la siguiente ecuación 8:
4.4. PROPUESTA PARA LA CARACTERIZACIÓN IMÁGENES MEDIANTE REDES
COMPLEJAS 44
Figura 4.5: Imagen como una superficie 3D en diferentes ángulos.
√
dij = α((xi − x 2 2 2
j) + (yi − yj) ) + β(Ii − Ij) (8)
donde el valor de α y β corresponden a variables paramétricas que ayudan a dar importancia
a ciertos aspectos, por ejemplo si se tienen valores altos para α y bajos para β eso quiere decir
que vecindades cercanas de pixeles tienen mayor importancia que la semejanza de los niveles
de intensidad y si el fuese el caso contrario los valores de intensidad serían priorizados.
Al igual que el modelo para series temporales se crearan diferentes redes, las cuales se
crearan en función a umbrales distintos Θ[θ1, θ1, ..., θi, ..., θM ] generando varias redes en la
siguiente figura 4.7 se puede apreciar el efecto que tiene el valor de diferentes umbrales, donde
claramente que valores bajos del parámetro de θi representan la importancia del contorno del
objeto dado que el contorno se considera el limite entre dos regiones y corresponden la divi-
sion entre uno y otro nivel de intensidad ese efecto se puede apreciar cuando el valor de este
parámetro toma el valor 2, 4 y 6. Claramente el método propuesto toma en consideración la
forma de los objetos tal como se menciono anteriormente.
4.4. PROPUESTA PARA LA CARACTERIZACIÓN IMÁGENES MEDIANTE REDES
COMPLEJAS 45
Figura 4.6: Representación de los vertices de una imagen del cerebro.
La propuesta también toma en consideración las texturas como se puede ver en la figura
4.8 donde se pueden ver cuatro texturas diferentes y cuatro redes generadas por la propuesta
cuando el valor de θ = 4, en la primera textura se puede apreciar una especie de cuadrícula
tipo una red y al ver su representación en red este aspecto se mantiene lo que es importante
ya que de forma similar sucede con la siguiente textura donde son líneas de distintos niveles
de intensidad y como se ve en su representación en red también mantiene dicha propiedad
otro ejemplo interesante de ver la textura 4 el cual ya es una matiz de intensidades de gris
y en su representación como red esta característica se mantiene. Como se pudo las 4 texturas
representan 4 redes diferentes lo cual es importante para la siguiente etapa donde se determinara
su vector de características.
4.4. PROPUESTA PARA LA CARACTERIZACIÓN IMÁGENES MEDIANTE REDES
COMPLEJAS 46
Figura 4.7: Efecto de diferentes umbrales para establecer las aristas.
4.4.2 Obtención del vector de características
La determinación del vector de características es igual al usado en la serie temporal en ese
sentido se hará un resumen de los diferentes pasos realizados.
• Primero una vez obtenida la matriz de distancias D, es necesario normalizarla de tal
manera que ayude a la determinación de los diferentes umbrales que se necesiten la cual
es realizada por:
D
D = (9)
maxdij
• Determinar el valor de incremento δθ para así determinar el tamaño del vector M .
• Multiplicar la matriz de distancias normalizada por el tamaño del vector de características
D′ = pM ×Dq.
• Calcular el histograma de la nueva matriz de distancias H = hist(D′).
4.5. CLASIFICADOR 47
Figura 4.8: Representación de diferentes texturas, se puede apreciar que las redes son diferentes,
manteniéndose las diferencias entre las cuatro texturas diferentes .
• Finalmente calcular los valores del vector de características V [v1, v2, ..., vi, ..., vM ] a partir
los valores acumulados del histograma H[h1, h2, ..., hi, ..., hM ] según:
∑i
vi = hi (10)
i=1
4.5 Clasificador
El vector de características resultante del proceso anterior tiene normalmente una alta dimen-
sionalidad, por ese motivo se debe usar alguna técnica de reducción de la dimensionalidad
4.5. CLASIFICADOR 48
ya que en general el funcionamiento de un clasificador es pesado computacionalmente en ese
sentido para poder alivianar el proceso es que se debe realizar reducción del espacio de car-
acterísticas el es realizados con el Canonical discriminant analysis (CDA) + Support vector
machine.
4.5.1 Canonical discriminant analysis (CDA)
El CDA es una técnica, que busca maximizar el espacio de separación entre las clases en ese
sentido similar que el análisis de componentes principales y otros métodos como el análisis
de discriminate multiple, etc. Estos métodos buscan el espacio de combinación lineales de las
características originales en el espacio llamado de variables canónicas. para poder realizar este
proceso es necesario tener una idea del espacio entre clases diferentes así como la distan dentro
de una misma clase. Sea U la matriz de dispersion de un vector de características el es definido
de la siguiente manera:
∑N
U = (xi − µ)(x t
i − µ) (11)
i=1
donde µ es el grado promedio de todo el conjunto de muestras. Esta ecuación representa la dis-
persion del conjunto total de los distintos vectores de características pertenecientes a diferentes
clases. Entonces sea Ui la matriz que indique la dispersion de los vectores pertenecientes a una
misma clase.
∑N
Ui = (xi − µi)(xi − µi)t (12)
i∈Ci
dondeCi es el conjunto de muestras de la clase i y µi es el valor promedio de la clase i. Entonces
el valor de variabilidad entre elementos de una misma clases puede ser definida porUintra_clase y
para el caso de la variabilidad entre clases distintas sera Uinter_clase las cuales pueden calcularse
como: ∑K
Uintraclase = Ui (13)
∑ i=1
K
Uinterclase = Ni(µi − µ)(µi − µ)t (14)
i=1
siendo que el valor de K es el numero de clases y Ni el numero de muestras en la clase i. Para
esas medidas de dispersion de los datos serán combinados en una nueva matriz U la cual sera
4.5. CLASIFICADOR 49
la combinación lineal como se puede ver en la siguiente ecuación 15:
U = Uintra_clase + Uinter_clase (15)
Para poder separar estos conjuntos existe una función que podría discriminar las diferentes
clases con la siguiente ecuación 16 la cual esta formada por las variables canónicas:
Yi = ai1X1 + ai2X2 + ...+ aipXp (16)
donde p es el numero de características y aij son los elementos de los autovectores ai = (ai1 +
ai2) + ...+ aip de la matriz C la cual esta dada por:
C = S × S−1inter intra (17)
Esta matriz C sera la encargada de reducir la dimensionalidad de los vectores de entrada y de
esa manera hacer que el proceso siguiente sea menos pesado, en el caso de la propuesta se uso
las maquinas de vectores soporte que es una técnica de clasificación supervisada.
4.5.2 Maquinas de vectores soporte (MVS)
Las maquinas vectores soporte son clasificadores capaces de encontrar una funciones de dis-
criminación que pueden ser lineales o n lineales que se usan para separar el espacio de repre-
sentación en regiones correspondientes a cada una de las clases consideradas (Vapnik, 2000).
MVS mapea los puntos de entrada a un espacio de características de una dimensión y en-
cuentra un hiperplano que los separe y maximice el margen m entre las clases en este espacio
como se aprecia en la 4.9. Maximizar el margen de separación m implica un problema de op-
timización de programación cuadrática que puede ser resuelto usando los multiplicadores de
Lagrange. De tal manera que se encuentra el hiperplano óptimo de separación utilizando el
producto punto con funciones en el espacio de características que son llamadas kernels. Este
hiperplano es la combinación de unos pocos puntos correspondiente a los patrones de entrada
que son llamados vectores de soporte. Existen dos casos que esta técnica puede resolver: prob-
lemas linealmente separables y no linealmente separables.
4.5.2.1 Caso linealmente separable
Supongamos que nos han dado un conjunto S de puntos etiquetados para entrenamiento como
se aprecia en al Figura 4.9
4.5. CLASIFICADOR 50
Figura 4.9: Caso linealmente separable
Cada punto de entrenamiento x ∈ Rn
i pertenece a alguna de dos clases y se le ha dado una
etiqueta yi ∈ 1,−1 para i = 1, ..., l En la mayoría de los casos, la búsqueda de un hiperplano
adecuado en un espacio de entrada es demasiado restrictivo para ser de uso práctico. Una
solución a esta situación es mapear el espacio de entrada en un espacio de características de una
dimensión mayor y buscar el hiperplano óptimo. Deseamos encontrar el hiperplano
W.z + b = 0 (18)
definido por el par (w, b), tal que podamos separar el punto xi, de acuerdo a la función
{
1 si yi = 1
f(xi) = signo(W.zi + b) = (19)
−1 si yi = −1
donde w ∈ Z y b ∈ R, el conjunto S se dice que es linealmente separable si existe (w, b) tal
que las siguientes inecuaciones:
{
W.zi + b ≥ 1
(20)
W.zu + b ≤ −1 i = 1, ..., l
Sean válidas para todos los elementos del conjunto S. Para el caso linealmente separable
de S, podemos encontrar un único hiperplano óptimo, para el cual, el margen entre las proyec-
ciones de los puntos de entrenamiento de dos diferentes clases es maximizado.
4.5. CLASIFICADOR 51
4.5.2.2 Caso no linealmente separable
Si el conjunto S no es linealmente separable entonces ocurrirán errores en la clasificación de
la SVM, como puede ser visto en la siguiente figura 4.10 no se puede establecer una linea
de separación para resolver el problema dado que los datos tienen una distribución circular
estando una clases dentro de otra clase Para tratar con datos que no son linealmente separables,
Figura 4.10: Caso no linealmente separable
el análisis previo puede ser generalizado introduciendo algunas variables no-negativas ξi ≥ 0
de tal modo que la ecuación 20 es modificado a
yi(w.zi + b) ≥ 1− ξi, i = 1, ..., l (21)
Los ξi 6= 0∑en (3)son aquellos para los cuales el punto xi no satisface la ecuación 19. Entonces
el término l
(i=1)ξi puede ser tomado como algún tipo de medida del error en la clasificación.
El problema del hyperplano óptimo e{s entonces re∑defin}ido como la solución al problema
min 1w.w + C ξ
2 i
yi(w.zi + b) ≥ 1− ξi, i = 1, ..., l (22)
ξi ≥ 0, i = 1, ..., l
donde C es una constante. El parámetro C puede ser definido como un parámetro de regular-
ización. Este es el único parámetro libre de ser ajustado en la formulación de la SVM. El ajuste
de éste parámetro puede hacer un balance entre la maximización del margen de separación entre
clases lo cual afecta a la clasificación.
4.6. VALIDACIÓN CRUZADA 52
Encontrar el hiperplano óptimo en la ecuación 22 es un problema de programación cuadrática,
que puede ser resuelto construyendo un Lagrangiano y transformándolo en el dual:
∑ ∑∑
max W∑(α) = α 1
i − αiα2 jyiyjzizj (23)
donde yiαi = 0, 0 ≤ αi ≤ C, i = 1, ..., l
donde , w ∈ Z y b ∈ R, α = (α1, ...αl) es una vector de multiplicadores de Lagrange positivos
asociados con las constantes en la ecuación 21.
Finalmente la idea es encontrar los valores de lo pesos w de tal manera que sea el hiperplano
óptimo de separación según la siguiente formu∑la
W = αiyizi (24)
Utilizando la función signo(w.z + b) se podrá determinar la respuesta correcta a nuestro prob-
lema
El usos de MVS puede usar varios kernels para poder clasificar los datos, la forma genérica
es K(xi, xj) ≡ φ(x )Ti φ(xj), es necesario probar con diferentes kernels:
• Linear: K(xi, x
T
j) = xi xj
• Polynomial: K(xi, xj) = (γxT d
i xj + r) , γ > 0
• Radial basis function(RBF):
K(xi, xj) = exp(−γ ‖ xi − x 2
j ‖ ), γ > 0
• Sigmoid: K(xi, x
T
j) = tanh(γxi xj + r)
4.6 Validación cruzada
Para poder validar los modelos de reconocimiento se planteo realizar la validación cruzada esta
es una técnica que se aplica al conjunto de datos inicial y se usa para evaluar de forma más
o menos exacta la calidad de un modelo de clasificación. La mayor ventaja de este diseño
experimental es que las estimaciones del error sobre los conjuntos de test son independientes
(los conjuntos de test no se solapan). Sin embargo, sí existe un cierto solapamiento en lo
que se refiere al conjunto de entrenamiento, ya que cada pareja de conjuntos de entrenamiento
comparte una alta fracción de los ejemplos pero a pesar de esto es una de las técnicas mas usada
para validar un modelo.
4.7. CONSIDERACIONES FINALES 53
En este método, los datos disponibles que tienen dimension n se dividen aleatoriamente en k
conjuntos de ejemplos disjuntos de igual tamaño, T1, .., T⋃k. Se realizan k experimentos, usando
como conjunto de entrenamiento en la iteración i-ésima j=6 i Tj y como conjunto de test Ti.
En esta tesis se uso un tipo particular de validación que es leave-one-out. Este tipo de
validación es un caso particular de la validación cruzada en el que k coincide con el número
total de patrones de aprendizaje n del conjunto de total de patrones. Estaríamos ante el caso más
extremo, ya que cada modelo estaría entrenado con n− 1 casos y probado con el caso restante
no usado. Este es el método de validación que devuelve resultados más exactos, pero su gran
inconveniente es la necesidad de entrenar tantos modelos como casos tuviera el conjunto de
datos inicial y el coste computacional necesario para llevar a cabo el proceso puede llegar a ser
muy elevado. Pero el nivel de confianza en este tipo de pruebas es mayor que otros métodos.
4.7 Consideraciones finales
Los modelos propuestos intentan mantener las características propias de cada tipo de señal
eso es importante para las operaciones de reconocimiento. En el caso de la serie temporal la
secuencia de estados según la temporalidad se mantiene y su análisis es realizado a nivel de
estructura topológica lo que es importante ya que la dinámica de un sistema es analizado desde
otro enfoque. En el caso de las imágenes las características de contornos, texturas e intensidades
de gris se mantienen en la representación mediante red compleja lo que también es deseado en
cualquier técnica de reconocimiento de patrones.
CAPÍTULO
5
Resultados experimentales
El modelo propuesto fue probado en dos aplicaciones distintas, una para el caso de series tem-
porales donde el modelo fue usado para el reconocimiento de palabras habladas. En este caso
se demostró como el modelo puede servir para extraer características de una señal de voz, las
palabras habladas corresponden a la grabación de los numeros del cero al nueve. Por otro lado
el modelo también fue probado para el reconocimiento de imágenes, en un proyecto que se
desarrolla en el marco de la cátedra Concytec, el proyecto consiste en el reconocimiento de
parásitos helmintos, en esta aplicación se demostró la aplicabilidad del modelo propuesto los
resultados serán presentados en las siguientes secciones.
5.1 Resultados de la aplicación para el reconocimiento de
palabras
Para el reconocimiento de palabras el modelo es usado para demostrar la aplicabilidad en el
reconocimiento de señales de voz. El modelo propuesto usa el criterio del par ordenado (A, t)
donde A es el valor de amplitud de la señal y t es el tiempo de duración de la grabación.
54
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 55
Figura 5.1: Gráfica de las amplitudes de las palabras grabadas: En la figura(a) son nueve pal-
abras diferentes; el numero Uno, Dos, Tres, Cuatro, Cinco, Seis, Siete, Ocho y Nueve; En la
figura (b) Muestras de una misma palabra pueden ser vistas
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 56
5.1.1 Adquisición, Cuantificación y Muestreo
El primer paso a desarrollar es la adquisición, cuantificación y muestreo de la señal. Para dicho
propósito se elaboro una base de datos de palabras habladas de los dígitos del uno al nueve
de los cuales se tuvo veinte ejemplares de cada palabra obteniéndose un total de 180 palabras,
para la grabación se utilizó un micrófono multimedia y la tarjeta de sonido de un computador
personal, la frecuencia de muestreo de la grabación fue de 44100 hz y la cuantificación fue
realizada a 16 bits.
En la siguiente figura 5.1 se puede apreciar algunas de las palabras grabadas, como se puede
apreciar la forma de las amplitudes de la señal son diferentes para palabras diferentes, esa
motivación ayuda a que la representación mediante redes complejas ayudara a acentuar esas
diferencias cuando sean representadas como redes complejas.
Figura 5.2: Determinación de ventanas solapadas para la detección del inicio y fin de palabra
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 57
5.1.2 Detección de inicio y fin
Una vez realizada la adquisición, es necesario implementar un algoritmo detector de inicio y fin
de la señal con el objetivo de eliminar información redundante de la señal (eliminar el fondo,
segmentando el inicio y el final de la señal de voz propiamente dicho).
Figura 5.3: Determinación de ventanas solapadas para la detección del inicio y fin de palabra
Este proceso de segmentación se realiza a través del cálculo de energía y detección de um-
brales de actividad de señal, el algoritmo basa sus cálculos en promedios temporales (mediante
el análisis una ventana de tiempo rectangular) del valor absoluto de la señal, el valor calculado
de la energía de la señal en esa ventana esta dado por la siguiente ecuación:
∑N1
E = |x(i)|2 (1)
N
i=1
donde el valor de E (energía) es comparado con un umbral T , si el valor es mayor que ese
umbral se dice que corresponde a la señal de voz y si es menor entonces se dice que es ruido
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 58
(fondo de la señal), la venta es solapada como se puede ver en la figura 5.3. Para determinar el
valor de umbral se calculo la energía de un segmento de ruido en ese sentido es necesario grabar
una porción de ruidos para una ventana dada, en este caso el tamaño de la venta es de 400 y el
valor del umbral en promedio es T = 0.8 el cual garantiza diferencia la señal de voz y el ruido
de la misma. Una vez determinado el inicio y fin de una palabra el siguiente paso es extraer
las características mediante redes complejas y finalmente se realiza la clasificación usando un
clasificador.
5.1.3 Extracción de características
Para poder extraer las características se uso el modelo propuesto para reconocimiento de series
temporales, el cual fue explicado en la sección 4.3, en el cual se construyeron varias redes
en función a la distancia entre cada par ordenado (A, t) que compone la serie temporal, en la
detección del inicio y fin de una palabra el tamaño de las palabras tiene dimensiones distintas
pero todas ellas son normalizadas a un intervalo entre [0 : 1] eso ayuda a la extracción de
características independientemente de la cantidad de elementos que tenga el vector de la señal.
El efecto de crear la red para diferentes distancias se puede ver en la figura 5.4 en el cual
se puede ver un segmento de la serie temporal, el cual corresponde 300 muestras de la serie
temporal y se varia el umbral de conectividad,el que indica la distancia maxima entre cada par
de nodos de la red. Como se puede ver a medida que el valor del umbral aumenta el número de
conexiones también se incrementa.
El vector de características es obtenido mediante la creación de diferentes redes, donde el
parámetro de umbral U varia desde U1 = 0.01 hasta el valor de U386 = 0.9 con incrementos de
δT < 0.0025 dando un total de 356 características, según las pruebas realizadas este parámetro
presente los mejores resultados.
5.1.4 Clasificación de las palabras habladas
Para la clasificación de las palabras habladas, el modelo debe ser capaz de discriminar entre los
diferentes sonidos de entrada realizando el reconocimiento de cada una de éstas con respecto a
un conjunto de datos previamente aprendido. Primero los datos obtenidos en la extracción de
características fueron reducidos de su dimensionalidad usando Canonical discriminant analysis
donde la dimension de 356 es reducida a 9 variables canónicas dado que existen 9 clases de pal-
abras en la siguiente figura 5.5 se puede apreciar gráficamente la relación entre algunas de estas
variables canonicas, donde se puede se puede ver que en algunos sub espacios pertenecientes
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 59
Figura 5.4: Redes construidas para diferentes distancias
a una misma palabra las cuales son de un mismo color, los elementos están separados casi
totalmente de otro sub conjunto, eso hace notar que habrá una clasificación adecuada.
Para las pruebas del modelo propuesto fue realizado la validación cruzada del tipo leave-one-out
usando como método de clasificación la maquina de soporte vectorial. Para poder probar la
maquina de soporte vectorial es necesario probar con diferentes parámetros siendo uno de los
principales el kernel que se debe usar, según el tipo de kernel se deben definir ciertos parámetros
como por ejemplo en el caso de un polinomial se debe ingresar como parámetro el grado del
mismo que podría ser cuadrático, cubico, etc. Otro parámetro usado también es el de regular-
ización el cual define si existe o no vectores dentro del margen de separación. En ese sentido el
modelo final de clasificación es robusto porque fue probado con diferentes variaciones de ker-
nel en la clasificación, kernels como el de base radial entre otros a pesar de obtener resultados
no adecuados, cometiendo mucho error por eso no fueron considerados en las estadísticas, eso
hace notar que los grupos formados no tienen distribución de datos de funciones de base radial.
Por otro lado en lo correspondiente a la creación de la red se probo con la variación del
parámetro de conectividad delta δT al momento de extraer características, hay tomar en cuenta
que a menor valor de δT mayor cantidad de características. Como podemos ver en la siguiente
5.1. RESULTADOS DE LA APLICACIÓN PARA EL RECONOCIMIENTO DE
PALABRAS 60
Figura 5.5: Relación entre las diferentes variables canónicas
tabla 5.6 donde el parámetro de conectividad fue incrementandose gradualmente, de tal manera
de poder encontrar los parámetros correctos para la clasificación de nuestro problema.
Finalmente podemos ver los resultados en la tabla 5.6, como se pudo ver cuando el valor de
∆T = 0.006 el porcentaje de acierto es el 99.99% tanto para el kernel polinomial como para el
lineal, pero si observamos la matriz de confusión el error se da en palabras diferentes, por eso a
continuación mostraremos las 2 matrices de confusion para los dos casos:
El caso del kernel lienal lo podemos ver en la tabla 5.2 donde el error de clasificación se da
en la palabra cuatro, el cual es confundido con la palabra ocho eso significa que de los veinte
ejemplares correspondientes a la palabra cuatro uno de ellos fue clasificado incorrectamente
como clase 8, por otro lado los del tipo ocho si fueron correctamente clasificados pero en la
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 61
Clasificador Nro. de carac- Nro. de imá- Porcentaje % ∆T
terísticas genes correctas Acierto
SVM - Lineal 890 166 92.22 0.001
SVM - Polinomial 890 163 90.55 0.001
SVM - Lineal 445 161 89.00 0.002
SVM - Polinomial 445 163 90.55 0.002
SVM - Lineal 222 171 95.00 0.004
SVM - Polinomial 222 171 95.00 0.004
SVM - Lineal 148 179 99.44 0.006
SVM - Polinomial 148 179 99.44 0.006
SVM - Lineal 110 164 91.11 0.008
SVM - Polinomial 110 166 92.22 0.008
SVM - Lineal 89 159 83.33 0.01
SVM - Polinomial 89 149 82.77 0.01
Tabla 5.1: Comparación de los resultados para diferentes parámetros del modelo propuesto.
recuperación de sus valores uno a mas fue realizado. Sin embargo en el caso del kernel poli-
nomial los resultados de error son diferentes al caso anterior, en este caso el error se da en la
recuperación de la palabra ocho, como se puede ver en la tabla 5.3, donde hay una palabra ocho
que no fue recuperada correctamente y podemos ver que el caso de la palabra cuatro uno a mas
fue reconocido siendo este el contrario del caso anterior, eso quiere decir que la separación entra
la palabra ocho y cuatro tienen una dificultad al momento de separar dichas clases.
5.2 Reconocimiento de parásitos helmintos
Para poder demostrar la aplicabilidad del modelo propuesto en la clasificación de imágenes se
utilizo los datos del proyecto PIBAP titulado Sistema automático de diagnostico de parásitos
intestinales a través de imágenes digitales (Contrato 028-2009-FINCyT-UNSA) en ese sentido
algunos de los resultados de esta investigación son usados para poder compáralos con los re-
sultados obtenidos con el modelo propuesto. Dado que esta tesis formaba parte del proyecto
anteriormente mencionado es que parte de la información de este capitulo fue resultado de in-
formes técnicos, así como artículos publicados en el marco del proyecto del cual se participo
como tesista.
Es importante tener en cuenta que un Helminto es un parásito que produce enfermedades
infecciosas. Las infecciones parasitarias provocadas por Helmintos están vinculadas a condi-
ciones socio ambientales que aquejan a Peruanos de bajos recursos económicos que viven en
condiciones favorables para el desarrollo de estos parásitos: cambios climáticos, alimentación
insuficiente, vivienda precaria, tierra contaminada, ausencia de agua potable, etc (Flint et al.,
2005).
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 62
1 2 3 4 5 6 7 8 9 Co(%)
1 100.0 0
2 100.0 0
3 100.0 0
4 95.0 5.0 5.0
5 100.0 0
6 100.0 0
7 100.0 0
8 100.0 0
9 100.0 0
Om(%) 0 0 0 0 0 0 0 5.0 99.44
Tabla 5.2: Matriz de confusion, cons sus respectivos error por cada clase, usando SVM con
kernel lineal.
1 2 3 4 5 6 7 8 9 Co(%)
1 100.0 0
2 100.0 0
3 100.0 0
4 100.0 0
5 100.0 0
6 100.0 0
7 100.0 0
8 5.0 95.0 5.0
9 100.0 0
Om(%) 0 0 0 5.0 0 0 0 0 99.44
Tabla 5.3: Matriz de confusion, cons sus respectivos error por cada clase, usando SVM con
kernel polinomial.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 63
Usualmente en puestos de salud publica de comunidades de bajos recursos del Perú no se
dispone de personal capacitado para diagnosticar enfermedades provocadas por estos parási-
tos. Habitualmente para realizar el diagnóstico en este caso se recurre a recolectar muestras de
heces de los pacientes y enviarlas a la ciudad más cercana para que realicen el diagnóstico. La
propuesta de realizar un sistema automático de diagnóstico tiene por objetivo principal realizar
un diagnóstico en tiempo real tomando las muestras de las imágenes de las micrografías desde
un microscopio y reducir el tiempo de espera para poder realizar un diagnóstico rápido. Au-
tomatizar este proceso que normalmente es realizado por personal altamente capacitado como
Biólogos expertos en parasitología, se dificulta al depender de procesos variables no automatiz-
ables como el procedimiento sedimentación y centrifugación de la muestra, incluso posterior a
este procedimiento es necesario aplicar una solución química sobre la micrografía para resaltar
los parásitos ante el ojo humano.
Actualmente los biólogos para distinguir a un parásito de un artefacto no deseado se basan en
la morfología de los Helmintos que normalmente son circulares y ovoides, el siguiente paso para
realizar el descarte es distinguir si la textura es rugosa o lisa; no consideran al color como una
característica relevante por ser directamente dependiente de las soluciones químicas que aplican
a la micrografía para que los candidatos puedan ser resaltados de mejor manera para el ojo
humano. Cabe resaltar que los biólogos caracterizan a estos parásitos para poder identificarlos
correctamente. Por eso con el modelo propuesto que integra la característica de la forma de los
objetos así como la textura de la misma, es algo que podría beneficiar a la automatización del
diagnostico de los parásitos por considerar aspectos que los biólogos resaltan en su diagnostico.
5.2.1 Conjunto de datos
Los experimentos fueron realizados sobre la base de datos SADPI8 v2.0 proporcionada por
el grupo PibapUnsa1 que contiene imágenes microscópicas extraídas de dos laboratorios de
diferentes ciudades del Perú, algunas imágenes de dicha base son mostrados en la figura 5.6.
Las imágenes fueron obtenidas con un microscopio óptico (MOTIBAC) el cual esta acoplado a
un ordenador por el cual se capturan imágenes con una magnificación objetiva 40× en formato
JPG. Los nombres de los parásitos que fueron usados para probar el modelo están están listados
en el cuadro 5.4 y pueden ser vistos en la figura 5.7. El conjunto de imágenes de micrografías
por especie así como imágenes segmentadas de entrenamiento están puestos en el siguiente
cuadro 5.4. Como se puede apreciar hay un total de 1036 imágenes como se puede apreciar no
existe la misma cantidad de imágenes por cada tipo de parásito, eso debido a que la incidencia
de un tipo de parásito es mayor que los otros.
1The website of this project is www.pibapunsa.org
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 64
Figura 5.6: Imágenes de la base de datos SADPI8 v2.0
Es importante notar que las imágenes originales capturadas desde el microscopio son como
las mostradas en la figura 5.6 donde podemos ver que existe la presencia de parásitos y además
de otros objetos a los cuales se llamaran artefactos por eso es necesario realizar la segmentación
de los objetos de interés (parásito), pero ese proceso no fue implementado en esta tesis ya que el
trabajo fue realizado por (Chuctaya et al., 2010) proporcionando los parásitos ya segmentados
estas imágenes fueron las que se usaron para probar el modelo.
Es importante notar que cada tipo de parásito es diferente y tienen características propias, en
la siguiente figura 5.7 se pueden apreciar las imágenes de cada uno de los helmintos a reconocer
como se puede ver tienen diferentes características que fueron formalizadas por descripciones
de los especialistas de la facultad de medicina de la Universidad Nacional de San Agustín.
Dicha formalización realizada por los expertos serán comentadas a continuación:
1. Trichiuris trichuira: Los huevos de esta especie tienen una forma o aspecto de limón,
con dos prominencias polares translucidas, semejantes a tapones. El tamaño varía de 50
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 65
Especie Num de Num de muestras
micrografías segmentadas
Ascaris Lumbroides 100 81
Uncinarias 75 51
Trichuris Trichiura 102 106
Hymenolepis Nana 115 74
Dyphillobothrium 103 164
Taenia Solium 211 231
Fasciola Hepatica 280 259
Enterobius Vermicularis 91 70
Total 866 1036
Tabla 5.4: Cantidad de micrografías por especie y parásitos segmentados encontrados en las
micrografías
Figura 5.7: Nombres de parásitos: 1) Ascaris 2) Uncinarias 3) Trichuris trichuria 4) Hy-
menolepis nana 5) Dyphillobothrium pacificum 6) Taenia solium 7) Fasciola hepática 8) En-
terobius vermicularis
a 54 por 23 micras. Presenta una capa externa de color amarillento y una capa interna
transparente. Los huevos fertilizados al momento de la oviposición = al ser expulsados
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 66
al exterior no muestran segmentación. El desarrollo embrionario tiene lugar fuera del
huésped.
2. Uncinarias por las especies Necator americanus y Ancylostoma duodenale: Los huevos
de estas dos especies, son casi indistinguibles, difieren solo ligeramente en el tamaño N.
americanus es de 64 a 76 por 36 a 40 micras mientras que los de A. duodenale son de
56 a 60 por 36 a 40 micras (hecho que el ojo humano no diferencia de manera rutinaria).
Los huevos tienen extremidades romas, redondeadas, y una capa hialina transparente, del-
gada, no están segmentados en la oviposición. En las heces frescas se les encuentra con
dos a ocho etapas celulares de división.
3. Ascaris lumbricoides: Los huevos miden de 45 a 70 por 35 a 50 micras. Una cubierta
externa densamente mamelonada, albuminosa que sirve de barrera auxiliar contra la per-
meabilidad, a veces puede faltar. El huevo propiamente dicho tiene una capa gruesa,
transparente, hialina con cubierta externa relativamente gruesa, que actúa como estructura
de sostén y otra interna, vitelina, delicada, lipoidal y muy impermeable. En el momento
de la oviposición, la cubierta contiene una masa ovoide de protoplasma no segmentado,
densamente impregnada con gránulos de lecitina. Los huevos no fértiles son mas largos
y estrechos, miden de 88ł 94 por 39 a 44 micras, tiene una cubierta más delgada y otra
irregular albuminosa, estando completamente llenos de una masa amorfa de protoplasma,
son gránulos retráctiles. También, hay huevos de aspectos caprichosos, sin cubierta al-
buminosa, con cubiertas externa anormales irregularmente. Generalmente los huevos no
fértiles, son difíciles de identificar y pueden pasar inadvertidos ante los ojos de un obser-
vador poco acucioso=poco entrenado.
4. Enterobius vermicularis: Los huevos de esta especie son difíciles de encontrar en un
examen de heces rutinario. Se les puede identificar muy rápidamente por su aspecto
asimétrico y por su contenido, un embrión bien desarrollado.
5. Diphyllobothrium pacificum: Los huevos miden de 55 a76 por 41 a 56 micras, tiene
una capsula simple con un opérculo medio oculto en uno de sus extremos y muestra un
pequeño engrosamiento en forma de botón en el otro.
6. Hymenolepis nana: El huevo es de forma oval o globular, miden de 47 por 37 micras.
Presentan dos membranas que encierran un embrión hexacanto. La membrana interna
tiene dos engrosamientos polares, de cada uno de ellos nacen de cuatro a ocho filamentos
polares muy finos.
7. Taena saginata / Taenia solium:Los huevos de estas especies no pueden distinguirse con
facilidad, son prácticamente iguales. Son de un color amarillo pardusco, con una cubierta
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 67
estriada radialmente que encierran un embrióforo. Miden de 30 a 40 por 20 a 30 micras.
Algunas veces se pueden observar huevos rodeados por una capa o membrana externa con
dos delicados filamentos polares(como se encuentran en el útero del céstodo), pero que se
pierden inmediatamente dejan el proglótido del céstode. Alguno autores, señalan que los
huevos maduros de Taenia solium, son indistinguible de los de Taenia saginata, contiene
un embrión hexacanto rodeado por una cubierta esférica o semiesférica, estriada, gruesa,
de color café claro y con un tamaño de 30 por 40 micras de diámetro.
8. Fasciola hepatica:Los huevos de esta especie, son grandes y ovales, de color amarillo
- pardusco. Son operculados y miden de 130 a 150 por 65 a 90 micras; no presentan
segmentación al momento de la oviposición(cuando son expulsados al exterior).
Una muestra de la base de datos de imágenes usada se puede ver en la siguiente imagen 5.8:
Estas características formalizadas ayudaron a determinar las técnicas de procesamiento de
imágenes necesarias para que estas pueden ser cuantificadas en un vector de características, por
eso es necesario dar conceptos teóricos de dichas técnicas ya que estas fueron implementadas y
probadas para poder comparar el modelo propuesto frente a técnicas ampliamente usadas en el
reconocimiento automático de imágenes.
5.2.2 Técnicas de extracción de características
La propuesta esta fundamentada en la simulación de los criterios de los biólogos donde la mor-
fología de los parásitos fue uno de los criterios tomados en consideración, otro aspecto impor-
tante es la textura. En el articulo (Humpire et al., 2011), mostraron resultados de clasificación
en los cuales el vector de características es de tamaño 8 y esta compuesto por dos descriptores:
4 geométricas y 4 de textura Gray Level Co-Ocurrence Matrix(GLCM) que usan el contorno y
la imagen en escala de grises del candidato. A continuación describiremos la técnica usada en
el articulo para poder comparar los resultados con los obtenidos por esta propuesta.
5.2.2.1 Características geométricas
Para poder definir la morfología del candidato es importante detectar el contorno exterior del
parásito para poder detectar el contorno se uso el filtro de Canny (Canny, 1986). La detección
del borde es un enfoque común para detectar discontinuidades diferenciales en imágenes en
niveles de gris. Para lograr dicho objetivo se usa la primera y segunda derivada como gradientes
y el laplaciano para detectar bordes en una imagen.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 68
Figura 5.8: Muestra de imágenes de diferentes parasitos de la base de datos usada para la
clasificación de parásitos
Un borde es un conjunto de puntos con el mismo nivel de intensidad entre los pixeles de
la imagen. Los bordes en una imagen pueden generalmente ser divididos en dos categorías de
bordes de intensidad (abruptos cambios) y borde de textura (regiones invariantes a condiciones
de luminosidad) (Tan et al., 1989). Este método es ideal para especies que tienen un cubierta
semitransparente en vista que la binarización puede obviar varias partes que imposibiliten su
proceso normal.
Para poder realizar la detección de contornos mendicante el algoritmo de Canny los sigu-
ientes pasos tienen que ser realizados:
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 69
5.2.2.2 Obtención del gradiente
Para la obtención del gradiente el método utiliza el filtro gaussiano aplicado a la imagen original,
con el propósito de suavizar la imagen y trata de eliminar posible ruido existente, pero hay
que tener en cuenta que no se debe realizar un suavizado excesivo ya que implicaría perdida
de características de la imagen, y generaría resultados no óptimos. Una vez que se suaviza la
imagen, para cada píxel se obtiene la magnitud y módulo (orientación) del gradiente, obteniendo
así dos imágenes. El suavizado del filtro gaussiano se obtiene promediando los valores de
intensidad de los píxeles en el entorno de vecindad con una mascara de convolución de media
cero y desviación estándar σ, la mascara gaussiana esta definida por la siguiente ecuación:
(x2+y2 2
G(x, y) = ke )/2σ (2)
El gradiente de una imagen f(x, y) en un punto (x, y) se
dado por la ecuación: [ ]define como un vector bidimensional
Gx
G[f(x, y)] = (3)
Gy
siendo el gradiente un vector perpendicular al borde, donde el vector G apunta en la dirección
de variación máxima de la función F en el punto (x, y), la magnitud y dirección están dadas
por dadas por:
√
|G| = G2
x +G2
y = |Gx|+ |Gy| (4)
Gy
Θ(x, y) = arctan (5)
Gx
siendo |G| la magnitud del gradiente y Θ(x, y) la dirección del gradiente.
5.2.2.3 Supresión de no-máximos al resultado del gradiente
Las imágenes generadas en el paso anterior sirven de entrada para generar una imagen con
los bordes adelgazados. El procedimiento es el siguiente, se consideran cuatro direcciones
identificadas por las orientaciones de 0◦, 45◦, 90◦y 135◦ con respecto al eje horizontal. Para cada
píxel se encuentra la dirección que mejor se aproxime a la dirección del ángulo de gradiente.
5.2.2.4 Histéresis de umbral
Del resultado del proceso anterior se obtiene una imagen que suele contener máximos locales
creados por el ruido. Una solución para eliminar dicho ruido es la histéresis basada en umbral.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 70
El proceso consiste en tomar la imagen obtenida del paso anterior, tomar la orientación de los
puntos de borde de la imagen y tomar dos umbrales, el primero más pequeño que el segundo.
Para cada punto de la imagen se debe localizar el siguiente punto de borde no explorado que
sea mayor al segundo umbral. A partir de dicho punto seguir las cadenas de máximos locales
conectados en ambas direcciones perpendiculares a la normal del borde siempre que sean may-
ores al primer umbral. Así se marcan todos los puntos explorados y se almacena la lista de todos
los puntos en el contorno conectado. Es así como en este paso se logra eliminar las uniones en
forma de Y de los segmentos que se unan en un punto.
5.2.2.5 Cierre de contornos abiertos
Como resultado del proceso anterior es posible hayan contornos abiertos, para poder cerrar estos
contornos se busca cada píxel uno de los ocho patrones posibles que delimitan la continuación
del contorno en tres direcciones posibles. Esto se logra con la convolución de cada píxel con
una máscara específica. Cuando alguno de los tres puntos es ya un píxel de borde se entiende
que el borde se ha cerrado, de lo contrario se elige el píxel con el valor máximo de gradiente
y se marca como nuevo píxel de borde y se aplica nuevamente la convolución. Estos pasos se
repiten para todo extremo abierto hasta encontrar su cierre o hasta llegar a cierto número de
iteraciones determinado.
Una vez detectado el contorno se procede a obtener algunas características que son:
• Diámetro máximo, es la mayor distancia existente entre dos puntos del contorno.
• Diámetro mínimo, es la distancia ortogonal desde el punto medio de la linea generada por
el diámetro máximo hacia el contorno.
• Área, pixeles contenidos en el contorno del parásito. Logra distinguir los parásitos grandes
de los pequeños
• Excentricidad, es la proporción existente entre el diámetro máximo y diámetro mínimo,
esta característica ayuda a diferenciar a los huevos de parásitos que son ovoides de los
circulares.
5.2.2.6 Características de textura interna Gray Level Occurrence Matrix
Esta técnica fue propuesta por (Lam, 1996) La matriz de co-ocurrencia describe la frecuencia de
un nivel de gris que aparece en una relación espacial especifica con otro valor de gris, dentro del
área de una ventana determinada. La matriz de co-ocurrencia es un resumen de la forma en que
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 71
los valores de los pixeles ocurren al lado de otro valor en una pequeña ventana. Normalmente
el procedimiento de generación de imágenes de textura requiere que el analista defina cinco
variables:
• Tamaño de la ventana
• Banda espectral de entrada
• Las texturas derivadas
• Cuantización (numero de bits) del canal de salida
• La componente espacial (la distancia interpixel y el ángulo para el computo de la co-ocurrencia).
Respecto del tamaño de la ventana, esta debe ser cuadrada y con numero impar de pixeles.
El resultado del calculo de la textura es un único numero que representa la ventana completa, el
cual es colocado en el lugar del pixel central. Luego, la ventana se mueve un pixel y el calculo
se repite calculando una nueva matriz de co-ocurrencia para esta nueva ventana y resultando
un nuevo valor, para el píxel central de esta nueva posición de la ventana. De este modo se
construye toda una nueva imagen con valores de texturas. Cada celda de la ventana debe situarse
en una celda que esté ocupada en la imagen original. Esto significa que el pixel central de la
ventana no puede ocupar un borde la imagen.
Las características de textura GLCM (Lam, 1996) están basadas en la matriz de co-ocurrencia
sobre la imagen segmentada en escala de grises. La matriz de co-ocurrencia es una matriz
cuadrada de N × N , donde N es el número de posibles valores en la imagen (niveles de gris),
La posiciónCij de la matriz representa la cantidad de pixeles de nivel i que están a una distancia
y en una dirección de otro pixel de nivel j.
Una vez obtenida la matriz de co-ocurrencia esta debe pasar por una normalización. Después
se debe escoger el descriptor apropiado que reducirá la matriz de co-ocurrencia a un solo valor
(En este caso un descriptor de contraste). Las pruebas fueron realizadas usando 8 niveles de
umbral y desplazamientos δx = 3, δy = 3. Las características calculadas son: correlación,
energía, contraste y homogeneidad.
La etapa de segmentación retorna imágenes recortadas contenedoras de candidatos con
background blanco, esta particularidad es aprovechada para descartar cualquier pixel blanco
del conteo para la matriz de co-ocurrencia garantizando así obtener características exclusiva-
mente del candidato en escala de grises.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 72
5.2.2.7 Características de Histograma
Los histogramas (Lin and Lin, 2011) son la representación de la distribución de la intensidad
de colores de una imagen, en una imagen en niveles de gris la propuesta tiene valores entre el
rango de [0, 255] donde 0 representa el color 0 y el valor de 255 es el blanco. Las características
extraídas mediante el histograma se obtiene contando las intensidades de cada pixel de la im-
agen. Entonces para reducir el numero de características el histograma puede ser representado
por cierta cantidad de bins, optimizando la cantidad de atributos de la imagen.
Los valores de los bins son calculados por el promedio de los valores del bucket del his-
tograma original, en ese caso las pruebas fueron realizados con 17 bins, cada bin es resultante
del promedio de un bloque de 15 unidades del histograma original.
5.2.2.8 Momentos de HU
En procesamiento de imágenes, los momentos invariantes son usados como un vector de car-
acterísticas para su clasificación de imágenes obteniendo atributos de las formas del objeto
basadas en su textura. En los años 1960, Hu (Hu, 1962) desarrolló 7 momentos invariantes de
escalas, rotación y traslación basados en momentos de teoría algebraica.
En reconocimiento de patrones se ha aplicado una leve modificación de estos momentos
invariantes para poder trabajar con imágenes y requiere de ser una matriz cuadrada para poder
obtener los 7 momentos de Hu como condición. Los momentos de Hu son 7 y están definidos
por las siguientes ecuaciones y son dependientes de sus anteriores ecuaciones:
ϕ1 = η20 + η02 (6)
ϕ2 = (η20 − η02)2 + 4η11 (7)
ϕ3 = (η30 − 3η 2 2
12) + (3η21 − η03) (8)
ϕ = (η 2 2
4 30 + η12) + (η03η21) (9)
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 73
[ ] [ ]
ϕ5 = (η30−3η12)(η30+η12) (η30+η
2
12) −(η21+η
2
03) +(3η21−η03)(η21+η03) 3(η 2 2
30+η12) −(η21+η03)
(10)
[ ]
ϕ6 = (η 2 2
20 − η02) (η30 + η12) − (η21 + η03) 4η11(η30 + η12)(η21 + η03) (11)
[ ] [ ]
ϕ7 = (3η21−η03)(η30+η12) (η +η )230 23 −3(η 2 2
21+η03) −(η30−3η12)(η03+η12) 3(η30+η12) −(η 2
21+η03)
(12)
5.2.2.9 Filtros de Gabor
Una filtro de Gabor es un complejo sinusoidal modulado por una envolvente Gaussiana. Para el
caso de dos dimensiones es una función compleja, sobre puesta a las dos partes del filtro los los
cuales solapados son equivalentes a una mascara.
Matemáticamente la función compleja de Gabor queda expresada de la siguiente manera:
2 2 2
g(x, y) = Ke(−π(a (x−x0) +b (y−y )20 ))e(j(2π(u0x+v0y)+P )) (13)
Y la parte real queda expresada como:
2 2 2
g(x, y) = Ke(−π(a (x−x0) +b (y−y0)2))e(cos(2π(u0x+v0y)+P )) (14)
Gabor a su vez otorga independencia de escala, rotación y traslación. La independencia
de escala es lograda dependiendo de un limite de escalas asignado al momento de extraer car-
acterísticas, la independencia de rotación es lograda por las múltiples rotaciones realizadas de
forma automática por Gabor teniendo como limite de rotaciones las asignadas al momento de
extraer características.
5.2.2.10 K-Gabor
Este extractor de características otorga una particularidad y ventaja para tipos de imágenes
que necesitan resaltar detalles de su morfología interna, tal es el caso en el reconocimiento de
parásitos ya que no basta con visualizar las características básicas pre-establecidas como alto,
ancho, área sino detalles internos para diferenciar entre especies de parásitos.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 74
Esta técnica se apoya en el uso de la clusterización por intensidad de grises usando K-means
para obtener diferentes niveles de contenido, para el presente caso de estudio se consideraron
5 clusters de los cuales el primer y ultimo cluster son descartados por contener información
global de la imagen, en cambio los clusters intermedios contienen información valiosa.
5.2.3 Redes complejas para la clasificación de parásitos
Para poder comparar el modelo propuesto frente a otros ya propuestos usando redes comple-
jas, se implementaron las otras técnicas en la clasificación de los parásitos, en ese sentido se
presentaran tres modelos de redes complejas para extracción del vector característico. Primero
explicaremos el modelo basado en los contornos, el modelo es el basado en la textura se imple-
mento según la propuesta de (Wesley, 2010) (Backes, 2010), finalmente el modelo propuesto es
descrito en detalle.
5.2.3.1 Red compleja basada en contorno
Este modelo se desarrollo en el marco del proyecto STIC-AMSUD (11STIC-07 - Webbased -
Web-based systems for bio-image analysis and interpretation) donde el modelo se desarrollo el
grupo de investigación del profesor Odermir Bruno de la Universidad de Sao Paulo - Brasil el
proceso puede ser visto en la figura 5.9:
Como se puede ver (figura 5.9), el método se basa en la detección del contorno externo y la
detección de los contornos de las estructuras internas. Para la detección del contorno externo
se realiza una binarización de la imagen usando el método propuesto por Otzu (Kurita et al.,
1992) una vez teniendo la imagen binarizada se extrae el contorno del parásito binarizado. Para
la detección de las estructuras internas se uso el algoritmo de Canny (Canny, 1986) y como ya
fue detectado el contorno externo este es eliminado quedando solo la estructura interna.
Como se puede ver en la siguiente figura 5.10 se muestra la figura de algunos parásitos de
de especies distintas donde el resultado de la obtención del borde exterior como de las estruc-
turas internas pueden ser apreciados siendo estas diferentes en su estructura interna eso ayuda
a compensar con dichas estructuras las texturas que ellos tienen.
Una vez teniendo el contorno se sigue la idea de construir la red según la distancia entre
los puntos del contorno donde los valores del umbral varia entre 0.05 a 0.95 con una variación
de umbral ∆T = 0.005 siendo un total de 190 intervalos de variación siendo dos vectores el
número total seria de 380 características, la propuesta obtiene dos vectores de características,
los valores del vector de características son el grado promedio de los nodos de la red.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 75
5.2.3.2 Red compleja basada en textura
Para poder construir la red primero see define una vecindad entre los pixels de la imagen for-
mando una red regular ya que todos los nodos de la red tienen el mismo grado, en ese sent√ido
se debe variar el parámetro de conectividad entre los pixeles, inicialmente el valor es de 2
una vez creada la red inicial para poder crear la red se considerara los niveles de intensidad
que tienen los pixeles calculando la diferencia de intensidades de tal manera que esta red tendrá
pesos w = |Ii−Ij| siempre y cuando los pixeles están conectados es decir que la distancia entre
los pixeles es menor que el radio definido inicialmente. Para convertir esta red regular con pesos
a una red compleja se usa valores umbrales T para conservar aristas con pesos menores a dicho
valor y eliminar aristas con valores mayores, en ese sentido varios umbrales son aplicados.
Una vez creada la red compleja se aplica las caminadas del turista obteniendo diferentes
memorias (µ1, ..., µM) y dinámicas mínimo y máximo son aplicadas en cada red compleja. el
vector de características es obtenida de la concatenación de los valores anteriores para diferentes
umbrales y distintos radios de conectividad.
5.2.4 Red compleja del modelo propuesto
Como se presento en capítulo 4 la red compleja del modelo propuesto es creada en función de la
distancia entre los valores de las posiciones de los pixeles y su valor de intensidad, una imagen
puede ser analizada de forma tridimensional, es decir que el punto 3D es la combinación de la
posición x, y y los niveles de intensidad I siendo estas posiciones los vertices en 3 dimensiones
(x, y, I) y en función a la distancia se establecerán las conexiones en la figura 5.11 se puede
apreciar la imagen correspondiente al parásito, además se puede ver su visualización en 3D,
también podemos ver dos redes construidas en función a dos distancias entre pixeles una es
d = 4. y el otro es d = 6 se puede ver claramente que a menor valor del umbral menor
conectividad existen entre vertices de la red, eso dice mucho del efecto que tiene el modelo
propuesto ante el cambio de umbral.
Por otro lado se puede ver también que las redes son diferentes eso indica que se pueden
diferenciar un tipo de otro eso es importante para las etapas siguientes de tal manera que garan-
tice la efectividad del método al momento de clasificar los parásitos.
Es importante considerar es que el modelo propuesto es invariante a las transformaciones ge-
ométricas eso garantiza la robustes de la propuesta, ya que ante el cambio en traslación rotación
o escala el valor del vector de características no se ve afectado, las transformaciones geométri-
cas mas comunes son la rotación, traslación y la escala en la figura 5.12 se puede ver el efecto
de rotar y escalar la imagen de una Enterobius Vermicularis, muy a pesar de las diferentes trans-
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 76
formaciones que sufrió la imagen, los vectores de características muestran valores semejantes
eso indica que el modelo es invariante a dichas transformaciones, eso hace robusto al modelo
ante este tipo de problemas.
Es importante tener en cuenta que el para poder construir la red compleja el fondo de la
imagen no es usada, para poder lograr dicho propósito la segmentación del parásito debe ser
realizada.
5.2.5 Clasificación de parásitos
Para poder clasificar los parásitos se tiene hacer una reducción de la dimensionalidad, usando
el CDA, una vez realizado el proceso de reducción podemos obtener las variables canónicas el
cual podemos apreciar en las siguientes figuras 5.13, 5.14.
Como se puede ver en la figura 5.13 al combinar la 8va y la 7ma variable se consigue una
separación aceptable entre las variables, pero el parásito Dyphillobothrium se sobrepone con
otros parásitos eso también sucede con la combinación de otras variables excepto en la combi-
nación de la 5ta variable con la 8va, es importante notar que en ese caso ese conjunto de datos
es fácilmente separable, se puede ver también que en varios casos los ascaris, Ucinarias, Faciola
hepatica y Enterobius vermicularis en varios casos es separable fácilmente eso indica que di-
chos parásitos son diferentes entre si. Se puede ver en general que las variables canónicas 1ra y
2da siempre presentan combinación de algunos parásitos lo que dificulta la clasificación. Pero
analizando las diferentes combinaciones también se puede ver que en algunos casos siempre
existe una separación de cada tipo de parásito.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 77
5.2.5.1 Resultados Estadísticos
Para validar el modelo propuesto se tuvo que realizar varias pruebas modificando el parámetro
principal que es la variación del delta δT ya que eso determina el nivel de conectividad de los
nodos de la red, donde hay que tomar en cuenta que a menor valor de δT mayor cantidad de
características. En la tabla 5.6 se puede ver la modificación del parámetro, de tal manera de
poder calibrar el modelo, también fueron probados diferentes kernels pero en los diferentes
experimento el polinomial fue el que presento mejores resultados. El parámetro fue variado
desde T = 0.01 hasta valores menores que T = 0.9 para diferentes δT .
∆T Nro. de carac- Nro. de imá- Porcentaje %
terísticas genes correctas Acierto
0.001 890 1023 98.74
0.002 445 1008 97.29
0.003 296 957 92.37
0.004 222 738 71.23
0.005 178 745 71.91
0.006 148 688 66.40
Tabla 5.5: Comparación de los resultados para diferentes parámetros del modelo propuesto.
Varios extractores de características han sido probados en el desarrollo de este proyecto, los
resultados obtenidos pueden ser resumidos en la siguiente tabla 5.6, puede verse que el modelo
propuesto consigue la mejor tasa de reconocimiento eso es importante por que muestra que usar
redes complejas se presentan como una solución promisoria en el area de reconocimiento de
patrones.
Extractor de Nro. de carac- Nro. de imá- Porcentaje %
Características terísticas genes correctas Acierto
Filtros de Gabor 48 994 95.94
Momentos de Hu 7 594 57.33
Histograma 17 869 83.88
Geometrico GLCM 8 971 93.72
GLCM 22 943 91.02
K = 2 Gabor 96 980 94.59
K = 3 Gabor 144 995 96.04
Contornos Red Compleja 390 1015 97.97
Textura Red Compleja 336 945 91.21
Modelo Propuesto 441 1023 98.74
Tabla 5.6: Comparación de los resultados para diferentes parámetros del modelo propuesto.
Es importante notar que los métodos basados en redes complejas tanto el método propuesto
como el método basado en contornos son los que mejores resultados ha obtenido, es por ese
motivo que mostraremos detalles del proceso de clasificación para eso usaremos las matrices de
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 78
confusion de dichos extractores como se puede ver en la tabla 5.7 se pueden ver los resultados
del modelo propuesto 5.7 y en la tabla 5.8 los resultados del modelo basado en contornos.
Como se puede ver en la figura 5.7 los parásitos 2 y 3 tienen algo de semejanza en forma
con otros parásitos, pero en textura son diferentes, en ese sentido es importante notar que el
modelo propuesto no cometió error en esos casos. Sin embargo el modelo basado en contornos
consiguió separar correctamente la clase 7; sin embargo el modelo cometió errores con con las
clases 1 y 4.
1 2 3 4 5 6 7 8 Co(%)
1 98.77 1.23 1.2
2 100
3 100
4 97.30 2.70 2.70
5 0.61 1.22 97.56 0.61 2.44
6 1.30 98.70 1.3
7 0.39 0.39 99.22 0.78
8 1.43 98.57 1.43
Om(%) 1.0 3.04 4.0 1.8 98.74
Tabla 5.7: Matriz de confusion, con sus respectivos error por cada clase de la clasificación del
método propuesto a los 8 especies de parásitos helmintos.
En resumen, los resultados obtenidos son muy alentadores en el sentido de que las redes
complejas si se pueden usar para el reconocimiento de patrones uní y bí dimensionales, posi-
bilitando resolver problemas reales como el diagnóstico de especies de parásitos helmintos, los
resultados demuestran que si es posible usar redes complejas para la caracterización de parási-
tos.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 79
Figura 5.9: Propuesta para la clasificación de los parásitos Helmintos
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 80
Figura 5.10: Contornos externos e internos de los diferentes parásitos
1 2 3 4 5 6 7 8 Co(%)
1 96.30 2.70 1.22 0.87 1.2
2 1.23 98.04 0.94 3.05 0
3 98.11 1.43 0
4 1.23 95.95 0.43 2.7
5 1.23 1.96 1.35 95.73 0.43 2.4
6 98.27 1.3
7 100 0.8
8 0.94 98.57 0
Om(%) 3.70 1.96 1.89 4.05 4.27 1.73 1.43 98.7
Tabla 5.8: Matriz de confusion, cons sus respectivos error por cada clase, para el modelo basado
en contornos.
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 81
Figura 5.11: Imagen micrográfica del parásito también se puede ver su visualización en 3D, y
dos redes generadas para dos parametros distintos cuando la distancia vale 4 y cuando vale 6
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 82
Figura 5.12: Enterobius Vermiculares con problemas de transformaciones geométricas, se
puede ver que su vector de características para las diferentes transformaciones geométricas
son muy parecidas eso hace al método robusto ante problemas de rotación y escala, (a) Re-
ducida de tamaño al 50% del tamaño original, (b) Imagen Original, (c) Aumentada de tamaño
al 150 %, (d) Imagen rotada y aumentada 150 %, (e) Imagen normal rotada, (f) Imagen rotada
y disminuida de tamaño
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 83
Figura 5.13: Análisis de las variables canónicas se pueden ver la combinación de la 8va variable
combinada con la 7ma, 6ta, 5ta, 4ta, 3ra, 2da, 1ra. Y 3ra combinada con las variables 2da, 1ra
5.2. RECONOCIMIENTO DE PARÁSITOS HELMINTOS 84
Figura 5.14: Visualización de la variable 7ma con la 6ta, 5ta, 4ta, 2da, 1ra variable. También
vemos la 4ta y 3ra, 2da, 1ra. Además la 6ta combinada con 5ta, 4ta, 2da, 1ra finalmente la 5ta
variable combinada con 4ta, 3ra, 2da, 1ra
CAPÍTULO
6
Conclusiones
6.1 Discusión sobre el modelos propuesto
Es importante tener en cuenta algunos aspectos que hacen que esta propuesta sea innovadora en
referencia a los modelos existentes
• La ida de esta propuesta es innovadora ya que según se revisaron los trabajos relacionados
no son similares al modelo propuesto, a pesar de ser una idea sencilla en su concepción
demostró ser potente para extracción de características de series temporales e imágenes.
• En cuanto a las series temporales la mayoría de los trabajos buscan representar redes
complejas enfocadas preservar las características de la naturaleza de la serie característi-
cas como aleatoriedad en caso de series aleatorias, así como periodicidad buscando cor-
relaciones y ciclos repetidos o pseudo repetidos para la creación de las mismas, e incluso
hay técnicas para preservar sus comportamiento de dinámicas complejas como lo es el
comportamiento caótico.
• En cuanto a la generalidad del modelo se puede notar que ya sea bidimensional o tridi-
mensional el modelos seria extensible a una dimension mayor, por ejemplo si se tuviera
una base de datos de imágenes 3D donde se tiene el concepto de voxel el cual tiene una
posición 3D x, y, z además de tener un valor de intensidad (color) asociado entonces la
propuesta de moderamiento seria la misma ya que cada nodo de la red seria la posición
85
6.2. CONCLUSIONES 86
4D x, y, z, I y la conectividad de la misma estará dada por distancia entre sus vertices
para diferentes umbrales y así crear diferentes redes.
• Para el caso de modelos para imágenes la propuesta presenta una ventaja clara ya que
normalmente se intenta resaltar características por separado de las imágenes, como lo es
la forma y la textura proponiendo modelos por separado sin embargo podemos ver que
en la propuesta cuando los niveles de distancia (Umbral) entre nodos es baja la forma de
las estructuras ya sean internas o externas son resaltas y cuando los niveles de distancia
son mayores la textura de la imagen es caracterizada, por lo tanto se puede decir que el
modelo es mas completo al considerar ambos aspectos a la vez. Ahora si por el contrario
se quisiese resaltar uno de los aspectos mas que otro (forma o textura), el modelo debería
ajustar el calculo de la distancia dando mayor valor al parámetro alfa o beta.
• El modelo propuesto para imágenes fue probado solo para imágenes en niveles de grises si
se quiere extender a color el modelo seria extensible de forma natural, ya que la posición
de un nodo seria el valor x, y del pixel mas el valor del color el cual puede ser colocado
en un universo de color especifico por ejemplo para el domino R G B, siendo la posición
final del nodo (x, y, R,G,B) y lo siguiente es calcular distancia entre los nodos usando
diferentes umbrales de distancias.
6.2 Conclusiones
Como pudo ser demostrado en el capitulo de resultados las redes complejas pueden ser uti-
lizados en el reconocimiento de patrones unidimensionales y bidimensionales, esto demuestra
la potencialidad del uso de las redes complejas en la solución de problemas reales, donde se
presentaron dos aplicaciones una en el reconocimiento de palabras habladas y la otra en el
reconocimiento de imágenes de parásitos helmintos.
En el caso del reconocimiento de palabras habladas se demostró como una serie temporal
puede ser estudiada desde el punto de vista topológico analizando sus propiedades, y usar dichas
propiedades para caracterizar y diferenciar señales temporales, mostrando porcentajes altos en
el reconocimiento llegando a un 99.44%, además el modelo es robusto ya que el principal
parámetro (variación de los umbrales) da tasas de reconocimiento altas para diferentes valores,
eso de muestra que el método no es una solución particular, por el contrario da buenos resultados
para diferentes valores.
En el caso de reconocimiento de imágenes se ha demostrado que los método basados en
redes complejas obtienen mejores resultados que técnicas tradicionales ampliamente usadas
en el reconocimiento de imágenes como los son los filtros de Gabor, eso es importante ya
6.3. RECOMENDACIONES 87
que la propuesta se presenta como una nueva alternativa de solución a distintos problemas de
reconocimiento de imágenes
Las propuestas basadas en redes complejas, se presentan como un campo potencial de apli-
cación en reconocimiento de patrones en general, la idea central es ver como el patron puede
ser representado como una red compleja, en ese sentido es importante que las características
del patron se vean reflejados en la representación por red, además nuevas características pueden
ser analizadas a partir del grafo. Un siguiente paso es ver que medida podría ser usada para
caracterizar y diferenciar los diferentes patrones, en la actualidad existen muchas medidas que
podrían usarse es importante hacer un análisis cuantitavo de las diferentes métricas usadas en
ese sentido es importante usar una maquina de aprendizaje para poder realizar dicha selección.
6.3 Recomendaciones
Una de las cosas que es importante notar es que el tamaño del patron es una aspecto que se debe
considerar ya que tanto una imagen como un sonido son muestreados a diferentes tamaños,
cuando una imagen es de gran tamaño hace que el numero de cálculos necesarios para extraer
el vector de características tomarían un tiempo considerable, incluso se tendría que considerar
una capacidad minima de memoria para poder procesar el patron.
En las aplicaciones presentadas tanto las imágenes como el archivo de sonido son soportados
por el computador pero imágenes de mayor resolución podrían desbordar la memoria. En esos
casos podría usarse técnicas de disminución del tamaño original. Por ejemplo en el caso de una
imagen se puede reducir el tamaño de una imagen, manteniendo las características originales de
forma y textura lo cual puede ser realizado de forma perceptual observando la imagen original y
sus reducciones, fue presentado en los resultados que el modelo es invariante a la transformación
de escala, claro que esa escala tiene una tolerancia para el caso de los parásitos un tamaño
mínimo de 50×50 pixels de resolución garantizando que el modelo presente buenos resultados.
En el caso de los archivos de sonido, es importante tomar en consideración que las graba-
ciones de sonido tienen intervalos de tiempo que corresponden a la palabra hablada así como
intervalos de silencio que no son necesarios en el reconocimiento y que por el contrario al-
teran el calculo de las características, pero eso es superado usando técnicas de detección de
inicio y fin de palabra, lo cual es lógico y es un paso usado también por cualquier técnica de
reconocimiento de palabras habladas.
Revisando la literatura uno puede notar la existencia de diferentes propuestas en la repre-
sentación de los patrones como redes complejas, eso muestra que las redes complejas presentan
flexibilidad y variedad de su uso en el reconocimiento de patrones. Es importante notar que la
6.4. TRABAJOS FUTUROS 88
propuesta es original a pesar de ser una idea simple puede usarse tanto unidimensional como
bidimensionalmente.
6.4 Trabajos Futuros
Diferentes aplicaciones en reconocimiento de imágenes pueden ser usadas por ejemplo en el
reconocimiento de rasgos biométricos como reconocimiento de iris o de rostros, las cuales son
problemas abiertos y ampliamente estudiados que ayudarían a mostrar la potencial aplicabilidad
del modelo presentado además de delimitar las limitaciones del modelo lo cual es importante
para aplicaciones reales.
En el caso de aplicar el modelo en el reconocimiento de palabras habladas el modelo no
fue comparado otras técnicas por eso seria importante cuantificar las diferencias con métodos
tradicionales para así cuantificar el desempeño real de la propuesta.
La propuesta fue probada para patrones unidimensionales y bidimensionales en ese sentido
podría ser usado para patrones tridimensionales usando el concepto del voxel lo cual seria una
extension natural del modelo propuesto, la diferencia entre las aplicaciones anteriores seria
minima, seria interesante mostrar una aplicación en esa area que hoy en día es posible ya que
varios dispositivos permiten tener patrones en esa dimension (imágenes 3D).
Referencias Bibliográficas
Albert, R., Jeong, H., and Barabási, A. (2000). Error and attack tolerance of complex networks.
Nature, 406(6794):378–382.
Aldana, M. (2006). Tutorial redes complejas. Technical report, Instituto de Ciencias Físicas
UNAM. http://www. fis. unam. mx/˜ max/English/notasredes.pdf.
Aldana, M. and Cluzel, P. (2003). A natural class of robust networks. Proceedings of the
National Academy of Sciences of the United States of America, 100(15):8710.
Amancio, D. R., Nunes, M. G., Oliveira Jr, O. N., and Costa, L. d. F. (2012). Extractive
summarization using complex networks and syntactic dependency. Physica A: Statistical
Mechanics and its Applications, 391(4):1855–1864.
Backes, A., Casanova, D., and Bruno, O. (2009). A complex network-based approach for
boundary shape analysis. Pattern Recognition, 42(1):54–67.
Backes, A., Gonçalves, W., Martinez, A., and Bruno, O. (2010). Texture analysis and classifi-
cation using deterministic tourist walk. Pattern Recognition, 43(3):685–694.
Backes, R. (2010). Estudos de Metodos de Analise de complexidade em imagenes. PhD thesis,
Instituto de Ciencias Matematicas e de Computacao - USP Brasil.
Barabási, A., Albert, R., and Jeong, H. (2000). Scale-free characteristics of random networks:
the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications,
281(1-4):69–77.
Barabasi, A. and Crandall, R. (2003). Linked the new science of networks. American journal
of Physics, 71:409.
89
REFERENCIAS BIBLIOGRÁFICAS 90
Bialonski, S. (2012). Inferring complex networks from time series of dynamical systems: Pit-
falls, misinterpretations, and possible solutions. arXiv preprint arXiv:1208.0800.
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D. (2006). Complex networks:
Structure and dynamics. Physics reports, 424(4-5):175–308.
Box, G., Jenkins, G., and Reinsel, G. (1976). Time series analysis: forecasting and control.
Holden-day San Francisco.
Campanharo, A. S., Sirer, M. I., Malmgren, R. D., Ramos, F. M., and Amaral, L. A. N. (2011).
Duality between time series and networks. PloS one, 6(8):e23378.
Canny, J. (1986). A computational approach to edge detection. Pattern Analysis and Machine
Intelligence, IEEE Transactions on, 8(6):679–698.
Chatfield, C. (2003). The analysis of time series: an introduction. CRC Pr I Llc.
Chuctaya, J., Mena, J., Humpire, G., Rodriguez, A., Beltrán, C., and Patino, R. (2010). Detec-
ción de huevos helmintos mediante plantillas dinámicas. Conferencia Latinoamericana de
Informática CLEI, pages 1–12.
Costa, L., Rodrigues, F., Travieso, G., and Boas, P. (2007). Characterization of complex net-
works: A survey of measurements. Advances in Physics, 56(1):167–242.
Davidsen, J., Grassberger, P., and Paczuski, M. (2005). Earthquake recurrence as a record
breaking process. Arxiv preprint physics/0507082.
de Angelis André, F. (2005). Tutorial redes complexas. Techni-
cal report, Fundação de Amparo à Pesquisa do Estado de São Paulo.
www.ft.unicamp.br/∼andre/Gerais/Tutorial_RedesComplexas.pdf.
Dellnitz, M., Molo, M., Metzner, P., Preis, R., and Sch
"utte, C. (2006). Graph algorithms for dynamical systems. Analysis, modeling and simulation
of multiscale problems, pages 619–645.
Donner, R., Hinrichs, U., and Scholz-Reiter, B. (2008). Symbolic recurrence plots: A new
quantitative framework for performance analysis of manufacturing networks. The European
Physical Journal-Special Topics, 164(1):85–104.
Donner, R. V., Zou, Y., Donges, J. F., Marwan, N., and Kurths, J. (2010). Recurrence network-
sŮa novel paradigm for nonlinear time series analysis. New Journal of Physics, 12(3):033025.
Fabricio, A. (2010). Aprendizado de maquina en redes complexas. PhD thesis, Instituto de
Ciencias Matematicas e de Computacao USP Brasil.
REFERENCIAS BIBLIOGRÁFICAS 91
Ferreira, D. S., Papa, A., and Menezes, R. (2013). The small world of seismic events. arXiv
preprint arXiv:1304.4979.
Flint, J., Van Duynhoven, Y., Angulo, F., DeLong, S., Braun, P., Kirk, M., Scallan, E., Fitzger-
ald, M., Adak, G., Sockett, P., et al. (2005). Estimating the burden of acute gastroenteritis,
foodborne disease, and pathogens commonly transmitted by food: an international review.
Clinical infectious diseases, 41(5):698–704.
Franses, P. and Van Dijk, D. (2000). Nonlinear time series models in empirical finance. Cam-
bridge Univ Pr.
Hidalgo, C. (2010). The value in the links: Networks and the evolution of organizations. Natural
Science of Networks.
Hirata, Y., Horai, S., and Aihara, K. (2008). Reproduction of distance matrices and original time
series from recurrence plots and their applications. The European Physical Journal Special
Topics, 164(1):13–22.
Hu, M. (1962). Visual pattern recognition by moment invariants. Information Theory, IRE
Transactions on, 8(2):179–187.
Humpire, G., Chuctaya, J.and Gutierrez, J. C., Bruno, O., and Beltrán, C. (2011). Detección de
huevos helmintos mediante plantillas dinámicas. Visão Computacional em Bioinformática.
Keeling, M. and Eames, K. (2005). Networks and epidemic models. Journal of the Royal
Society Interface, 2(4):295.
Keogh, E., Chu, S., Hart, D., and Pazzani, M. (2004). Segmenting time series: A survey and
novel approach. World Scientific Publishing.
Kim, H. and Kim, J. (2005). Cyclic topology in complex networks. Arxiv preprint
physics/0503168.
Kurita, T., Otsu, N., and Abdelmalek, N. (1992). Maximum likelihood thresholding based on
population mixture models. Pattern Recognition, 25(10):1231–1240.
Lacasa, L., Luque, B., Ballesteros, F., Luque, J., and Nuño, J. C. (2008). From time series to
complex networks: The visibility graph. Proceedings of the National Academy of Sciences,
105(13):4972–4975.
Lam, S. (1996). Texture feature extraction using gray level gradient based co-occurence matri-
ces. In Systems, Man, and Cybernetics, 1996., IEEE International Conference on, volume 1,
pages 267–271. IEEE.
REFERENCIAS BIBLIOGRÁFICAS 92
Latora, V. and Marchiori, M. (2001). Efficient behavior of small-world networks. Physical
Review Letters, 87(19):198701.
Liao, W. et al. (2005). Clustering of time series data–a survey. Pattern Recognition,
38(11):1857–1874.
Lin, C. and Lin, W. (2011). Image retrieval system based on adaptive color histogram and
texture features. The Computer Journal, 54(7):1136–1147.
Luque, B., Lacasa, L., Ballesteros, F., and Luque, J. (2009). Horizontal visibility graphs: Exact
results for random time series. Physical Review E, 80(4):046103.
Marina, M. J. and Carlos, G. C. J. (2010). Modelamiento de red compleja para el análisis de
comunidades en twitter. Proceedings, CSPC-2010 IX Congreso de la Sociedad Peruana de
Computación, pages 113–122.
Marwan, N., Donges, J., Zou, Y., Donner, R., and Kurths, J. (2009). Complex network approach
for recurrence analysis of time series. Physics Letters A, 373(46):4246–4254.
Newman, M. (2001). Scientific collaboration networks. i. network construction and fundamen-
tal results. Physical review E, 64(1):016131.
Newman, M. (2003). The structure and function of complex networks. SIAM review,
45(2):167–256.
P., E. and A., R. (1959). On random graphs. Publicationes Matematicae, 6:290–297.
Pagani, G. A. and Aiello, M. (2013). The power grid as a complex network: a survey. Physica
A: Statistical Mechanics and its Applications.
Pardo, T., Antiqueira, L., das Gracas Nunes, M., Oliveira, O., and da Fontoura Costa, L.
(2006). Using complex networks for language processing: The case of summary evalua-
tion. In Communications, Circuits and Systems Proceedings, 2006 International Conference
on, volume 4, pages 2678–2682. IEEE.
Parker, J. (2010). Algorithms for image processing and computer vision. Wiley.
Ravasz, E. and Barabási, A. (2003). Hierarchical organization in complex networks. Physical
Review E, 67(2):026112.
Reijneveld, J., Ponten, S., Berendse, H., and Stam, C. (2007). The application of graph theoreti-
cal analysis to complex networks in the brain. Clinical Neurophysiology, 118(11):2317–2331.
REFERENCIAS BIBLIOGRÁFICAS 93
Rubinov, M. and Sporns, O. (2010). Complex network measures of brain connectivity: uses
and interpretations. Neuroimage, 52(3):1059–1069.
Salas, J. and Delleur, J. (1980). Applied modeling of hydrologic time series. Water Resources
Publication.
Tan, H., Gelfand, S., and Delp, E. (1989). A comparative cost function approach to edge
detection. Systems, Man and Cybernetics, IEEE Transactions on, 19(6):1337–1349.
Vapnik, V. (2000). The nature of statistical learning theory. Springer-Verlag New York Inc.
Wang, D. (2011). Multifractal characterisation and analysis of complex networks.
Watts, D. and Strogatz, S. (1998a). Collective dynamics of Śsmall-worldŠnetworks. nature,
393(6684):440–442.
Watts, D. and Strogatz, S. (1998b). Small world. Nature, 393:440–442.
Wesley, N. (2010). Caminhadas deterministicas em redes complexas, aplicda en visao com-
putacional. PhD thesis, Instituto de Ciencias Matematicas e de Computacao - USP Brasil.
Xu, X., Zhang, J., and Small, M. (2008). Superfamily phenomena and motifs of net-
works induced from time series. Proceedings of the National Academy of Sciences,
105(50):19601–19605.
Yang, Y. and Yang, H. (2008). Complex network-based time series analysis. Physica A: Statis-
tical Mechanics and its Applications, 387(5-6):1381–1386.
Zhang, J. (2007). Detecting and describing pseudo-periodic dynamics from time series.
Zhang, J. and Small, M. (2006). Complex network from pseudoperiodic time series: Topology
versus dynamics. Physical review letters, 96(23):238701.
Zhang, J., Sun, J., Luo, X., Zhang, K., Nakamura, T., and Small, M. (2008). Characterizing
pseudoperiodic time series through the complex network approach. Physica D: Nonlinear
Phenomena, 237(22):2856–2865.