WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

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

Борисова Ирина Артемовна

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАСПОЗАНАВАНИЯ ОБРАЗОВ

КОМБИНИРОВАННОГО ТИПА

Специальность 05.13.17 – Теоретические основы информатики

Автореферат диссертации на соискание ученой степени

кандидата технических наук

Новосибирск 2008

Работа выполнена в Институте математики им. С.Л. Соболева СО РАН,

г. Новосибирск

Научный руководитель: доктор технических наук, профессор

Загоруйко Николай Григорьевич

Официальные оппоненты: доктор технических наук, профессор

Попов Александр Александрович

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

Витяев Евгений Евгеньевич

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН,

г. Новосибирск

Защита состоится « 13 » ноября 2008 года в 14-00, на заседании диссертационного совета Д 212.173.06 при Новосибирском государственном техническом университете по адресу: 630092, г. Новосибирск, пр. Карла Маркса, 20.

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

Автореферат разослан « » октября 2008 г.

Ученый секретарь

диссертационного совета Чубич В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Основным объектом исследования в данной работе являются задачи распознавания образов комбинированного типа. Такого рода задачи возникают в случае, когда для более полного и всестороннего анализа выборки одновременно и согласованно решается несколько задач распознавания образов основных типов (к ним относятся задачи построения решающего правила, таксономии, выбора информативных признаков). Комбинированные задачи хорошо согласуются с механизмами анализа информации, используемыми человеком, и открывают новые возможности для решения сложных плохо обусловленных прикладных задач, количество которых неуклонно возрастает в последнее время. Ярким примером этих задач являются задачи в генетике и медицине, в которых небольшое число объектов (пациентов, страдающих определенным заболеванием) описывается огромным количеством признаков (симптомов, вплоть до описания активности отдельных генов). В связи с практической значимостью такого рода «некорректных» с точки зрения классической теории распознавания задач, разработка методов их решения приобретает все большую актуальность.

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

Основные направления исследований. В качестве основы для большинства предложенных алгоритмов используется функция конкурентного сходства (FRiS-функция) и некоторые ее модификации. Исследуется эффективность FRiS-функции при выборе информативной системы признаков. Показывается применимость FRiS-функции для обнаружения зон локального сгущения объектов. Сочетание этих свойств позволяет успешно использовать FRiS-функции при формировании критериев качества решений различных задач комбинированного типа.

Методы исследований опираются на аппарат методов оптимизации, используются элементы математической статистики, широко применяется имитационное моделирование.

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

  1. В рамках исследования применимости FRiS-функций показана их эффективность в качестве критерия информативности при решении задачи одновременного построения решающего правила и выбора наиболее информативного подпространства признаков. Предложена методика оценки надежности получаемых информативных систем признаков, их «неслучайности». Также предложена методика оценки надежности распознавания каждого нового объекта при использовании решающих правил, полученных с помощью алгоритма FRiS-Stolp.
  2. Разработан алгоритм FRiS-Tax для решения задачи комбинированного типа – одновременного построения таксономии и решающего правила, ее описывающего. Этот алгоритм не только хорошо воспроизводит результаты, получаемые человеком-экспертом при решении задачи таксономии в пространствах малых размерностей, но и позволяет автоматически определять наилучшее число таксонов из заданного диапазона.
  3. Сформулированы основные требования, предъявляемые к «естественным» классификациям. Установлена связь между задачей построения «естественной» классификации и задачей комбинированного типа – построением таксономии с одновременным выбором наиболее информативного подпространства признаков. Для решения данной задачи разработан алгоритм NatClass.
  4. Сформулирована наиболее сложная задача распознавания образов комбинированного типа – задача одновременного построения таксономии и решающего правила для ее описания в наиболее информативном признаковом пространстве. Предложена методика решения этой задачи, позволяющая максимально структурировать массивы данных в случае отсутствия какой бы то ни было дополнительной информации относительно природы этих данных. На основе этой методики разработан алгоритм FRiS-SDX.

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

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

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

  • KDS-2001, 2007 (Knowledge-Dialog-Solutions),
  • PRIA-2004, 2007 (Pattern Recognition and Image Analysis),
  • PRIP-2005, 2007 (Pattern Recognition and Image Processing),
  • ММРО-12, 13 (Математические Методы Распознавания Образов),
  • ACIT-SE-2005 (Automation, Control and Information Technology),
  • BGRS-2006 (Bioinformatics of Genome Regulation and Structure),
  • ЗОНТ-2007 (Знания, Онтологии, Теории).

Отдельные этапы работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ (проекты № 02-01-00082-а, №05-01-00241-а).

Личный вклад. Основные результаты, связанные с разработкой, исследованием и апробацией алгоритмов FRiS-Tax, Nat-Class и FRiS-SDX получены автором лично. Постановка задач комбинированного типа и обсуждение возможных путей их решения осуществлялись совместно с руководителем. Исследование эффекта «псевдоинформативности» и способов снижения его влияния проводилось совместно с соавторами. Методика восстановления зависимости между величиной FRiS-функции и надежностью распознавания конкретного объекта по обучающей выборке, а также способ оценки информативности через сравнение подсистемы признаков, выбранной на реальных данных, с аналогичной подсистемой, выбранной на случайных таблицах, разработана лично соискателем.

Публикации. По теме диссертации опубликованы 16 работ, из них 2 научные статьи в журналах, входящих в перечень изданий, рекомендованных ВАК РФ, 2 научные статьи в ведущих рецензируемых журналах, 2 – в сборниках научных трудов, 10 – в сборниках трудов конференций.

Структура работы. Диссертационная работа изложена на 121 страницах и состоит из введения, обзора литературы (глава 1), четырех глав, содержащих основные результаты, и заключения. Иллюстративный материал представлен 24 рисунками и 1 таблицей. Список литературы включает 77 ссылок.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

  • DX – задача одновременного построения решающего правила и наиболее информативного пространства признаков;
  • SX – задача таксономии и одновременного отыскания информативного пространства признаков;
  • SD – задача одновременного построения таксономии и решающего правила для дальнейшего ее распознавания;
  • SDX – задача одновременного построения таксономии, решающего правила для ее распознавания и пространства информативных признаков.

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

Хотя термин «задача комбинированного типа» известен с 70-х годов, эту область нельзя назвать тщательно проработанной. Если задачей DX занималось и занимается большое количество исследователей, то задача SX решается в основном в статистической постановке, когда выбор признаков осуществляется после фиксации вероятностной модели рассматриваемой выборки с точностью до нескольких параметров. Что касается наиболее сложной и интересной задачи комбинированного типа – задачи SDX - серьезных исследований, касающихся методов ее решения, очень немного.

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

Во второй главе дается определение функции конкурентного сходства (FRiS-функции) и исследуется ее применимость при решении задачи комбинированного типа DX.

Рассмотрим обучающую выборку А, состоящую из m объектов, описанных множеством из n признаков X. Все объекты разделены на k классов. Каждый класс описывается набором из l эталонных образцов (столпов). Соответственно, вся обучающая выборка А описывается набором столпов. В общем случае S может состоять как из реальных объектов выборки A так и из искусственно сгенерированных эталонов классов. Мы будем рассматривать только случай SA. Для объекта a из обучающей выборки A, относящегося к классу определим r1(a,S)= – расстояние до ближайшего столпа «своего» образа, а r2(a,S)= – расстояние до ближайшего столпа образа-конкурента. Тогда функция конкурентного сходства объекта a со своим классом вычисляется по формуле:

Если мы найдем среднее значение FRiS-функции при фиксированном наборе столпов S по всей выборке, то полученная величина:

= (1)

характеризует, насколько полно этот набора столпов описывает выборку. Чем больше, тем более подробное и точное описание выборки у нас имеется. На этом свойстве FRiS-функции основывается алгоритм FRiS-Stolp, создающий в процессе работы сокращенное описание выборки A в виде набора столпов S. Его использование позволяет сократить описание выборки, избавиться от ошибок и «выбросов», содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов. Непосредственно распознавание при этом осуществляется по следующему правилу: объект относится к тому классу, конкурентное сходство с которым оказывается максимальным.

Аналог величины, вычисленный для случая, когда все объекты выборки считаются ее столпами (когда в качестве r1 берется расстояние до ближайшего объекта «своего» образа, а в качестве r2 – расстояние до ближайшего объекта из образа «конкурента») обозначим за FS. Он позволяет оценить, насколько отделены друг от друга образы в пространстве описывающих признаков X. Поэтому величина FS может использоваться в качестве критерия для выбора наиболее информативного подпространства признаков, в котором образы максимально отделены друг от друга.

В рамках данной работы показывается, что критерий FS, основанный на функции конкурентного сходства, оказывается эффективнее существующих аналогов, таких как средняя ошибка распознавания, оцениваемая в режиме скользящего экзамена U, критерий Фишера Q, взвешенный критерий семейства алгоритмов RELIEF W. Результаты сравнения этих критериев на серии модельных задач приводятся на рис. 1. Здесь по оси абсцисс откладывается количество признаков в выбранной информативной подсистеме, по оси ординат – надежность этой подсистемы при распознавании контрольной выборки.

Рис. 1 Сравнение эффективности четырех критериев выбора информативной системы признаков.

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»