Tesis doctorales DAC - AKS Doktoretza tesiak
Permanent URI for this collection
Browse
Recent Submissions
Publication Open Access Aggregation and pre-aggregation functions in fuzzy rule-based classification systems(2018) Lucca, Giancarlo; Bustince Sola, Humberto; Sanz Delgado, José Antonio; Automática y Computación; Automatika eta KonputazioaUna manera eficiente de tratar problemas de clasificación, entre otras, es el uso de Sistemas de Clasificación Basados en Reglas Difusas (SCBRDs). Estos sistemas están compuestos por dos componentes principales, la Base de Conocimiento (BC) y el Método de Razonamiento Difuso (MRD). El MRD es el método responsable de clasificar nuevos ejemplos utilizando la información almacenada en la BC. Un punto clave del MRD es la forma en la que se agrega la información proporcionada por las reglas difusas disparadas. Precisamente, la función de agregación es lo que diferencia a los dos MRDs más utilizados de la literatura especializada. El primero, llamado de Regla Ganadora (RG), tiene un comportamiento promedio, es decir, el resultado de la agregación está en el rango delimitado por el mínimo y el máximo de los valores a agregar y utiliza la mayor relación entre el nuevo ejemplo a clasificar y las reglas. El segundo, conocido como Combinación Aditiva (CA), es ampliamente utilizado por los algoritmos difusos más precisos de la actualidad y aplica una suma normalizada para agregar toda la información relacionada con el ejemplo. Sin embargo, este método no presenta un comportamiento promedio. En este trabajo de tesis, proponemos modificar la manera en la que se agrega la información en el MRD, aplicando generalizaciones de la integral Choquet. Para ello, desarrollamos nuevos conceptos teóricos en el campo de los operadores de agregación. En concreto, definiremos generalizaciones de la Choquet integral con y sin comportamientos promedio. Utilizamos estas generalizaciones en el MRD del clasificador FARC-HD, que es un SCBRD del estado del arte. A partir de los resultados obtenidos, demostramos que el nuevo MRD puede ser utilizado, de manera eficiente, para afrontar problemas de clasificación. Además, mostramos que los resultados son estadísticamente equivalentes, o incluso superiores, a los clasificadores difusos considerados como estado del arte.Publication Open Access Novel methodologies for improving fuzzy classifiers: dealing with multi-class and Big Data classification problems(2018) Elkano Ilintxeta, Mikel; Galar Idoate, Mikel; Barrenechea Tartas, Edurne; Automática y Computación; Automatika eta KonputazioaLos Sistemas de Clasificación Basados en Reglas Difusas (SCBRDs) son métodos de aprendizaje automático que permiten construir modelos predictivos capaces de predecir la clase a la que pertenecen los datos de entrada. La ventaja de estos sistemas es que proporcionan un modelo formado por una serie de reglas que contienen etiquetas lingüísticas interpretables por el ser humano (por ejemplo, “bajo”, “medio”, “alto”), lo que les permite explicar el razonamiento llevado a cabo al realizar una predicción. Estas etiquetas lingüísticas permiten a los SCBRDs no solamente explicar el porqué de las predicciones, sino también manejar la incertidumbre proveniente de información imprecisa. Los problemas de clasificación pueden dividirse en dos grupos dependiendo del número de clases que los componen: binarios (dos clases) y multi-clase (más de dos clases). En general, los problemas multi-clase implican fronteras de decisión más complejas que son más difíciles de aprender que en problemas binarios, debido al mayor número de clases. Una forma eficaz de lidiar con esta situación es descomponer el problema multi-clase original en problemas binarios más sencillos que son afrontados por clasificadores independientes, cuyas predicciones son agregadas cuando se clasifican los datos de entrada. Esta metodología ha mostrado ser eficaz a la hora de mejorar el rendimiento de una gran variedad de clasificadores, incluidos los SCBRDs. Sin embargo, el uso de estrategias de descomposición en SCBRDs plantea una nueva problemática: lidiar con diferentes estructuras de reglas y métodos de razonamiento difuso (FRM). Las diferencias estructurales en las reglas vienen dadas por la variedad de métodos de construcción de reglas existentes en la literatura. Estos métodos pueden diferir, por ejemplo, en el tipo de etiquetas lingüísticas generadas, en el operador de conjunción/disyunción empleado en reglas con más de un antecedente, o en la longitud media de las reglas. Por otro lado, el FRM encargado de inferir la salida adecuada a partir de las reglas construidas puede variar notablemente de un SCBRD a otro. Estos factores hacen que el comportamiento de las técnicas de descomposición sea dependiente del SCBRD empleado. Por consiguiente, algunos de los métodos de agregación más populares no son capaces de aprovechar el potencial mostrado en otro tipo de clasificadores. Además de la dificultad añadida de los problemas multi-clase, en los últimos años las técnicas de aprendizaje automático se han topado con un nuevo reto: en ocasiones la cantidad de información a procesar excede la capacidad de cómputo o almacenamiento de un ordenador convencional moderno, lo que denominamos problemas Big Data. Para solventar este problema se hace uso de la computación distribuida, la cual consiste en distribuir los datos a través de múltiples nodos (ordenadores) con el objetivo de procesarlos en paralelo. A pesar de que esta metodología soluciona los problemas asociados con las exigencias de cómputo y almacenamiento, el procesamiento distribuido de la información implica diseñar métodos que soporten dicha funcionalidad. En el caso de los SCBRDs diseñados para Big Data, la dificultad añadida de la computación distribuida ha impedido explotar el potencial que han mostrado estos sistemas cuando se han aplicado de forma local y secuencial. Además de la computación distribuida, otra metodología (complementaria) para poder manejar grandes volúmenes de datos son las técnicas de reducción de prototipos (PR). Los métodos de PR permiten que algoritmos de aprendizaje automático que no están diseñados para Big Data puedan ejecutarse en estos entornos empleando una versión reducida de los datos. Sin embargo, gran parte de las aproximaciones de PR propuestas hasta la fecha presentan serias limitaciones de escalabilidad que afectan a su eficiencia, debido en gran parte a la complejidad computacional cuadrática que generalmente caracteriza a este tipo de técnicas. El objetivo de esta tesis es mejorar el rendimiento de los SCBRDs en problemas multi-clase y Big Data. En el caso de los problemas multi-clase, hemos estudiado y analizado el efecto de diferentes métodos de aprendizaje y razonamiento difuso de varios SCBRDs en el rendimiento de las estrategias de descomposición. Una vez identificados algunos de los problemas que presenta esta sinergia, hemos propuesto una modificación del FRM que permite mejorar su rendimiento. En cuanto a las metodologías planteadas para Big Data, hemos presentado dos nuevos algoritmos de aprendizaje distribuido para SCBRDs que solucionan algunas de las limitaciones presentes en los métodos existentes. De forma transversal, hemos aprovechado uno de estos algoritmos para desarrollar un nuevo método de PR de complejidad lineal.Publication Open Access Computing with uncertainty truth degrees: a convolution-based degrees(2017) Miguel Turullols, Laura de; Bustince Sola, Humberto; Baets, Bernard de; Induráin Eraso, Esteban; Automática y Computación; Automatika eta KonputazioaLa teoría de los conjuntos difusos puede contemplarse como un conjunto de herramientas matemáticas excepcionalmente adaptadas para trabajar con información incompleta, falta de nitidez e incertidumbre no aleatoria. De hecho, como herramienta en ingeniería, para traducir el lenguaje natural humano impreciso en un objeto matemático, los conjuntos difusos juegan un papel decisivo para superar la brecha entre el hombre y los ordenadores. Sin embargo, es ampliamente conocido que la asignación de un valor preciso como pertenencia no es una tarea sencilla. En la literatura, se han propuesto y estudiado varias generalizaciones de los conjuntos difusos para resolver esta dificultad. Más aún, estas generalizaciones han demostrado ser una herramienta útil, al mejorar los resultados en diferentes aplicaciones. Las generalizaciones difieren de los conjuntos difusos en el objeto matemático que se utiliza para modelar la imprecisión y/o incertidumbre. Especifícamente, los conjuntos difusos toman elementos en el intervalo unidad [0, 1] mientras que las generalizaciones toman objetos matemáticos más complejos como intervalos (conjuntos difusos intervalo-valorados), subconjuntos del intervalo unidad (conjuntos difusos "conjunto-valorados") o funciones (conjuntos difusos tipo-2), entre otros. No obstante, el uso de las generalizaciones de los conjuntos difusos tiene un gran inconveniente. Antes de aplicar las generalizaciones de los conjuntos difusos es necesario adaptar ad hoc cada noción teórica al correspondiente objeto matemático que modela la incertidumbre en la aplicación, es decir, es necesario redefinir cada noción teórica reemplazando el intervalo unidad [0, 1] por objetos matemáticos más complejos. En la historia de los conjuntos difusos quedó claro relativamente pronto que la relación natural entre la teoría de conjuntos y la lógica clásica podía ser imitada generando una relación entre la teoría de los conjuntos difusos y la lógica multi-valuada. Hoy en día esta lógica multivaluada recibe el nombre de lógica difusa. Del mismo modo, cada generalización de los conjuntos difusos genera un nuevo sistema lógico. Todos estos sistemas lógicos coinciden en que intentan modelar incertidumbre, pero difieren en el objeto matemático que representa esta incertidumbre. Es fácil comprobar que el mismo problema entre conjuntos difusos y sus generalizaciones puede encontrarse en los distintos sistemas lógicos, es decir, aunque todos ellos son similares, cada noción teórica tiene que ser redefinida para cada lógica. Este problema, junto con el gran número de lógicas que modelan incertidumbre, nos ha llevado a estudiar si es o no posible encontrar un sistema que englobe estas lógicas y nos ha motivado a proponer un sistema lógico que permita modelar la incertidumbre de manera más flexible. Centrándonos especialmente en sistemas lógicos provenientes de la lógica difusa, en esta tesis doctoral proponemos un nuevo sistema lógico que recupera varias de las lógicas de la literatura. La principales ventajas de nuestra propuesta son: evitará la excesiva repetición de las nociones teóricas; permitirá adaptar la aplicación a la generalización de los conjuntos difusos más adecuada de una manera mucho más sencilla. En esta tesis doctoral presentamos la semántica del modelo lógico propuesto junto con un estudio en profundidad de la operación de convolución que se utiliza para definir las conectivas disyunción y conjunción del sistema.Publication Open Access Técnicas eficientes de filtrado de tráfico para monitorización de redes de comunicaciones(2001) Magaña Lizarrondo, Eduardo; Aracil Rico, Javier; Villadangos Alonso, Jesús; Automática y Computación; Automatika eta KonputazioaLas necesidades de intercambio de datos han crecido de manera espectacular en los últimos años y con ello la infraestructura de telecomunicaciones asociada. Además, la aparición de nuevos servicios ha requerido cada vez un control más estricto de la red. Por todo ello, la gestión de las redes de comunicaciones se ha convertido en un campo de actuación muy importante. Dentro de él se pueden enmarcar los sistemas de monitorización que ofrecen información detallada del tráfico que circula por las redes. En el presente trabajo se presenta un algoritmo de filtrado de paquetes con aplicación a los sistemas de monitorización de redes de datos que poseen una problemática particular. En concreto, el número de filtrados simultáneos que se suele requerir a los sistemas de monitorización es elevado. En una primera parte se presentan las diferentes alternativas existentes en la actualidad para el filtrado de paquetes. Por un lado están los sistemas packet filter, optimizados para filtrado de un único flujo de paquetes. Por otro lado existen multitud de propuestas para clasificación de paquetes en routers de alta velocidad, que sin embargo se centran únicamente en campos muy concretos del paquete como las direcciones IP destino para realizar la clasificación. También existen sistemas de filtrado o clasificación de paquetes en los propios sistemas operativos, para poder proveer de diferentes puntos de acceso a servicios a las aplicaciones de la misma máquina y para realizar el encaminamiento cuando la máquina posea varios interfaces de red. Existen escasas propuestas específicamente orientadas a sistemas de monitorización. Posteriormente se realiza una propuesta de técnica de filtrado que se aprovecha de las particularidades de los sistemas de monitorización: el algoritmo PAM-Tree. Su característica principal es la reutilización de bloques de subfiltrado con lo que se soporta de manera más adecuada un mayor número de filtros simultáneos. Además se incorporan en la propia estructura de filtrado los parámetros de monitorización por lo que la actualización de parámetros es inmediata a la vez que se realiza el proceso de filtrado de cada paquete. Tras su descripción, se realiza una formalización mediante teoría de autómatas que se aplica a la demostración de las propiedades del algoritmo propuesto. Una vez presentado el algoritmo, se pasa a un estudio analítico, modelando el coste de filtrado de un paquete como el tiempo de servicio en un sistema de colas M/G/1. Al comparar el modelo del algoritmo PAM-Tree con otro aplicable a los sistemas de tipo packet filter, se comprueba la mejora obtenida con PAM-Tree conforme crece el número de filtros. Tras ello, una comparativa experimental entre PAM-Tree y los packet filter BPF/LSF nos dará una visión más real del comportamiento del algoritmo propuesto sobre implementaciones de sistemas de monitorización. Los resultados experimentales obtenidos validan el modelo analítico considerado. El algoritmo propuesto se ha implementado en dos sistemas de monitorización implantados sobre las redes de datos de una empresa fabricante de coches y una operadora de cable regional, en dos versiones, una primera con funcionalidades recortadas. El algoritmo de filtrado es el núcleo fundamental de estas herramientas y su funcionamiento de terminará la flexibilidad en la definición de parámetros de monitorización de red por parte del gestor.Publication Open Access Aproximación al modelado y predicción de tráfico de Internet como múltiplex de conexión de transporte(2001) Morató Osés, Daniel; Aracil Rico, Javier; Automática y Computación; Automatika eta KonputazioaEl tráfico de datos en la Internet actual presenta un nuevo reto de caracterización y modelado para el correcto dimensionamiento de los equipos y enlaces que conforman la llamada “red de redes”. En este trabajo presentamos una revisión de los modelos propuestos hasta la fecha, lo cual nos lleva desde los límites de la telefonía clásica hasta los conceptos de dependencia a largo plazo y autosimilitud. A partir de estos modelos abordamos la caracterización de una gran población de usuarios de Internet. Para ello nos hemos basado en trazas del tráfico del enlace IP sobre ATM para acceso a Internet en la Universidad Pública de Navarra. Dichas trazas han sido obtenidas mediante una novedosa herramienta de monitorización de enlaces ATM. Con estas trazas presentamos un análisis macroscópico de protocolos y servicios en el enlace que nos muestra a TCP como principal protocolo y al Web como el servicio más utilizado al suponer más de tres cuartas partes del tráfico generado. A la vista de la predominancia de estas conexiones TCP realizamos una caracterización en base a procesos estocásticos para el múltiples de flujos TCP. Dicha caracterización se fundamenta en varias características observadas del tráfico, concretamente que la tasa de las conexiones TCP depende fuertemente del retardo extremo a extremo (RTT) de la conexión y que la intermitencia de las mismas no sigue la progresión exponencial que se esperaría del algoritmo slow-start. Esto nos lleva a un modelo mediante restricciones (σ, ρ) que permite el empleo de tecnologías de conmutación de circuitos para la reserva de ancho de banda por flujo. Con el conocimiento obtenido del funcionamiento de los flujos TCP en la red actual realizamos una revisión del modelo M/G/∞ de flujos. Este es uno de los modelos más empleados tanto para generación de tráfico sintético de datos como en el estudio analítico de las características del mismo. Confirmamos dos de las hipótesis en que se basa (proceso de llegadas de Poisson y duraciones de flujos con varianza infinita), pero vemos que la hipótesis de tasa constante de transferencia dista de lo observado en el tráfico real. Por ello proponemos una alteración del modelo mediante la incorporación de una variable aleatoria de Weibull para la tasa de flujos. Esta modificación permite que el tráfico resultante ajuste mejor la variabilidad de la marginal del mismo. El modelo M/G/∞ clásico subestima la variabilidad del tráfico aunque modele correctamente su dependencia a largo plazo. Mostramos, sin embargo, que en futuras redes de alta velocidad que formarán la próxima generación de internet el efecto de dependencia a largo plazo tenderá a desaparecer a costa de un aumento en la variabilidad del tráfico, que pasará a ser el factor que condicione las prestaciones de la red. Esto último es un fuerte apoyo para aceptar modificaciones del modelo en la línea de la propuesta. Finalmente, empleamos la caracterización de flujos TCP obtenida para proponer un algoritmo de estimación de ancho de banda basado en el RTT de las conexiones. La estimación está orientada a la reserva de ancho de banda en enlaces de proveedores de acceso a Internet. Los resultados muestran que la estimación en base a parámetros conocidos a priori es realizable y mejora los resultados obtenidos con asignadores basados en tasa de pico, asignaciones estáticas o best-effort. Esto abre numerosas posibilidades de estudio de algoritmos de asignación así como de cálculo dinámico de los parámetros de los mismos.Publication Open Access Herramientas pasivas para el análisis y evaluación de prestaciones en redes de alta velocidad(2016) Prieto Suárez, Iria; Izal Azcárate, Mikel; Automática y Computación; Automatika eta KonputazioaHoy en día el uso de las redes de ordenadores se ha vuelto imprescindible para casi cualquier tarea. Como consecuencia de la expansión de las mismas, comprobar que una red alcanza el rendimiento y funcionamiento esperado supone una tarea crítica para los administradores. Debido a las dimensiones y a la cantidad de flujos de datos que alcanzan, no siempre es posible utilizar medidas activas. En este tipo de escenarios se puede utilizar herramientas de monitorización pasiva, aunque estos métodos no son siempre triviales. Durante la realización de esta tesis se han analizado algunos problemas para la evaluación de prestaciones a través del uso de herramientas pasivas. El primer enfoque ha sido el estudio de un generador de tráfico, que sirviera para ser utilizado en simulaciones en las que se pueda reproducir los problemas de una red real. Con este objetivo, se ha propuesto una adaptación del algoritmo de Perlin Noise para generar tráfico al vuelo, de forma ilimitada y con las características de un modelo Fractional Gaussian Noise (FGN). La precisión obtenida de este modelo era comparable con la obtenida por un generador de tipo Random Midpoint Displacement (RMD). Otro de los problemas analizados durante la realización de la tesis ha sido la detección de los problemas de disponibilidad percibidos por los clientes. En la actualidad, la detección de interrupciones constituye una de las tareas más críticas en una red. Con este objetivo, se ha propuesto un algoritmo para la detección de interrupciones de servicio a través del estudio del tráfico pasivo. El algoritmo propuesto es simple, puesto que se basa en el uso de contadores sencillos y en la utilización de dos filtros, para decidir si en un intervalo de tiempo los clientes no pueden acceder a un servicio. El algoritmo ha sido probado en un entorno emulado y un escenario real con clientes accediendo a servicios populares de Internet. Para ambos escenarios se obtuvieron buenos resultados de detección. Otro problema habitual en las redes es la estimación de la latencia de la red. Mientras que en la literatura se pueden encontrar multitud de estudios para su aproximación a través de medidas activas, se encuentra poco sobre métodos pasivos. Un estimador preciso que puede ser utilizado pasivamente es el uso del Timestamp Transport control Protocol (TCP). Sin embargo, se ha comprobado cómo sólo podría ser usado para un pequeño porcentaje de conexiones. Por este motivo, se ha propuesto un estimador enfocado a redes de alta velocidad, basado en la hipótesis que el servidor intentará ajustarse a la ventana anunciada por TCP en el cliente, sin mandar nunca más datos que los permitidos por este. El método ha sido comparado con los valores obtenidos por el estimador basado en el Timestamp TCP, y si bien no es tan preciso como este, los resultados han sido lo suficientemente buenos como para ser utilizados. La última prestación pasiva analizada ha sido la identificación del algoritmo de control de congestión del protocolo TCP utilizado por los servidores. El algoritmo de control de congestión es un algoritmo interno de TCP, que no es anunciado en el establecimiento de la conexión y que depende del sistema operativo del servidor. En la literatura existen numerosos estudios en los que se compara el rendimiento obtenido en un escenario dependiendo del algoritmo de control de congestión utilizado. Por contra, no hay tantos para la identificación de los mismos y menos todavía de forma pasiva. Se ha realizado una primera aproximación de la identificación pasiva utilizando solamente el parámetro principal que caracteriza estos algoritmos. La estimación del parámetro ha permitido la elaboración de un algoritmo clasificador. Este algoritmo ha sido probado tanto para un escenario de entrenamiento como para uno de validación. Dichos experimentos han derivado en porcentajes de identificación elevados.Publication Open Access Web browsing interactions inferred from a flow-level perspective(2015) Torres García, Luis Miguel; Magaña Lizarrondo, Eduardo; Automática y Computación; Automatika eta KonputazioaDesde que su uso se extendiera a mediados de los noventa, la web ha sido probablemente el servicio de Internet más popular. De hecho, muchos usuarios la utilizan prácticamente como sinónimo de Internet. Hoy en día los usuarios de la web utilizan una gran cantidad dispositivos distintos para acceder a ella desde ordenadores tradicionales a teléfonos móviles, tabletas, lectores de libros electrónicos o, incluso, relojes inteligentes. Además, los usuarios se han acostumbrado a acceder a diferentes servicios a través de sus navegadores web en vez de utilizar aplicaciones dedicadas a ello. Este es el caso, por ejemplo del correo electrónico, del streaming de vídeo o de suites ofimáticas (como la proporcionada por Google Docs). Como consecuencia de todo esto, hoy en día el tráfico web es muy complejo y el efecto que tiene en las redes es muy importante. La comunidad científica ha reaccionado a esta situación impulsando muchos estudios que caracterizan la web y su tráfico y que proponen maneras de mejorar su funcionamiento. Sin embargo, muchos estudios centrados en el tráfico web han considerado el tráfico de los clientes o los servidores en su totalidad con el objetivo de describirlo estadísticamente. En otros casos, se han introducido en el nivel de aplicación al centrarse en los mensajes HTTP. Pocos trabajos han buscado describir el efecto que las sesiones de un sitio web y las visitas a páginas web tienen en el tráfico de un usuario. No obstante, esas interacciones son las que el usuario experimenta al navegar y, por tanto, son las que mejor representan su comportamiento. El trabajo que se presenta en esta tesis gira alrededor de esas interacciones y se enfoca especialmente en identificarlas en el tráfico de los usuarios. Esta tesis aborda el problema desde una perspectiva a nivel de flujo. En otras palabras, el estudio que se presenta se centra en una caracterización del tráfico web obtenida para cada conexión mediante datos de los niveles de transporte y red, nunca mediante datos de aplicación. La perspectiva a nivel de flujo introduce ciertas limitaciones en las propuestas desarrolladas, pero lo compensa al permitir desarrollar sistemas escalables, fáciles de instalar en cualquier red y que evitan acceder a información de usuario que podría ser sensible. En los capítulos de este documento se introducen varios métodos para identificar sesiones a sitios web y descargas de páginas web en el tráfico de los usuarios. Para desarrollar dichos métodos se ha caracterizado tráfico web capturado de varias formas: accediendo a páginas automáticamente, con la ayuda de voluntarios en un entorno controlado y en el enlace de la Universidad Pública de Navarra. Los métodos que presentamos se basan en parámetros a nivel de conexión como los tiempos de inicio y final de los flujos o las direcciones IP de servidor. Estos parámetros se emplean para encontrar conexiones relacionadas en el tráfico de los usuarios. La validación de los resultados obtenidos con los distintos métodos ha sido complicada al no disponer de trazas etiquetadas correctamente que puedan usarse para verificar que las clasificaciones se han realizado de forma correcta. Además, al no haber propuestas similares en la literatura científica ha sido imposible comparar los resultados obtenidos con los de otros autores. Por todo esto ha sido necesario diseña métodos específicos de validación que también se describen en este documento. Ser capaces de identificar sesiones a sitios web y descargas de páginas web tiene aplicaciones inmediatas para administradores de red y proveedores de servicio ya que les permitiría recoger datos sobre el perfil de navegación de sus usuarios e incluso bloquear tráfico indeseado y dar prioridad al importante. Además, las ventajas de trabajar a nivel de conexión se aplican especialmente en su caso. Por último, los resultados obtenidos a través de los métodos presentados en esta tesis podrían emplearse en diseñar esquemas capaces de clasificar el tráfico web dependiendo del servicio que lo haya producido ya que se podrían utilizar como parámetros de entrada las características de múltiples conexiones relacionadas.