Buscando resultados para: Dr. Pedro Lara Velázquez

Un sistema clasificador no supervisado utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Angel Gutiérrez Andrade

Resumen: Un sistema clasificador no supervisado es un tipo especial de reconocimiento de patrones, significa poner una etiqueta a un objeto de acuerdo a sus características. Los seres humanos hacemos reconocimiento de patrones cotidianamente, aunque lo hacemos de forma inconsciente. El reto de un modelo de reconocimiento de patrones es enseñarle a una computadora a hacer esta actividad de una forma eficiente. El problema de coloración de gráficas suaves busca encontrar una coloración que minimiza la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético entre otros.

Objetivo general

• Construir un algoritmo para un sistema clasificador de uso general con el modelo de coloración de gráficas suaves

Objetivos específicos

• Diseñar e implementar un algoritmo de reconocimiento de patrones, ya sea en lenguaje C o FreeBasic bajo el esquema de coloración de gráficas suaves
• Aplicar el algoritmo para clasificación de varias instancias benchmark

Un sistema clasificador no supervisado utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade

Resumen: Un sistema clasificador no supervisado es un tipo especial de reconocimiento de patrones, significa poner una etiqueta a un objeto de acuerdo con sus características. Por ejemplo, cuando alguien observa una foto de un grupo de personas, se puede reconocer si alguno de ellos es alguien conocido, o si se está clasificando la ropa sucia, se puede hacer una pila de “ropa blanca” y una de “ropa oscura”. Los seres humanos hacemos reconocimiento de patrones cotidianamente, aunque lo hacemos de forma inconsciente. El reto de un modelo de reconocimiento de patrones es enseñarle a una computadora a hacer esta actividad de una forma eficiente.

Dado un conjunto de objetos no clasificados, podemos crear una medida de la distancia entre ellos, por ejemplo, si ponemos una medida de la cantidad de luz que refleja un paño podemos decidir si pertenece a la pila de “blancos” u “obscuros”. Si la luz que reflejan dos piezas de ropa es similar, es muy probablemente estarán en la misma pila, o si difieren mucho en luminosidad, van a estar en pilas diferentes. En este caso, la distancia entre objetos se está dando por una sola variable, que es la luminosidad, pero en general, la clasificación se realiza considerando métricas más complejas. El problema de coloración de gráficas suaves busca encontrar una coloración que minimiza la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético entre otros. Se ha demostrado que es un problema NP-duro aunque para instancias pequeñas, máximo de 20 vértices, se utilizan algoritmos exactos que resuelven el problema. Para instancias más grandes el uso de técnicas heurísticas es necesario y se cuenta con varios algoritmos genéricos que resuelven el problema de forma aproximada.

Objetivo general

• Construir un algoritmo para un sistema clasificador de uso general con el modelo de coloración de gráficas suaves.

Objetivos específicos

• Diseñar e implementar un algoritmo de reconocimiento de patrones, ya sea en lenguaje C o FreeBasic bajo el esquema de coloración de gráficas suaves.
• Aplicar el algoritmo para la clasificación de varias instancias benchmark.

Modelo filológico para lenguas romances y germánicas utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El concepto de protolenguaje indoeuropeo fue creado a finales del siglo XIX en Alemania por Franz Bopp, quien notó la gran similaridad entre el alemán y el sánscrito en su libro Gramática comparativa. Bajo este modelo se reconocen 8 subgrupos, de los cuales en esta propuesta se utilizarán dos tipos: instancias en lenguas germánicas y romances. Estos modelos fueron del tipo empírico durante casi 200 años, hasta donde se propone un modelo filológico donde se consideran gráficas y se propone una métrica entre lenguajes basada en sus características. Esta métrica se puede utilizar como base para la generación de las distancias en un modelo de coloración de gráficas suaves.

El problema de coloración de gráficas suaves busca encontrar una coloración que minimice la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético, entre otros. Se ha demostrado que es un problema NP-difícil, aunque para instancias pequeñas, máximo de 20 vértices, se utiliza un modelo de programación lineal entera mixto. Para instancias con más de 20 vértices es necesario el uso de técnicas heurísticas que resuelven el problema de forma aproximada.

Objetivo general

• Crear un modelo filológico para lenguajes romances y germánicos utilizando coloración de gráficas suaves.

Objetivos específicos

• Construcción formal del modelo filológico utilizando coloración de gráficas suaves.
• Seleccionar la mejor métrica al modelo.
• Validar el modelo en un conjunto representativo de lenguas romances.
• Validar el modelo en un conjunto representativo de las lenguas germánicas.

Un sistema clasificador no supervisado utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade

