ВВЕДЕНИЕ 3
1 АНАЛИЗ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ ДАННЫХ 6
1.1 Сравнение алгоритмов кластеризации данных 6
1.2 Основные элементы задачи оптимизации 8
2 РАЗРАБОТКА ПРИНЦИПОВ КЛАСТЕРИЗАЦИИ ДАННЫХ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ 13
2.1 Анализ математического аппарата эволюционных вычислений 13
2.2 Функции для тестирования работы генетических алгоритмов 35
2.3 Результаты анализа принципов работы генетического алгоритма 41
2.4 Синтез алгоритма кластеризации на основе эволюционных вычислений 44
3 МОДЕЛИРОВАНИЕ АЛГОРИТМА КЛАСТЕРИЗАЦИИ 49
3.1 Программное моделирование предложенного алгоритма кластеризации 49
3.2 Вычислительный эксперимент 51
3.3 Обсуждение результатов 59
ЗАКЛЮЧЕНИЕ 60
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 62
Актуальность исследования определена необходимостью совершенствования алгоритмов кластеризации данных для повышения их точности работы.
Использование алгоритмов кластеризации данных связано с решением различных практических задач, таких, например, как сегментация изображения, которая связана с кластеризацией его составных элементов - пикселей. Другой пример - подготовка обучающей выборки при создании классификатора, которая связана с предварительной кластеризацией данных для оценки их состава.
Алгоритмы машинного обучения в настоящее время активно развиваются. К ним относятся генетические алгоритмы (подобласть - «обучение с подкреплением»). Однако в настоящее время не изучена возможность применения генетических алгоритмов для решения задач кластеризации данных.
Цель исследования - разработка способа кластеризации данных, основанного на применении эволюционных вычислений.
Объектом исследования является кластеризация данных, предметом исследования - разработка методики использования генетического алгоритма для кластеризации данных.
Гипотезой исследования является предположение, что генетические алгоритмы, предназначенные для решения задач оптимизации, можно адаптировать для выполнения кластеризации данных.
Поставленная цель достигалась путем последовательного решения следующих задач:
1. Проведение анализа состояния вопроса по теме исследования.
2. Разработка методики по использования генетического алгоритма для кластеризации данных.
3. Разработка программной реализации для моделирования работы генетического алгоритма, основанного на предложенных подходах.
4. Проведение вычислительных экспериментов для оценки эффективности применения генетического алгоритма при кластеризации данных.
Исследованиями в области совершенствования алгоритмов кластеризации занимаются такие современники как: Kanzawa Y., Bao L., Oshio S., Chaimontree S., Yan Q., Ryazanov V., LaPlante F., Handl J., Yang X., Araujo D., Aszalos L., Almutairi N., Zhang Y., Zhu Q., Jin H., Vega-Pons S., Bhattacharyya D., Daliri M., Castellani U., Boryczka U. и др.
В ходе выполнения работы применялись такие методы теоретического исследования, как изучение и анализ научной литературы по проблемам кластеризации данных и вопросам практического использования генетических алгоритмов.
Также в ходе выполнения работы применялись практические методы исследования, такие как проведение вычислительных экспериментов, обработка статистических данных, программное моделирование работы генетических алгоритмов.
Научная новизна исследования - доказано, что генетические алгоритмы можно адаптировать под решение задачи кластеризации данных. При этом возможность генетического алгоритма выходить из локальных решений позволяет получать кластерные структуры лучше (с точки зрения плотности), чем при использовании алгоритма k-means.
Практическая значимость работы заключается в разработке методики применения генетических алгоритмов для решения задач кластеризации данных.
Апробация результатов исследования проходила на базе V Международной научно-практической конференции (школы-семинара) молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук».
На защиту выносятся:
1. Методика применения генетического алгоритма для кластеризации данных.
2. Результаты апробации предложенной методики.
В рамках написания магистерской диссертации были опубликованы следующие статьи:
1. Перспективы использования эволюционных вычислений при кластеризации данных [41].
2. Кластеризация изображения на основе оценки геометрической формы объектов [42].
В рамках выполнения магистерской диссертации разработано программное обеспечение для моделирования генетических алгоритмов и для кластеризации данных с использованием предложенных подходов. Результаты тестирование программного обеспечения показали состоятельность предложенной в диссертации методики кластеризации данных с использованием эволюционных вычислений.
1. В обзор литературных источников по теме исследования позволил установить, что при решении практических задач из различных областей науки техники требуется выполнение кластеризации данных (например, при сегментации изображений кластеризации подвергаются его пиксели). По этой причине актуальной задачей остается развитие методов кластеризации данных.
2. Генетические алгоритмы предназначены для решения задач оптимизации. В исследовании предложены подходы, позволяющие представить задачу кластеризации, как задачу оптимизации кластерной структуры. Данные подходы включают в себя использования в качестве целевой функции сумму квадратов расстояний от объектов кластеризации до центра ближайшего кластера (при этом решается задача минимизации значения функции). В качестве входных параметров функции предложено использовать координаты центров кластеров. Данные подходы позволяют применять различные методы оптимизации, но уже для кластеризации данных.
3. Проведено исследования математического аппарата генетических алгоритмов, по результатам которого был сделан вывод о возможности его использования при кластеризации данных (раздел 2.3). Также произведен синтез конфигурации генетического алгоритма, направленный на решения задачи кластеризации данных (раздел 2.4).
4. Разработано программное обеспечение для моделирования генетических алгоритмов и для кластеризации данных с использованием предложенных подходов (раздел 3.1).
5. Для апробации предложенной конфигурации генетического алгоритма в рамках решения задачи кластеризации данных были проведены вычислительные эксперименты (раздел 3.2). Результаты экспериментов (см. раздел 3.3) показывают состоятельность предложенных подходов.
Основные результаты работы были доложены на V Международной научно-практической конференции (школы-семинара) молодых ученых «Прикладная математика и информатика: современные исследования в области естественных и технических наук».
Также в рамках написания магистерской диссертации были опубликованы следующие статьи:
1. Перспективы использования эволюционных вычислений при кластеризации данных [41].
2. Кластеризация изображения на основе оценки геометрической формы объектов [42].
Помощь студентам и аспирантам в выполнении работ от наших партнеров
