Оптимизация выбора признаков с помощью генетических алгоритмов

Оптимизация выбора признаков с помощью генетических алгоритмов — простой в использовании скрипт Python

Введение

В Just Eat Takeaway.com улучшение наших моделей, основанных на данных, является частью нашей ДНК. Рекомендательные системы являются важной частью нашей связи с нашими пользователями. Чтобы сделать возможной лучшую рекомендацию ресторана, был определен длинный список функций, которые используются для предоставления предложений через горизонтальную карусель. Эти функции определяют, какой контент будет отображаться в карусели. Например, можно предложить рестораны для завтрака (см. изображение ниже) утром или кофейни днем.

В мире науки о данных функции могут расти экспоненциально с течением времени, вызывая то, что мы называем «взрывом функций». Среди них есть унаследованные или специфичные для рынка функции, а некоторые могут демонстрировать высокую степень корреляции друг с другом. Каждая функция привязана к определенному конвейеру данных, что усложняет и увеличивает стоимость обслуживания системы. Поэтому важно периодически просматривать и оценивать, какие функции стоит сохранить. Уменьшение количества функций также может привести к повышению производительности модели.

Вот в чем проблема: представьте, что у вас есть 100 функций, и вы хотите сократить их, скажем, до 30 функций. Используя приведенную ниже формулу комбинации:

import math

# Calculating the possible combinations nCr
n = 100 # total number of objects in the set
r = 30 # number of choosing objects from the set
nCr = math.factorial(n) / (math.factorial(r) * math.factorial(n - r))
print(f"The total possible combinations without repetitions is: {nCr}")

Всего 2,94e+25 возможных комбинаций! Если вы хотите обучить своего рекомендателя и протестировать такое количество комбинаций, это займет у вас довольно много времени. Вот где методы оптимизации могут помочь машинному обучению.

Существуют различные методы уменьшения количества функций, используемых в модели. Один подход включает анализ индивидуального вклада каждой функции с помощью таких методов, как значения Шепли, которые возникли из теории игр. Однако в тех случаях, когда признаки сильно коррелированы, опора исключительно на значения Шепли может не раскрыть всей истории. В таких случаях можно использовать генетические алгоритмы для изучения взаимодействий между признаками, что приводит к более всестороннему анализу. Эти методы предлагают строгий и систематический подход к сокращению признаков в науке о данных.

Описание алгоритма

Генетические алгоритмы — это класс алгоритмов оптимизации, вдохновленных принципами естественного отбора и генетики. Они используются для решения сложных задач, которые трудно решить с помощью традиционных методов оптимизации. Генетические алгоритмы имитируют процесс естественного отбора, когда наиболее приспособленные особи в популяции выживают и размножаются, передавая свои гены следующему поколению.

В генетическом алгоритме задача представляется как совокупность потенциальных решений, где каждое решение называется отдельным. Эти люди оцениваются с использованием функции пригодности, которая измеряет их способность решить проблему. Люди с более высокой приспособленностью отбираются в качестве родителей следующего поколения, и их генетический материал объединяется для создания потомства, которое наследует черты своих родителей. Этот процесс повторяется для нескольких поколений, пока не будет найдено удовлетворительное решение.

Одним из основных преимуществ генетических алгоритмов является их способность находить глобальные оптимумы, в отличие от других методов оптимизации, которые могут застрять в локальных оптимумах. Однако генетические алгоритмы могут быть дорогостоящими в вычислительном отношении и требуют тщательной настройки параметров для получения хороших результатов.

В статье будет представлен простой в реализации и воспроизводимый сценарий Python, который не использует реальные данные клиентов, чтобы продемонстрировать, как работают генетические алгоритмы, и дать возможность читателям быстро создавать свои собственные генетические алгоритмы.

Генетический алгоритм

Перейдем к техническим компонентам. Ниже вы можете увидеть блок-схему, которой будет следовать наш генетический алгоритм:

Начинать

Здесь вы должны импортировать библиотеки, которые будут использоваться, и подготовить список функций. Для простоты будет создано 100 функций с именами feature_0, feature_1 и т. д.:

from typing import List
import pandas as pd
import numpy as np
import random

# Generate a list of 100 features
n_total_features = 100
list_total_features = [f"feature_{i}" for i in range(0, n_total_features)]

Начальная популяция

Вторым шагом является создание начальной популяции. Популяция – это совокупность особей. Индивидуум в этом контексте представляет собой список характеристик, подлежащих оценке. Начальная популяция имеет размер num_individuals, а каждый индивидуум имеет размер num_features.