Resumen: Un sistema clasificador no supervisado es un tipo especial de reconocimiento de patrones, significa poner una etiqueta a un objeto de acuerdo a sus características, Los seres humanos hacemos reconocimiento de patrones cotidianamente, aunque lo hacemos de forma inconsciente. El reto de un modelo de reconocimiento de patrones es enseñarle a una computadora a hacer esta actividad de una forma eficiente. En un sistema clasificador, la etiqueta puede ser determinada previamente, y se debe decidir poner un objeto en una clase particular o no. Dado un conjunto de objetos no clasificados, podemos crear una medida de la distancia entre ellos, por ejemplo, si ponemos una medida de la cantidad de luz que refleja un paño podemos decidir si pertenece a la pila de “blancos” u “obscuros”. El Problema de Coloración de Gráficas Suaves (PCGS) es un caso especial del problema de coloración donde se busca una coloración que minimiza la tensión en la gráfica, es decir, se minimiza la suma total de las tensiones entre los vértices que tienen el mismo color.

Objetivo general

• Construir un algoritmo para un sistema clasificador de uso general con el modelo de coloración de gráficas suaves

Objetivos específicos

• Diseñar e implementar un algoritmo de reconocimiento de patrones, ya sea en lenguaje C o FreeBasic bajo el esquema de coloración de gráficas suaves
• Aplicar el aloritmo para clasificación de varias instancias benchmark

Modelo filológico para lenguas romances y germánicas utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El problema de coloración de gráficas suaves busca encontrar una coloración que minimiza la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético entre otros. Se ha demostrado que es un problema NP-difícil aunque para instancias pequeñas, máximo de 20 vértices, se utiliza un modelo de programación lineal entera mixto. Para instancias con más de 20 vértices es necesario el uso de técnicas heurísticas que resuelven el problema de forma aproximada. El modelo de este proyecto está basado en el Problema de Coloración de Gráficas Suaves (PCGS) el cual es un caso especial del problema de coloración donde se busca una coloración que minimiza la tensión en la gráfica, es decir, se minimiza la suma total de las tensiones entre los vértices que tienen el mismo color.

Objetivo general

• Crear un modelo filológico para lenguajes romances y germánicos utilizando coloración de gráficas suaves

Objetivos específicos

• Construcción formal del modelo filológico utilizando coloración de gráficas suaves
• Seleccionar la mejor métrica al modelo
• Validar el modelo en un conjunto representativo de lenguas romances
• Validar el modelo en un conjunto representativo de lenguas germánicas

Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade

Resumen: La coloración de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignación de frecuencias en problemas de telecomunicación; asignación de registros en un sistema operativo, programación de tareas; entre otras. La coloración de grafos se presenta en una gran variedad de formas de las cuales, la Coloración de Gráficas Suaves (CGS) es considerada una generalización del problema de coloración de gráficas.  El problema de Coloración de Gráficas Suaves se ha utilizado recientemente en problemas de clasificación y de reconocimiento de patrones en general. En este problema tenemos que, dada una gráfica con ponderaciones en las aristas, el objetivo es encontrar una coloración que minimice la suma de las aristas con el mismo color en ambos extremos; es decir, la suma de las penalizaciones denominada dureza. Asimismo, existen otros parámetros importantes en la Coloración de Gráficas Suaves como lo son la solidez, la cual proporciona un valor promedio de las penalizaciones de la gráfica y resilencia que permite encontrar una cantidad adecuada de colores. Es sabido que este problema es del tipo NP-duro y es necesario el uso de metaheurísticas en instancias mayores a 20 vértices.

Objetivo general

• Desarrollar un algoritmo que resuelva varios problemas clásicos de coloración utilizando el enfoque de coloración de gráficas suaves

Objetivos específicos

• Realizar un estudio del estado del arte de los problemas de coloración clásicos, así como su representación como gráfica suave
• Compilación de instancias benchmark clásicas de cada uno de los problemas que se estudiarán
• Desarrollo de los algoritmos de solución
• Análisis de resultados y conclusiones

Búsqueda dispersa para el problema de coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El problema de coloración de gráficas suaves es una generalización del problema de coloración, en donde un grafo completo, las aristas tienen penalizaciones. Este problema se ha demostrado que puede resolver otros problemas tales como coloración mínima, coloración equitativa, entre otros; y en tiempos recientes, como parte de un trabajo de tesis de maestría, se ha demostrado su utilidad como clasificador no supervisado. Debido a que este modelo es del tipo NP-difícil, se requiere el uso de metaheurísticas para problemas con mas de 20 vértices. En este proyecto se propone realizar un algoritmo de solución utilizando la metaheurística de búsqueda dispersa.

Objetivo general

• Desarrollar un algoritmo de solución para el problema de coloración de gráficas suaves utilizando la técnica metaheurística de búsqueda dispersa

Objetivos específicos

• Revisión del estado del arte de problema a resolver y la técnica de solución
• Planteamiento de instancias apropiadas para verificar la calidad del algoritmo
• Propuesta de un algoritmo de solución
• Implementación del algoritmo en C, FreeBASIC o Python, y su validación en las instancias de prueba seleccionadas anteriormente
• Redacción de la idónea comunicación de resultados