Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 66

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Фактически использование маски перестановок позволяет изменять форму детектора в простран­стве признаков, в то время как форма "своего" про­странства остается неизменной. Каждое фиксиро­ванное представление формирует свои "дыры", а использование нескольких представлений снижет вероятность того, что одна и та же "чужая" строка приведет к формированию "дыр" одновременно во всех представлениях детектора.

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

Существенным недостатком метода является то, что он применим только для метрики rcb.

5. Метод обучения с маскированием

С целью устранения недостатков метода, опи­санного выше, авторами предлагается использо­вать детекторы с маскированием. Для этого необ­ходимо расширить алфавит, на основе которого формируются детекторы, дополнив его еще одним символом символом маски Z : £2 = {0,1,Z}.

Значение Z играет особую роль оно соот­ветствует любому значению {0,1} бита в битовой строке. Учитывая этот факт, существующие метри­ки должны быть модифицированы.

Так, метрика Хемминга для порогового значе­ния r и битовых строк s и d длиной l может быть представлена в виде:

Метрика rcb для маскированных детекторов вы­числяется следующим образом:

match (d, s )--

1,       dt ф Z a dt ф st }> r;

[0, впротивном случае. Иными словами, детектор d и битовая строка s совпадают, если у них совпадают r незамаски­рованных битов.

match(d, s)

1,31,t =   .  - r:       d = Z a dt = st }> r;

[0, впротивном случае.

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

match(d, s)

1,      d = Z v d = St } = l;

t=1

[0, впротивном случае.

Такая метрика предполагает, что детектор со­ответствует строке, если все незамаскированные биты детектора соответствуют битам строки.

Жизненньгй цикл детектора включает в себя следующие стадии:

— формирование полностью замаскированного детектора, т.е. такого детектора, у которого значе­ние всех битов равно Z;

замена замаскированных значений битов де­тектора;

добавление детектора в набор.

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

1. Сформировать замаскированный детектор d = {Zу.

2. Если 3s eS: match (d, s) = 1, тогда перейти к этапу 3, в противном случае — к этапу 5.

3. Выбрать произвольным образом бит dt, t = 1,.. ,l, dt = Z . Если такого бита не существует, тогда перейти к этапу 1, в противном случае — пе­рейти к этапу 4.

4. Установить значение -го бита детектора: dt = —st. Перейти к этапу 2.

5. Добавить детектор d в набор детекторов: D = D и {d}. Если достигнуто достаточное для не­обходимого уровня точности количество детекто­ров, тогда перейти к этапу 6, в противном случае — перейти к этапу 1.

6. Останов.

В результате работы метода будет получен набор детекторов, у которых незамаскированные биты определяют правила, по которым можно прово­дить дальнейшую классификацию. Например, де­тектор {001Z1} можно рассматривать следующим образом: если у экземпляра отсутствует 1-ый и 2-ой признаки, однако присутствуют 3-ий и 5-ый, то экземпляр считается чужим.

Так как метод не проверяет наличие подобных детекторов в наборе, то в процессе работы метода могут быть сгенерированы идентичные детекто­ры. По той же причине могут быть получены такиепары детекторов, у которых все незамаскирован­ные биты совпадают, например {010Z} и {01ZZ}.

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

6. Модифицированный метод обучения с маскированием

Предложенный выше метод позволяет сокра­тить количество детекторов в наборе, тем самым повысив скорость процесса классификации с ис­пользованием модели отрицательного отбора. Однако формирование такого набора детекторов остается ресурсоемкой задачей, поскольку каждый новый детектор после изменения некоторого бита требуется сопоставить с каждым "своим" экзем­пляром.

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

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

1. Сформировать замаскированный детектор c0 ={Z Г.

2. Создать набор кандидатов в детекторы C = {c }.

3. Выбрать произвольным образом кандидат в детекторы из набора ceC.

4. Если 3s eS: match (c, s) = 1, тогда перейти к этапу 5, в противном случае перейти к этапу 8.

5. Выбрать произвольным образом бит c, t = , c = Z. Если такого бита не существует, тогда перейти к этапу 1, в противном случае — пе­рейти к этапу 6.

6. Установить значение t -го бита детектора:

ct = -st.

7. Добавить модифицированный кандидат в на­бор C = C и {c}. Перейти к этапу 3.

8. Добавить кандидат c в набор детекторов: D = D u{c} . Если достигнуто достаточное для не­обходимого уровня точности количество детекто­ров перейти к этапу 9, в противном случае пе­рейти к этапу 1.

9. Останов.

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

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

7. Эксперименты и результаты

Предложенный метод синтеза диагностической модели тестировался как на синтетических выбор­ках, так и на практических задачах диагностирова­ния [10] с использованием программной реализа­ции метода на языке Python.

Синтетические тесты включали в себя наборы детекторов длинной l = 4,...,12. Обучение прово­дилось на экземплярах "своего" класса, затем про­водилась классификация и вычислялось значение ошибки первого рода, определяемое числом не­верно распознанных чужих экземпляров выборки.

На рис. 1 представлены графики, отображаю­щие зависимости количества детекторов в наборе D от длины битовых строк l для метода с цензу­рированием и для предложенной модификации метода с маскированием соответственно.

Рис. 2 отображает количество проверок соот­ветствия детекторов и экземпляров для каждого из методов.

3500 «-■-■-■-■-■-■-■-1

4 5 6 7,8 9 10 11 12

длина битовых строк

Рис. 1. График зависимости размера набора детекторов от размерности задачи

Как видно из рис. 1 и рис. 2, предложенный ме­тод требует значительно меньше вычислений при построении модели отрицательного отбора, хотя при этом точность работы метода выше и состав­ляет 95—100%.

4.5Є+06

4 5 Б 7^8 9 10 11 12

длина битовых строк

Рис. 2. График зависимости количества проверок правила сопоставления от размерности задачи

Выводы

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

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

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

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

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

Список литературы: 1. Миркес, Е.М. Логически прозрач­ные нейронные сети и производство явных знаний из данных [Текст] / Е.М. Миркес, А.Н. Горбань, В.Л. Дунин-Барковский, А.Н. Кирдин и др. // Нейроинформатика.

Новосибирск: Наука. Сибирское предприятие РАН, 1998. — С. 296. 2. J. Ross Qutnlan C4.5: Programs for Machine learn­ing // Massachusetts, USA: Morgan Kaufmann Publishers, 1993. P. 324. 3. Gonzalez F., Dasgupta D., Gomez J. The effect of binary matching rules in negative selection // Proceedings of the Genetic and Evolutionary Computation Conference GECCO—2003 (9-11 July, 2003). Berlin-Heidelberg: Springer-Verlag, 2003. P. 195—206. 4. Jt Z., Dasgupta D. Revisiting negative selection algorithms // Evolutionary Computation. 2007. №15. P. 223—251. 5. Forrest S., Perelson A.S., Cheru-kurt R., Allen L. Self-Nonself Discrimination in a Computer // Proceedings of the 1994th IEEE Symposium on Research in Security and Privacy (1994). CA: IEEE Computer Society Press, 1994. P. 202—212. 6. D'haeseleer P., Forrest S., Hel-man P. An immunological approach to change detection: algorithms, analysis, and implications // Proceedings of the 1996th IEEE Symposium on Computer Security and Privacy (6-8 May, 1996). CA: IEEE Computer Society Press, 1996. P. 110—119. 7. Balthrop J., Esponda F., Forrest S., Gltckman M. Coverage and generalization in an artificial immune system // Proceedings of the Genetic and Evolutionary Computation Conference GECCO—2002 (9-13 July, 2002). San Fran-sisco, USA: Morgan Kaufmann, 2002. P. 3—10. 8. Farmer J., Packard N., Perelson A. The immune system, adaptation, and machine learning // Physica D: Nonlinear Phenomena. 1986. №2. P. 187—204. 9. Hofmeyr S., Forrest S. Architecture for an Artificial Immune System // Evolutionary Computation. 2000. №8(4). P. 443—473. 10. Герасимчук, Т.С. Использование искусственных иммунных систем для прогнозирования риска развития реккурентных респираторных инфекций у детей раннего возраста [Текст] / Т.С. Герасимчук, С.А. Зайцев, С.А. Субботин // Матеріали міжрегіональної науково-практичної конференції "Діагностика та лікування інфекційно опосередкованих соматичних за­хворювань у дітей" : конференція (10-11 лютого 2011 р.). Донецьк: Норд-пресс, 2011. — С. 27—29.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа