Algoritmos eficientes para el cálculo de medidas de consistencia para Selección de Características

Abstract

La Selección de Características es una técnica usada en Aprendizaje Automático que consiste en tener en cuenta únicamente un subconjunto de las características del conjunto de datos sobre el que se realiza el aprendizaje, en lugar de utilizar toda la información disponible, de modo que se simplifique y acelere dicho proceso, procurando mantener la precisión del modelo entrenado resultante, o incluso mejorarla si fuera posible.

Existen varias medidas para evaluar dichos subconjuntos, de forma que, en función de una calificación, sea posible estimar qué subconjunto de características obtendrá los mejores resultados. La medición de la consistencia del subconjunto es un ejemplo de estas medidas, y son varios los beneficios que ofrece. Por desgracia, esta métrica necesita, por regla general, organizar la información completa de los ejemplos del conjunto, según los valores de las características seleccionadas, para comprobar la clase a la que pertenecen, lo que repercute negativamente en su rendimiento. Una vía de organización consiste en utilizar tablas que recojan la información de los ejemplos, ordenadas según los valores de las características.

Esta tesis realiza una caracterización de los diferentes métodos de Selección de Características existentes, y propone el concepto de un caché algorítmico que almacene tablas ordenadas, de modo que puedan ser reutilizadas, con el objetivo de acelerar el proceso de Selección de Características. Dicha propuesta incluye tres posibles métodos de ordenación, así como dos estrategias de gestión de tablas almacenadas.

Con el objetivo de comprobar su rendimiento y determinar su utilidad, se realiza un estudio empírico con 34 conjuntos de datos convencionales, cinco estrategias de búsqueda representativas, cuatro medidas de consistencia y una medida de información, utilizando diferentes combinaciones de métodos de ordenado y estrategias de gestión de caché.

Adicionalmente, se realiza otro estudio empírico con 4 conjuntos de datos con gran cantidad de características y/o ejemplos, cinco estrategias de búsqueda representativas, y dos medidas de consistencia, utilizando diferentes combinaciones de métodos de ordenado y estrategias de gestión de caché, para comprobar si las conclusiones del estudio empírico siguen vigentes en conjuntos de datos de este tipo.

Por último, se realiza otro estudio empírico en el que se compara el caché algorítmico propuesto con otra técnica de aceleración del proceso, consistente en la confección de un conjunto de características inicial a partir de características preseleccionadas basándose en algún criterio. En dicho estudio se compara el rendimiento de dichas técnicas, por separado y de forma conjunta, con 34 conjuntos de datos convencionales, cinco estrategias de búsqueda representativas, cuatro medidas de consistencia y una medida de información, utilizando diferentes combinaciones de métodos de ordenado y estrategias de gestión de caché.

Los resultados de la experimentación realizada muestran que el caché algorítmico de tablas ordenadas propuesto reduce el tiempo de computación, que es competitivo frente a las estructuras de tablas hash, y proporciona recomendaciones acerca de qué método de ordenación, qué estrategia de gestión de caché o si confeccionar un conjunto de datos inicial en función del algoritmo a utilizar o las propiedades del conjunto de datos.

Feature Selection is a technique employed in Machine Learning that involves considering only a subset of the features within the dataset used for learning, rather than exploiting all the available information. The purpose of this approach is to simplify and accelerate the learning process while striving to preserve, or even enhance, the accuracy of the resulting trained model.

Several measures exist for evaluating these subsets in order to estimate, based on a scoring criterion, which subset of features is likely to yield the best results. The consistency measure of a subset is one example of such evaluation criteria and offers several advantages. Unfortunately, this metric generally requires organizing the complete set of examples according to the values of the selected features to verify their corresponding class labels, which negatively impacts performance. One possible way to organize this information is through tables that store the examples sorted by the values of their features.

This thesis presents a characterization of the various existing Feature Selection methods and proposes the concept of an algorithmic cache that stores sorted tables, allowing them to be reused in order to accelerate the Feature Selection process. The proposed approach includes three possible sorting methods and two strategies for managing the stored tables.

To evaluate its performance and determine its usefulness, an empirical study was conducted using 34 conventional datasets, five representative search strategies, four consistency measures, and one information-based measure, applying different combinations of sorting methods and cache management strategies.

In addition, another empirical study was carried out using four datasets with a large number of features and/or examples, together with five representative search strategies and two consistency measures, employing different combinations of sorting methods and cache management strategies to assess whether the conclusions drawn from the previous study remain valid for datasets of this nature.

Finally, a third empirical study was performed to compare the proposed algorithmic cache with another acceleration technique, consisting of constructing an initial feature subset from preselected features based on a specific criterion. This study compares the performance of both techniques, individually and jointly, using the same 34 conventional datasets, five representative search strategies, four consistency measures, and one information-based measure, combined with different sorting methods and cache management strategies.

The results of the experiments demonstrate that the proposed algorithmic cache of sorted tables significantly reduces computation time, achieves performance competitive with hash table structures, and provides insights into which sorting method, cache management strategy, or initialization approach is most appropriate depending on the algorithm employed and the characteristics of the dataset.