Разработка математических моделей и методов тестового распознавания образов с учётом ограничений на ресурсы тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Митрофанов, Андрей Андреевич

• Митрофанов, Андрей Андреевич
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Митрофанов, Андрей Андреевич

Введение.

Глава 1. Задача распознавания образов при ограниченных ресурсах.

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

1.2. Содержательная постановка задачи распознавания образов при ограниченных ресурсах.

1.3. Формальная постановка задачи распознавания образов при ограниченных ресурсах.

Глава 2. Способы оценки информативности признаков.

2.1. Таблицы различий.

2.2. Множество строк таблицы различий и некоторые его подмножества.

2.3. Покрытия таблицы различий и их свойства.

2.4. Дифференцирующая сила и разделяющая способность признаков.

2.5. Способы определения малоинформативных признаков.

Глава 3. Методы построения тестов с минимальными затратами ресурсов и времени.

3.1. Построение тестов с минимальными затратами ресурсов при равных затратах на измерение значений признаков.

3.2. Построение тестов с минимальными затратами ресурсов при неравных затратах на измерение значений признаков.

3.3. Методы построения тестов с минимальными затратами времени.

Глава 4. Реализация методов и исследование их характеристик.

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

4.2. Описание и результаты вычислительных экспериментов.

Введение диссертации (часть автореферата) на тему «Разработка математических моделей и методов тестового распознавания образов с учётом ограничений на ресурсы»

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

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

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

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

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

В разделе 2.1 дается определение и способ построения таблиц различий для заданного множества описаний объектов.

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

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

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

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

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

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

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

В разделе 3.3 рассматривается случай, когда работы по измерению значений признаков производятся как последовательно, так и параллельно. Даны основные понятия, связанные с сетевыми графиками работ. Приводится способ задания ограничений на порядок измерения работ. Даны описания 2-х эвристических методов формирования тестов. Первый метод позволяет учитывать ограничения на порядок измерения работ при последовательно-параллельном выполнении работ. Второй метод позволяет учитывать ограничение на максимальное число параллельно выполняемых работ.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Митрофанов, Андрей Андреевич, 2013 год

1. Андреев, А. Е. О тупиковых и минимальных тестах / А. Е. Андреев // ДАН СССР. — 1981. — Т. 256, №3. — С. 521-524.

2. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман — М.: Мир, 1979. — 535 с.

3. Баркалов, С. А. Минимизация упущенной выгоды в задачах управления проектами / С. А. Баркалов, В. Н. Бурков, Н. М. Гилязов, П. И. Семенов. — М.: ИПУ РАН, 2001. — 67 с.

4. Баркалов, С. А. Системный анализ и принятие решений / С. А. Баркалов, П. Н. Курочка, И. С. Суровцев. — Воронеж: ИПЦ ВГУ, 2010. — 652 с.

5. Бенерджи, Р. Теория решения задач. Подход к созданию искусственного интеллекта / Р. Бенерджи — М.: Мир, 1972. — 224 с.

6. Божченко, А. П. Определение региональной принадлежности папиллярного узора / А. П. Божченко, И. А. Толмачев // Проблемы экспертизы в медицине. — 2009. — №36-4. — С. 23-26.

7. Бродская, Ю. А. Алгоритм формирования ключевого набора признаков на частотной идентификационной матрице / Ю. А. Бродская // Теоретические проблемы информатики и ее приложений. — Саратов: Изд-во "Колледж", 1999. — Вып. 3. — С. 16-25.

8. Бродская, Ю. А. Распознавание образов при заданных ограничениях / Ю.А.Бродская // Доклады 11-й всероссийской конференции «Математические методы распознавания образов». — М.: ВЦ РАН, 2003. — С. 30-33.

9. Бродская, Ю. А. Алгоритм формирования кратчайших покрытий / Ю. А. Бродская // Теоретические проблемы информатики и ее приложений; Под ред.проф. А. А. Сытника — Саратов: Изд-во "Колледж", 2001. — Вып.4. — С. 40-48.

10. Бродская, Ю. А. Формирование кратчайших покрытий небулевых матриц при решении задач диагностики / Ю. А. Бродская // Мат. шестой междунар. конф. «Автоматизация проектирования дискретных систем».— Мн.: ОИПИ НАН Беларуси, 2007. — Т. 1. — С. 138-145.

11. Вайнцвайг, М. Н. Алгоритм обучения распознаванию образов "кора" / М. Н. Вайнцвайг // Алгоритмы обучения распознаванию образов; Под ред. В. Н. Вапник. — М.: Советское радио, 1973. — С. 110-116.

12. Васильев, В.И. Распознающие системы: Справочник / В.И.Васильев К.: Наукова думка, 1983. - 230 с.

13. Воронцов, К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания: дис. . канд. физ.-мат. наук: 01.01.09 / Воронцов Константин Вячеславович. — М., 1999. — 86 с.

14. Гилл, Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М. Райт // Пер. с англ. — М.: Мир, 1985. — 509 с.

15. Голенко, Д. И. Статистические методы сетевого планирования и управления / Д. И. Голенко. — М.: Наука, 1968. — 400 с.

16. Горелик, А. Л. Методы распознавания / А. Л. Горелик, В. А. Скрипкин — Изд. 4-е, испр. — М.: Высшая школа, 2004. — 261 с.

17. Горелик, А. Л. Современное состояние проблемы распознавания. Некоторые аспекты / А. Л. Горелик, И. Б. Гуревич, В. А. Скрипкин. — М.: Радио и связь, 1985. — 160 с.

18. Городецкий, С. Ю. Нелинейное программирование и многоэкстремальная оптимизация / С. Ю. Городецкий, В. А. Гришагин // — Нижний Новгород: Издательство Нижегородского Университета, 2007. — С. 357-363.

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

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

21. Дуда, Р. Распознавание образов и анализ сцен. / Р. Дуда, П. Харт; Пер.с англ. — М.: Мир, 1978. — 510 с.

22. Дюкова, Е. В. Построение распознающих процедур на базе элементарных классификаторов/ Е. В. Дюкова, Н. В. Песков // Математические вопросы кибернетики; Под ред. О. Б. Лупанова. — М.: Физматлит, 2005. — Т. 14.

23. Журавлев, Ю. И. Экстремальные задачи, возникающие при обосновании эвристических процедур / Ю. И. Журавлев // Проблемы прикладной математики и механики. — М.: Наука, 1971. — С. 67-75.

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

25. Журавлёв, Ю. И. «Распознавание». Математические методы. Программная система. Практические применения. / Ю. И. Журавлёв, В. В. Рязанов, О. В. Сенько — М.: ФАЗИС, 2006. — 176 с.

26. Загоруйко, Н. Г. Прикладные методы анализа данных и знаний / Н. Г. Загоруйко — Новосибирск: ИМ СО РАН, 1999. — 270 с.

27. Загоруйко, Н. Г. Методика отбора показателей для рейтинговой оценки деятельности кафедр университета / Н. Г. Загоруйко, С. С. Донецкая, С. Н. Рыскулов // Университетское управление: практика и анализ. — 2006.6. —С. 25-31.

28. Загоруйко, Н. Г. Гипотезы компактности и Л-компактности в методах анализа данных / Н. Г. Загоруйко // Сиб. журн. индустр. математики. — 1998. — Т.1,№. — С. 114—126.

29. Искусственный интеллект: в 3-х кн. Кн. 2. Модели и методы / Под ред. Д. А. Поспелова — М.: Радио и связь, 1990. — 304 с.

30. Ким, Дж.-О. Факторный, дискриминантный и кластерный анализ. / Дж.-О. Ким, Ч. У. Мьюллер, У. Р. Клекка, М. С. Олдендерфер, Р. К. БлэшфилдМ.: Финансы и статистика, 1989. — 215 с.

31. Колесникова, С. И. Методы анализа информативности разнотипных признаков. / С. И. Колесникова // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2009. — Вып. 1(6). — С. 69-80.

32. Конвей, Р. В. Теория расписаний / Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер. — М.: Наука, 1975. — 362 С.

33. Константинов, Р. М. О комбинаторно-логическом подходе к задачам прогноза рудоносности / Р. М. Константинов, 3. Е. Королева, В. Б. Кудрявцев // Проблемы кибернетики. — М, 1976. — Вып. 31. — С. 553.

34. Косоруков, О. А. Исследование операций / О. А. Косоруков, А. В. МищенкоМ.: Экзамен, 2003. 446 с.

35. Костюков, А. В. Повышение операционной эффективности предприятий на основе мониторинга в реальном времени / А. В. Костюков, В. Н. КостюковМ.: Машиностроение, 2009. — 192 с.

36. Кудрявцев, В. Б. Теория тестового распознавания / В. Б. Кудрявцев, А. Е. Андреев, Э. Э. Гасанов — М.: Физматлит, 2007. — 320 с.

37. Куфарева, И. Б. Тестирование конечных автоматов в контексте: метод синтеза проверяющих тестов на основе сетевого эквивалента / И. Б. Куфарева, В. Н. Тренькаев // Вестник Томского государственного университета. — 2003. —№278. — С. 122-128.

38. Манд ель, И. Д. Кластерный анализ / И. Д. Манд ель — М.: Финансы и статистика, 1988. — 176 с.

39. Миркин, Б.Г. Анализ качественных признаков. (Математические модели и методы) / Б. Г. Миркин — М.: Статистика, 1976. — 168 с.

40. Новоселова, Н. А. Эволюционный подход к выделению информативных признаков в задачах анализа медицинских данных / Н. А. Новоселова, А. С. Мастыкин, И. Э. Том // Искусственный интеллект. — 2008. — № 3. — С. 105-112.

