Diseño e implementación de una herramienta con metaheurísticas para la aproximación de sub-espacios óptimos en problemas de regresión lineal

Abstract

Gracias a los avances tecnológicos, los sistemas de información cada día han ido almacenando conjuntos de datos cada vez más grandes. Por lo anterior, crear modelos de estimación ha sido una tarea necesaria en diferentes campos de acción. La regresión lineal, como modelo matemático, es entonces una herramienta de ajuste que aproxima la relación que hay entre la variable dependiente (la solución asociada al sub-espacio) y las variables independientes (los atributos de grupo de muestras dadas). El inconveniente que presenta la regresión lineal es que compromete cierta precisión en el ajuste a cambio de tener un tiempo menor de procesamiento.

El proyecto presenta como resultado cuatro mecanismos de optimización combinatoria (basados en: Búsqueda Tabú, Recocido Simulado, Colonia de Hormigas y un Algoritmo Genético) que realizan el proceso de estimación agrupando atributos del conjunto de datos haciendo posible la generación de un sub-espacio más óptimo que el de la regresión lineal simple tradicional.

La solución propuesta realiza agrupamiento de atributos y consta de algoritmos de validación cruzada que generan los coeficientes para la regresión creada, estos son buscados mediante una descomposición en valores singulares, efectuando una mejora en la velocidad con una perdida muy baja de precisión, esto se valida con el método de mínimos cuadrados, considerando que la distancia entre las ecuaciones generadas represente mejor la muestra. Cuando se obtiene la mejor solución, luego de realizar distintas iteraciones, se obtienen los coeficientes obtenidos por el recurso desarrollado. Para realizar las pruebas se tomaron diferentes conjuntos de datos con una cantidad relativamente grande de atributos (20 a 100), todos ellos de libre acceso obteniendo así sub-espacios en los que el error de aproximación era menor al de la solución obtenida por medio de la regresión lineal tradicional.

Thanks to technological advances, information systems store bigger datasets. This is why creating estimation models has been a necessary task to manage appropriately any given system, whether in a public or a private setting. Linear regression, as a mathematical model is, then, an adjustment tool which approximates the relation that exists between a dependent variable (related to the solution) and the independent variables (the attributes of a samples group). The inconvenient presented by linear regression is that it compromises some precision in the adjustment, in exchange of less processing time.

The project presents as result four combinatorial optimization mechanisms (based on: Tabu Search, Simulated Annealing, Ant Colony and a genetic algorithm) that carry out the estimation process grouping attributes from the dataset, attempting to generate a more optimum sub-space than that in the traditional simple linear regression. A waterfall model method was used to complete the project.

The proposed solution groups attributes and consists of crossovering algorithms that generate the coefficients for the given regression. These are found through a singular value decomposition, reaching an improvement in the speed, with a very low precision loss. This is validated with the least squares method, considering that the distance between the given equations represents the sample better. When the best solution is obtained, after performing various iterations, the coefficients given by the developed resource were obtained. To carry out the tests different datasets were taken with many attributes (between 20 and 100), all of them of free access obtaining a sub-space in which the approximation error was lower than the solution obtained from traditional linear regression.