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

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

ТАРАСОВА Алина Сергеевна

ииз163424

МОДЕЛИРОВАНИЕ ОБОБЩЕННЫХ ПРОЦЕДУР КЛАСТЕРИЗАЦИИ И АНАЛИЗ ДАННЫХ СЛОЖНОЙ СТРУКТУРЫ

Специальности 05 13 18 - Математическое моделирование, численные методы и комплексы программ 05 13 01 - Системный анализ, упраатение и обработка информации

АВТОРЕФЕРАТ

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

2 '» ЯНВ 2003

Воронеж-2007

003163424

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

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

доктор технических наук, профессор Леденева Татьяна Михайловна

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

Буховец Алексей Георгиевич

кандидат физико-математических наук, доцент

Гудовнч Ирина Семеновна

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

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

Защита состоится «17» января 2008 г в 10 часов в конференц-зале на заседании диссертационного совета Д 212 037 01 Воронежского государственного технического университета по адресу 394026, г Воронеж, Московский пр, 14

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

Автореферат разослан «/^>> декабря 2007 г

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

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

Питолин В М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы Как известно, кластерный анализ предназначен дтя разбиения множества объектов на заданное или неизвестное число кластеров на основании некоторого математического критерия качества кластеризации Процедуры кластерного анализа используются как на стадии предварительной обработки информации при решении задач управления, прогнозирования, принятия решений, позволяя решить проблемы сокращения размерности, структуризации и выявления скрытых закономерностей в имеющейся информации, так и имеют самостоятельное значение (упорядоченная и in неупорядоченная кластеризация объектов заданного множества) Алгоритмы кластеризации достаточно полно и подробно рассмотрены в литературе и отличаются большим разнообразием, которое обусловлено доступной исходной информацией, особенностями критерия качества кластеризации и его формализацией, выбором метрики, отражающей схожесть объектов, нацеленностью на определенную структуру группировок объектов и др В связи с этим возникает необходимость сравнения результатов кластеризации, полученной с помощью различных алгоритмов, и выявления такого алгоритма, который в наибольшей степени учитывает специфику данных Важно, что при этом одно и то же (или почти одно и то же) классификационное разбиение может быть результатом нескольких процедур, поэтому актуальным является исследование существующих взаимосвязей между подходами к кластеризации и моделирование основных компонент процедуры кластеризации с тем, чтобы разбиение данных было нацелено на получение кластеров с определенными свойствами Вопросы, касающиеся формирования кластеров с заранее заданными свойствами, рассматривались А Д Гвишиани, С M Агаяном, Ш Р Богоутдиновым Один из путей усовершенствования известных процедур кластерного анализа - их обобщение на «нечеткий» случай Вопросами разработки нечетких алгоритмов кластеризации занимались J Bezdek, Е Gustafson, W Kessel, I Gath, A В Geva, U Kaymak, R Babuska

Многие алгоритмы кластеризации позволяют формировать кластеры определенной геометрической формы Навязывание данным неприсущей им структуры приводит не только к неоптимальным, но иногда и к принципиально неверным результатам Вопросами, касающимися форм кластеров, занимались Е Gustafson, W Kessel, D -W Kim, R Babuska Проблема учета геометрической формы кластеров при анализе данных требует детального исследования, а разработка методов кластеризации, которые реконструируют форму кластера в процессе его нахождения, позволит повысить адекватность моделей и методов кластерного анализа

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

Воронежского государственного университета по направлению «Анализ и математическое моделирование сложных систем»

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

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

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

2 Разработка обобщенного подхода к построению процедур кластеризации

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

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

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

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

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

• модификация схемы «Обобщенный Роден», отличающаяся введением нечеткой процедуры высекания и позволяющая сформировать нечеткие классификационные разбиения,

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

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

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

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

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

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

Реализация результатов работы. Результаты диссертационной работы в форме моделей, алгоритмов и программ используются в учебном процессе Воронежского государственного университета Кроме того, программный комплекс КЛАССМОД использовался для кластеризации данных о рейтингах банков и изменении курса евро - доллар в ООО «Воронежская инвестиционная палата», ООО «Стройэнергомонтаж-Воронеж», а также для формирования групп клиентов компании ООО «М-Бит»

Апробация работы Основные научные результаты диссертации докладывались и обсуждались на УП Всероссийской научной конференции с международным участием «Новые информационные технологии Разработка и аспекты применения» (Таганрог, 2004 г.), IX Международной научной конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2005 г), XVIII Международной научной конференции «Математические методы в технике и технологиях - ММТТ-18» (Казань, 2005 г), Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2006 г), Международной научной конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2006 г), Второй научной школе-семинаре по

проблемам управления большими системами (Воронеж, 2007 г), а также на научных семинарах Воронежского госуниверситета

Публикации По результатам исследований опубликовано 11 научных работ, в том числе одна в издании, рекомендованном ВАК РФ В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежит в [4] - новый подход к кластеризации, основанный на выделении кластеров с заранее заданными свойствами, в [5] - алгоритм получения кластеров с линейной зависимостью, в [6] - алгоритм «FCM-Роден», в [9] - описание методов кластеризации, реализованных в среде MATLAB

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, списка литературы из 121 наименования и 6 приложений на 11 страницах Основная часть работы изложена на 148 страницах, содержит 70 рисунков и 25 таблиц

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной работы, сформулированы цели и задачи исследования, определены научная новизна и практическая значимость результатов работы

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

Во второй главе разрабатывается обобщенный подход к кластеризации на основе схемы «Обобщенный Роден» (рис 1)

Рис 1 Схема алгоритма «Обобщенный Роден»

Пусть , , £т} - упорядоченная совокупность критериев качества классификационного разбиения, а,, а2, , ат - соответствующие пороговые значения качества, которые предполагается достичь в процессе разбиения множества X на кластеры Требуется в X построить кластер К, удовлетворяющий всем ограничениям вида Б,(К)>а1, 1 = 1,от Кластер находится на основе принципа высекания «слабейшего» с точки зрения данного качества объекта Достоинство схемы «Обобщенный Роден» заключается в том, что полученные по этой схеме классификационные разбиения содержат информацию о качестве кластеров, а значит, становится возможным сравнение результатов кластеризации по качеству, а также описание классов и распознавание новых объектов на основе используемых критериев качества Схема «Обобщенный Роден» позволяет встраивать «новые качества» в алгоритм кластеризации и, следовательно, получать разбиения, обладающие дополнительными свойствами Основная идея предложенного нами обобщенного подхода к кластеризации состоит в том, что для получения классификационных разбиений, эффективных с точки зрения какого-либо алгоритма кластеризации, необходимо внести соответствующие критерии качества в схему «Обобщенный Роден» и разработать стратегии высекания для достижения заданных порогов качества, при этом алгоритм разбиения данных на кластеры остается неизменным Это позволит, с одной стороны, унифицировать схему кластеризации, а с другой - наделить классификационные разбиения достоинствами схемы «Обобщенный Роден»

В рамках идеи изложенного выше подхода нами предложены модели процедур кластеризации известных алгоритмов «Форель» и «КРАБ» Их выбор обусловлен возможностью выделить качества кластеров, построенных по данным алгоритмам, а значит возможностью применить схему «Обобщенный Роден» для разработки процедур кластеризации, эффективных с точки зрения данных алгоритмов Принадлежность «Форель» и «КРАБ» к различным классам алгоритмов кластеризации подтверждает универсальность схемы «Обобщенный Роден»

Рассмотрим основную идею алгоритма «Форель-Роден 1» Алгоритмы семейства «Форель» продуцируют кластеры в форме гиперсфер заданного

радиуса, центр которых расположен в центре тяжести кластера Качество кластеризации, полученной с помощью «Форель», оценивается по критерию

к |1»| / \

А=1 у=1

где сА - центр гиперсферы А, х^ - объект гиперсферы А, - кластер А, \ЬИ\ -

количество объектов в кластере А, который характеризует меру внутренней связи в кластерах

Так как «Обобщенный Роден» выделяет кластеры последовательно, один за другим, то для оценки качества отдельного кластера предлагается использовать величину

! Ш

Р(Ьн) = -Г^(хь ск), (2)

¿Л 7=1

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

Утверждение 1 (стратегия высекания) Для того чтобы улучшить качество кластера, необходимо высечь точку хт такую, что ¿(хт,ск)>Р(Ьк)

Утверждение 2 Качество кластера улучшится, если центр кластера перенести в центр тяжести нового множества, получившегося после высекания хт

Идея алгоритма «Форель-Роден 2» состоит в следующем При формировании очередной гиперсферы не рассматриваются объекты, уже отнесенные к сформированным ранее гиперсферам Определим множество элементов, которые были распределены в некоторую гиперсферу Б1 с центром с , но оказались ближе к центру новой гиперсферы 51+1 в виде

М'+1={х:е5Л7=ГГ й(х,с,+1 )<гп1лй(х,с^)< ¿(х,су(3) В диссертационной работе доказаны следующие утверждения Утверждение 3 Если присоединить элементы из множества М'+ к текущей гиперсфере 5'+1, то значение критерия Fуменьшится, т е качество классификационного разбиения улучшится

Утверждение 4 Если присоединить элементы из множества М'+1 к текущей гиперсфере, то классификационное разбиение станет более равномерным

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

Роден 1» продуцирует классификационные разбиения, содержащие кластеры различной геометрической формы В табл 1 представлены результаты сравнения классификационных разбиений по алгоритмам «Форель» и «Форель-Роден 1», «Форель-Роден 2» и «Форель» (данные 25 инвестиционных компаний по 4 признакам) с помощью разработанной нами методики

Т а б т и ц а 1

Сравнение алгоритмов «Форгчь», сФоре1ь-Ро0сл 1»и «Фор\ль-Ро0сн 2»

Критерии Форсль/Форсль-Роген 1 Форель-Роден 2 Форель

Среднее расстояние между кластерами 0 7143 1 001Д

Среднее расстояние межд> центрами классов 07143 1 оооо

Расстояние ближайшего соседа 1 6667 0 6667

Мера равномерности 2 0000 9 Гл00

Мера внутренней связи в кластерах 2 0000 2 3333

Итого 1 2о42 1 5и00

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

1 1>А и

Яи= — V (4)

где а\' - длина 1-го ребра кластера И, 1А - число элементов кластера И,

- критерий неоднородности на границах кластеров,

Ри,сВп а,

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

- критерий удаленности кластеров

^=-¿-1«, (6)

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

Утверждение 5 Если ребро удовлетворяет ограничению ат > Л/,, то его высекание приведет к уменьшению меры внутренней связи хотя бы в одной из образовавшихся компонент связности

Есчи а„ - длина максимального ребра и существует хотя бы одно ребро с меньшей длиной, ю ат(1^ - \)> а , а следовательно ат >ЛА На основе

данного утверждения предложены две стратегии высекания для улучшения меры внутренней свят

]) если высекать граничное ребро такое, что ат > К/,, то мера внутренней связи в кластере /; уменьшится (подходит только для неравномерных множеств),

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

В основу алгоритма «КРАБ-Роден 1» была положена первая стратегия, в основу «КРАБ-Роден 2» - вторая стратегия

Нами предложено следующее правило высекания для угучшения меры

чокалыюй неоднородности Пусть

СоЛ/

а -О* -

где в,

оШ

Спеи1 Л

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

1)Л#СЛ>0, 2) а„= оцтах ПАС,,, (7)

где ат - высекаемое ребро

=

Ртш«)

I (8)

а' а'еАф(а,)

где Б, - количество ребер, смежных с а,, Аф(а,) - множество ребер, смежных с а.

Если V«, е В/, (5, = 1), то

=

а, а'

(9)

Нами предложено следующее правило высекания для меры удаленности

-д

оШ

где

ЯГ

значение меры

кластеров пусть = И™

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

1) Л//®,, >0, 2) ат =аг§тах/Э402)А, где ап - высекаемое ребро

«,<=ЯА

»Фъ= I -(5,(ю)

Если У а, е (5, = 1), то

£»№=(«;-«,) (11) Результаты экспериментов показали, что кластеры, полученные с помощью «КРАБ-Роден 2», обладают ботее сильной внутренней связью, чем кластеры в разбиении «КРАБ-Роден 1» Классификационное разбиение, полученное с помощью «КРАБ-Роден 1», лучше разбиения «КРАЬ-Роден 2» по мере локальной неоднородности и мере отделимости

Аналогичным образом нами был разработан нечеткий алгоритм кластеризации «БСМ-Роден», который является расширением схемы «Обобщенный Роден» для получения нечетких классификационных разбиении Процедура высекания, состоящая в исключении объекта из рассмотрения, заменена нечеткой процедурой высекания, которая заключается в уменьшении степени принадлежности объекта к кластеру на основе одной из стедующих функций высекания

1 )мГ(хт.1) = мтт <1пзхЕКхп,1), (12)

1 *

гДе <*тах = ~тахО(х1,х]), В(х„х] ) = ^¿(х^х*), 1 1<> ¿=1

</(**,**; = -х)) {хктах-хкт,п), цтт - минимальная степень

принадлежности объекта к классу, которая назначается объекту, если расстояние от него до центра кластера равно с/тах,

2) О3)

а

где а > 1 задается экспертным путем и отвечает за скорость изменения весов признаков

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

данному признаку вычисляется по формуле ^ (х1 ,х* ) = \х'к - т/ | (х™" - д:™"1), тогда меру удаленности между объектами с учетом весов признаков определим в виде

¿(х,у)='Ц»к<1к(х,у), (14)

/ К _

где = \»к / Х™* > > к = ГТ В предположении, что каждый признак в / к=\

различной степени влияет на кластеризацию, найдем эту меру влияния Каждому классу поставим в соответствие функцию

Р<,(*)= (15)

которая является мерой принадлежности объекта х к классу с номером ц, В(х,Ьп) = ^ ^с1(х,у)-среднее расстояние от объекта до кластера т

I ¿т I 1С/,

Пусгь классификационное разбиение содержит М классов В каждом классе критерием качества является ря(х) - мера принадлежности объекта к

класс} Заладим порог е для качества Необходимо получить такие веса

признаков н'= ^н,, , ), чтобы V* е Ьц [рч(х) > е), ц = \,М

В диссертации сформулированы и доказаны следующие утверждения Утверждение 6 (стратегия высекания) Если преобразовать вес

признака к0 такого, что к0 = a/gwí/!í/t(х,у0), где >'0 = а^ттс1Сх,у()), по

1с~ 1 К

<\) ^ » - (\)реэ

правгт , = , где а> 1, то нормированный вес этого признака щ

^ а

уменьшится а нормированные веса остальных признаков кфкп,

_> ветчатся

Утверждение 7 (усювие применения стратегии высекания) Если мера удаленности между объектами х и у0 равна по всем признакам, т е

с!к (х,у0) = (х,у0 ) к = 1,К, то применение процедуры высекания не приведет к изменению меры удаленности .между объектами

Утверждение 8 Есчи расстояния .между соответствующими объектами (х,у0) не равны по всем признакам, то после про11едуры высекания на первой итерации алгоритма мера удаленности объектов из двух соответствующих кластеровувечичится (х,у0)> (х,у0 )

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

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

Пусть известно классификационное разбиение ,

А, - | х б X х - х, р < г, р | - гиперсфера, покрывающая часть класса 5,,

-х, р - один из центров плотности класса Б,, г: - специально подобранный ради\с гиперсферы, - евклидово расстояние Разобьем процесс описания

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

Для выявления центров плотности кластеров был применен способ, предложенный в методе разностной кластеризации Каждому объекту поставим в соответствие потенциал становления его центром класса

где х, — ооъект, а -

положительная константа

V

В качестве первого центра класса выбираем объект с наибольшим потенциалом Затем потенциал каждого объекта в группе изменяется по правилу Vr^ е А

|рnew = о] Далее выбирается объект с наибольшим потенциалом из оставшихся и объявляется вторым центром класса Процесс продолжается до тех пор, пока не выполнится устовие Р^ < (ЗР\ . где Р1 - потенциал первого центра класса, Р е (0,1)

Пусть х — один из центров плотности класса S, Если объект х близок

к х, , то х принадлежит классу S, со степенью принадлежности в 2

р -а х-х, '

Ms,(x) = e

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

С \

хеА,х или. или

V V

xeA,Pi \то xeS,

(16)

Данное высказывание будем называть есчи-то правилом Заметим, что

р,

функция принадлежности объекта д: к классу 5, есть /л

р=1

Пусть К, р - количество объектов, содержащихся в гиперсфере А1 Зададим критерий точности для гиперсферы А, р в виде

Т = — К,

Z

хеА, р \х:cS,

tcS, xeS.

(17)

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

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

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

1 :1 ч " .

' : I I ; < ' '

Рис. 2. Радиус гиперсфер велик рис 3_ Результат работы

для некоторых классов алгоритма

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

используемой для измерения расстояния между объектами. Пусть х1 -

объект, ] = !,/■/, с' - центр класса, 1 = 1,С, /2у - степень принадлежности

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

Матрица квадратичной формы В при К = 2 задает кривую второго

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

Модель 1: Р(З^В,) = X ^^'(х*,с'$-+тт. (19)

{¡:]=Щлм„>0.5}

Модель 2

I ичйв(х>,с')-{/у=1 Л',,я >0 5)

(20)

ух, {/ у = 1,ЛГл^>05} [й\(х>,с')> о)

Предложенный алгоритм был реализован в среде МАТЬАВ Для тестирования использовались данные о колебании курса евро - доллар за сто дней по трем признакам Результаты экспериментов (рис 4, 5) показали, что алгоритм, основанный на модели 1, позволяет описывать классы с помощью эллипсов, прямых и гипербол Получение матриц квадратичной формы определяющих гиперболы, обусловлено отсутствием ограничения на неотрицательность функции ¿^(х1,с') Алгоритм, основанный на модели 2 позволяет описывать классы с помощью эллипсов и прямых

Рис 4 Результаты работы метода для Рис 5 Результаты работы мегода для

модели 1 в плоскости признаков 1, 3 модели 2 в плоскости признаков 1, 2

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

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

Пусть в каждом кластере г = 1,С данные описываются с помощью зависимости у = /, (г, в,) + £,, где в, - параметр уравнения для кластера г, е[ -ошибка аппроксимации для кластера г, распределенная по закону

Пусть (у,б,))2 характеризует ошибку аппроксимации для

объекта х} в кластере ; Необходимо в каждом кластере определить такие значения параметров в,, чтобы критерий качества кластеризации

Е,Ю=^и9Ед{в,)<6, (21)

П

где 5 > 0 - допустимый порог ошибки Заметим, что если fJ (х, 01) линейны по параметрам 0,, то параметры могут быть получены методом наименьших квадратов

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

т„ =аг8тах{{1ие™), (22)

7=1 п

изменяя его степень принадлежности по правиту и"™ =(р[и°и£где р(г) -убывающая функция Нами предложено три вида функции <р

/ / \N

1)^(0=

mm

Итт\ паху -тту

old _ \J=J=in

ЩJ , t

(23)

где итт - значение степени принадлежности элемента к кластеру, если ошибка

составляет величину, равную max у - тту.

,7=1 л 7=1 п 1

2)«ь(0 = г г""', (24) t-a

где z =-, где а - среднее значение, а - разорос,

I и \

3) пусть итах - максимальная степень принадлежности элемента к кластеру, при которой элемент «не принадлежит» кластеру (высечен), тогда функцию принадлежности определим в виде

.old Um

сръ{{)=тт\и°и,^ (25)

К основным свойствам данной функции относятся

а) 9ъ(})<тт{и^,итах),

б) <р3 (г) стремится слева к итах при / —> 0

Результаты экспериментов (рис 6, 7, табл 2, 3, тестовые данные 60 объектов, 2 признака) показали, что применение этого метода позволяет строить кусочно-линейную зависимость в данных на основе специальным образом введенных фиктивных переменных Построенная на основе

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

Таблица2

Поиск линейной зависимости до применения кластеризациоино-регрессионного метода

Характеристики построенного уравнения у = ах + с а с

Значения коэффициентов в уравнении 0 66 -0 23

Среднеквадратическая ошибка для коэффициентов 0 09 0 08

Коэффициент детерминации 0 47

Среднеквадратическая ошибка для у 0 23

ТаблицаЗ

Поиск линейной зависимости с использованием результатов кластеризации

Характеристики построенного уравнения у = а ,х' + арг + с, где х1, д^ - фиктивные переменные а2 «1 с

Значения коэффициентов в уравнении 064 0 10 -0 004

Среднеквадратическая ошибка для коэффициентов 004 0 05 004

Коэффициент детерминации 091

Среднеквадратическая ошибка для у 0 10

о

Т ■

I

- - « ■ I

V

о

г

1 я

Ч а

хппсР ргтттт ЩШ ЮЕР □ ^

Рис 6 Данные, состоящих из двух струетур с линейной зависимостью

Рис 7 Результаты кластеризационно-регрессионного алгоритма

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

Также в четвертой главе описан программный комплекс КЛАССМОД, разработанный на основе предложенных в диссертации модельных решений и

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

Разработанные нами модели и методы были применены для решения ряда практических задач Внедрение программного комплекса КЛАССМОД для формирования групп клиентов компании ООО «М-Бит» и разработки стратегий работы с ними позволило оценить перспективы работы с клиентами фирмы и ((отсечь» ненадежных клиентов, что в конечном итоге ведет к уменьшению дебиторской задолженности, а следовательно, уменьшению времени ее оборота, оказывая положительное влияние на показатели ликвидности Программный комплекс КЛАССМОД также был использован для анализа рейтингов банков и изменения курса евро - доллар в ООО «Воронежская инвестиционная палата» и ООО «Стройэнергомонтаж-Воронеж» Внедрение данного программного комплекса позволило оценить положение банков на рынке банковских услуг, а также валютный риск для корректировки показателей устойчивости компаний и определения наиболее выгодных способов инвестирования

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

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

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

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

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

визуализации результатов в виде кривых второго порядка для каждой пары признаков

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

6 Разработан в среде Delphi 6 программный комплекс КЛАССМОД, позволяющий производить анализ данных предложенными методами и оценивать результаты с помощью визуализации данных, отчетов в графическом и текстовом виде

7 Результаты диссертационной работы применяются в учебном процессе, прошли успешную проверку при решении ряда практических задач, связанных с анализом данных об инвестиционных компаниях, рейтинге банков, колебании курсов валют евро - доллар, а также внедрены и используются в компаниях ООО «М-Бит», ООО «Воронежская инвестиционная палата» и ООО «Стройэнергомонтаж-Воронеж»

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

Публикации в изданиях, рекомендованных в ВАК РФ

1 Тарасова А С Методы определения оптимальной геометрической формы в задачах кластерного анализа /АС Тарасова // Информационные технологии - 2007 - №11 - С 14-21

Статьи и материалы конфереций

2 Тарасова А С Модификация алгоритма кластеризации С-средних на основе использования объемных прототипов и слияния схожих кластеров /АС Тарасова // Вестник ВГУ Серия «Системный анализ и информационные технологии» - Воронеж Изд-во ВГУ, 2007 - № 1 - С 68-74

3 Тарасова А С К вопросу об обобщенном алгоритме классификации /АС Тарасова // Моделирование сложных систем Современные направления теории и практические приложения Материалы Междунар школы - семинара «Современные проблемы механики и прикладной математики» -Воронеж Изд-во ВГУ, 2004 - С 136-140

4 Тарасова А С Оценка качества и сравнительный анализ классификаций /АС Тарасова, Т М Леденева // Новые информационные технологии Разработка и аспекты применения Труды VII Всероссийской науч конф с международным участием - Таганрог ПБЮЛ В А Кравцов, 2004 - С 249-252

5 Тарасова А С Построение и реализация классификационно-регрессионных нечетких алгоритмов на основе схемы «Роден» /АС Тарасова, Т М Леденева // Системный анализ в проектировании и управлении Труды IX Междунар науч конф - СПб Изд-во Политехнического университета, 2005 - С 364-370

6 Тарасова А С Разработка нечетких алгоритмов классификации на основе схемы «Роден» /АС Тарасова, Т М Леденева // Математические

методы в технике и технологиях - ММТТ-18 Том 6 Секции 6, 8 - Казань Изд-во Казанского государственного технологического университета, 2005 -С 51-55

7 Тарасова А С Об одном методе распознавания данных /АС Тарасова // Современные проблемы прикладной математики и математического моделирования - Воронеж Изд-во ВГУ, 2006 - С 217 — 218

8 Тарасова А С Об одном методе распознавания данных на основе если-то правил /АС Тарасова // Системный анализ в проектировании и управлении Труды X Междунар науч конф - СПб Изд-во Политехнического университета, 2006 - С 238-242

9 Леденева Т М Основы нечеткого моделирования в среде MATLAB / , А С Тарасова, Д С Татаркин // Воронеж Издательско-полиграфический центр ВГУ, 2006 - 52 с

10 Тарасова А С Адаптивные если-то правила /АС Тарасова // Вестник факультета прикладной математики и механики -Воронеж Изд-во ВГУ, 2007,Вып 6 -С 169-181

11 Тарасова А С Индексы сходства и включения Использование в задачах кластерного анализа /АС Тарасова // Управление большими системами Труды второй науч школы-семинара - М ИГГУ РАН, 2007. - С 42-47

Подписано в печать 12 12 07 Формат 60x84 '/и Уел печ л 1 2 Тираж 100 ж! Заказ2641

Отеча1ано с готового оригинала-макета в типографии Издагельско-по шграфического исигра Воронежского государственного университета Я94000 Воронок у л Пушкинская Я

ВВЕДЕНИЕ.

ГЛАВу^ 1. АНАЛИЗ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧИ КЛАСТЕРИЗАЦИИ И РАСПОЗНАВАНИЯ ДАННЫХ.

1.1. Кластерный анализ.

1.1.1. Постановка задачи кластеризации.

1.1.2; Этапы решения задачи кластеризации.

1.1.3.Сравнительный анализ подходов к решению задачи кластеризации .23.

1.2. Распознавание данных.

1.2.1. Постановка задачи распознавания.

1.2.2. Виды систем распознавания.

1.2.3. Модели для решения задач распознавания.36.

1.2.4: Нечеткие методы распознавания, основанные на продукционных правилах.

1.3s. Цель и задачи исследования.41*

Выводы к первой главе.

ГЛАВА 2. РАЗРАБОТКА МЕТОДОВ КЛАСТЕРИЗАЦИИ НА ОСНОВЕ

СХЕМЫ АЛГОРИТМА «ОБОБЩЕННЫЙ РОДЕН».

2:1. Алгоритм Роден.

2:2. Разработка алгоритмов, эффективных с точки зрения алгоритма «Форель» на основе схемы-алгоритма «Обобщенный Роден».

2.3. Разработка алгоритмов кластеризации,. эффективных с точки зрения алгоритма «КРАБ».

2.4. Разработка нечетких алгоритмов кластеризации. на основе схемы алгоритма «Роден».

Выводы ко второй главе.

ГЛАВА 3. РАЗРАБОТКА МЕТОДОВ ОПИСАНИЯ КЛАССОВ И

РАСПОЗНАВАНИЯ НОВЫХ ОБЪЕКТОВ.

3.1. Распознавание новых объектов на основе подбора весов признаков для классификационного разбиения.

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

3.3. Методы определения геометрической формы кластеров.

3:4. Построение и реализация кластеризационно-регрессионных нечетких алгоритмов на основе схемы алгоритма «Обобщенный Роден».

Выводы к третьей главе.

ГЛАВА 4. РЕАЛИЗАЦИЯ ПРЕДЛОЖЕННЫХ МЕТОДОВ И АНАЛИЗ

ВЫЧИСЛИТЕЛЬНОЙ ЭКСПЕРТИЗЫ.

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

4.2. Описание программного комплекса КЛАССМОД, реализующего предложенные методы.

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

4.4. Результаты практической апробации разработанных алгоритмов кластеризации и распознавания новых объектов на примере анализа данных о клиентах компании ООО «М-Бит».

Выводы к главе 4.

ТСак известно, кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число кластеров на основании некоторого математического критерия качества кластеризации. Процедуры кластерного анализа используются как на стадии предварительной обработки информации при решении задач управления, прогнозирования, принятия решений, позволяя решить проблемы сокращения размерности, структуризации и выявления скрытых закономерностей в имеющейся информации, так- и имеют самостоятельное значение (упорядоченная или неупорядоченная кластеризация объектов заданного множества). Алгоритмы кластеризации достаточно полно и подробно рассмотрены в литературе и отличаются большим разнообразием, которое обусловлено доступной исходной информацией; особенностями критерия качества кластеризации, и его формализацией; выбором метрики, отражающей схожесть объектов; нацеленностью на определенную структуру группировок объектов и др. В связи с этим возникает необходимость сравнения результатов кластеризации, полученной с помощью различных алгоритмов, и выявление такого алгоритма, который в наибольшей степени учитывает специфику данных. Важно, что при этом одно и то же (или почти одно и то же) классификационное разбиение может быть результатом нескольких процедур, поэтому актуальным является исследование существующих взаимосвязей между подходами к кластеризации и моделирования основных компонент процедуры кластеризации с тем, чтобы разбиение данных было нацелено на получение кластеров с определенными свойствами. Вопросы, касающиеся получения, кластеров с заранее заданными качествами, разрабатывались А.Д. Гвишиани, С.М. Агаяном, Ш.Р. Богоутдиновым. Важнейшим фактором, влияющим на выбор алгоритма, является неопределенность. Один из путей усовершенствования1 известных процедур кластерного анализа - их обобщение на «нечеткий» случай, Вопросами разработки нечетких алгоритмов кластеризации занимались J. Bezdek, Е. Gustafson, W. Kessel, I. Gath,. A. B. Geva, U. Kaymak, R. Babuska.

Многие алгоритмы кластеризации позволяют формировать кластеры определенной геометрической формы. Например, алгоритм С-средних (J. Bezdek) позволяет формировать кластеры в форме гиперсфер. Навязывание данным неприсущей им структуры приводит не только к неоптимальным, но иногда и к принципиально неверным результатам. Поэтому появились методы кластеризации, позволяющие извлекать кластеры различной геометрической формы. Е. Gustafson и W. Kessel разработали метод, позволяющий- выделять кластеры в форме гиперэллипсоидов. Вопросы, касающиеся форм кластеров, разрабатывал D.-W. Kim. R. Babuska разработал методы аппроксимации функций с помощью если-то правил эллипсоидальной формы. Проблема учета геометрической формы кластеров при анализе данных требует детального исследования, а разработка методов кластеризации, которые реконструируют форму кластера в процессе его нахождения, позволит повысить адекватность моделей и методов кластерного анализа.

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

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

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

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

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

2. Разработка обобщенного подхода к кластеризации.

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

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

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

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

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

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

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

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

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

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

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

Результаты внедрения. Результаты диссертационной работы в форме моделей, алгоритмов и программ используются в учебном процессе Воронежского государственного университета и Воронежского государственного технического университета при чтении спецкурсов и для проведения лабораторных занятий. Кроме того, программа КЛАССМОД использовалась для кластерного анализа данных о рейтингах банков, о рейтинге инвестиционных компаний, о колебании курсов валют, для формирования групп клиентов компании ООО «М-Бит».

Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на VII Всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004г.); IX Международной научной конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2005г.); XVIII Международной научной конференции «Математические методы в технике и технологиях - ММТТ-18» (Казань, 2005г.); Международной научной конференции «Современные проблемы прикладной математики и математического моделирования», (Воронеж, 2006г.); Международной научной конференции «Системный , анализ в проектировании и управлении», (Санкт-Петербург, 2006г.), Второй научной школы-семинара по проблемам управления большими системами (Воронеж, 2007 г.), а также на научных семинарах Воронежского госуниверситета.

