Алгоритмы вычисления оценок со сложными системами опорных множеств и их замыкания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. МОДЕЛЬ АЛГОРИТМОВ РАСПОЗНАВАНИЯ, ,ОСНОВАННАЯ НА ВЫЧИСЛЕНИИ ОЦЕНОК СО СЛОЖНЫМИ СИСТЕМАМИ ОПОРНЫХ МНОЖЕСТВ И ЭФФЕКТИВНЫЕ ФОРМУЛЫ ДЛЯ

ВЫЧИСЛЕНИЯ ОЦЕНОК.

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

§ 1.2. Построение эффективных вычислительных процедур при вычислении оценок в алгоритмах со сложными системами опорных множеств

§ 1.3. Эффективные формулы для вычисления оценок в алгоритмах со сложными системами опорных множеств

ГЛАВА П. ПОСТРОЕНИЕ АЛГОРИТМ РАСПОЗНАВАНИЯ,ОПТИМАЛЬНОГО ПО ШЖВДОНАЛУ КАЧЕСТВА В МОДЕЛИ ВЫЧИСЛЕНИЯ ОЦЕНОК.

§ 2.1. Принципы построения алгоритма распознавания оптимального по функционалу качества

§ 2.2. Построение оптимального алгоритма с системой опорных множеств в качестве параметра оптимизации.

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

§ 2.4. Исследование на полноту одной специальной модели вычисления оценок. 47.

ГЛАВА Ш. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И РЕШЕНИЕ ПРИКЛАДНОЙ ЗАДАЧИ.

§ 3.1. Организация программного комплекса и его назначение.

§ 3.2. Описание программного комплекса

§ 3.3. Решение прикладной задачи.

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

В формальной постановке основная задача распознавания заключается в следующем: задана совокупность допустимых объектов "[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. Программный комплекс апробирован на двух реальных практических задачах.

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970.

2. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М.: Наука, 1979.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979.4. 1Уревич И. Б., Журавлев Ю.И. Минимизация булевых функций и ф эффективные алгоритмы распознавания. Кибернетика, 1974,3, с. 16-20.

4. Дмитриев А.Н., Журавлев Ю.И., Креццелев Ф.П. О математических цринципах классификации предметов и явлений. Сб. "Дискретный анализ", вып. 7. Новосибирск: ИМ СО АН СССР, 1966, с. З-П.

5. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. Об одном принципе классификации и прогноза геологических объектов и явлений. Известия Сиб.отд. АН СССР, Геология и геофизика, 1968, № 5,с. 50-64.

6. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 1971, .№ 3, с. 1-11.

7. ЗЕуравлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: ФАН, 1974.

8. Журавлев Ю.И., Михалевич М. Алгоритмы распознавания, основанные на вычислении оценок для задач с пересекающимися классами. Труды ВЦ Польской АН, вып. 145, Варшава, 1974.

9. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации. Докл. АН СССР, 1976, т. 231, № 3, с. 532-535.- 72

10. Журавлев Ю.И. Непараметрические задачи распознавания образов. Кибернетика, 1976, Jß 6, с. 93-103.

11. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I. Кибернетика, 1977, № 4, с. 5-17.

12. Куравлев Ю.И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. П. Кибернетика, 1977, J6 6, с. 21-27.

13. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритшв. Ш. Кибернетика, 1978, J6 2, с. 35-43.

14. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Сб. "Проблемы кибернетики", вып. 33. М.: Наука, 1978, с. 5-68.

15. Журавлев Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных для данной контрольной выборки. Еурнал вычисл.математ. и матем. физики, 1979, .№ 3, т. 19, с. 726738.

16. Журавлев Ю.И., Зенкин A.A., Зенкин А.И., Исаев И.В., Кольцов П.П., Кочетков Д.В., Рязанов В.В. Задачи распознавания и классификации со стандартной обучающей информацией. Журнал вычисл.математики и матем. физики, 1980, т. 206, 5, с. 1294-1309.

17. Жзфавлев Ю.И., Мирошник С.Н., Швартин С.М. Об одном подходе к оптимизации в классе параметрических алгоритмов распознавания. Журнал вычисл. математики и матем. физики, т. 16, J6 I, 1976, с. 209-218.

18. Исаев И.В. Задача синтеза корректного алгоритма распознавания как задача построения минимального покрытия. Журнал- 73 вычисл. математики и матем. физики. 1983, т. 23, № 2, с.467-476.

19. Исраилов И.М. Эффективные формулы для вычисления оценок в одном классе алгоритмов распознавания. %рнал вычисл. математики и матем. физики, т. 24, № 5, 1984, с. 740-746.

20. Исраилов И.М. Об одной модели алгоритмов вычисления оценок. Журнал вычисл. математики и матем. физики, т. 23, № 2, 1983, с. 501-504.

21. Исраилов И.М. Форгдулы вычисления оценок в алгоритмах распознавания с системой опорных множеств, представших пересечением шаров и интервалов в . Журнал, вычисл. математики и математ. физики. В печати.

22. Исраилов И.М., Кольцов П.П., Кручинин Е.3. -о применении алгоритма вычисления оценок для решения задач медицинской диагностики. "Изв. АН Уз.ССР", 1981, № 5.

23. Камилов М.М. 0 программном распознающем комплексе ПРАСК-1. Сб. "Вопросы кибернетики", вып. 51, Ташкент, Ж с ВЦ АН Уз. ССР, 1972, с. 63-65.

24. Камилов М.М. Об оптимизации и некоторых применениях алгоритмов вычисления оценок. Труды Международного симпозиума по практическим применениям методов распознавания образов. М., ВЦ АН СССР, 1973, с. 246-258.

25. Камилов М.М., Абдукаримов Р.Т. Схемы решения задачи автоматической классификации объектов с помощью алгоритмов вычисления оценок. "Изв. АН Уз.ССР", серия техн.наук, 1975, }£ 2.

26. Камилов М.М., Адбукаримов Р.Т. Об одном алгоритме распознавания образов. "Изв. АН Уз.ССР", серия техн.наук, 1976, .№ 3.

27. Камилов М.М., Абдукаримов Р.Т. Логико-эвристические алгоритмы распознавания объектов, основанные на поиске признаков- 74 классов. "Изв. АН Уз.ССР", серия техн.наук, 1977, 5

28. Кочетков Д.В. О функциях близости. М.: ВЦ АН СССР, 1978.

29. Мазуров В.Д. Комитеты системы неравенств и задача распознавания. Кибернетика, 1971. гё 3, с. 140-146.

30. Метод комитетов в распознавании образов. Сб. научн. трудов АН СССР, Уральский научный центр, Свердловск, 1974.

31. Мирошник С.Н. Алгоритмы голосования с непрерывной метрикой. Кибернетика, J& 2, 1972, с. 54-63.

32. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк. Журнал вычисл. математики и матем. физики, т. 16, Jê 6, 1976, с. 1559-1570.

33. Рудаков К.В. О некоторых классах алгоритмов распознавания Общие результаты. М. : ВЦ АН СССР, 1980.

34. Рудаков К.В. О некоторых классах алгоритмов распознавания параметрической модели. М. : ВЦ АН СССР, 1980.

35. Себастьян Г.С. Процессы принятия решений при распознавании образов. М. : Изд-во Техника, 1965.

36. Дж.Ту., Р.Гонсалес. Принципы распознавания образов. Изд-во Мир, M., 1978.

37. Холл М. Комбинаторика. М. : Мир, 1970.

38. Чегис И.А., Яблонский C.B. Логические способы контроля электрических схем. Труды Математического института им. В. А. Стек-лова АН СССР. M., 1958, т. 51, с. 270-360.