Введение к работе
Актуальность темы. Проблема распознавания и классификации в течение достаточно продолжительного времени привлекает к*себе пристальное внимание многих исследователей в области прикладной математики и информатики.
В настоящее время методы распознавания и классификации получили широкое применение во многих областях исследовательской и практической деятельности при обработке экспериментальных данных и решении прикладных задач в слабо формализованных областях естествознания, геологическом прогнозировании, экологии, дистанционном зондировании, автоматизации научных исследований и т. д.
Становление распознавания как самостоятельной научной теории характеризуется следующими этапами:
появлением большого числа различных некорректных (эвристических) методов и алгоритмов, применявшихся без какого-либо серьезного обоснования для решения практических задач. Такие методы и алгоритмы обосновывались непосредственной проверкой-успехом решения реальных задач.
переходом от описания отдельных некорректных алгоритмов к описанию принципов их формирования. Этот период связан с построением и исследованием нескольких типов моделей. Переход к моделям алгоритмов распознавания сам по себе не привел ни к создании некоей универсальной модели, ни к формализации процесса выбора определенной модели, но появление моделей позволило ставить и. решать в рамках определенной модели задачу выбора экстремального по функционалу качества алгоритма.
- построением и исследованием коллективных Скомнтзтных,
групповых) метоцов, предусматривавших формирование
решения задачи распознавания на основе результатов
обработки неходкой информации отдельным»: алгоритмами.
- созданьем и развитием алгебраического подхода к решения
задач распознавания, позволяющий строить экстремальные
алгоритмы, как правило, с использованием несложной
математической техники.
С другой стороны для решения задач классификации
(таксономии, распознавания без учителя), создано большее число методов и алгоритмов, накоплен значительный практический опыт, однако такого качественного развития, какое имеется в распознавания, пока не произошло. Используемые в классификации алгоритмы и модели являются некорректными (эвристическими), а многолетний процесс развития различны7 направлений не привел к создании универсальных моделей, а также к формализации принципа выбора определенной модели илй: алгоритма для решения соответствующей задачи,
В силу специфики постановки задачи классификации, оценить работу отдельного .алгоритма, а также нескольких алгоритмов, использующих различные принципы формирования классификации, и, как правило, имеющих существенные. различия в результатах, не всегда представляется возможным из-за отсутствия общего критерия, аналогичного той , оценке, которая, принята .в распознавании, например,' по доле правильных ответов на контрольном материале, вероятности ошибки или значению среднего риска. Поэтому в задачах классификации, с целью получения объективной ;информации о структуре анализируемого множества,также применяются групповые (коллективные), методы, формирующие решение да основе ; результатов нескольких алгоритмов, однако такого развития, как в аналогичных задачах распознавания не имеют.
Анализ групповых методов классификаций, проведенный в работе, показал что существующие методы ориентированы на конкретный вид представления исходных . классификаций и эффективны лишь для'классификаций с малым числом классов или -небольшого числа объектов и в настоящее время разработаны еще недостаточно. Используемый при разработке, методов аппарат не может быть применен для групповых методов классификаций континуального множества объектов, а также для построения корректных расширений моделей классификации и корректных алгоритмов, являющихся групповым синтезом базисных алгоритмов.
Поэтому разработка теории , и применения групповых методов классификаций для конечных и континуальных множеств объектов является актуальной проблемой распознавания образов. Представляемая работа посвящена этому новому перспективному направлению теории распознавания и классификации.
Связь темы исследования с планами НИР, Настояная работа выполнена в соотвествии с программой АН РК "Разработка математического обеспечения автоматизации научных исследований" на 1980-1985 гг. Cn гос. per. 8005В001) и в'рамках Республиканской региональной программы Р.077.01 "Создание и развитие автоматизированных систем и эффектиьного использования вычислительной техники в отраслях Республики Казахстан, на 1986-1990 гг. и на период до Я005 года".
Цель работы. Целью работы является разработка и исследование принципов, методов и алгоритмов синтеза групповых классификаций конечных и континуальных множеств объектов, заданных различными представлениями. Построение и исследование моделей и алгоритмов распознавания 'и классификации на континуальной информации.
Методы исследования. В работа использованы методы и аппарат теории множеств и анализа, булевой алгебры, теории структур, теории отношений и алгебры.
Научная новизна. В работе впервые , предлагаются два новых подхода - метрический и структурный, основанные на использовании метрических свойств пространства классификаций конечного множества объектов и координатных представлениях классификаций, соответственно, дляреализации групповых' методов.классификаций и построения короектных расширений моделей на основе базисных представлений классификаций. .
Среди основных содержательных результатов отметим следующие, . обладающие новизной.
1. Введена метрика в пространстве классификаций конечного
множества объектов, являющаяся более эффективной . для решения
.рассматриваемого класса задач, по сравнения с метрикой Хеммин-
гова типа, используемой для оценки близости классификаций.
Получены ее обобщения на случай пространств классификаций кон
тинуальных множеств объектов, позвряявдие решать задачу груп-
.повой классификации в_этих пространствах.
-
Исследованы основные метрические свойства пространства классификаций конечного множества обьеетов,
-
Построены алгоритмы синтеза групповых классификаций, основанные на матричоском подходе. Получены оценки их сложности. . '
4. Построены модели результирующих бинарных отношений
(графов) и характеристических наборов центров классов, доказана
их полнота, получены значения параметров, позволяющие строить
оптимальные результирующие отношения и наборы центров.
5. Получено координатное представление классификаций, ос
нованное на структурных свойствах пространства классификаций
конечного множества объектов.
В. Построен прямой (без оптимизации) метод точного пост- роения групповой классификации конечного множества объектов.
-
Построена и исследована корректная алгебра для задач классификации конечного множества объектов, на основе базисных представлений классификаций.
-
Получены методы порождения континуальной обучающей информации из заданного конечного множества объектов с соответствующей информационной матрицей.
-
Построены модели алгоритмов распознавания на континуальной обучающей информации. Получены эффективные процедуры вычисления оценок. Исследована корректность алгебраического замыкания модели для начальной информации, заданной произвольными ограниченными областями - положительной меры,, получен корректный алгоритм и исследована его.устойчивость.
-
Исследованы.принципы построения алгоритмов распознавания и классификации на континуальных множествах положительной меры. '
-
Построены алгоритмы распознавания конечных множеств объектов, сходящиеся почти всюду к корректному алгоритму для задачи распознавания континуальных множеств.
Приведенные результаты представляют собой основные положения диссертационной работы, выносимые на защиту.
Практическая ценность. Разработанные методы группового синтеза классификаций могут быть успешно, применены как в задачах анализа данных, так и в качестве аппарата предварительной обработки исходной информации . при решении . различных аспектов научных и прикладных проблем. К числу таких , проблем следует отнести задачи распознавания, прогнозирования, а также ряд задач связанных с принятием решений. Относящиеся к нетрудно реализуемым моделям распознавания с континуальной обучающей информацией, порожденной покрытием исходной конечной
информации гиперпараллелепипедами, модели алгоритмов находят широкое применение в задачах дешифрирования многозональной аэрокосмическон информации, цифровой обработки изображений, а также в целом ряде исследовательских задач, где ставится, например, задача определения Фоновых (не принадлежащих никаким классам) объектов.
В этом плане, применение методов, предложенных в работе, позволит рьшать широкие классы прикладных задач.
Реализация'. Разработанные в диссертации методы,- алгоритмы и соответствующее программное обеспечение были' использованы при решении ряда важных прикладных задач геологического прогнозирования, экологии, сельскохозяйственного мониторинга и внедрены в ПО "Эмбанефть" МНП СССР, Центре "Казэкология" РК, Институте гидрогеологии и гидрофизики АН РК, Институте географии АН РК и ГВЦКП Минсельхоза РК.
Работа проводилась в рамках 2 хоздоговорных научно-исследовательских работ, 2 договоров о научно-техническом.сотрудничестве и по постановлении правительства Республики Казахстан, соответственно.
Результаты внедрения подтверждены соотвествующими документами.
Апробация. Основные результаты диссертации докладывались и обсуждались на: і Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, 1981 г.), Советско-Германских семинарах "Дискретная математика и ее приложения в кибернетике" (Москва, 1983 г. , Алма-Ата, 1985 г. , йена, 1986 г.); Международной конференции "Проблемы искусственного интеллекта и распознавания образов" (Киев, 1984 г.), 11 Всесоюзной конференции "Математические методы распознавания образов" (Дилижан, 1985 г."), Всесоюзном симпозиуме "Машинное обнаружение закономерностей" (Минск, .1985 г.), х 'Всесоюзном совещании "Проблемы управления-85" (Алма-Ата, 1986 г.), II Всесоюзной конференции "Икформатика-87" СЕреван, 1987 г.), іи Всесоюзной конференции "Математические методы распознавания образов" (Львов, 1987 г.), и Республиканской коррекции "Проблемы вычислительной математики и автоматизации научных исследований" (Алма-Ата, 1988 г.), Всесоюзной школе-семинаре по
рудопромысловой гидрогеохимии" СЧпта, 1988 г.), iv Всесоюзной
конференции "Математические методы распознавания образов" СРи
га, 1989 г.), Республиканской научно-технической конференции
"Использование достижений НТП в области охраны природы
Казахстана" С Алма-Ата, 1990 г.О, Международной научно-техничес
кой конференции "Применение статистических методов в
производстве и управлении" СПермь, 1990 г.), Республиканском
совещании "Проблемы создания систем обработки, анализа и
понимания изображений" СТашкент, 1991 г.), v Всесоюзной конфе
ренции "Математические методы распознавания образов" (Звениго
род, 1991 г.), Международной конференции при специализированной
выставке "СПЕКТР-914 СМинск, 1992 г.), а также на ежегодных
отчетно-научных конференциях Института математики и механики
АНРК с 1980 по 1991 гг. /
Публикации, По основным результатам диссертации опубликовано 25 работ. Всего по материалам выполненных исследований по теме диссертации опубликовано 35 работ. Личный вклад автора в совместных работах [14,15,18^22-24], имеющих прикладной характер, состоит в формальной постановке задач и разработке методов и алгоритмов, относящихся к групповому синтезу классификаций и дешифрирование многозональных космоснимков.
Структура и объем работы.. Диссертация состоит из введения, шести глав, заключения, списка литературы из 126 наименований. Объем диссертации - 245 страниц.