{"id":2882,"date":"2022-08-14T03:31:36","date_gmt":"2022-08-14T03:31:36","guid":{"rendered":"https:\/\/pcyti.izt.uam.mx\/?p=2882"},"modified":"2022-08-14T03:31:37","modified_gmt":"2022-08-14T03:31:37","slug":"un-sistema-clasificador-no-supervisado-utilizando-coloracion-de-graficas-suaves-2","status":"publish","type":"post","link":"https:\/\/pcyti.izt.uam.mx\/?p=2882","title":{"rendered":"Un sistema clasificador no supervisado utilizando coloraci\u00f3n de gr\u00e1ficas suaves"},"content":{"rendered":"\n

 Descargar versi\u00f3n PDF<\/a><\/p>\n\n\n\n

Profesores<\/strong>: Dr. Pedro Lara Vel\u00e1zquez<\/a> y Dr. Miguel \u00c1ngel Guti\u00e9rrez Andrade<\/a><\/p>\n\n\n\n

Resumen<\/strong>: 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\u00edsticas. 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\u00e1 clasificando la ropa sucia, se puede hacer una pila de \u201cropa blanca\u201d y una de \u201cropa oscura\u201d. 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\u00f1arle a una computadora a hacer esta actividad de una forma eficiente.<\/p>\n\n\n\n

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\u00f1o podemos decidir si pertenece a la pila de \u201cblancos\u201d u \u201cobscuros\u201d. Si la luz que reflejan dos piezas de ropa es similar, es muy probablemente estar\u00e1n 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\u00e1 dando por una sola variable, que es la luminosidad, pero en general, la clasificaci\u00f3n se realiza considerando m\u00e9tricas m\u00e1s complejas. El problema de coloraci\u00f3n de gr\u00e1ficas suaves busca encontrar una coloraci\u00f3n que minimiza la \u201ctensi\u00f3n\u201d en la gr\u00e1fica, es decir, minimizar la suma de distancias entre v\u00e9rtices con colores id\u00e9nticos. Este modelo se utiliza en la programaci\u00f3n de eventos susceptibles de cambios, asignaci\u00f3n estable de frecuencias del espectro electromagn\u00e9tico entre otros. Se ha demostrado que es un problema NP-duro aunque para instancias peque\u00f1as, m\u00e1ximo de 20 v\u00e9rtices, se utilizan algoritmos exactos que resuelven el problema. Para instancias m\u00e1s grandes el uso de t\u00e9cnicas heur\u00edsticas es necesario y se cuenta con varios algoritmos gen\u00e9ricos que resuelven el problema de forma aproximada.<\/p>\n\n\n\n

Objetivo general<\/strong><\/p>\n\n\n\n