Публикации. По результатам исследований опубликовано 11 научных работ, в том числе 2 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, и приведенных в конце автореферата, лично соискателю принадлежит: в [35] — описание методов кластеризации, реализованных в среде MATLAB, в [56]~новый подход к кластеризации, основанный на выделении кластеров с заранее заданными свойствами, в [57] -основанная идея и алгоритм получения кластеров с линейной зависимостью, [58]-алгоритм «FCM-Роден».

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 121 наименования и 6 приложений на 11 страницах. Основная часть работы изложена на 148 страницах, содержит 70 рисунков и 25 таблиц.

Выводы к главе 4

I. Произведено сравнение алгоритмов «Форель», ФР1, ФР2. Для этого разработаны системы критериев качества для оценки разбиений на кластеры и предложен метод сравнения алгоритмов кластеризации. Данный метод может служить решающим правилом для выбора алгоритма кластеризации, который следует применять к конкретным данным.

Эксперименты показали, что в целом алгоритм «Форель» выдает более качественные разбиения, чем ФР1, а алгоритм ФР2 превосходит «Форель» на небольшую величину по качеству;

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

3. Разработаны структуры данных для эффективного хранения компонентов моделей в памяти и манипулирования списками элементов и параметрами моделей в оперативной памяти ЭВМ;

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

ЗАКЛЮЧЕНИЕ

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

1. В рамках доказательства универсальности схемы алгоритма Обобщенный Роден разработаны алгоритмы: a) «Форель-Роден» (2 схемы, первая схема позволяет строить классификационные разбиения, эффективные с точки зрения критерия качества алгоритма «Форель», вторая схема позволяет строить классификационные разбиения с улучшенным качеством и повышенной равномерностью классов) b) «КРАБ-Роден» (разработано 2 схемы. Первая подходит только для неравномерных множеств, у которых есть один большой класс объектов, а остальные точки «фоновые». Вторая ведет к увеличению равномерности. Такой метод подходит как для равномерных, так и для неравномерных множеств), с) Нечеткий алгоритм «FCM-Роден». Предложено два вида степени принадлежности, изучено влияние управляющего параметра на сходимость метода и степень нечеткости классификационного разбиения, а также предложен способ комплексной оценки нечеткого классификационного разбиения.

2. Разработаны следующие алгоритмы описания кластеров и распознавания новых объектов: a) Предложен алгоритм распознавания новых объектов на основе подбора весов признаков для классификационного разбиения, позволяющий строить функции принадлежности объектов для каждого класса. Метод выдает более точные результаты, чем алгоритм кластеризации «Форель» и линейный метод распознавания новых объектов. b) Предложен алгоритм распознавания новых объектов, позволяющий строить покрытие каждого класса множеством гиперсфер разного радиуса. Преимущество данного метода состоит в том, что с его помощью можно описывать кластеры разной формы, а также с помощью правил-гиперсфер малого радиуса возможно достаточно точно описать кластеры, в случае когда близки границы двух кластеров. c) Предложен алгоритм определения геометрической формы кластеров. Он основан на подборе матрицы квадратичной формы для каждого класса и для каждой пары координат. Затем определяется кривая, соответствующая данной матрице - эллипс, гипербола или пара параллельных прямых. Предложено две версии метода. Одна из них находит матрицу квадратичной формы для каждого кластера, не накладывая при это никаких ограничений, во второй версии матрица квадратичной формы задает функцию расстояния, d) Предложен алгоритм кластеризации, который позволяет выделять кластеры с линейной зависимостью. Данный метод рекомендуется применять в том случае, если не удается применить метод линейной регрессии к данным. Метод позволяет строить кусочно-линейную зависимость данных. Предложено три вида функции принадлежности для работы с данным методом.

3. На основе предложенных алгоритмов создан программный комплекс «КЛАССМОД», позволяющий производить анализ данных предложенным методами и производить анализ результатов.

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

1. Азарнова Т.В., Методы оптимизации. Элементы теории, алгоритмы и примеры/ Азарнова Т.В. Каширина И.Л., Чернышова Г.Д. // Воронеж: Изд-во ВГУ, 2000.

2. Айвазян С.А. Классификация многомерных наблюдений / Айвазян С.А., БежаеваЗ.И., Староверов О.В. М.: Статистика, 1974.-240 с.

3. Айвазян С.А. Прикладная статистика и основы эконометрики. Учебник для вузов / Айвазян С.А., Мхитарян B.C. М.: ЮНИТИ, 1998,-1022 с.

4. Айвазян С.А. Прикладная статистика. Классификация и снижение размерности / Айвазян С.А., Бухштабер В.М., Енюков И.С, Мешалкин Л.Д. -М.: Финансы и статистика, 1989, 607 с.

5. Александров В.В. Анализ данных на ЭВМ (на примере системы СИТО) / Александров В.В., Алексеев А.И., Горский Н.Д. М.: Финансы и статистика, 1990, 192 с.

6. Андерсон Т. Введение в многомерный статистический анализ. -М.:-ФИЗМАТГИЗ, 1963. 500 с.

7. Архангельский А.Я. Delphi 6. Справочное пособие./ А.Я. Архангельский. М: ЗАО «Издательство БИНОМ», 2001.-1024 с.

8. Бокий Г.Б. Вопросы классификации и системного подхода в минералогии / Классификация в современной науке. Сборник научных трудов, Новосибирск, Наука, 1989, с. 87 100.

9. Боровиков В. STATISTICA: искусство анализа данных на компьютере. Для профессионалов. СПб.: Питер, 2001. - 655 с.

10. Ю.Гайдышев И. Анализ и обработка данных. Специальный справочник. /И. Гайдышев. Спб: Питер, 2001.-355 с.

11. П.Гвишиани А.Д. О новом подходе к кластеризации / А.Д. Гвишиани, С.М. Агаян, Ш.Р. Богоутдинов //Кибернетика и системный анализ. 2002. —№2.-С.104-122.)

12. Гнеденко Б.В. Курс теории вероятностей. M.-JI.: 1950, 387 с.

13. Головкин Б.А. Машинное распознавание и линейное программирование/ Б.А. Головкин -М.: «Советское радио», 1973-100с.

14. Н.Горелик А. Д., Скрипкин В. А. Методы распознавания. М.: Высшая школа , 1986.

15. Гублер Е. В. Вычислительные методы анализа и распознавания патологических процессов. Л.: Медицина , 1984.

16. Деньги. №21 325. 30.05.2001.

17. Дорофеюк А.А. Алгоритмы автоматической классификации (обзор) //Автоматика и телемеханика, 1971, № 12, с. 78 113.

18. Дорофеюк А.А. Алгоритмы автоматической классификации (обзор) //Автоматика и телемеханика, 1971, № 12, с. 78 113.

19. Дубров A.M., Мхитарян B.C., Трошин Л.И. Многомерные статистические методы: Учебник. М.: Финансы и статистика, 2000. — 352 с.

20. Дюран Б., Оделл П. Кластерный анализ / Пер с англ.- М.: Статистика, 1977. -128 с.

21. Елисеева И.И., Рукавишников В.О. Группировка, корреляция, распознавание образов (Статистические методы классификации и измерения связей). М.: статистика, 1977, 245 с.

22. Жамбю М. Иерархический кластер анализ и соответствия: пер. с фр. -М.: Финансы и статистика, 1988, 243 с.

23. Заде JI.A. Понятие лингвистической переменной и его применение к принятию приближенных решений.-М.:Мир, 1976.-165 с.

24. Интерпретация и анализ данных в социологических исследованиях. М.: Наука, 1987. - 252 с.

25. Кендалл М., Стьюарт А. Многомерный статистический анализ и временные ряды. М.: Наука, 1976, - 736 с.31 .Классификация и кластер. Под ред. Дж. Вэн. Райзин. М.: Мир, 1980, 389с.

26. Князева Е.Н., Курдюмов СП. Будущее и его горизонты: методология в прогнозировании. В сб. Синергетика. Труды семинара. Т.4. Естественнонаучные, социальные и гуманитарные аспекты. М.: МГУ, 2001. -с.5- 19.

27. Кострикин А.И. Манин Ю.И. Линейная алгебра и геометрия. М.: Наука, 1986.

28. Кофман, А. Введение в теорию нечетких множеств / Пер. с фр. В. Б. Кузьмина; Под ред. С. И. Травкина .— М. : Радио и связь, 1982 .— 431, 1. с. : ил., табл. —Парал. тит. л. фр. — 25.00.

29. Леденева Т.М., Тарасова А.С., Татаркин Д.С. Основы нечеткого моделирования в среде MATLAB. Воронеж: Издательско-полиграфический центр ВГУ, 2006. - 52с.

