Uso de algoritmos evolutivos para una selección rápida de características con grandes conjuntos de datos
Esta es la última parte de una serie de dos partes sobre la selección de funciones. Leer parte 1 aquí.
Breve resumen: al ajustar un modelo a un conjunto de datos, es posible que desee seleccionar un subconjunto de funciones (en lugar de utilizar todas las funciones), por varias razones. Pero incluso si tiene una función objetivo clara para buscar la mejor combinación de características, la búsqueda puede llevar mucho tiempo si el número de características N es muy grande. Encontrar la mejor combinación no siempre es fácil. La búsqueda de fuerza bruta generalmente no funciona más allá de varias docenas de funciones. Se necesitan algoritmos heurísticos para realizar una búsqueda más eficiente.
Si tienes N características, lo que estás buscando es un vector de N longitud [1, 1, 0, 0, 0, 1, ...] con valores de {0, 1} . Cada componente del vector corresponde a una característica. 0 significa que la característica está rechazada, 1 significa que la característica está seleccionada. Necesita encontrar el vector que minimice la función costo/objetivo que está utilizando.
En el artículo anterior, analizamos un algoritmo clásico, SFS (búsqueda secuencial de características), y lo comparamos con un algoritmo evolutivo eficiente llamado CMA-ES. Comenzamos con el conjunto de datos de precios de la vivienda en Kaggle que, después de algún procesamiento, arrojó 213 características con 1453 observaciones cada una. El modelo que intentamos adaptar fue statsmodels.api.OLS() y la función objetivo era el BIC (criterio de información bayesiano) del modelo, una medida de pérdida de información. Un BIC más bajo significa un mejor ajuste, por lo que intentamos minimizar el objetivo.
En este artículo, veremos otra técnica evolutiva: los algoritmos genéticos. El contexto (conjunto de datos, modelo, objetivo) sigue siendo el mismo.
Los algoritmos genéticos están inspirados en la evolución biológica y la selección natural. En la naturaleza, los seres vivos son (en términos generales) seleccionados por los genes (rasgos) que facilitan la supervivencia y el éxito reproductivo, en el contexto del entorno en el que viven.
Ahora piense en la selección de funciones. Tienes N características. Estás intentando encontrar vectores binarios de longitud N. [1, 0, 0, 1, 1, 1, ...] que seleccionan las características (1 = característica seleccionada, 0 = característica rechazada) para minimizar una función costo/objetivo.
Cada uno de estos vectores puede considerarse como un “individuo”. Cada componente del vector (valor 0 o valor 1) se convierte en un “gen”. Aplicando la evolución y la selección, podría ser posible hacer evolucionar una población de individuos de tal manera que se acerque al mejor valor para la función objetivo que nos interesa.
Aquí está GA en pocas palabras. Comience generando una población de individuos (vectores), cada vector de longitud N. Los valores de los componentes del vector (genes) se eligen aleatoriamente entre {0, 1}. En el siguiente diagrama, N = 12 y el tamaño de la población es 8.
Una vez creada la población, evalúe a cada individuo mediante la función objetivo.
Ahora realice la selección: mantenga a los individuos con los mejores valores objetivos y descarte aquellos con los peores valores. Aquí hay muchas estrategias posibles, desde una clasificación ingenua (que no funciona muy bien) hasta la selección de torneos, que es muy eficiente. Aquí hay una breve lista de técnicas de selección.y consulte los enlaces al final para obtener más información.
Una vez que se han seleccionado los mejores individuos y se han descartado los menos aptos, es hora de introducir variación en el acervo genético mediante dos técnicas: cruce y mutación.
El cruce funciona exactamente como en la naturaleza, cuando dos seres vivos se aparean y producen descendencia: el material genético de ambos padres se “mezcla” en la descendencia, con cierto grado de aleatoriedad.
La mutación, una vez más, es más o menos lo que sucede en la naturaleza cuando se producen mutaciones aleatorias en el material genético y se introducen nuevos valores en el acervo genético, aumentando su diversidad.
Después de todo eso, el algoritmo retrocede: los individuos son nuevamente evaluados a través de la función objetivo, ocurre la selección, luego el cruce, la mutación, etc. Se pueden usar varios criterios de parada: el bucle puede romperse si la función objetivo deja de mejorar durante un cierto número de generaciones. O puede establecer un límite estricto para el número total de generaciones evaluadas. En cualquier caso, se debe considerar que los individuos con los mejores valores objetivos son las “soluciones” al problema.
GA tiene varios hiperparámetros que puedes ajustar:
- tamaño de la población (número de individuos)
- probabilidades de mutación (por individuo, por gen)
- probabilidad de cruce
- estrategias de selección, etc.
Realizar pruebas manualmente con varios valores de hiperparámetros es una forma de encontrar el mejor código. O podría encapsular GA en Optuna y dejar que Optuna trabaje para encontrar los mejores hiperparámetros, pero esto es computacionalmente costoso.
Aquí hay un código GA simplificado que se puede usar para seleccionar funciones. Usa la biblioteca profunda, que es muy potente, pero la curva de aprendizaje puede ser pronunciada. Esta versión sencilla, sin embargo, debería ser bastante clara.
# to maximize the objective
# fitness_weights = 1.0
# to minimize the objective
fitness_weights = -1.0# copy the original dataframes into local copies, once
X_ga = X.copy()
y_ga = y.copy()
# 'const' (the first column) is not an actual feature, do not include it
X_features = X_ga.columns.to_list()[1:]
try:
del creator.FitnessMax
del creator.Individual
except Exception as e:
pass
creator.create("FitnessMax", base.Fitness, weights=(fitness_weights,))
creator.create(
"Individual", array.array, typecode='b', fitness=creator.FitnessMax
)
try:
del toolbox
except Exception as e:
pass
toolbox = base.Toolbox()
# Attribute generator
toolbox.register("attr_bool", random.randint, 0, 1)
# Structure initializers
toolbox.register(
"individual",
tools.initRepeat,
creator.Individual,
toolbox.attr_bool,
len(X_features),
)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalOneMax(individual):
# objective function
# create True/False selector list for features
# and add True at the start for 'const'
cols_select = [True] + [i == 1 for i in list(individual)]
# fit model using the features selected from the individual
lin_mod = sm.OLS(y_ga, X_ga.loc[:, cols_select], hasconst=True).fit()
return (lin_mod.bic,)
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
random.seed(0)
pop = toolbox.population(n=300)
hof = tools.HallOfFame(1)
pop, log = algorithms.eaSimple(
pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=10, halloffame=hof, verbose=True
)
best_individual_ga_small = list(hof[0])
best_features_ga_small = [
X_features[i] for i, val in enumerate(best_individual_ga_small) if val == 1
]
best_objective_ga_small = (
sm.OLS(y_ga, X_ga[['const'] + best_features_ga_small], hasconst=True)
.fit()
.bic
)
print(f'best objective: {best_objective_ga_small}')
print(f'best features: {best_features_ga_small}')
El código crea los objetos que definen a un individuo y a toda la población, junto con las estrategias utilizadas para la evaluación (función objetiva), cruce/apareamiento, mutación y selección. Comienza con una población de 300 individuos y luego llama eaSimple() (una secuencia enlatada de cruce, mutación, selección) que se ejecuta durante solo 10 generaciones, por simplicidad. Se define el Salón de la Fama con un tamaño de 1, donde el mejor individuo absoluto se preserva contra ser mutado/omitido accidentalmente durante la selección, etc.
Este código simple es fácil de entender, pero ineficiente. Revisa el cuaderno en el repositorio para una versión más compleja del código GA, que no voy a citar aquí. Sin embargo, ejecutar el código más complejo y optimizado desde el portátil durante 1000 generaciones produce estos resultados:
best objective: 33705.569572544795
best generation: 787
objective runs: 600525
time to best: 157.604 sec
Y aquí está la historia completa del código GA completo y optimizado del portátil, ejecutándose durante 1000 generaciones, intentando encontrar las mejores funciones. De izquierda a derecha, el mapa de calor indica la popularidad de cada característica dentro de la población a través de generaciones (tono más brillante = más popular). Puede ver cómo algunas funciones siempre son populares, otras se rechazan rápidamente y otras pueden volverse más o menos populares a medida que pasa el tiempo.