Разработка математических моделей и методов тестового распознавания образов с учётом ограничений на ресурсы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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⁷.

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.