Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ВВЕДЕНИЕ В АНАЛИЗ ДАННЫХ
Посмотреть оригинал

В2.3. Вычисление

Если распределение признака записано в массиве df, то команда МатЛаба

» bar(df, .4);h=axis;axis(1.1 *h);

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

Энтропию и индекс Джини можно вычислить с помощью команд:

» df=df/sum(df); h=-sum(df .*log2(df)); % h энтропия;

» df=df/sum(df); g=-sum(df .*( 1-df)); % g индекс Джини.

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

Ответ. Совпадают.

Проект 2.1. Вычисление центра по критерию Минковского

Рассмотрим множество значений признака х-„ i = 1, 2,..., N, и положительную величину т > 1. Вычислим такое значение а, которое минимизирует критерий Минковского, т.е. сумму т-х степеней расстояний:

При т ф 2 не существует общего аналитического решения этой задачи. Есть несколько способов ее численного решения. Один из них — это использование итеративного метода приближения к точке (локального) минимума. Этот метод заключается в пошаговом перемещении в обратном градиенту направлении, как бы «спускаясь» по градиенту (отсюда название «метод градиентного спуска»). Альтернативный способ решить поставленную задачу — использовать алгоритм, инспирированный природой. В таких алгоритмах популяция допустимых решений итеративно эволюционирует, причем лучшие из найденных решений запоминаются в соответствии с теми или иными правилами поддержания элиты.

Рассмотрим два метода минимизации Lm:

  • (i) Итерационный градиентный спуск;
  • (п) Итерационный алгоритм, инспирированный природой.
  • (i) Градиентный спуск MC AG

Исследуем свойства критерия Lm из выражения (2.7). Для простоты примем, что т > 1. Упорядочим все N чисел из X в порядке возрастания, так что .г, < х2 < <... lV. Несложно доказать, что, во-первых, рассматриваемый критерий является выпуклой функцией (рис. 2.11) и, во-вторых, что оптимальное значение а находится между х, и xjV.

где /+ — это множество индексов г, для которых а > х{, и 1_ — множество индексов г, для которых а < х,. Производная Lm(a) из уравнения (2.8) равна

Допустим обратное, т.е. что минимум достигается вне заданного интервала, например, при а >xN. Но тогда Lm(xN) < Lm(a), потому что |х,- — xN < |х,- — адля любого i = = 1,2,..., N, и то же самое верно для т-х степеней модулей. Что касается выпуклости, рассмотрим любое а в интервале между х, и xv. Тогда критерий (2.7) имеет вид

а вторая производная:

Выпуклая функция от а

Рис. 2.11. Выпуклая функция от а

Последнее выражение положительно при любых значениях а, если т > 1. Как известно из математического анализа, дифференцируемая функция, у которой вторая производная положительна, является выпуклой. Следовательно, Lm(a) — выпуклая функция. Тогда минимум достигается вблизи точки я,-*, на которой достигается минимум на имеющихся наблюдениях, Ьт{) по всем i = 1,2, ..., N. Точнее, минимум Lm(a) принадлежит интервалу (х(> х”), где х- — то из чисел xit которое ближе всего к хг с левой стороны, т.е. с той, где Lm(xf-) < Lm(xr). Аналогично, х" - то из чисел xj} которое ближе всего к хг с правой стороны, где Lm(xt) > Lm(xr).

Перечисленные выше свойства позволяют сформулировать следующую версию алгоритма градиентного спуска при т > 1:

MCFD

  • 1. Инициализация: примем аО =х{* и зададимся какой-либо скоростью обучения X > 0.
  • 2. Вычислим разность аО - XLmf(aO) по формуле (2.9) и примем найденное значение за а, если оно попадает в интервал (х/, х"). В противном случае несколько уменьшим X, например на 10%, и повторим шаг уменьшения до тех пор, пока разность нс окажется в интервале (х/, х”).
  • 3. Проверим, совпадают ли а и «0 с точностью до заранее определенного порога. Если да, останавливаем процесс и возвращаем а в качестве оптимального значения а. Если нет, то продолжаем вычисления.
  • 4. Проверим условие Lm(a 1) < Lm(a0). Если оно верно, присвоим аО = а и L„,(a0) = Lm(a 1), и перейдем к шагу 2. Если нет, уменьшим X и перейдем к (2), не меняя аО.
  • (и) Метод MCNI, инспирированный природой

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

  • 1. Определение области допустимых решений. Определим область А, которой принадлежат допустимые решения, т.е. точки, среди которых находится оптимальное решение или несколько оптимальных решений. В данном случае это нетрудно сделать. Выше было доказано, что оптимум лежит между минимумом lb и максимумом rb выборки xv г = 1, 2,..., N. Следовательно, область допустимых решений — это интервал (lb, rb).
  • 2. Инициализация популяции. Зададим размер популяции ре. Пусть, например, ре = 15. Случайным образом выберем точки sv s2,spe из допустимой области (lb, rb).
  • 3. Инициализация элиты. Оценим значение критерия (2.7) для каждого из элементов популяции и запомним в переменной se налучший из них (элиту), т.е. ту из величин s*, на которой достигается минимум критерия.

4. Переход к новому поколению. Во-первых, добавим случайный Гауссовый шум г.

Во-вторых, если какое-то из значений выйдет за границы допустимой области А, вернем его обратно, на границу.

  • 5. Поддержка элиты. Найдем значения критерия для всех элементов нового поколения, выберем иаилучшее и наихудшее значения sb и sw, и сравним их с элитой se. Если sh лучше, чем se, запомним sh в se. Если sh и, тем более, sw хуже, чем se, заменим sw в текущей популяции на se.
  • 6. Условие остановки. Если число итераций не превышает заранее заданной величины, переходим к шагу 4. В противном случае выдаем элиту se как решение задачи.

Эксперименты показывают, что метод градиентного спуска в данной задаче работает быстрее, чем метод, инспирированный природой. Но первый метод работает только при т > 1, а второй — при любых значениях т.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы