Обобщенная модель искусственной иммунной системы
|
|
Скачать 126.25 Kb.
|
|
Содержание
1. Постановка задачи2. Анализ существующих моделей ИИС 3. Гиперклетка в задачах классификации 4. Эксперименты и результаты Результаты тестирования различных моделей ИИС |
|
ISBN 978-5-7262-1226-5. НЕЙРОИНФОРМАТИКА – 2010. Часть 2 С.А. ЗАЙЦЕВ, С.А. СУББОТИН Запорожский национальный технический университет, Украина [email protected] ОБОБЩЕННАЯ МОДЕЛЬ ИСКУССТВЕННОЙ ИММУННОЙ СИСТЕМЫ Проведен анализ основных моделей искусственных иммунных систем: положительного и отрицательного отборов, а также клональной селекции. Выполнена экспериментальная оценка работы различных видов детекторов в задачах классификации. Предложен принцип построения моделей искусственных иммунных систем, позволяющий повысить скорость и точность процесса классификации. Введение Современные методы и модели искусственных иммунных систем (ИИС) представлены тремя основными моделями: отрицательного отбора, клональной селекции и иммунной сети [1-3]. Эти модели находят свое практическое применение в ряде задач, таких как распознавание образов, обнаружение вторжений в системах безопасности, классификация, прогнозирование и многих других [4]. Успех применения той или иной модели напрямую зависит от вида детекторов, применяемых в модели ИИС [5], поэтому многие современные исследования в области ИИС уделяют внимание развитию новых и обобщению уже существующих видов детекторов. ^ Поскольку природная иммунная система предназначена для решения задач классификации в живом организме, это создает предпосылки для использования ИИС в подобного рода технических приложениях. Однако механизм работы природной иммунной системы до сих пор полностью не изучен и существует несколько различных теорий, объясняющих принципы её работы. Искусственные реализации этих теорий называют моделями ИИС. Традиционная постановка задачи распознавания образов для случая двух классов предполагает задание обучающего множества экземпляров, содержащего примеры обоих классов (позитивные и негативные примеры). Однако ИИС не требуют задания примеров обоих классов, исходными данными задачи построения распознающей модели на основе ИИС является обучающая выборка  , где  – мощность обучающей выборки, все экземпляры которой принадлежат только к одному классу. Задача классификации сводится к определению принадлежности некоторых произвольных экземпляров к данному классу. Если распознаваемый экземпляр не принадлежит к классу, моделируемому ИИС, то его относят к альтернативному классу.Модели ИИС во время классификации используют правила сопоставления  . Так,  определяет аффинность между  и  , где – детектор, – входные данные, подлежащие классификации.В процессе работы модель ИИС формирует так называемую иммунную память – набор детекторов, способствующих правильной классификации  , где  – количество детекторов в иммунной памяти.Целью данной работы является анализ различных моделей ИИС в задачах классификации и разработка такого метода построения иммунных моделей, который позволил бы повысить эффективность работы ИИС. ^ Модель отрицательного отбора является одной из наиболее широко известных моделей ИИС. Её принцип работы заключается в генерации детекторов, соответствующих аномальному поведению исследуемого объекта. Метод отрицательного отбора состоит из двух фаз: обучения и классификации. Во время обучения на вход модели поступают “свои” антигены (self-antigen). При этом в ИИС вырабатываются случайные клетки, которые становятся детекторами лишь в том случае, если они не реагируют ни на один из антигенов, а также и на уже существующие иммунные клетки (антитела). Таким образом, полученная во время обучения популяция клеток в значительной степени описывает пространство предполагаемых “чужих” клеток. В процессе распознавания клетка считается патогенной (“чужой”), если ее распознает хоть один из существующих детекторов. Метод неоднократно подвергался критике [6] в силу низкой точности классификации и больших временных затрат на работу. Однако некоторые его модификации, в частности V-детектор [7], показали хорошие результаты и определили новые пути развития модели. Положительный отбор основан на схеме работы модели отрицательного отбора, за исключением того, что детектором считают случайную клетку, реагирующую хотя бы на один антиген из обучающей выборки. Клональная селекция является наиболее распространенной моделью положительного отбора. Её особенность заключаются в том, что после генерации случайного положительного детектора он подвергается клонированию, а затем осуществляется мутация каждого из клонов. Таким образом, из популяции клонов можно определить наиболее точно соответствующий антигену детектор, который и заменит родительский детектор в общей популяции. Этот подход позволяет ускорить процесс сходимости метода, при этом размер популяции существенно не увеличивается, что приводит к экономии вычислительных ресурсов. Очевидно, что отрицательный отбор по сравнению с положительным более эффективен в случаях, когда область “чужих” клеток существенно меньше области “своих”. Таким образом, для правильного выбора модели необходимо обладать априорными знаниями о распределении “своих” и “чужих” клеток, а это представляется возможным далеко не всегда. В зависимости от вида задач применяют два основных вида детекторов: представленный вектором действительных чисел и строкой конечного алфавита. Если с помощью детекторов первого вида можно задавать только численные значения признаков в многомерном пространстве, то строковые детекторы предназначены для представления битовых строк, бинарных данных, категорийных значений и т.д. Числовые детекторы характеризуются координатами центра детектора в пространстве признаков и радиусом детектора. Считают, что детектор соответствует антигену, если мера расстояния от центра детектора до антигена меньше его радиуса. В качестве меры расстояния используют евклидово расстояние или расстояние Манхэттена. Идея использования изменяющихся детекторов описана в [7] и заключается в том, что детекторы могут отличаться не только радиусом, но и формой, а также другими параметрами. Это позволяет получать более точные решения, в частности с применением модели отрицательного отбора. Другие исследования [8] показали эффективность многослойных детекторов, осуществляющих как положительный, так и различные виды отрицательного отбора. Точность работы модели в таком случае повышается, поскольку клетка классифицируется не одним детектором, а логическим выражением, описывающим реакцию нескольких детекторов на антиген. ^ Гиперклетка – это самоорганизующийся абстрактный объект, объединяющий понятия иммунной модели и детектора. Рассмотрим применение гиперклеток в задаче классификации в двухмерном пространстве. Обучающая выборка S состоит из объектов одного класса. Если считать основной моделью гиперклетки отрицательный отбор, то обучающая выборка будет состоять из “чужих” элементов. Для удобства визуального представления результатов считаем пространство признаков объекта двухмерным. Признаки представлены вещественными числами. В качестве правила будет выступать евклидово расстояние между объектами в пространстве признаков.Хотя понятие гиперклетки предполагает модификацию любых ее параметров во время обучения (модель, вид и размер детектора, критерии останова и пр.), рассмотрим поведение гиперклетки с изменением формы. Каждая гиперклетка изначально описывает форму представляемого ею детектора. Изменение формы как одной из наиболее важных характеристик клетки можно свести к отсечению определенных, принадлежащих ее изначальной форме, частей. Если форму детектора в двухмерном пространстве описывать с помощью центра детектора и его радиуса, то детектор любой формы можно представить как вписанную в окружность некоторого мета-детектора фигуру. Для того, чтобы мета-детектор отображал определенную форму, необходимо каким-то образом хранить описание области, покрываемой детектором. С точки зрения ИИС описание формы области задается множеством клеток. Иными словами, можно сгенерировать набор детекторов меньшего радиуса внутри мета-детектора таким образом, чтобы они с наименьшей ошибкой покрывали множество “чужих” элементов  .Следовательно, задачу изменения формы детектора можно свести к основной задаче отрицательного отбора – нахождению областей “своих” (области покрытия модифицированного детектора) и “чужих” клеток. Во время инициализации метода создается одна гиперклетка, покрывающая все допустимое пространство признаков. Очевидно, что такой детектор покрывает не только “чужие”, но и “свои” объекты, поэтому появляется необходимость его обучения, включающего следующие этапы. 1. Инициализируем иммунную память пустыми множествами положительных и отрицательных детекторов  ∅. Положительные детекторы  реагируют на “свои” объекты, отрицательные  – на “чужие”. При этом считаем, что  .2. Для каждого элемента  выполняем этапы 3-5.3. Вычисляем аффинность  каждого отрицательного детектора  . Считаем, что правило M выполняется, когда значение аффинности ниже порогового, т.е. когда  и достаточно подобны.4. Для тех  , для которых выполняется правило  , рекурсивно производим процедуру обучения.Шаг 5. Если процедуру обучения невозможно произвести (например, из-за ограничения высоты дерева гиперклеток), то дочернюю гиперклетку перемещаем из отрицательной области памяти в положительную:  ,  .Атомарными клетками будем называть клетки, не способные обучаться. Так, атомарными можно считать клетки, которые:
Как видно, критерии атомарности клетки отражаются как на точности, так и на скорости работы метода. Генерация новых дочерних гиперклеток производится следующим образом. 1. Генерируем случайную гиперклетку  в пространстве родительской клетки . Соотношение радиуса дочерней гиперклетки и родительской является еще одним параметром, влияющим на точность классификации. Так, слишком большие дочерние клетки не позволяют точно описать форму детектора на одном уровне иерархии, в то время как слишком маленькие клетки делают популяцию избыточной.2. Если существует такая положительная или отрицательная гиперклетка  , для которой справедливо правило  , считаем клетку неподходящей и переходим к этапу 1.3. Если данная клетка аффинна объекту из обучающей выборки (выполняется  ), помещаем ее в отрицательную память  , иначе – в положительную  .Это приведет к формированию отрицательной (  ) и положительной ( ) памяти в пространстве признаков, принадлежащем корневой гиперклетке.Процедура классификации неизвестного детектора содержит следующие этапы.1. Для гиперклетки произвести классификацию поступившего детектора . Если гиперклетка является атомарной, то считаем, что класс детектора совпадает с классом клетки – т.е. если  , то детектор “свой”, иначе – “чужой”. В противном случе переходим к шагу 2.2. Перебираем дочерние гиперклетки . Для тех гиперклеток , которые афинны детектору , выполняем процедуру классификации до тех пор, пока не будет получено однозначное решение от атомарной гиперклетки.Таким образом, в процессе распознавания антигена производится своего рода поиск по дереву. Такое структурирование данных позволяет ускорить добавление новых детекторов, а также оптимизировать процесс поиска. ^ Для сравнения ИИС выполнялось экспериментальное исследование свойств: отрицательного отбора, клональной селекции, V-детектора и гиперклеточной модели. В качестве исходных данных были взяты выборки двухмерных данных, образующих геометрические фигуры – кольцо (задача классификации № 1) и пятиконечная звезда (задача классификации № 2). Использование этих выборок обосновано в [7]. Результаты эксперимента приведены в табл. 1. В качестве характеристик работы методов были выбраны следующие: время обучения и классификации, доля ложноположительных и ложноотрицательных срабатываний метода, иными словами, ошибки 1-го и 2-го рода, соответственно. Визуальное представление результатов работы обученной модели гиперклеток показано на рис. 1. Таблица 1 ^
  а) б) Рис. 1. Расположение детекторов обученной модели (внизу) по данным обучающей выборки (вверху): а) для задачи классификации №1; б) для задачи классификации №2 Высокая скорость обучения гиперклеток по сравнению с классическими моделями объясняется тем, что процедура происходит не на всем пространстве признаков, а только в области родительского детектора. Этот факт позволяет ускорить поиск и приводит к локально оптимальной комбинации детекторов. В таком случае области с низкой концентрацией “чужих” антигенов будут покрыты детекторами большего радиуса, что снижает размер популяции. Заключение В работе решена актуальная задача построения ИИС, обобщающей достоинства существующих моделей, что позволяет эффективно использовать ее в задачах классификации. Предложена новая гибридная модель ИИС, которая объединяет в себе свойства частного вида детекторов и модели в целом. Модель гиперклетки реализует новые принципы иерархичности иммунных клеток. Гиперклетка не является пассивным компонентом модели, а представляет собой активный объект, который обладает следующими свойствами. Так же, как и детектор, гиперклетка:
Так же, как и модель:
Область применения гиперклеток не ограничивается вещественными признаками. Для признаков, представляемых строками, можно создать иерархию с помощью регулярных выражений или, увеличивая длину rcb-правила [9]. Был проведен анализ моделей ИИС и выявлены положительные моменты в их работе; на основании результатов анализа была разработана новая модель ИИС, которая показала свою эффективность в процессе ее экспериментального исследования. Список литературы 1. Forrest S., Perelson A.S., Allen L., Cherukuri R. Self-nonself discrimination in a computer // Research in Security and Privacy: Proceedings of IEEE Computer Society Symposium. – Los Alamitos: IEEE Computer Society Press, 1994. – P. 202-212. 2. de Castro L.N., Von Zuben F.J. Learning and optimization using the clonal selection principle // IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems. – 2002. – Vol. 6. – № 3. – P. 239-251. 3. de Castro L.N., Von Zuben F.J. AiNet: An Artificial Immune Network for Data Analysis // Data Mining: A Heuristic Approach. / Eds.: H.A. Abbass, R.A. Sarker, C.S. Newton. –Hershey: Idea Group Publishing, 2001. – P. 231-259. 4. Artificial Immune Systems and their applications / Ed. D. Dasgupta. – New York: Springer-Verlag, 1998. – 306 p. 5. Ji Z., Dasgupta D. Revisiting negative selection algorithm // Evolutionary Computation. – 2007. – Vol. 15. – № 2 (Summer). – P. 223-251. 6. Freitas A.A., Timmis J. Revisiting the foundation of artificial immune systems: A problem-oriented perspective // Second International Conference on Artificial Immune System (ICARIS 2003): Proceedings. – Berlin–Heidelberg: Springer-Verlag, 2003. – Ser. LNCS 3239. – P. 229-241. 7. Ji Z., Dasgupta D. Real-valued negative selection algorithm with variable-sized detectors // Genetic and Evolutionary Computation (GECCO 2004): Proceedings. – Berlin–Heidelberg: Springer-Verlag, 2004. – Ser. LNCS 3102. – Part I. – P. 287–298. 8. Dasgupta D., Yu S., Majumdar N.S. MILA – multilevel immune learning algorithm // Genetic and Evolutionary Computation (GECCO 2003): Proceedings. – Berlin–Heidelberg: Springer-Verlag, 2003. – Ser. LNCS 2723. – P. 183–194. 9. Gonzalez F., Dasgupta D., Gomez J. The effect of binary matching rules in negative selection // Genetic and Evolutionary Computation (GECCO 2003): Proceedings. – Berlin–Heidelberg: Springer-Verlag, 2003. – Ser. LNCS 2723. – P. 195-206. УДК 004.032.26(06) Нейронные сети |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ваша оценка этого документа будет первой.
Ваша оценка:
Похожие:
База данных защищена авторским правом ©MedZnate 2000-2016
allo, dekanat, ansya, kenam
обратиться к администрации | правообладателям | пользователям
allo, dekanat, ansya, kenam
обратиться к администрации | правообладателям | пользователям