Введение 3
1 Задача кластеризации данных 5
1.1 Понятие кластеризации 5
1.2 Постановка задачи кластеризации 6
1.3 Метрики для задания кластеров 9
1.4 Критерии кластеризации 10
1.5 Типы кластерных структур 13
1.6 Методы кластеризации 15
2 Классические методы решения задачи кластеризации данных 20
2.1 Метод k-средних 20
2.2 Решение задачи кластеризации методом FOREL 23
3 Генетические алгоритмы 26
3.1 Основные понятия генетических алгоритмов 27
3.2 Классический генетический алгоритм 28
3.3 Генетический алгоритм для решения задачи кластеризации 35
4 Сравнение предложенных алгоритмов со стандартными методами
кластеризации 42
5 Решение практической задачи кластеризации 45
5.1 Описание статистики 46
5.2 Решение задачи кластеризации методом k-средних и генетическим
алгоритмом кластеризации с детерминированным числом кластеров 46
5.3 Решение задачи кластеризации методами FOREL и генетическим
алгоритмом кластеризации с заданным радиусом кластеров 49
5.4 Сравнение полученных результатов 51
5.5 Визуализация результатов 52
Заключение 55
Список использованных источников 56
Приложение А 59
Целью бакалаврской работы является разработка генетического алгоритма, решающего задачу кластеризации многомерных статистических данных.
Задача кластеризации данных [14] (также называемая таксономией, автоматической классификацией или группировкой объектов) является одной из наиболее важных и сложных задач анализа данных.
Кластерный анализ [15] представляет собой раздел статистического анализа данных, объединяющий методы разбиения (группировки) множества наблюдаемых объектов на сравнительно однородные группы, называемые кластерами. Однородность кластеров означает, что объекты, отнесенные к одному кластеру, должны быть близки относительно выбранной метрики. Объекты из разных кластеров должны существенно отличаться. Кластерный анализ является востребованной и успешно развивающейся дисциплиной современной теоретической информатики. Его методы имеют широкий спектр применений практически во всех областях человеческой деятельности, связанных с изучением объектов и процессов: медицине, биологии, химии, маркетингу, психологии, социологии, менеджменту, филологии, археологии и другим.
В первой части работы приводятся основные понятия и постановка задачи кластеризации данных. Перечисляются виды наиболее часто выделяемых кластерных структур и критерии качества кластеризации. Рассматриваются основные методы кластеризации данных. Особое внимание в работе уделяется двум наиболее популярным методам кластеризации данных: методу k-средних и FOREL [6]. Дается подробное описание данных алгоритмов, и указываются особенности их работы.
Во второй части работы излагаются принципы работы генетических алгоритмов [7], являющихся эвристическими алгоритмами поиска, широко используемыми для решения задач оптимизации и моделирования путём случайного подбора и вариации параметров с использованием механизмов, аналогичных естественному отбору в природе. В работе рассматриваются назначение и виды основных операторов генетических алгоритмов, в том числе операторы скрещивания, мутации и селекции. Приводится схема этапов работы генетического алгоритма в общем виде.
В работе предлагаются два генетических алгоритма, позволяющих решать задачу кластеризации данных. Первый алгоритм решает задачу кластеризации данных с заранее заданным числом кластеров. Второй алгоритм разбивает объекты на кластеры заданного радиуса. Приводится подробное описание видов операторов инициализации, скрещивания, мутации и селекции и схема работы для обоих предложенных алгоритмов кластеризации данных.
Было разработано программное приложение, реализующее работу предложенных алгоритмов кластеризации, а также классических алгоритмов k-средних и FOREL.
В работе проводится сравнение предложенных генетических алгоритмов и классических алгоритмов (k-средних и FOREL) по их вычислительной сложности. Выполняется серия численных экспериментов, позволяющих оценить работу разработанных алгоритмов на ряде тестовых примеров. Полученные результаты кластеризации сравниваются с результатами вышеперечисленных классических алгоритмов кластеризации для тех же тестовых примеров.
В работе решается практический пример кластеризации данных - кластеризация 50 ведущих российских банков по основным показателям их финансовой деятельности. Данная задача решается с помощью разработанных генетических алгоритмов и классических алгоритмов (к- средних и FOREL). Исследование основывается на реальных статистических данных. Проводится сравнение результатов работы методов и анализ полученных результатов.
В работе получены следующие результаты:
►Изучены основные алгоритмы кластеризации многомерных данных.
►Реализованы методы кластеризации k-средних и FOREL.
► Разработан генетический алгоритм для решения задачи кластеризации многомерных данных с заданным количеством кластеров.
► Разработан генетический алгоритм для решения задачи кластеризации с заданным размером кластеров.
► Создано программное приложение, реализующее работу предложенных алгоритмов, а также изученных классических алгоритмов кластеризации.
► Проведено сравнение изученных и предложенных методов по их вычислительной сложности и результатам работы.
►Решена практическая задача кластеризации 50 российских банков по показателям их финансовой деятельности.
► Проведено сравнение результатов, полученных в результате работы каждого метода.
Результаты работы докладывались и опубликованы на международной научно-технической конференции студентов, аспирантов и молодых ученых «Проспект Свободный - 2015» (г. Красноярск, 2015), на международной научно-технической конференции студентов, аспирантов и молодых ученых «Проспект Свободный - 2016» (г. Красноярск, 2016).
