Файл: Журавлёв, Ю. И. Алгоритмы вычисления оценок и их применение [монография].pdf

построению с их помощью определенного набора весовых коэф­ фициентов [3, , Р2 , ... , Зл^ , позволяющего достигать удовлетво­

рительного распознавания.

Большое развитие получил подход к решению /1-задачи, назван­ ный методом потенциальных функций и использующий гипотезу компактности. Мы не будем специально останавливаться на этом методе, так как он полно освещен в периодической и даже моно­ графической литературе [2, 3]. Заметим лишь, что исследованиями авторов метода потенциальных функций доказана глубокая анало­ гия между работой персептрона, предложенного Ф. Розенблаттом [61], и алгоритмом потенциалов в пространстве рецепторов.

Из алгоритмов, решающих задачу классификации объектов с помощью заданных эталонов, на практике применяются еще два— алгоритм построения «обобщенного портрета» [11] и алгоритм «Кора» [8]. Первый заключается в построении разделяющей ги­ перплоскости, минимизирующей число ошибок на эталонном мате­ риале (при этом используются некоторые эвристические приемы), второй основан на выделении достаточных признаков (например, если классов эталонных объектов два, то достаточным признаком для первого называется признак, который на всех объектах второго

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

Пусть для каждого класса Ки, и — 1, 2, ... , I известны функ­ ция плотности вероятности р (S/Ka ) и вероятность Р( Ки) появ­ ления Ки.[ Задача классификации объектов может быть сформу­

гипотезы R , в то время как верна гипотеза Rlt. Условный риск

12

= 1 ,2 , ... ,/, которое минимизирует средний риск r(P, R). Опти­ мальным (в этом смысле) является решение, получаемое на ос­ нове байесова правила [69]. Если положить

P ( ^ ) P { S / K u) - p ( K Q)p(S/Kq)= 0 .

совокупности признаков объектов представляет собой серьезную

13

ла бы извлечение достаточного количества информации для удов­ летворительного различения классов в M R и распознавания нового

объекта S e D с помощью имеющихся эталонов.

Вопрос отбора признаков связан в первую очередь с качеством классификации. Особую важность он приобретает в системах по­ следовательного распознавания [69], в которых на протяжении всего последовательного процесса классификации необходимо вы­ бирать для измерения наиболее «информативный» признак с тем, чтобы процесс мог быть завершен как можно раньше. Для решения задачи так или иначе нужно привлечь понятие и меру информа­ тивности признака или набора с точки зрения различения классов. Поэтому эту задачу в последующем будем условно называть I-за­ дачей.

Имеется ряд подходов к решению /-задачи [7, 14, 16, 51, 70—71, 76, 77]. Упомянем лишь некоторые из них.

Льюис [76] в качестве критерия отбора и упорядочения признаков предложил использовать некоторую функцию в виде энтропии. Мерой информативности („добротности11) признака яв­ ляется число G. , выбираемое как среднее значение этой функ­

ции. G. трактуется также в виде взаимной информации признака o.j и классов Кл , ... , Кг

Мерилл и Грин [77] для отбора признаков применили критерий расхождения классов, соответствующий мощности различия меж­ ду ними.

В работе [14] предложен другой подход к решению задачи, не требующий полного знания вероятностных описаний образов и ос­ нованный на использовании разложения Карунена—Лоэва.

Интересный подход к получению эффективного пространства признаков М а разработан Г. С. Лбовым [51]. Этот метод, назван­

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

3. Задача классификации объектов без эталонов. В этой зада­

анализ некоторых других методов таксономии с исчерпывающей полнотой приведены в книге [34].

4. Задача определения затрат Q (Q-задача). Задача связана с определением суммарных затрат на систему распознавания. Если

14

Г л а в а II

АЛГОРИТМЫ РАСПОЗНАВАНИЯ, ОСНОВАННЫЕ НА ВЫЧИСЛЕНИИ ОЦЕНОК

§1. Необходимые определения

1.Алфавит признака. Пусть задана совокупность множеств

В качестве алфавитов могут выступать, например, следующие множества М.:

а) множество из двух элементов (0,1), при этом 1 — означает наличие какого-то свойства, 0 — его отсутствие;

б) множество из трех элементов (0,1, — ), при этом прочерк показывает отсутствие информации о наличии какого-то свойства, отображаемого Mt;

в) конечное, множество целых чисел {1, 2 , ... ,/г}, Содержатель­ ное значение такого признака часто отражает степень выражен­ ности соответствующего свойства;

г) множество точек интервала (а, Ь) с той же содержатель­ ной трактовкой; безусловно, содержательная интерпретация зна­ чений признаков может быть проведена и по-другому;

д) множество вероятностных мер {р.}г, определенных на фик­

сированном множестве еЖ (например, на отрезке (а, b)).

2. Объект распознавания. Под объектом будем понимать много­ мерный вектор, компонентами которого являются конкретные зна­

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

16

а столбцами — значения признаков. Такую таблицу Тпт будем называть допустимой таблицей.

4.ш-часть таблицы. Рассмотрим совокупность булевых векто­

часть таблицы Татназовем ш-частью таблицы 7лш. Строки новой

таблицы обозначим через ojSj , wS2 , ... , wSm. В дальнейшем бу­ дем рассматривать как совокупность допустимых таблиц, так и

разбиение строк по классам представим следующим образом:

Таблицу Т , строки которой разбиты на I классов, обозна­ чим через Тпт[ .

§ 2. Этапы задания алгоритмов вычисления оценок

Алгоритмы вычисления оценок определяются заданием шести основных этапов.

1.Система опорных множеств. Рассмотрим всевозможные

подмножества /И- множества II, 2, ... , /г!. Обозначим совокуп-

со

ность всех таких подмножеств через 9. Первым этапом опреде­ ления алгоритма А вычисления оценок является задание семей­ ства множеств 9Д СЙ, которое мы назовем системой опорных

множеств алгоритма А. Примерами таких систем могут быть: а) совокупность .всех элементов 9 одинаковой мощности; б) само множество 9; в) совокупность тестов таблицы Тпт1\

г) совокупность всех тупиковых тестов таблицы Тпт1.

2 -6 0