автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Конструктивизация моделей классификации конечных объектов: концепция, методы и компьютерная реализация

На правах рукописи

Ж

КАЛЯДИН НИКОЛАЙ ИВАНОВИЧ

УДК 519.712 + 510.25 -+- 510.67

КОНСТРУКТИВИЗАЦИЯ МОДЕЛЕЙ КЛАССИФИКАЦИЙ КОНЕЧНЫХ ОБЪЕКТОВ: КОНЦЕПЦИЯ, МЕТОДЫ И КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ

.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

і о "::•;! тз

Екатериїїбург — 2013

005061992

Работа выполнена на кафедре «Прикладная математика и информатика» ФГБОУ ВПО «Ижевский государственный технический университет имени М.Т. Калашникова» (ИжГТУ имени М.Т. Калашникова)

Официальные оппоненты: Бельтюков Анатолий Петрович, доктор физико-математических наук, профессор, ФГБОУ ВПО «Удмуртский государственный университет», заведующий кафедрой «Теоретические основы информатики»;

Дикусар Василий Васильевич, доктор физико-математических наук, профессор, ФГБУН «Вычислительный центр им. A.A. Дородницына Российской академии наук», ведущий научный сотрудник сектора методов оптимизации;

Мазуров Владимир Данилович, доктор физико-математических наук, профессор, ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина», профессор кафедры «Эконометрика и статистика».

Ведущая организация: ФГБУН Институт механики УрО РАН, г. Ижевск

Защита состоится «26» июня 2013 г. в 13 чалов на заседании диссертационного совета Д 212.285.25 на базе ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина» по адресу: 620000, г. Екатеринбург, пр. Ленина, 51, зал заседаний диссертационных советов, комн. 248.

С диссертацией можно ознакомиться в библиотеке ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

Автореферат разослан ......М.Я.Я...........2013 г.

Ученый секретарь диссертационного совета доктор физико-математических наук,

