Выбор признаков с помощью генетических алгоритмов (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 37: Строка 37:
В наборе не было следующих функций, участвовавших в порождении: sin( x ), ( x.^2 ).*sin( x ).
В наборе не было следующих функций, участвовавших в порождении: sin( x ), ( x.^2 ).*sin( x ).
[[Изображение:SSE( number of generations ) for varyingPopulationSize.png|1000px]]
[[Изображение:SSE( number of generations ) for varyingPopulationSize.png|1000px]]
-
[[Изображение:Number of Iterations(PopulationSize).png|600px]] <br />
+
[[Изображение:Number of Iterations(PopulationSize).png|800px]] <br />
[[Изображение:Least squares linear fit for varyingPopulationSize.png|1000px]] <br />
[[Изображение:Least squares linear fit for varyingPopulationSize.png|1000px]] <br />
[[Изображение:SSE( number of generations ) for varyingCrossoverFraction.png|1000px]]
[[Изображение:SSE( number of generations ) for varyingCrossoverFraction.png|1000px]]
-
[[Изображение:Number of Iterations(CrossoverFraction).png|600px]] <br />
+
[[Изображение:Number of Iterations(CrossoverFraction).png|800px]] <br />
[[Изображение:Least squares linear fit for varyingCrossoverFraction.png|1000px]] <br />
[[Изображение:Least squares linear fit for varyingCrossoverFraction.png|1000px]] <br />
Строка 49: Строка 49:
=== Результаты на реальных данных ===
=== Результаты на реальных данных ===
Использовался следующий набор порождающих функций ( всего 22 ): <br />
Использовался следующий набор порождающих функций ( всего 22 ): <br />
-
(x(:,1)).^0 (x(:,1)).^1 (x(:,1)).^2 (x(:,1)).^3 (x(:,1)).^4 (x(:,2)).^0 (x(:,2)).^1 (x(:,2)).^2 (x(:,2)).^3 (x(:,2)).^4 sin(x(:,1)) sin(x(:,2)) ((x(:,1)).^1).*((x(:,2)).^1) ((x(:,1)).^1).*((x(:,2)).^2) ((x(:,1)).^1).*((x(:,2)).^3) ((x(:,1)).^1).*((x(:,2)).^4) ((x(:,1)).^2).*((x(:,2)).^1) ((x(:,1)).^2).*((x(:,2)).^2) sin(x(:,1)).*((x(:,2)).^1) sin(x(:,1)).*((x(:,2)).^2) sin(x(:,2)).*((x(:,1)).^1) sin(x(:,2)).*((x(:,1)).^2)
+
(x(:,1)).^0 (x(:,1)).^1 (x(:,1)).^2 (x(:,1)).^3 (x(:,1)).^4 (x(:,2)).^0 (x(:,2)).^1 (x(:,2)).^2 (x(:,2)).^3 (x(:,2)).^4 sin(x(:,1)) sin(x(:,2)) ((x(:,1)).^1).*((x(:,2)).^1) ((x(:,1)).^1).*((x(:,2)).^2) ((x(:,1)).^1).*((x(:,2)).^3) ((x(:,1)).^1).*((x(:,2)).^4) ((x(:,1)).^2).*((x(:,2)).^1) ((x(:,1)).^2).*((x(:,2)).^2) sin(x(:,1)).*((x(:,2)).^1) sin(x(:,1)).*((x(:,2)).^2) sin(x(:,2)).*((x(:,1)).^1) sin(x(:,2)).*((x(:,1)).^2). <br />

Версия 21:28, 27 апреля 2010

Содержание

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

Постановка задачи

Задана выборка — множество \{x_1,...,x_n|x_i\in\mathbb{R}^M\} значений свободных переменных и множество \{y_1,...,y_n| y_i\in\mathbb{R}\} соответствующих им значений зависимой переменной. Задано множество порождающих функций линейной регрессионной модели \{\mathbf{f}_1,...,\mathbf{f}_N\}, где \mathbf{f}_i:\: \mathbb{R}^M \to \mathbb{R}. Введем обозначения:
c\in\{0,1\}^N, F(c) =\left(\begin{array}{ccc} \mathbf{f}_{i_1}(x_1) & \ldots & \mathbf{f}_{i_k}(x_1)\\ \mathbf{f}_{i_1}(x_2) & \ldots & \mathbf{f}_{i_k}(x_2)\\ \ldots & \ldots & \ldots \\ \mathbf{f}_{i_1}(x_n) & \ldots & \mathbf{f}_{i_k}(x_n)\\ \end{array} \right) , k = ||c||1, { ij }j=1k⊂{ 1,...,N } : c( ij )=1 при j=1,...,k;
\mathbf{w(c)} = (F(c)^TF(c))^{-1}F(c)^T\mathbf{y};
\mathbf{y(c)} = F(c)\mathbf{w(c)}.
Требуется решить следующую задачу:
SSE(c) = (\mathbf{y}-\mathbf{y(c)})^T(\mathbf{y}-\mathbf{y(c)}) \to min_c.

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

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

  1. Инициализация( создание начальной популяции необходимого размера ). Хромосомы особей представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: n=0.
  2. n:=n+1. Проверка условий завершения: либо n превысило максимально допустимое значение, либо изменения целевой функции SSE для лучшей особи в популяции за некоторое число итераций оказалось слишком малым.
  3. Селекция( выбор особей для следующего поколения ). Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
  4. Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. Оператор скрещивания ). В результате этой операции каждая аллель ( т. е. позиция в хромосоме особи ) случайным образом заполняется геном 1-ого или 2-ого родителя.
  5. Мутация. Для каждой особи в каждой аллели с вероятностью 0.01 происходит мутация, которая выражается в замене текущего гена на 0 или 1 случайным образом( равновероятно ).
  6. Возвращение на шаг 2.

