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

ВВЕДЕНИЕ.•.

ГЛАВА I. Решение задачи прогнозирования состояний динамических объектов на основе синтеза методов экстраполяции и распознавания ц

§ I.I. Постановка задачи. Основные определения.*. II

§ 1.2, Описание математической модели основной задачи 9

§ 1.3. Обучение распознаванию и прогнозированию как решение основной задачи для контрольных объектов

ГЛАВА 2. Задача синтеза корректных алгоритмов распознавания и прогнозирования

§ 2.1. Построение распознающего корректора.

§ 2.2. Построение прогнозирующего корректора.

§ 2.3. Алгоритм решения основной задачи SF

§ 2.4. Вопрос об устойчивости корректного алгоритма прогнозирования

ГЛАВА 3. Программная реализация разработанных алгоритмов

§ 3.1. Описание блок-схемы алгоритма решения основной задачи &

§ 3.2. Решение задачи распознавания в диалоговом режиме

§ 3.3. Практическое применение

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

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

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

Существует большой класс задач прогнозироваия, постановка которых на отдельных этапах предполагает использование решения некоторых задач распознавания.

Для решения задач распознавания были сформированы параметрические модели с разделяющими поверхностями, потенциальными функциями, вычислением оценок и т.п, £ 10,1,19-21 J •

Одним из эффективных методов является метод распознавания, алгоритмы которого основаны на вычислении/оценок f 21 j .

В лаборатории проблем распознавания ВЦ АН СССР под влиянием работ Ю.И.Журавлева были начаты исследования по применению методов распознавания к задачам прогнозирования состояний динамических процессовf17, 23 J » наблюдаемых в сложных системах иерархической структуры £ 22 J • Дальнейшее их развитие связано с использованием алгебраической теории корректных алгоритмов распознавания [ 13-15 ] в решении задач динамического прогнозирования [ 12 ] .В работе £ 12 ] задача прогнозирования состояний динамического процесса сводится к решению одной задачи стохастического программирования, в алгебраическом замыкании модели вычисления оценок строится корректный алгоритм прогнозирования.

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

Алгебраическая теория построения корректного алгоритма, разработанная в [ 13-16 J основана на принципе синтеза алгебраического замыкания над эвристическими алгоритмами, в котором существовал бы алгоритм, дающий безошибочное решение для любой наперед заданной задачи распознавания с конечным числом объектов. Распознающие алгоритмы представляются в виде В' С > где В - распознающий оператор, С - решающее правило. Распознающий оператор В переводит описание задачи в числовую матрицу, число строк которой равно числу распознаваемых объектов, а число столбцов - числу классов. Решающее правило С переводит эту матрицу в матрицу окончательных ответов, при этом оператор С зафиксирован, Доказана теорема [l3 ] о существовании в алгебраическом расширении множества распознающих операторов 3 с введенными в нем операциями сложения, умножения и умножения на скаляр корректного распознающего оператора $ * , определяющего соответствующий корректный алгоритм. Приводится конструктивное построение корректного алгоритма /4 . Выписывается формула для вычисления степени расширения множества операторов £ , в котором существует

Г.

Корректный алгоритм /4 записывается в явном виде:

Л* = +сЛ*?AjtM.pj'KbA). ш где С - пороговое решающее правило; j - элементы информационной матрицы контрольных объектов; £ - число контрольных объектов; С - число классов; J) - построенный специальным образом распознающий оператор. Степень расширения Л имеет оценку:

Для полной записи кода корректного алгоритма требуется по крайней мере + ^ / fMfyfe-/J) чисел

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

Алгебраический подход к построению корректного алгоритма используется в теоретических исследованиях, но при решении задач распознавания большой размерности на ЭВМ приходится сталкиваться с известными трудностями. Это объясняется тем, что для записи корректного алгоритма требуется достаточно большой объем памяти.

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

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

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.

ЗАКЛЮЧЕНИЕ

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

Описан подход к построению корректных алгоритмов распознавания и прогнозирования путем последовательного применения к результатам эвристических алгоритмов соответствующих корректоров в виде линейных преобразований. Исследованы условия существования распознающего и прогнозирующего корректоров. Рассмотрен вопрос об устойчивости корректного алгоритма прогнозирования /jg . Вычисляется радиус устойчивости ^р С?} .

Описан алгоритм, допускающий программную реализацию всех шагов. Составленные программы реализованы на ЭВМ БЭСМ-6. Решение задачи распознавания в диалоговом режиме позволяет экономить машинное время. Диалоговый монитор разработанной диалоговой системы распознавания ДИСАРО функционирует в рамках мониторной системы "ДУБНА" [ 25 ].

В качестве практического применения разработанных методов решена задача прогнозирования солеобразования нефтяных скважин по исходной информации, полученной в п/о им. В.И.Ленина "Нижне-вартовскнефтегаз". Результаты работы свидетельствуют об эффективности рассматриваемого подхода к решению задачи безошибочного определения принадлежности прогнозных состояний наблюдаемых объектов к классам

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

2. Акназарова Р.Б. Об одном способе построения корректного алгоритма прогнозирования. Алма-Ата, 1984. - 14 с.

3. Акназарова Р.Б., Веселов Е.Н., Рязанов В.В. Разработка диалоговых систем распознавания. Оптимизация моделей распознавания в диалоговом режиме. М.: ВЦ АН СССР, 1984. - 15 с.

4. Акназарова Р.Б., Исаев И.В. Некоторые методы обработки информации для решения задач распознавания образов в системе "человек-ЭВМ". М.: ВЦ АН СССР, 1984. - 31 с. (в печати).

5. Акназарова Р.Б. Алгоритм прогнозирования состояний динамических объектов. М.: ВЦ АН СССР, 1984. - 15 с.(в печати) .

6. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление, вып.1, М.: Мир, 1974. - 406 с.

7. Бурова Н.К., Станевичене Л.И., Станевичюе А.-И.А.,

8. Шкляр П.Э. Система линейного программирования ЛП БЭСМ-6. -М.: ВЦ АН СССР, 1981.

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

10. Веселов Е.Н. Инструментальная система для построения диалоговых пакетов программ. Дис. . канд. физ.-матем. наук. М.: ВЦ АН СССР, 1980.

11. Гаффоров А., Зенкин А.И. Метод прогнозирования, основанный на использовании данных обучающей выборки. -М.: ВЦ АН СССР, 1982. 24 с.

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

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

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

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

16. Журавлев Ю.И., Зенкин А.И., Рязанов В.В. Алгоритм прогнозирования состояний производственных процессов. В кн.: Вопросы радиоэлектроники, серия АСУ, вып.1, М., 1974,с.32-42.

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

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

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

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

21. Зенкин А.И., Кудрявцев В.Б., Айдарханов М.Б. Задача восстановления состояний функционирования производственных комплексов. В сб. работ по матем. кибернетике, вып.2. М.: ВЦ АН СССР, 1977, с.97-139.

22. Зенкин А.И., Рязанов В.В. Алгоритмы прогнозирования состояний контролируемых объектов. Журнал вычисл. матем. и матем. физ., 1977, т.17, № 6, с.1564-1573.

23. Ивахненко А.Г., Лапа В.Г. Предсказание случайных процессов. Киев: Наукова думка, 1971. - 415 с.

24. Мазный Г.Л. Программирование на БЭСМ-6 в системе "Дубна". -М.: Наука,- 1978. 272 с.

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

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

27. Рязанов В.В. Методы оптимизации многопараметрических моделей распознавания и прогнозирования. Дис. . канд. физ.-матем. наук. М.: ВЦ АН СССР, 1976.