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

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.10.2024

Просмотров: 100

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Организация признаковых пространств является самой ответст­ венной и наиболее трудной задачей в рассматриваемой проблеме.

I

§ 5. Другие применения алгоритмов вычисления оценок

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

1.Оценка качества экспертов, формирующих таблицу обучения

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

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

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

Будем считать, что группа экспертов Э {, ... , Эг сформиро­ вала две таблицы — таблицу обучения Тп m ,(7^) и таблицу кон­

троля Тп т.л (Т 2У

здесь п — число

признаков, задающих эта­

лонные

объекты,

т,

т! — количество строк (эталонных

объектов

в таблицах обучения и контроля

соответственно),

/ — число

классов.

В таблице

обучения классу АГ;- соответствуют строки

S m i+1 , ... , Sm , у = 1, 2 , ... , /, гп^= 0, т1— т, в таблице контро­

ля — 5,„’._1+1 , ... , Sm. , / = 1 , 2 , . . . , /, т'0 -- 0, т1= т.

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

Kj , сформированные экспертом 9 t , через

J, jS^j.

Очевидно,

100


Рассмотрим функционал качества алгоритма распознавания, основанного на вычислении оценок. Обозначим через Q число пра­ вильно распознанных объектов в таблице контроля. Положим

со (А) = Q'm';

здесь А — выбранный алгоритм распознавания, пг' — число эле­ ментов таблицы контроля.

Допустим, что нами построен алгоритм Л*, на котором до­ стигается максимум функционала о (Л). Пусть алгоритм опреде­

ляется параметрами /г,

s ,

е, , ... ,

sn,

^ , ... ,

8* .

Выделим

параметры у* , которые

в

экстремальном

алгоритме

получили

строки, сформированные экспертом

Эс,

i =

Г, 2, ...

,

Чем боль­

шую важность получили объекты, отобранные экспертом, тем выше качество данного эксперта. Поэтому мера р (З д оценки

качества эксперта' 3 Z может быть введена следующим образом. Пусть строка 5;., сформированная экспертом 3 f,.получила в эк­ стремальном алгоритме параметр 7 * [S^). Положим

г t

is u)

(V.14)

 

По'сле построения экстремального алгоритма вычисление ве­ личин р (Э.), i = 1, 2 не представляет труда. Упорядочий

номера экспертов по убыванию величины р ( З г) будем иметь

представление об их сравнительной степени квалификации. Возможен и другой подход к оценке качества ' экспертов,

формировавших таблицы обучения и контроля. Допустим, что мы снова построили алгоритм с экстремальными параметрами

Обозначим его через А* и вычислим величину ср (А*). Удалим из таблицы обучения строку S .. По новой таблице обучения

построим новый экстремальный алгоритм А? . Положим

р ф ) = «р (а *) - <? (а ; ).

Величина р (5.) характеризует изменение качества распознавания при удалении из таблицы обучения строки . Естественно счи­

тать эту величину мерой важности строки таблицы обучения. 4 Теперь можно ввести оценку качества эксперта 3 t. , г = 1 , 2 ,..., г

следующим' образом: i

Ж ) 2

2

/=» 1

SU6 l s4 )

I.

 

p ( s u ) 2 p & )

(V.15)

(

uu


Реальное вычисление р (Э.} сводится к проведению (/и+1)-

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

локально-экстремальных алгоритмов Л*, A t . Для бинарных таб­ лиц возможно полное решение оптимизационной задачи.

Знание

оценок качества р (Д,) эксперта 3 t позволяет судить

0 степени

его компетентности в формировании таблиц обучения-

В таблицах обучения необходимо оставлять те объекты, которые сформированы экспертами, имеющими достаточно высокие оценки

качества. Можно пойти

и дальше. Приняв таблицу

обучения

Тп ffl„ г сформированную

компетентными экспертами,

за исход­

ную, можно попытаться еще более сжать ее объем, исключив малоинформативные признаки и малоинформативные (в некото­ ром смысле) объекты. Исключение малоинформативных призна­ ков можно осуществить, реализовав описанные в § 2 данной главы процедуры 2 или 3, в результате чего получается новая таблица Тп, т. ( , отличающаяся от исходной Тп т, ; меньшим

числом ///

столбцов.

 

 

 

 

г необ­

Для получения в окончательном виде таблицы Тп. Н1.

ходимо теперь удалить из Тп, m„ 1 малоинформативные

строки-

объекты.

Для

этого

предварительно определяются

меры ин­

формативности

строк

следующим

образом.

Иа основе

таблиц

Т „ . и

Т , ,

подсчитывается

значение

ф (Л*).

Из

таблицы

Тп т„ ! удаляется строка St и вновь вычисляется <р(Л*). В ка­ честве меры информативности строки принимается величина

р (•$,) -- ? (А*) - (р(л*),

характеризующая изменение качества распознавания при уда­ лении из таблицы обучения строки Sr

Подсчитанные значения р (.S.), i —■1, 2 ,..., т упорядочива­

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

малоинформативных (по значению р (S ) ) строк. Контроль конца исключения объектов осуществляется слежением за уменьшением значения ср (Л*). Процедурз завершается, когда это уменьшение переходит за максимально допустимый порог Д(р(Л*).

Врезультате реализации двух описанных последовательных процедур сокращения (по признакам и объектам) получается таблица Tn, т„ , .

Внекоторых практических случаях может наблюдаться такая

ситуация, когда любое сокращение

исходной таблицы обучения

Тn m.„ 1 приводит к недопустимому

уменьшению ср (Л*). Это оз­

начает, что в качестве, Т , m„ , должна быть принята таблица

Т1 n m". I'

10?


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

малоинформативные столбцы. Можно предложить и схему с по­ очередным исключением строк и столбцов.

По-видимому, вопрос о том, какая схема является предпочти­ тельной, должен решаться с помощью проведения ряда .модельных экспериментов на ЭВМ.

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

Пусть задано множество из N объектов, являющееся метриче­ ским пространством. Классификацией называется разбиение этого множества на систему непересекающнхся множеств. Обычно в ка­ честве подмножеств берутся гиперсферы различного радиуса. По­ следнее не является необходимым, но разбиения на гиперсферы технически выполняются проще. На множестве разбиений исходной совокупности объектов задается функционал, определяющий каче­ ство разбиений (таксономии). Такой функционал вводится в [23].

Существующие алгоритмы таксономии, например, типа «Форэль» [23, 34, 74], дают лишь локальные экстремальные разбиения, так как количество возможных разбиений велико и удается даже на современных ЭВМ перебрать только некоторые из них.

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

ных объектов [33].

 

 

 

 

 

Опишем сначала общую схему такого уточнения.

которые

Предположим,

что заданы

объекты

5

, S2, ... , Sm,

каким-либо таксономическим алгоритмом разделены на I классов.

При этом в класс

попали

объекты

5 ,

5,, ... , Sm ,

в класс

АГ., — объекты 5

5

и т.

д.

и, наконец,

в класс

~

’ ••• ’ $т-

 

 

 

 

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

Рассмотрим классификацию, построенную каким-либо алгорит­ мом таксономии, и проведем серию уточняющих операций. Каж­

дый из объектов Sr

S.,, ... , Sm подвергнем процессу

опознавания

с помощью алгоритма А. Предположим, что объект

в исход­

ной классификации

был отнесен к классу АТГ Возможны два

случая:

 

 

1) величина Г (S.) дает максимальное значение из Г

- ■ О Д ;

103