На пути к интеллектуальным биоиндикационным системам icon

На пути к интеллектуальным биоиндикационным системам


Смотрите также:
I  Международная молодежная конференция по интеллектуальным технологиям и системам...
Международный конгресс по интеллектуальным системам и информационным технологиям...
Проект «образование»...
Программа развития Южного Федерального Университета на 2007-2010 годы...
Для студентов, преподавателей, аспирантов экономических вузов...
Международный конгресс по интеллектуальным системам и информационным технологиям...
Интеграция платформы электронного обучения и системы трансляции видеоконференций gwots streaming...
Дни ступень первая курс «Специалист по Системам менеджмента информационной безопасности»...
Отчет по поводу заседания рабочей группы по экспертным системам в медицине...
27-29 июля 2012г столица солнечной Аджарии, г...
Xiii санкт-петербургская международная конференция по интегрированным навигационным системам 29...
Впомощь библиотекам и библиотечным системам (Информационный список литературы по основным...



Загрузка...
страницы:   1   2   3   4
скачать
Глава 9. На пути к интеллектуальным

биоиндикационным системам


9.1. Классификация наблюдений с использованием

иерархических деревьев решений


Формулировка задачи

Пусть в таблице произвольных гидробиологических наблюдений X размерностью m >1 один из признаков, измеренный в порядковой шкале, определяет класс объекта и может принимать значения из некоторого фиксированного набора {у1, у2, …, yk, …, yp}. Необходимо на основе обучающей выборки сформировать дерево классификации (дерево решений), содержащее совокупность логических условий, позволяющих для произвольного измерения х из Х указать класс качества yk , к которому оно может принадлежать.

Еще в XVII столетии великий ученый Готфрид Лейбниц ("Новые опыты о человеческом разуме", 1704 г.) пытался раскрыть тайну "^ Всеобщего Искусства Открытия". Он утверждал, что одной из двух частей этого искусства является комбинаторика – перебор постепенно усложняющихся комбинаций исходных данных. Второй частью является эвристика – свойство догадки человека. На языке нашего времени эта часть соответствует модели мышления человека, включающей в себя процессы генерации эвристик (догадок, изобретений, открытий).

Универсальным методом поиска решений является метод полного перебора 1 и, обладай мы бесконечным запасом времени и ресурсов, то можно найти решение любой задачи. Здесь имеется в виду не конструирование нового знания, а, прежде всего, "выбор" наиболее правдоподобных вариантов. Можно отметить другой универсальный метод ускорения полного перебора — быстрое отсечение ложных (или вероятно ложных) ветвей перебора на основе использования алгебр логики.

Простейшие (одномерные) логические правила типа "если A, то В" мы рассматривали в разделе 6.4, когда описывали детерминационный анализ. Более широкие возможности предоставляют системы анализа на основе деревьев решений (Tree Analyzer), которые позволяют свести исходную матрицу данных X к набору простых правил, представленных в виде иерархической структуры – дерева. Этот метод моделирования сочетает мощный аналитический аппарат генерации решений с простотой использования технологии и интуитивно понятными конечными результатами.

Рекомендуемая литература: [Breiman et al., 1984; Коршунов, 1995; Loh, Shih, 1997; Деревья классификации.., URL]. Интересные методические материалы и Интернет-конференция по теме находятся также на сайте лаборатории BaseGroup Labs – http://www.basegroup.ru/labs.


Математический лист

Деревья решений – один из методов автоматического анализа данных, основные идеи которого восходят к работам П. Ховленда (Р. Hoveland) и Е. Ханта (Е. Hunt) конца 50-х годов XX в. Их итогом явилась основополагающая монография [Hunt et al., 1966], давшая импульс развитию этого направления.

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

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

Есть целый ряд причин, делающих деревья классификации более гибким средством, чем традиционные методы анализа:

  • схема одномерного ветвления, которая позволяет изучать эффект влияния отдельных предикторных переменных и проводить последовательный анализ их вклада;

  • возможность одновременно работать с переменными различных типов, измеренных в непрерывных и порядковых шкалах, либо осуществлять любое монотонное преобразование признаков;

  • отсутствие предварительных предположений о законах распределения данных.

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

  • ^ Описание данных: деревья решений позволяют хранить информацию о данных в компактной форме, т.е. вместо обширных таблиц данных мы можем хранить дерево решений, которое содержит в концентрированной форме точное описание объектов;

  • Классификация: деревья решений отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов; при этом целевая переменная должна быть измерена в порядковой шкале;

  • Регрессия: если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых (входных) переменных. Например, к этому классу относятся задачи численного прогнозирования (предсказания значений целевой переменной).

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

  • CART (Classification and Regression Tree), разработанный Л. Брейманом с соавторами [Breiman et al., 1984], представляет собой алгоритм построения бинарного дерева решений – дихотомической классификационной модели; каждый узел дерева при разбиении имеет только двух потомков; как видно из его названия, алгоритм решает задачи как классификации, так и регрессии;

  • C4.5 – алгоритм построения дерева решений с неограниченным количеством потомков у узла, разработанный Р. Куинленом [Quinlan, 1993]; не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации;

  • QUEST (Quick, Unbiased, Efficient Statistical Trees) – программа, разработанная В. Ло и И. Ши [Loh, Shih, 1997], в которой используются улучшенные варианты метода рекурсивного квадратичного дискриминантного анализа, позволяющие реализовать многомерное ветвление по линейным комбинациям порядковых предикторов; содержит ряд новых средств для повышения надежности и эффективности индуцируемых деревьев классификации.

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

Пусть в некотором узле дерева сконцентрировано некоторое множество примеров Х*, Х*Х. Тогда существуют три возможные ситуации.

  1. Множество Х* содержит один или более примеров, относящихся к одному классу yk. Тогда дерево решений для Х* – это "лист", определяющий класс yk .

  2. ·Множество Х* не содержит ни одного примера, т.е. представляет пустое множество. Тогда это снова "лист", и класс, ассоциированный с "листом", выбирается из другого множества, отличного от Х* (скажем, из множества, ассоциированного с родителем).

  3. Множество Х* содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество Х* на некоторые подмножества. Для этого выбирается один из признаков j, имеющий два и более отличных друг от друга значений и Х* разбивается на новые подмножества, где каждое подмножество содержит все примеры, имеющие определенный диапазон значений выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока любое подмножество Х* не будет состоять из примеров, относящихся к одному и тому же классу.

Описанная процедура построения дерева решений сверху вниз, называемая схемой "разделения и захвата" (divide and conquer), лежит в основе многих современных методов построения деревьев решений. Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction).

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

  • какой принять вид критерия для селекции признака, по которому пойдет разбиение;

  • как выбрать момент, когда следует прекратить дальнейшие ветвления;

  • каков механизм отсечения ветвей.


