Введение к работе
Актуальность темы. Применение математические, методов, математического моделирования и вычислительной техники для решения разнообразных научных задач стало к настоящему времени одним из основных инструментов исследований. Общеизвестны практические успехи применета. математического моделирования в экономике, экологии, проектировании, физике и многих других областях. В последнее время метода математического моделирования с успехом внедряются в такие мало-формализованные области, как медицина, социология, история.
3 то же время для математического моделирования явлений, ситуаций, объектов или процессов необходим определенный уровень знаний и информации, связанных с объектами исследований. Прежде всего необходимо иметь качественную модель объекта исследования, то есть знать, какие факторы являются определяющими и каковы связи между ними. Необходимо знать систему закономерностей, уравнений, функционалов и т.п., описывающих адекватно исследуемый объект. Наконец, необходим определенный объем информации' и уровень ев точности для точного вычисления в математических моделях различных величин, решения уравнений и т.п. Отсутствие каких-либо из данных условий зачастую приводит к непреодолимым в рамках математического моделирования проблемам.
Здесь можно отметить следующие две типичные практические ситуации: "
имеется необходимость в исследовании и анализе новых процессов или явлений,'для которых отсутствуют математические модели, а их разработка требует определенного времени зли невозможна на данном этапе знаний о предметной области:
применение существующих моделей является- невозможным в какой-то новой обстановке из-за неполноты и (или) неточности данных.
3 подобных стандартных и весьма распространенных ситуациях метода теории распознавания и классификации являются зачастую единственным инструментом практического использования имеющейся информации в науке или производстве. О важности применения теории распознавания в "описательных" науках, а также о еб потенциальных возможностях в процессе математи-
ческсго моделирования отмечено академиком А.А.Дородницыным1.
Не требуя априорных знаний о сущности рассматриваемых явлении, процессов или ситуации и используя минимальную о них информацию в виде выборок описание имеющихся прецедентов-наблюдений, методы теории распознавания позволяют не только успешно решать задачи распознавания, диагностики, классификации или прогноза, но и находить практически ценные знания о природе объекта исследования (информативные признаки, эталонные объекты, эмпирические закономерности и т.д.). Последние, кроме непосредственного практического применения, могут служить основой для последуияего математического моделирования. Как отмечено академиком Ю. И. Журавлевым2, к постановкам теории распознавания сводятся также многие задачи принятая решений.
За 30-40 лет интенсивного развития теории распознавания оыли созданы сотни алгоритмов распознавания и классификации, основанные на различных идеях, гипотезах и принципах. В настоящее время выделяются следующие три последовательных этапа процесса конструирования точных распознающих алгоритмов по выборкам прецедентов:
создание параметрических моделей распознавания, основанных на эмпирических закономерностях;
оптимизация параметрических моделей распознавания;
- построение коллективных решений задачи распознавания с
помощью логических или алгебраических корректоров.
Поскольку точность распознавания является важнейшей характеристикой распогяакщих алгоритмов и она зависит от качества решения каждого из этапов, исследования по данным этапам - направлениям относятся к числу актуальных проблем. Для решения задач оптимальной логической или алгебраической коррекции коллективов распознающих алгоритмов фундаменталь-
Дороднитргя А.А. Проблемы математического моделирования в описательных науках// Кибернетика. 1983, №4, C.6-I0.
адураглев О. И. 00 алгебраическом подходе к решению задач распознавания или классификации// Проблемы кибернетики. М.: Наука, 1978. Вып. С.5-68.
ныв ,результатн получена Ю.й.яуравлэвнм (алгебраическая теория распознавания) и его учениками, правде всего академиком РАО В.Л.Магросовнм и чл.?ч.-корр. РАЕН К.В.Рудаковым; данные вопросы в настоящей раОотэ на рассматриваются.
Известные модели распознавания, основанные на поиске по обучающим данным алшрических закономерностей, ориентированы обычно на определенный тип признаков, требуют выполнения некоторых условий или гипотез на начальной информации или ограничены использованием эвристических и локальных средств. Таким образом, актуальным направлением является создание новых, обобщающих известные моделей распознавания с эмпирическими закономерностями. Существующие метода оптимизации сложных многопараметліческих моделей нах правило связаны либо с построением локальных решений в отдельных параметрических подпросгравх убвх, либо с оптимизацией линейных решающих правил. Позтом., исследование оптимизационных проблем в і.., многопараметрическк с, существенно нелинейных моделях с
..'разнотипными параметрами, разработка методов оптимизации моделей в полных парагетричесхих пространствах является
' также актуальной «мой исследований. Третьим актуальным направлешоч, разгшаемом в настоящей работе, является разработка аьзлогов алгебраического подхода в теории классификации (таксономии), с целью автоматизации построения оптимальных решений задач классификации на базе имеющихся коллективов эвристических прсдодур.
Соответствие исследовательским планам. Диссертация вы-полнена в соответствии с плановыми НИР : Ц РАН "Развитие алгоритмического и программного обеспечения для применения вычислительных машин при решении задач прогнозирования и диагностики на базе алгебраических и . огических методов"(НГР ОГ.86.0 130490), дискретные и неклассичесние модели обработки информации и принятия решений (Тема І.ІЗ.12.6), Алгебраические метода в теории распознавания и прогнозирования (Программа "Перспективные информационные технологии", решение ГКНГ * 836), Грантом РФ*И * 93-012-457: Математические метода синтеза решений неклассических задач экстраполяции (в том числе задлч распозяЕвания, классификации и прогнозирования), тремя хозяйственными договорами.
Цель работы. Реальностью настоящего этапа развития теории распознаваниями классификации (кластерного анализа,
таксономии) является существование обширного множества разработанных математических, алгоритмических и программных средств. предназначенных для решения дост. точно ограниченного набора стандартних задач: задач распознавания и классификации, обучен»" распознаванию и оптимизации моделей распознавания, сжатия описаний классов объектов и т.д. Кроме того, данные средства оперирует с конечными наборами формальных объектов (признаки, эмпирические закономерности, опорные множества и т.п.). Как правило, практический пользователь имеет в наличии наборы различных математических средств, формальных объектов и вычислительных процедур, которые мы будем называть коллективами, ориентированных на решение определенных стандартных задач.
Целью работы является разработка и исследование методов распознавания, оптимизации моделей распознавания, а также методов коррекции алгоритмов классификации, -основанных на формализациг, создании и оптимальном использовании коллективов различных понятий и объектов - коллективов эмпирических закономерностей, функционалов, оптимизационных процедур, алгоритмов классификации, программных модулей.
Метода исследования. В работе использованы методы и аппарат алгебры, анализа, математического программирования, теории распознавания.
Научная новизна. I. Предложен новый общий подход к формализации понятия "эмпирическая закономерность" для задач распознавания со стандартными начальны.-.. информациями, как коллективов специальных подмнокеств пространства допустишь признаковых описаний - оптимальных систем признаковых окрестностей. Разработаны параметрические и непарамвтричзс-кие способы их описания. Задачи нахождения оптимальных систем признаковых окрестностей пол юмиально сведены к решению специальных линейных (БМС-ВДП) и билинейных задач целочисленного программирования. Исследована взаимосвязь между размэрностью задачи БМС-ВДП и величиной оптимума функционала качества системы г.окрестностей. Разработан новкй класс распознающих алгоритмов - основанных на локальных критериях оптимальности.
2. Разработан и обоснован новый подход к решению задачи оптимизаци.. сложных многопараметрических моделей распознавания, основанный на последовательной оптимизации операторов
близости, распознающего оператора и решающего правила е различных параметрических подпространствах. Получены количественные оцзнки для значений оптимума стандартного функционала качества распознавания, выражаемые через значения оптимума функционала качества опет{ лора близости. Получен ряд качественных соотношений между различными оптимизационными постановками и их решениями. Разработаны и обоснованы методы оптимизации оператора близости, распознающего оператора и решающего правила.
3. Построено параметрическое расширений релаксационных
алгоритмов решения систем выпуклых неравенств, предложен и
обоснован новый оптикизационнй принцип выбора релаксационного сдвига на каздой итерации. Введены понятия оптимального релаксационного алгоритма и его приближений. Разработаны новые эффективные приближенные релаксационные алгоритмы, ориентированные на системы неравенств с трудоёмким вычислением функций и их градиентов, а также специальными дополнительными свойствами, . отражающими специфику задач оптимизации распознающих операторов к алгоритмов.
-
Впервые разработан аналог алгебраического подхода а теории распознавания для решения задач классификации (таксономии) - теория комитетного синтеза коллективных решений задачи классификации. Введены и исследованы критерии оптимальности коллективных решэний, разработан эффективный алгоритм поиска оптимальных комитетных решений при использовании хэмминговой метрики в пространства матриц оценок.
-
Впервые предложена и реализована в программных системах ДИСАРО и ОБРАЗ идеология последовательно-параллельного исследования стандартных информации и решения задач распознавания и классификации.
Практическая ценность. Результаты диссертации могут быть использованы в следующих научных и прикладных областях:
разработка качественных моделей процессов, ситуаций и явлений по прецедентной информации в малоформализованных областях;
создание новых моделей распознавания, основанных на поиске эмпирических закономерностей;
- разработка специализированных методов оптимизации
различных многопараметрическкх моделей распознавания;
- решение задач диагностики, классификации, прогноза, .
распознавания и контроля в медицине, геологии, технике,
социологии и других областях.
Апробация. Основные результаты диссертации докладывались и обсувдались на I Всесоюзном совещании по статистическому и дискретному анализу нечисловое информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, IS8I г.) Советско-Германских семинарах "Дискретная математика и ев приложения в кибернетике" (Росток, 1977 г., Москва, 1983 г., Алма-Ата, 1985 г., Тбилиси, 1986 г., Самарканд, 1987 г.), Первой - пятой Всесоюзных конференциях "Математические методы распознавания образов" (Москва, 1983 г.. Дилижан , 1985 г., Львов, 1987 г», Рига, 1989 г., Москва,. 1991 г.), Всероссийской конференции "Математические методы распознавания образов"(Москва, 1993 г.), Международных конференциях "Проблемы искусственного интеллекта и распознавания образов" (Киев, 1984 г.), Советско-йшском семинаре по практическому распознаванию (Тбилиси, 1987 г.), "Информационные технологии в обработке изображения и распознавании образов" (Львов, 1990 г.),"Информатика-88" (Гавана, 1988 г.),"Информатиха-90" (Гавана, 1990 г.), Международных школах-семинарах по биокибернетике (Варшава, 1986 г., 1987 г.), Российско-Германском семинаре "Понимание изображений и распознавание образов" (Зрланген, 1993 г.), семинарах Вычислительного центра РАН (1977 г., 1981 г., 1987 г., 1994г.), факультета БЫК МГУ (1977 г.). Института Социально-экономических проблем РАН (Санкт-Петербург, 1989 г.), Московского физико-технического института (1977 г., 1994 г.), Белорусского Государственного университета (Минск, 1986 г.). Сибирского научно-исследовательского института нефтяной промышленности (Тюмень,1992 г.), Института математики АН ГДР (Берлин, 1985 г.), Гумбольд--университета (Берлин, 1983 г.), Вильгельм Пик- университета (Росток, 1983 г.), Высшей технической школы (Магдебург, 1985 г.), Института математики, кибернетики и физики АН Кубы (Гавана, IS88 г., 1990 г.).
Реализация. Разработанные в диссертации методы, алго-ритмы и программные системы были использованы при решении различных прикладных задач (более 20 наименований) и внедрены в П/0 "ЮГАЯСКНВИЕГАЗ" (Нефтеюганск, Г986 г.), СибГОИП (Тюмень, 1992 г.), "ШКГРПРОГРАММСКСТШ" (Тверь, 1989 г. ), рядэ научных и производственных учреждений МО, Министерства
здравохранения, Министерства сельского хозяйства.
Публикации. Результаты опубликованы в 41 печатной работа.. Личный вклад автора в совместных работах, имеющих прикладной характер, состоит в формальных постановках, разработке алгоритмов и программ, связанных с реализацией методов построения оптимальных коллективных решений в задачах распознавания и классификации. В статье /35/ автором написаны первые два главы.
Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы из 174 наименований. Обгем диссертации 263 стр. машинописного текста.