профессор ( ' Пименов В.Г.

Общая характеристика работы

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

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

В основе современных наиболее развитых подходов в распознавании образов, таких как статистические методы3, комитетпные конструкции4 5, распознавание по прецедентам6 7, нейронные cemtfi лежит предположение о выполнении гипотезы компактности9 10:

1 Конструктивизация образов, моделей объектов и т. п. вводится согласно сложившимся основным понятиям конструктивной математики, в частности, конечный (конструктивный) объект есть образ, описываемый конечным объемом информации.

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

3Валник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974. — 400 с.

4Мазуров В. Д. Метод комитетов в задачах оптимизации и классификации. — М.: Наука, 1990. — 248 с.

5Mazurov Vl.D., Khachay M.Yu., Rubin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Predication. // Proceedings of the Steklov Institute of mathematics. Suppl.l, 2002. — Pp. 67-101.

6Журавлев Ю.И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов // Кибернетика. — Ч. 1, — 1977. — № 4. — С. 5-17; — Ч. 2, 1977. — № 6. - С. 17-24; - Ч. 3, 1978. — № 2. — С. 35-43.

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

8Загоруйко Н.Г. Методы распознавания и их применение. — М.: Сов. радио, 1972. — 203 с.

9Белозерский Л.А. Современный взгляд на гипотезу компактности // Искусственный интеллект. — Донецк, 2005. — № 3. — С. &-12.

10Гуров С.И., Потепалов Д.Н., Фатхутдинов И.Н. Решение задач распознана- /

«...образам соответствуют компактные множества в пространстве выбранных свойств».

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

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

Проблемами разрешимости и вычислимости различных конкретных теорий фундаментальных наук занимались многие зарубежные и отечественные математики: Barwise D., Bernaus Р., Blum M., Co' hen P.L., Chang C.C., Church A., Cutland N., Enderton H., Feferman S., Godel К., Goodstein R.L., Hilbert D., Jensen R., Keisler H.J., Kleene S.C., Lachlan A.H., Macintyre A., Post E., Robinson D., Rogers H., Sacks G., Scott D.S., Shelah S., Shoenfield J.R., Sikorski A., Tarski A., Turing A., Penrose R., Van der Waerden B.L. и другие;

Адян С.И., Барздпнь Я.М., Бельтюков А.П., Гончаров С.С., Ершов Ю.Л., Журавлев Ю.И., ЗаславскийИ.Д,, Колмогоров А.Н., Куш-нер В.А., Мазуров Вл.Д., Мальцев А.И., Марков A.A., Маслов С.Ю., Матиясевич Ю.В., Минц Г.Е., Нагорный Н.М., Новиков П.С., Орев-ков В.П., Палютин Е.А., Перетятькин М.Г., Тайманов А.Д., Трах-тенброт Б.А., Успенский В.А., Цейтлин Г.С., Шанин H.A., Шрей-дер Ю.А., Яблонский C.B., Якубович С.М. и многие другие.

Фундаментальные результаты о разрешимости и вычислимости в конструктивных моделях для теорий получены научной школой академика РАН Ю.Л. Ершова11, но в распознавании образов подобных работ достаточно мало.

Выделим две отечественные научные школы, где традиционными математическими методами впервые ставились и исследовались вопросы разрешимости и вычислимости в распознавании образов.

1. Предложенная в начале 70-х гг. прошлого века Вл.Д. Мазуро-

ния с невыполненной гипотезой компактности // Всеросс. конф. ММРО-13. — М.: МАКС Пресс, 2007. - С. 27-29.

11 Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. — М.: Наука, 1980. — 416 с.

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

Вл.Д. Мазуровым и его учениками М.Ю. Хачаем, А.И. Рыбиным, А.И. Кривоноговым, Ю.А. Зуевым, Н.Г. Белецким сформулированы и доказаны теоремы существования комитетных решений для различных систем ограничений. М.Ю. Хачай12 всесторонне исследовал вопросы вычислительной сложности задач о минимальном комитете.

2. Академиком РАН Ю.И. Журавлевым введены основопологаю-щие понятия (разрешимость, регулярность, полнота) в некорректных (эвристических) информационных моделях, позволяющие синтезировать «прямыми методами» корректные, т.е. точные на прецедентах, алгоритмы классификации.

Задача — разрешима, еслн существует ее решение; задача называется регулярной, если она разрешима и разрешимы также все задачи, отличающиеся от нее лишь набором значений решений на объектах обучения. Под полнотой семейства алгоритмов погашается существование в нём решений для всех регулярных задач.

Представителями научной школы Ю.И. Журавлева в дальнейшем более детально исследованы введенные им понятия. Выполненный К.В. Рудаковым13 углубленный анализ ограничений для задач классификации расширил область их применений за счет привлечения морфизмое категорий.

A.A. Черепнин14 рассмотрел класс задач с различными оценками радиусов разрешимости и регулярности.

Ю.В. Чехович15 получил критерии локальной разрешимости и локальной регулярности в задачах выделения трендов.

A.C. Вальков16 предложил критерии разрешимости и регулярно-

12Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете и смежных задач // Доклады РАН. - 2006. - Т. 406, № 6. - С. 742-745.

13Рудаков К.В. Об алгоритмической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. - М.: Наука, 1989. Вып. 1. — С. 176-201.

14Черепнин A.A. О радиусах разрешимости и регулярности задач распознана^ ния // Всеросс. конф. ММРО-11. — М.: Регион-Холдинг, 2003. — С. 210-211.

15Чехович Ю.В. Мощности окрестностей в задачах выделения трендов // Всеросс. конф. ММРО-11. — М.: Регион-Холдинг, 2003. — С. 215-216.

16Вальков A.C. Задачи распознавания с отношением соседства на объектах. Критерии разрешимости и регулярности // Всеросс. конф. ММРО-Ю. — М.:

сти в задачах распознавания с отношением соседства на объектах.

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

Последнее вызывает необходимость проведения дополнительных исследований одной из перспективных версий прецедентного подхода — использование логических закономерностей-предикатов над числовыми и/или символьными данными в концепции поэтапной конструкта визацгт в классификации образов: разрешимость, вычислимость и реализуемость на моделях классификации конечных объектов.

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

- проблема разрешимости моделей классификации конечных объектов (в дальнейшем просто — проблема разрешимости) состоит в следующем: существует ли алгоритм, который по описанию на языке расширенного исчисления предикатов устанавливает принадлежность исследуемого объекта к рассматриваемому множеству М или

к

к одному из классов разбиения 5 ^ {М\, М^,..., Мк}, М = и М»;

¿=1

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

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

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

АЛЕВ-В, 2001. — С. 17-20.

17Горелов Ю.И. О разрешимости и регулярности задач управления, решаемых в рамках теории распознавания образов // Всеросс. конф. ММРО-Ю. — М. : АЛЕВ-В, 2001. — С. 33-34.

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

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

Научная новизна. Отметим элементы новизны результатов диссертации, выносимые на защиту.

1. Разработан на единой методологической основе теоретико-модельный подход к проблеме классификации, позволивший получить новые критерии (не)разрешимостн моделей классификации конечных объектов.

2. Исследованы вопросы представимости и вычислимости описания конечных объектов с целью оптимизации вычислительных затрат при компьютерной реализации алгоритмов классификации:

- получены новые методы сокращения длины описания конечных объектов, что равносильно уменьшению требуемого объема памяти классификатора;

- найдены впервые необходимые и достаточные условия существования предельно быстрой (симультанной) модели классификации;

- получены новые методы сокращения времени классификации в моделях, допускающих распараллеливание;

- рассмотрены быстрые спектральные преобразования Адамара - Уолша.

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

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

5. Пред пожен метод представления предикатами Радемахера все-

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

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

Практическая ценность работы.

I. В области обработки текстурных изображений.

Разработанный под научным руководством автора диссертации аппаратно-программный комплекс АРМ-Д для дешифрирования аэрокосмических снимков нашел практическое применение в технологиях двойного назначения, где носителями информации являются текстурные изображения: в авиации (аэроснимки тестовых трасс полета), медицине (рентгеновские снимки, материалы цито-, гистологических и эндоскопических исследований), технике (металловедение — шлифы металлов, сварных швов), экологии (аэроснимки зон экологического загрязнения).

Опытные образцы комплекса АРМ-Д и комплекса АМК (автоматизированное изготовление издательских оригиналов тематических карт) внедрены в ПГО «Гидроспецгеология* Мингео СССР (г. Москва, 1988 г.), Госцентре «Природа» (г. Москва, 1990 г.).

Методика обработки текстурных изображений на комплексе АРМ-Д использована при интерпретации результатов машинного анализа аэроснимков (ОКБ «Интеграл» при ЛГУ, г. Ленинград, 1988 г.), для компьютерной диагностики заболеваний костей (остеопороз) человека (Курганское НИИ экспериментальной и клинической ортопедога (г. Курган, 1988 г.), Маммологический центр Удмуртии (г. Ижевск, 1995 г.)); компьютерной диагностики онкопатологий человека (Республиканский онкологический диспансер (г. Ижевск, 1994-1999 гг.).

И. В компьютеризации медицинских технологий.

Разработан и внедрен комплекс алгоритмов и программ по компьютерному анализу и прогнозированию (1940-2020 гг.) заболеваний населения Удмуртии (онкологических, психических, инфекционных).

Разработаны, испытаны и внедрены первые в России отечественные мониторио-компыотерные системы для "медицинских учрежде-

ний г. Ижевска (медсанчасть №7,1992 г.; Iя Республиканская клиническая больница, 1994 г.; Республиканский клинический кардиологический диспансер, 1999 г.).

В работе представлены акты внедрения от Уральского регионального отделения Академии медико-технических наук Российской Федерации, ОАО «Ижевский Мотозавод «Аксион-Холдинг», ФГУП «Ижевский механический завод», ОАО «Ижевский электромеханический завод «Купол».

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

Научно-технические конференции Ижевского механического института (Ижевск, 1975-1991); Всесоюзный симпозиум «Машинные методы обнаружения закономерностей» (Новосибирск, 1976); IV Всесоюзная конференция «Автоматизация ввода письменных знаков в ЦВМ» (Каунас, 1977); VII Всесоюзная конференция «Теория кодирования и передачи информации» (Москва, 1978); I, IV Всесоюзная конференция «Методы и средства обработки сложноструктурированной семантически насыщенной графической информации» (Горький, 1983; Нижний Новгород, 1998); Всесоюзная конференция «Обработка изображений и дистанционные исследования» (Новосибирск, 1984); VIII Всесоюзная конференция «Автоматизация в тематической картографии» (Москва, 1984); VI Всесоюзное совещание «Проблемы автоматизации анализа изображений микроструктур» (Пущино, 1984); 2е Всесоюзное совещание «Космическая антропология: техника и методы исследования» (Ленинград, 1984); II, III Всесоюзная конференция «Математические методы распознавания образов» (Рига, 1987, 1989); IX научные чтения по космонавтике (Москва, 1988); Международная конференция ОИДИ-ЭО (Новосибирск, 1990); Iя Всесоюзная конференция РОАИ-1-91 «Распознавание образов и анализ изображений» (Минск, 1991); II Международная конференция «Математические алгоритмы» (Нижний Новгород, 1995); Международная конференция «Математическое моделирование в науке и технике» (Ижевск, ИПМ УрО РАН, 1995 г.); III Всероссийская конференция РОАИ «Распознавание образов и анализ изображений: новые информационные технологии» (Нижний Новгород, 1997); научно-технические конференции ИжГТУ (Ижевск, 19912004); VI Всероссийская с участием стран СНГ конференция «Мето-

ды и средства обработки сложной графической информации» (Нижний Новгород, 2001); научная конференция-семинар «Теория управления и математическое моделирование» (Ижевск, 2006); Международная конференция «Теория управления и математическое моделирование», посвященная памяти д. ф.-м. н., проф. Азбелева Н.В., организатора Ижевского математического семинара (Ижевск, 8.05.2008); научный семинар ИММ УрО РАН (г. Екатеринбург, 16.10.2009).

Работа поддержана грантами РФФИ (03-01-00255,04-01-96016,0601-0074).

Прикладные результаты отражены в отчетах о НИОКР, выполненных под руководством автора в рамках государственных, отраслевых и целевых научно-технических программ.

Публикации и личный вклад автора. Основные результаты диссертации опубликованы в 44 работах, из которых 28 — в рецензируемых журналах и изданиях, определенных ВАК. Список публикаций приведен в конце автореферата. Из совместных работ в диссертацию вошли результаты, полученные лично автором.

Структура и объем работы. Диссертация состоит из введения, четырех глав, объединяющих 20 параграфов, заключения, приложения и списка литературы из 263 наименований. В работу включены 47 рисунков, 7 таблиц и акты о внедрении результатов работы. Общий объем работы 339 страниц.

Краткое содержание работы

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

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

Первая глава (§§1-4) посвящена разрешимости конструктивных моделей классификации конечных объектов.

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

определяются конкретной физической природой распознаваемых объектов или явлений.

исходного описания образа х € М для перехода от физической или семантической модели к математической.

Пусть М — исходное множество классифицируемых (распознаваемых) образов х произвольной природы; К — множество конструктивных (конечных) объектов; <р : М —> К — функция кодирования классифицируемых (распознаваемых) образов х конечным множеством из К.

О {Хх, ЗС2,..., Хт} — обучающая выборка — семейство множеств г € Зт ^{1,2,..., т}, то есть набор известных реализаций (описаний) ЗС; классифицируемых (распознаваемых) образов х.

X — неизвестная реализация классифицируемого (распознаваемого) образа х.

5 (Лз,..., 914} — разбиение обучающей выборки на классы

(эталоны) 91,, 2 6 Ъ ^ {1,2,...,«}; ^ П Щ = 0 для г ф j.

/ : 37П —* Зг — классифицирующая функция, закрепляющая номера г 6 Зт элементов обучающей выборки X; £ О за номерами эталонов — классов 6 5, € Зг-

Тогда функции цели задач распознавания, классификации п идентификации, определим через предикаты [о]18 следующим образом.

1. Распознавание:

Первым шагом при конструктивизации является формализация

(У.г Є М)(ЭХ Є К)\Х€ <р(М{)] = |

1, если X е <р(М{) С К, О, в противном случае.

2. Идентификация:

(У£єО)Г£ = £І] = |

1, если X = Х{, г € Зт, О, в противном случае.

3. Классификация:

если £ Є 91, , у & Ои в противном случае.

18Минский М., Пейперт С. Персептроны. — М.: Мир, 1971. — 261 с.

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

В предложенном подходе (§1) к распознаванию образов показано, как сочетание геометрических и лингвистических установок при описании образов на языке расширенного исчисления предикатов в выбранном спыстралъном пространстве определяет экзистенциалъ-ностъ, то есть возможность анализа проблемы классификации на разрешимость.

Определение I.19 Пара Я ^ (М, ) называется входным пространством распознающей системы, если выполняются следующие аксиомы:

у з хп у {существование толерантности),

(Ао) V Дм С п (рефлексивность), Дм = {(х, ж)| х € М},

*€£»+

М,) у П = тГ1 (симметричность),

(Ал) V (* < я) = (п С г3) (упорядоченность),

) у Г(ГЯ С п+з (квазиаддитивность),

где — класс отношений толерантности (сходства) на множестве М, индексированный множеством неотрицательных вещественных чисел Г>+, ТО есть То+ — {п }<€£>+•

Пусть заданы дополнительно:

р _ мера На множестве М из входного пространства Я;

Р — множество некоторых элементарных предикатов на множестве М; _

У {МиМъ...,Мт}, м< с м, г = 1,т, причем каждый класс

(образ) Л/,- описывается некоторой логической комбинацией элементарных предикатов рз(х) € Р : М, = {х € М| ¿<[рг(х), (х)]}, где - некоторая пропозициональная функция, з = 1,к{.

Определение 2. Набор (Я,Р,У» называется логической моделью распознавания, если выполняются следующие аксиомы:

19В автореферате принята независимая от текста диссертации система нумерации соотношений и утверждений

{/(%) V V ( 3 хтгу -» 3 хт£г) (связность), е£П+ хйЬи \У€М, /

(/<Г2) з у хпу (ограниченность),

(К3) Б = 1,(Ь> 0) (объемность),

(К*) 2 (МГ) = ^(Л/ДМГ), (о < < 1) (отделимость).

Определение 3. Модель распознавания (Д, Р, V, ц) называется спектрально-логической, если:

1) М = Г>то, где Пт — т- я декартова степень множества вещественных чисел;

2) м — есть лебеговская мера в т-мерном пространстве Вт\

3)Т0+ — класс отношений толерантности, элементы которого определены с помощью евклидовой метрики на М :

xrty ==

(х< ~ У*)1

.1=1

В спектрально-логической модели описание любого объекта распознавания х € М может быть произведено с помощью упорядоченного набора числовых коэффициентов, определяющего некоторую точку в пространстве Dm. Такие наборы чисел и есть спектры в самом широком понимании этого термина (Трахтман A.M.).

В рамках спектрально-логического подхода осуществляется поиск критериев разрешимости и вычислимости моделей классификации конечных объектов. С этой целью исходное множество объектов из М редуцируется к множеству всех натуральных чисел N ^ i=i {0,1,2,...} через отображение ip : М N. Пара (M,ip) объявляется множеством конструктивных (конечных) объектов, если при этом ¡р — взаимно однозначное отображение, то пара (М, (р) называется множеством сильно конструктивных объектов.

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

Пусть Ш ^ <p(M),Tl с Ф — семейство всех конечных подмножеств множества N ^ {0,1,2,...}; S^ {9ti}i€3 - разбиение семейства Ш, где 3 не более чем счетное индексное множество; 7 : JV —> Ф — стандартная нумерация.

Рассмотрим модель (Ш; 6) с основным множеством Ш и сигнатурой в ^ (Рі)ієз > гДе предикаты Рі (Ж) будем интерпретировать следующим образом: (У£ Є ЯЛ) [Рі (x) = 1 X Є 91»].

Вопрос о разрешимости предиката Рі (X) назовем проблемой ■распознавания для класса Учитывая, что Рі(Х) = 1— Хаі(7~1(Х)), где ХАі — характеристическая функция множества А» ^ то

в силу тезиса Чёрча справедливо

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

Вопрос о существовании алгоритма, позволяющего указать номер і класса Є 3, для которого Рі (X) = 1, где X Є Ф, назовем проблемой классификации для разбиения Я семейства Ш С Ф.

Предложение 2 (критерий разрешимости 2). Проблема классификации для разбиения Б ^ семейства Ш разрешима тогда и только тогда, когда 3 конечно и для всякого і Є З [Ш» — сильно рекурсивно].

Отношение ^т (т-сводимости) позволяет расширить критерий разрешимости (предложение 2) для различных конечных объектов (множеств, кортежей, отношений) в виде

Следствие 1. Если проблема классификации для разбиения в ^ ...,91г} семейства Ш разрешима, В ^ {їй}, 212, ...,21г} такое разбиения семейства £, что для любого і ^ г Є N [7""1 (Оіі) — прообраз стандартной нумерации элементов разбиения В т-сводит-ся к прообразу 7_1 (91і) стандартной нумерации элементов разбиения Б, то есть у~1 (ЗІ,) 7-1 (9Ї*)], то проблема классификации для разбиения В семейства £ разрешима.

В практике классификации встречаются случаи, когда множество (р(М) С N соответствует частично разрешимым предикатам. Тогда справедливо

Предложение 3 (критерий неразрешимости 1). Пусть (М, (р) — множество конструктивных объектов таково, что </?(М) рекурсивно перечислимо, но не рекурсивно. Тогда для любого конечного разбиения К множества М проблема классификации для тройки {М, Я, <р) не является разрешимой.

Поставленная таким образом задача классификации допускает многоам,ьтернативное решение. Одним из условий сокращения альтернатив является требование к функции 'р : М —> N обладать взаимной однозначностью, то есть когда {М, ¡р) — сильно конструктивные объекты.

Более общим условием однозначного принятия решений является требование попарного непересечеюш множеств и <р(М)) (г ф

Ф 3 £ Зт ) для исходного разбиения множества М.

Определение 4.20 Семейство Фо С Ф конечных множеств называется сильно перечислимым (сильно рекурсивным), если множество 7-1 (Фо) рекурсивно перечислимо (рекурсивно).

Вводя Ф„ С Ф как сильно перечислимое (сильно рекурсивное) мнолсество в сужении Д : М —» Ф, А = 7для стандартной нумерации 7 : Аг —► Ф, получим

Предложение 4 (критерий неразрешимости 2). Пусть А (М) сильно перечислимо, но не сильно рекурсивно. Тогда для любого конечного разбиения К множества М проблема классификации для тройки (М, Я, А) не является разрешимой.

В силу однозначности и вычислимости нумерация 7 сводит проблему классификации для тройки (А/, Я, А) к уже известной проблеме классификации для тройки (М, Я, ¡р) :

Предложение 5. (критерий разрешимости для (Л/, Я, А)). Проблема классификации для тройки. (А/, Я, А) разрешима тогда и только тогда, когда (УМ* € Я) [А(АЛ) сильно рекурсивн$.

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

Сформулированы (§3) условия однозначной разрешимости (существования и единственности решений) для моделей классификации, допускающих распараллеливание в известных решающих правилах: моделей Вальда, Лапласа, Сэвиджа, Евклида, коллективного голосования и сильного голосования.

20Ершов Ю.Л. Теория нумераций. -М.: Наука, 1977.- 416с.

Вторая глава (§§5-11) посвящена проблеме вычислимости разрешимых моделей классификации конечных множеств; при этом рассмотрены две ситуации: когда элементы множеств максимально различны и, наоборот, когда наблюдается сильное пересечение («сцепление») множеств.

В зависимости от «силы сцепления» множеств определяются возможные пути к построению различных по эффективности вычислений предикатов классификации.

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

Теорема 1(о существовании информативных элементов). Пусть (V. € Ъ) № ф 0} и (Уг фз £ Зг) [Чц = 1 => Ял = 0] - Тогда существует I информативных элементов а,- € ^ + таких, что предикат классификации

вг (X) = \аг 6 £1 &

V [а,- € X] & Яц

обращается в «единицу> тогда и только тогда, когда X = где ХеОо, - индексные множества, получаемые по рекуррентной

схеме:

= / если ф 0; = V).

* \ в противном случае.

элементы вспомогательной логической матрицы д = \\qijW ■

= Г 0, еслиУ?\Х]ф0; ^ \ 1, в противном случае.

