Отбор признаков с использованием генетических алгоритмов в R

Оригинал: Feature Selection using Genetic Algorithms in R

Что такое генетические алгоритмы?

Генетические алгоритмы (GA) - это математическая модель, вдохновленная известной идеей естественного отбора Чарльза Дарвина.

Естественный отбор сохраняет только наиболее приспособленных особей из разных поколений.

Представьте себе популяцию 100 кроликов в 1900 году, если мы посмотрим на популяцию сегодня, мы увидим других кроликов, более быстрых и умелых в поисках пищи, чем их предки.

GA в ML

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

Подобрать правильное подмножество переменных - задача комбинаторики и оптимизации.

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

Идея GA состоит в том, чтобы комбинировать различные решения поколение за поколением, чтобы извлечь лучшие гены (переменные) из каждого из них. Таким образом создаются новые и более подходящие сущности.

Мы можем найти другие варианты использования GA, такие как настройка гиперпараметров, поиск максимума (или минимума) функции или поиск правильной архитектуры нейронной сети (нейроэволюция).

GA в выборе признаков

Все возможные решения GA, которые представляют собой выбранные переменные (единственные), рассматриваются как единое целое, оно не будет ранжировать переменные по отдельности относительно цели.

И это важно, потому что мы уже знаем, что переменные работают в группе.

Как выглядит решение?

Чтобы упростить пример, представьте, что у нас есть всего 6 переменных. Одним из решений может быть выбор трех переменных, скажем: var2, var4 и var5. Другим решением может быть: var1 и var5.

Эти решения представляют собой так называемые индивидуумы или хромосомы в популяции. Это возможные решения нашей проблемы.

На изображении решение 3 можно представить в виде вектора: c (1,0,1,0,1,1). Каждая единица обозначает решение, содержащее эту переменную. В данном случае: var1, var3, var5, var6. Пока решение 4: c (1,1,0,1,1,0). Каждая позиция в векторе - это ген.

Процесс GA и его операторы

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

Эта комбинация следует за основными операциями GA, а именно: отбор, мутация и скрещивание.

• Отбор: подберите наиболее подходящих индивидуумов в поколении (то есть: решения, обеспечивающие наивысший ROC).
• Скрещивание: создайте 2 новых индивидуума на основе генов двух решений. Эти дети появятся в следующем поколении.
• Мутация: случайное изменение гена у человека (например: 0 на 1).

Идея в том, что для каждого поколения мы будем находить более качественных особей, как у кроликов.

Я рекомендую пост Vijini Mallawaarachchi о том, как работает генетический алгоритм.

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

Функция пригодности

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

Функция пригодности берет возможное решение (или хромосому, если вы хотите) и каким-то образом оценивает эффективность выбора.

Обычно функция пригодности принимает вектор c (1,1,0,0,0,0), создает, например, случайную модель леса с переменными var1 и var2 и возвращает значение пригодности (ROC).

Значение пригодности в этом коде рассчитывается следующим образом: значение ROC/количество переменных. Таким образом алгоритм штрафует решения с большим количеством переменных. Аналогично идее информационного критерия Акаике или AIC.

Генетические алгоритмы в R!

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

Чтобы использовать свой собственный набор данных, убедитесь, что data_x (data frame) и data_y (factor) совместимы с функцией custom_fitness.

Основная библиотека - GA, разработанная Лукой Скрукка. Смотрите здесь виньетку с примерами.

Важно: приведенный ниже код неполный. Клонируйте репозиторий, чтобы запустить пример.

# data_x: input data frame
# data_y: target variable (factor)# GA parameters
param_nBits=ncol(data_x)
col_names=colnames(data_x)# Executing the GA 
ga_GA_1 = ga(fitness = function(vars) custom_fitness(vars = vars, 
                                                     data_x =  data_x, 
                                                     data_y = data_y, 
                                                     p_sampling = 0.7), # custom fitness function
             type = "binary", # optimization data type
             crossover=gabin_uCrossover,  # cross-over method
             elitism = 3, # best N indiv. to pass to next iteration
             pmutation = 0.03, # mutation rate prob
             popSize = 50, # the number of indivduals/solutions
             nBits = param_nBits, # total number of variables
             names=col_names, # variable name
             run=5, # max iter without improvement (stopping criteria)
             maxiter = 50, # total runs or generations
             monitor=plot, # plot the result at each iteration
             keepBest = TRUE, # keep the best solution at the end
             parallel = T, # allow parallel procesing
             seed=84211 # for reproducibility purposes
)# Checking the results
summary(ga_GA_1)── Genetic Algorithm ─────────────────── GA settings: 
Type                  =  binary 
Population size       =  50 
Number of generations =  50 
Elitism               =  3 
Crossover probability =  0.8 
Mutation probability  =  0.03 GA results: 
Iterations             = 17 
Fitness function value = 0.2477393 
Solution = 
     radius_mean texture_mean perimeter_mean area_mean smoothness_mean compactness_mean
[1,]           0            1              0         0               0                1
     concavity_mean concave points_mean symmetry_mean fractal_dimension_mean  ... 
[1,]              0                   0             0                      0      
     symmetry_worst fractal_dimension_worst
[1,]              0                       0# Following line will return the variable names of the final and best solution
best_vars_ga=col_names[ga_GA_1@solution[1,]==1]# Checking the variables of the best solution...
best_vars_ga[1] "texture_mean"     "compactness_mean" "area_worst"       "concavity_worst"

Синие точки: средняя пригодность популяции.

Зеленые точки: лучшее значение пригодности.

Примечание: не ждите такого быстрого результата

Теперь рассчитаем точность на основе лучшего выбора!

get_accuracy_metric(data_tr_sample = data_x, target = data_y, best_vars_ga)[1] 0.9508279

Точность составляет около 95,08%, в то время как значение ROC близко к 0,95 (ROC = значение пригодности * количество переменных, проверьте функцию пригодности).

Анализ результатов

Я не люблю анализировать точность без точки отсечения (Scoring Data), но полезно сравнить с результатами, указанными в этой публикации на Kaggle.

Там автор получил аналогичный результат точности, используя рекурсивное исключение функций, или RFE, на основе 5 переменных, в то время как наше решение остается с 4 переменными.

Попробуйте далее сами

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

Некоторые конфигурации рассчитываются долго. Балансируйте классы перед моделированием и поиграйте с параметром p_sampling. Методы выборки могут иметь большое влияние на модели. Для получения дополнительной информации проверьте размер выборки и баланс классов в публикации об эффективности модели.

Как насчет изменения скорости мутаций или элитарности? Или пробовать другие перекрестные методы?

Увеличьте popSize, чтобы одновременно тестировать больше возможных решений (за определенную плату). Не стесняйтесь делиться любыми мыслями или идеями, чтобы улучшить выбор.

Клонируйте репозиторий, чтобы запустить пример.

Связанные концепции

Существует параллелизм между GA и Deep Learning, концепция итераций и улучшений во времени аналогична.

Я добавил параметр p_sampling, чтобы ускорить процесс. И обычно добавлся своей цели. Это подобно концепции пакетной обработки, используемой в Deep Learning. Другая параллель - между запуском параметра GA и критериями ранней остановки в обучении нейронной сети.

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