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

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

МИНАЕВ Валерий Евгеньевич

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

Специальности: 05.13.17 - «Теоретические основы информатики»; 05.13.11 - «Математическое и программное обеспечение

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

ПЕНЗА 2009

003484367

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет».

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

Лебедев Виктор Борисович.

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

Макарычев Пётр Петрович; кандидат технических наук, доцент Дрождин Владимир Викторович.

Ведущее предприятие - ООО НПФ «КРУГ» (г. Пенза).

Защита диссертации состоится 15 декабря 2009 г., в 14 часов, на заседании диссертационного совета Д 212.186.01 в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет», с авторефератом -~на сайте http://www.pnzgu.ru

Автореферат разослан 14 ноября 2009 г.

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

диссертационного совета

доктор технических наук,

профессор

Гурин Е. И.

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

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

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

Для увеличения скорости и повышения качества анализа и классификации информационных ресурсов в настоящее время применяют дискретные методы, основанные на использовании результатов и идей дискретного анализа. Аппарат и методы дискретной математики обладают рядом преимуществ и позволяют, например, получить результат при отсутствии сведений о функциях распределения и при наличии малых обучающих выборок. К дискретным методам классификации относятся, например, алгебраический подход, методы комбинаторного анализа структуры пространств описаний и др. Вопросы создания и разработки дискретных методов анализа информации нашли свое отражение в работах российских ученых: Ю. И. Журавлева, К. В. Рудакова, К. В. Воронцова, Е. В. Дюковой, Н. Г. Федотова, В. Б. Лебедева и др. Известны также работы зарубежных уче-

ных, связанные с применением дискретных методов распознавания: Герберта Симона (Herbert Simon), Т. М. Митчелла (Т. М. Mitchell), Р. Куинлена (R. Quinlan) и др.

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

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

Результаты исследования позволили разработать алгоритм дискретной классификации на основе модификации алгоритма, использующего методы КУМ и его программную реализацию. Рассмотрены вопросы выполнения параллельных вычислений для реализации разработанного алгоритма.

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

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

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

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

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

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

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

- разработаны программные средства дискретной классификации и визуализации результатов на основе выбранной модели решетки кортежей данных;

- проведено сокращение времени поиска элементарных классификаторов при выполнении процедуры обучения в разработанном алгоритме;

- экспериментально исследована эффективность классификации образов с помощью разработанного алгоритма;

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

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

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

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

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

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

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

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

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

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

На защиту выносятся:

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

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

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

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

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

Реализация и внедрение результатов. Основные результаты диссертационной работы использованы при выполнении проекта № 06-07-89167 «Система интеллектуализации анализа и поиска биометрической информации в базе данных с помощью методов стохастической геометрии» по гранту Российского фонда фундаментальных исследований (РФФИ) в Пензенском государственном университете и внедрены в разработках ЗАО «Пензенская телефонная компания» (г. Пенза).

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: VII, VIII Международных научно-технических конференциях «Новые информационные технологии и системы» (г. Пенза, 2006, 2008 гг.); VII, VIII, IX Международных научно-технических конференциях «Современные технологии документооборота в бизнесе, производстве и управлении» (г. Пенза, 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 таблиц.

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

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

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

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

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

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

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

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

В основе базовой модели объекта распознавания в методах КУМ лежит решетка Ь^, которая строится с использованием оператора

замыкания А— Г) Ял, заданного на порождающем семействе

множеств {л} значений признаков классификации объекта. Здесь

(1 . • А - замыкание множества; А с и7?, 11А - множество семейства {Щ ,

ьф}

которое содержит А в качестве подмножества, т. е. АсЯа. Все

П

замкнутые подмножества А = А образуют полную решетку Ь^ , упорядоченную включением.

По определению, элементарным классификатором (ЭК) является любой, отличный от структурного нуля и единицы элемент решетки , который покрывается элементами порождающего семейства

[Щ, принадлежащими одному классу. Задача классификации заключается в определении семейства минимальных ЭК, которые минимальны по мощности и образуют минимальное по мощности подсемейство, покрываемое только элементами одного класса объектов распознавания в решетке обучающей выборки. В процессе обучения алгоритм классификации строит диаграмму Хассе решетки Ь^

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

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

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

К — (Кт),т ~ \,М, К -М - число признаков в описании одного

объекта, то каждое из множеств Кт = = \,Ыт в кортеже, ин-

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

множеств |, (к^ = где С - число

кортежей в семействе (обозначение ^ характеризует кортеж одноэлементных множеств), а -М . к(1) - МНОЖССТ1Ю прецедентов, заданных кортежами, соответствует семейству [Щ , т. е. является семейством порождающих множеств кортежей. Тогда

{к{1\ и |МИ| = 1' {кг)т вКт-Если признак отсутст-

вует, то =0.

Семейство множеств кортежей изоморфно некоторому подсемейству множества , где IЖ = |кт п } - множество всех допустимых значений признаков, упорядоченных в кортежах. При этом сохраняются операции включения. Изоморфизм определяется как отображение: ф:и^->ил, где 1)Л= и Л = - множество

ЩЩ

всех допустимых значений признаков классификации в модели 1Л]), и {= \иЩ . Данный изоморфизм можно представить так:

Я»=

Г К\ Кг - кщ - - - 4

^1,1 ¿4,2 ■•• Кщ ^2,1 ••• ^,N2 - км, 1 - км,Ым 11 Ъ ........................ П

Каждому кортежу соответствует отображение

как неупорядоченное подмножество множества Л^А, которое устанавливает отношение не только между элементами множеств, но и их индексами:

ф(*/и,л) = '/,где / =

т при п = 1,

,т = \,М, /7 = 1,^.

"»+ прии>1,

9=1

В этом случае отображение <р является биективным и сохраняет отношения порядка, т. е. А с: В о <р-1 (А) -< ф-1 (5). Для такого отображения справедлив изоморфизм решеток, поэтому решетка имеет прообраз в виде решетки кортежей Ь^. Например, если К = ({а,6,с},{а,с,й?,/},{а,Ь,с,/}) и

({с},{а}.{Ь}),({с}.{а},{с}),({с},{/}.{с}>}.

и М = 3,ЛГ] =3,Ы2 =4, то согласно установленному изоморфизму порождающее семейство множеств имеет вид

{Л} = {{1,6,8},{1,5,8},{1,4,8},{2,4,9},{2,4,11},(3,4,10},{3,7,10}}

(здесь элементы множеств равны отображению ф индексов семейства IIАГ = {кт „|). На рис. 1 изображены решётка 1у и изоморфная ей решетка ¿ф (для упрощения структурный нуль и структурная единица решеток не показаны, элементы разных классов обозначены разными геометрическими фигурами). Минимальными ЭК являются для класса А - кортеж {{в}>{0}>{я}). Для класса □ - семейство

кортежей {({б},{а},{0}^{0},{а},{А})|, для класса О - кортеж

<Ш*>Ш)-

-Ь' ^ . }>? Ч^ ^ «ч»4 лГ ^ Ч^ лУ ч»4 .0' чУ

Рис. 1. Диаграммы изоморфных решеток Ь^ и

на

Пусть множество кортежей Б1 Ж классов Б®" = | \ I, Ы=Щ у=, где

классифицировано и разделено ~ — ^

= У„ - мощ-

ность

по-

класса и ^ } • Операция комбинаторного

парного пересечения (КПП) для двух кортежей одноэлементных множеств одного класса будет иметь следующий вид:

осо-

^Г} г^) ={{кх}т гл^}т). Рассмотрены

бенности алгоритма дискретной классификации, основанного на построении решетки кортежей Ь9, показаны направления разработки,

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

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

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

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

Т^ отдельно для каждого класса. Классификация заключается в поиске минимальных семейств ЭК, которые покрывают множество признаков классифицируемог о объекта. Схема работы системы распознавания па основе такого алгоритма представлена на рис. 2,а. На рис. 2,6 представлена схема алгоритма поиска минимальных ЭК.

шшшж

11' = ж ■

Удаление общих ЭК

ешиишшшМ

Опрев, мини- ; мвльньм ЭК [

; щ

п.ЩВвод п/естовоаоМ | момента £ ,

«Зз

Определение покрытии ЭК ¥

Принятые ро июния

( Конец ^г-

Формирование вектора у\к)

*

Выполнении операции КПП

_ 1 _

7 Проверка уникальности элемента

Ъ

Конец \

а б

Рис. 2. Схема работы системы распознавания (а); схема алгоритма поиска ЭК (б)

("истома делит все обучающие объекты на классы. Для каждого

класса поиск ЭК ведется отдельно. В каждой таблице Т^ определяются элементы, покрываемые обучающими объектами только одного класса. Установлено, что каждая таблица Т^ является симметричной относительно главной диагонали. Предложено свести построение таблиц к построению векторов У^. Это существенно со-

кращает время выполнения операции КПП в . На рис. 2,6 Yw число обучающих элементов из одного класса w, к- номер вектора V^, Ik - число ЭК в векторе V^. После проверки всех возможных

векторов V^ (если очередное Ik < 1) общее число ЭК / <; £ 1у ,

к ()>• 1

где Н- максимальное число векторов V^ (число шагов алгоритма), Iу - число ЭК, покрываемых (^S^ ^ .

Для каждой пары ЭК операция КПП выполняется М раз. Для со кращения количества операций КПП предложено помечать непустые одноэлементные множества путём введения дополнительного множества меток. Если = , то множество меток S^^J ■-■

= {~k}m~{\,2,...,m,...,M) при условии, что {к} Ф0 \/т~Л,М.

Установлено, что это существенно уменьшает время выполнения операции КПП.

Для увеличения быстродействия использован подход деления ЭК на условные уровни. Наибольший эффект достигается при большом числе признаков в распознаваемых объектах. Для повышения производительности алгоритма предложено использовать SPMD (single-program тиШр1е-<Ыа)-нарадигму программирования, которая позволяет реализовать параллельную обработку процесса обучения.

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

Я Dr\

<2=1.2.^-0,,

м ы

где II- число шагов алгоритма для нахождения всех ЭК, Dj размер множества кортежей на каждом шаге алгоритма. Общее число опера •

r

ций КПП при Р процессах (Ц-Q'P+Щ • Предложен способ

И Н)

управления списками ЭК, основанный на использовании очереди FIFO для контроля уникальности ЭК.

В четвёртом разделе рассмотрена методика исследования эффективности алгоритма дискретной классификации на основе методов КУМ. Приведено сравнение качественных характеристик разработанного алгоритма дискретной классификации в сравнении с другими известными алгоритмами распознавания образов.

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

Для определения эффективности разработанного алгоритма использована классическая задача «Mushroom Database» Калифорнийского университета г. Ирвина, предназначенная для эмпирического анализа эффективности алгоритмов обучения в задачах классификации и распознавания образов. Она содержит дискретное описание в терминах физических характеристик 8124 различных грибов, поделённых на два класса: съедобные и несъедобные. Каждый объект имеет 22 признака. В сформированных обучающих выборках объекты распределены равномерно, размер каждой новой обучающей выборки возрастает.

В работе проведено сравнение с другими известными алгоритмами. Использованы алгоритмы из системы классификации и распознавания образов «Weka» (университет Вайкато, Гамильтон, Новая Зеландия). С использованием пакета STATISTICA 8 для разности исходной и полученной частот случаев, чувствительности и специфичности, получены значения описательных статистик. Результаты представлены в табл. 1.

Таблица 1

Наименование алгоритма Среднее значение

Разность частот Чувствительность Специфичность

Алгоритм дискретной классификации на основе КУМ 0,000786 0,998382 1,000000

Расстояние Хемминга 0,003558 0,992735 1,000000

Дерево регрессий 0,003764 0,991595 1,000000

1В1 классификатор 0,003282 0,992979 1,000000

Евклидово расстояние 0,013685 0,970618 0,998050

Минимаксный критерий 0,074065 0,867067 0,987755

Дерево принятия решений 0,012299 0,982570 0,997375

Наивный байесовский классификатор 0,048430 0,903863 0,994473

Дерево принятия решений с использованием наивного байесовского классификатора 0,016998 0,987896 0,972317

Также получены значения описательных статистик для вероятности FRR и FAR. Результаты представлены в табл. 2.

Таблица 2

Значения вероятностей ошибок FRR и FAR алгоритмов классификации

Наименование алгоритма Вероятность FRR Вероятность FAR

Среднее значение Стандартная ошибка среднего Среднее значение Стандартная ошибка среднего

Алгоритм дискретной классификации на основе КУМ 0,000000 0,000000 0,001618 0,000143

Расстояние Хемминга 0,000000 0,000000 0,007265 0,000435

Дерево регрессий 0,000000 0,000000 0,008405 0,000666

1В1 классификатор 0,000000 0,000000 0,007021 0,000508

Евклидово расстояние 0,001950 0,000422 0,029382 0,003386

Минимаксный критерий 0,012245 0,002641 0,132933 0,018200

Дерево принятия решений 0,002625 0,002625 0,017430 0,009529

Наивный байесовский классификатор 0,005527 0,001135 0,096137 0,003016

Дерево принятия решений с использованием наивного байесовского классификатора 0,027683 0,009721 0,012104 0,003704

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

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

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

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

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

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

4. Разработана модификация алгоритма дискретной классификации на основе решетки кортежей одноэлементных множеств данных, которая позволяет сократить время поиска минимальных элементарных классификаторов по сравнению с базовым алгоритмом на 10-80 % в зависимости от структуры обучающей информации.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в издании, рекомендованном ВАК

1. Минаев, В. Е. Классификация объектов распознавания методом комбинаторно-упорядоченного моделирования / В. Б. Лебедев, В. Е. Мл-наев // Инфокоммуникационные технологии, 2008. - Т. 6. - Специальный выпуск «Технологии безопасности и охраны». - С. 30-34.

Публикации в других изданиях

2. Минаев, В. Е. Устройство биометрического контроля на основе ассоциативного ЗУ / Р. А. Бикташев, В. Е. Минаев // Современные методы и средства обработки пространственно-временных сигналом : сб. ст. IV Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2006. - С. 106-109

3. Минаев, В. Е. Алгоритмы сравнения биометрических образов на основе ассоциативной памяти / Р. А. Бикташев, В. Б. Лебедев, В. Е. Минаев // Современные методы и средства обработки пространственно-временных сигналов : сб. ст. IV Всерос. науч.-техн. конф. - Пенза : ПДЗ, 2006. - С. 109-113.

4. Минаев, В. Е. О методах реализации комбинаторно-упорядоченных процедур классификации описаний распознаваемых объектов / В. Б. Лебедев, В. Е. Минаев // Новые информационные технологии и системы : тр. VII Междунар. науч.-техн. конф. - Ч. 2. - Пенза : ПГУ, 2006. - С. 32-34.

5. Минаев, В. Е. О реализации алгоритма построения решетки с помощью оператора замыкания / В. Б. Лебедев, В. Е. Минаев // Современные технологии документооборота в бизнесе, производстве и управлении: сб. ст. VII Междунар. науч.-техн. конф. - Пенза : ПДЗ, 2007.- С. 96-98.

6. Минаев, В. Е. О способах распараллеливания алгоритма па-строения решетки с помощью оператора замыкания / В. Б. Лебедев,

В.Е. Минаев // Университетское образование : сб. ст. XI Междунар. науч.-метод. конф. - Пенза : ПДЗ, 2007. - С. 54-57.

7. Минаев, В. Е. Дискретная классификация на основе решетки множества кортежей / В. Б. Лебедев, В. Е. Минаев // Современные методы и средства обработки пространственно-временных сигналов : сб. ст. V Всерос. науч.-техн. конф. - Пенза : ПДЗ, 2006. - С. 90-92.

8. Минаев, В. Е. Система распознавания на основе комбинаторно-упорядоченной модели пространства признаков / В. Б. Лебедев,

B. Е. Минаев // Математическое и компьютерное моделирование естественнонаучных и социальных проблем : сб. ст. I Междунар. науч.-техн. конф. - Пенза : ПДЗ, 2007. - С. 59-61.

9. Минаев, В. Е. Исследование метода дискретной классификации в задаче распознавания образов на основе решетки множества кортежей / В. Б. Лебедев, В. Е. Минаев // Проблемы информатики в образовании, управлении, экономике и технике : сб. ст. VII Всерос. науч.-техн. конф. - Пенза : ПДЗ, 2007. - С. 18-21.

10. Минаев, В. Е. Построение изоморфных решеток в задаче дискретной классификации / В. Б. Лебедев, В. Е. Минаев // Университетское образование : сб. ст. ХП Междунар. науч.-метод. конф. - Пенза : ПДЗ, 2008.-С. 247-249.

11. Минаев, В.Е. Исследование метода дискретной классификации на основе изоморфных решеток / В. Е. Минаев // Университетское образование : сб. ст. ХП Междунар. науч.-метод. конф. - Пенза : ПДЗ, 2008.-С. 250-252.

12. Минаев, В. Е. Применение комбинаторно-упорядоченных моделей для анализа информации / В.Б. Лебедев, В.Е. Минаев// Современные технологии документооборота в бизнесе, производстве и управлении : сб. ст. VIII Междунар. науч.-техн. конф. - Пенза: ПДЗ, 2008.-С. 137-139.

13. Минаев, В. Е. Эффективность классификации на основе комбинаторно-упорядоченного моделирования / В. Е. Минаев // Современные технологии документооборота в бизнесе, производстве и управлении : сб. ст. VID Междунар. науч.-техн. конф. - Пенза : ПДЗ, 2008. -

C. 139-142.

14. Минаев, В. Е. О методах распараллеливания алгоритма дискретной классификации на основе комбинаторно-упорядоченных моделей / В. Е. Минаев // Перспективы развития систем среднего и

высшего профессионального образования в современном обществе : сб. ст. Междунар. науч.-практ. конф. - Ч. 1. - Пенза: ПДЗ, 2008. — С.125-127.

15. Минаев, В. Е. Метод дискретной классификации / В. Б. Лебедев, В. Е. Минаев // Новые информационные технологии и системы : тр. VIII Междунар. науч.-техн. конф. - Ч. 2. - Пенза: ПГУ, 2008. -С. 113-118.

16. Минаев, В. Е. О реализации алгоритма дискретной классификации / В. Е. Минаев // Новые информационные технологии и системы : тр. VIII Междунар. науч.-техн. конф. - Ч. 2. - Пенза: ПГУ, 2008.-С. 118-122.

17. Минаев, В. Е. Эффективность метода дискретной классификации в задачах информационной безопасности / В. Б. Лебедев, В. Е. Минаев // Современные технологии документооборота в бизнесе, производстве и управлении: сб. ст. IX Междунар. науч.- пракг. конф. - Пенза : ПДЗ, 2009. - С. 71-73.

18. Минаев, В. Е. Об эффективности классификации методом комбинаторно-упорядоченного моделирования / В. Б. Лебедев, В. Е. Минаев // Университетское образование : сб. ст. XIII Междунар. метод, конф. - Пенза : ПДЗ, 2009. - С. 404-406.

Научное издание

МИНАЕВ Валерий Евгеньевич

Классификация образов на основе решетки множества кортежей данных

Специальности: 05.13.17 - «Теоретические основы информатики»; 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Редактор О. Ю. Ещина Технический редактор Н. А. Вьялкоеа

Корректор Ж. А. Лубенцова Компьютерная верстка Н. В. Ивановой

Сдано в производство 09.11.2009. Формат 60x84'/16. Усл. печ. л. 1,16 . Заказ № 561. Тираж 100.

Издательство ПГУ. 440026, Пенза, Красная, 40.

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ КЛАССИФИКАЦИИ.

1.1. Анализ методов распознавания образов.

1.2. Методы дискретной классификации.

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

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

Статистические методы классификации - одна из первых идей для решения задач классификации и распознавания образов [1-15]. Подобные методы весьма эффективны при решении задач, где объекты классификации характеризуются ограниченной степенью изменчивости. В основе таких методов лежит анализ различных коэффициентов сходства и метрик, определяющих близость объектов в анализируемом ограниченном пространстве признаков. Выбор этих параметров зависит от самого пространства, в котором расположены объекты, и неявных характеристик отдельных групп данных. Большинство из таких методов уже хорошо изучены и с трудом поддаются дальнейшему совершенствованию. Различные статистические системы классификации зачастую включают в себя давно разработанные алгоритмы, которые были созданы в предыдущие десятилетия. Исходные данные во многих современных задачах не дают возможности оценить вероятностные характеристики с необходимым уровнем, который позволил бы статистическому алгоритму достаточно точно классифицировать объекты. Вследствие этого подобными методами сложно проводить быстрый и эффективный анализ, так как в реальных современных задачах анализа и обработки информации каждый объект анализа имеет, как правило, сложное описание и может быть представлен десятками, а иногда сотнями и тысячами различных данных. Возникает проблема поиска и разработки более эффективных инструментов анализа больших объемов накопленной информации.

Для увеличения скорости и повышения качества анализа и классификации информационных ресурсов в настоящее время применяют дискретные методы, основанные на использовании результатов и идей дискретного анализа. Аппарат и методы дискретной математики обладают рядом преимуществ и позволяют, например, получить результат при отсутствии сведений о функциях распределения и при наличии малых обучающих выборок. К дискретным методам классификации относятся, например, алгебраический подход, методы комбинаторного анализа структуры пространств описаний и др. Вопросы создания и разработки дискретных методов анализа информации нашли свое отражение в работах российских ученых, Ю.И. Журавлева, К.В. Рудакова, К.В. Воронцова, Е.В. Дюковой, Н.Г. Федотова, В.Б. Лебедева и других. Известны также работы зарубежных ученых по обучающимся алгоритмам распознавания Герберта Симона (Herbert Simon), Т.М. Митчелла (Т.М. Mitchell), Р. Куинлена (R. Quinlan).

В частности, в работах Ю.И. Журавлева рассматривается универсальная схема построения оптимальных алгоритмов распознавания, основанная на применении методов алгебры [16,17]. Данные методы получили дальнейшее развитие в работах К.В. Рудакова и К.В. Воронцова [18-21]. Однако эти методы не обеспечивают ни создания некоторой универсальной модели, ни формализации процесса выбора модели для решения конкретной задачи. Попытки расширить область применения приводят к необходимости использования значительного объема априорной информации, которую можно получить, имея лишь полную модель объекта. Применение методов, основанных на аппарате булевой алгебры, теории дизъюнктивных нормальных форм, теории покрытий булевых и целочисленных матриц Е.В. Дюковой [22-25] оказывается сложным в силу чисто вычислительных трудностей переборного характера на этапе поиска информативных фрагментов описаний объектов. Кроме того, на этапе обучения требуется дополнительная проверка качества полученных описаний с использованием простых эвристик. В работах В.Б. Лебедева и Н.Г. Федотова рассматривается подход, основанный на методах комбинаторно-упорядоченного моделирования (КУМ) структур данных, использующих методы теории упорядоченных множеств и теории решеток [2630]. Работы Герберта Симона, Т.М. Митчелла, Р. Куинлена [31-34] связаны с обучаемыми алгоритмами распознавания, в частности с алгоритмами исключения кандидата, добавления и усиления повторяющихся элементов, а также деревьев решений. Здесь даже один неверно классифицированный объект может сделать алгоритм расходящимся, а ветвление идет в основном по атрибутам с большим числом значений. Кроме того, некоторые наборы данных с идентичными значениями приводят к различным результатам.

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

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

Результаты исследования позволили разработать алгоритм дискретной классификации на основе модификации методов КУМ и его программную реализацию. Рассмотрены вопросы выполнения параллельных вычислений для реализации разработанного алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов. Основные результаты диссертационной работы использованы при выполнении проекта №06-07-89167 «Система интеллектуализации анализа и поиска биометрической информации в базе данных с помощью методов стохастической геометрии» по гранту Российского фонда фундаментальных исследований (РФФИ) в Пензенском государственном университете и внедрены в разработках ЗАО «Пензенская телефонная компания» (г. Пенза) (приложение В). В частности результаты использованы при разработке системы автоматизированного биллинга услуг связи, предназначенной для учета объема потребляемых абонентами услуг, расчета и списания денежных средств в соответствии с тарифами. Данное внедрение позволило повысить эффективность сбора и обработки информации о потребляемых абонентами услугах с целью определения более перспективных направлений развития предоставляемых услуг.

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

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

- VII, VIII Международных научно-технических конференциях «Новые информационные технологии и системы» (г. Пенза, 2006, 2008 г.г.);

- VII, VIII, IX Международных научно-технических конференциях «Современные технологии документооборота в бизнесе, производстве и управлении» (г. Пенза, 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 таблиц.

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

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

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

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

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

4. Разработана модификация алгоритма дискретной классификации на основе решетки кортежей одноэлементных множеств данных, которая позволяет сократить время поиска минимальных элементарных классификаторов по сравнению с базовым алгоритмом на 10-80 % в зависимости от структуры обучающей и информации.

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

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

1. Ту Дж. Принципы распознавания образов Щж. Ту, Р. ГонсалесП Пер. с англ. И.Б. Гуревича, под ред. Ю.И. Журавлева. М.: Мир, 1978. - 411 с.

2. Гренандер У. Лекции по теории образов /У. ГренандерП Пер. с англ. И.Б. Гуревича, под ред. И.Ю. Журавлева. М.: Мир, 1979-1983. Т. 1-3.

3. Буховец А.Г. Об одном подходе к задаче классификации / А.Г. Бухо-вецП Институт социологии РАН. URL: http://www.isras.ru/files/File/4M/18/Buhovec.pdf (дата обращения: 29.07.09).

4. Поспелов Д.А. Искусственный интеллект /Д.А. Поспелов// Модели и методы: Справочник. — М.: Радио и связь, 1990. — Т.2. — 304 с.

5. Воронцов К.В. Классификация, кластеризация, регрессия, многомерное шкалирование /К.В. Воронцов// Лекции по метрическим алгоритмам: электронный ресурс ВЦ РАН. 2006. URL: http://www.ccas.ru/voron/download/MetricAlgs.pdf (дата обращения: 30.07.09).

6. Гиршов Е. Алгоритмы кластеризации /Е. ГиршовИ Библиотека попечительского совета мех.-мат. факультета МГУ. 2006. URL: http://lib.mexrnat.ru/books/13811 (дата обращения: 30.07.09).

7. Методы кластерного анализа. Итеративные методы // Интернет-университет информационных технологий. URL:http://www.intait.ra/department/database/datamining/14/date (датаобращения: 30.07.09).

8. Anil К. Jain. Statistical pattern Recognition: A Review / Anil K. Jain, Duin Robert P. W., Mao Jianchang II IEEE Transactions on pattern analysis and machine intelligence. 2000. - No.l. - Vol. 22.

9. Fraley Chris. Model-Based Clustering, Discriminant Analysis, and Density Estimation /Fraley Chris., E. Raftery Adrian// Journal of the American Statistical Association. 2002.-No. 458.-Vol. 97.-P. 611-631(21).

10. Калинина B.H., Соловьев В.И. Введение в многомерный статистический анализ /В.Н. Калинина, В.И. Соловьев// Учеб. пособие для вузов. — М.: ГОУВПО ГУУ, 2003 г. С. 6-16.

11. Daniel Fasulo. An Analysis of resent Work on Clustering Algoritms /Daniel Fasulo// Technical report. Department of Computer Science & Engineering university of Washington. 1999. - P. 2 -13.

12. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации НО. И. Журавлев// Проблемы кибернетики. — М.: Наука, 1978. Т. 33. - С. 5-68.

13. Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации /Ю. И. Журавлев/7 Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1988.- Т. 1.— С. 9-16.

14. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания /К.В. Воронцов// ЖВМ и МФ. 2000. - Т. 40, № 1. - С. 166-176.

15. Рудаков К.В. Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов /К.В. Рудаков, Ю.В. ЧеховичИ Доклады РАН. 2003. - Т. 388, № 1. - С. 33-36.

16. Рудаков К.В. Критерии полноты моделей алгоритмов и семейств решающих правил для задач классификации с теоретико-множественными ограничениями /К.В. Рудаков, Ю.В. ЧеховичИ Доклады РАН. — 2004. — Т. 394, №4.

17. Рудаков К.В. О некоторых универсальных ограничениях для алгоритмов классификации /КВ. Воронцов// ЖВМ и МФ. м 1986. — Т. 26, № 11.— С. 1719-1730.

18. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. /Е.В. Дюкова/У Учеб. пособие. М.: Прометей, 2003. — 29 с.

19. Дюкова Е.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания /Е.В. Дюкова, Н.В. Песков/7 ЖВМ и МФ. 2002. - Т. 42, № 5. - С. 741-753.

20. Дюкова Е.В. Построение распознающих процедур на базе элементарных классификаторов /Е.В. Дюкова, Н.В. Песков// Математические вопросы кибернетики: под ред. О. Б. Лупанов. — М.: Физматлит, 2005. — Т. 14.

21. Дюкова Е.В. О процедурах классификации, основанных на построении покрытий классов /Е.В. Дюкова, А. С. ИнякинИ ЖВМ и МФ. — 2003. — Т.43. №12. - С. 1884 - 1895.

22. Лебедев В.Б. Структурный анализ систем управления /В.Б. Лебедев/7 Учеб. пособие. Пенза: ПГУ, 2000. - 100 с.

23. Лебедев В.Б. Технология ассоциации данных методом комбинаторно-упорядоченного моделирования IB.Б. Лебедев/7 Новые информационные технологии и системы: труды VI Междунар. науч.-техн. конф. —4.1. Пенза: ПГУ, 2004.-С. 249-253.

24. Лебедев В.Б. Поиск ассоциаций данных методом комбинаторно-упорядоченного моделирования /В.Б. Лебедев, М.О. Богданов// Вычислительные системы и технологии обработки информации: межвуз. сб. науч. трудов Вып.З (29) - Пенза: ПГУ, 2005. - С. 115 - 120.

25. Федотов Н.Г. Теория признаков распознавания образов на основе стохастической геометрии и функционального анализа. — М.: ФИЗМАЛИТ, 2009.-304 с.

26. Mitchell Т.М. Generalization as search /Т.М. Mitchell!7 Artificial Intelligence. 1982. - No. 18(2). - P. 203-226.

27. Induction of decision trees /J.R. QuinlanH Machine Learning. 1986. -No. 1(1).-P. 81-106.

28. Quinlan J.R. C4.5: Programs for machine learning /J.R. QuinlanH San Francisco: Morgan Kaufmann. 1993. - V. 302.

29. Quinlan J.R. Bagging. Boosting and CN4.5 /J.R. QuinlanH In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI96). Menlo Park: AAAI Press, 1996. -P.725-730.

30. Воронцов K.B. Лекции по статистическим (байесовским) алгоритмам классификации /КВ. Воронцов// ВЦ РАН, Москва. URL: http://www.ccas.ru/voron/download/Bayes.pdf (дата обращения: 29.07.09).

31. Шалымов Д. С. Рандомизированный алгоритм стохастической аппроксимации в задаче распознавания отдельных слов речи /Д.С. Шалымов// С.-Петербург Гос. Университет. URL:http://www.math.spbu.ru/user/gran/sb2/shalymov.pdf (дата обращения: 29.07.09).

32. Бауман Е.В. Методы стохастической аппроксимации в задачах кластерного анализа /Е.В. Бауман, А.А. ДорофеюкП Математические методы распознавания образов (ММРО-11): Сборник докладов 11-й Всероссийской конференции. -М.: "Регион-Холдинг", 2003. С.16-18.

33. Дюк В. Data Mining состояние проблемы, новые решения /В. Дюк //С.-Петербург. инстит. информат. и автоматиз. РАН. URL: http://freelance4.narod.ru/DM.htm (дата обращения: 29.07.09).

34. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора" /М.Н. Вайнцвайг// Алгоритмы обучения распознаванию образов. — М.: Сов.радио, 1973. С. 8-12.

35. Системы распознавания образов (идентификации). Геометрический и структурный подходы // Интернет-Университет Информационных Технологий. URL: http://www.intuit.rU/department/expert/artintell/3/2.html (дата обращения: 29.07.09).

36. Richard W. Hamming. Error-detecting and error-correcting codes /Richard W. Hamming// Bell System Technical Journal. 1950. No. - 29(2). - P. 147160.

37. Паклин H. Алгоритмы кластеризации на службе Data Mining /Н. ПаклинИ Лаборатория BaseGroup «Технологии анализа данных». URL:http://www.basegroup.ru/library/analysis/clusterization/datamining/ (дата обращения: 29.07.09).

38. Обобщенные методы кластерного анализа. // SPC-consulting. StatSoft Russia. URL: http://www.spc-consulting.ru/DMS/introcl.htm (дата обращения: 29.07.09).

39. Современное состояние в области практических методов распознавания, классификации и анализа данных. // Data Mining. URL: http://azfor.ucoz.ru/publ/3-l-0-4 (дата обращения: 09.08.09).

40. Коллективы решающих правил. // CODENET. Все для программиста. URL: http://www.codenet.ru/progr/alg/ai/htm/gl39.php (дата обращения: 30.07.09).

41. Лапко В.А. Нелинейные непараметрические коллективы решающих правил /В.А. Лапко, Р.В. Бадмаев, А.Н. Капустин// Вестник КрасГУ. «Физико-математические науки». — 2006. — №4. — С. 102-108.

42. Методы классификации и прогнозирования. Метод опорных векторов. // Интернет-Университет Информационных Технологий. — http://www.intuit.rU/department/database/datamining/l0/dataminingl0.html (дата обращения: 29.07.09).

43. Романов П.В. Интеллектуальные информационные системы в экономике /П.В. Романов// Учеб. пособие: под ред. д.э.н. проф. Н.П. Тихомирова. М.: «Экзамен». - 2003. - 496 с.

44. Гончаров М. Модифицированный древовидный алгоритм Байеса для решения задач классификации /М. Гончаров// Spellabs it.company. 2007. URL: http://www.spellabs.ru/download/AugmentedNaiveBayes.pdf (дата обращения: 29.07.09).

45. Воронцов КВ. Лекции по методу опорных векторов /К.В. Ворон-цов//ВЦ РАН, Москва. URL: http://www.ccas.ru/voron/download/SVM.pdf (дата обращения: 29.07.09).

46. Dan Roth. The SNoW Learning Architecture /Dan Roth// Department of computer science and the Beckman institute. University of Illinois. URL: http://12r.cs.uiuc.edu/~danr/snow.html (дата обращения: 04.08.09).

47. Sparse Network of Winnows method (SNoW). // Graphics and Media Lab Library. URL: http://library.graphicon.ru/pubbin/viewprop.pl?propid=223 (дата обращения: 04.08.09).

48. Вежневец A. Boosting — усиление простых классификаторов /А. Вежневец, В. Вежневец// Компьютерная графика и мультимедиа: сетевой журн. URL: http://cgm.computergraphics.ru/content/view/112 (дата обращения: 30.07.09).

49. Халафян A.A. Statistica 6. Статистический анализ данных: учебник для вузов, 3-е изд. М.: БИНОМ. - 2007. - 315 с.

50. STATISTICA для Windows. Техническое описание. // StatSoft Russia. URL: http://www.statsoft.ru/home/Products/Statistica/details/default.htm (дата обращения: 30.07.09).

51. STATGRAPHICS Centurion XV. // StatPoint Technologies, Inc.: сайт. URL: http://www.statgraphics.com (дата обращения: 30.07.09).

52. Учись работать с SPSS // learnSPSS.ru: сайт. URL: http://www.learnspss.ru (дата обращения: 30.07.09).

53. Горелъннк A.JI. Методы распознавания HA.JI. Горельник, В.А. СкрипкинИ Учеб. пособие для вузов. М.: Высшая школа, 1977. — 222 с.

54. Simon H.A. Why should machines learn /Н.А. Simon// In Michalski et al. С A: Tioga Press, 1983. - Chapter 2. - P.

55. Люгер Джордж Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание /Джордж Ф. ЛюгерИ Пер. с англ. — М.: «Вильяме», 2003. 864 с.

56. Журавлев Ю. И. Распознавание образов и распознавание изображений НО. И. Журавлев, И.Б. ГуревичИ Распознавание, классификация, прогноз. Математические методы и их применение. — М.: Наука, 1989. — Т. 2. — С. 5— 73.

57. Журавлев Ю. И. Об алгебраической коррекции процедур обработки (преобразования) информации /Ю. И. Журавлев, К.В. Рудаков// Проблемы прикладной математики и информатики. 1987. - С. 187-198.

58. Рудаков К.В. О симметрических и функциональных ограничениях для алгоритмов классификации /К.В. Рудаков// Доклад АН СССР. — 1987.— Т. 297, № 1.-С. 43^46.

59. Рудаков К.В. Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации /К.В. Рудаков И Кибернетика. 1987. - № 4. - С. 73-77.

60. Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов /КВ. Рудаков// Кибернетика. 1987. — №2.-С. 30-35.

61. Рудаков К.В. Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами /К.В. Рудаков, С.В. Трофимов/7 ЖВМ и МФ. 1988. - Т. 28, № 9. - С. 1431-1434.

62. Рудаков К.В. О применении универсальных ограничений при исследовании алгоритмов классификации /КВ. Рудаков/7 Кибернетика. -1988.-№ 1.-С. 1-5.

63. Рудаков К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания /КВ. Рудаков, К.В. Воронцов И Доклады РАН. 1999. - Т. 367, № з. с. 314-317.

64. Дюкова Е.В. Дискретный анализ признаковых описаний в задачах распознавания большой размерности /Е.В. Дюкова, Ю.И. Журавлев/7 ЖВМ и МФ 2000. - Т.40. - №8. - С. 1264 - 1278.

65. Дюкова Е.В. Дискретный анализ данных в задачах кластеризации /Е.В. Дюкова, А.С. ИнякинН Интеллектуализация обработки информации: тез. докладов междунар. науч. конф. — Симферополь: Крымский, науч. центр НАН Украины, 2006. С. 73-75.

66. Инякин А.С. Алгоритмы поиска неприводимых покрытий булевых матриц /А.С. ИнякинН Сообщ. по прикладной мат. — М.: Вычислительный Центр им. А.А. Дородницына РАН, 2004. С. 3-22.

67. Djukova E.V. Selection of typical objects in classes for recognition problems /Е. V. Djukova, N. V. PeskovH Pattern Recognition and Image Analysis. — 2002. No 3. - Vol. 12. - P. 243-249.

68. Дюкова E. В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели /Е.В. Дюкова/7 Приложение к учеб. пособию. М.: Прометей, 2003. — 16 с.

69. Djukova E.V. Discrete recognition procedures: The complexity of realization /Е. V. Djukova!7 Pattern Recognition and Image Analysis. — 2003. — No. 1. — Vol. 13.-P. 8-10.

70. Djukova E.V. Increasing the efficiency of combinatorial logical data analysis in recognition and classification problems IE.V. Djukova, A.S. Inyakin, N. V. PeskovH Pattern Recognition and Image Analysis. 2005. - No. 4. -Vol. 16.-P. 707-711.

71. Дюкова Е.В. О построении тупиковых покрытий булевых и целочисленных матриц /Е.В. Дюкова, А.С. ИнякинН Математические методы распознавания образов (ММРО-13): сбор, докладов 13-й Всероссийской конф. — М.: "МАКС Пресс", 2007. С.252-254.

72. Дюкова Е.В. О некоторых подходах к вычислению информативных характеристик обучающей выборки /Е.В. Дюкова, Н.В. Песков// Математические методы распознавания образов (ММРО-9): сбор, докладов 9-й Всероссийской конф. -М.: AJIEB-B, 1999. С. 181-183.

73. Велсневец В. Оценка качества работы классификаторов /В. Вежне-вец// Компьютерная графика и мультимедиа: сетевой журн. 2007. URL: http://www.cgm.computergraphics.rU/content/view/l 06 (дата обращения: 30.07.09).

74. Паклин H. Логистическая регрессия и ROC-анализ математический аппарат /Н. Паклин// Лаборатория BaseGroup «Технологии анализа данных». URL: http://www.basegroup.ru/library/analysis/regression/logistic (дата обращения: 30.07.09).

75. Айгнер М. Комбинаторная теория. /М. АйгнерИ Пер. с англ. — М.: Мир, 1982.-558 с.

76. Горбатов В.А. Фундаментальные основы дискретной математики /В.А. Горбатое// Информационная математика. М.: Изд-во Наука. Физмат-лит, 2000. - 544с.

77. Вавилов Н. Конкретная теория групп /Н. Вавилов// С.-Петербургский гос. университет. Мат.-мех. факультет. URL:http://www.math.spbu.ru/user/valgebra/grou-book.pdf (дата обращения: 26.03.06).

78. Минаев В.Е. Метод дискретной классификации /В.Б. Лебедев, В.Е. Минаев/'/ Новые информационные технологии и системы: труды VIII Междунар. науч.-техн. конф. 4.2. Пенза, ПТУ, 2008. - С. 113 - 118.

79. Минаев В.Е. Построение изоморфных решеток в задаче дискретной классификации /В.Б. Лебедев, В.Е. Минаев// Университетское образование: сборник статей XII Междунар. науч.-метод. конф. Пенза: ПДЗ, 2008. - С. 247 - 249.

80. Минаев В.Е. Классификация объектов распознавания методом комбинаторно-упорядоченного моделирования /В.Б. Лебедев, В.Е. Минаев// Ин-фокоммуникационные технологии, 2008. Т.6. — Специальный выпуск «Технологии безопасности и охраны». - С. 30 - 34.

81. Кохонеп Т. Ассоциативные запоминающие устройства. — М.:Мир, 1982.-384 с.

82. Кохонеп Т. Ассоциативная память. — М.:Мир, 1980. — 240 с.

83. Минаев В.Е. О реализации алгоритма дискретной классификации /В.Е. Минаев!I Новые информационные технологии и системы: Труды VIII Междунар. науч.-техн. конф. 4.2. Пенза, ПТУ, 2008. - С. 118 - 122.

84. Минаев В.Е. О способах распараллеливания алгоритма построения решетки с помощью оператора замыкания /В.Б. Лебедев, В.Е. Минаев!I Университетское образование: сб. ст. XI Междунар. науч.-метод. конф. — Пенза: ПДЗ, 2007.-С. 54-57.

85. Flynn М. Very high-speed computing system /М. FlynnH Proc. IEEE. -1966.-No. 54.-P. 1901-1909.

86. Flynn M. Some Computer Organisations and Their Effectiveness /М. FlynnH IEEE Trans. Computers. 1972. - No. 9. - Vol. 21. - P.948-960.

87. Топорков B.B. Модели распределенных вычислений. -M.:ФИЗМАТЛИТ, 2004. 320с.

88. Антонов А.С. Введения в параллельные вычисления /А.С. Антонов// Методическое пособие. М.: МГУ, 2002. - 69 с.

89. Ed. R. Buyya. High performance cluster computing. V. 1. Architectures and systems. V. 2. Programming and applications. — New Jersey: Prentice Hall PTR, 1999.

90. Айвазян C.A. Прикладная статистика: Классификация и снижение размерности: справочное издание /С.А. Айвазян, В.М. Бухштабер, И.С. Ето-ковН Под ред. С.А. Айвазяна. М.: Финансы и статистика, 1989. — С. 608.

91. ЧакчирС.Я. Свой или "чужой"? 1С. Я. Чакчир, А. А. БорейшоП Системы безопасности: журнал. 2006. — № 3. — С. 118-119.

92. Минаев В.Е. Об эффективности классификации методом комбинаторно-упорядоченного моделирования /В.Б. Лебедев, В.Е. Минаев// Университетское образование: сборник статей XIII Междунар. методич. конф. — Пенза: ПДЗ, 2009. С. 404 - 406.

93. Ходасевич Г.Б. Обработка экспериментальных данных на ЭВМ. Обработка одномерных данных /Г.Б. Ходасевич// Учеб. пособие. — URL: http://dvo.sut.ru/libr/opds/il30hodopartl/index.htm (дата обращения: 4.08.09).

94. UCI Machine Learning Repository. // University of California. Irvin. URL: http://archive.ics.uci.edu/ml/about.html (дата обращения: 30.07.09).

95. Mushroom Data Set. // UCI Machine Learning Repository. University of California. Irvin. URL: http://archive.ics.uci.edu/ml/datasets/Mushroom (дата обращения: 30.07.09).

96. Минаев В.Е. Исследование метода дискретной классификации в задаче распознавания образов на основе решетки множества кортежей /В.Б.

97. Лебедев, В.Е. МинаевП Проблемы информатики в образовании, управлении, экономике и технике: сборник статей VII Всероссийск. науч.-техн. конф. — Пенза: ПДЗ, 2007. С. 18 - 21.

98. Минаев В.Е. Исследование метода дискретной классификации на основе изоморфных решеток /В.Е. Минаев// Университетское образование: сборник статей XII Междунар. науч.-метод. конф. — Пенза: ПДЗ, 2008. С. 250-252.

99. Weka 3: Data Mining Software in Java. // WEKA. The University of Waikato. URL: http://www.cs.waikato.ac.nz/ml/weka/ (дата обращения: 30.07.09).

100. Aha D. "Instance-based learning algorithms" ID. Aha, D. Kibler // Machine Learning. 1991.-Vol.6.-P. 37-66.

101. George H. Estimating Continuous Distributions in Bayesian Classifiers /Н. George, P. LangleyH Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. San Mateo: Morgan Kaufmann. - 1995. P. 338-345.

102. Freund Y. The alternating decision tree learning algorithm /Y. Freund, L. Mason// Proceeding of the Sixteenth International Conference on Machine Learning. 1999. Bled, Slovenia. - P. 124-133.

103. Lievens S. A Probabilistic Framework for the Design of Instance-Based Supervised Ranking Algorithms in an Ordinal Setting IS. Lievens// Annals of Operations Research. -2008. V. 163. - P. 115-142.• 137 •

104. Андреев И. Деревья решений — CART математический аппарат. Часть 2. /И. Андреев// Лаборатория BaseGroup «Технологии анализа данных». URL: http://www.basegroup.ru/library/analysis/tree/mathcartpart2/ (дата обращения: 30.07.09).

105. Метод k-средних // Глоссарий: лаборатория BaseGroup «Технологии анализа данных». URL: http://www.basegroup.ru/glos-sary/definitions/kmeans/ (дата обращения: 30.07.09).

106. Расстояние Евклида. Глоссарий: лаборатория BaseGroup «Технологии анализа данных». URL: http://www.basegroup.ru /glossary/definitions/euclid/ (дата обращения: 30.07.09).

107. Расстояние Хемминга. Глоссарий: лаборатория BaseGroup «Технологии анализа данных». URL: http://www.basegroup.ru/glossary/definitions/hammingdistance/ (дата обращения: 30.07.09).

108. Кирьянов Д.В. Mathcad 14. С.-Петербург: BHV, 2007. - 704 с.

109. Среднее значение // Электронный статистический словарь: StatSoft Russia. URL: http://www.statsoft.ru/home/textbook/glossary/glosss.html. (дата обращения: 30.07.09).

110. Стандартная ошибка среднего // Электронный статистический словарь: StatSoft Russia. URL: http://www.statsoft.ru/home /textbook/glossary/glosss.html (дата обращения: 30.07.09).

111. Медиана // Электронный статистический словарь: StatSoft Russia. URL: http://www.statsoft.ru/home/textbook/glossary/glossm.html (дата обращения: 30.07.09).

112. Стандартное отклонение // Электронный статистический словарь: StatSoft Russia. URL: http://www.statsoft.ru/home/textbook/glossary/glosss.html (дата обращения: 30.07.09).

113. Корреляция // Электронный статистический словарь: StatSoft Russia. URL: http://www.statsoft.ru/home/textbook/glossary/glossk.html (дата обращения: 09.08.09).