Optimización Computacional de ReliefF: Estrategias basadas en Búsqueda Aproximada y Prototipado

Abstract

[Resumen] Ante el crecimiento exponencial del volumen de datos, la selección de características es indispensable, pero la complejidad cuadrática O(n2 ·m) de los algoritmos basados en vecindarios, como ReliefF, resulta insostenible a gran escala, tanto en cómputo como en consumo energético, en contra de los principios de la IA Verde. Este trabajo propone dos variantes que reducen drásticamente ese coste sin alterar el criterio de relevancia, conservando la capacidad de ReliefF para detectar interacciones entre variables. HNSW-ReliefF sustituye la búsqueda exacta de vecinos por consultas de coste sublineal sobre un índice de grafo navegable jerárquico (HNSW), y Proto-ReliefF comprime el conjunto de entrenamiento en un número acotado de prototipos representativos mediante clustering. Sobre datos de hasta millones de instancias, donde ReliefF es inviable, ambas logran aceleraciones de más de dos órdenes de magnitud y reducen las emisiones en más de un 30%, manteniendo una calidad de selección estadísticamente equivalente a la del algoritmo original.

[Abstract] Given the exponential growth in data volume, feature selection is indispensable, yet the quadratic complexity O(n2 · m) of neighbourhood-based algorithms such as ReliefF is unsustainable at scale, both in computation and energy consumption, against the principles of Green AI. This work proposes two variants that drastically reduce that cost without altering the relevance criterion, preserving ReliefF’s ability to detect feature interactions. HNSWReliefF replaces the exact nearest-neighbour search with sublinear-cost queries over a Hierarchical Navigable Small World (HNSW) graph index, and Proto-ReliefF compresses the training set into a bounded number of representative prototypes through clustering. On datasets of up to millions of instances, where ReliefF is infeasible, both achieve speed-ups of more than two orders of magnitude and cut emissions by over one third, while keeping a selection quality statistically equivalent to that of the original algorithm.