Selección de instancias y atributos en conjuntos de datos mediante algoritmos sobre grafos

Resumen

Los grafos son de utilidad en un sinfín de problemas. Con la aparición de las redes de comunicaciones, internet, las redes sociales, etcétera, que no son sino grafos, su utilidad y aplicabilidad se ha visto incrementada. La Minería de Datos se ha utilizado ampliamente para analizar los grafos; sin embargo en pocas ocasiones se han utilizado los grafos para desarrollar algoritmos de Minería de Datos. Muchos problemas están descritos naturalmente como grafos, como todos aquellos que tengan que ver con rutas, flujos, redes, etcétera; este tipo de problemas se resuelve evidentemente con algoritmos sobre grafos. Otros problemas no tienen en principio nada que ver con un grafo, pero haciendo las transformaciones oportunas, pueden convertirse en un grafo, pudiéndose ya resolver con los algoritmos correspondientes. La posibilidad que ofrecen los grafos de analizar informaciones en un contexto global nos animó a abordar problemas clásicos de la Minería de Datos sobre esta estructura, en concreto la selección de subconjuntos de atributos y de subconjuntos de instancias para ser aplicados a la clasificación. Hemos desarrollado sendos algoritmos: uno para la selección de un subconjunto instancias, en el que consideramos las instancias como nodos de un grafo sobre el que aplicamos un algoritmo similar al PageRank que nos permite establecer un rango entre las instancias. A partir de este ranking hemos desarrollado un algoritmo de selección de instancias que resulta tan bueno en precisión como los mejores algoritmos existentes, mejorándolos en reducción. El otro problema que hemos abordado es el de la selección de un subconjunto de atributos. Para esto hemos representado los atributos como nodos de un grafo, usando correlaciones como aristas y a este grafo le hemos aplicado un algoritmo clásico, el del Flujo Máximo ¿ Corte Mínimo, que nos devuelve un subconjunto de atributos. El algoritmo desarrollado obtiene unos resultados muy buenos. Siendo conscientes de que en el mundo de la Minería de Datos el avance de una décima puede ser aparentemente poco, para dotar de fortaleza nuestras afirmaciones hemos realizado un riguroso análisis estadístico de los resultados que nos permite afirmar que sí que hemos conseguido buenos algoritmos.