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

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

МАМАТОВ Евгений Михайлович

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

Специальность 05.13.01 Системный анализ, управление и обработка информации (информационно-телекоммуникационные системы)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Белгород 2006

Работа выполнена в Белгородском государственном университете

Научный руководитель:

доктор технических наук, профессор Жиляков Евгений Георгиевич

Официальные оппоненты:

доктор технических наук, профессор Капалин Владимир Иванович

кандидат технических наук, доцент Васильев Павел Владимирович

Ведущая организация:

Орловский государственный технический университет

Защита состоится «16» ноября 2006 г. в 14.00 на заседании диссертационного совета Д.212.015.04 при Белгородском государственном университете: 308015, г. Белгород, ул. Победы, 85.

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

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

Ученый секретарь диссертационного совета

С.Е. Савотченко

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

разрезания графов. Для реализации алгоритма создана программная поддержка, которая прошла опытно-промышленные испытания в ФГУП ВИОГЕМ и показала свою работоспособность в ходе тестовых испытаний с использованием реальных данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

• Международная научно-практическая конференция, посвященная 30-летию академии «Качество, безопасность, энерго- и ресурсосбережение в

промышленности строительных материалов и строительстве на пороге XXI века», г. Белгород, 2000г.

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

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

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

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

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

Научные публикации по теме диссертации — 17(в журналах из списка ВАК - 1; в материалах конференций - 8; тезисов докладов - 3; зарегистрированных патентов и свидетельств - 1 (список ВАК); в других научных изданиях - 4;). Объем и структура работы

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

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

Введение

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

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

Процессы классификации объектов и распознавания образов здесь представлены в виде SADT (Structured Analysis and Design Technique) диаграмм. Данные процессы декомпозированы в подпроцессы (рис.1, рис.2).

Рис. 1. Процесс классификации объектов

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

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

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

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

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

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

Рис. 2. Процесс распознавания образов

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

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

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

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

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

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

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

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

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

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

Рис. 3 Неоднородность плотности точек

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

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

- т

1пИ

где х = (х......хы)'; штрих означает транспонирование;

м

Нетрудно доказать справедливость утверждений:

О ^ Р(х) < 1; (3)

тах(Р(х)) = 1, (4)

тогда и только тогда, когда

1

Xi = N;

(5)

min F(x) = 0, (6)

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

Промежуточные значения F(x) будут соответствовать иным соотношениям между компонентами х.

Следует отметить, что элементы матрицы Гессе

3'F 1 . . м аГВСТ r'J = 1-N' (7)

Ge~

обладают свойствами

d2F дх.дх,

О, г*j, 1

---, r = j,

х,

(8)

то есть Ge является отрицательно определ енной.

Следовательно F(x) имеет единственный глобальный максимум, что является полезным свойством для задач оптимизации.

В заключение можно сказать, что сумма в правой части (1) по форме совпадает с определением энтропии в теории информации. Поэтому функцию F(x) представляется уместным назвать информационным критерием.

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

Уточним постановку задачи классификации. Пусть исходное множество содержит М элементов, которые необходимо разбить на К классов. В дальнейшем Mq означает мощность q-oro подмножества, так что

4=1

На основе разработанной меры однородности в данной главе был сконструирован новый функционал

¿ = (Ю)

GR

где D - мера однородности расстояний между центрами тяжестей классов; Н -мера однородности количества элементов в классах; G - мера однородности расстояний между элементами одного и того же класса; R - Мера однородности максимальных расстояний между объектами одного и того же класса.

Формальное представление всех предпочтений функционала содержит формулу вида (1).

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

Поэтому для меры О предлагается использовать представление вида

к к

Ьп(К(К-1)/2)

где К — количество классов,

(И)

(12)

XXX

1=1 ¿-1+1

где Уч, - расстояние между геометрическими центрами тяжестей я - ого и 1 - ого классов.

