Алгоритмы вычисления оценок со сложными системами опорных множеств и их замыкания

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

В формальной постановке основная задача распознавания заключается в следующем: задана совокупность допустимых объектов «[51. Множество {б} представлено в виде объединения конечного числа своих подмножеств К4, Кг, К{, > называемых классами. Известна некоторая информация 1(К1 К^) 0 классах и описание объектов некоторого конечного подмножества множества {3]. В этой задаче требуется, используя только информацию IСК^, Ке) и описания объекта 3 б{3, 3, 3^}, установить для каждого класса значение свойств 5 ?

I, 1Н, 2 ,., ^ .

В настоящее время существует несколько самостоятельных методов для решения задачи распознавания в такой постановке. В работе [I] предложены алгоритмы типа потенциальных функций, в работах [2, 3] описаны статистические методы, в [30, 31] предложены алгоритмы, основанные на принципе разделения (комитетные алгоритмы), тестовые [5, 6], логико-эвристические [27, 28], алгоритмы вычисления оценок [7,8, 15] и т. д.

Предложенная Ю. И. Журавлевым модель алгоритмов вычисления оценок является одной из основных моделей алгоритмов распознавания, базирующихся на принципе частичной прецедентности. С помощью этой модели в период 1971;1985гг. было решено большое число прикладных задач с достаточно высокой точностью распознавания. Исследованию этой модели посвящены многочисленные публикации [9, 18, 24, 25, 26, 33] .

В большой серии работ [10 — 15] Ю. И. Журавлевым разработан алгебраический подход к задачам распознавания и классификации. Это направление развития теории распознавания связано с построением моделей распознающих алгоритмов и выбором в рамках модели оптимального по качеству распознающего алгоритма. Над множеством эвристических алгоритмов, составляющих модель, вводятся алгебраические операции. С их помощью выполняется расширение модели. При этом требуется, чтобы в алгебраическом расширении модели существовал алгоритм, правильно классифицирующий все объекты контрольной выборки.

Одним из центральных вопросов в алгебраической теории распознающих алгоритмов является проблема полноты модели алгоритмов [ю]. Если выбранная модель полна, то в ней существует алгоритм, классифицирующий все объекты из контрольной выборки правильно (корректный алгоритм). В [II, 12] доказана полнота линейного и алгебраического замыканий моделей распознающих алгоритмов с кусочно-линейными разделяющими поверхностями и алгоритмов вычисления оценок. При доказательстве были построены распознающие операторы, которые в совокупности образуют базис в линейном пространстве. В работах [34, 35] были получены необходимые и достаточные условия полноты, которые позволяют исследовать различные классы алгоритмов распознавания на полноту с помощью проверки специального вида условий. Особенно хорошо зарекомендовали себя при решении прикладных задач корректные алгоритмы в алгебраическом расширении модели вычисления оценок.

Центральной частью модели вычисления оценок является процесс вычисления оценки обобщенной близости между распознаваемым объектом и классом по заданным множествам признаков. К построению эффективных вычислительных процедур были посвящены работы [4, 15, 29] .

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

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

В § 1.1 приводятся основные понятия, формулировка задачи распознавания и процесс решения задачи в модели вычисления оценок.

В § 1.2 описаны эффективные вычислительные процедуры для вычисления оценок Г. (5), когда характеристические векторы систе4 мы опорных множеств алгоритма являются: а) пересечением интервала элементарной конъюнкции с шарами Хэммингаб) интервалом элементарной конъюнкциив) шаром Хэмминга.

— 7

В § 1.3 для таких систем опорных множеств получены эффективные (не требующие перебора по элементам системы опорных множеств) формулы для Г, (5) в аналитическом виде для двух фиксированных <1 функций близости и антиблизости.

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

В § 2.1 описаны методы построения оптимального алгоритма в модели вычисления оценок. Коротко перечислены существующие подходы.

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

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

В § 2.4 исследована полнота одной специальной модели вычисления оценок ТТЦу.р.е,^) и ее подмодели, где в отличие от известных моделей вычисления оценок, при формировании числовой матрицы (матрицы оценок) используется принцип алгоритмов потенциальных функций.

В третьей главе диссертации описана программная реализация разработанных в главе П алгоритмов и приведены результаты решения конфетных прикладных задач. Здесь рассмотрены прикладные задачи, возникающие в медицинской диагностике и при прогнозировании рыбного промысла. Число ошибок для таких задач при распознавании «неизвестных» объектов не превысило порога 4%, Программный комплекс написан на алгоритмическом языке РЬ/1 и реализован .на ЭВМ ЕС 1060.

В § 3.1 описываются принципы организации программного комплекса и назначение его функциональных модулей.

В § 3.2 проводится подробное описание основных параметров функциональных модулей программного комплекса.

§ 3.3 посвящен описанию двух прикладных задач, решенных с помощью программного комплекса.

Автор выражает искреннюю благодарность своему научному руководителю члену-корреспонденту АН СССР Юрию Ивановичу Журавлеву за помощь и постоянное внимание к работе.

ЗАКЛЮЧЕНИЕ

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

Получены эффективные формулы в аналитическом виде для вычисления оценок П (5) для таких систем опорных множеств. На бас зе полученных результатов разработан и программно реализован метод оптимизации для построения оптимального алгоритма по функционалу качества в модели вычисления оценок, где параметром оптимизации является система опорных множеств алгоритма.

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

Исследована полнота одной специальной модели вычисления оценок 171 и ее подмодели, где в отличие от известной модели вычисления оценок, при формировании числовой матрицы (матрицы оценок) используется принцип алгоритшв потенциальных функций.

На базе полученных теоретических результатов и алгоритглов, разработан и реализован программный комплекс на алгоритмическом языке Р1/1 для ЭВМ ЕС 1060. Программный комплекс апробирован на двух реальных практических задачах.