Вычислительный эксперимент

Показана работа алгоритма на реальных и модельных данных.

Модельные данные

Данные порождались следующим образом: 

x = [ 1:0.5:20 ]';
y = x + x.^2 + sin( x ) + log( x ) + x.*log( x ) + ( x.^2 ).*sin( x ) + randn( size( x, 1 ), 1 );

Выборка делилась на training и testing части в соотношении 60%:40% случайным образом. Исследовались 2 эффекта: ложная ( ранняя ) сходимость и переобучение.

Результаты на модельных данных

Использовался следующий набор порождающих функций ( всего 13 ):
x.^0 x x.^2 log(x) x.^3 x.*log(x) x.^4 (x.^2).*log(x) (x.^2).*cos(x) cos(x).*log(x) x.^3 (x.*sin(x)).*log(x) ((x.^2).*cos(x)).*log(x).
В наборе не было следующих функций, участвовавших в порождении: sin( x ), ( x.^2 ).*sin( x ).



Выводы

Реальные данные

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

Результаты на реальных данных

Использовался следующий набор порождающих функций ( всего 22 ):
(x(:,1)).^0 (x(:,1)).^1 (x(:,1)).^2 (x(:,1)).^3 (x(:,1)).^4 (x(:,2)).^0 (x(:,2)).^1 (x(:,2)).^2 (x(:,2)).^3 (x(:,2)).^4 sin(x(:,1)) sin(x(:,2)) ((x(:,1)).^1).*((x(:,2)).^1) ((x(:,1)).^1).*((x(:,2)).^2) ((x(:,1)).^1).*((x(:,2)).^3) ((x(:,1)).^1).*((x(:,2)).^4) ((x(:,1)).^2).*((x(:,2)).^1) ((x(:,1)).^2).*((x(:,2)).^2) sin(x(:,1)).*((x(:,2)).^1) sin(x(:,1)).*((x(:,2)).^2) sin(x(:,2)).*((x(:,1)).^1) sin(x(:,2)).*((x(:,1)).^2).


Исходный код

Скачать листинги алгоритмов можно здесь: createArtificialData1D.m, testGaEffeciency.m, gaEffeciency.m, evalSSE.m, plotRes.m, plotRegression.m,

Смотри также

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D0%B1%D0%BE%D1%80_%D0%BF%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%B3%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты