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

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

Бояркин Михаил Игоревич

СИНТЕЗ ИНФОРМАЦИОННОЙ СИСТЕМЫ ГРУППИРОВКИ МНОГОМЕРНЫХ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ КЛАСТЕРНОГО АНАЛИЗА

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

АВТОРЕФЕРАТ

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

003455927

Самара-2008

003455927

Работа выполнена иа кафедре «Автоматика и управление в технических системах» ГОУ ВПО «Самарский государственный технический университет».

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

- доктор технических наук Юдашкин Александр Анатольевич

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

- доктор технических наук, профессор Батищев Виталий Иванович

- доктор технических наук Минаков Игорь Александрович

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

Учреждение Российской академии наук Институт систем обработки изображений РАН, г. Самара

Защита диссертации состоится 23 декабря 2008г. в 9 часов на заседании диссертационного совета Д 212.217.03 в Самарском государственном техническом университете по адресу: 443010, г. Самара, ул. Галактионовская, 141, ауд. 28.

С диссертацией можно ознакомиться в библиотеке Самарского государственного технического университета по адресу: 443100, г.Самара, ул. Первомайская, 18, корп. №1 и на официальном сайте www.samgtu.ru.

Отзывы на автореферат в двух экземплярах заверенные печатью просим направлять по адресу: 443100, г.Самара, ул. Молодогвардейская, 244, СамГТУ, Главный корпус, ученому секретарю диссертационного совета Д 212.217.03.

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

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

--— Н.Г. Губанов

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

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

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

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

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

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

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

- не существует заранее классифицированной обучающей выборки,

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

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

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

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

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

- исследование и анализ существующих методов кластерного анализа; обоснованный выбор моделей кластеризации многомерных векторов, в условиях растущего объема обрабатываемых данных;

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

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

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

анализ и обоснование достоверности полученных результатов.

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

Научная новизна.

В диссертации получены следующие основные научные результаты:

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

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

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

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

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

ной системы индексации и поиска графической информации;

Реализация результатов работы. Результаты диссертационных исследований использованы при разработке автоматизированной системы индексации больших массивов графических данных с учетом критерия визуального сходства изображений с данными, поступающими в режиме реального времени, в конструкторском отделе промышленного предприятия ООО «Эллипс» (г. Самара), а также в учебном процессе подготовки магистрантов по направленшо 22.00.00 «Автоматика и управление» в дисциплинах «Интеллектуальные технологии в системах управления» и «Системное моделирование» в ГОУ ВПО «Самарский государственный технический университет».

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на XXXI Самарской областной научной конференции (Самара, 2005); II Всероссийской научной конференции «Математическое моделирование и краевые задачи» (Самара, 2005); V Всероссийской межвузовской конференции «Практика применения научного программного обеспечения в образовании и исследованиях» (Санкт-Петербург, 2007); VI Всероссийской научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях» (Санкт-Петербург, 2008); X Международной конференции «Проблемы управления и моделирования в сложных системах» (Самара, 2008). Работа поддержана грантом РФФИ по проекту 07-08-00401-а.

Публикации. По теме диссертации опубликовано 9 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 115 страницах машинописного текста, содержит 21 рисунок, 1 таблицу, список литературы из 80 наименований и 2 приложения.

Основные положения, выносимые на защиту:

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

Форма меры близости в модели кластеризации, зависящей от топологических свойств фазового пространства динамической системы распознавания образов.

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

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

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

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

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

В процедуре кластерного анализа данных существует ряд основных этапов-составляющих:

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

2. Выбор меры «близости». Мера близости - это функция, которая количественно определяет насколько «схожи» или «различны» два образа.

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

4. Контроль правильности результатов кластеризации - проверка корректности разбиения выборки образов на кластеры. То есть, установление факта адекватности результата и его соответствия исходным ожиданиям исследователя.

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

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

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

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

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

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

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

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

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

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

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

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

Предъявляемый к распознаванию образ q{0) является вектором, состоящим из N вещественных чисел. В модели имеется М образов-прототипов v, (/ = 1,2,...,М ), имеющих такую же структуру. В процессе распознавания образ

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

м

*(') = 2>,( (1)

1=1

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

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

м / м \ м Г м ^

а, = Л,<1, --с^Щ 1>,А , (2)

}*, v й=1 у /=1 )

где В, С, Л,- - в общем случае неотрицательные настраиваемые параметры; начальные условия определяются как d(Q)=AVq(G), где А - С1, С = У'У; У -матрица Ы*М, составленная из набора вектор-столбцов {V,, г2,..., у„ }.

Аналогично методу модифицировашгого правила Хэбба, используем разложение <7 на уже известную системе часть - </у. и новую составляющую qы в

виде: Я = <1-/ + Чъ > гДе </у {чУ) = ; . Евклидово

пространство размерности п, образуемое набором линейно независимых, в общем случае, не ортонормированных векторов {г,, г2,..., ун} можно обозначить

как Е^с- . Составляющая qY вектора q по отношению к набору векторов

{у,,^,...,^} - это проекция ц на пространство , то есть та часть вектора,

которую можно полностью описать при помощи эталонных образов модели. Вектор это, соответственно, степень «новизны» </ по отношению к введенному набору {уру2,...,уи} , </к является проекцией на нормаль к пространству

Е"г и частью </, которую невозможно описать при помощи эталонных образов

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

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

Рис. 1 Геомеарическая интерпретация разложения образа

Мера различия с/ между вектором q и группой векторов {V,,у2,...,ул вводится как отношение модулей векторов <7У (ч< У), которое после

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

Данная мера не является метрической. В геометрической интерпретации значение функции - это значение тангенса угла между q и его проекцией на

Ер. Значение меры тем больше, чем меньше составляющая часть вектора q,

которую можно описать набором векторов , и тем меньше, чем

больше эта составляющая. Значение функции меры различия равно 0 в случае,

если вектор г/ принадлежит Е"Г,:. . Таким образом, выполняется физический

смысл функции меры различия в моделях кластеризации. Для использования данной меры в последовательной алгоритмической схеме кластеризации, необходимо определить понятие представителя кластера или его некоторой усредненной характеристики. Для этого вводится понятие «ядра кластера». .Ядро кластера - подмножество образов С" кластера С, которое формируется в процессе роста кластера, таким образом, чтобы наилучшим образом аппроксимировать его свойства. Мера различия между образом и кластером - это мера различия между образом и ядром: Л (с/, С) = . Матрица У'^ содержит упорядо-

ченный в порядке попадания в ядро набор линейно независимых векторов ядра , ^ ,..., усп |. Набор преобразуется в ортонормированный базис пространства Е$г. при помощи процедуры ортогонализации Грамма - Шмидта, с последующей нормировкой. Условие попадание в ядро кластера - это попадание значения меры различия в некоторый диапазон 0 < в, < с/(<7,С) < 02 <© определяемый положительными константами 0,, ©2.

(3)

Попадание образа в область притяжения кластера в классической последовательной схеме кластеризации обозначается выражением й{х,С) >© , где ©некоторый порог, обозначающий радиус области притяжения кластера.

Данное условие модифицируется из-за специфики векторного взаимодействия образов. Прежде всего, из данной геометрической интерпретации логично вытекает значение порога &: составляющая (]у должна быть по модулю больше чем составляющая д^, то есть 0 = 1. Кроме того, на составляющую накладывается ряд дополнительных граничений исходя из ее физического смысла. В случае одиночного ядра составляющая qY должна быть сонаправлена с векто-

7Г

ром у^ . Исходя из геометрической интерпретации, это означает что ап^ <1 < — (рис. 2).

Область попадания е ядро кластера

Рис. 2 Область притяжения кластера с одиночным ядром С ростом размерности ядра, область притяжения кластера расширяется.

Анализ взаимодействия группы векторов {?,v,c,Vj } в пространстве Е^гС- при

помощи аппарата линейной алгебры (рис. 3), с последующим обобщением выводов на случай взаимодействия q с ядром любой размерности n<N , позволяет сформулировать данные дополнительные ограничения:

Условие I: Хотя бы одна компонента вектора г/0 положительна. Условие 2: Для всех отрицательных компонент вектора dt) выполняется:

ы

Данный набор условий в совокупности с условием d{x,C) > 1 используется для отбора кластеров ],/ = 1,...,к в область притяжения которых попадает кластеризуемый образ q.

< cos—, /:«„,< 0.

4

1 ^

lz

Рис. 3 Область притяжения кластера с двойным ядром

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

на основе результатов конкурса среди кластеров-кандидатов }. В данном случае, производится распознавание при помощи используемой модели нейрон-

= 1.....Jt. Победивший

ной сети образа q по набору образов |</г,

(]У1 указывает на С'сжЛ, в который будет добавлен образ q.

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

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

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

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

13

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

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

- это снижение процента ошибок второго рода, или ложных несрабатываний фильтра. В теории распознавания образов данный показатель называется FAR (false acceptance rate - коэффициент ложного пропуска). Ошибки первого рода более критичны для модели кластеризации. Систематические ошибки первого рода приводят к неправильной тенденции кластеризации - формированию кластерной структуры, которая не учитывает, на необходимом уровне, неформали-зуемый критерий ассоциативного сходства. Расхождение реальной структуры групп контекстно-схожих многомерных данных с генерируемой алгоритмом кластерной структурой будет расти по аналогии со «снежным комом». Уменьшение вероятности появления ошибок первого рода возможно только ценой роста ошибок второго рода, что хоть и менее критично, но так же нежелательно, так как ведет к существенному снижению эффективности работы модели, которая рассчитана на работу с большими объемами данных. Исходя из выводов, сделанных в главе 2, наиболее интересным представляется исследование данного вопроса при 0 =1. В соответствии с методикой, изложенной в главе 2, смоделирован механизм фильтрации образов на основе значений меры различия в форме (3). Используемая в исследовании выборка образов {</, v,, v2,..., vM}, где

А/=100, N=1000 - размерность векторов, сгенерированна на основе шума при помощи генератора случайных чисел пакета инженерных вычислений matlab®. Векторы выборки генерируются таким образом, чтобы эмулировать некоторое естественное состояние кластерной структуры. Причем q - входной кластеризуемый образ, векторы выборки {vp v2,...,vM} выполняют роль кластеров, а точнее проекций q на ядра некоторых кластеров в пространстве

v, =? у,

г , , \

,i-\,...,M, так как взаимодействие между кластеризуемым

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

v, была некоторая доля векторов М'>0 v,' для которых , причем

м

«1. После расчета значений мер, вектор q предъявляется для распознава-

ния в модели с М запомненными векторами у1 .

Цель эксперимента - определение способности механизма фильтрации на ошибочные срабатывания. Под ошибочным срабатыванием понимается ситуация, при которой через фильтр не проходит такой образ V, который максимально похож на q среди всех {v,, с точки зрения распознающей нейронной сети. Успешным исходом эксперимента считается результат распознавания, при котором образу q ставился в соответствие вектор \'к е , то есть, для

которого значение меры меньше порога 0. Показатель эффективности измеряется, как доля успешных исходов 5 = ^ среди общего количества экспериментов на каждом из которых выборка {у,, у2,...,ум } генерируется заново.

1

Доля успешных исходов 5

ЙБ 07 08 09 1 11 12 13 1 4 .1-0.9-1.1

1

.1 1, к • .....(

0 95 03 ое5 08 0 75 07

/

/

/

00Е 01 015 Дисперсия значении мер

о е 07 ое оэ 1 11 12 13 ы

¡И) .8-1.2

1,

\ 1 №

Рнс. 4 Характеристики работы механизма фильтрации в зависимости от кластерной струкгуры векторов

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

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

Для оценки качества кластеризации вводится численный аналог показателя качества результата группировки, в виде ряда статистических показателей используемых в теории кластерного анализа для валидации кластерной структуры данных. Эти показатели основаны на сравнении кластерной структуры С = {С,,..., Ст}, полученной в результате работы алгоритма кластеризации, и, определенной независимо от алгоритма, реальной структуры разбиения выборки образов на группы Р = /'} с целью количественного измерения меры согласованности между данными структурами. При оценке качества использовались 4 показателя: статистика Ранда (Rand statistic), коэффициент Джаккарда (Jaccard coefficient), индекс Фолкса-Мэллоуса (Fowlkes-Mallows index), нормированная статистика Хьюберта (Hubert statistic).

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

1) Значения меняются в диапазоне [0,1].

2) Чем выше значение показателя - тем больше согласуются С и Р.

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

позволяют реализовать практически любую математическую модель, и с достаточной точностью производить все расчеты в процессе кластеризации, в том числе выполнять численное интегрирование системы ДУ (2) при моделировании распознавания в нейронной сети Хакена при помощи метода Рунге-Кутта 4-5 порядков.

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

Р = Р.}-

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

1) Не функционирует механизм распознавания образов: решение о включении образа в кластер принимается на основании минимума меры различия;

2) У кластеров не образуется ядер: ядро - это первый образ кластера, которое независимо от включения новых образов не меняется.

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

значения показателей подтверждают данную гипотезу. Значения приведены в таблице 1.

Таблица I. Значения показателей качества для разных режимов модели_

Показатель Я Показатель J Показатель Р\У Показатель Г

Режим 1 0.9808 0.0764 ■ 0.2643 0.2609

Режим 2 0.8748 0.0679 0.2415 0.2238

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

Для оценки эффективности применения разработанного алгоритма кластеризации для синтеза системы поиска и индексации графической информации проведено сравнение времени затрачиваемого на поиск образа среди выборки размера А/=[Ю; 5000] в двух системах: системе распознавания образов и системе поиска и индексации изображений на основе разработанной модели кластеризации. Обе системы построены на базе пакета Млтьав®. В первом случае производится распознавание образа, во втором - поиск наиболее подходящего кластера по разработанному алгоритму. Полученный результат (рис. 5) говорит о том, что поиск происходит существенно быстрее во второй системе.

Рис. 5 Графики времени, затрачиваемого па поиск изображения в разных системах

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

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

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

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

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

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

1) индексирование и кластеризация доступных системе изображений;

2) обработка поисковых запросов пользователей;

3) рекластеризация уже проиндексированных системой изображений для

повышения качества работы системы в целом.

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

1) локализация объектов на изображении;

2) индексация и кластеризация локализованных изображений;

3) обновление ядра кластера;

4) рекластеризация.

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

В рамках системы существуют следующие типы компонентов (рис. 6): Index - хранилище данных, содержащее информацию о проиндексированных графических файлах, кластерах.

Logic Machine - компонент системы, реализующий функции диспетчера конвейера;

Image Machine ~ компонент системы локализующий объекты на изображении, формирующий служебную информацию для последующего хранения или поиска этой информации в Index, а также выполняющий индексирование и кластеризацию локализованных изображений.

Registration Machine - компонент для мониторинга и центрального управления. Bot (робот) - компонент системы, предназначенный для сбора изображений, их предварительной обработки и подготовки метаданных.

Бипр1еАР1 - веб-сервис, дополнительный уровень абстракции от структур данных, использующихся в процессе обработки изображений и метаданных. Это программный интерфейс для использования «тонкими» \УЕВ-клиентами.

Рис. 6 Компоненты системы

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

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

Заключение

В работе получены следующие основные результаты:

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

сравнению с существующими моделями распознавания образов и классификации.

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

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

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

5. Произведено внедрение разработанной распределенной системы индексации и поиска изображений в конструкторском подразделении на предприятии ООО «Эллипс».

Основное содержание диссертации опубликовано в работах:

1. Бояркин М.И. «Формирование интеллектуальных критериев в задачах кластеризации сложной графической информации»// Вестник СамГТУ, серия «Технические науки», №21 -2008, с. 178-180. ISSN 1991-8542

2. Бояркин М.И., Юдашкин A.A. «Исследование поведения динамической системы распознавания образов при спонтанном изменении конфигурации Р2Р-сети»// Вестник СамГТУ, серия «Технические науки», №20 - 2007, с.5-11. ISSN 1991-8542

3. Бояркин М.И., Данилушкин И.А., Колпащиков С.А., Миронов A.A., Рязанов A.C., Юдашкин A.A. «Возможности кластеризации сложной графической информации в соответствии с топологическими свойствами фазового иростран-

ства динамической системы распознавания образов»// Вестник СамГТУ, серия «Физико-математические науки», №15-2007, с. 202-204. ISSN 1991-8615

4. Бояркин М.И. «Статистический подход к настройке параметров нелинейных обыкновенных дифференциальных уравнений в задаче распознавания образов»// Вестник СамГТУ, серия «Математические науки», №45 - 2006, с. 63-70. ISBN 5-7964-0874-7

5. Бояркин М.И. «Практика использования пакета MATLAB при исследовании и синтезе систем и алгоритмов распознавания графических изображений»// Научное программное обеспечение в образовании и научных исследованиях: Труды VI научно-технической конференции. - Санкт-Петербург: Изд-во СПбГПУ, 2008, с. 157-160.

6. Бояркин М.И., Быченков К.В., Данилушкин И.А., Калинкин В.В., Кол-пащиков С.А., Масленников A.B., Юдашкин A.A. «Распределенная ассоциативная система обработки, индексации и поиска мультимедийной информации в Интернет»// Проблемы управления и моделирования в сложных системах: Труды X Международной конференции. - Самара: Институт проблем управления сложными системами РАН, 2008, с. 502-507.

7. Бояркин М.И. «Моделирование и анализ распознавания образов на основе искусственной нейронной сети»// Практика применения научного программного обеспечения в образовании и исследованиях: Труды V межвузовской конференции. - Санкт-Петербург: Изд-во СПбГПУ, 2007, с. 72-73.

8. Бояркин М.И., Юдашкин A.A. «Математическое моделирование и управление свойствами искусственной нейронной сети для достижения требуемых характеристик»//ХХХ1 Самарская областная научная конференция: Тезисы докладов. 4.1: Общественные, естественные и технические науки. - Самара: СамГТУ, 2005, с. 79.

9. Бояркин М.И., Юдашкин A.A. «Управление параметрами модели распознавания изображений на основе нейронной сети Хакена»// Математическое моделирование и краевые задачи: Труды II Всероссийской конференции. 4.2. -Самара: СамГТУ, 2005, с. 56-60.

Разрешено к печати диссертационным советом Д 212.217.03

протокол № 9 от 14 ноября 2008г. Формат 60x84 1/16. Усл. печ. л. 1. Тираж 100. Заказ № 770. ГОУ ВПО «Самарский государственный технический университет» Типография СамГТУ 443100, г. Самара, ул. Молодогвардейская, 244.

Введение.

1. Основные принципы применения методов кластерного анализа для обработки данных.

1.1 Основные методы теории кластерного анализа и их свойства.

1.2 Анализ oq3aHH4eHHfi на выбор элементов модели кластеризации.

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

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

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

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

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

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

- не существует заранее классифицированной обучающей выборки,

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

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

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

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

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

- исследование и анализ существующих методов кластерного анализа;

- обоснованный выбор моделей кластеризации многомерных векторов, в условиях растущего объема обрабатываемых данных;

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

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

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

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

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

В диссертации получены следующие основные научные результаты:

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

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

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

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

- разработан алгоритм индексации графической информации с учетом критерия визуального сходства изображений. Показана эффективность работы алгоритма индексации, выполняющего качественную классификацию графической информации со значительно меньшими затратами вычислительных ресурсов по сравнению с системами распознавания образов. Алгоритм использован в виде компонентов автоматизированной системы индексации и поиска графической информации; Реализация результатов работы. Результаты диссертационных исследований использованы при разработке автоматизированной системы индексации больших массивов графических данных с учетом критерия визуального сходства изображений с данными, поступающими в режиме реального времени, в конструкторском отделе промышленного предприятия ООО «Эллипс» (г. Самара), а также в учебном процессе подготовки магистрантов по направлению 22.00.00 «Автоматика и управление» в дисциплинах «Интеллектуальные технологии в системах управления» и «Системное моделирование» в ГОУ ВПО «Самарский государственный технический университет».

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на XXXI Самарской областной научной конференции (Самара, 2005); II Всероссийской научной конференции «Математическое моделирование и краевые задачи» (Самара, 2005); V Всероссийской межвузовской конференции «Практика применения научного программного обеспечения в образовании и исследованиях» (Санкт-Петербург, 2007); VI Всероссийской научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях» (Санкт-Петербург, 2008); X Международной конференции «Проблемы управления и моделирования в сложных системах» (Самара, 2008). Работа поддержана грантом РФФИ по проекту 07-08-00401-а.

Публикации. По теме диссертации опубликовано 9 печатных работ. Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 115 страницах машинописного текста, содержит 21 рисунок, 1 таблицу, список литературы из 80 наименований и 2 приложения.

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

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

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

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

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные результаты:

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

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

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

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

5. Произведено внедрение разработанной распределенной системы индексации и поиска изображений в конструкторском подразделении на предприятии ООО «Эллипс».

1. Бояркин, М.И. Исследование поведения динамической системы распознавания образов при спонтанном изменении конфигурации Р2Р-сети / М.И. Бояркин, А.А. Юдашкин // Вестник СамГТУ. Сер.: техн. науки. Самара: СамГТУ. 2007. - № 2(20). - С. 5-11.

2. Бояркин, М.И. Формирование интеллектуальных критериев в задачах кластеризации сложной графической информации / М.И. Бояркин // Вестник СамГТУ. Сер.: техн. науки. Самара: СамГТУ. 2008. - № 1(21). - С. 178-180. ISSN 1991-8542.

3. Лоскутов, А.Ю. Введение в синергетику / А.Ю. Лоскутов, А.С. Михайлов. -М.: Наука, 1990.-272 с.

4. Фаулер, М. Архитектура корпоративных программных приложений / М. Фаулер. М.: Издательский дом «Вильяме», 2007. - 544 с.

5. Юдашкин, А.А. Бифуркации стационарных решений в синергетической нейронной сети и управление распознаванием образов / А.А. Юдашкин //Автоматика и Телемеханика, 1996.-№ 11.- С. 139-147.

6. Anderberg, M.R. Cluster Analysis for Applications / M.R. Anderberg. -Academic Press, 1973.

7. Ball, G.H. A clustering technique for summarizing multivariate data / G.H. Ball, D.J. Hall // Behavioral Science. March 1967. - Vol. 12. - Pp. 153155.

8. Bezdek, J.C. A convergence theorem for the fuzzy Isodata clustering algorithms / J.C. Bezdek // IEEE Transactions on PAMI. 1980. - Vol. 2(1). -Pp. 1-8.

9. Boberg, J. General formulation and evaluation of agglomerative clustering methods with metric and non-metric distances / J. Boberg, T. Salakoski // Pattern Recognition. 1993. - Vol. 26(9). - Pp. 1395-1406.

10. Bobrowski, L. c-Means clustering with 11 and loo norms / L. Bobrowski, J.C. Bejdek // IEEE Transactions on Systems Man and Cybernetics. May/June 1991.-Vol. 21(3).-Pp. 545-554.

11. Brockett, P.L. Information theoretic analysis of questionnaire data / P.L. Brockett, P.D. Haaland, A. Levine // IEEE Transactions on Information Theory. 1981. - Vol. 27. - Pp. 438-445.

12. Calinski, R.B. A dendrite method for cluster analysis / R.B. Calinski, J. Harabasz // Communications in Statistics. 1974. - Vol. 3. - Pp. 1-27.

13. Carpenter, G.A. Adaptive Resonance Theory / G.A. Carpenter, S. Grossberg. MA: MIT Press, 2003. - 2nd ed. - Pp. 87-90.

14. Carpenter, G.A. ART2: Self-organization of stable category recognition codes for analog input patterns / G.A. Carpenter, S. Grossberg // Applied Optics. 1987. - Vol. 26. - Pp. 4919-4930.

15. Clarke, C. Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System / C. Clarke, G. Cormack // TechRep MT-95-01. University of Waterloo. 1995.

16. Dave, R.N. Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries / R.N. Dave // Pattern Recognition. 1992. - Vol. 25(7).- Pp. 713-721.(6)

17. Dave, R.N., Adaptive fuzzy c-shells clustering and detection of ellipses / R.N. Dave, K. Bhaswan // IEEE Transactions on Neural Networks. 1992. -Vol. 3(5). - Pp. 643-662. (a)

18. Deerwester, S. Indexing by Latent Semantic Analysis / S. Deerwester et al. // Journal of the American Society for Information Science. 1990. -Vol. 41(6).-Pp. 391^107.

19. Dixon, J.K. Pattern recognition with partly missing data / J.K. Dixon // IEEE Transactions on Systems Man and Cybernetics. 1979. - Vol. SMC 9. - Pp. 617-621.

20. Duda, R.O. Pattern Classification and Scene Analysis / R.O. Duda, P. Hart. John Wiley & Sons, 1973.

21. El-Gazzar, A. The taxonomy of Salvia: A test of two radically different numerical methods / A. El-Gazzar, L. Watson, W.T. Williams, G. Lance // J. Linn. Soc. (Bot.). 1968. - Vol. 60. - Pp. 237-250.

22. Everitt, B. Cluster Analysis / B. Everitt. Halsted Press, 1981. - 2nd ed.

23. Frigui, H. A comparison of fuzzy shell clustering methods for the detection of ellipses / H. Frigui, R. Krishnapuram // IEEE Transactions on Fuzzy Systems. May 1996. - Vol. 4(2).

24. Frigui, H. Clustering by competitive agglomeration / H. Frigui, R. Krishnapuram // Pattern Recognition. 1997. - Vol. 30(7). - Pp. 1109-1119.

25. Fu, L. Real-time adaptive clustering of flow cytometric data / L. Fu et al. // Pattern Recognition. 1993. - Vol. 26(2). - Pp. 365-373.

26. Fuchs, A. Pattern recognition and associative memory as dynamical processes in a synergetic system / A. Fuchs, H. Haken // Biol. Cybern. 1988. — Vol. 60, №. l.-Pp. 17-22.

27. Gersho, A. Vector Quantization and Signal Compression / A. Gersho, R.M. Gray. Kluwer Academic Publishers, 1992.

28. Goodall, D.W. A new similarity index based on probability / D.W. Goodall // Biometrics. 1966. - Vol. 22. - Pp. 882-907.

29. Gowda Chidananda, K. Divisive clustering of symbolic objects using the concepts of both similarity and dissimilarity / K. Gowda Chidananda, T.V. Ravi // Pattern Recognition. 1995. - Vol. 28(8). - Pp. 1277-1282.

30. Gower J.C. A general coefficient of similarity and some of its properties / J.C. Gower // Biometrics. 1971. - Vol. 27. - Pp. 857-872.

31. Gower, J.C. A comparison of some methods of cluster analysis / J.C. Gower // Biometrics. 1967. - Vol. 23. - Pp. 623-628.

32. Gray, R.M. Vector quantization / R.M. Gray // IEEE ASSP Magazine. -1984.-Vol. l.-pp. 4-29.

33. Haken H. Synergetic computers and cognition: A top-down approach to neural nets/H. Haken. Berlin: Springer-Verlag, 1991.

34. Hall, A.V. Methods for demonstrating resemblance in taxonomy and ecology / A.V. Hall // Nature. 1967. - Vol. 214. - Pp. 830-831.

35. Hopfield J. J. Neural networks and physical systems with emergant collective computation abilities // Proc. Natl. Acad. Sci. USA, 1982. Vol. 79. -P. 2554-2558.

36. Horn, B.K.P. Robot Vision / B.K.P. Horn. MIT Press, 1986.

37. Hubert, L.J. A general statistical framework for assessing categorical clustering in free recall / L.J. Hubert, J.R. Levin // Psychological Bulletin. -1976.-Vol. 83.-Pp. 1072-1080.

38. Jain, A.K. Algorithms for Clustering Data / A.K. Jain, R.C. Dubes // Prentice Hall, 1988.

39. Jain, A.K. Data clustering: a review / A.K. Jain, M.N. Murty, P.J. Flynn // ACM Computing Surveys. 1999. - Vol. 31(3). - Pp 264 - 323.

40. Johnson, S.C. Hierarchical clustering schemes / S.C. Johnson // Psycho-metrika. 1967. - Vol. 32. - Pp. 241-254.

41. Kanlcanhalli, M.S. Cluster-based color matching for image retrieval / M.S. ' Kanlcanhalli, B.M. Mehtre, J.K. Wu // Pattern Recognition. 1996. - Vol. 29(4).-Pp. 701-708.

42. Karen, D. Describing complicated objects by implicit polynomials / D. Karen, D. Cooper, J. Subrahmonia // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. - Vol. 16(1). - pp. 38-53.

43. Koutroumbas, K. Neural network architectures for selecting the maximum input / K. -Koutroumbas, N. Kalouptsidis // International Journal of Computer Mathematics. 1998. - Vol. 68(1-2).

44. Krishnapuram, R. A possibilistic approach to clustering / R. Krishnapuram, J.M. Keller // IEEE Transactions on Fuzzy Systems. 1993. - Vol. 1(2). -Pp. 98-110.

45. Krishnapuram, R. The possibilistic c-means algorithm: Insights and recommendations / R. Krishnapuram, J.M. Keller // IEEE Transaction on Fuzzy Systems. 1996. - Vol. 4(3). - Pp. 385-393.

46. Kurita, T. An efficient agglomerative clustering algorithm using a heap / T. Kurita // Pattern Recognition. 1991. - Vol. 24. - Pp. 205-209.

47. Lance, G.N. A general theory of classificatory sorting strategies II. Clustering systems / G.N. Lance, W.T. Williams // Computer Journal. 1967. — Vol. 10.-Pp. 271-277.

48. Li, X. Parallel algorithms for hierarchical clustering and cluster validity / X. Li // IEEE Transactions on Pattern Analysis and Machine Intelligence. -1990.-Vol. 12(11).-Pp. 1088-1092.

49. Li, X. The first stage in two-stage template matching / X. Li, R.C. Dubes // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1985. — Vol. 7.-Pp. 700-707.

50. Lippmann, R.P. An introduction to computing with neural nets / R.P. Lippmann // IEEE ASSP Magazine. 1987. - Vol. 4(2). - Pp. 4-22.

51. Lloyd, S.P. Least squares quantization in PCM / S.P. Lloyd // IEEE Transactions on Information Theory. 1982. - Vol. 28(2).

52. MacNaughton-Smith, P. Dissimilarity analysis / P. MacNaughton-Smith, W.T. Williams, M.B. Dale, L.G. Mockett // Nature. 1964. - Vol. 202. -Pp. 1034-1035.

53. MacQuenir, J.B. Some methods for classification and analysis of multivariate observations / J.B. MacQuenn // Proceedings of the Symposium on

54. Mathematical Statistics and Probability. 5th Berkeley. University of California Press. 1967. - Vol. 1. - Pp. 281-297.

55. McQuitty, 'L.L. Multiple hierarchical classification of institutions and persons with reference to union-management relations and psychological well-being / L.L. McQuitty //Educ. Psychol. Measur.- 1962.-Vol.23.- pp. 55-61.

56. Milligan, G.W. An examination of procedures for determining the number of clusters in a data set / G.W. Milligan, M.C. Cooper // Psychometrika. -1985.-Vol. 50(2).-Pp. 159-179.

57. Murtagh, F. Multidimensional clustering algorithms / F. Murtagh // COMPSTAT Lectures. Vienna: Physica-Verlag. 1985. - Vol. 4.

58. Murthy, M.N. Knowledge-based clustering scheme for collection, management and retrieval of library books / M.N. Murthy, A.K. Jain // Pattern Recognition. 1995. - Vol. 28(7). - Pp. 949-963.

59. Nikolaou, N. Color image retrieval using a fractal signature extraction technique / N. Nikolaou, N. Papamarkos // Engineering Applications of Artificial Intelligence. 2002. - Vol. 15. - Pp. 81-96.

60. Pritchard, N.M. Observations on the use of cluster analysis in botany with an ecological example / N.M. Pritchard, A.J.B. Anderson // J. Ecol. 1971. -Vol. 59.-pp. 727-747.

61. Sheals, J.G. An application of computer techniques to Acrine taxonomy: A preliminary examination with species of the Hypoaspio-Androlaelaps complex Acarina / J.G. Sheals // Proc. Linn. Soc. Lond.-l965.-Vol.176. pp. 11-21.

62. Sneath, P.H.A. Numerical Taxonomy / P.H.A. Sneath, R.R. Sokal. San Francisco: W.H. Freeman & Co, 1973.

63. Solomon, H. Numerical taxonomy in Mathematics in the Archaeological and Historical Sciences / H. Solomon et al.. University Press, 1971.

64. Spath, H. Cluster Analysis Algorithms / Ii. Spath. Ellis Horwood, 1980.

65. Tanimoto, T. An elementary mathematical theoiy of classification and prediction / Т.-Tanimoto. Int. Rpt., IBM Corp., 1958.

66. Theodoridis, S. Pattern recognition / S. Theodoridis, K. Koutroumbas. Elsevier, 2003. - 2nd ed. -707 p.

67. Trahanias, P. An efficient sequential clustering method / P. Trahanias, E. Scordalakis // Pattern Recognition. 1989. - Vol. 22(4). - Pp. 449-453.

68. Viola, P. Object Detection using a Boosted Cascade of Simple Features / P. Viola, M. J. Jones // IEEE CVPR. 2001.

69. Wallace, C.S. An information measure for classification / C.S. Wallace, D.M. Boulton // Computer Journal. 1968. - Vol. 11. - Pp. 185-194.

70. Ward, J.IT. Plierarchical grouping to optimize an objective function / J.H. Ward // Journal of the American Statistical Association. 1963. - Vol. 58. — pp. 236-244.

71. Zadeh, L.A. Fuzzy sets / L.A. Zadeh // Information and Control. 1965. -Vol. 8.-Pp. 338-353.