41. Песков, H. В. Поиск информативных фрагментов описаний объектов в задачах распознавания: дис. . канд. физ.-мат. наук: 05.13.17 / Песков Николай Владимирович. — М., 2004. — 67 с.

42. Потапов, А. С. Распознавание образов и машинное восприятие: Общий подход на основе принципа минимальной длины описания / А. С. ПотаповСПб.: Политехника, 2007. — 548 с.

43. Розен, В. В. Цель-оптимальность-решение (математические модели принятия оптимальных решений) / В. В. Розен — М.: Радио и связь, 1982. — 168 с.

44. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: дис. . д-ра физ.-мат. наук: 05.13.17 / Рудаков Константин Владимирович. — Вычислительный центр АН СССР, 1992. —274 с.

45. Сафронов, К. В. Применение алгоритмов оптимизации для решения задачи распознавания образов / К. В. Сафронов, И. М. Чушенков, X. Вёрн // Матер, всерос. молодёжи, науч.-техн. конф. — 2007. — Т. 3. — С. 46^7.

46. Соловьев, Н. А. Тесты: (теория, построение, применение) / Н. А. Соловьев,Новосибирск: Наука, 1978. — 189 с.

47. Сытник, А. А. Интеллектуальные средства восстановления правильного функционирования технических систем / А. А. Сытник // Интеллектуальные средства диагностирования РЭА. — Ленинград, 1991. — С. 51-53.

48. Taxa А. Хемди. Введение в исследование операций / Taxa А. Хемди — М.: Вильяме, 2005. —912 с.

49. Твердохлебов, В. А. Логические эксперименты с автоматами / В. А. Твердохлебов — Саратов: Изд-во Саратовского университета. 1988. — 184 с.

50. Твердохлебов, В. А. Математические модели в технической диагностике /B. А. Твердохлебов // Методы и системы технической диагностики: межвуз. сб. науч. тр. — Саратов: Изд-во Сарат. ун-та, 1991. — Вып. 16. — С. 29-38.

51. Ту, Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес; пер. с англ. И. Б. Гуревича; под ред. Ю. И. Журавлева — М.: Мир, 1978. — 411 с.

52. Хогдал, Дж. Анализ и диагностика компьютерных сетей. Просто и доступно / Дж. Хогдал; пер. с англ. М. Кузьмин. — М.: «Лори», 2001. — 362 с.

53. Чегис, И. А. Логические способы контроля работы электрических схем / И. А. Чегис, С. В. Яблонский // Труды математического института им. В. А. Стеклова. — 1958. — Т. 51. — С. 270-360.

54. Янковская, А. Е. Исследование эффективности генетического поиска оптимального подмножества безызбыточных тестов для принятия решений / А. Е. Янковская, Ю. Р. Цой // Искусственный интеллект. — 2006. — № 2. —C. 257-260.

55. Янковская, А. Е. Алгоритмы построения логических тестов в пространстве к-значных и номинальных признаков в системе распознавания образов / А. Е. Янковская, А. Н. Кузоваткин // Искусственный интеллект. — 2002. — №2. —С. 330-337.

56. Alok Sharma Approximate LDA Technique for Dimensionality Reduction in the Small Sample Size Case / Alok Sharma, Kuldip Paliwal // Journal of Pattern Recognition Research — 2011. — Vol. 6 №. 2 — P. 298-306.

57. Clarke, E. M. Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications / E. M. Clarke, E. A. Emerson, A. P. Sista // ACM Transactions On Programming Languages and Systems. — 1986. — Vol. 8, № 2.

58. Dash, M. Feature selection for classification / M. Dash // Intelligent Data Analysis. — 1997.—Vol. 1, No 3. —P. 131-156.

59. Fleming, Q. W. Earned Value Project Management / Q. W. Fleming, J. M. Hoppclman. — PMI, 1996. — 141 p.

60. Fleming, Q. W. Taking Step Four with Earned Value: Establish the Project Baseline / Q. W. Fleming, J. M. Hoppclman // PM Network. — 1995. — № 5. — P. 26-29.

61. Hall, M. A. Correlation-based feature selection for machine learning. / M. A. Hall // PhD thesis, Department of Computer Science, University of Waikato, Hamilton, New Zealand. — 1998. — 178 p.

62. Hildebrandt, R. The book of Postfix : state-of-the-art message transport / R. Hildebrandt, P. Koetter — San Francisco: No Starch Press, 2005. — 496 p.

63. Payri, B. Limitations in the Recognition of Sound Trajectories as Musical Patterns Электронный ресурс. / Bias Payri — Режим доступа: http://www.smcnetwork.org/files/proceedings/2010/11 .pdf (дата обращения: 15.11.2012).

64. Rosenblatt F. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms / Frank Rosenblatt — Washington, DC: Spartan Books, 1962. — 616 c.