Следствие 2. Пусть О = ||и»,-|| таково, что (V* 6 3{) [ЗЦф0] « (V* 6 Зг) ^и^ЗЕ,- ^ 0] • Тогда существует I информативных элементов а< € таких, что предикат М4 (ж) =

_ ( 1, если а* = ху, где - _ / ___)Жг1у е о, и индекс ] вы-

1 0,в противном случае, бран из условия с,- - с, < % < с^ обращается в «единицу» тогда и только тогда, когда х = щ е О.

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

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

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

С каждым разбиением S ^ {9ti, ...,0tr} семейства Ш связана модель (Ш; &) с основным множеством Ш и сигнатурой © ^ (Pi,..., Рг) ■

Одноместные предикаты классификации Р, на модели (ЯЯ; €>) интерпретируются так: (VX Є TI) [P¿ (X) = 1 ^ X € 9t¿, (і = V1)].

Ставится следующая задача минимизации предикатов классификации: для любого разбиения S ^ {9li, ...,ОТГ}, (і — Х,г) семейства ШТ найти г минимальных (по числу элементов) подмножеств Sі Є ü(9Jt) для вычисления предикатов Р»(Х) модели {Ш\ &) с помощью подмножеств Si (системы подмножеств).

Через S обозначим класс всех разбиений S элементов из ЗИ.

Предложение 6. Для любого разбиения S є S2 и для любого г є Эт, где т — номер разбиения S, если [qij — 1 —► qji = 0],

то Рі (X) --- Ri (X) &-

V Rk(X)hqik

кЄОт\{і]

■{i

. если Si Л O (71 (і)) Ф 0, i,j Є 3m; (',J • п в противном случае,

0(71(1)) — объединение образов гёделевой нумерации 71-

Задача классификации для разбиений 5 из семейства Ш эффективно решается путем построения процедур для вычисления предикатов моделей (О (5); &}, соответствующих разбиению 3, посредством выявления минимальных подмножеств {г = 1 ,г) , где г =

Интерпретация критериев разрешимости для типовых игровых решающих правил позволила построить общую схему принятия решений Ш ^ {M;0;f,<Ti>, повышающую (за счет распараллелив^ ния) вычислительную эффективность и в целом надежность классификации объектов: общее решение — Rk(x) = ,gV Qi(x), где множество номеров эталонных объектов — Dk — ' {»!/(*) = & — = "ЦТ; некоторая реализация объекта х — (xi,...,хп) € М; сигнатура С\ = (Qn,Qi2,---,Qit) из t одноместных частных решающих предикатов

Г 1, если с{щ,х) = со;

4?»W — ^ о, в противном случае,

где со = max(min){c(üi, ж),.. .,с{йе,х)}, с(щ,х) - некоторый функционал, выражающий меру близости (сходства) между эталонами обучающей выборки й< € О = I — число эталонов, п -

число признаков; щ = (и{1,иь, ...,uin), i = 1, t. и неизвестной реализации X = {¡El,.. .,xn), j = 1,П.

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

Языком, удовлетворяющим критериям представимости и вычислимости, располагает система В = (Вп; V, 0,1), образующая алгебру булевых функций (или функций алгебры логики — ФАЛ) f(xn), Zn = («1,®з,...,я:«>, е {0,1}, i = 1 ,п; Вп = {/|/ : {0,1}" --{0,1}}.

F(xn) — правильно построенная формула (ппф), полученная суперпозицией элементарных ФАЛ q € L - {-,&, V, —А,/,,о} из класса Р2 или переименованием переменных х, G х„ и скобок (,).

Другим преимуществом языка ФАЛ является возможность эффективных вычислений (распознавания) образа f{xn) по его описанию — ппф F(xn), то есть алгоритма А: F(xn) /(£«)•

Теорема 2. Для реализации алгоритма А: F((xn ) =» /(in) необходимо и достаточно вычислить ядро К- и построить рекурсивный процесс вычисления Щ : Fe(xn) Э Fe'1(xn) Э ... Э F°(x„). Через I шагов процесс заканчивается получением ' h

F°(xn) = <

:/(2„), где bj е {0,1}, j- = 1,2Г

Для уменьшения объема памяти вычислителя (количество одновременно хранимых промежуточных результатов) потребуем выполнения на каждом шаге условия обеспечения эффективности алгоритма — использование логических связей в исходной формуле Ff(xn) согласно следующему правилу: если {/<"[} =*> Оь {Щ+1} => О2 и существует такая операция , что имеет место {Кр^' {К1+'}, то {(О^д1'-' (От)} => 0\. Критерий эффективности — минимальный объем памяти при реализации алгоритма А: Р(хп) =Ф /(£•„).

а>

в)

0 12 3 4

6)

Р!

0 У 2 2 i Я

F( у, ) = -> <ж241*э ■* х2)!)

Р,

г) I

i.....L

0 12 3 15

F( X, ) = X, V хг V ж3 V X, V ж.

) = X, V х2 & (т,Дл, ) * х, « х,

Рис. 1. Виды элементарных (базовых) спектров: а) монотонно убывающий; б) монотонно возрастающий; в) постоянный; г) осциллирующий.

Интерпретация ппф F(x„) как описания некоторого образа f(xn) в пространстве бинарных признаков х,; € хп, г = 1,п позволяет обнаружить закономерности (упорядоченность) в отображении ш : F(xn) S(gf), где 5(зГ) ^GC {1,2,...,j} х (рх>рг,... ,Pj}, j&N — номер операции qj € L\- в ппф F(xn), Pj € N — порядок (ранг) операции д., е 2Д— в ппф F(xn).

S(q?s) — спектр структурных связей взвешенных бинарных one-

раций между признаками Хі Є хп образа /(хп). Этот спектр есть дискретный или линейчатый.

Є — график зависимости величины порядка р^ операции qj от ее связи и расположения («глубины погружения») в ппф -Р(х„).

Отметим ряд полезных свойств спектра ¿>(<7^).

Лемма 1. Спектр ) момсет содержать только осцил-

лирующие, монотонно возрастающие (убывающие) или постоянные участки (рис. 1.).

Теорема 3. Для одной и той же формулы Р*(хп) можно построить один и только один спектр то есть инъектив-

ное отображение и : Р^(хп) —> 5г(^).

Для построения эффективного алгоритма А: Р*(хп) => Д(хп) необходимо указать правило выбора такого 1-го шага, который обеспечивал бы запоминание минимального количества промежуточных результатов при вычислении формулы Р*(хп).

Теорема 4 (метод сечений). Для отыскания 1-го (начального) шага эффективного алгоритма А: Д(хп) необходимо и достаточно:

1) построить отображение ш : Р*(хп) —+ ¿^(з^3 );

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

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

Операции qj Є Ь\— в исходной Р*(хп), соответствующие их локальным максимумам, являются ядрами 0-го ранга.

Теорема 5. Для построения эффективного алгоритма А: => /к(хп) необходимо и достаточно по методу сечений выбрать 1-й шаг и, выдерживая на каждом шаге условие эффективности, вычислить ядра, соответствующие локальным минимумам, в порядке, обратном сечениям спектра ).

2 I

4 5

10 12 5

17 16 11 и. 8 7

18 14 9

19 и

20

1 2 1 4 5 6 7 * 9 (О 11 12 13 14 15 16 I? 1« 19 20

1 сеч

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

2 сет

} сеч

1дро0-го ранга

4 сеч

5 сеч

Рис. 2. Выбор 1-го шага для получения эффективного алгоритма А: Р%(хп) /к(хп)

ю

Теоремы 4, 5, исключая эвристику при построении эффективного алгоритма А: ¿^(х„) Д(х„), указывают пути автоматизации вычислений булевой функции /*(х„).

Оценки сложности вычислений булевых функций. В качестве меры сложности 5[^(ж„)] вычисления //Дх«) введены два типа сигнализируюгцих функций:

1) функции, связанные с длительностью вычислений Д(х„) :

Фг < < Фз,

где ф2 — £ — верхняя оценка, € — длина формулы ^(х,»), ф\ = г+ 1— £ + 1

нижняя оценка,

2) функции, связанные с объемом промежуточной памяти:

е + 1

= ¿о[Р*(хп)} ^ ф2 =

2

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

В работе предложены конструктивные представления конечных объектов для построения классификаторов отношений последовательно-параллельного действия на основе конечных моделей с минимально полной сигнатурой (предикатами Радемахера, использующие дискретные функции). Например, для синтеза генераторов предикатов конечной модели Ш (М; а), где М {ы1,«2,--.,от}, <? ^ ^ (Дь Я2, , необходимо, в первую очередь, через предикаты

Радемахера представить точечные предикаты Р\,Р2, Рт, где

Р , Л I х, если х — ац (г = 1, т) ; * ~ " в противном случае.

Теорема 6. Для любого к € Зт ^ {1,2, ...,т}, т € 6 N точечные предикаты Рк (ж) представшш через предикаты, Радемахера Щ (х) :

Рк(х) = Я*(х)&^(х)&...&Я*(х),

где Я^х1) = I ССЛи ~ = 0;

* ' 1 -1 Щ{х), в противном случае,

v - 2п/т; [•] — целая часть числа, [и • (к - 1)] = £ 2* 1 [i/ - (к - 1)]4;

¿=1

[и . (fc _ 1)]. <= {о, 1} ; п = fiy(2V > m), ju - оператор минимизации, (i = Î7n; к - 1 ,m).

Доказано, что любой предикат Q{xu ...,Xk) на, M можно разложить по предикатам Радемахера, допускающим простую аппаратную реализацию двоичными п разрядными регистрами Рг(п).

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

Минимизация предикатных форм в конечных моделях.

Проблема простейшего представления предикатных форм для сигнатуры a сводится к выбору базиса и наиболее экономичного представления предикатов в этом базисе (§14).

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

Примеры реализации этапов конструктивизации.

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

Представление текстурных изображений (§15).

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

Пусть имеется множество текстурных изображений Т с отображением : Т —► F в пространство дискретных изображений F, где в качестве дискретных взяты изображения

Xi = {(x,y,f(x,y) }|<х,у> € M2,/(я, у) : M2 - M}.

В пространстве наблюдений F вводится обучающая выборка О = = такая, что Îl(£i) = Хи ...,Q(Xe) = Xt, и

задается классифицирующая функция g : —► 3t, £ — число классов;

^ {1,2,{1,2,...,*}.

На множестве Р введем бинарную операцию ЕЕЗ с помощью полусуммы:

аШ Жа = {{х,у, {Мх,у) + Ых,у)}/2)},

где изображения Хг = {{х, у, /г{х, у))}; = {{х, у, /2(ж, ?/))}, [•] целая часть числа, чтобы получить алгебру изображений ^ . С

помощью бинарной операции ЕВ и множеств А.к — {/¡{х,у)|г € -О/Л, где '£>* == {г|д (г) = &}, (/с = Т|7), порождаются отношения-образы ^ в модели Ш =

Построенная модель 9Я адекватна исходной модели <5 = Ть..., Т4) с основным множеством Т и некоторыми априорно заданными классами 2* С Т, (г = 1,4). Адекватность достигается тем, что операция Ш отражает компактность, имеющую место между текстурами одного класса.

Представление точечных изображений предикатами Ра-демахера.

Точечные изображения примем в виде функции / (х, у) двух переменных с областью определения Vf = {{х, у) \х, у = 1,2, ...,2П} , областью изменения р] С {1,2,..., 2"} для некоторого п е N ^

{0,1,2,...}. Для функции / (х, у) можно взаимно однозначно сопоставить отношение F следующего вида: Р = {{х,у, / (х, у)) |(х, у) е € 2?/}, которое необходимо представить в базисе предикатов Раде-махера.

Пусть Р = {<Х,у,/(х,у))\(х,у) € 2?/} = {<¿11, ¿12, ¿13),..., ?'«)}■

Соответствующий этому отношению предикат

Г 1 еі

Р(хі,х2,х-з) = I в

если (хі,х2,хз) є в противном случае,

можно записать в виде дизъюнктивного разложения но «единичным» значениям предиката Р(хі,х2,хз) на кортелсах (іеі-,Ч2,Чз)

Р(х 1,х2,х3) = -Р111іП2,ггз (Хі,Х2,Х3) V... V Ріп,геі,ііз (хі,а<'2>Жз) ,

где

Рін,ін,ін (х!,х2,х3)=Рін (Х1)ЬРь (*2)&Р<„ (хз), (і = М) ■

Подставляя в последнем выражении вместо P¿Jfc (хк)

Pijk (хк) = Щк (хк)&Щк {хк)к...кШк (хк),

(Rp (хк), если (п - р + 1) разряд двоичного разложения числа q — 1 равен 0; -uRp (х*;), в противном случае, (к =1,2,3) получаем требуемое разложение отношения по предикатам Радема-хера.

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

Минимальное разбиение растрового изображения.

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

Определение 5. Классом базисных прямоугольников назовем множество прямоугольников Ф {у?п(х,у)} со сторонами х, у € N\0, удовлетворяющих условию

(Vi, j € N\0) (3/е € N\0) [</?□ {xi,yi) П <pa (xjfyj) = ya (xk,yk)].

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

Определение 6. Геометрическим спектром (ГС) изображения А относительно класса базисных прямоугольников Ф назовем график

5Ф (А) ^ {(к (с (х, у)), с(х, у))},

где с(х,у) — канторовская нумерация пар (х,у) базисных прямоугольников ifia (х, у), а соответствующая fe-я гармоника геометрического спектра есть натуральное число

к (с (х,у)) = ]{g(tx,ty)\g{tx,ty)(pa(x,y) е А}\.

Определение 7. Структурным графиком изображения А, образованного из базисных прямоугольников класса Ф с помощью преобразований из группы G = ({g(tx,tv)} , о) преобразований 9 (tx> ty) i назовем график

QgAa) - {{c{t^ty),c(x,y))\a(n,m) = g{tx,tv)y{x,y) € А},

где c{tx, ty) — п,с(х,у) = m есть соответственно канторовские номера пар (tx,ty), (х,у); а(п,т) — прямоугольный элемент изображения А, о — операция композиции преобразований.

Определение 8. Полным подспектром (А) = = {{к (т), т)} изображения А назовем подспектр изображения, удовлетворяющий условию:

Г г г г г г

(n, m)] - Л Z Z D ta (ni>т<) П a =

n=lm=l m=l m.i—1 n,=l m,=l

где i,j € N, {щ,пц) ф (rij,mj); г — число элементов подграфика структурного графика Оа,Ф {А) изображения А, соответствующего минимальному полному подспектру; D [а (п., т)} = 1 (т) ■ г (т) есть площадь элемента а (п, т).

Т е о р е м а 7. Минимальное разбиение изображения А является подграфиком его структурного графика Gg& (А) — {{n,m}}, соответствующим минимальному полному подспектру (Л) =

= {{к(т),т)}-

Предложен алгоритм оптимизации, значительно (почти в 400 раз) сокращающий объем памяти при компьютерном анализе и синтезе растровых изображений. Новизна метода подтверждена авторским свидетельством [27].

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

функций позволяет решить:

1) задачу синтеза — построить спектр с наперед заданными свойствами, определяемыми некоторым модулятором;

2) задачу анализа — выявить в исходном спектре идентификаторы, достаточные для классификации конечных объектов.

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

Четвертая глава (§§17-20) содержит прикладные результаты по компьютерной классификации (распознаванию) наиболее динамичных и трудных для исследований объектов: текстурных изображений, функциональных состояний человека.

Компьютерная классификация текстур (§§17—18).

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

В системе картобеспечения рационального природопользования одно из ведущих мест принадлежит черно-белым интегральным космическим фотоснимкам (КФС) масштаба 1:180000-1:340000, обеспечивающим оперативное получение достоверной информации о больших площадях земной поверхности.

Ввиду потенциальной неограниченности числа классов на КФС и слабой приспособленности зрительного анализатора человека для работы с малоразмерными, низкоконтрастными элементами (объектами) на КФС надежность визуального дешифрирования КФС по всем классам объектов, к сожалению, не превосходит 35-40%, а по одному из самых распространенных и сложных классов — растительным покровам и грунтам (РПиГ) — 20-30%, что не обеспечивает полноту содержания многих тематических и топографических карт, составляемых (обновляемых) по КФС.

На основе выполненных теоретических исследований разработан

21Кельманов A.B. Апостериорный подход к решению типовых задач анализа и распознавания числовых квазипериодических последовательностей: обзор результатов // Всеросс. конф. ММРО-12. — М.: МАКС Пресс, 2005. — С. 125-128.

аппаратно-программный комплекс АРМ-Д для автоматизированного дешифрирования аэрокосмических фотоснимков при составлении и обновлении топографических и тематических карт [4, 5].

Для оценки качества работы комплекса АРМ-Д в производственных условиях проведены сопоставительные контрольные испытания: рассмотрено 47 типов РПиГ на 39 КФС, в пределах которых выделено 236 контуров, 528 фрагментов текстурных изображений РПиГ. Надежность их дешифрирования составила в среднем 77,4 ±1,7%, в том числе для районов-аналогов — 77,2±4,2%.

Универсальность комплекса АРМ-Д позволила применить его также для решения широкого круга нетопографических задач фотограмметрии в медицине, технике, авиации, биологии, физике, экологических исследованиях.

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

Компьютеризация медицинских технологий (§19).

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

В частности, выявленные при компьютерном анализе на рентгеновских снимках скрытые дефекты (пустоты, каверны) в микроар-хитектоиике костной ткани объясняют этиологию и патогенез подчас возникающего остеомиелита при сращивании костей человека с использованием аппарата и методики Илизарова Г.А. (Курганское НИИ экспериментальной и клинической ортопедии и травматологии, г. Курган, 1994 г.).

2. Выполненные с помощью пакета «OSTEO» исследования регулярности трабекулярной структуры костной ткани на рентгеновских изображениях суставов женщин предоставили возможность обнаружить и проследить возрастную динамику онкопатологий (в 20 —► 35 —» 50 лет), связанных с уменьшением костной массы и изменениями микроархитектоники костной ткани (Маммологический центр Удмуртии, г. Ижевск, 1995 г.).

3. Разработан компьютерный эндоскоп — аппаратно-программный

ен™"

Рис. 3. Оценка состояния костной ткани пациента (компьютерная система «ОЗТЕО»)

комплекс, сопряженный с эндоскопом под управлением единого программного обеспечения (система «ЭНДО»).

Проведенные клинические испытания компьютерного эндоскопа (23 объекта эзофагоспии) в Республиканском онкологическом диспансере Удмуртии (1995 г.) подтвердили экспериментально повышение качества эндоскопических исследований за счет исключения субъективных ошибок врача-эндоскописта и предоставляемой ему возможности ведения диалога с компьютерной экспертной системой, накопленной базой знаний и базой данных при решении задач диагностики, мониторинга и прогнозирования.

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

Рвужтаг «вмйм»1«ргей яумтпфмкмсам «фвММГ* я икямп ящцомшеапп «п^ммнй едяетл «Ьапя

Рис. 4. Исследование динамики эндоскопического объекта пациента (компьютерная система «ЭНДО»)

научную и общественную значимость, В работе описаны методы и приведены результаты, позволяющие на основе статистических данных прогнозировать показатели онкостатистики на различные периоды, устанавливать факторы, влияющие на показатели заболеваемости, и связи между различными локализациями. Компьютерный ретроспективный анализ (1946-1990 гг.) онкопатологий населения Удмуртии позволил выполнить онкопрогноз на период 1990-2015 гг. (система «он ко»).

5. Разработай и внедрен пакет прикладных программ для компьютерного анализа и прогнозирования:

- психических заболеваний населения Удмуртии в 1940-2016 гг.

ж;_

Шдввд

Динамик» и прогноз онковабогававмоети я Удмуртии на 100305 кампмбм. 19?» -2619 год»!

(шкллкэация трлхсв,*мн*«. «гкясинМ'тни зякопевяетол»)»

/"> "" «»Я.ЗзНН

шаУ, / -1 ию.агГ'Щ&

V I а г» —

Тму /о "■*•&* а вэ.ов-

,19»* - Мю жалтЛЧ ЗвК«ИК-в|Ш»ОС«>

тедж о, ероихи, ЛвГКИС ишкчшш

л«кллн^йии<£ 1Я»

ЙВО* - «ЮЗ

Рис. 5. Компьютерный анализ и прогноз онкозаболеваний населения Удмуртии в 1946-2015 гг. (система «ОНКО»)

(система «ПСИХ», 1992 г.);

- инфекционных заболеваний (клещевой энцефалит, лайм-борре-лиоз) населения Удмуртии в 1976-2020 гг. (система «Клещ», 1997 г.).

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

в частности, разработанная подсистема «ЭДИТА», реализуются компьютерную технологию диагностирования эпилепсии, базируется на классификаторе — системе индивидуальных признаков пациента.

7. Разработанный комплекс алгоритмов и программ по монитори-

рованию основных физиологических параметров человека: электрокардиограмма (ЭКГ), артериальное давление (АД), пульсоксимет-рия (Sp02), реография (PEO), электроэнцефалограмма (ЭЭГ), температура (Т) реализован в различных моделях мониторно-компью-терных систем, прошедших длительную опытную эксплуатацию в разнообразных клинических условиях (отделения — реанимационные, операционные, неотложной кардиологии, палаты интенсивной терапии).

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

- монитор компьютерный неонатальный МНК-01-НИОТК-Иж (per. № 98/219, включен в государственный реестр медицинских изделий, разрешенных для применения в медицинской практике и к серийному производству, Минздрав РФ, М., 1999 г., доп. № 1-2).

Новизна и оригинальность технических решений подтверждены авторским свидетельством [28].

8. Разработаны, изготовлены и испытаны на ФГУП ИЭМЗ «Купол» (г. Ижевск, 2000 г.) мониторы компьютерные медицинские: монитор анестезиологический компьютерный (МАК-01), монитор реанимационный компьютерный индивидуальный (МРКИ-01), реогра-фичеЫий комплекс компьютерный (РКК-01); мониторно-компьютер-ная система реанимационная общего профиля (система «МКС-ОНК-А»).

Рис. 6. Модель монитора компьютерного неонатального МНК-01-НИОТК-ИЖ

Заключение

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

1. Разработан на единой методологической основе теоретико-модельный подход к проблеме классификации, позволивший получить новые критерии (не) разрешимости моделей классификации конечных объектов. ;

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

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

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

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

6. Разработан конструктивный метод анализа и синтеза фрактальных спектров структурных связей мелоду булевыми операторами.

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

8. Разработаны и реализованы алгоритмы классификации для ряда прикладных задач:

- распознавание текстур (дешифрирование КФС, диагностика остеопороза, онкопатологпй);

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

9. Разработана и практически апробирована в клинических условиях в 1991-2006 гг. новая компьютеризированная наукоемкая технология медицинского мониторинга, позволяющая создать на единой

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

10. Разработай и внедрен комплекс алгоритмов и программ по компьютерному анализу и прогнозированию (1940-2020 гг.) заболеваний населения Удмуртии (онкологических, психических, инфекци-. онных).

11. Результаты работы внедрены более чем в 10 организациях и предприятиях, используются в выполнении НИОКР и в учебном процессе при чтении курса «Дискретная математика» в ИжГТУ имени М.Т. Калашникова.

Основное содержание диссертации отражено в следующих работах автора:

I. Статьи в рецензируемых научных журналах и изданиях, определенных ВАК

1. Калядпн Н.И. Диагностическое значение пальцевой денсогра-фии / Е.М. Гнедина, Э.Н. Ипатова, Н.И. Калядин, В.В. Певчих // Казанский медицинский журнал, Казань.: Изд-во ТАТОб, 1974. —, №6. - С.24 - 25.

2. Калядин Н.И. Использование ЭВМ «Мир-2» для визуально«) вывода полутоновых изображений / В.И. Заболотских, Н.И. Калядин, В.Е. Кацман // Жур. «Приборы и техника эксперимента». — М.: АН СССР, 1979. - №2. - С.90 - 92.

3. Калядин Н.И. О полноте алгебраического замыкания пространства распознающих операторов с тестовыми опорными множествами / А.Г. Ицков, Н.И. Калядин // Журнал вычислительной математики и мат. физики. - М.: АН СССР, 1984. - Т. 24. - №4. - С.579 - 586.

4. Калядин Н.И., Александров Ф.М., Липовецкий Ю.Л. и др. Автоматизированное изготовление издательских оригиналов карт // Геодезия и картография. — М.: Геоиздат, 1990. - №1. - С.Зб - 38.

5. Калядин Н.И., Леменков В.А., Липовецкий Ю.Л. и др. Комплекс автоматизированного дешифрирования крупномасштабных космических фотоснимков // Геодезия и картография. - М.: Геоиздат, 1991. - №8. - С.18 - 25.

6. Калядин Н.й. Единый методологический подход при алгоритмизации и построении экспертных систем типа норма-патология в медицине / Н.И. Калядин, В.А. Белоусов, С.В. Филатова // Медицинская техника. - М.: Медицина, 1996. - № 3. - С.6 - 7.

7. Kalyadin N.I. A Simultaneous Apporach to Decision Making / V. A. Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis. 1998. vol.8, no. 2, pp.106 - 107.

8. Kalyadin N.I. Problems of Recognition and Classification for Families of Subsets of Natural Numbers / V.A. Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis. 1998. vol.8, no.2, pp.108 - 109.

9. Kalyadin N.I. On the Problem of Classification of Sets of Natural Numbers / V.A. Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis. 1998. vol. 8, no. 2, pp. 157 - 159.

10. Kalyadin N.I. Computer Prediction of Infectious Disiases / N.I. Kalyadin, M.D. Khodyreva, T.T. Sadykov, K.E. Shumilov // Pattern Recognition and Image Analysis. 1998. vol.8, no.2, pp.414 - 415.

11. Калядин Н.И. Нумерация конечных множеств для компьютер-ной классификации // Вестник Московской академии рынка труда и информационных технологий. - 2004. - №3(11). - С.64 - 69.

12. Калядин Н.И. Временная оптимизация решающих правил классификации // Вестник Московской академн и рынка труда и информационных технологий. - 2004. - №3(11). - С.70 - 76.

13. Калядин Н.И. Преобразование Адамара-Уолша для эффективных вычислений спектров // Вестник Московской академии рынка труда и информационных технологий. - 2004. - №4(12). - С. 27 -33.

14. Калядин Н.И. Симультанная классификация множеств конечных объектов // Вестник Московской академии рынка труда и информационных технологий. - 2004. - № 4(12). - С.34 - 40.

15. Калядин Н.И. Классификация сильно слипающихся множеств // Вестник Московской академии рынка труда и информационных технологий. - 2004. - № 4(12). - С.41 - 46.

16. Калядин Н.И. Конструктивизация в классификации образов // Вестник Удмуртского университета. Серия "Математика. Механика. Компьютерные науки". - Вып.2. - Ижевск: Изд-во УдГУ, 2008. - С.188 - 193.

17. Калядин Н.И. Вычислимость в классификации образов // Вестник ИжГТУ. - Вып. 3(39). - Ижевск: Изд-во ИжГТУ, 2008. -

С.127 - 129.

18. Калядин Н.И. Разрешимость в классификации образов // Вестник ИжГГУ. - Вып.4(40). - Ижевск: Изд-во ИжГТУ, 2008. - С.169 -172.

19. Калядпн Н.И. Симультанность в классификации бинарной информации /Н.И. Калядин, В.А. Белоусов // Вестник ИжГТУ. -Вып.4(40). - Ижевск: Изд-во ИжГТУ, 2008. - С.172 - 174.

20. Калядин Н.И. Компьютерное моделирование спектров структурных связей / Н.И.Калядин, Д.Н. Сандалов // Вестник ИжГТУ.

- Вып.2(42). - Ижевск: Изд-во ИжГТУ, 2009. - С.141 - 144.

21. Калядин Н.И. Конструктивнзация в логико-алгебраических моделях // Вестник ИжГТУ. - Вып.2(42). - Ижевск: Изд-во ИжГТУ, 2009. - С. 144 - 147.

22. Калядин Н.И. Установление фрактальности в синтезированных спектрах / Н.И. Калядин, Д.Н. Сандалов // Вестник ИжГТУ.

- Вып.3(43). - Ижевск: Изд-во ИжГТУ, 2009. - С.127- 129.

23. Калядин Н.И. Распознавание отношений методом коллективного голосования // Вестник Удмуртского университета. Серия "Математика. Механика. Компьютерные науки". - Вып. 3. - Ижевск: Изд-во УдГУ, 2011. - С.154 - 162.

24. Калядин Н.И. Моделирование экспертных систем для распознавания отношений // Вестник ИжГТУ. - Вып.4(52). - Ижевск: Изд-во ИжГТУ, 2011. - С.170 - 174.

25. Калядин Н.И. Минимизация представления предикатных форм в конечных моделях // Вестник ИжГТУ имени М.Т. Калашникова.

- Вып. 1(53). - Ижевск: Изд-во ИжГТУ, 2012. - С.137 - 142.

26. Калядин Н.И." Симультанность в задачах классификации конечных объектов // Вестник Удмуртского университета. Серия "Математика. Механика. Компьютерные науки". - Вып.1. - Ижевск: Изд-во УдГУ, 2012. - С.133 - 143.

II. Авторские свидетельства

27. Авторское свидетельство №739595, СССР, М. Кл2 G06K15.20. Устройство для отображения графической информации на экране электронно-лучевой трубки / В.И. Заболотских, Н.И. Калядин, В.Е. Кацман - Заявл. 09.01.78, № 2568812; опубл. - Бюл. 1980, №21.

28. Авторское свидетельство № 25265 от 27.09,1999 г. Медицинский монитор / Н.И. Калядин, В. А. Леменков, A.B. Коробейников и др. - Заявл. 16.12.99 № 99125594; опубл. - Бюл. 2002, №27.

III. Монография

29. Калядин Н.И. Конструктивизация моделей классификации конечных объектов // Известия института математики и информатики УдГУ. Ижевск: Иэд-во УдГУ, 2007. - Вып. 1(38). - С.З - 231.

IV. Учебное пособие

30. Калядин Н.И. Основы теории алгоритмов и нумераций: Учебное пособие. - Ижевск: Изд-во ИжГТУ, 2006. - 68с.

V. Другие публикации

31. Калядин Н.И. Некоторые вычислительные аспекты в задачах распознавания булевых функций // Машинные методы обнаружения закономерностей: Материалы Всесоюз. симпозиума (5-7/04 -1976 г.).

- Новосибирск: ИМ СО АН СССР, 1976. - С. 128 - 138.

32. Калядин Н.И. Алгоритмический подход к проблемам распознавания и классификации / В.А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. - Вып.4. - Ижевск: Изд-во

ИМИ, 1982. - С.86 - 93.

33. Калядин Н.И. Конечные модели и их применение к построению классификатора отношений последовательно-параллельного действия / В.А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. - Вып.5. - Ижевск: Изд-во ИМИ, 1983. - С.83 -

88 34. Калядин Н.И. Теоретико-игровой подход к классификации текстурных изображений / Н.И. Калядин, Ю.М. Липовецкий // Труды IX научных чтений по космонавтике. - М.: ИИЭТ АН СССР, 1988.

- С-143 - 150.

35. Калядин Н.И. Представление точечных изображений предикатами Радемахера / В.А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. - Вып.9. - Ижевск: Изд-во ИМИ, 1989. - С.З - 12.

36. Калядин Н.И. Относительная полнота в конечных моделях / В А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. - Вып.Ю. - Ижевск: Изд-во ИМИ, 1990. - С.5 - 12.

37. Калядин Н.И. Алгебро-логические алгоритмы в распознавании, идентификации и классификации медицинских объектов / Н.И. Калядин, В.А.Белоусов // Вестник ПГТУ. Математика и прикладная математика. - Пермь: Изд-во ПГТУ, 2005. - С.61 - 66.

38. Калядин Н.И. К вопросу построения медицинских экспертных систем / Н.И. Калядин, В.А.Белоусов // Вестник ПГТУ. Прикладная

математика и механика. - JV»1. - Пермь: Изд-во ПГТУ, 2005. - С. 113

- 119.

39. Калядин Н.И. К вопросу существования симультанной модели классификации объектов / Н.И. Калядин, В.А.Белоусов // Вестник Удмуртского университета. Математика. - №1. - Ижевск: Изд-во УдГУ, 2006. - С.151 - 160.

40. Калядин Н.И. Об одном существенном условии в распознавании конечных множеств / Н.И. Калядин, В.А.Белоусов [/ Известия Института математики и информатики Удмуртского государственного университета. - Вып. 2(36). - Ижевск: Изд-во УдГУ, 2006. -С.113-116.

41. Калядин Н.И. Конструктивизация классифицируемых множеств // Вестник ПГТУ. Прикладная математика и механика. - Л"*1.

- Пермь: Изд-во ПГТУ, 2006. - С.8 - 15.

42. Калядин Н.И. Нумерации в проблеме классификации // Ве<п> ник ПГТУ. Математика и прикладная математика. — №1. — Пермь: РИО ПГМА, 2007. - С.51 - 55.

43. Калядин Н.И. Оценки мощности множеств синтезированных спектров структурных связей / Н.И. Калядин, Д.Н. Сандалов // Труды Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования». - Том 3. - Ижевск: Изд-во УдГУ, 2009.

- С.38 - 41.

44. Калядин Н.И. Фрактальность в спектрах структурных связей / Н.И. Калядин, Д.Н. Сандалов // Труды Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования».

- Том 3. - Ижевск: Изд-во УдГУ, 2009. - С.41 - 45.

Н.И. Калядин

Отпечатано с орнгинал-макета заказчика. Подписано в печать 25.03.13. Усл. печ. л. 2,33. Формат 60x84 1/16. Тираж 100 экз. Заказ № 130 Типография Издательства Ижевского государственного технического университета имени М. Т. Калашникова 426069, Ижевск, ул. Студенческая, 7

ФГБОУ ВПО «ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ М.Т. КАЛАШНИКОВА»

05201351256

КАЛЯДИН Николай Иванович

УДК 519.712 + 510.25 + 510.67

КОНСТРУКТИВИЗАЦИЯ МОДЕЛЕЙ КЛАССИФИКАЦИИ КОНЕЧНЫХ ОБЪЕКТОВ: КОНЦЕПЦИЯ, МЕТОДЫ И КОМПЬЮТЕРНАЯ

РЕАЛИЗАЦИЯ

05.13.18 — Математическое моделирование, численные методы и

комплексы программ

На правах рукописи

ДИССЕРТАЦИЯ

на соискание ученой степени доктора физико-математических наук

Ижевск 2012

Оглавление

Обозначения................................. 6

Введение................................... 8

Глава 1. Разрешимость конструктивных моделей классификации .................................17

§ 1. Предпосылки к конструктивизации................17

1.1. Предварительные сведения .................17

1.2. Экзистенциальность в классификации образов......24

§ 2. Алгоритмический подход к проблемам классификации.....27

2.1. Конструктивизация......................28

2.2. Нумерованные совокупности конечных объектов.....41

§ 3. Разрешимость моделей решающих правил............48

3.1. Модели решающих правил..................48

3.2. Теоремы существования и единственности в системах

принятия решений .....................59

§ 4. Полученные результаты и выводы.................62

Глава 2. Вычислимость конструктивных моделей классификации .................................64

§ 5. Кодирование классифицируемых множеств............64

§ 6. Два подхода к классификации конечных множеств.......66

6.1. Классификация с использованием информативных эле-

ментов ............................67

6.2. Классификация с использованием инвариантных зон ... 99 § 7. Решающие правила для классификации отношений.......108

7.1. Модели решающих правил для отношений.........109

7.2. Симультанный метод распознавания отношений .....112

7.3. О нумерации в спектрах отношений ............113

§ 8. Оптимизация решающих правил..................114

8.1. Обоснование оптимизации..................115

8.2. Постановка задачи......................116

8.3. Учет альтернативных частных решений..........116

§ 9. Симультанность в принятии решений при обучении.......117

9.1. Симультанность при идентификации............118

9.2. Обобщенная симультанная модель распознавания . . . .119

9.3. Нейронные сети симультанной схемы принятия решений . 122 § 10. Вычислимость в задачах распознавания булевых функций . . . 124

10.1. Существование эффективного алгоритма.........126

10.2. Спектр структурных связей.................131

10.3. Изоморфизм спектров структурных связей........138

10.4. Построение фильтров при вычислении булевых функций 145

10.5. Оценки сложности вычислений булевых функций .... 147 § 11. Полученные результаты и выводы.................149

Глава 3. Реализуемость конструктивных моделей классификации .................................151

§ 12. Пролонгация языков.........................151

§ 13. Дискретные функции Уолша ...................153

13.1. Дискретные функции Уолша при произвольном конеч-

ном числе точек определения...............153

13.2. Связь адамаровского упорядочивания функций Уолша с

секвентным и диадным...................156

13.3. Алгоритм быстрого двумерного преобразования Адамара-

Уолша............................165

§ 14. Представимость объектов в конечных моделях..........168

14.1. Построение классификаторов отношений .........168

14.2. Минимизация предикатных форм в конечных моделях . . 178 § 15. Представление изображений для моделирования.........184

15.1. Основные операции над изображениями..........184

15.2. Представление точечных изображений предикатами Ра-

демахера...........................187

15.3. О минимальном разбиении растрового изображения . . . 191

15.4. Описание текстур предикатами Радемахера........196

15.5. Кластеризация с порождением отношений-образов . . . .197

15.6. Нелинейные персептроны..................203

15.7. Анализ и синтез спектров в представлении булевых функ-

ций ..............................211

15.8. Конструктивизация в логико-алгебраических моделях . . 222 § 16. Полученные результаты и выводы.................228

Глава 4. Прикладные результаты ...................230

§ 17. Классификация текстурных изображений (примеры)......230

17.1. Математическое обеспечение анализа двумерных полей . 230

17.2. Обнаружение классификационных закономерностей ме-

тодом альтернативных решающих правил........232

17.3. Экспресс-метод распознавания текстур...........238

17.4. Теоретико-игровой подход в классификации текстур . . . 242 § 18. Представление текстур для компьютерного анализа.......250

18.1. Параметризация текстурных изображений.........250

18.2. Сегментация текстурных изображений...........252

18.3. Дешифрирование космических фотоснимков .......253

§ 19. Компьютеризация медицинских технологий ...........259

19.1. Построение медицинских экспертных систем .......259

19.2. Денсометрия сердечно-сосудистой системы человека . . . 265

19.3. Диагностика эпилепсии ...................269

19.4. Эндоскопия. Микроархитектоника костной ткани.....270

19.5. Статистический анализ медицинской информации и про-

гноз по онкологическим заболеваниям..........272

19.6. Компьютеризированная технология медицинского мони-

торинга ............................275

19.7. Примеры из компьютеризации медицинских технологий . 278

§ 20. Полученные результаты и выводы.................299

Заключение .................................301

Литература..................................303

Приложение (акты о внедрении результатов работы) ......329

Обозначения

а е Угт+1 — информативные элементы («идентификационные метки»);

(^">3 = 1,ш) — информативные зоны; [а £ X] — предикат принадлежности элемента а множеству X; X — конечное подмножество множества всех натуральных чисел N ^ {0,1,2,...};

^ — есть обозначение для;

Зт ^ {1,2,..., га}, ^ {1, 2,..., £} — множества индексов га, £ £ Л^\0; / : Зто —> — классифицирующая функция;

(р : М ^ К — функция кодирования образа конечным множеством из К] К — множество (универсум) конечных объектов; М — основное (исследуемое) множество образов;

О = ||^г,||гхп — обучающая матрица; г = 1, /— число объектов; ] = I, / — число признаков;

[X = Хг~| — предикат равенства множеств X — неизвестного, предъявленного для классификации (распознавания) и Хг — эталонного (известного); [л —оператор минимизации;

я. = НЯуИтхт ~ логическая (булева) матрица, ^ е {0,1};

г — отношение толерантности (сходства);

А В — множество А га— сводится к множеству В;

А =т В — множества А и В т— эквивалентны;

^ : N —> 5 — нумерация, то есть отображение ./V на 5;

Н : N Р{М) — вычислимая функция, -Р(А^) — булеан;

Ф — множество всех конечных подмножеств натурального ряда ./V;

7 : N —► Ф — стандартная нумерация;

— не более чем счетное множество конечных подмножеств из ./V;

Л4 = (М; О; /; <тг) — модель решающего правила, г = 1, аг — сигнатура модели ЛЛ\ - операция полусуммы;

и

= {г|/(г) = к}, /с = 1, £ — множество номеров эталонных объектов;

S? — классы разбиений (г = 0,1, 2);

Рг(Х) ^ X G У1г — предикат принадлежности неизвестного множества X классу эквивалентности г =

С(щ, х) — функционал близости реализации объекта х стратегии йг £ О; R%{X) ^ (£г П X) — предикат пересечения эталонного множества 8г с неизвестным множеством X, г = 1,£; £г — множество эталонных элементов;

Pj {^1] 5 ) — мера толерантности (сходства, близости) между эталонными и13 и предъявленными Xj значениями г—го признака j— го объекта; S ^ .OTt} — множество классов эквивалентности;

X (\Х = £г]) — характеристическая функция предиката равенства; L = {—, &, V, —= , Д, /, , о} — множество ФАЛ из класса Ръ] с(х,у) — канторовский номер пары (х,у)] 0(21) — операция объединения семейства множеств 21; П(21) — операция пересечения семейства множеств 21;

= (^1) •■■■> Яп)■> £ {0,1}, г = 1,п — набор булевых переменных; F(xn) — логическая (булевая) формула; Я® п) булевая функция, f(xn

А : F(xn) /(хп) — алгоритм вычисления f(xn) по формуле F(xn); с[3 — операция q3 G L\— порядка р3, (0 ^ p3 ^ — 1,2,3, Fe(xn) — логическая формула длины t £ iV\0; S{(f33) — спектр структурных связей (fj между признаками хг Е хп] 7г : F^{xn) -г* Si{(f33) — отображение скобочных связей в формуле F^(xn) спектром St{(f33)\

^{1,2,3,...} — множество целых положительных чисел; R — множество действительных чисел;

и™ (к) — г-я дискретная функция Уолша, определенная в т точках, к = 0,т — 1; те Z+\

г2"(г, /с) — дискретные функции Радемахера, г = 0, п, /с = О, 2n — 1; Щ(х) — предикаты Радемахера, к — l,m, i = 0, гг.

Введение

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

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

В основе современных наиболее развитых подходов в распознавании образов, таких как статистические методы [20, 252], комитетные конструкции [130, 237], распознавание по прецедентам [41, 42], нейронные сети [46] лежит предположение о выполнении гипотезы компактности [5]: «...образам соответствуют компактные множества в пространстве выбранных свойств».

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

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

Проблемами разрешимости и вычислимости различных конкретных теорий фундаментальных наук занимались многие зарубежные и отечественные математики: Barwise D., Bernaus Р., Blum M., Cohen P.L., Chang С.С.,

1Конструктивизация образов, моделей объектов и т. п. вводится согласно сложившимся основным понятиям конструктивной математики, в частности, конечный (конструктивный) объект есть образ, описываемый конечным объемом информации [121, 173, 190].

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

Church A., Cutland N., Enderton H., Feferman S., Godel K., Goodstein R.L., Hilbert D., Jensen R., Keisler H.J., Kleene S.C., Lachlan A.H., Macintyre A., Post E., Robinson D., Rogers H., Sacks G., Scott D.S., Shelah S., Shoenfield J.R., Sikorski A., Tarski A., Turing A., Penrose R., Van der Waerden B.L. и другие;

Адян С.И., Барздинь Я.М., Бельтюков А.П., Гончаров С.С., Ершов Ю.Л., Журавлев Ю.И., Заславский И.Д., Колмогоров А.Н., Кушнер Б.А., Мазуров Вл.Д., Мальцев А.И., Марков A.A., Маслов С.Ю., Матиясевич Ю.В., Минц Г.Е., Нагорный Н.М., Новиков П.С., Оревков В.П., Палютин Е.А., Пе-ретятькин М.Г., Тайманов А.Д., Трахтенброт Б.А., Успенский В.А., Цейтлин Г.С., Шанин H.A., Шрейдер Ю.А., Яблонский С.В., Якубович С.М. и многие другие.

Фундаментальные результаты о разрешимости и вычислимости в конструктивных моделях для теорий получены академиком РАН Ю.Л. Ершовым [40], но в распознавании образов подобных работ достаточно мало.

Выделим две отечественные научные школы, где традиционными математическими методами впервые ставились и исследовались вопросы разрешимости и вычислимости в распознавании образов.

1. Предложенная в начале 70-х гг. прошлого века Вл.Д. Мазуровым теория комитетных решений оказалась весьма продуктивной для построения безошибочных (корректных) алгоритмов распознавания, что нашло отражение в последующих многоплановых исследованиях как теоретического, так и прикладного характера [38, 131, 132, 236-239].

Вл.Д. Мазуровым и его учениками М.Ю. Хачаем, А.И. Рыбиным, А.И. Кривоноговым, Ю.А. Зуевым, Н.Г. Белецким сформулированы и доказаны теоремы существования комитетных решений для различных систем ограничений [131]. М.Ю. Хачай всесторонне исследовал вопросы вычислительной сложности задач о минимальном комитете [181-183, 226, 227].

2. Академиком РАН Ю.И. Журавлевым введены [41-44, 202, 215, 255, 262] основополагающие понятия (разрешимость, регулярность, полнота) в некорректных (эвристических) информационных моделях, позволяющие син-

^ тезировать «прямыми методами» корректные, т.е. точные на прецедентах,

алгоритмы классификации.

Задача — разрешима, если существует ее решение; задача называется регулярной, если она разрешима и разрешимы также все задачи, отличающиеся от нее лишь набором значений решений на объектах обучения. Под полнотой семейства алгоритмов понимается существование в нём решений для всех регулярных задач.

Представителями научной школы Ю.И. Журавлева в дальнейшем более детально исследованы введенные им понятия. Выполненный К.В. Рудаковым углубленный анализ ограничений для задач классификации расширил область их применений за счет привлечения морфизмов категорий [156-159].

A.A. Черепнин рассмотрел класс задач с различными оценками радиусов разрешимости и регулярности [186, 187].

Ю.В. Чехович получил критерии локальной разрешимости и локальной регулярности в задачах выделения трендов [189].

A.C. Вальков предложил критерии разрешимости и регулярности в задачах распознавания с отношением соседства на объектах [19].

Однако, как показал Ю.И. Горелов [25, 26], в общем случае для регулярных задач управления, решаемых в рамках теории распознавания образов, использование эвристических информационных моделей может привести не только к нерегулярности, но и к неразрешимости некоторых алгоритмов распознавания.

Последнее вызывает необходимость проведения дополнительных исследований одной из перспективных версий прецедентного подхода [42] — использование логических закономерностей-предикатов над числовыми и/или символьными данными в концепции поэтапной конструктивизации в классификации образов: разрешимость, вычислимость и реализуемость на моделях классификации конечных объектов.

Возникающие при проектировании распознающих систем особенности представимости и вычислимости описания образов потребовали развития и моди-

фикации традиционных схем разрешимости и вычислимости конструктивных моделей, в частности:

- проблема разрешимости моделей классификации конечных объектов (в дальнейшем — проблема разрешимости [40, 71, 112]) состоит в следующем: существует ли алгоритм, который по описанию на языке расширенного исчисления предикатов [145, 164] устанавливает принадлежность исследуемого

объекта к рассматриваемому множеству М или к одному из классов разби-

к

ения 5 ^ {Мъ М2,.. •, Мк}, м=им,;

г=1

- проблема вычислимости моделей классификации конечных объектов (или просто — проблема вычислимости [72, 112, 154]) заключается в установлении эффективной процедуры, гарантирующей получение результатов вычислений соответствующих предикатов классификации объектов.

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

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

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

Научная новизна. Отметим элементы новизны результатов диссертации.

1. Разработан на единой методологической основе теоретико-модельный подход к проблеме классификации, позволивший получить новые критерии (не)разрешимости моделей классификации конечных объектов.

2. Исследованы вопросы представимости и вычислимости описания конечных объектов с целью оптимизации вычислительных затрат при компьютерной реализации алгоритмов классификации:

- получены новые методы сокращения длины описания конечных объектов, что равносильно уменьшению требуемого объема памяти классификатора;

- найдены впервые необходимые и достаточные условия существования предельно быстрой (симультанной) модели классификации;

- получены новые методы сокращения времени принятия решения в моделях классификации, допускающих распараллеливание;

- рассмотрены быстрые спектральные преобразования Адамара-Уолша.

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

4. Разработан конструктивный метод анализа и синтеза фрактальных спектров структурных связей между булевыми операторами.

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

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