Содержание к диссертации
Введение
Глава 1. Анализ подходов к решению задачи кластеризации и распознавания данных 11
1.1. Кластерный анализ 11
1.1.1. Постановка задачи кластеризации 11
1.1.2: Этапы решения задачи кластеризации 13
1.1.3. Сравнительный анализ подходов к решению задачи кластеризации .23.
1.2. Распознавание данных 32
1.2.1. Постановка задачи распознавания 32
1:2.2.' Виды систем распознавания 34
1.2.3. Модели для решения задач распознавания 36.
1.2.4: Нечеткие методы распознавания, основанные на продукционных правилах 37
1.3: Цель и задачи исследования 41*
Выводы к первой главе 43
Глава 2. Разработка методов кластеризации на основе схемы алгоритма «обобщенный роден» 44
2:1. Алгоритм Роден 44
2:2. Разработка алгоритмов, эффективных с точки зрения алгоритма «Форель» на основе схемыалгоритма «Обобщенный Роден» 50
2.3. Разработка алгоритмов кластеризации, эффективных с точки зрения алгоритма «КРАБ» 60
2.4. Разработка нечетких алгоритмов кластеризации на основе схемы алгоритма «Роден» 69
Выводы ко второй главе 78
Глава 3. Разработка методов описания классов и распознавания новых объектов 80
3.1. Распознавание новых объектов на основе подбора весов признаков для классификационного разбиения 80
3:2. Метод описания классов и распознавания новых объектов, позволяющий строить покрытие кластера множеством сферических правил различного радиуса 93
3.3. Методы определения геометрической формы кластеров 101
3:4. Построение и реализация кластеризационно-регрессионных нечетких алгоритмов на основе схемы алгоритма «Обобщенный Роден» 116
Выводы к третьей главе 123
Глава 4. Реализация предложенных методов и анализ вычислительной экспертизы 125
4.1. Разработка методики сравнения результатов алгоритмов кластеризации 125
4.2. Описание программного комплекса КЛАССМОД, реализующего предложенные методы 132
4.3. Программа для реализации метода распознавания данных с помощью правил различной геометрической формы 138
4.4. Результаты практической апробации разработанных алгоритмов кластеризации и распознавания новых объектов на примере анализа данных о клиентах компании ООО «М-Бит» 139
Выводы к главе 4 145
Заключение 146
Литература 148
Приложение 1 159
Приложение 2 160
Приложение 3 162
Приложение 4 164
Приложение 5 166
Приложение 6
- Сравнительный анализ подходов к решению задачи кластеризации
- Разработка алгоритмов, эффективных с точки зрения алгоритма «Форель» на основе схемыалгоритма «Обобщенный Роден»
- Метод описания классов и распознавания новых объектов, позволяющий строить покрытие кластера множеством сферических правил различного радиуса
- Описание программного комплекса КЛАССМОД, реализующего предложенные методы
Введение к работе
Как известно, кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число кластеров на основании некоторого математического критерия качества кластеризации. Процедуры кластерного анализа используются как на стадии предварительной обработки информации при решении задач управления, прогнозирования, принятия решений, позволяя решить проблемы сокращения размерности, структуризации и выявления скрытых закономерностей в имеющейся информации, так и имеют самостоятельное значение (упорядоченная или неупорядоченная кластеризация объектов заданного множества). Алгоритмы кластеризации достаточно полно и подробно рассмотрены в литературе и отличаются большим разнообразием, которое обусловлено доступной исходной информацией; особенностями критерия качества кластеризации, и его формализацией; выбором метрики, отражающей схожесть объектов; нацеленностью на определенную структуру группировок объектов и др. В связи с этим возникает необходимость сравнения результатов кластеризации, полученной с помощью различных алгоритмов, и выявление такого алгоритма, который в наибольшей степени учитывает специфику данных. Важно, что при этом одно и то же (или почти одно и то же) классификационное разбиение может быть результатом нескольких процедур, поэтому актуальным является исследование существующих взаимосвязей между подходами к кластеризации и моделирования основных компонент процедуры кластеризации с тем, чтобы разбиение данных было нацелено на получение кластеров с определенными свойствами. Вопросы, касающиеся получения, кластеров с заранее заданными качествами, разрабатывались А.Д. Гвишиани, СМ. Агаяном, Ш.Р. Богоутдиновым. Важнейшим фактором, влияющим на выбор алгоритма, является неопределенность. Один из путей усовершенствования известных процедур кластерного анализа - их обобщение на «нечеткий» случай. Вопросами разработки нечетких алгоритмов кластеризации занимались J. Bezdek, Б. Gustafson, W.. Kessel, I. Gam,. 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 таблиц.
Структура и краткое содержание работы. Во введении обоснована актуальность темы диссертационной работы, определены цель и задачи исследования, охарактеризованы используемые методы, описаны структура работы, взаимосвязь и краткое содержание ее разделов.
В первой главе дается понятие о кластерном анализе, определения кластеров, кластеризации и кластерного анализа. Обсуждаются основные этапы решения задачи кластеризации. Рассмотрена проблема выбора метода кластеризации, выбора способа представления данных. Рассмотрена одна из определяющих компонент каждого алгоритма кластерного анализа - мера подобия. Далее приводится классификация и сравнительный анализ существующих методов кластерного анализа. В первой главе также дается понятие метода распознавания, приводятся виды систем распознавания и основные модели для решения задачи распознавания новых объектов. Далее приводятся цели и задачи исследования.
Во второй главе описываются основные идеи алгоритмов кластеризации, разработанных на основе схемы алгоритма «Обобщенный Роден», а также результаты практической апробации этих методов.
Третья глава посвящена разработке методов описания классов и распознаванию новых объектов. Произведены вычислительные эксперименты, описаны основные особенности поведения предложенных методов и даны рекомендации по настройке параметров.
В четвертой главе с помощью предложенного и автоматизированного автором метода по сравнению алгоритмов кластеризации произведено сравнение новых алгоритмов кластеризации с традиционными методами. Четвертая глава также посвящена описанию программного обеспечения по кластерному анализу данных. Разработанное программное обеспечение позволяет отображать исходные данные в графическом режиме с помощью визуализации методом многомерного шкалирования. По результатам анализа создаются отчеты, как в текстовом, так и в графическом режиме, а именно изображается визуализация выходного классификационного разбиения, а также изображаются функции принадлежности для классов и результаты методов описания классов. Предусмотрена возможность сохранения результатов анализа в файл. Рассмотрена архитектура системы и приведено руководство пользователя с описанием интерфейса разработанного программного обеспечения. Приведено также описание отдельного модуля для построения правил описания классов различной геометрической формы, реализованной в пакете MATLAB. В четвертой главе также обсуждаются результаты использования предложенных методов, алгоритмов и программных средств для анализа данных о клиентах компании ООО «М-Бит».
В заключении формулируются научные и практические результаты диссертационного исследования.
В приложениях приводятся используемые в работе данные и результаты экспериментов.
Сравнительный анализ подходов к решению задачи кластеризации
На рис. 1.6 представлена классификация подходов к задаче кластеризации. Эта классификация основана на рассуждениях в [95]. На верхнем уровне различают иерархический подходы, строящие ряды разбиений, вложенные друг в друга, и подходы, строящие одно разбиение.
Рассмотрим различные подходы к кластеризации, которые в той или иной мере присутствуют в каждой группе методов, представленной на схеме. Агломеративный или разделяющий. Агломеративный подход начинает с каждого объекта в отдельном кластере (синглтон) и сливает кластеры пока не выполнится критерий останова. Разделяющий подход начинает с кластера, содержащего все данные, и производит разделение, пока не выполнится критерий останова.
Монотетичные или политетичные. Кластеризация по одному признаку (Monothetic) или кластеризация, основанная на одном сравнении нескольких признаков (Polythetic). Большинство алгоритмов политетичные, т.е. все признаки участвуют в вычислении расстояний между объектами.
Четкие или нечеткие. Четкие алгоритмы кластеризации распределяют каждый объект в один кластер. Нечеткие алгоритмы присваивают каждому объекту степень принадлежности к каждому кластеру. Нечеткие методы кластеризации позволяют одному и тому же объекту принадлежать одновременно нескольким (или даже всем) кластерам, но с различной степенью. Нечеткая кластеризация во многих ситуациях более "естественна", чем четкая, например, для объектов, расположенных на границе кластеров. Нечеткая кластеризация может быть преобразована в четкую путем распределения объекта в тот кластер, где его степень принадлежности максимальна или используют методы дефазификации. Нечеткую кластеризацию целесообразно также применять, к данным, содержащим «фоновые» точки. В- случае четкой кластеризации такие объекты образуют отдельный кластер, в то время как при нечеткий кластеризации данные объекты будут определены в какой-либо из кластеров с гораздо более малой степенью принадлежности, чем степень принадлежности остальных точек.
Детерминистские или стохастические. Данный вопрос более релевантен для подходов, строящих одно разбиение, основанных на минимизации функции от квадрата ошибки. Эта оптимизация может быть произведена с использованием традиционных технологий или через случайный поиск в пространстве состояний, состоящем из всех возможных классификационных разбиений.
Инкрементные или не инкрементные. Данный вопрос возникает, когда множество объектов очень велико, и ограничения на память или время выполнения влияют на строение алгоритма. Ранняя история методологий кластеризации содержит не много алгоритмов, разработанных для кластеризации больших объемов данных. Но появление технологий data mining благоприятствовало развитию алгоритмов. кластеризации, которые минимизируют количество проходов по множеству данных, уменьшающих количество объектов, анализируемых во время выполнения или уменьшающих размер структур данных, используемых в операциях алгоритма. Методы кластеризации также классифицируются по тому, определено ли количество кластеров заранее или нет. В .последнем случае количество кластеров определяется в ходе выполнения алгоритма на основе распределения исходных данных. Бесспорно то, что определение алгоритма для кластеризации обычно оставляет достаточно гибкости для его реализации.
Работа алгоритма иерархической кластеризации представлена на рис. 1.8. На нем изображены 7 объектов, которые расклассифицированы в 3 кластера. Иерархический алгоритм выдает дендрограмму, представляющую группирования объектов, вложенные друг в друга, и уровни подобия, на которых эти группировки изменяются. Дендрограмма для данных, семи объектов получена с помощью алгоритма Одиночной связи (single-link), [95] и изображена на рис. 1.9. Дендрограмма может быть разбита на различных уровнях, с тем чтобы получить различные классификационные разбиения.
Большинство алгоритмов кластеризации - это вариации алгоритма одиночной связи, алгоритма полной связи (complete-link), и алгоритма минимального отклонения (minimum variance). Наиболее популярны из них -алгоритм одиночной связи и алгоритм полной связи. Эти два алгоритма отличаются тем, как они характеризуют сходство между парами кластеров. В методе одиночной связи расстояние между двумя кластерами - это минимум из расстояний между всеми парами объектов (один объект— из первого кластера -второй — из второго). В алгоритме полной связи расстояние между двумя кластерами - максимум всех парных расстояний между объектами из двух кластеров. В любом случае, два кластера сливают, формируя больший кластер, основываясь на критерии минимума расстояния. Алгоритма полной связи выдает тесно связанные или компактные кластеры. Алгоритм одиночной связи, напротив, страдает от эффекта связывания.
Алгоритмы, строящие одно разбиение, имеют преимущество перед иерархическими, когда необходимо произвести кластеризацию большого количества данных, для которых построение дендрограммы невозможно осуществить из-за слишком большого объема вычислений. Проблема, сопровождающая использование алгоритмов разбиения - выбор количества кластеров. Статья [84] содержит указания по этой ключевой проблеме. Технологии разбиения обычно строят кластеры, оптимизируя функцию-критерия, определенную либо локально (на подмножестве объектов), либо глобально (на всех объектах). Комбинаторный поиск множества различных классификационных разбиений для оптимизации критерия невозможен из-за большого объема вычислений. Поэтому на практике алгоритм запускается несколько раз с различными начальными параметрами, и наилучшая конфигурация, полученная из всех запусков алгоритма, есть выходное классификационное разбиение. Алгоритмы квадрата ошибки, теоретико-графовая кластеризация [121, 73, 108, 115], алгоритмы с разрешенным смешиванием [95], подходы, основанные на поиске (mode-seeking algorithms), алгоритм модельной "закалки" (улучшающий свойства модели ) [112] относятся к алгоритмам, строящим одно разбиение.
Сравнение подходов к решению задачи кластерного анализа с точки зрения критериев эффективности задачи оптимизации Сравним различные стохастические и детерминистические технологии поиска решения проблемы кластеризации как оптимизационной проблемы. Сравнение алгоритмов SA (модельной закалки), GA (Генетические алгоритмы), TS (Tabu-поиск) было произведено в [105]. Изучение стратегий гибридного поиска (HS) было произведено в [94]. Будем считать, что объем данных мал, если рассматривается менее 200 объектов. Эффективности алгоритмов кластеризации, основанных на нейросетях, изучалась в [103]. Таблица 2 содержит результаты сравнения подходов к решению задачи кластеризации. Подход Отличительные черты Квадрата ошибки Форма кластера в виде гиперсферы.Чувствительность к выбору контролирующих параметров.Не использует дополнительную информацию об исследуемыхданных.Способен обработать большой объем данных.Высокая скорость (превосходит более чем в 500 раз по сравнению сдругими алгоритмами при кластеризации 60 объектов на 5кластеров) [71].Выдает локальное решение [113].
Разработка алгоритмов, эффективных с точки зрения алгоритма «Форель» на основе схемыалгоритма «Обобщенный Роден»
Алгоритм работает следующим образом. Центр первой гиперсферы с заданным радиусом помещается в любую точку множества. Определяются объекты, которые оказались внутри гиперсферы. Затем происходит вычисление центра тяжести гиперсферы и перемещение в него центра гиперсферы. И так далее, пока центр тяжести сферы не перестанет смещаться с некоторой заданной точностью. При этом гиперсфера останавливается в области локального экстремума плотности объектов множества. Эту гиперсферу принимают за первый кластер. Далее ее исключают из рассмотрения и оставшееся множество подвергают дальнейшей кластеризации, выделяя следующий кластер по описанной выше процедуре.
Заметим, что вопрос о выборе центра следующей сферы может решаться по-разному, например можно в качестве центра брать точку, находящуюся дальше всех от центров уже существующих кластеров (c +l =argmax d(cJ ,х)). xeXl[)Sj J=l Алгоритм «Форель» является достаточно простым и распространенным алгоритмом. В своем исследовании мы предлагаем алгоритмы, позволяющие получать кластеры, эффективные с точки зрения используемого в алгоритме «Форель» критерия качества, реализованные на схеме «Роден». Алгоритм «Форель-Роден 1» Таким образом, классификационное разбиение, полученное по «Форель» - это множество кластеров в форме гиперсфер, центры которых расположены в центре в центре тяжести кластера. Предложим способ получения таких множеств с помощью идеологии Роден. Так как Роден выделяет кластеры последовательно, один за другим, а F-критерий возможно рассчитать только для всего множества, то для критерия качества каждого кластера предлагается Iі использовать F(Lh) =— d(xh ,ch), который характеризует среднее расстояние от центра гиперсфер до его элементов. Пусть задан порог на ограничение меры внутренней связи / (экспертным путем). Так как F среднее расстояние от элементов кластера до его центра, то / следует задавать так, чтобы выполнялось ограничение f — , где d - расстояние между двумя наиболее отдаленными друг от друга элементами. Заметим, что если F{Lk) f, то выполнено и ограничение на меру внутренней связи всего классификационного разбиения F = \Lk\ F(Lk) /J] Lk\ = fn.
Центр гиперсферы будем всегда помещать в центр тяжести множества. При этом если центр тяжести не является элементом множества, то мы все равно помещаем в нее центр кластера. Добиваться заданного порога качества будем путем высекания точек, обеспечивающих наибольшее значение F{Lk). Если одновременно несколько точек удовлетворяют условию высекания, то мы высекаем любую из этих точек. Когда качество будет удовлетворять заданному порогу, то можно посчитать радиус гиперсферы как г, =maxd(x,ck). Таким образом, мы получили кластер в виде гиперсферы с центром в центре тяжести его элементов, с радиусом гх и средним расстоянием от центра до элементов гиперсферы, не превышающим /. Далее это множество исключается из рассмотрения и по описанному выше алгоритму ищется следующий кластер.
Замечание 2. Если классификационное разбиение содерэюит один кластер, количество объектов в котором сравнимо с количеством всего мнооїсества данных, то кластеризация данных бесполезна, так как мы не можем извлечь какую-либо информацию о структуре данных. В этом смысле целесообразно получать более равномерные классификационные разбиения.
Рассмотрим как данную идеологию можно осуществить с помощью схемы «Обобщенный Роден». Элементами множества будем считать гиперсферы. Как и ранее, качеством будем считать среднее расстояние от центра кластера до всех его элементов: F{Lk) = Td (x,ck). Перед тем как « измерять качество множества, нужно разбить его на гиперсферы по следующему принципу.
Зададим величину порога качества /(экспертным путем). Будем добиваться такого значения критерия качества F, что F{Lk) f. Будем измерять качество каждой гиперсферы и ту гиперсферу, где качество минимально будем высекать.
Алгоритм «КРАБ» Методы семейства «КРАБ», предложенные в [26], позволяют получать кластеры с их «естественной» формой. Эти алгоритмы представляют собой результат попытки выявить и применить те критерии качества кластеризации, которыми неосознанно пользуется человек при кластеризации. Кластеризация тем лучше, чем меньше мера близости объектов внутри кластеров (R), чем больше мера взаимной удаленности кластеров (D), иногда исследователю нужно получить равномерные распределения (Н), также при кластеризации важны скачки плотности точек (G). Если удачно подобрать все указанные меры, то можно добиться совпадения экспертной и автоматической кластеризации.
Еще одним отличием алгоритма «КРАБ-Роден» будет то, что после выделения очередного кластера элементы, которые не вошли в него могут оказаться не связанными в КНП. Поэтому на оставшихся элементах мы будем снова проводить КНП с тем, чтобы построить кластеры из оставшихся элементов.
Метод описания классов и распознавания новых объектов, позволяющий строить покрытие кластера множеством сферических правил различного радиуса
Многие системы анализа данных включают в себя систему поиска если-то правил, которые помогают решать проблемы распознавания новых объектов. ,i По сравнению с другими методами распознавания, если-то правила предъявляют минимальные требования к типу данных и могут быть применены к разнородным данным [45,46]. Главное преимущество отслеживания поведения данных в форме нечетких если-то правил в их простоте по сравнению, например с нейронными сетями. Нечеткие правила легко понимать, проверять и расширять. Разработчик системы может проверить нечеткие правила на адекватность содержательной постановке задачи интуитивно, проверить систему на полноту и настраивать систему, добавляя правила в базу правил. Этим объясняется интерес к использованию если-то правил. Можно выделить следующие подходы к поиску если-то правил, например, методы, в основе которых лежит построение начального приближения правил, а затем идет их уточнение, то есть подбор таких параметров, участвующих в определении функций, которые доставляют максимальное качество набора правил. К таким методам относятся эволюционные алгоритмы, разностную кластеризацию. Также построение если-то правил осуществляют такие методы как деревья решений и подходы ограниченной комбинаторной сортировки. Для построения начальной базы правил мы использовали способ, указанный в методе разностной кластеризации [45, 46]. Рассмотрим основные идеи этого метода. Разностная кластеризация Г45,461 Пусть имеется п объектов х{,х2,...,хп. Требуется произвести кластеризацию данных.
Мы используем такое качество как точность и способность покрыть данные, то есть стремимся получить максимально точный набора гиперсфер, который покрывает все множество точек. Шаг 1. Задаєм га— начальный радиус гиперсфер, Pmin є (0,1] — минимальную ТОЧНОСТЬ, которая должна быть достигнута, и множитель Rch є (0,1), на который изменяется радиус на каждой итерации.
Получена кластеризация этих данных рис_ З.ю. Результат работы на 7 кластеров с помощью нечеткого алгоритма, алгоритма «FCM-Роден». (рис.3.7). Различные цвета и фигуры, изображающие элементы данных, обозначают принадлежность к различным кластерам.
Для нахождения гиперсфер были выбраны следующие параметры: га =0.4, Ртт =0.95, Нл =0.8, /7 = 0.1. Представим начальный результат, один из промежуточных и окончательный. На рисунках заштрихованная область - это область действия гиперсферы, для каждого кластера данная область штрихуется разным цветом. Крестики обозначают центры плотностей, определяющие гиперсферы.
Таким образом, получено 14 гиперсфер. Класс №1 описывается і одной гиперсферой с радиусом 0.32, Класс №2 описывается семью гиперсферами с различными а радиусами 0.20, 0.16, 0.13, четырьмя с гиперсферами с радиусом 0.07, Класс №3 описывается двумя правилами, с радиусом 0.13 и 0.03, классы № 4,5,6 описываются одной гиперсферой.
Таким образом, предложенный метод позволяет строить гиперсферы и распознавать новые объекты достаточно адекватно. В дальнейшем планируется усовершенствовать метод, в сторону оптимизации базы правил по всем предложенным критериям качества, а также строить правила, форма которых подбирается, в процессе работы метода.
Описание программного комплекса КЛАССМОД, реализующего предложенные методы
В программе предусмотрены средства для регулирования параметров визуализации (рис 4.4), а именно выбора одной из двух целевых функций, шага и точности метода. Также пользователь может посмотреть получившиеся координаты и достигнутую точность метода. Далее пользователю предлагается выбрать один из видов анализа: кластеризацию по «Форель-Роден», по «КРАБ-Роден», оценка классификационных разбиений по соответствующим методам или распознавание новых объектов.
Кластеризация данных На рис. 4.5 представлена форма кластеризации по «Форель-Роден 2». Заметим, что в качестве результатов кластеризации предлагается два вида информации: 1. Текстовый результат, который представляет собой ход кластеризации, содержание кластеров и качественные параметры полученного классификационного разбиения (рис 4.6).
Результаты кластеризации Рис.4.7. Визуализация разбиения данных 2. Визуализацию классификационного разбиения, где каждый класс изображается своим знаком (рис.4.7). Пользователю предоставляется возможность сохранить результаты в файл.
Распознавание новых объектов с помощью алгоритма «Обобщенный Роден» Входная информация: 1. Классификационное разбиение объектов, то есть количество классов и содержание каждого класса; 2. Величина а для корректировки весов при высекании; 3. Порог меры принадлежности для классов. Мы задаем один порог для всех классов. 4. Величина, которая на графике будет обозначать бесконечность.
Данный метод был реализован в среде MATLAB 6 ввиду того, что в этой среде доступны такие функции как функции построения эллипса, направленного не вдоль осей координат, функций по обращению матриц и нахождению собственных значений и собственных векторов. Реализация данного метода в среде Delphi по этим причинам была затруднена.
На вход в программу подается имя файла с данными и имя файла с данными разбиения на кластеры. Программа содержит 184 строки, обращается к 5 подпрограммам, содержащихся в 5 отдельных файлах. На выходе программа выдает графическое изображение построенных правил для каждой пары признаков. Программа работает достаточно медленно и рекомендуется к использованию на процессорах, скорость которых не менее 1 Гц.
Данные о клиентах были получены путем выгрузки оборотов по счетам и ступеней напоминаний клиентов за 2006 год из системы SAP ERP. В целях неразглашения коммерческой тайны номера клиентов были изменены. Всего было выгружена 221 запись. Были выгружены данные со следующими признаками: 1. Сальдо предыдущего периода - начальное сальдо на 01.01.2006; 2. Дебет, кредит, оборот по счету клиента за каждый из 16 периодов (12 соответствуют месяцам и 4 периода, предназначенные для закрытия года); 3. Сумма выравнивания - сумма, которую заплатил клиент, чтобы закрыть открытую позицию, возникшую в результате задолженности; 4. Ступень напоминания. Измеряется от 0 до 4. Напоминание используется в системе SAP ERP в случае, если клиент не заплатил в срок по задолженности. С каждым напоминанием ступень напоминания увеличивается на 1. То есть у хороших клиентов ступень напоминания равна 0, а у самых ненадежных клиентов - 4.
Целью исследования является изучение структуры множества клиентов, выделения классов клиентов, построения правил распознавания новых объектов, с тем, чтобы отнести новых клиентов у одному из существующих классов.
Рассмотрим поэтапно исследование данных о клиентах. 1. Так как в разработанных нами методах считается, чем больше значение признака, тем лучше, мы преобразовали признак Endsaldo и Mahnstufe, умножив их на (-1) - если в конце года конечное сальдо положительно, то клиент должен компании деньги, то есть этот клиент ненадежен. Также, чем больше ступень напоминания, тем хуже. 2. Визуализация данных
Как видно из рис.4.16, еще до кластеризации данных, можно сказать, что существует один большой кластер, к которому принадлежат практически все клиенты, и существуют клиенты, которые «выделяются из общей массы».
Из визуализации видно, что данный объект лежит за границами какого-либо из кластеров. Со степенью принадлежности, близкой к 0.34, данный объект можно отнести к кластеру №2.
Итак, с помощью разработанных нами методов, мы выделили группы клиентов, а также построили правила распознавания новых объектов. Внедрение профаммного комплекса КЛАССМОД позволило оценить перспективы работы с клиентами фирмы и позволяет «отсечь» ненадежных клиентов, что в конечном итоге ведет к уменьшению дебиторской задолженности, следовательно, уменьшается время ее оборота, оказывая положительное влияние на показатели ликвидности.
1. Произведено сравнение алгоритмов «Форель», ФРІ, ФР2. Для этого разработаны системы критериев качества для оценки разбиений на кластеры и предложен метод сравнения алгоритмов кластеризации. Данный метод может служить решающим правилом для выбора алгоритма кластеризации, который следует применять к конкретным данным.
Эксперименты показали, что в целом алгоритм «Форель» выдает более качественные разбиения, чем ФР1, а алгоритм ФР2 превосходит «Форель» на небольшую величину по качеству;
2. Методы кластерного анализа и методы описания кластеров и распознавания новых объектов, разработанные в предыдущих главах, нашли практическую реализацию в специальном программном обеспечении по кластерному анализу;
3. Разработаны структуры данных для эффективного хранения компонентов моделей в памяти и манипулирования списками элементов и параметрами моделей в оперативной памяти ЭВМ;
4. Содержательные компоненты пользовательского интерфейса и графические средства для визуализации данных, комплекс отчетов в текстовом и графическом виде позволяют качественно осуществить анализ данных и разработать эффективные стратегии принятия решений.
Похожие диссертации на Моделирование обобщенных процедур кластеризации и анализ данных сложной структуры