Ввиду свойств (4) и (5) будет иметь место Бтах = 1 когда все расстояния между геометрическими центрами тяжести классов будут равны, а ввиду свойства (6) будет иметь место Этт = 0 когда К=>1.

Для меры Н предлагается на основе выражения (1) использовать представление

к

Хтч-1л(тч)

н = ~а=!-

(13)

Ьп(К)

где т =-

м„

" М

Ввиду свойств (4) и (5) будет иметь место Нтах = 1 когда количества элементов в классах будут равны. Виду свойства (6) будет иметь место Нпип = 0 когда в одном классе будут содержаться все элементы исходного множества, а в остальных ни одного.

Мера в определяется соотношением

Лм.ч

1 к

К- ,=1

¿р;,-Ьп(р!ч) _

Ьп(М„ -1)

где

р

А£с'

/■=1

(14)

(15)

(16)

- общая длина внутренних ребер q-гo подмножества, а г,ч - длина ¡-ого

ребра в я-ом подмножестве (¡=1,...,Мч-1). Ребра получаются путем построения минимального остового дерева для каждого класса.

Ввиду того, что в находится в знаменателе функционала будет иметь место Сшах = 1 при максимальной неоднородности внутриклассовых расстояний и Отт =0 когда однородность внутриклассовых расстояний буде наилучшей. Мера Я по аналогии с мерой О имеет представление

Л = 1+

Ьп(К)

где

(18)

где - максимальное из расстояний между самыми дальними элементами ц - ого класса.

Ввиду свойств (4) и (5) будет иметь место 11тт = 0 когда максимальные расстояния между самыми дальними элементами каждого из классов будут равны. Виду свойства (2.6) будет иметь место Яшах = 1 когда в одном классе будут содержаться все элементы исходного множества, а в остальных ни одного.

На практике предельные случаи мер (11), (13), (14), (17) при большом количестве объектов в исходном множестве встречаются довольно редко.

На основе функционала (10) в рамках настоящей работы разработан вариационный алгоритм автоматической классификации объектов.

На первом этапе вычисляется матрица расстояний с использованием Евклидовой меры расстояния.

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

Пр.1

Пр.2

Рис. 4. Результат работы алгоритма Р. Прима

Далее необходимо предусмотреть оценку граничного случая, при котором все объекты принадлежат одному классу, то есть все объекты в заданном признаковом пространстве находятся друг от друга на одинаковых расстояниях. В таких случаях все ребра КНП равны. Для этого следует вычислить и запомнить значение функционала Ь (10) при 0=Н=:И=1, а значение меры й вычисляется по выражению

ЛГ -1

в =.-! + -

- ¿"(А)