def create_population(list_total_features: List[str], num_features: int, 
                      num_individuals: int) -> List[List[str]]:

  initial_population = []
  for _ in range(num_individuals):

        # Generating a string of random numbers between 0 and 
        # the lenght of the possible features to generate
        # random individuals

        test_features_list_id = random.sample(range(0, len(list_total_features)), num_features) 
        initial_population.append([list_total_features[feature_id] for feature_id in test_features_list_id])
    
  return initial_population

Оценка

После создания начальной популяции следующим шагом является оценка приспособленности особей. Здесь он должен быть специфичным для бизнеса. Предположим, что мы используем показатель площади под кривой рабочих характеристик приема (или AUC) для оценки нашей модели.

AUC — это значение от 0 до 1, где 0 означает, что все прогнозы модели неверны, 1 означает, что все прогнозы модели верны. Известно, что оценка AUC 0,5 — это оценка, которую вы получили бы, если бы ваша модель делала случайные прогнозы.

Поскольку идея состоит в том, чтобы дать вам код, который вы можете легко воспроизвести, и поскольку мы не используем конкретную базу данных, предоставляется код, который присваивает случайное значение пригодности от 0,4 до 0,9. Каждому человеку также дается идентификатор, чтобы отслеживать всех существующих людей. Это следует заменить вашей собственной моделью машинного обучения. Для набора функций вы будете обучать и оценивать модель и получать желаемую метрику (в нашем случае AUC). Для простоты:

def population_evaluation(initial_population: List[List[str]], 
                          ID_counter) -> pd.DataFrame:

    # General counter to keep track of every individual trained and evaluated
    c = ID_counter
    individuals_list = []

    for individual in initial_population:

      random_performance_metric = random.uniform(0.4, 0.9)
      individuals_list.append([c, random_performance_metric, individual])
      c = c + 1

    column_names = ["ID", "Fitness", 'Features']

    return pd.DataFrame(individuals_list, columns=column_names)

Выбор

До сих пор вы создавали случайную начальную популяцию, обучали и оценивали эту случайную популяцию, отслеживая каждого человека, набор функций и его приспособленность. Теперь начинается забавная часть генетического алгоритма: выбор набора особей для размножения.

Основополагающим принципом генетических алгоритмов является концепция воспроизводства. Люди с высокой приспособленностью будут воспроизводить потомство с высокой приспособленностью. В этом случае мы рассматриваем признаки, которые мы выбираем, как хромосомы. Эти функции случайным образом передаются их дочерним элементам в алгоритме либо от родителя A, либо от родителя B. Этот принцип воспроизведения можно использовать в наших интересах в моделях машинного обучения. В модели люди (т. е. наборы признаков), получившие высокие оценки, скорее всего, передадут эти высокие оценки своим потомкам, которые унаследуют часть их пригодности. Однако важно отметить, что это не всегда так. Иногда люди с высокой приспособленностью могут производить потомство с более низкой приспособленностью или наоборот. Несмотря на эту изменчивость, генетические алгоритмы по-прежнему могут быть мощным инструментом машинного обучения. Используя принцип воспроизведения, мы можем повторять многие поколения алгоритма, и каждое поколение становится лучше в решении проблемы. Со временем алгоритм сойдется к решению, которое оптимизирует целевую функцию задачи.

Имейте в виду, что это проблема оптимизации, а не точная копия эволюции. Мы по-прежнему пытаемся найти оптимальное решение, максимально ограничивая вычисления. Это означает, что мы будем отбирать особей, которые будут размножаться и создавать детей. Для этого существуют разные методы. Выбор ранга, например, состоит из сортировки людей по их пригодности и разрешения воспроизводить только людей с самым высоким рейтингом. Это, однако, может привести к быстрой сходимости к локальным оптимумам. В приведенном ниже примере был предложен метод выбора колеса рулетки. Отбор на колесе рулетки — это процесс, который позволяет выбрать наиболее подходящих людей, но не гарантирует этого.

Общая приспособленность населения распределяется по приспособленности каждого человека, и создается колесо рулетки, как показано на изображении ниже. При каждом вращении колеса рулетки выбирается один человек, и веса рулетки пересчитываются. Это дает всем особям возможность размножения, с большей вероятностью для более приспособленных особей и с меньшей вероятностью для менее приспособленных особей, что может способствовать разнообразию популяции и дает больше шансов найти оптимальное решение.

Вот код для этого:

def population_selection(evaluated_individuals_df: pd.DataFrame,
                         n_individuals_to_select: int) -> pd.DataFrame:

    return np.random.choice(evaluated_individuals_df['ID'], n_individuals_to_select, replace=False,
                            p=evaluated_individuals_df['Fitness'] / evaluated_individuals_df['Fitness'].sum())

Воспроизведение

Следующим шагом является создание детей. Воспроизведение осуществляется методом кроссовера. Есть разные способы сделать это, но здесь мы используем пересечение в середине каждого человека. Предполагая следующих двух родителей, где каждый блок является хромосомой (т. Е. Признаком):

Два потомка будут созданы следующим образом:

Существует вероятность того, что когда два родителя создают детей, некоторые хромосомы становятся общими и передаются детям в виде дубликатов. Если это так, дублированные хромосомы будут заменены новой случайной хромосомой (признак). Этот процесс известен как мутация. Этот процесс будет повторяться до тех пор, пока не исчезнут все дублированные хромосомы.

При разработке генетических алгоритмов мутация часто является явной частью процесса и предназначена для добавления разнообразия в популяцию. Существуют и другие методы, которые могут увеличить разнообразие, такие как «судный день», который заключается в случайном исключении некоторых особей и добавлении новых через несколько поколений. Здесь это не рассматривалось, но может быть интересно изучить этот и другие интересные способы улучшения генетических алгоритмов.

def population_reproduction(selected_ind_list: pd.DataFrame, 
                            list_total_features: List[str], num_features: int) -> List[List[str]]:

    def features_agg_fn(rows):
        half = len(rows.iloc[0]) // 2
        return np.unique(rows.iloc[0][:half] + rows.iloc[1][half:]), np.unique(
            rows.iloc[1][:half] + rows.iloc[0][half:])

    children = selected_ind_list.groupby(selected_ind_list.index // 2).agg({'Features': features_agg_fn}).Features.explode()

    children = children.reset_index(drop=True)
    updated_children = []

    for child in children:
        child = child.tolist()

        while len(child) < num_features:
            child = child + [random.choice(list_total_features)]
            child = np.unique(child).tolist()

        updated_children.append(child)

    return updated_children

Новые случайные люди

Чтобы увеличить разнообразие в нашем алгоритме, рядом с ранее созданными дочерними элементами создается количество num_new_individuals случайных индивидуумов.

Алгоритм останавливается, как только достигается заданное общее количество поколений. В конце концов, самый приспособленный из когда-либо созданных индивидуумов считается (суб)оптимальным решением. Для этого шага можно повторно использовать функцию create_population.

Полный процесс

Ниже вы можете найти полный процесс и все функции вместе взятые.

# GA parameters
num_features = 10
num_individuals = 100
n_individuals_to_select = 40
num_new_individuals = 10
id_start = 1
num_generations = 10
penalization = True

total_list_individuals = pd.DataFrame()

# Initial population
population = create_population(list_total_features, num_features, num_individuals)

for i in range(num_generations):

  evaluated_individuals_df = population_evaluation(population, id_start)
  id_start = id_start + len(population)
  total_list_individuals = total_list_individuals.append(evaluated_individuals_df, ignore_index=True)

  selected_individuals_list = population_selection(evaluated_individuals_df, n_individuals_to_select)

  children_list = population_reproduction(selected_individuals_list, list_total_features, num_features)

  new_random_individuals = create_population(list_total_features, num_features, num_new_individuals)
  population = new_random_individuals + children_list

print(f"The most fitted individual has an AUC score of: {max(total_list_individuals['Fitness']):.2f}.")

Заключение

Вот и все! Вы реализовали полный генетический алгоритм, используя выбор колеса рулетки. Окончательное решение, оптимальное или субоптимальное, будет зависеть от сложности вашей задачи, вычислительных возможностей, количества реализуемых вами индивидуумов и поколений и общего количества возможных комбинаций. Успех генетических алгоритмов также зависит от того, насколько хорошо проблема может быть представлена как проблема генетической оптимизации, поскольку наследование пригодности не всегда гарантируется во всех задачах. Для нас на Just Eat Takeaway.com удалось найти сокращенный набор функций, которые имели такую же пригодность, что и полный набор функций, даже имея 2,94e + 25 возможных комбинаций!

Особая благодарность Максу Ноббауту за его вклад в эту статью!

Just Eat Takeaway.com набирает сотрудников! Хотите пойти работать с нами? Подать заявку сегодня.

Оптимизация выбора признаков с помощью генетических алгоритмов — простой в использовании скрипт Python!