Математическая постановка задачи распознавания образов

ДИСТАНЦИОННАЯ ЛЕКЦИЯ № 1 1. Математическая постановка задачи распознавания образов Распознавание образов − раздел математической кибернетики, разрабатывающий методы классификации и идентификации предметов, явлений, процессов, сигналов и ситуаций, которые могут быть описаны конечным набором некоторых признаков или свойств, характеризующих объект. Под задачей классификации понимают задачу разделения исходного множества объектов на заранее заданные классы. При классификации с обучением эталонные непересекающиеся классы выделяет эксперт. В случае классификации без обучения информация о принадлежности каких-либо элементов к эталонным классам отсутствует. Как правило, сначала выполняется классификация без обучения, выделяются эталонные классы, а затем на основе полученных классов проводится классификация с обучением. Задача классификации (распознавания) формулируется следующим образом. Пусть дано множество объектов; на этом множестве имеется разбиение на конечное число подмножеств (классов) , Каждый класс имеет внутреннюю структуру в виде некоторого множества объектов-эталонов. Объект описывается значениями признаков . Информация о вхождении объекта в какой-либо класс представляется в виде информационного вектора , где несет информацию о принадлежности объекта к классу (1) Решение (1) о принадлежности произвольного объекта классу принимается на основе сравнения расстояний между объектом и классами. Для решения этой задачи используются: • методы дискриминантного анализа, • информационный подход, • метод потенциальных функций, • искусственные нейронные сети, • деревья решений, • байесовский классификатор и другие методы. Узловым моментом в задачах кластеризации и классификации является выбор метрики (или меры близости объектов), от которой существенным образом зависит вариант разбиения объектов на группы при заданном алгоритме разбиения. Априорная информация в задаче распознавания с непересекающимися классами часто задается в виде так называемой таблицы обучения (учебной выборки). Рассмотрим наиболее распространенную задачу бинарной классификации объектов. Пусть задана исходная таблица с прецедентами (таблица 1). Таблица 1 содержит данные о множестве объектов, каждый из которых описан вектором значений информационных признаков и отнесен экспертом к одному из двух классов . Выдвигается гипотеза, что задача отнесения объекта определенному классу может быть решена гиперплоскостями. В соответствии с алгебраической теорией Ю.И.Журавлева имеем систему из неравенств вида (2) Здесь - вектор коэффициентов гиперплоскости. Если система неравенств (2) совместна, то имеется гиперплоскость, разделяющая множество объектов на два подмножества. Таблица 1− Таблица прецедентов, классифицированных экспертами Объекты Признаки и их значения Класс Уравнение разделяющей гиперплоскости может быть записано в виде (3) Если система несовместна, то задача решается проведением гиперплоскостей с построением решающей функции по методу комитета большинства. Под комитетом понимают набор векторов такой, что каждому из неравенств (2) удовлетворяет большее число таких векторов. Тогда принадлежность объекта определенному классу будет определяться по результирующему значению распознающей функции . , (4) где - означает неопределенность. На практике довольно часто решают следующую задачу: по заданному запросу (характеристикам) объекта выполнить поиск наиболее близких образцов в заданной базе данных. В этом случае эксперты предварительно формируют классы на основе анализа некоторого числа признаков и отнесения по ним имеющихся образцов к тому или иному классу. При этом знания экспертов могут быть зафиксированы в базе знаний, использованы в качестве обучающей выборки для построения классификатора для автоматического поиска объектов в базе. 2. Оценка значимости признаков для решения задачи распознавания образов Известно несколько методов выделения и оценки важности (информативности) признаков, необходимых для надежного распознавания образов. Довольно часто в практически важных приложениях можно ограничиться случаем бинарных признаков, принимающих значения «0» или «1». 2.1. Оценка важности признаков по Журавлеву Ю.И. Пусть задана таблица бинарных признаков для случая двух классов. Определение 1: тестом таблицы называется совокупность столбцов таких, что после удаления из таблицы всех прочих столбцов все пары строк, принадлежащие разным классам, различны. Определение 2: тест называется тупиковым, если никакая его истинная часть не является тестом. Таким образом, тест – это минимальный набор признаков, для которого отсутствуют одинаковые векторы-строки в разных классах обучающей выборки. Тупиковый тест = это не сжимаемое далее описание, которое содержит все сведения о разделении исходного множества объектов на классы. Тупиковый тест не содержит внутри себя другие тесты с меньшим числом признаков. Если признак участвует в формировании число тупиковых тестов, то его значимость определяется по формуле , где – общее количество тупиковых тестов. Рассмотрим пример (таблица 2). Таблица 2 − Объекты и их бинарные признаки Объекты (ситуации) Класс 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1. Выписываем все тупиковые тесты: 2. Находим значимость каждого признака: . Чем больше , тем важнее признак для описания допустимых объектов. 2.2. Информационный подход к оценке значимости признаков и распознаванию Информационный подход применяют для распознавания ситуаций и решения задачи классификации для случая бинарных признаков. Например, применительно к задаче оценки состояния сложного объекта необходимо: 1) определить параметры, характеризующие состояние объекта (признаковое пространство), 2) создать математическую модель для определения состояния (классификации). Пусть текущее состояние объекта оценивается вектором бинарных признаков , фиксирующих наличие (значение “1”) или отсутствие (значение “0”) некоторых характеристик (например, наличие или отсутствие высокой температуры, высокого давления, физического износа, высокой скорости реакции и т.д.). Пусть в общем случае выделено несколько классов состояния объекта, , например, «отличное», «хорошее», «сомнительное», «плохое», «очень плохое». Каждому состоянию соответствуют наборы векторов признаков, составляющих обучающую выборку. Необходимые эталонные вектора, описывающие классы состояний получают на основе накопленного опыта и знаний экспертов. По обучающей выборке оценивается информационная значимость каждого k-го признака в классе по формуле Таким образом, определяются частные информации каждого признака о состоянии испытуемого объекта. Заметим, что при подсчете вероятностей должны выполняться условия: причем классы считаются равновероятными. Тогда все частные информации можно записать в таблицу 3. Таблица 3 – Информационная значимость значений признаков Значения частной информации отдельных признаков используются для вычисления суммарной информации о принадлежности -го вектора (-ой ситуации) -ому классу. Полученные таким образом характеристики используются для построения решающих функций, отражающих количественную связь между классом и суммарной информацией о состоянии. Пусть, например, получена следующая информация о классах «хороший» и «плохой» в виде учебных векторов, задающих определенную ситуацию, отнесенную экспертом к определенному классу (таблица 4). Таблица 4 – Исходная таблица данных (обучающая выборка) Номер ситуации Признаки Класс 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 1 1 1 4 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 7 1 1 1 1 1 1 8 1 1 1 1 1 9 1 1 1 1 1 1 1 10 1 1 1 1 1 1 Для случая двух классов «хорошего» и «плохого» положим =1, . Вычисляя частную информацию по каждому признаку, получим таблицу 5 Таблица 5 – Оценка информационной значимости признаков Признаки -0.3923174228 1.607682578 1.607682578 -0.3923174228 1.607682578 -0.3923174228 -0.3923174228 1.607682578 0.08161376528 1.836501268 1.081613765 0.2515387663 1.192645078 0.6076825774 0.6076825774 1.192645078 0.08161376528 1.836501268 1.081613765 0.2515387663 0.2217914235 2.081613766 0.6368289226 1.081613765 1.607682578 -0.3923174228 -0.3923174228 1.607682578 0.6076825774 1.192645078 1.192645078 0.6076825774 1.836501268 0.08161376528 0.2515387663 1.081613765 0.2515387663 1.081613765 1.836501268 0.08161376528 1.607682578 -0.3923174228 -0.3923174228 1.607682578 0.6665762660 1.251538767 0.6665762660 1.251538767 Оценим далее информацию о принадлежности состояния объектов «хорошему» - и «плохому» - классам. Для подсчета информации как меры принадлежности ситуации тому или иному классу используется сумма частных информаций отдельных признаков, входящих в состав конкретной ситуации. Так, например, информацию о принадлежности первой ситуации классу можно вычислить как следующую сумму: =1.607682578+1.607682578+….+0.6665762660 Обобщенная по признакам таблица 6 содержит полную информацию о ситуации Таблица 6 – Информация о ситуации Номер ситуации 1 13.37069323 3.785730716 2 16.40044057 3.060590556 3 8.785730718 8.615805717 4 11.23051557 8.230515559 5 14.88046823 4.370693216 6 1.030843215 15.20076822 7 4.200768217 13.20076822 8 4.785730716 12.61580572 9 4.785730718 11.44588072 10 10.64555306 8.815478060 На основе полученной информации строится алгоритм распознавания текущей тестируемой ситуации. Для построения разделяющей функции предлагается следующая, довольно эффективная для нашего случая интерпретация задачи. Выполним ранжирование множества состояний X по степени убывания величины для определенного класса, например . Аналогично выполним эту же операцию для . В таблице 7 даны отсортированные по количеству информации вектора-ситуации. Таблица 7 − Упорядочение ситуаций по количеству информации , (отсортировано по убыванию) Номера ситуаций соответствующие , (отсортировано по возрастанию) Номера ситуаций соответствующие 16.40044057 2 3.060590556 2 14.88046823 5 3.785730716 1 13.37069323 1 4.370693216 5 11.23051557 4 8.230515559 4 10.64555306 10 8.615805717 3 8.785730718 3 8.815478060 10 4.785730718 9 11.44588072 9 4.785730716 8 12.61580572 8 4.200768217 7 13.20076822 7 1.030843215 6 15.20076822 6 Каждому упорядоченному по информации состоянию поставим в соответствие точку некоторого пространства . Графическая интерпретация результата упорядочения представлена на рисунке 8. Рисунок 8a − Упорядочение Рисунок 8b – Упорядочение Воспользуемся простейшей линейной интерполяцией и построим соответствующие кривые (рисунок 9). Рисунок 9 − Графическая интерпретация задачи распознавания Точка пересечения этих кривых обозначит границу раздела классов («хороший» − «плохой»). Далее можно «размыть» эту границу, проведя дополнительную «область нечувствительности». Это означает, что в пространстве входных описаний X существует, по крайней мере, одна функция, которая полностью разделяет множества, принадлежащие разным классам. Теперь для любой текущей ситуации можно достаточно уверенно определить точное состояние системы. Более того, при достаточно большой учебной выборке удается выявить ошибки самих экспертов, составивших эту выборку. На рисунке 9 выделена зона, в которой имеет место близость и смешение классов. Назовем ее зоной нечувствительности. Вне зоны нечувствительности можно уверенно отнести произвольный текущий вектор ситуации к тому или иному классу на основе вычисленной для него информации. Заметим, что в более сложном случае, когда признаки не являются бинарными, для информационной оценки признаков и классов можно использовать подход, предложенный в работе. Мерой трудности распознавания ситуации в этом случае служит энтропия распределенной плотности вероятности исследуемых состояний. Решающая (разделяющая) функция может быть построена также на основе метода потенциальных функций. В соответствии с рассмотренным подходом предполагается следующий порядок проведения испытаний. В результате обследования объекта в некоторый момент времени формируется вектор текущего состояния и вычисляются его информационные характеристики. Далее производится сравнительная оценка принадлежности состояния тому или иному классу (по количеству информации), на основе чего принимается решение. После распознавания ситуации происходит уточнение класса, за счет включения распознанного текущего вектора состояния. Рассмотренный подход, использующий основы теории информации, может быть полезен при оценке состояния оборудования различного класса, включая компьютерное оборудование в масштабах крупного предприятия. В случае, когда информация о текущей ситуации является неполной можно применить логико-вероятностный подход к анализу ситуации и принятию решения. Логико-вероятностный подход основан: 1) на формировании логических выражений классов в виде дизъюнктивно- конъюнктивной формы относительно бинарных переменных ,,…,, 2) на формировании текущего вектора входных признаков и определении вероятности его принадлежности каждому классу. 2.3. Методы сокращения числа признаков DEL и ADD Пусть имеется независимых признаков. Необходимо сократить количество признаков до . Существуют различные подходы к решению этой актуальной задачи. Схема алгоритма DEL. 1. Сначала берут признаков и оценивают ошибку распознавания тестовой выборки. 2. Далее, последовательно удаляют первый признак, проводят испытание, направленное на определение величины ошибки распознавания . Затем возвращают первый признак и удаляют второй признак, измеряют ошибку и т.д. Процесс продолжается до определения ошибки . 3. Удаляется признак, отсутствие которого приводит к наименьшей ошибке распознавания. Остается признаков. 3. Процедура повторяется с оставшимися признаками, пока не останутся необходимые признаков. Общее количество проверяемых наборов признаков . Метод дает выигрыш по сравнению с полным перебором, который требует проверки наборов. Схема алгоритма ADD. 1. Вначале все признаков проверяются поочередно на информативность путем распознавания тестовой выборки. 2. Отбирают наиболее информативный признак и включают его в информативный набор. 3.Затем к нему поочередно добавляют все признаков. Полученные двумерные подпространства оцениваются по количеству ошибок распознавания. 4. Выбирается наиболее информативная пара признаков, к которой аналогичным способом подбирают третий признак из оставшихся . 5. Процесс повторяется до получения системы из признаков. Данный алгоритм имеет примерно такую же сложность, что и DEL но приводит к лучшим результатам, так как риск ошибочного признания информативного признака неинформативным здесь ниже. Для улучшения результата, связанного с ослаблением ошибок на первых шагах алгоритма применяют смешанную стратегию попеременного применения алгоритмов ADD и DEL. Рассмотрим пример применения алгоритмов DEL и ADD для выявления информативных признаков при обнаружении сетевых атак. Для этого использовались данные базы сетевых атак KDD-99 (URL: http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html). Множество выделяемых информативных признаков (таблица 8) определяется структурой базы KDD-99, кроме того, введены две дополнительные группы признаков, выделяемых на основе анализа структуры запросов передаваемых по протоколу HTTP и на основании анализа SNMP пакетов. Таким образом, все выделяемые информативные признаки могут быть разделены на шесть групп: 1) Признаки, информация о которых может быть выделена из заголовка сетевого пакета (1-9); 2) Признаки, выделяемые из информационной части пакета на основании экспертных знаний, либо как информация о состоянии контролируемого узла (10-22); 3) Признаки, значения которых вычисляются как статистика за прошедшие две секунды сетевой активности, для TCP протокола (23-31); 4) Признаки, значения которых вычисляются как статистика за последние 100 соединений (32-41); 5) Признаки, выделяемые на основе анализа HTTP запросов (42-55); 6) Признаки, значения которых вычисляются как статистика за прошедшие две секунды сетевой активности, для SNMP протокола (56-60). Таблица 8 − Выделяемые информативные признаки № Имя признака Тип данных (I – целое, S – строка, F – с плавающей точкой) Описание 1 Duration I Продолжительность сессии (в секундах) 2 protocol_type S Тип протокола (TCP/UDP) 3 Service S Тип сервиса (http, telnet, и т.п.) 4 Flag S Состояние соединения (возможные значения SF, S0, S1, S2, OTH, REJ, RSTO, RSTOS0, SH, RSTRH, SHR). Выделяется только для TCP. 5 src_bytes I Количество байт переданных от источника к приемнику (вычисляется на уровне IP протокола) 6 dst_bytes I Количество байт переданных от приемника к источнику (вычисляется на уровне IP протокола) 7 Land I 1 если IP источника и приемника совпадают, 0 – в ином случае 8 wrong_fragment I Количество «неправильных» последовательностей (ошибки seq/ack номеров в передаваемой последовательности пакетов). Выделяется только для TCP. 9 Urgent I Количество пакетов с установленным флагом URG. Выделяется только для TCP. 10 Hot I Количество опасных индикаторов 11 Num_failed_logins I Количество некорректных попыток входа 12 logged_in I 1 если вход выполнен успешно; 0 в ином случае 13 Num_compromised I Суммарное количество попыток входа которые могут указывать на атаку 14 Root_shell I 1 если получен shell с правами root; 0 в ином случае 15 su_attempted I 1 если была попытка выполнения команды «su root»; 0 в ином случае 16 Num_root I Количество входов с правами «root» 17 Num_file_creations I Количество операций по созданию файлов 18 Num_shells I Количество активных shell 19 Num_access_files I Количество операций доступа к контролируемым системным файлам 20 num_outbound_cmds I Количество исходящих ftp запросов 21 is_hot_login I 1 если текущий пользователь может вносить изменения в систему; 0 в ином случае В реализации совпадает с root_shell (14) 22 is_guest_login I 1 если вход совершен с правами «guest»; 0 в ином случае. Выделяется только для TCP. Значение обратное root_shell (14) 23 Count I Количество соединений с тем же хостом (за последние 2 секунды). Выделяется только для TCP. 24 srv_count I Количество обращений к тому же сервису (за последние 2 секунды). Выделяется только для TCP. 25 serror_rate F % соединений с хостом имеющих ошибки SYN. Выделяется только для TCP. 26 srv_serror_rate F % обращений к сервису имеющих ошибки SYN. Выделяется только для TCP. 27 rerror_rate F % соединений с хостом имеющих ошибки REJ. Выделяется только для TCP. 28 srv_rerror_rate F % обращений к сервису имеющих ошибки REJ. Выделяется только для TCP. 29 same_srv_rate F % обращений к текущему сервису. Выделяется только для TCP. 30 diff_srv_rate F % обращений к другим сервисам. Выделяется только для TCP. 31 srv_diff_host_rate F % соединений с другими хостами. Выделяется только для TCP. 32 dst_host_count I Количество соединений с текущим хостом (за последние 100 сессий). Выделяется только для TCP. 33 dst_host_srv_count I Количество обращений к текущему порту назначения. Выделяется только для TCP. 34 dst_host_same_srv_rate F % обращений к тому же сервису, среди сессий учтенных в dst_host_count (32). Выделяется только для TCP. 35 dst_host_diff_srv_rate F % обращений к другим сервисам, среди сессий учтенных в dst_host_count (32). Выделяется только для TCP. 36 dst_host_same_src_port_rate F % соединений с того же порта источника, среди соединений учтенных в dst_host_srv_count(33). Выделяется только для TCP. 37 dst_host_srv_diff_host_rate F % соединений с других хостов, среди соединений учтенных в dst_host_srv_count(33). Выделяется только для TCP. 38 dst_host_serror_rate F % соединений находящихся в состоянии s0, s1, s2 или s3, среди сессий учтенных в dst_host_count (32). Выделяется только для TCP. 39 dst_host_srv_serror_rate F % соединений находящихся в состоянии s0, s1, s2 или s3, среди соединений учтенных в dst_host_srv_count(33). Выделяется только для TCP. 40 dst_host_rerror_rate F % соединений находящихся в состоянии REJ, среди сессий учтенных в dst_host_count (32). Выделяется только для TCP. 41 dst_host_srv_rerror_rate F % соединений находящихся в состоянии REJ, среди соединений учтенных в dst_host_srv_count(33). Выделяется только для TCP. 42 http_type I Тип HTTP команды (GET,POST,HEAD,other). Выделяется только для TCP. 43 http_protocol I Версия HTTP протокола (0.9, 1.0, 1.1, other). Выделяется только для TCP. 44 http_length I Длина HTTP запроса. Выделяется только для TCP. 45 http_var_count I Количество переменных использованных в запросе. Тело запроса не анализируется. Выделяется только для TCP. 46 http_substr_1 I Количество символов % в запросе. Выделяется только для TCP. 47 http_substr_2 I Количество символов ' в запросе. Выделяется только для TCP. 48 http_substr_3 I Количество символов + в запросе. Выделяется только для TCP. 49 http_substr_4 I Количество последовательностей .. в запросе. Выделяется только для TCP. 50 http_substr_5 I Количество символов \ в запросе. Выделяется только для TCP. 51 http_substr_6 I Количество символов ( в запросе. Выделяется только для TCP. 52 http_substr_7 I Количество символов ) в запросе. Выделяется только для TCP. 53 http_substr_8 I Количество последовательностей // в запросе. Выделяется только для TCP. 54 http_substr_9 I Количество символов < в запросе. Выделяется только для TCP. 55 http_substr_10 I Количество символов > в запросе. Выделяется только для TCP. 56 snmp_pdu_0 I Количество запросов с PDU = 0 (get-request), к текущему хосту, за последние 2 секунды. Выделяется только для UDP. 57 snmp_pdu_1 I Количество запросов с PDU = 1 (get-next-request), к текущему хосту, за последние 2 секунды. Выделяется только для UDP. 58 snmp_pdu_2 I Количество запросов с PDU = 2 (set-request), к текущему хосту, за последние 2 секунды. Выделяется только для UDP. 59 snmp_pdu_3 I Количество запросов с PDU = 3 (get-response), к текущему хосту, за последние 2 секунды. Выделяется только для UDP. 60 snmp_pdu_4 I Количество запросов с PDU = 4 (trap), к текущему хосту, за последние 2 секунды. Выделяется только для UDP. Отбор независимых признаков выполняется согласно алгоритму, основанному на ранжировании переменных (таблица 8), исходя из значения соответствующих коэффициентов парной корреляции между отдельными переменными. Сила связи характеризуется абсолютной величиной коэффициента корреляции. Для описания величины коэффициента корреляции используются градации, отмеченные в таблице 9. Таблица 9 – Категории корреляционной связи Значение Интерпретация до 0,2 Очень слабая корреляция до 0,5 Слабая корреляция до 0,7 Средняя корреляция до 0,9 Высокая корреляция свыше 0,9 Очень высокая корреляция На практике считается, что число наблюдений должно быть не менее, чем в 5-6 раз превышать число факторов (также встречается рекомендация использовать пропорцию не менее, чем в 10 раз превышающую количество факторов). В случае, если число наблюдений превышает количество факторов в десятки раз, в действие вступает закон больших чисел, который обеспечивает взаимопогашение случайных колебаний. Для известных классов атак были выбраны номера независимых признаков, а затем отсортированы по информативности с помощью алгоритмов Add и Del и расстояния Евклида-Махаланобиса (таблица 10) Таблица 10 – Информативные признаки для известных классов атак № Наименование класса атаки Кол-во признаков Номера признаков Метод Add Метод Dell Normal 24 0 1 2 4 5 6 7 8 10 11 13 14 16 17 18 19 20 30 31 34 35 36 37 38 7 19 38 10 6 20 8 14 13 17 37 16 18 4 36 34 30 0 5 35 1 2 31 11 2 4 35 5 1 0 31 30 34 6 7 8 10 13 14 16 17 18 19 20 36 37 38 11 1 Dos 18 0 2 6 7 8 10 13 14 15 16 17 18 19 20 21 30 31 36 8 10 13 14 15 6 16 17 18 19 20 21 0 7 36 30 31 2 31 30 0 6 7 8 10 13 14 15 16 17 18 19 20 21 36 2 2 Probe 16 0 2 4 5 6 7 8 9 11 13 14 17 18 19 20 23 5 4 6 7 8 13 14 17 18 19 20 0 9 11 23 2 2 4 6 7 8 13 14 17 18 19 20 5 9 0 11 23 3 r2l 20 0 1 2 4 5 6 7 8 13 14 16 18 19 20 22 23 30 32 34 36 1 6 7 14 19 20 36 8 13 18 34 16 22 30 5 4 0 32 23 2 22 34 1 0 23 2 32 16 5 6 7 8 13 14 18 19 20 30 36 4 4 u2r 32 0 1 2 4 5 6 7 9 10 11 12 13 14 16 17 18 19 20 21 23 25 26 29 30 32 34 35 36 37 38 39 40 25 6 7 14 19 20 21 30 10 18 37 38 40 26 29 34 1 36 39 17 32 11 13 16 35 12 5 0 23 9 2 4 4 0 2 9 23 5 1 6 7 10 11 12 13 14 16 17 18 19 20 21 25 26 29 30 34 35 36 37 38 39 40 32 Для окончательной оценки информативности признаков выполнено обобщение полученной информации и ранжирование независимых признаков, что привело к результатам, указанным в таблице 11. Таблица 11 – Ранжирование признаков по их информативности Кол-во признаков Номера признаков 36 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, Заметим, что методы Add и Dell дают одинаковые результаты слияния признаков 2.4. Метод случайного поиска с адаптацией Рассмотрим последовательность реализации данного подхода. Разобьем отрезок [0-1] на равных частей, где – количество признаков, и закрепляем каждый участок за соответствующим признаком. Запускаем датчик случайных чисел в диапазоне (0-1) и проверяем, на какой участок отрезка выпадает случайное число. Запуская датчик многократно, формируем −мерных наборов признаков случайным образом. Далее полученные наборы проверяют на качество, которое оценивается ошибкой распознавания. Среди наборов окажется один наилучший и один наихудший. Затем реализуется процедура «поощрения» и «наказания» признаков, так, чтобы признаки, которые попали в наилучший набор, были поощрены, а те, которые попали в наихудший - наказаны. Поощрение и наказание осуществляется расширением или сужением участка соответствующего признака на величину (). Если один и тот же признак попал дновременно в наилучший и наихудший набор, то его участок не меняется. После изменения размеров участков процедура формирования наборов повторяется. Через несколько итераций процесс установится т.к. отбираемые подсистемы стабилизируются и будут содержать одни и те же признаки. В это время процесс может быть остановлен, тем самым будет найден наилучший −мерный набор признаков.