30. Любищев А.А. О критериях реальности в таксономии. // Информационные вопросы семиотики, лингвистики и автоматического перевода. М.: ВИНИТИ, 1971, вып. 1, с.67 82.

31. Любищев А.А. О количественной оценке сходства. В сб.: Применение математических методов в биологии. ЛГУ, 1969.

32. Мальцев А.И. Основы линейной алгебры.М.: Наука, 1975.

33. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988,-176 с: ил.

34. Математические методы анализа и интерпретация социологических данных. М.: Наука, 1989. - 173 с.

35. Математические методы анализа и интерпретация социологических данных. М.: Наука, 1989. - 173 с.

36. Матчо Д. Delphi /Д. Матчо, Д.Р. Фолкнер: Пер. с англ.- М:«Бином», 1995.-464 с.

37. Миркин Б.Г. Анализ.качественных признаков и структур/ Б.Г. Миркин.- М: «Статистика», 1980.-319 с.

38. Миркин Б.Г. Анализ качественных признаков. М.: Статистика, 1976, 166 с.

39. Многомерные классификации в социально экономических исследованиях. Отв. ред. В. Жуковская. М.: 1973, вып. 2.

40. Мучник И.Б., Новиков С.Г., Петренко Е.С. Метод структурный классификации в задаче построения типологии городов по социально- демографическим характеристикам населения // Социологические исследования, 1975, №2.

41. Орлов А.И. Заметки по теории классификации. Социология: методология,методы, математические модели. 1991, № 2, с.28 -50. 48.Орлов А.И. Эконометрика: учебник для вузов. М.: Экзамен, 2003, - 576 с.

42. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения / Р.К. Прим Кибернетический сборник. 1961.- №2. - С. 95-107.

43. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. -М.: Наука, 1967, 237 с. 51 .Распознавание образов в социальных исследованиях. Отв. ред. Загоруйко

44. Н.Г., Заславская Т.И. Новосибирск, Наука, 1968, 196 с.

45. Распознавание образов и медицинская диагностика / Под ред. Ю. Неймарка. М.: Наука, 1972.

46. Тарасова А.С. Методы определения оптимальной геометрической формы в задачах кластерного анализа // Информационные технологии 2007. -№11.- С. 14-21.

47. Тарасова А.С. Модификация алгоритма кластеризации С-средних на основе использования объемных прототипов и слияния схожих кластеров // Вестник ВГУ. Серия «Системный анализ и информационные технологии». -Воронеж: Изд-во ВГУ, 2007. №3. - С.

48. Тарасова А.С. Об одном методе распознавания данных // Современные проблемы прикладной математики и математического моделирования. — Воронеж: Изд-во ВГУ, 2006. С. 217 - 218.

49. Тарасова А.С. Об одном методе распознавания данных на основе если-то правил // Системный анализ в проектировании и управлении: Труды X Междунар. научн. конф. Санкт-Петербург: Изд-во Политехнического университета, 2006. - С.

50. Тарасова А.С. Адаптивные если-то правила / Вестник факультета прикладной математики и механики. Вып. 6. - Воронеж: Изд-во ВГУ, 2007. -С. 169-181.

51. Тарасова А.С. Индексы сходства и включения. Использование в задачах кластерного анализа // Управление большими системами. Труды второй научн. школы-семинара. М.: ИПУ РАН, 2007. - С.

52. Т.М. Леденева. Обработка нечеткой информации/ Воронеж: Воронежский государственный университет, 2006.-233 с.

53. Тейксейра С. Delphi 5. Руководство разработчика, том 1. Основные методы и технологии программирования / С. Тейксейра, К. Пачеко: Пер. с англ. М.: Издательский дом «Вильяме», 2001.-832 с.

54. Терёхина А.Ю. Анализ данных методами многомерного шкалирования/ А.Ю. Терёхина-М.: «Наука», 1986- 166 с.

55. Типология и классификация в социологических исследованиях. М.: Наука, 1982, 296 с.

56. Толстова Ю.Н. Глава 2. Этапы решения задач типологии. Комплексное использование математических методов. В кн.: Типология и классификация. М.: Наука, 1982, с. 29 - 56.

57. Тюрин Ю.Н. Анализ данных на компьютере/ 3-е изд., перераб. и. доп. М: ИНФРА-М, 2003.-543 с.

58. Факторный, дискриминантный и кластерный анализ: Пер. с англ./ Под ред. И. С. Енюкова. М.: Финансы и статистика. 1989. - 215с: ил.

59. Шрейдер Ю.А. Логика классификации. Научно -техническая информация, Сер. 1, 1973, №5, с.З - 7.

60. A1-Sultan, К. S. Computational experience on four algorithms for the hard clustering problem / K. S Al-Sultan, M. M. Khan // Pattern Recogn. Lett. 17, 3, 1996, 295-308.

61. Anderberg, M. R. Cluster Analysis for Applications / M.R. Anderberg // Academic Press, Inc., NewYork, NY. 1973.

62. Auguston, J.G. Ananalysis of some graph theoretical clustering techniques / J.G. Auguston, J. Minker// J. ACM 17, 4 (Oct. 1970), 571-588.

63. Babu, G.P. A near-optimal initial seed value selection in K-means algorithm using a genetic algorithm / G.P. Babu, M.N. Murty //Pattern Recogn. Lett. 14, 10 (Oct. 1993), 763-769.

64. Babuska, R. An Overview of fuzzy modeling for control/ R. Babuska, H.B. Verbruggen//Control Engineering Practice 4(11), 1996, pp. 1593-1600.

65. Babuska, R. Identification of composite linear models via fuzzy clustering/ R. Babuska, H.B. Verbruggen// Proceedings European Control Conference, Rome, Italy, 1995, pp.1207—1212.

66. Bezdek, J. Pattern Recognition with Fuzzy Objective Function. Plenum Press, New York, 1981.

67. Bhuyan, J.N. Genetic algorithm for clustering with an ordered representation / J.N. Bhuyan, V.V. Raghavan, K.E. Venkatesh // In Proceedings of the Fourth International Conference on Genetic Algorithms, 1991. 408-415.

68. Carpenter, G. ART3: Hierarchical search using chemical transmitters in self-organizing pattern recognition architectures /G. Carpenter, S. Grossberg // Neural Networks 3, 1990. 129-152.

69. Chiu, Stephen L. An Efficient Method for Extracting Fuzzy Classification Rules from High Dimensional Data / Stephen L. Chiu // J. Advanced Computational Intelligence, Vol. l,No. 1, 1997

70. Chiu, Stephen L. Extracting Fuzzy Rules from Data for Function Approximation and Pattern Classification / Stephen L. Chiu // Fuzzy Information Engineering: A Guided Tour of Applications, ed. D. Dubois, H. Prade, and R. Yager, John Wiley & Sons, 1997.

71. Diday, E. Clustering analysis / E. Diday, J. C. Simon // Digital Pattern Recognition, Ed. Springer-Verlag, Secaucus, NJ, 1976, 47-94.