Правило разбиения: каким образом следует выбрать признак?

Для построения дерева c одномерным ветвлением, находясь на каждом внутреннем узле, необходимо найти такое условие проверки, связанное с одной из переменных j, которое бы разбивало множество, ассоциированное с этим узлом на подмножества. Общее правило для выбора опорного признака можно сформулировать следующим образом: «выбранный признак должен разбить множество Х* так, чтобы получаемые в итоге подмножества Х*k , k = 1, 2, …, p, состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. количество чужеродных объектов из других классов в каждом из этих множеств было как можно меньше».

Были разработаны различные критерии, например, теоретико-информационный критерий, предложенный Р. Куинленом:

, (9.1)

где H(Х*) и H(Х*k ) – энтропия подмножеств, разбитых на классы, рассчитанная по формуле Шеннона.

Алгоритм CART использует, так называемый, индекс Джини (в честь итальянского экономиста Corrado Gini), который оценивает "расстояние" между распределениями классов

, (9.2)

где c – текущий узел, а pj – вероятность класса j в узле c.

Большинство из известных алгоритмов являются "жадными алгоритмами": если один раз был выбран атрибут и по нему произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. И поэтому на этапе построения дерева нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение.

Правило остановки: разбивать дальше узел или отметить его как лист?

В дополнение к основному методу построения деревьев решений были предложены следующие правила:

  • использование статистических методов для оценки целесообразности дальнейшего разбиения или так называемой "ранней остановки" (prepruning); в конечном счете, "ранняя остановка" процесса построения привлекательна в плане экономии времени обучения, но здесь уместно сделать одно важное предостережение: этот подход строит менее точные классификационные модели и поэтому ранняя остановка крайне нежелательна – признанные авторитеты в этой области Л. Брейман и Р. Куинлен советуют буквально следующее: «Вместо остановки используйте отсечение».

  • ограничение глубины дерева; можно остановить дальнейшее построение, если разбиение ведет к дереву с глубиной превышающей заданное значение;

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

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

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

Очень часто алгоритмы построения деревьев решений дают сложные деревья, которые имеют много узлов и ветвей. Такие "ветвистые" деревья очень трудно понять, а ценность правила, справедливого скажем для 1-3 объектов, крайне низка и в целях анализа данных практически непригодно. Гораздо предпочтительнее иметь дерево, состоящее из малого количества узлов, не вполне идеально классифицирующее обучающую выборку, но обладающее способностью столь же хорошо прогнозировать результат для тестовой выборки.

К сожалению, достаточно непросто конкретно определить, что же такое дерево классификации "подходящего размера", кроме общего тезиса о том, что оно должно уметь использовать ту информацию, которая улучшает точность прогноза, и игнорировать ту информацию, которая прогноза не улучшает. Для решения вышеописанной проблемы часто применяется так называемое "отсечение ветвей" (pruning), которое происходит снизу вверх, двигаясь с листьев дерева, отмечая узлы как листья, либо заменяя их поддеревом. Если под точностью дерева решений понимается отношение правильно классифицированных объектов, то нужно отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки.


Классификация новых примеров

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


Результаты расчетов

Сформируем обучающую выборку, состоящую из 117 наблюдений, признаками которой являются значения индексов Вудивисса, Шеннона, Пареле, Балушкиной, а также число видов в пробе, средние значения численности и биомассы, концентрация минерального фосфора и тип водоема (значения от 1 до 5 в зависимости от ширины русла и скорости течения). В качестве целевой переменной будем использовать класс качества вод от 2 до 6.

Получим два дерева решений: "компактное" дерево с использованием жестких процедур отсечения ветвей и упрощения правил и "полное" дерево, где единственным условием было концентрация в одном узле не менее 2 примеров обучающей выборки. "Компактное" дерево, представленное на рис. 9.1, состоит только из 8 узлов, в основе логических правил которых лежит всего 3 исходных признаков из 9.




Рис. 9.1. Дерево решений, построенное для классификации качества вод с использованием

процедур отсечения ветвей и упрощения.

В частности, двигаясь от корня, мы, вместе с 7 измерениями попадаем в узел B, если индекс Вудивисса больше 6.75, либо, в противном случае, с остальными измерениями поступаем в узел А. Из узла B, используя дополнительное условие по типу водоема, осуществляется переход на два листа C и D. Двигаясь же по основной ветви от узла А мы, в конце концов, приходим к узлу G, где сосредотачиваются все плохо распознаваемые примеры в количестве 63 измерений. Всем этим объектам присваивается класс 4, причем в 44 случаях это было выполнено ошибочно. Таким образом, исполнив свою объясняющую роль интерпретации существенных факторов, "компактное" дерево показало посредственные результаты в прогнозировании (38.4% ошибок).

Полное дерево, построенное без применения излишне жестких мер по обрезанию ветвей, использует все 9 предикторных переменных и гораздо сложнее в интерпретации, поскольку состоит из 54 узлов, из которых 28 являются "листьями" (см. табл. 9.1). Однако громоздкость сформированных правил компенсируется великолепными интерполяционными свойствами: на обучающей выборке зафиксировано только 9 ошибок классификации, что составляет 7.6%.


^ 9.2. Генетический алгоритм селекции информативных переменных


Формулировка задачи

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

Важным условием применения любых статистических методов является объективно существующая связь между известными входными значениями и неизвестным откликом. Эта связь может носить случайный характер, искажена шумом, но она должна существовать. Известный афоризм «garbage in, garbage out» («мусор на входе – мусор на выходе») нигде не справедлив в такой степени, как при использовании методов самоорганизации и нейросетевого моделирования. Это объясняется, во-первых, тем, что итерационные алгоритмы направленного перебора комбинаций параметров нейросети оказываются весьма эффективными и очень быстрыми лишь при хорошем качестве исходных данных. Однако, если это условие не соблюдается, число итераций быстро растет и вычислительная сложность оказывается сопоставимой с экспоненциальной сложностью алгоритмов полного перебора возможных состояний. Во-вторых, сеть склонна обучаться, прежде всего, тому, чему проще всего обучиться, а, в условиях сильной неопределенности и зашумленности признаков, это – прежде всего артефакты и явления "ложной корреляции".

Отбор информативных переменных в традиционной регрессии и таксономии осуществляют путем "взвешивания" признаков с использованием различных статистических критериев. Так в главе 8 нами были описаны пошаговые процедуры, основанные, в той или иной форме, на анализе коэффициентов частных корреляций или ковариаций. Однако трудность проблемы формирования наиболее информативного подмножества признаков обусловлена тем, что после отбрасывания одного признака соотношение значимостей остальных анализируемых переменных в общем случае изменяется. Прямой путь решения этой задачи заключается в полном переборе всех Сmm-p сочетаний переменных, что требует гигантского объема вычислений. Поэтому для этих целей используют различные секвенциальные (последовательные) процедуры, не всегда приводящие к результату, достаточно близкому к оптимальному. Элегантный автоматизированный подход к выбору значимых входных переменных может быть реализован с использованием генетического алгоритма, который можно считать "интеллектуальной" формой метода проб и ошибок.

Рекомендуемая литература: [Goldberg, 1989; Скурихин, 1995; Васильев, Ильясов, 1999].


Таблица 9.1

Дерево решений, построенное для классификации качества вод без использования

процедур отсечения ветвей и упрощения

(условные обозначения в шапке: ^ M – количество примеров обучающей выборки,

ассоциированных с узлом, f – число ошибок, k – лист класса качества вод)

Правило узла

M

f

k

if Инд_Вудивисса <= 6.5 then

110







| if Инд_Вудивисса <= 6.25 then

108







| | if Инд_Вудивисса <= 0.75 then Класс 3

2

0

3

| | if Инд_Вудивисса > 0.75 then

106







| | | if Инд_Пареле <= 0.96 then

105







| | | | if P_мин <= 0.346 then

103







| | | | | if Инд_Балушкиной <= 0.165 then Класс 4

2

1

4

| | | | | if Инд_Балушкиной > 0.165 then

101







| | | | | | if Инд_Вудивисса <= 1.5 then

8







| | | | | | | if P_мин <= 0.0905 then Класс 5

6

0

5

| | | | | | | if P_мин > 0.0905 then Класс 4

2

0

4

| | | | | | if Инд_Вудивисса > 1.5 then

93







| | | | | | | if Инд_Шеннона <= 1.075 then Класс 3

2

0

3

| | | | | | | if Инд_Шеннона > 1.075 then

91







| | | | | | | | if P_мин <= 0.0075 then Класс 4

5

1

4

| | | | | | | | if P_мин > 0.0075 then

86







| | | | | | | | | if Инд_Шеннона <= 1.52 then

8







| | | | | | | | | | if Тип <= 3.5 then Класс 2

2

1

2

| | | | | | | | | | if Тип > 3.5 then Класс 4

6

0

4

| | | | | | | | | if Инд_Шеннона > 1.52 then

78







| | | | | | | | | | if Инд_Балушкиной <= 6.43 then

41







| | | | | | | | | | | if N_видов <= 6.5 then

6







| | | | | | | | | | | | if P_мин <= 0.1335 then Класс 3

4

0

3

| | | | | | | | | | | | if P_мин > 0.1335 then Класс 4

2

1

4

| | | | | | | | | | | if N_видов > 6.5 then

35







| | | | | | | | | | | | if Инд_Вудивисса <= 4.75 then

27







| | | | | | | | | | | | | if Ср_Биомасса <= 171.305 then Класс 4

23

0

4

| | | | | | | | | | | | | if Ср_Биомасса > 171.305 then

4







| | | | | | | | | | | | | | if P_мин <= 0.0915 then Класс 4

2

0

4

| | | | | | | | | | | | | | if P_мин > 0.0915 then Класс 3

2

0

3

| | | | | | | | | | | | if Инд_Вудивисса > 4.75 then

8







| | | | | | | | | | | | | if Ср_Численность <= 2590 then Класс 3

5

0

3

| | | | | | | | | | | | | if Ср_Численность > 2590 then Класс 4

3

0

4

| | | | | | | | | | if Инд_Балушкиной > 6.43 then

37







| | | | | | | | | | | if Ср_Биомасса <= 225.245 then

34







| | | | | | | | | | | | if Тип <= 5 then

30







| | | | | | | | | | | | | if Инд_Пареле <= 0.625 then

19







| | | | | | | | | | | | | | if Ср_Численность <= 5380 then Класс 4

15

1

4

| | | | | | | | | | | | | | if Ср_Численность > 5380 then

4

0




| | | | | | | | | | | | | | | if Тип <= 2 then Класс 4

2




4

| | | | | | | | | | | | | | | if Тип > 2 then Класс 5

2

1

5

| | | | | | | | | | | | | if Инд_Пареле > 0.625 then

11







| | | | | | | | | | | | | | if Тип <= 3.5 then Класс 5

8

0

5

| | | | | | | | | | | | | | if Тип > 3.5 then Класс 4

3

0

4

| | | | | | | | | | | | if Тип > 5 then

4







| | | | | | | | | | | | | if P_мин <= 0.074 then Класс 5

3

0

5

| | | | | | | | | | | | | if P_мин > 0.074 then Класс 3

1

0

3

| | | | | | | | | | | if Ср_Биомасса > 225.245 then Класс 3

3

1

3

| | | | if P_мин > 0.346 then Класс 4

2

1

4

| | | if Инд_Пареле > 0.96 then Класс 5

1

0

5

| if Инд_Вудивисса > 6.25 then Класс 2

2

1

2

if Инд_Вудивисса > 6.5 then

7







| if Тип <= 4 then Класс 2

6




2

| if Тип > 4 then Класс 3

1




3



^ Математический лист

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

Принципы эволюционной теории, заложенные Чарльзом Дарвиным в работе "Происхождение видов", сводятся к двум основным выводам:

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

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

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

Генетический алгоритм был разработан Дж. Холландом (J. Holland) в 1975 г. в Мичиганском университете. В дальнейшем Д. Голдберг (D. Goldberg) выдвинул ряд гипотез и теорий, помогающих глубже понять природу эволюции, а К. ДеДжонг (C. DeJong) предложил оптимальный вариант подбора параметров алгоритма для повышения общей эффективности работы.

Канонический генетический алгоритм характеризуется следующими особенностями.

  1. Задается функция оптимальности , определяющая эффективность каждой найденной комбинации признаков. Формируемое решение кодируется как вектор х, который называется "хромосомой" и соответствует битовой маске, т.е. двоичному представлению набора исходных переменных. В хромосоме выделяются части вектора – "гены", изменяющие свои значения в определенных позициях – "аллелях".

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

  3. Каждая хромосома xi, i = 1,..., в популяции декодируется в форму, необходимую для последующей оценки, и ей присваивается значение эффективности (xi) в соответствии с вычисленной функцией оптимальности. Кроме того, каждой хромосоме присваивается вероятность воспроизведения P(xi), i = 1,...,, которая зависит от эффективности данной хромосомы. Существуют различные схемы отбора, самая популярная из них – пропорциональный отбор:

. (9.3)

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

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

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

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



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

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



Мутация нужна для расширения пространства поиска ("эволюционное исследование") и предотвращения невосстановимой потери бит в аллелях.

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

Для исследования эффективности генетических алгоритмов используется понятие «шаблона». Шаблоны представляют собой гиперплоскости различной размерности в l-мерном пространстве и определяются с помощью элементов множества , где l – длина хромосомы в битах, * – в данной позиции может быть любой бит. Генетический алгоритм обрабатывает шаблоны, и производит выборку значительного числа гиперплоскостей из областей с высокой приспособленностью, причем в течение одного поколения популяции оценивается структур. Это и отличает эволюционные процессы от различных эвристических и случайно-поисковых методов, в которых единственное решение развивается само по себе, а предыдущий опыт не используется.

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


^ Результаты расчетов

Используем для последующего анализа выборку из 520 измерений, где в качестве варьируемых переменных представлены общее число видов X1 = N и показатели обилия отдельных таксонов зообентоса (для хирономид – подсемейств и триб); Xj = ln((NsjBsj)0.5), Nsj и Bsj – суммарные по видам численность и биомасса j-й таксономической группы в пробе, j = 2, 3, …, 51. В предыдущей главе эта выборка уже использовалась нами при описании логистической регрессии и дискриминантного анализа (см. разделы 8.2 и 8.3). В качестве прогнозируемого отклика была взята категория качества воды в альтернативной шкале «Чисто» (2 и 3 класс) / «Грязно» (4 – 6 класс).

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

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

Таблица 9.2

Результаты эволюционного процесса формирования информативного

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

( (xi) – оценка эффективности хромосомы)


итераций

 (xi)

Битовые маски хромосом

1

2.0001

10000011011001011010100111010010110100010001011110

2

2.0093

11101010010110010100000101100001110010110010011010

3

2.0049

10010101100100010011110111001111111110001001101011

4

2.0124

11100000110011000100011101010010110000010001011110

5

2.0154

11000111001101101101101111010010110101010001010110

6

2.0076

00011010010110010100010101100001110010111011000111

7

2.0078

00011010010111010100010101100001110010010010000111







97

2.0063

10010011101100010001101011110110111000001101100011

98

2.0070

10111001110101000100101001001001000101001101110010

99

2.0149

10111001101100000100101001001001000101101001000010

100

2.0042

01111000111100000110001101000010111101101001000010

Наилучшее найденное решение:




2.0450

11011010111111100010001001110000110101101110101010




оставить комментарий
страница1/4
Дата02.10.2011
Размер1,05 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх