Аннотация 2
Введение 3
1. Кластеризация 5
1.1. Меры расстояний 5
1.2. Понятие алгоритма кластеризации 6
1.3. Виды алгоритмов 8
2. Алгоритм K-средних 10
2.1. Описание алгоритма 10
2.2. Зависимость алгоритма K-средних от начальных приближений
центров 12
2.3. Вычислительная сложность 14
3. Агломеративная иерархическая кластеризация 16
3.1. Обобщенный алгоритм 16
3.2. Симметричная функция подобия R 16
Заключение 21
Список использованных источников и литературы 22
Приложение А 23
Приложение Б 25
Приложение В 28
Методы статистического анализа многомерных данных появились еще в начале ХХ века. Но из-за сложности и большого объема вычислений они получили широкое распространение только после создания компьютеров. Специальные методы статистического анализа многомерных данных необходимы для облегчения понимания закономерностей функционирования не до конца исследованных сложных социально-экономических процессов. Также они могут использоваться как инструмент анализа многомерных реальных, стремительно меняющихся ситуаций.
Одним из таких методов является кластерный анализ. Другое его название - кластеризация.
Определение. Кластеризация - это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп этих точек [1].
В данной работе проводится исследование алгоритмов кластеризации, в основе которых лежит объединение разрозненных данных в группы.
Цель исследования: реализация алгоритмов кластеризации методом k- средних и иерархической кластеризации на языке Python [2] с последующим сравнением вычислительной сложности данных алгоритмов.
Задачи:
1. Изучение литературы по теме «Кластерный анализ»;
2. Изучение популярных алгоритмов кластеризации;
3. Оценивание вычислительной сложности исследуемых алгоритмов;
4. Проведение сравнения алгоритмов по сложности;
5. Освоение языка Python;
6. Создание программ на языке Python, отражающих работу исследуемых алгоритмов.
Методы исследования: использование языка Python и методов теории алгоритмов, в том числе оценку вычислительной сложности.
Python - универсальный язык программирования с большими возможностями. Для него характерны краткость синтаксиса и читабельность кода, а значит программы, написанные на языке Python, отличаются компактностью и лаконичностью.
В июне 2019 года редакторы TIOBE Index [3] заявили: «В этом месяце Python снова достиг высочайшей позиции в TIOBE Index, его результат составил 8,5 %. Если Python удержит такой темп, то в течение ближайших трех-четырех лет он сможет заменить С и Java, став самым популярным языком программирования в мире».[4] А уже в мае 2022 года язык Python стал самым популярным языком программирования по версии TIOBE Index.
У данного языка можно выделить следующие особенности [5]:
1. Интерпретируемость. Программы выполняются построчно, без предварительной компиляции.
2. Строгость и лаконичность. В языке отсутствуют избыточные конструкции, но в то же время его работа зависит от правильной расстановки пробелов и отступов.
3. Присутствие возможностей объектно-ориентированного
программирования.
4. Тип переменной изменяется вместе с данными, присваиваемыми данной переменной.
5. Большой набор стандартных библиотек.
В работе представлено исследование, проводимое с использованием языка Python, алгоритмов кластеризации, выполняющих объединение объектов выборки Ас = {х”, ...,х”}, где х” = {х^1, •••x^eR”, i = 1,t в заданное количество кластеров.
При исследовании результатов, полученных при разбиении выборки на некоторое количество кластеров с помощью алгоритма K-средних, было подтверждено, что точность разбиения зависит от начальных приближений центров будущих кластеров.
Также было установлено, что среди алгоритмов агломеративной иерархической кластеризации, кластеризация с использованием расстояния Уорда.
На основе данных о вычислительной сложности исследуемых алгоритмов сделан вывод о том, что алгоритм K-средних будет более эффективен, нежели алгоритмы агломеративной кластеризации, при больших объемах выборки. В то же время отсутствие требований алгоритмов агломеративной иерархической кластеризации к заданию начальных приближений центров уменьшает вероятность возникновения недостоверных результатов.