72. Diday, E. .The symbolic approach in clustering / E. Diday // Classification and Related Methods, Ed. North-Holland Publishing Co., Amsterdam, The Netherlands. 1988.

73. Dubes, R. C. How many clusters are best? — an experiment / R.C. Dubes // Pattern Recogn. 20,6 (Nov. 1, 1987), 645-663.

74. Everitt B. Cluster Analysis. New York, 1974.

75. Fisher, L. Admissible clustering procedures / L. Fisher, J. W. Van Ness // Biometrika 58, 1971.91-104.

76. Fu, K.S. A clustering procedure for syntactic patterns // K.S. Fu, S.Y. Lu/ЯЕЕЕ Trans. Syst. Man Cybern. 7, 1977. 734-742.

77. Fukunaga, K. Introduction to Statistical Pattern Recognition / K. Fukunaga // 2nd ed. AcademicPress Prof., Inc., San Diego, CA. 1990.

78. G.R. Dattatreya and L.N. Kanal, Decision Trees in Pattern Recognition / L.N. Kanal, A. Rosenfeld (Editors), Elsevier Science Publishers B.V. (North-Holland), 1985.

79. Gowda, К. C. Agglomerative clustering using the concept of mutual nearest neighborhood//K.C. Gowda, G. Krishna//PatternRecogn. 10, 1977. 105-112.

80. Gowda, K.C. Symbolic clustering using a new dissimilarity measure / K.C. Gowda, E. Diday // IEEE Trans. Syst. Man Cybern. 22, 1992. 368-378.

81. Gustafson, E. Fuzzy clustering with a fuzzy covariance matrix/ E. Gustafson, W. Kessel // Proc. IEEE Conf. Decision Control, 1979, 761-766.

82. Ichino, M. Generalized Minkowski metrics for mixed feature-type data analysis/

83. M. Ichino, H. Yaguchi// IEEE Trans. Syst. Man Cybern. 24, 1994, 698-708. 94.Ismail, M. A. Multidimensional data clustering utilizing hybrid search strategies / M. A. Ismail, M. S Kamel // Pattern Recogn. 22, Jan. 1989, 75-89.

84. Jain, A.K. Algorithms for Clustering Data / A.K. Jain, R. C. Dubes // Prentice-Hall advanced reference series. Prentice-Hall, Inc., Upper Saddle River, NJ. 1988.

85. Jarvis, R.A. Clustering using a similarity method based on shared near neighbors / R.A. Jarvis, E.A. Patrick // IEEE Trans. Com-put. C-22, 8 (Aug.), 1973. 10251034.

86. Jones, D. Solving partitioning problems with genetic algorithms / D. Jones, M.A. Beltramo // In Proceedings of the Fourth InternationalConference on Genetic Algorithms, 1991. 442-449.

87. Kim, D.-W. Detecting clusters of different geometrical shapes in microarray gene expression data/ D.-W. Kim, К. H. Lee, D. Lee // BIOINFORMATICS. № 21. - 09. 2005 .- C. 1927-1934.

88. Klawonn, F. Constructing a Fuzzy Controller from Data / F. Klawonn, R. Kruse // Fuzzy Sets and Systems, 85, pp. 177-193, 1997.

89. Knuth, D. The Art of Computer Programming / D. Knuth // Addison-Wesley, Reading, MA. 1973.

90. Kohonen, Т. Self-Organization and Associative Memory / T. Kohonen // 3rd ed. Springer information sciences series. Springer-Verlag, New York, NY. 1989.

91. L. Breiman, J.H. Friedman, R.A. Olshen and C.J. Stone, Classification and Regression Trees, Wadsworth & Brooks/Cole, Montrey, CA, 1984.

92. Mao, J. A self-organizing network for hyperellipsoidal clustering (НЕС) / J. Mao, A. K. Jain // IEEE Trans. Neural Netw. 7, 1996, 16-29.

93. Michalski, R. Automated construction of classifications: conceptual clustering versus numerical taxonomy /R. Michalski, R.E. Stepp, E. Diday // IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 5 (Sept.), 1983.396-409.

94. Mishra, S. K. An empirical study of the performance of heuristic methods for clustering / S. К Mishra, V. V Raghavan // Pattern Recognition in Practice 1994, 425-436.

95. Nauck, D. Foundations of Neuro-Fuzzy Systems / D. Nauck, F. Klawonn, R. Kruse // Wiley, Chichester, 1997.

96. Ozawa, K. A stratificational overlapping cluster scheme / K. Ozawa // Pattern Recogn. 18, 1985.279-286.

97. Pal, N.R. Generalized clustering networks and Kohonen's self-organizing scheme / N.R. Pal, J.C. Bezdek, E. C-K. Tsao // IEEE Trans. Neural Netw. 4, 1993. 549-557.

98. Raghavan, V.V. A clustering strategy based on a formalism of the reproductive process in a natural system / V.V. Raghavan, K. Birchard // In Proceedings of the Second International Conference on Information Storage and Retrieval, 1979. 1022.

99. Raghavan,V.V. A comparison of the stability characteristics of some graph theoretic clustering methods / V.V. Raghavan, C.T. Yu // IEEETrans. Pattern Anal. Mach. Intell. 3, 1981. 393-402.

100. Rose, K. Deterministic annealing approach to constrained clustering // K. Rose, E. Gurewitz, F.C. Fox // IEEE Trans. PatternAnal. Mach. Intell. 15, 1993. 785-794.

101. Selim, S. Z. K-meanstype algorithms: A generalized convergence theorem and characterization of local optimality / S. Z Selim, M. A Ismail //IEEE Trans. Pattern Anal. Mach. Intell 6, 1984, 81-87.

102. Takagi,T. Fuzzy identification of systems and its application to modeling and control / T. Takagi, M. Sugeno // IEEE Trans. On Systms, Man & Cybernetics, vol.15, pp. 116-132, 1985.

103. Toussaint, G. T. The relative neighborhood graph of a finite planar set / G.T. Toussaint // PatternRecogn. 12, 1980. 261-268.

104. Usay Kaymak. Extended fuzzy clustering algorithms / Usay Kaymak and Magne Setnes // Erim Report Series Research in Management, November 2000, 24 pages.

105. Watanabe, S. Pattern Recognition: Human and Mechanical / S. Watanabe // John Wiley and Sons, Inc., New York, NY. 1985.

106. Wilson, D.R. Improved heterogeneous distance functions / D.R. Wilson, T. R. Martinez // J. Artif. Intell. Res. 6, 1997. 1-34.119. www.banks-rate.ru.

107. Zadeh, L. Fuzzy sets as a basis for a theory of possibility / Fuzzy Sets and Systems 1, 3-28, 1978.

108. Zahn, C.T. Graph-theoretical methods for detecting and describing gestalt clusters / C.T. Zahn // IEEE Trans. Comput. C-20 (Apr. 1971), 68-86.