Содержание к диссертации
Введение
Глава 1. Методы классификации объектов и распознавания образов 15
1.1. Методы и алгоритмы классификации объектов 15
1.2. Методы и алгоритмы распознавания образов 29
1.3. Распознавание образов на основе алгоритмов вычисления оценок 35
1.4. Постановка задач исследований 38
Глава 2. Разработка и применение информационной меры однородности характеристик объектов в вариационном алгоритме автоматической классификаций объектов 43
2.1. Вариационные алгоритмы автоматической классификации объектов (критерии качества классификации объектов) 43
2.2 Разработка и исследование свойств критерия однородности основанного наинформационной мере 46
2.3. Построение функционала качества классификации объектов на базе критерия однородности 47
2.4. Разработка алгоритма классификации объектов с новым функционалом качества 50
2.5. Вычислительные эксперименты по сравнению работы алгоритма КРАБ с новым вариационным алгоритмом автоматической классификации объектов 55
2.6. Вычислительный эксперимент по оценке классификации объектов вариационным алгоритмом с новым функционалом качества 63
2.7. Основные результаты и выводы главы 74
Глава 3. Разработка и применение информационной меры однородности характеристик объектов при распознавании образов 78
3.1. Разработка и исследование меры информативности признаков при распознавании образов с использованием алгоритмов вычисления оценок (АВО) 78
3.2. Вычислительные эксперименты по сравнению значения веса признака с оценкой вероятности правильного распознавания 82
3.3. Разработка и исследование меры репрезентативности классов в методе АВО распознавания образов 88
3.4. Вычислительный эксперимент по сравнению работы АВО с использованием весов признаков и репрезентативностей классов и без их использования 90
3.5. Основные результаты и выводы главы 94
Глава 4. Программная поддержка вариационного алгоритма автоматической классификации объектов и алгоритма распознавания образов на основе информационной меры однородности 96
4.1. Обоснование выбора аппаратно - программной платформы для прототипа системы классификации объектов и распознавания образов 96
4.2. Основные функции прототипа системы и их использование 98
4.3. Описание структуры данных прототипа системы 99
4.4. Описание пользовательского интерфейса прототипа системы 106
4.5. Вычислительные эксперименты 116
4.5.1. Автоматизированное районирование экологического состояния территории города по данным лихеноиндикации 116
4.5.2. Использование вариационного алгоритма для классификации изображений 122
4.6. Основные результаты и выводы главы 126
Заключение 128
Литература 130
Приложения 145
Приложение №1. Свидетельство и извещение об отраслевой регистрации разработки 146
Приложение№2. Сравнительное исследование результатов работы алгоритма КРАБ и вариационного алгоритма автоматической классификации объектов, использующего новый функционал качества классификации 150
Приложение №3. Листинг программного модуля предназначенного для извлечения информации с картинки 156
Приложение №4. Акт опытно-промышленных испытаний информационной технологии автоматической классификации объектов 158
- Методы и алгоритмы классификации объектов
- Вариационные алгоритмы автоматической классификации объектов (критерии качества классификации объектов)
- Разработка и исследование меры информативности признаков при распознавании образов с использованием алгоритмов вычисления оценок (АВО)
- Обоснование выбора аппаратно - программной платформы для прототипа системы классификации объектов и распознавания образов
Введение к работе
Одно из центральных мест в прикладном анализе эмпирических данных занимает задача автоматического агрегирования элементов различной природы. Данная задача имеет достаточно большую область применений, например: в кибернетике, управлении, принятии решений, экономике, социологии, медицине, геологии, астрономии, биологии и т. п. Решением задачи автоматической классификации объектов является такое разбиение исходного множества анализируемых объектов без участия человека на непересекающиеся подмножества, в которых содержатся только сходные, близкие друг к другу в заданном признаковом пространстве, в некотором, возможно неизвестном, но объективно существующем отношении.
Задача распознавания образов заключается в отнесения неизвестного объекта (ОИ) исследования к одному из априорно заданных классов объектов определенной предметной области. Очень часто классы, задаваемые относительно задачи распознавания, называют образами. Следовательно, отсюда и название [15 - 16].
Основное отличие задачи классификации объектов от задачи распознавания образов заключается в том, что на этапе постановки задачи распознавания используется априорная информация о принадлежности известных ОИ к конечному числу классов, которую получают в ходе выполнения процесса классификации объектов [4].
Современные методы решения задач классификации объектов базируются на двух основных подходах: эвристическом и вариационном. Вариационный подход наиболее приемлем для решения задачи автоматического агрегирования элементов, хотя и в данном подходе присутствует эвристическая составляющая при построении функционала качества разбиения, экстремальное значение которого соответствует наилучшему разделению в интуитивном понимании исследователя. В некоторых работах обращается внимание на степень однородности (похожести) объектов внутри каждого класса, которая должна быть учтена в функционале качества разбиения. В данной работе предложен критерий однородности, основанный на информационной мере в виде аналога иегэнтропии по Шеннону, который может быть использован при конструировании функционалов, учитывающих степень однородности (похожести) объектов внутри каждого класса.
Актуальность темы диссертационного исследования обусловлена тем, что проблема автоматической классификации объектов и распознавания образов возникает во многих областях науки и техники. Для ее решения предложены различные подходы, в основе которых используются различные принципы, и в частности принцип максимальной однородности, что является моделью принятия решений человеком при ручной классификации. Однако, остается открытым вопрос -какова должна быть мера однородности? В диссертационной работе предложено использовать информационную меру, на основании которой построен функционал качества разбиения, максимизация которого позволяет осуществить автоматическую классификацию. Также предложено использовать информационную меру в алгоритмах вычисления оценок для определения различительной способности признаков (весов) и репрезентативностей классов при решении задач распознавания образов.
Основной целью диссертационной работы является разработка и исследование методов применения информационной меры однородности в задачах автоматической классификации объектов и распознавания образов.
Для достижения этой цели на основе анализа состояния вопроса были сформулированы и решены следующие задачи:
1. Разработка и исследование свойств критерия однородности основанного на информационной мере.
Разработка и исследование вариационного алгоритма автоматической классификации объектов на основе информационной меры однородности.
Разработка и исследование меры информативности признаков при распознавании образов с использованием метода алгоритмов вычисления оценок (АВО).
Разработка и исследование меры репрезентативности классов в методе АВО распознавания образов.
Создание программной поддержки вариационного алгоритма автоматической классификации объектов и алгоритма распознавания образов на основе информационной меры однородности.
В ходе выполнения диссертационной работы были использованы следующие методы исследований:
Методы классификации объектов.
Методы распознавания образов.
Вычислительный эксперимент.
Методы системного анализа.
Вариационные методы обработки информации. Научно-практическая значимость работы.
Научная новизна работы заключается:
В новой мере однородности разбиения объектов на классы в виде функционала, максимизация которого позволяет достичь наилучшего в этом смысле качества автоматической классификации.
В новой мере информативности признаков при распознавании образов с использованием метода алгоритмов вычисления оценок.
В доказательстве прямо пропорциональной зависимости вероятности правильного распознавания на основе некоторого признака от значения его информационной меры однородности.
В предложенной мере репрезентативности классов для задачи распознавания образов по методу Ю.И.Журавлева (АВО).
Практическую значимость составляет созданный в работе вариационный алгоритм максимизации функционала качества автоматической классификации, отражающего принцип максимальной однородности, с использованием метода разрезания графов. Для реализации алгоритма создана программная поддержка.
Получено свидетельство об отраслевой регистрации разработки " Программа автоматической классификации объектов на основе информационной меры однородности " в Отраслевом фонде алгоритмов и программ Федерального агентства по образованию № регистрации 6201.
Положения, выносимые на защиту:
Критерий однородности, основанный на информационной мере в виде аналога негэитропии по Шеннону.
Вариационный алгоритм автоматической классификации объектов на основе информационной меры однородности.
Мера информативности признаков при распознавании образов с использованием метода алгоритмов вычисления оценок.
Мера репрезентативности классов при распознавании образов с использованием метода алгоритмов вычисления оценок.
Вычислительные процедуры вариационного алгоритма автоматической классификации объектов и алгоритма распознавания образов на основе информационной меры однородности.
Программно-алгоритмические реализации разработанных вычислительных процедур.
Достоверность полученных результатов и выводов обусловлена корректностью математических выкладок и подтверждается результатами большого количества вычислительных экспериментов по обработке модельных и реальных эмпирических данных.
Личный вклад соискателя заключается в том, что все изложенные в диссертационной работе результаты исследований получены либо соискателем лично, либо при его непосредственном участии. Апробация работы
Основные результаты работы были представлены на следующих научно-технических конференциях:
Международная научно-практическая конференция «Региональные особенности в процессе трансформации общества», г Архангельск, 1999 г.
Российская научная конференция "Экономические информационные системы на пороге XXI века" г.Москва, 1999г.
Международная научно-практическая конференция, посвященная 30-летию академии "Качество, безопасность, энерго- и ресурсосбережение в промышленности строительных материалов и строительстве на пороге XXI века", г. Белгород, 2000г.
Седьмые Академические чтения РААСН «Современные проблемы строительного материаловедения» г.Белгород, 2001г.
Международный конгресс «Современные технологии в промышленности строительных материалов и стройиндустрии», г.Белгород,2003г.
Конференция «Современные проблемы прикладной математики и математического моделирования», г.Воронеж, 2005г.
Связь с научно техническими программами
Разработка нового вариационного алгоритма автоматической классификации объектов частично финансировалась в рамках гранта Министерства образования и науки РФ по проекту РНП.2Л.2.4974 «Разработка и исследование вариационных методов анализа и восстановления сигналов в линейных системах по дискретным эмпирическим данным ограниченной длительности». Публикации
Научные публикации по теме диссертации составляют следующий объем - 17, в том числе: в журналах из списка ВАК: 1; в зарубежных международных журналах: 0; в других научных изданиях: 4; в материалах конференций: 8; тезисов докладов: 3; монографий: 0; зарегистрированных патентов и свидетельств: 1 (список ВАК); из них без соавторов: 9, Объем и структура работы
Диссертационная работа состоит из Введения, четырех глав, Заключения и Приложений. Работа изложена на L44 страницах машинописного текста, включающего Збрисунков, 4 таблицы и список литературы из 152 наименований.
Работа выполнена в Белгородском государственном университете в соответствии с планами научно-исследовательских работ.
Отдельные положения диссертации используются при подготовке бакалавров по направлению «Математика. Компыотерные науки». Планируется использовать их при обучении студентов специальности "Радиосвязь, радиовещание и телевидение". СОДЕРЖАНИЕ РАБОТЫ
Диссертация состоит из Введения, четырех глав, Заключения и Приложений.
Методы и алгоритмы классификации объектов
Классификация - это процесс разбиения исходного множества объектов, характеризующихся некоторым количеством критериев, на определенное заранее или отыскиваемое в ходе анализа число непустых попарно непересекающихся подмножеств объектов подобных друг другу в некотором априорно или объективно существующем отношении,
Процесс классификации включает в себя ряд подзадач, которые исследователю необходимо выполнить. Графически эти подзадачи и их взаимосвязь можно представить в виде SADT (Structured Analysis and Design Technique) диаграммы на рисунке 1.1.
class2 Разработка и применение информационной меры однородности характеристик объектов в вариационном алгоритме автоматической классификаций объектов class2 link2 Вариационные алгоритмы автоматической классификации объектов (критерии качества классификации объектов) link3
В рамках настоящей работы, говоря о методах решения задач классификации объектов, уделяется внимание точным методам решения задач кластеризации. Под точными методами следует понимать то, что исследователь, руководствуясь о качестве получаемого разбиения, формализует свои представления о качестве классификации в виде функционала. Данный функционал, посредством сконструированного алгоритма, должен достичь определенного экстремального значения, при котором будет найдено наилучшее разбиение исходного множества объектов с точки зрения исследователя. Следует заметить то, что экстремальное значение функционала в некоторых методах носит локальный характер, то есть глобального экстремума функционал не достигает в виду особенностей и ограничений самого метода классификации.
Точные постановки задач классификации были предложены в начале 50-х годов прошлого века. Об этом говорит, например, появление в 1951 году статьи Т. Далениуса «Проблема оптимальной стратификации». Данная статья обсуждалась в работе [136]. Она содержала формулировку критерия минимизации внутриклассовой дисперсии и алгоритм поиска оптимального решения типа к - средних. Так же в эти годы был предложен алгоритм «Ворцлавской таксономии», в котором говорили о разрезании минимального отставного дерева таким образом, чтобы сумма внутриклассовых ребер была минимальной. Данный функционал имел недостаток в том, что при достижении глобального минимума функционала в каждом классе всегда оставалось по два объекта. По-этому процесс разрезания конечного незамкнутого пути (КНП) останавливался, когда функционал достигал первого локального минимума либо пока не будет достигнуто требуемое количество классов.
В настоящий момент времени предложено большое количество способов задания критериев качества классификации, и алгоритмов их реализующих. Например, в работе [91] их насчитывается порядка 46 разновидностей. Следует заметить то, что большая часть алгоритмов в силу свойств своих функционалов требуют априорного задания количества классов. На практике довольно часто определить конечное число классов до запуска процедуры классификации бывает невозможно.
Таким образом, на сегодняшний день все функционалы качества классификации в той или иной мере отражают правильность конечного разбиения исходного множества объектов на подмножества с точки зрения исследователя, сконструировавшего данный функционал, опираясь на свои интуитивные предположения о качестве разбиения [93].
Прежде чем говорить о качестве классификации объектов следует определиться с целью ее проведения. Цель классификации объектов заключается в том, чтобы была выявлена возможность описать исходное множество объектов в более кратком виде.
Другими словами исследователь, имея конечный набор изучаемых объектов, надеется понять структурные закономерности всех объектов генеральной совокупности, определить распадается ли совокупность на локальные группы классов, выявить количество классов их размеры и формы. Придание структуры исходной ТО С позволяет описать большой массив данных более кратко. Для достижения выше поставленной цели можно аппроксимировать группы объектов каким-нибудь законом распределения, запомнив его характеристики. Далее по полученным характеристикам и свойствам индивидуального объекта можно будет определить, какому классу данный объект принадлежит. Либо можно выделить один или несколько типичных представителей каждого класса и по максимальному сходству объекта и эталона определить принадлежность любого объекта к одному из классов. Также можно указать границы классов путем описания их геометрических параметров (уравнения разделяющих гиперплоскостей, центры и радиусы гиперсфер) и по этим данным представляется возможным определить принадлежность любого объекта гиперпространства к одному из известных классов. Заменяя описания индивидуальных свойств объектов свойствами их групп следует сохранять возможность указать принадлежность к тому или иному классу как объекта изучаемого множества, так и нового объекта из генеральной совокупности.
Таким образом, задача классификации в общем случае состоит из двух частей: 1. Разделение исходного множества объектов на конечное число классов (кластеризация);
2, Краткого описания в виде правила отнесения объектов к своим классам (обучение для последующего распознавания).
Проводя классификацию «в ручную» исследователь решает эти задачи и руководствуется интуитивными, зачастую неосознанными критериями качества классификации [99].
В рамках настоящей работы представляется интересным способ формализации критериев качества классификации в алгоритме КРАБ [61].
Здесь выдвинуто одно из предположений то, что человек использует некоторую форму близости (R) точек признакового пространства и считает, что классификация тем лучше, чем меньше расстояния между точками одного и того же класса. Он тем уверение делает классификацию, чем дальше одни группы точек отстоят от других групп, так что мера взаимной удаленности (D) классов также играет важную роль. При прочих равных условиях исследователя больше устраивает равномерное распределение (Н) числа объектов по классам. Чем больше отличия между классами по их мощности (числу объектов или другими словами - репрезентативности), тем хуже классификация: каждый класс в дальнейших построениях будет служить кодом, обозначающим набор факторов, и с точки зрения теории оптимального кодирования нужно стремиться к такой кодировке, при которой все коды встречались бы одинаково часто. Для этого они должны быть «равномерно нагруженными».
Разработка и исследование меры информативности признаков при распознавании образов с использованием алгоритмов вычисления оценок (АВО)
В общем случае задачей распознавания образов является задача отнесения объекта исследования, характеризующегося вектором значений признаков, к одному из априорно заданных классов объектов, существующих в некотором признаковом пространстве.
В зависимости от полноты исходных данных для решения задачи распознавания образов она может быть поставлена как [24], [34], [35]:
1. задача распознавания образов без обучения;
2. задача распознавания образов с обучением;
3. задача распознавания образов с самообучением.
В задачах первого класса первоначальной информации достаточно для того, чтобы на основании выбранного принципа классификации разделить все множество объектов на попарно непересекающиеся подмножества (классы ) объектов и при дальнейшей обработке этих данных описать каждый класс на языке словаря признаков так, чтобы вновь пришедший для распознавания объект был однозначно отнесен к одному из заранее известных классов. Таким образом, в ходе решения данная задача не нуждается в привлечении дополнительной (недостающей) информации.
В задачах второго класса доля исходной информации меньше чем в задачах первого класса и ее не хватает для описания классов на языке признаков. Поэтому данный класс задач требует процедур обучения, которые выполняет «учитель». Таким образом, «учитель» в ходе выполнения своей работы восполняет недостаток полной априорной информации [115], [116].
В задачах третьего класса априорной информации достаточно только для определения словаря признаков. Таким образом, самообучение реализуется с применением методов кластерного анализа и только после этого выполняется описание полученных классов на языке словаря признаков.
Одним из этапов решения всех видов задач распознавания образов является формирование признакового пространства, то есть его качественного состава и размерности [23]. О необходимости формирования достаточно информативного словаря признаков излагается в работах [20], [26], [29 - 31], [38-42], [50- 51], [62], [64 - 66], [78], [86], [94 - 97], [107], [ПО], [120], [123 - 124], [132 - 133], [149 - 150]. Признаковое пространство должно подбираться таким образом, чтобы каждый признак обладал достаточной для решения задачи разделительной способностью при как можно меньшей размерности данного пространства. Уменьшение размерности признакового пространства при сохранении его различительной способности в целом необходимо для осуществления реализации алгоритмов распознавания образов на вычислительных машинах. В некоторых случаях размерность пространства признаков является критичной при машинной реализации процедур распознавания [10]. Например, при реализации всевозможных вариационных методов или при реализации алгоритмов основанных на разрезании графов[77].
При формировании признакового пространства исследователь может столкнуться с некоторыми ограничениями:
1. в словарь включают признаки, относительно которых может быть получена априорная информация, достаточная для описания классов на языке этих признаков;
2. некоторые малоинформативные признаки необходимо включать в основное признаковое пространство;
3. некоторые наиболее информативные признаки не могут быть определены (в виду отсутствия дорогостоящей аппаратуры).
Таким образом, в состав признакового пространства должны входить признаки, которые, с одной стороны, наиболее информативны и , с другой стороны, могут определяться имеющейся аппаратурой.
Обоснование выбора аппаратно - программной платформы для прототипа системы классификации объектов и распознавания образов
Программная поддержка вариационного алгоритма автоматической классификации объектов и алгоритма распознавания образов на основе информационной меры однородности реализована в виде пакета прикладных программ, включающих в себя:
1. программу генерирования исходных данных;
2. программу создания, сохранения, и открытия данных из системы управления базой данных (СУБД) MS Access;
3. программу классификации объектов;
4. программу распознавания образов на основе АВО;
5. программу, подсчитывающую ошибку распознавания на отклассифицированном множестве объектов.
В качестве аппаратной платформы была выбрана ЭВМ класса IBM РС} так как по оценкам независимых экспертов ЭВМ данного типа составляют 85 - 90 % парка персональных компьютеров в мире. ЭВМ данного типа доступны по стоимости большому количеству пользователей и могут быть использованы как персональные домашние компьютеры, так и в качестве рабочих станций локальных вычислительных сетей (ЛВС).
Персональные компьютеры строятся с использованием ряда архитектур:
1, CISC (Complex Instruction Set Command ) с полным набором системы команд;
2. RISC (Reduced Instruction Set Command) с усеченным набором системы команд. Данный факт также говорит о их огромной популярности, так как данные архитектуры до недавнего времени разрабатывались разными фирмами-изготовителями и конкурировали между собой на мировом рынке.
В качестве операционной системы была выбрана система на базе ядра Windows NT. Таким образом, программная поддерлска информационной технологии может функционировать в среде MS Windows 2000 Prof или MS Windows XP. Выбор операционной системы данного типа обусловлен следующими факторами:
1. Операционная система MS Windows 2000 Prof используется для управления рабочими станциями ЛВС, a MS Windows XP для управления домашними ПЭВМ подавляющим большинством пользователей Российской Федерации и стран СНГ. Операционные системы данного класса доминируют на указанном географическом пространстве, так как все остальные операционные системы занимают менее 15% рынка.
2. Графически ориентированная оболочка данного класса систем обладает дружественным и русифицированным интерфейсом, что позволяет создать такой же интерфейс для программной поддержки информационной технологии.
3. Операционная система Windows широко используется в глобальной сети Интернет, что позволит получить доступ к программной поддержке информационной технологии большому количеству российских пользователей.
4. Под операционной системой MS Windows работает СУБД Microsoft Access, используемая для хранения данных созданной программной поддержки информационной технологии.
5. Операционная система MS Windows 2000 сертифицирована по стандарту Common Criteria , согласно которого гарантируется уровень защиты данных не ниже С2. Подсистема защиты контролирует доступ и учетную информацию и имеет встроенные средства по поддержки резервных копий данных. Таким образом, среди современных операционных систем вопросы безопасности лучше всего продуманы в выбранной операционной системе.