(=1__

Ьп{М -1) !

где

и

5>,=Л;

(19)

(20) (21)

(I

И.ч - общая длина внутренних ребер КНП, а г, - длина 1-ого ребра в КНП 1, ...,М-1).

Следующим этапом работы алгоритма будет поиск и «разрезание» в КНП самого длинного ребра. Таким образом, мы получим ш исходного КНП два поддерева, соответствующих дву м классам (см. рис. 5).

На основе полученного разбиения вычислим функционал Ь (10), содержащий компоненты Е>, Н, II и <3.

Мера О вычисляется согласно выражений (11) и (12), где К12 определяется как расстояние между геометрическими центрами тяжестей между 1 и 2 классами (см. рис. 6). На данном шаге мера О будет равна нулю, так как расстояние между классами будет одно (приграничный случай). Поэтому в данном случае положим 0=1 для исключения влияния этой меры на значение функционала.

Рис. 5. Два поддерева, соответствующие двум классам

Мера Н вычисляется с помощью выражения (13) при известных М| и М2 (см. рис. 6).

Рис. 6. Данные дая вычисления функционала

Мера Я вычисляется согласно выражения (17) при известных , и .

Мера О определяется согласно выражений (14), (15) и (16).

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

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

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

1*110. 7. Результат работы алгоритма Данный алгоритм был реализован с помощью среды программирования DELPHI 7 и зарегистрирован в Отраслевом фонде алгоритмов и программ. Копия свидетельства о регистрации в приложении № 1.

Достоинствами вариационного алгоритма автоматической классификации объектов с новым функционалом качества разбиения являются:

1. Возможность разбивать исходное множество объектов на классы как со сферической формой, так и не сферической, то есть с вычурной формой;

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

3. Конечное разбиение объектов на классы соответствует глобальному экстремальному значению функционала, а не локальному.

4. Вариационный алгоритм может выделять в отдельные классы объекты-прецеденты.

В рамках данной главы проведены вычислительные эксперименты :

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

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

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

В заключении главы отмечено то, что были решены следующие задачи:

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

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

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

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

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

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

По аналгии с выражениями (1) — (6) разработан следующий подход для определения весов информативности количественных признаков.

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

5Л. (22)

1

где Д|у — расстояние между соседними значениями центров классов признака

д*(2з>

Следует заметить, что выполняется равенство

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

Следует подчеркнуть, что при применении выражения (25) значение V будет максимальным и равным 1 только тогда, когда Л4 = сотг, т.е. значения центров классов признака распределены равномерно, соответственно V—>0 при выполнейии условия :

^->0, к~\,...,М—\, к Ф т, (26)

где т — любой из номеров интервалов.

Такое поведение V соответствует ишуитивному представлению об информационной различающей силе признаков.

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

Значение веса признака сравнивалось с оценкой вероятности правильного распознавания при распознавании объектов полученных:

1. путем добавления к исходным объектам равномерно распределенной случайной величины в интервале (А,В);

2. путем добавления к исходным объектам распределенной по Гауссу случайной величины с математическим ожиданием ш и дисперсией а.

На основе результатов эксперимента были построены следующие графические зависимости (при количестве классов М = 200, количестве объектов в классе К=50, количестве раз изменения значений признака Н=200):

1. Зависимость оценки вероятности правильного распознавания Р" объектов, полученных путем добавления к исходным объектам равномерно распределенной случайной величины в интервале INT от веса признака V (рис. 8).

2. Зависимость оценки вероятности правильного распознавания /"объектов, полученных путем добавления к исходным объектам распределенной по Гауссу случайной величины с математическим ожиданием ш=0 и дисперсией с ~ S*Int, где S=3, от веса признака V (рис. 9).

3. Зависимость оценки вероятности правильного распознавания Р* объектов, полученных путем добавления к исходным объектам распределенной по Гауссу случайной величины с математическим ожиданием т=0 и дисперсией о = S*Int, где S=-. от веса признака V (рис. 10).

0.74

0,66

I

| 0,49 8 0.41

к033

«{0,25 0,16 о,ов

(1,25 0.33 0,41 0,43 3.57 О,И 0,74 0,82 0.9 0.9« Весг^ипнак*

Рис. 8. Зависимость оценки вероятности правильного распознавания Р" объектов от веса признака V д.тя первого случая

9.492 £ В."

С 0,326 |

|о,В4 0.093

Рис. 9. Зависимость оценки вероятности правильного распознавания Рг объектов от веса признака V для второго случая

0,083

г 0,1313 о

£ 0,655

а

2 0,«92 а

^ 0,328 0,1 В4

Рис. 10 Зависимость оценки вероятности правильного распознавания Рг объектов от веса признака V для третьего случая

i .

.....

> 1 • 1 1 Г 1 •

1 1 1 • 1 1 » » 1

: :

; • ! : : . :

1 < >(•>

.....?",:". ................

0,346 0.328 й,< 1 0,482 0,573 0.SSS € ,П7 0.U19 0,901 0,9 »3 вес гомэимгя

I-W

.«с*

—(0,993

0,246 0.333 0,11

0,432 С,573 Q.SS5 0.737 0,819 0,901 Bt>c прианака

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

Для оценки равномерности расстояний между объектами в классе следует построить в выбранном признаковом пространстве конечный незамкнутый путь (КНП) или по-другому минимальное остовое дерево. Зная расстояния между объектами, то есть длины ребер КНП по аналогии с выражениями (22-25) можно определить репрезентативность класса объектов.

Таким образом, репрезентативность i-oro класса будет равна

где R, - ребро КНП i-oro класса.

Следует отметить в (27) отсутствие нормировочного знаменателя Ln(K-l), что дает возможность учесть не только равномерность (однородность) ребер КНП, но и их количество.

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

Вычислительный эксперимент по сравнению ABO с использованием весов признаков и репрезентативностей классов и без их использования действительно показал то, что применение информационной меры однородности в алгоритмах вычисления оценок не только придает им гибкость, но в некотором смысле увеличивает устойчивость работы ABO. Результат работы алгоритмов вычисления оценок с использованием весов признаков и репрезентативностей классов и без их использования при коэффициенте корреляции Rk=0,7 и с разными значениями дисперсий = . представлены на рис. 11.

(27)

где К, - количество объектов в i-ом классе, а

(28)

о

3 5 7 9 Значения диссперсий

—«— алгоритм с

— алгоритм без использования весов признаков и репр. классов

использованием весов признаков и репр. классов

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

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

1. Разработана и исследована мера информативности признаков при распознавании образов с использованием мегода алгоритмов вычисления оценок (ABO);

2. Разработана и исследована мера репрезентативности классов в методе ABO распознавания образов.

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

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

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

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

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

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

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

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

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

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

географического факультета БелГУ по автоматизированному районированию экологического состояния территории города по данным лихеноиндикации. Вычислительный эксперимент доказывает то, что разработанный вариационный алгоритм автоматической классификации объектов в сочетании с картографированием может быть использован при оценке состояния урбоэкосистем и стоимости городских земель. Результаты автоматической классификации мест забора проб показателей экологического состояния были обработаны и введены в геоинформационную систему «БелГИС», с помощью которой была сгенерирована карта зонирования территории города Белгорода по экологической напряженности, представленная на рис. 12.

Зонирование территории города Белгорода

- - границы зон

Рис. 12. Зонирование территории города Белгорода

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

7. Разработана программно-алгоритмическая реализация поиска максимального значения функционала качества разбиения.

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

9. Разработан прототип программной системы, включающий в себя подсистемы автоматической классификации объектов и распознавания образов по методу Ю.И.Журавлева (ABO), объединенные общим интерфейсом.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Житков Е.Г., Маматов Е.М. Информационный критерий однородности классификации объектов.// Российская научная конференция «Экономические информационные системы на пороге XXI века» :Сборник докладов / Московский государственный университет экономики, статистики и информатики:-М., 1999. -С. 197-200.

2. Жиляков Е.Г., Маматов Е.М. Использование информационной меры в автоматической классификации объектов // Международная научно-практическая конференция, посвященная 30-летию академии «Качество, безопасность, энерго- и ресурсосбережение в промышленности строительных материалов и строительстве на пороге XXI века». -Белгород: Изд-во БелГТАСМ, 2000г.

3. Жиляков Е.Г., Маматов Е.М. Классификация месторождений сырья для производства строительных материалов. // Седьмые Академические чтения РААСН «Современные проблемы строительного материаловедения». - Белгород: Изд-во БелГТАСМ, 2001.

4. Жиляков Е.Г., Маматов Е.М. Об Автоматической классификации объектов // Математическое моделирование в научных исследованиях / Материалы Всероссийской научной конференции. 4.1. - Ставрополь: Изд-во СГУ, 2000. - С. 36-38.

5. Жиляков Е.Г., Маматов Е.М. Определение весов признаков в алгоритмах вычисления оценок // Распознавание образов и обработка информации Сб. науч. тр. - Минск, 1999.

6. Жиляков Е.Г., Маматов Е.М. Оценка информативности признаков в задачах распознавания образов. // Россия на пороге XXI века. Региональные особенности в процессе трансформации общества: Тезисы Международной научно-практической конференции, г.Архангельск, 29 мач 1999 г. - Архангельск: Мевдународный «ИНСТИТУТ УПРАВЛЕНИЯ», 1999.

7. Жиляков Е.Г., Маматов Е.М. Программа автоматической классификации объектов на основе информационной меры однородности. // Отраслевой фонд алгоритмов и программ ФГНУ «Государственный координационный центр информационных технологий» - 2006 г.

8. Лисецкий Ф.Н., Жиляков Е.Г., Удянская Е.А., Маматов Е.М. Автоматизированное районирование экологического состояния территории города по данным лихеноиндикации. // V Всеросийский симпозиум «Математическое моделирование и компьютерные технологии». - Кисловодск: Кисловодский институт Экономики и права, 2002. -С.. 37-39.

9. Маматов Е.М. Автоматизированное рабочее место для автоматической классификации объектов и распознавания образов. // Вестник Национального технического университета "Харьковский политехнический институт". Сборник научных трудов. Тематический выпуск: Информатика и моделирование. - Харьков: НТУ «ХПИ», - 2003. - №26. -С.111- 114.

10. Маматов Е>М. Алгоритмы классификации объектов и распознавания образов в промышленности по производству строительных материалов. // Вестник БГТУ / научно-теоретический журнал. / Материалы международного конгресса «Современные технологии в промышленности строительных материалов и стройиндустрии», посвященного 150-летию В.Г. Шухова /Часть III. - №6.2003г„ с 166-168.

11. Маматов Е.М. Модели голосования в задачах распознавания объектов// Компьютерное моделирование : Изд-во БелГТАСМ, 1998. с. 91 - 97.

12. Маматов Е.М. О классификации объектов // Международная научно-практическая конференция Проблемы регионального управления, экономики, права и информационных процессов в образовании: Тезисы докладов научно-практической конференции. - Таганрог. - 1999г.

13. Маматов Е.М. Обработка растровых изображений с использованием вариационного алгоритма автоматической классификации объектов, основанного на функционале однородности. // Современные проблемы прикладной математики и математического моделирования: Материалы конференции. - Воронеж: Воронежск<1Я государственная академия, 2005 г, с. 142.

14. Маматов Е.М. О формировании признакового пространства в задачах распознавания образов и классификации объектов. // ВЕСТНИК Московской академии рынка труда и информационных технологий № 4(26) - 2006г. - с.20 - 28.

15. Маматов Е.М. Определение весомости признаков в задачах распознавания образов и классификации объектов, // Научные ведомости. Белгородский государственный университет. Серия: Информатика и прикладная математика. № 2., Выпуск 3,. Белгород: Изд-во БелГУ - 2006г., с 107 - 117.

16. Маматов Е.М. Определение порог ов близости для метрики Журавлева в задачах классификации объектов. // Потребительская кооперация России н i пороге трегьего тысячелетия: Тезисы докладов научно-практической конференции профессорско-преподавательского состава 4.2 - Белгород: Изд-во БУПК, 1999, с. 108-109.

17. Маматов Е.М. Оценка информативности признаков при решении задач классификации объектов. // Потребительская кооперация России на пороге третьего тысячелетия: Сборник научных трудов участников научно-практической конференции профессорско-преподавательского состава 4.2 - Белгород: Изд-во БУПК, 1999, с. 165-175.

Подписано в печать 26.09.2006. Формат 60x84/16. Гарнитура Times. Усл. п. л. 1,0. Тираж 100 экз. Заказ 210. Оригинал-макет подготовлен и тиражирован в издательстве Белгородского государственного университета 308015 г. Белгород, ул. Победы, 85

Введение.

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

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.