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

Страницы:
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 

1 Запорожский национальный технический университет, г. Запорожье,

zaitsev.serge@gmail.com

2 Запорожский нацщональный технический университет, г. Запорожье,

subbotin@zntu.edu.ua

МОДЕЛЬ ОТРИЦАТЕЛЬНОГО ОТБОРА С ИСПОЛЬЗОВАНИЕМ МАСКИРОВАННЫХ ДЕТЕКТОРОВ И МЕТОД ЕЁ ОБУЧЕНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИАГНОСТИРОВАНИЯ

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

ОТРИЦАТЕЛЬНЫЙ ОТБОР, БИТОВАЯ СТРОКА, ДЕТЕКТОР, ПРАВИЛО СОПОСТАВЛЕНИЯ, МАСКИРОВАНИЕ

Введение

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

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

Используемые для решения данной задачи подхо -ды имеют ряд недостатков. В частности, нейронные сети требуют дополнительной процедуры вербали­зации для упрощения правил [1]. Деревья принятия решений часто сходятся на локальных оптимумах, при большом количестве признаков полученные правила значительно усложняются, а также деревья решений плохо поддаются переобучению [2].

В целях устранения перечисленных выше недо­статков при решении данной задачи целесообраз­но использовать принцип отрицательного отбора в искусственных иммунных системах. Он обладает таким рядом свойств, как способность работать с бинарным представлением признаков, возмож­ность обучаться на экземплярах только одного класса, распределенность вычислений [3].

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

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

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

Пусть мы имеем выборку S', состоящую из эк­земпляров, описанных битовыми строками фик­сированной длины l. Будем считать, что набор всех возможных битовых строк длиной l форми­рует пространство признаков U. Множество U можно разделить на два комплементарных под­множества, опис^івающих "свои" (годные) и "чу­жие" (дефектные) экземпляры соответственно: U = S и N, S n N = 0, где S множество годных экземпляров, а N множество дефектных. Обу­чающая выборка состоит только из годных экзем­пляров SS . В этом случае задача построения модели отрицательного отбора заключается в ге­нерации такого набора правил, представленного множеством детекторов D , на основании которого каждый x<eU можно однозначно отнести к классу годных или дефектных экземпляров.

2. Метод обучения модели отрицательного отбора с цензурированием

Рассмотрим модель [5], реализующую парадиг­му отрицательного отбора.

Как правило, для определения принадлежности экземпляра к множеству S или N модель отрица­тельного отбора в процессе обучения добавляет в набор D такие детекторы, которые не соответству­ют "своим" экземплярам. Поскольку множества S и N комплементарны, то предполагается, что любая битовая строка x принадлежит множеству N , если ей соответствует хотя бы один детектор из набора D . Определение соответствия экземпляра детектору происходит на основании правила сопо­ставления match(d,x), которое принимает значе­ние "истина", если детектор соответствует экзем­пляру, и "ложь" — в противном случае.

Таким образом, работа данной модели осущест­вляется в два этапа.

1. Генерация набора детекторов. Для этого слу­чайно сгенерированные кандидаты в детекторы C , представленные в виде битовых строк, подлежат цензурированию, и те из них, которые не отсеива­ются на данном этапе, попадают в набор детекто­ров В . В результате цензурирования отсеиваются те кандидаты в детекторы c є C , для которых суще­ствует такой x єS, чтобы match (c, x) = 1.

2. Классификация. На этом этапе экземпляр x , поступающий на вход модели, сравнивается с детекторами из набора В , используя правило со­поставления. Если хотя бы один из детекторов при этом активизируется, т.е. 3d єВ: match(d,x) = 1, считается, что x є N , в противном случае x є S.

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

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

3. Бинарные метрики

В качестве правила сопоставления двух бинар­ных детекторов применяются различного рода ме­трики, позволяющие определить степень подобия двух битовых строк [5-8].

