Введение 4
1 Задача кластеризации данных 6
1.1 Понятие кластеризации 6
1.2 Постановка задачи кластеризации 8
1.3 Метрики для задания кластеров 11
1.4 Критерии качества кластеризации 12
1.5 Типы кластерных структур 15
2 Классические методы решения задачи кластеризации данных 19
2.1 Обзор методов кластеризации 19
2.2 Метод k-средних 23
3 Генетические алгоритмы 27
3.1 Основные понятия генетических алгоритмов 27
3.2 Классический генетический алгоритм 28
3.3 Генетический алгоритм кластеризации с детерминированным числом кластером 34
3.4 Сравнение предложенного генетического алгоритма с методом k-средних 36
4 Исследование влияния параметров генетического алгоритма на скорость
его работы 37
5 Решение практической задачи кластеризации 40
5.1 Описание статистики 40
5.2 Решение задачи кластеризации методом k-средних и генетическим
алгоритмом кластеризации с детерминированным числом кластеров 40
5.3 Сравнение полученных результатов 43
5.4 Визуализация результатов 45
Заключение 47
Список использованных источников 48
Приложение А 50
Целью бакалаврской работы является разработка генетического алгоритма, решающего задачу кластеризации многомерных статистических данных.
Задача кластеризации данных [14] является одной из наиболее актуальных и сложных задач анализа данных. Кластерный анализ [15] представляет собой раздел статистического анализа, объединяющий методы разбиения совокупности объектов на однородные группы, называемые кластерами. Его методы имеют широкий спектр применений практически во всех областях человеческой деятельности, связанных с изучением объектов и процессов: медицине, биологии, психологии, социологии, менеджменте, маркетинге, банковском деле, актуарной математике и других.
В первой главе работы приводятся основные понятия и постановка за-дачи кластеризации данных. Перечисляются виды наиболее часто выделяемых кластерных структур и критерии качества кластеризации. Во второй главе проводится обзор существующих методов кластеризации данных. Особое внимание в работе уделяется наиболее популярному методу кластеризации данных: методу k-средних [6]. Дается подробное описание данного алгоритма, и указываются особенности его работы.
В третьей главе излагаются принципы работы генетических алгоритмов [7], являющихся эвристическими алгоритмами поиска, широко используемыми для решения задач оптимизации и моделирования путём случайного подбора и вариации параметров с использованием механизмов, аналогичных естественному отбору в природе. В работе рассматриваются назначение и виды основных операторов генетических алгоритмов, в том числе операторы скрещивания, мутации и селекции. Приводится общий вид схемы этапов работы генетического алгоритма.
В работе предлагается генетический алгоритм, позволяющий решать задачу кластеризации многомерных данных с заранее заданным числом кластеров. Приводится подробное описание вида операторов инициализации, скрещивания, мутации и селекции, а также последовательность этапов работы предложенного генетического алгоритма кластеризации.
Было разработано программное приложение, реализующее работу предложенного генетического алгоритма кластеризации и классического алгоритма k-средних. Выполняется серия численных экспериментов, позволяющих оценить работу разработанного алгоритма на ряде тестовых примеров.
В работе проводится сравнение предложенного генетического алгоритма и классического алгоритма k-средних по их вычислительной сложности.
Проводится исследование влияния параметров операторов скрещивания и мутации на скорость работы генетического алгоритма.
В работе решается практический пример кластеризации данных- кластеризация 57 муниципальных районов Красноярского края по четырём экономическим показателям. Данная задача решается с помощью разработанных генетических алгоритмов и классического алгоритма k-средних. Исследование основывается на реальных статистических данных. Проводится сравнение результатов, полученных обоими методами.
В работе получены следующие результаты:
• Изучена задача кластеризации данных типа и основные алгоритмы кластеризации многомерных данных.
• Разработан генетический алгоритм для решения задачи кластеризации многомерных данных с заданным количеством кластеров.
• Создано программное приложение, реализующее работу предложенного алгоритма, а также алгоритма кластеризации k-средних.
• Проведено сравнение изученного и предложенного методов по их вы-числительной сложности и результатам работы.
• Проведено исследование влияния параметров генетического алгоритма на скорость его работы.
• Решена практическая задача кластеризации 57 муниципальных районов Красноярского края по четырём экономическим показателям
• Проведено сравнение результатов, полученных в результате работы каждого метода.
