Введение
Постановка задачи 6
0. Кластеризация 8
0.1 Иерархическая кластеризация 10
0.2 Методы иерархической кластеризации 12
0.2.1 Одиночная связь 12
0.2.2 Полная связь 12
0.2.3 Групповое среднее 13
0.2.4 Среднее расстояние 13
0.2.5 Расстояние Уорда (Варда) 13
0.2.6 Медианное расстояние 14
0.2.7 Расстояние Хаусдорфа 14
0.3 Формула Ланса-Уильямса 15
0.4 Реализация 16
0.5 Генерирование выборки 20
1. Качество кластеризации 25
1.1 Функционал качества кластеризации 25
1.2 Кластерная валидация 26
1.2.1 Индексы кластерной валидации 28
1.2.2 Особенности индексов кластерной валидации 34
2.4 Результаты экспериментов 36
2. Расстояния 44
2.1 Ультраметричность и метричность 46
2.1.1 Результаты экспериментов 49
2.2 Расстояния между точками в многомерном пространстве 51
2.2.1 Результаты экспериментов 53
2.3 Трансформация расстояний 60
2.3.1 Результаты экспериментов 61
2.4 Ультраметрики, порождаемые иерархической кластеризацией 66
2.4.1 Исследования и результаты 68
2.5 Субдоминантная ультраметрика 72
2.5.1 Субдоминантная ультраметрика в иерархической кластеризации 72
2.5.2 Субдоминантная ультраметрика и минимальное покрывающее дерево 74
2.5.3 Исследования и результаты 77
3. Интерфейс и дополнительные возможности 80
Заключение 87
Список литературы 89
Приложение 91


Купить

Анализ данных применяется во многих областях науки и техники, таких как биоинформатика, анализ изображений [7], генетика, финансы и электротехника. Возросший интерес к анализу данных порождает много новых методов, порой сложных и имеющих свои недостатки и проблемы.
Одним из самых полезных методов является кластеризация для обнаружения групп и выявления интересных распределений и шаблонов в данных. Кластерный анализ (или кластеризация) - это задача группировки набора объектов таким образом, что объекты, попавшие в одну группу (называемую кластером) более схожи между собой, а объекты разных групп максимально различны.
Одной из основных проблем кластеризации является способ оценки результатов без использования дополнительной информации. Это необходимо как для сравнения работы различных алгоритмов кластеризации, так и для выявления наилучшего разбиения. Распространенным методом оценки результатов является применение функционалов качества кластеризации и индексов кластерной валидации.
Второй, не менее важной проблемой является оценка расстояний между объектами для кластеризации. Далеко не всегда матрица расстояний между объектами является метричной, что затрудняет оценку степени несходства между объектами. Возникает вопрос о существовании метрик или ультраметрик, аппроксимирующих исходное расстояние.
В данной магистерской диссертации будут рассмотрены 7 алгоритмов иерархической кластеризации. Это одиночная связь, полная связь, групповое среднее, среднее расстояние, расстояние Уорда, медианное расстояние и расстояние Хаусдорфа. Будет проведена оценка качества каждого алгоритма иерархической кластеризации, а также анализ индексов кластерной валидации для поиска наилучшего разбиения.
Будут введены понятия метричности и ультраметричности пространства и расстояний, рассмотрена зависимость качества разбиений от начального расстояния на множестве объектов, а также исследована зависимость метричности и ультраметричности исходного множества и качества кластерного разбиения.
Кроме того, в данной магистерской диссертации будут исследованы преобразования, которые могут повысить степень ультраметричности расстояний. Будет рассмотрено влияние этих преобразований на качество кластеризации в различных алгоритмах иерархической кластеризации.
Также будут исследованы ультраметрики, порождаемые алгоритмами иерархической кластеризации и произведен поиск ультраметрики, наилучшим образом аппроксимирующей исходное расстояние. Будет определено понятие субдоминантной ультраметрики и ее свойства.
Постановка задачи
В магистерской диссертации были поставлены следующие задачи:
1. Исследование и программная реализация 7 алгоритмов иерархической кластеризации
2. Оценка качества 7 алгоритмов иерархической кластеризации
3. Изучение и реализация функционала качества и индексов кластерной валидации
4. Исследование влияния различных расстояний между точками на качество кластерного разбиения
5. Исследование влияния трансформаций расстояний на качество кластеризации
6. Исследование ультраметрик, порождаемых иерархической кластеризацией и сравнение их с исходным расстоянием
7. Изучение и построение субдоминантной ультраметрики
8. Возможность кластеризовать реальные данные
9. Реализация программного комплекса, выполняющего поставленные задачи
В данной магистерской диссертации были найдены ответы на следующие вопросы:
• Какие алгоритмы иерархической кластеризации порождают ультраметрики?
• Какая из аппроксимаций исходного расстояния является наилучшей?
• Каково влияние степени метричности и ультраметричности пространства на качество кластерного разбиения?
• Как оценить кластерное разбиение и определить оптимальное число кластеров?
Для выполнения поставленных задач была изучена литература по методам иерархической кластеризации, ультраметричности, функционалам качества кластеризации, индексам кластерной валидации, видам расстояний в многомерном пространстве, способам трансформации расстояний, субдоминантной ультраметрике. А также был разработан программный комплекс, реализующий поставленные задачи, проведено большое количество экспериментов, анализ результатов и оформление выводов.
Программный комплекс был написан на языке C# в среде VisualStudio 2017 с использованием .NET Framework версии 4.5.2.
Купить