Правило г-последовательных битов (r-contiguous rule, RCB rule) [5-7] использовалось изначально в модели отрицательного отбора. Метод генерации детекторов для модели отрицательного отбора опе­рировал строками фиксированной длины. Так, для двух строк, представленных в виде последователь­ности из n битов x = {x1,x2,...,xn] и d = {d1,d2,...,dm] правило выглядит следующим образом:

match(d,x)

1,3/,/ < n - r +1, V/ < j < i + r -1: xj = dj;

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

Иными словами, две строки совпадают, если существует такое окно размером r , в пределах ко­торого все биты обеих строк совпадают.

Данная метрика отличается своей простотой и используется в оригинальном методе генерации детекторов для модели отрицательного отбора, по­лучившем свое дальнейшее развитие в линейном и "жадном" методах генерации детекторов [6]. Все эти методы ограничиваются использованием би­нарной формы представления детекторов и RCB-правила.

Метрика R-chunks [7] является более общей по сравнению с RCB-метрикой, т.е. любой детектор, оперирующий RCB-правилом, может быть пред­ставлен в виде множества r-chunks детекторов. Для двух строк x = {x1,x2,...,xn} и d = {d1,d2,...,dm) длиной n и m соответственно, n < m, правило r-chunks можно представить как:

match(d,x)

1: x,

dj;

V/<j</+m j

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

где / определяет позицию начала отрезка строки (chunk).

Правило r-chunks позволяет повысить точность работы метода отрицательного отбора.

Метрика Хемминга применялась в [8] в качестве правила сопоставления:

match(d,x)

1, ^ x/ © dJ > r;

i=1

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

где n длина битовой строки, © — операция "ис­ключающее ИЛИ", r порог срабатывания пра­вила, 0 < r < n .

Метрика Левенштейна [8] может считаться обоб­щением метрики Хемминга. Её значение опреде­ляется минимальным количеством изменений, необходимых для преобразования одной бинарной строки в другую. При этом изменения могут быть следующего вида: вставка разряда, удаление разря­да, замена одного разряда (бита) другим из алфа­вита. В некоторых вариациях метрика Левенштей-на считает замену нескольких смежных разрядов одной операцией.

Использование метрики Левенштейна целесоо­бразно, если экземпляры обладают различным ко­личеством признаков.

Важно отметить, что в случае использования ме­трики rcb и r-chunks необходимо заранее учитывать информативность признаков и возможно произве­сти перестановку битов в строках таким образом, чтобы биты, соответствующие информативным признакам образовывали последовательность — только в таком случае, метрики rcb и r-chunks смо­гут учитывать их значения наиболее эффективно.

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

Использование бинарных детекторов часто приводит к такому явлению, как "дыры". "Дырой" (hole) называют такую бинарную строку, описы­вающую экземпляр чужого класса, для которой невозможно сгенерировать корректный детектор (т.е. любой сгенерированный детектор, который соответствует этой строке, будет также соответ­ствовать какой-то строке, описывающей "свои" экземпляры). Иными словами, чужая строка a є N образовывает "дыру", тогда и только тогда, когда Vx є U,match(x,a) = 1:3s є S,match(s,a) = 1. "Дыры" образовываются при использовании любой метри-ки с фиксированной вероятностью соответствия [6]. В [9] предлагается решение этой проблемы. Каждый детектор должен иметь несколько спосо­бов представления в бинарном виде. Например, для строк s1 = 01101011, s2 = 00010011 зададим пра­вило перестановки бит L = 1 - 6 - 2 - 5 - 8 - 3 - 7 - 4 . Применив это правило к строкам, получим: L (s1 ) = 00111110 L (s2 ) = 00001011. Используя rcb-метрику с параметром r = 3 , можно увидеть, что match (s1, s2) = 1, т.к. последние три бита этих строк совпадают. Однако match(L(s1 ),L(s2 )) = 0 .

Страницы:
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 самых важных уроков библии

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

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

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

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