Un sistema clasificador no supervisado utilizando coloración de gráficas suaves
2014Profesores: 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.
Ultima actualización 14/08/2022 por pcyti