Содержание к диссертации
Введение
1. Анализ методов классификации 12
1.1. Анализ методов распознавания образов 12
1.2. Методы дискретной классификации 27
1.3. Критерии оценки качества алгоритмов распознавания 38
Основные результаты и выводы 40
2. Решение задачи дискретной классификации с использованием комбинаторно упорядоченных моделей 42
2.1. Обоснование использования методов КУМ 42
2.2. Интерпретация методов КУМ для решения задачи классификации 45
2.3. Модификация алгоритма КУМ 50
2.4 Обучение и классификация 54
Основные результаты и выводы 65
3. Реализация алгоритма дискретной классификации с использованием метода КУМ 67
3.1. Схема работы алгоритма дискретной классификации на основе метода КУМ 67
3.2. Поиск элементарных классификаторов 69
3.3. Минимизация времени выполнения операции комбинаторного попарного пересечения 72
3.4. Минимизация времени выполнения проверки уникальности существенного элемента 76
3.5. Параллельная обработка 81
3.6. Пути реализации параллельной обработки 84
Основные результаты и выводы 93
4. Анализ возможностей алгоритма дискретной классификации на основе метода КУМ 95
4.1. Выбор метода исследования алгоритма дискретной классификации 95
4.2. Выбор исходных данных для исследования 100
4.3. Оценка эффективности алгоритма дискретной классификации 107
Основные результаты и выводы 119
Основные результаты работы 121
Список использованных источников 123
- Критерии оценки качества алгоритмов распознавания
- Интерпретация методов КУМ для решения задачи классификации
- Минимизация времени выполнения операции комбинаторного попарного пересечения
- Оценка эффективности алгоритма дискретной классификации
Введение к работе
Актуальность работы. Быстрое развитие вычислительной техники в последние десятилетия привело к ее широкому внедрению почти во все сферы жизнедеятельности человека. Вследствие этого значительно выросли объемы информационных ресурсов в различных отраслях науки и техники, причем все более остро встают проблемы быстрого поиска, анализа и обработки накопленных объемов информации как задач классификации и распознавания образов.
В работе показано, что статистические методы, являющиеся одной из первых идей для классификации и распознавания образов, наиболее эффективны при решении задач, где объекты классификации характеризуются ограниченной степенью изменчивости. Большинство статистических методов хорошо изучены и с трудом поддаются дальнейшему совершенствованию. Однако исходные данные во многих современных задачах не дают возможности оценить вероятностные характеристики с необходимым уровнем, который позволил бы статистическому алгоритму достаточно точно классифицировать объекты. Вследствие этого подобными методами сложно проводить быстрый и эффективный анализ, так как в реальных современных задачах анализа и обработки информации каждый объект анал и-за имеет, как правило, сложное описание и может быть представлен десятками, а иногда сотнями и тысячами различных данных. Возникает проблема поиска и разработки более эффективных инструментов анализа больших объемов накопленной информации.
Для увеличения скорости и повышения качества анализа и классификации информационных ресурсов в настоящее время применяют дискретные методы, основанные на использовании результатов и идей дискретного анализа. Аппарат и методы дискретной математики обладают рядом преимуществ и позволяют, например, получить результат при отсутствии сведений о функциях распределения и при наличии малых обучающих выборок. К дискретным методам классификации относятся, например, алгебраический подход, методы комбинаторного анализа структуры пространств описаний и др. Вопросы создания и разработки дискретных методов анализа информации нашли свое отражение в работах российских ученых: Ю. И. Журавлева, К. В. Рудакова, К. В. Воронцова, Е. В. Дюковой, Н. Г. Федотова, В. Б. Лебедева и др. Известны также работы зарубежных уче-
ных, связанные с применением дискретных методов распознавания: Герберта Симона (Herbert Simon), Т. М. Митчелла (Т. М. Mitchell), Р. Куинлена (R. Quinlan) и др.
В работе рассмотрены недостатки и нерешенные вопросы для дискретных методов классификации, в частности, задача эффективного выделения отдельных описаний признаков для всего множества классифицируемых объектов. Имеющиеся методы не позволяют в полной мере учесть взаимосвязи отдельных описаний признаков конкретного объекта. Кроме того, становится весьма затруднительным их использование в задачах большой размерности, с большим числом разнородных признаков.
Предлагаемый в работе алгоритм дискретной классификации является модификацией алгоритма, использующего методы комбинаторно-упорядоченного моделирования (КУМ), основанный на построении и анализе решеток кортежей признаковых данных. Подобная модификация позволяет более точно структурировать классифицируемую информацию ещё на этапе обучения алгоритма классификации и тем самым сохранить взаимосвязи отдельных признаков. Классификация ведется по отдельным элементарным классификаторам, которые с высокой точностью классифицируют объект на всем исследуемом множестве признаков. Предлагаемая модификация позволяет также значительно увеличить производительность алгоритма классификации.
Результаты исследования позволили разработать алгоритм дискретной классификации на основе модификации алгоритма, использующего методы КУМ и его программную реализацию. Рассмотрены попросы выполнения параллельных вычислений для реализации разработанного алгоритма.
Необходимо отметить, что разработанный алгоритм может применяться для решения задач классификации и структурирования набора дискретных данных различного типа.
Объект исследования - методы и средства классификации данных в задаче распознавания образов.
Предмет исследования - методы и средства классификации данных на основе методов комбинаторно-упорядоченного моделирования, использующих представления в виде решеток кортежей данных.
Целью диссертационной работы являются разработка и обоснование алгоритма дискретной классификации объектов распознавания на основе методов комбинаторно-упорядоченного моделирования путем построения и анализа решеток кортежей признаковых данных.
Для достижения поставленной цели решены следующие задачи:
выполнено представление классифицируемой информации в виде решетки кортежей данных с использованием методов комбинаторно-упорядоченного моделирования;
создан алгоритм дискретной классификации на основе методов комбинаторно-упорядоченного моделирования, использующий решетку кортежей данных и позволяющий более адекватно структурировать обучающую информацию с сохранением взаимосвязей признаков;
разработаны программные средства дискретной классификации и визуализации результатов на основе выбранной модели решетки кортежей данных;
проведено сокращение времени поиска элементарных классификаторов при выполнении процедуры обучения в разработанном алгоритме;
экспериментально исследована эффективность классификации образов с помощью разработанного алгоритма;
выполнено повышение эффективности вычислений путем их распараллеливания в разработанном алгоритме дискретной классификации.
Методы исследования. При решении поставленных задач использовались методы теории классификации образов, дискретной математики, математический аппарат теории решеток, методы распределенных вычислений.
Научная новизна работы заключается в следующем:
Предложена математическая модель дискретной классификации образов на основе метода комбинаторно-упорядоченного моделирования, использующая решетки кортежей данных и позволяющія более адекватно структурировать обучающую информацию с сохранением взаимосвязей признаков, что повышает эффективность распознавания.
Разработан алгоритм дискретной классификации, основанный на построении и анализе решетки кортежей данных и позволяющий повысить эффективность классификации образов.
Предложен способ организации вычислений для выполнения операции комбинаторного попарного пересечения множества кортежей в разработанном алгоритме дискретной классификации, что позволяет сократить общее время поиска элементарных классификаторов при обучении.
Разработан и обоснован параллельный способ реализации алгоритма дискретной классификации на основе решетки кортежей данных, что позволяет повысить эффективность вычислений в алгоритме при сохранении точности классификации.
Практическая значимость работы состоит в создании новых, более эффективных алгоритмов дискретной классификации, позволяющих увеличить точность классификации и производительность вычислений. В работе получены следующие практические результаты:
Разработан алгоритм дискретной классификации с применением решетки множества кортежей данных, основанный на модификации алгоритма, использующего методы комбинаторно-упорядоченного моделирования.
Разработана и исследована программная реализация предложенного алгоритма дискретной классификации, основанная на методе комбинаторно-упорядоченного моделирования с использованием кортежей одноэлементных множеств, которая позволяет автоматизировать процесс обучения (поиска элементарных классификаторов), а также автоматизировать процесс построения структуры обучающей информации в виде решетки.
На защиту выносятся:
Алгоритм дискретной классификации образов, использующий методы комбинаторно-упорядоченного моделирования на основе решетки кортежей данных.
Представление классифицируемых данных в виде кортежей одноэлементных признаков, что повышает эффективность процедуры обучения в алгоритме дискретной классификации на основе методов комбинаторно-упорядоченного моделирования.
Организация вычислений в разработанном алгоритме дискретной классификации на основе методов комбинаторно-упорядоченного моделирования, что позволяет сократить время выполнения процедуры обучения.
Экспериментальное исследование эффективности классификации с помощью разработанного алгоритма дискретной классификации, использующего решетки кортежей данных.
Способ параллельной обработки обучающей информации, увеличивающий производительность выполнения процедуры обучения в разработанном алгоритме дискретной классификации на основе методов комбинаторно-упорядоченного моделирования.
Реализация и внедрение результатов. Основные результаты диссертационной работы использованы при выполнении проекта № 06-07-89167 «Система интеллектуализации анализа и поиска биометрической информации в базе данных с помощью методов стохастической геометрии» по гранту Российского фонда фундаментальных исследований (РФФИ) в Пензенском государственном университете и внедрены в разработках ЗАО «Пензенская телефонная компания» (г. Пенза).
Достоверность результатов работы обоснована строгой аргументацией базовых положений, корректным использованием математического аппарата, проведением и сопоставительным анализом теоретических и экспериментальных исследований.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: VII, VIII Международных научно-технических конференциях «Новые информационные технологии и системы» (г. Пенза, 2006, 2008 гг.); VII, VIII, ГХ Международных научно-технических конференциях «Современные технологии документооборота в бизнесе, производстве и управлении» (г. Пенза, 2007-2009 гг.); XI, XII, XIII Международных научно-методических конференциях «Университетское образование» (г. Пенза, 2007-2009 гг.); IV, V Всероссийских научно-технических конференциях «Современные методы и средства обработки пространственно-временных сигналов» (г. Пенза, 2006, 2007 гг.); I Международной научно-методической конференции молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (г. Пенза, 2007 г.); VII Всероссийской научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (г. Пенза, 2007 г.); Международной научно-практической конференции «Перспективы развития систем среднего и выс-
шего профессионального образования в современном обществе» (г. Пенза, 2008 г.); XVIII, XIX, XX Всероссийских научно-технических конференциях профессорско-преподавательского состава и студентов (г. Пенза, 2007-2009 гг.).
Публикации. По теме диссертации самостоятельно и в соавторстве опубликованы 18 печатных работ, в том числе 14 статей (одна работа опубликована в издании, рекомендованном ВАК).
Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения, приложений и списка литературы, включающего 134 наименования. Работа содержит 122 страницы основного текста, 29 рисунков и 11 таблиц.
Критерии оценки качества алгоритмов распознавания
В частности методы, основанные на оценках плотностей распределения значений признаков берут свое начало в теории статистических решений, где объект исследования есть многомерная случайная величина, распределенная по какому либо закону. Подобные методы базируются на байесовской схеме принятия решения, которая апеллирует к вероятностям принадлежности объектов к классам, а также плотности распределения признаков. Это подход является наиболее разработанным параметрическим методом в современной статистике. К данной группе можно отнести методы вычисления отношения правдоподобия для независимых признаков. Так как методы данной группы не предполагают знания закона распределения, их можно отнести к непараметрическим методам распознавания образов. Другие виды непараметрических методов могут применяться, когда вид кривой плотности распределения неизвестен, невозможно сделать предположение о характере кривой. К ним относятся известные метод многомерных гистограмм, метод к-ближайших соседей, метод евклидова расстояния, метод потенциальных функций [7] и др., обобщением которых является метод, получивший название «оценки Парзена» [5] или метод парзеновского окна [7,35]. Эти методы формально оперируют объектами как целостными структурами. Недостатком подобных методов является необходимость запоминания всей обучающей выборки для вычисления оценок локальных плотностей распределения вероятностей и высокая чувствительность к непредставительности обучающей выборки.
Методы, основанные на предположении о классе решающих функций. Здесь считается известным общий вид решающей функции и задан функционал ее качества. Далее отыскивается наилучшее приближение решающей функции. Самыми распространенными являются представления решающих функций в виде линейных и обобщенных нелинейных полиномов. Группа содержит большое число методов, что объясняется широким спектром используемых функционалов качества решающего правила и алгоритмов поиска экстремума. Обобщением является метод стохастической аппроксимации [36,37]. В отличие от параметрических методов распознавания успешность применения данной группы методов не так сильно зависит от рассогласования теоретических представлений о законах распределения объектов в пространстве признаков с эмпирической реальностью. Главная цель — нахождению экстремума функционала качества решающего правила. Однако, параметрические методы для случая нормальных распределений объектов в различных классах с равными ковариационными матрицами приводят к линейным решающим функциям. Алгоритмы отбора информативных признаков в линейных диагностических моделях, можно интерпретировать как частные варианты градиентных алгоритмов поиска экстремума. Сходимость этих алгоритмов доказана только для случая, когда распознаваемые классы объектов отображаются в пространстве признаков компактными геометрическими структурами. Однако стремление добиться достаточного качества решающе/го правила очень часто удовлетворяется с помощью алгоритмов, не имеющих строгого математического доказательства сходимости решения к глобальному экстремуму [5]. К таким алгоритмам относится большая группа процедур эвристического программирования, представляющих направление эволюционного моделирования [38,39]. Известный представитель эволюционного моделирования — метод группового учета аргументов [5]. Здесь синтезируются и отбираются члены обобщенного полинома. Синтез и отбор производится с нарастающим усложнением, и заранее нельзя предугадать, какой окончательный вид будет иметь обобщенный полином. Сначала обычно рассматривают простые попарные комбинации исходных признаков, из которых составляются уравнения решающих функций, как правило, не выше второго порядка. Каждое уравнение анализируется как самостоятельная решающая функция, и по обучающей выборке тем или иным способом находятся значения параметров составленных уравнений. Затем из полученного набора решающих функций отбирается часть в некотором смысле лучших. Проверка качества отдельных решающих функций осуществляется на контрольной выборке. Далее отобранные частные решающие функции рассматриваются как промежуточные переменные, используемые для аналогичного синтеза новых решающих функций и т. д. Процесс такого иерархического синтеза продолжается до тех пор, пока не будет достигнут экстремум критерия качества решающей функции, что на практике приведет к ухудшению этого качества при попытках дальнейшего увеличения порядка членов полинома относительно исходных признаков. С помощью подобных методов (эволюционных или градиентных), можно строить системы высокой сложности и получать приемлемые результаты. Однако это не сопутствует извлечению новых знаний о природе распознаваемых объектов. Возможность извлечения этих знаний, в частности знаний о механизмах взаимодействия признаков ограничена заданной структурой такого взаимодействия, зафиксированной в выбранной форме решающих функций. Поэтому после построения той или иной диагностической модели можно лишь перечислить комбинации признаков и сами признаки, вошедшие в результирующую модель. Но смысл комбинаций, отражающих природу и структуру распределений образов, в рамках данного подхода часто остается нераскрытым.
Логические методы [10] распознавания образов базируются на аппарате алгебры логики и позволяют оперировать информацией, заключенной не только в отдельных признаках, но и в сочетаниях значений признаков. В этих методах значения какого-либо признака рассматриваются как элементарные события [5]. В общем виде логические методы можно охарактеризовать как разновидность поиска по обучающей выборке логических закономерностей и формирование системы логических решающих правил, каждое из которых имеет собственную значимость. Группа логических методов разнообразна и включает методы различной сложности и глубины анализа. Для булевых признаков популярными являются так называемые древообразные классификаторы [6,10], метод тупиковых тестов [40], алгоритм «Кора» [41] и др. Так алгоритм «Кора», как и другие логические методы распознавания образов, является достаточно трудоемким, так как при отборе конъюнкций необходим полный перебор. Поэтому при применении логических методов предъявляются высокие требования к эффективной организации вычислительного процесса, и эти методы хорошо работают при сравнительно небольших размерностях пространства признаков и только на мощных компьютерах.
Лингвистические методы [10,42] распознавания образов основаны на использовании специальных грамматик порождающих языки, с помощью которых может описываться совокупность свойств распознаваемых объектов. Здесь для классов объектов выделяются атомарные элементы (признаки) и возможные отношения между ними, а грамматикой называют правила построения объектов из этих непроизводных элементов. Каждый объект представляется набором непроизводных элементов связанных между собой грамматиками некоторого «языка». Путем синтаксического анализа (грамматического разбора) устанавливается его синтаксическая «правильность» т.е. может ли некоторая фиксированная грамматика (описывающая класс) породить имеющееся описание объекта. Грамматический разбор производится так называемым «синтаксическим анализатором», который представляет полное синтаксическое описание объекта в виде дерева грамматического разбора, если объект является синтаксически правильным (принадлежит классу, описываемому данной грамматикой). В противном случае, объект либо отклоняется, либо подвергается анализу с помощью других грамматик, описывающих другие классы объектов. Задача восстановления (определения) грамматик по некоторому множеству высказываний, порождающих данный язык, является трудно формализуемой. Существует описание множества эвристических правил автоматического восстановления грамматик.
Интерпретация методов КУМ для решения задачи классификации
Делается попытка создать универсальный алгоритм, в рамках которого укладывались бы все существующие алгоритмы. Такое построение ведется путем синтеза базиса в алгебраическом замыкании модели алгоритмов и поиска алгоритма в виде разложения по базису. Такой подход позволяет отказаться от использования трудоемких оптимизационных процедур и обеспечивает корректность алгоритма «по построению». В частности Ю.И. Журавлев в [16,65] отмечает, что задача распознавания является в частном случае дискретным аналогом проблемы поиска оптимальных решений. Смысл данного подхода состоит в том, что семейство алгоритмов рассматривается как некоторая алгебра, операции которой позволяют на основе базиса семейства алгоритмов строить такое расширение этого семейства, которое содержит корректный оптимальный алгоритм, правильно классифицирующий выборку. Принципы, действующие над подмножествами алгоритмов, сначала формулируются в плохо формализованном виде, и только потом в виде точных математических описаний. Однако здесь имеет место эвристический характер выбора принципа, а алгоритмы, порождаемые на его основе могут строиться стандартным образом. Все это приводит к появлению моделей распознающих алгоритмов. Но сам по себе переход к моделям распознающих алгоритмов не привел ни к созданию некоторой универсальной модели, ни к формализации процесса выбора модели для решения конкретной задачи распознавания. При построении стандартных распознающих алгоритмов требуется дополнительно решить задачу выбора экстремального алгоритма, которая состоит в нахождении набора параметров распознающего оператора - решающего правила, которое определяет алгоритм [16]. Как указывает автор, для этих целей необходимо воспользоваться методами локального спуска, случайного поиска, направленного перебора или их комбинацией. Это значительно усложнит процедуру распознавания. Также возможна замена функционала качества на более простой. Этот факт может негативно сказаться на качестве результата. Построение таких алгоритмов обычно приводит к исследованию и реализации вычислительных систем для нестандартных экспериментальных задач. Попытки расширить область применения оптимального алгоритма приводят к необходимости использования значительного объема априорной информации, которую можно получить, если имеется достаточно точная модель объекта, что бывает крайне редко в реальных задачах.
Данные методы получили дальнейшее развитие в работах К.В. Рудакова и К.В. Воронцова [18-21,67-69,70-72]. Так в [18] К.В. Воронцов предложил оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания Ю.И. Журавлева. В данном методе на каждом шаге в композицию добавляется один алгоритм, который настраивается по обучающей выборке совместно с корректирующей операцией. Настройка алгоритма преследует две цели одновременно: аппроксимировать обучающую выборку и компенсировать совокупный дефект предыдущих алгоритмов. Также К.В. Воронцов вводит специальный параметр, позволяющий на каждом шаге перераспределять приоритет между этими двумя целями. Рассматриваются модификации метода, предназначенные для решения задач классификации и восстановления регрессии с использованием линейных и монотонных корректирующих операций. Однако предложенная стратегия настройки имеет ряд существенных недостатков. Так многократно решая одну и туже задачу получения корректировок, есть большая вероятность того, что будут получены одинаковые корректирующие операторы. Такая ситуация может возникнуть даже при некотором изменении метода настройки. В таком случае никакая корректирующая операция не позволит построить алгоритм, качественно отличающийся от уже имеющихся.
В [19] К.В. Рудаков предлагает алгоритм для формализации проблемы синтеза обучаемых алгоритмов выделения трендов, при использовании алгебраического подхода. Введенный им комплекс понятий и полученные результаты позволяют решать задачу поиска минимальной системы окрестностей по заданному набору прецедентов. В [20,21,67-69] задача классификации рассматривается, как задача синтеза алгоритма преобразования информации, а также рассматриваются некоторые универсальные симметрические и функциональные ограничения для алгоритмов классификации. В частности в [67] автор пишет, что задачи распознавания могут ставиться как задачи синтеза алгоритмов, реализующих отображения из одного заданного пространства (пространства возможных начальных информаций) в другое (пространство возможных финальных информаций), причем реализуемые отображения должны удовлетворять некоторым ограничениям (каждая система таких ограничений определяет соответствующую задачу). А в [68] говорится, что симметрические универсальные ограничения возникают в конкретных задачах, как выражение информации о различного рода однородностях объектов и классов. Однако в [69] автор отмечает, что под корректирующей операцией может пониматься произвольная операция над множеством. Такое общее определение оставляет открытым принципиальный вопрос о способах реализации корректирующих операций, а при решении конкретных задач распознавания эти операции должны быть обязательно определены в явном виде. В результате автор использует стандартные способы определения корректирующих операций, однако их использование во многих случаях не дает удовлетворительных результатов. Универсальные ограничения и эвристические модели алгоритмов формализуются для конкретных задач на основе одних и тех же общих представлений о взаимосвязи начальной информации и результата. Требования полноты для моделей алгоритмических операторов является самым слабым из возможных. Может оказаться, что некоторая модель не имеет полноту в своей категории. В этом случае может найтись реальная задача, что для ее полноты нельзя будет добиться при использовании любых множеств корректирующих операций и решающих правил, что свидетельствует о неадекватном представлении исходной информации.
Еще один подход при решении задач распознавания с использованием дискретных процедур рассматривает Е.В. Дюкова в [22-25,73-80]. В частности в [22] изложены общие принципы, лежащие в основе дискретного подхода к задачам распознавания. В данном подходе центральная проблема — поиск информативных фрагментов признаковых описаний объектов (элементарных классификаторов). Для этих целей используется аппарат логических функций, а также теория аппарата дискретной математики, в частности булевой алгебры, теории дизъюнктивных нормальных форм, теории покрытий булевых и целочисленных матриц. Однако применение дискретного подхода оказывается во многих случаях сложным в силу чисто вычислительных трудностей переборного характера, возникающих на этапе поиска информативных фрагментов описаний объектов. Как замечают авторы в [65] одна из наиболее универсальных форм представления данных в задачах распознавания — это наличие длинных последовательностей, т.е. когда вектор признаков объекта распознавания описывается бинарной последовательностью. Специфика таких последовательностей в том, что большой объем информации делает работу с ними, как с целыми практически невозможной. Возникает задача по сокращению вектора или поиска более компактных описаний, достаточных -для распознавания.
Минимизация времени выполнения операции комбинаторного попарного пересечения
Как известно, в реальных задачах объекты распознавания могут описываться десятками, а иногда и сотнями тысяч величин. Из этого вытекают две проблемы. Первая заключается в том, что для хранения всей этой обучающей информации требуется большой объем памяти вычислительной системы, при этом память должна иметь очень хорошее быстродействие, чтобы обучающая функция могла иметь к ним быстрый доступ. Вторая проблема связана с постоянной необходимость совершенствовать и увеличивать производительность самой функции обучения. В связи с возможным большим количеством характеристик объектов в реальных задачах появляется необходимость в разработке таких алгоритмов обучения, которые позволили бы значительно сократить размерность данных и при этом максимально точно описывать объекты кластеризации.
В соответствии с [1] цель работы системы распознавания образов заключается в том, чтобы на основе собранной информации определить на множестве распознаваемых объектов класс объектов с характеристиками, аналогичными измеренным. Качество классификации зависит от объема различающей информации, содержащейся в измеренных характеристиках и эффективности использования этой информации. Поэтому ограничения по времени, пространству и затратам, возникающие на практике, требуют развития рациональных подходов при распознавании.
Принцип перечисления членов класса, когда класс задается перечислением образов, из которых он состоит, а распознавание выполняется посред- ствам сравнения с эталоном. Множество образов принадлежащих одному классу запоминается системой распознавания, а при предъявлении новых выполняется последовательное сравнение. Такая система будет работать удовлетворительно, если выборка образов в памяти близка к идеальной.
Принцип кластеризации, когда образы некоторого класса представляют собой векторы действительных чисел, этот класс можно рассматривать как кластер и выделять только его свойства в пространстве образов кластера. Построение системы определяется удаленностью кластеров. Если последние пересекаются, то приходится пользоваться достаточно сложными методами разбиения пространства образов.
Принцип общности свойств основан на задании класса с помощью свойств, общих для всех входящих в его состав членов, т.е. образы, принадлежащие одному классу, обладают рядом общих свойств или признаков. При предъявлении системе неклассифицированного образа из него выделяется набор признаков, а затем сравнивается с имеющимися. Эта концепция во многом превосходит распознавание по принципу перечисления классов, поскольку признаки, характеризующие класс в целом обладают инвариантностью, допускается вариация характеристик отдельных образов, и хранение признаков требует гораздо меньше памяти, чем хранение образов. Однако исключительно трудно найти для некоторого класса полный набор различающих признаков.
Этот последний принцип является определяющим при выборе метода классификации образов для построения системы распознавания. Наиболее полно данному принципу удовлетворяют методы комбинаторно- упорядоченного моделирования (КУМ) [26-30,86-88]. Эти методы основаны на теории упорядоченных множеств, изучающей более сложные объекты, чем графы. В частности, в основе методов КУМ лежит понятие решетки (дискретной структуры), которая является разновидностью частично упоря- доменного множества. Для наглядного представления упорядоченных множеств применяют диаграммы Хассе. Упорядоченное множество, в котором каждое двухэлементное подмножество имеет точную верхнюю и точную нижнюю грани называется решеткой Ьу. Наибольший элемент решетки называется структурной единицей, а наименьший — структурным нулем. Диаграммы Хассе решеток являются транзитивными орграфами, не содержащими петель и транзитивно замыкающих дуг [86,89]. На рис.2.1 представлен пример диаграммы Хассе. Дуги на диаграммах Хассе показывают, с целью упрощения рисунка, без указания их ориентации. Точки диаграмм изображают на условных уровнях так, что соответствующее направление дуг всегда следует с нижнего уровня на верхний и обеспечивает наглядность упорядочения. Данная группа методов является универсальной, обладает хорошей наглядностью и структурированностью, алгебраическими и геометрическими свойствами, а также легко представима в ЭВМ [90]. Подобные методы КУМ позволяют исследовать такие структурные свойства, которые недоступны для исследования методами теории графов [26]. Алгоритм [26] может быть использован для построения дискретных систем классификации и распознавания на основе обучения с учителем [9193]. При этом качество классификации в общем случае зависит от объема обучающей выборки. Алгоритм позволяет выделить элементарные описания (классификаторы) для каждого обучающего элемента, а также структурировать взаимосвязи как между самими обучающими элементами, так и между их элементарными описаниями. Определение 2.1. Элементарным классификатором назовем элемент решетки, отличный от структурного нуля и единицы, и покрываемый обучающими элементами, принадлежащими одному классу. Минимальным элементарным классификатором назовем минимальный по мощности элементарный классификатор. В решетке минимальный элементарный классификатор расположен на более нижнем условном уровне относительно других элементарных классификаторов для одного класса. Все обучающие элементы решетки Ь покрыты структурной единицей. Согласно [26] покрытием (нижним) п{1) элемента решетки /еД,, называется такое подмножество ее элементов, которое удовлетворяет условию я(1) := [а е Ь\ а -1}. Часто используют отношение покрытия а -Ъ означающее, что а- Ъ и при этом Ъ плотно покрывает а (или а плотно покрыто Ъ), где - знак отношения плотного покрытия. Иными словами, покрытие тг{1) элемента решетки / е представляет собой подмножество ее элементов, которые плотно покрыты данным элементом /. Существует также отношение неполного покрытия а- Ь где Ь покрывает а не плотно, т.е. между элементами а и Ь могут быть другие элементы решетки. Например, если существуют а Ъ и Ь с, то а с. Подобное определение покрытия а- Ъ приводится в [64] Д.Ф. Люге- ром. Согласно его определению выражение а является более общим, чем Ь, и при этом Ь является логическим следствием а. Это позволяет существенно сузить направление поиска выполняемого алгоритма обучения.
Оценка эффективности алгоритма дискретной классификации
При проверке на практике оказалось, что способ разделения элементарных классификаторов на условные уровни имеет преимущества над хешированием, в котором значительная часть времени уходит на хеширование кортежей одноэлементных множеств. В случае использования условных уровней сравнение выполняется по двум критериями: совпадению индексов непустых одноэлементных множеств и совпадению значений этих множеств. Такой способ сравнения еще на начальном этапе позволяет обнаружить различия пары кортежей одноэлементных множеств, то есть при проверке первых непустых одноэлементных множеств. При большом числе признаков в распознаваемых объектах (большом числе одноэлементных множеств) подход будет наиболее эффективен.
Разработанный алгоритм дискретной классификации на основе методов КУМ с использованием кортежей одноэлементных множеств позволяет решать задачи классификации большой размерности. При этом на длительность обучения будет влиять в основном число кортежей одноэлементных множеств (7 (при увеличении С время обучения также увеличивается). Число одноэлементных множеств М (число признаков объекта) слабо влияет на время обучения и может достигать нескольких тысяч. Также на время обучения может повлиять число возможных значений каждого из одноэлементных множеств Ыт (чем больше значений, тем меньше частота появления этих значений в обучающей выборке, а значит и меньше время обучения). Так например, время обучения алгоритма с параметрами (7 — 20, М = 65000, Кт- числа с плавающей запятой двойной точности при числе классов Ж—З составило около 4 минут. А время обучения с параметрами С = 2987, М = 20, Ит е[2,10] и Ж =2 составило около 19 минут. Длительность классификации одного объекта определяется числом M и числом найденных элементарных классификаторов / для всех классов и составляет много меньше времени обучения. Так например, при М — 20 и /=1893 время классификации одного объекта составило около 11 секунд.
Все ранее рассмотренные варианты ускорения процесса поиска элементарных классификаторов реализованы для последовательной обработки, то есть когда обработкой управляет только один процесс. Однако наибольший интерес могут представлять способы реализации параллельной обработки и поиска элементарных классификаторов [100,101], так как эта задача имеет наибольшую трудоемкость в работе алгоритма. Для выбора способа распараллеливания воспользуемся классификацией предложенной в 1966 году М.Флинном [102,103]. В основе этой классификации лежат следующие архитектуры: - SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных; - SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных; - MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных; - MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Прежде чем выбрать одну из архитектур, необходимо определить, требования к обрабатываем данным и функционированию алгоритма поиска элементарных классификаторов. Первой проблемой при распараллеливании алгоритма является разделение исходных и промежуточных данных по процессам. В соответствии с последовательностью работы алгоритма обработки векторов рассмотренного ранее, каждый процесс должен иметь доступ ко всем кортежам одноэлементных множеств. Вторая проблема — сохранение образующих элементов на каждом шаге, так как каждый образующий элемент в итоговом списке должен быть уникальным. Здесь требуется синхронизация и обмен данными между процессами.
Из сказанного следует, что наиболее подходящей архитектурой является MISD. При таком подходе каждый процесс будет иметь доступ ко всем исходным данным. К данному классу можно отнести системы с конвейерной обработкой. Подобные системы все более начинают распространяться. Достаточно хорошей альтернативой может оказаться архитектура SIMD. Так в [104] автор пишет, что парадигма параллельного программирования — это реализация того или иного типа параллелизма, характерного для некоторого класса алгоритмов. Тип параллелизма отражает структуру приложения и/или структуру данных. В первом случае имеет место функциональный параллелизм, или параллелизм по управлению, во втором — параллелизм по данным. Функциональный параллелизм означает одновременное выполнение различных задач, которые могут взаимодействовать друг с другом. В случае параллелизма по данным возможно совместное протекание процессов, соответствующих выполнению одного и того же программного кода, но с различными данными. Наиболее часто используемая парадигма - «одна программа — множественные данные» (single-program multiple-data, или SPMD). В рамках SPMD каждый процесс соответствует выполнению одного и того же кода с различными данными, т.е. данные распределяются по доступным процессорам и воплощается параллелизм по данным (рис.3.6).
Каждый из процессоров системы взаимодействует с процессорами- соседями, причем нагрузка на коммуникационную среду пропорциональна размеру промежуточных результатов вычислений. Вычислительная нагрузка на процессор зависит от размера отрабатываемого блока данных. Между различными процессорами периодически осуществляется синхронизация, причем взаимодействия процессов обычно хорошо структурированы и заранее предсказуемы. Парадигма SPMD может быть очень эффективной, если данные легко распределяются между процессами и вычислительная система является однородной, т.е. процессорные узлы идентичны.
В нашем случае процессы должны иметь доступ ко всем исходным данным, по этому деление данных между процессами не требуется. Однако процесс должен знать, какие именно данные он должен обрабатывать. Это необходимо чтобы процессы не дублировали действия друг друга при выполнении однотипных операций. Следовательно, подобная парадигма наиболее хорошо подходит при решении задачи распараллеливания.
Далее необходимо подобрать модель вычислений, которая согласно [104] служит связующим звеном между архитектурой и моделью программирования и в распределенных системах должна отражать взаимодействие процессов. Для организации такого взаимодействия используют стандартные коммуникационные библиотеки MPI (Message Passing Interface) [105] или PVM (Parallel Virtual Machine). Здесь же автор пишет, что параллелизм по данным для SPMD, не предусматривает явной передачи сообщений или синхронизации. Программист распределяет данные последовательной программы по процессорам, выполняющим параллельную программу, причем каждый процессор работает с собственными данными. Известная реализация этой идеи — проект HPF (High Performance Fortran). Идея параллельного объектно-ориентированного программирования призвана обеспечить разработку хорошо структурированных приложений за счет применения подходящих абстракций и методов. Как и в традиционной объектной модели, объекты представляют собой абстрактные типы (пассивные контейнеры) данных, состояние которых определяется интерфейсом. Если эту модель обогатить набором разделяемых объектов, то она будет хорошо соответствовать концепции программирования над общей памятью. Известны реализации параллельных объектно-ориентированных сред на основе языка С++ [106].
Похожие диссертации на Классификация образов на основе решетки множества кортежей данных
