Применение информационной меры однородности в задачах автоматической классификации объектов и распознавания образов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Маматов, Евгений Михайлович

• Маматов, Евгений Михайлович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Маматов, Евгений Михайлович

Введение.

Глава 1. Методы классификации объектов и распознавания образов.

1.1. Методы и алгоритмы классификации объектов. i# 1.2. Методы и алгоритмы распознавания образов.

1.3. Распознавание образов на основе алгоритмов вычисления оценок.

1.4. Постановка задач исследований.

Глава 2. Разработка и применение информационной меры однородности характеристик объектов в вариационном алгоритме автоматической классификации объектов.

2.1. Вариационные алгоритмы автоматической классификации объектов критерии качества классификации объектов).

2.2 Разработка и исследование свойств критерия однородности основанного на информационной мере.

2.3. Построение функционала качества классификации объектов на базе критерия однородности.

2.4. Разработка алгоритма классификации объектов с новым функционалом качества.

2.5. Вычислительные эксперименты по сравнению работы алгоритма КРАБ с новым вариационным алгоритмом автоматической классификации объектов.

2.6. Вычислительный эксперимент по оценке классификации объектов вариационным алгоритмом с новым функционалом качества.

Введение диссертации (часть автореферата) на тему «Применение информационной меры однородности в задачах автоматической классификации объектов и распознавания образов»

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

Задача распознавания образов заключается в отнесения неизвестного объекта (ОИ) исследования к одному из априорно заданных классов объектов определенной предметной области. Очень часто классы, задаваемые относительно задачи распознавания, называют образами. Следовательно, отсюда и название [15-16].

Основное отличие задачи классификации объектов от задачи распознавания образов заключается в том, что на этапе постановки задачи распознавания используется априорная информация о принадлежности известных ОИ к конечному числу классов, которую получают в ходе выполнения процесса классификации объектов [4].

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

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

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

Для достижения этой цели на основе анализа состояния вопроса были сформулированы и решены следующие задачи:

1. Разработка и исследование свойств критерия однородности основанного на информационной мере.

2. Разработка и исследование вариационного алгоритма автоматической классификации объектов на основе информационной меры однородности.

3. Разработка и исследование меры информативности признаков при распознавании образов с использованием метода алгоритмов вычисления оценок (АВО).

4. Разработка и исследование меры репрезентативности классов в методе АВО распознавания образов.

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

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

1. Методы классификации объектов.

2. Методы распознавания образов.

3. Вычислительный эксперимент.

4. Методы системного анализа.

5. Вариационные методы обработки информации. Научно-практическая значимость работы.

Научная новизна работы заключается:

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

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

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

4. В предложенной мере репрезентативности классов для задачи распознавания образов по методу Ю.И.Журавлева (АВО).

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

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

1. Критерий однородности, основанный на информационной мере в виде аналога негэнтропии по Шеннону.

2. Вариационный алгоритм автоматической классификации объектов на основе информационной меры однородности.

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

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

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

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

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

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

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

• Международная научно-практическая конференция «Региональные особенности в процессе трансформации общества», г Архангельск, 1999 г.

• Российская научная конференция "Экономические информационные системы на пороге XXI века" г.Москва, 1999г.

• Международная научно-практическая конференция, посвященная 30-летию академии "Качество, безопасность, энерго- и ресурсосбережение в промышленности строительных материалов и строительстве на пороге XXI века", г. Белгород, 2000г.

• Седьмые Академические чтения РААСН «Современные проблемы строительного материаловедения» г.Белгород, 2001г.

• Международный конгресс «Современные технологии в промышленности строительных материалов и стройиндустрии», г.Белгород,2003г.

• Конференция «Современные проблемы прикладной математики и математического моделирования», г.Воронеж, 2005г.

Связь с научно техническими программами

Разработка нового вариационного алгоритма автоматической классификации объектов частично финансировалась в рамках гранта Министерства образования и науки РФ по проекту РНП.2.1.2.4974 «Разработка и исследование вариационных методов анализа и восстановления сигналов в линейных системах по дискретным эмпирическим данным ограниченной длительности». Публикации

Научные публикации по теме диссертации составляют следующий объем - 17, в том числе:

• в журналах из списка ВАК: I;

• в зарубежных международных журналах: 0;

• в других научных изданиях: 4;

• в материалах конференций: 8;

• тезисов докладов: 3;

• монографий: 0;

• зарегистрированных патентов и свидетельств: 1 (список ВАК);

• из них без соавторов: 9. Объем и структура работы

Диссертационная работа состоит из Введения, четырех глав, Заключения и Приложений. Работа изложена на 144 страницах машинописного текста, включающего 56 рисунков, 4 таблицы и список литературы из 152 наименований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Маматов, Евгений Михайлович

4.6. Основные результаты и выводы главы т

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

1. Генерировать исходное множество объектов случайным образом по нормальному закону распределения в двухмерном признаковом пространстве. Данные генерации сохраняются в базе данных (БД) для последующего их разбиения на классы.

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

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

4. В случае двухмерных объектов выводить результат в виде конечного незамкнутого пути в графическом поле с окрашиванием вершин дерева (объектов) в цвета соответственно принадлежащим определенным классам. Также в этом случае информация об объектах и о результатах разбиения выводиться в текстовое поле. В случае агрегирования объектов (3-7) - ми мерном пространстве признаков информация об объектах и о результатах разбиения выводиться так же в текстовое поле.

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

6. Основываясь на результатах разбиения, распознавать вновь введенные т единичные объекты.

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

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

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

Также работоспособность информационной технологии автоматической классификации объектов подтверждена результатами опытно-промышленных тестовых испытаний с использованием реальных данных в ФГУП ВИОГЕМ (Приложение №4).

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

Заключение

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

1. Разработка и исследование свойств критерия однородности основанного на информационной мере.

2. Разработка и исследование вариационного алгоритма автоматической классификации объектов на основе информационной меры однородности.

3. Разработка и исследование меры информативности признаков при распознавании образов с использованием метода алгоритмов вычисления оценок (АВО).

4. Разработка и исследование меры репрезентативности классов в методе АВО распознавания образов.

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

В ходе решения поставленных задач были получены определенные результаты. К наиболее важным и новым результатам диссертационной работы относятся:

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

2. Разработан функционал качества классификации, в котором формализованы четыре предпочтения о качестве классификации. Результат классификации исходного множества объектов на подмножества будет тем лучше, чем : 1) равномернее распределены объекты внутри каждого класса; 2) однороднее размеры получаемых классов; 3) равномернее расстояния между полученными классами; 4) равномернее насыщение классов объектами, т.е. однороднее количество элементов по классам.

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

128 максимальное значение. Работоспособность алгоритма, реализованного в виде программно - алгоритмической поддержки информационной технологии подтверждена результатами опытно-промышленных тестовых испытаний с использованием реальных данных в ФГУП ВИОГЕМ (Приложение №4).

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

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

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

7. Разработан прототип системы автоматической классификации объектов и распознавания образов по методу Ю.И.Журавлева (АВО) с использованием весов признаков и репрезентативностей классов, значения которых получены путем применения меры однородности. Таким образом, в прототипе системы есть две подсистемы (распознавания и классификации),в каждой из которых использована разработанная в данной работе информационная мера однородности.

Список литературы диссертационного исследования кандидат технических наук Маматов, Евгений Михайлович, 2006 год

1. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика, 1974.

2. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970.

3. Алгоритмы обучению распознаванию образов / Под. ред. В.Н. Вапника. Сов. радио, 1973.

4. Александров В.В., Горский Н.Д. Алгоритмы и программы структурного метода обработки данных. Л.: «Наука», 1983, с.208.

5. Белкин А.Р., Левин М.Ш. Принятие решений: Комбинаторные модели аппроксимации информации. Москва: Наука, 1990.

6. Бериков В.Б., Лбов Г.С. О прогнозирующей способности методов распознавания. // Доклады Всероссийской конференции «Математические методы распознавания образов», ММРО 12: Изд-во ВЦ РАН, Москва, 2005. с. 29 - 31.

7. Берлянт A.M. Геоиконика. М., 1996. - 208 с.

8. Бондарев В.М, Основы программирования. Ростов-на-Дону "Феникс" 1997.

9. Боровиков В.П. Русская версия системы STATISTICA // КомпьютерПресс. -1999. №5.

10. Бородин А.Н. Элементарный курс теории вероятностей и математической статистики. СПб: Лань, 1999. - 224 с.13.