Давайте сначала разберемся с некоторыми важными концепциями.
Евклидово расстояние
Сходство между наблюдениями измеряется с помощью показателя, называемого Евклидово расстояние.
Евклидово расстояние между двумя точками (x1, y1) и (x2, y2) рассчитывается следующим образом:
Итак, на приведенном выше рисунке евклидово расстояние между двумя точками (1, 4) и (4, 1) равно:
Центроид
Центр кластера называется центроидом. Он рассчитывается как среднее значение координат всех точек данных в кластере. Например, предположим, что у нас есть 3 точки данных в кластере, (x1, y1), (x2, y2), (x3, y3). Координаты центроида (X, Y) рассчитываются как:
Теперь предположим, что у вас есть набор точек данных, которые нужно сгруппировать в 2 кластера. Алгоритм кластеризации K-средних работает следующим образом:
- Произвольно выберите два центроида для данного набора точек, так как мы хотим иметь два кластера.
- Назначьте каждую точку данных каждому центроиду, что означает вычисление евклидова расстояния каждой точки данных от каждого центроида. Этот шаг называется Назначение.
- Теперь каждая точка принадлежит кластеру 1 или 2 в зависимости от евклидовых расстояний. Основываясь на этой группировке, вычислите новые центроиды по указанной выше формуле для центроидов. Этот шаг называется Оптимизация.
- Повторно сформируйте кластеры на основе вышеуказанных координат центроида.
Шаги присвоения и оптимизации повторяются (называемые итерациями) до тех пор, пока координаты центроида не останутся неизменными или алгоритм не сойдется.
Алгоритм K Means ++
В алгоритме K-средних мы произвольно выбираем начальные центроиды в зависимости от количества кластеров, которые мы хотим сформировать. Алгоритм K-Means ++ - более разумный способ определения этих начальных центроидов. Это следующие шаги:
- Определите желаемое количество кластеров, которые нужно сформировать (скажем, 3), и выберите любую точку в наборе точек данных в качестве первого центроида.
- Вычислите евклидовы расстояния до каждой точки данных от этого первого центроида и возведите их в квадрат.
- В зависимости от полученных значений выберите самую дальнюю точку данных в качестве второго центроида.
- Повторите процесс на шаге 2, на этот раз для обоих центроидов и выберите самую дальнюю точку в качестве третьего центроида.
Алгоритм K Means ++ помогает алгоритму K Means сходиться быстрее, то есть количество итераций, необходимых для получения окончательных центроидов, меньше по сравнению со случайным выбором начальных центроидов.
Некоторые недостатки, которые следует учитывать при использовании алгоритма K-средних:
- Количество формируемых кластеров должно быть определено изначально.
- Выбранные начальные центроиды определяют, как кластеры будут формироваться в конце.
- Кроме того, поскольку алгоритм K-средних интуитивно чувствителен к выбросам, выбросы будут препятствовать формированию оптимальных кластеров.
Метод локтя и метод оценки по силуэту
Иногда бывает сложно определить количество кластеров, просто взглянув на данные. Чтобы найти оптимальное количество кластеров для кластеризации K-средних, пригодятся два метода: метод локтя и метод оценки по силуэту. Оба метода дают нам количество кластеров, которые могут быть сформированы, в зависимости от наших данных.
График изгиба - это график между SSD (суммой квадратов расстояний) от каждой точки до назначенного ей центра и количеством кластеров. Это похожий на руку график, который изгибается при определенном значении числа кластеров. Предполагается, что это значение будет наилучшей оценкой для начального количества кластеров, которые будут учитываться при кластеризации K-средних.
Оценка силуэта отображает степень близости каждой точки в одном кластере к точкам в соседних кластерах. В основном он измеряет качество сформированных кластеров. Если имеется 2 кластера, в идеале межкластерное расстояние между точками данных двух кластеров должно быть большим, а внутрикластерное расстояние между точками данных в кластере должно быть ниже. Оценка силуэта рассчитывается по следующей формуле:
Где:
a - это среднее расстояние от точки данных до точек в ближайшем кластере, частью которого эта точка данных не является.
b - это среднее расстояние внутри кластера до всех точек в собственном кластере.
Поэтому в идеале a должно быть максимальным, а b - минимальным.
Значение диапазона оценки силуэта находится в диапазоне от -1 до 1. Оценка, близкая к 1, указывает на то, что точка данных очень похожа на другие точки данных в кластере. Оценка, близкая к -1, указывает на то, что точка данных не похожа на точки данных в своем кластере.
Иерархическая кластеризация
Мы видели, что в алгоритме кластеризации K-средних количество кластеров, которые необходимо сформировать, должно было определяться в самом начале. В иерархической кластеризации дело обстоит иначе. Здесь происходит серия слияний или разделений точек данных, в зависимости от того, какой тип иерархической кластеризации мы используем. Существует два типа иерархической кластеризации: Агломеративная и Разделительная.
Результат иерархической кластеризации называется дендрограммой. Агломеративный подход - это подход снизу вверх, в то время как разделительный подход - это подход сверху вниз.
Давайте подробно обсудим агломерационный подход. Разделительный подход прямо противоположен агломеративному подходу.
Предположим, у нас есть N точек данных. Шаги в агломеративной иерархической кластеризации следующие:
- Первоначально каждая точка рассматривается как отдельный кластер. Итак, у нас есть N кластеров.
- Рассчитываются расстояния каждой точки от каждой другой точки и формируется матрица NxN.
- Две точки, между которыми находится наименьшее расстояние, группируются вместе.
- Затем два кластера с наименьшим расстоянием между ними объединяются.
- Шаг 4 повторяется до тех пор, пока не будет сформирован один большой кластер, содержащий все точки данных.
Это слияние кластеров зависит от того, какой тип связи выполняется. Есть 3 типа связей:
- Одинарная связь: два кластера объединяются в зависимости от кратчайшего расстояния между точками в двух кластерах.
- Полная связь: два кластера объединяются в зависимости от наибольшего расстояния между точками в двух кластерах.
- Средняя связь: два кластера объединяются в зависимости от среднего расстояния между каждой точкой одного кластера и каждой другой точкой другого кластера.
После того, как дендрограмма сформирована, следующим шагом будет вырезание дендрограммы на соответствующем уровне. Количество точек, в которых линия разреза пересекает дендрограмму, дает нам количество сформированных кластеров.
Здесь мы видим, что линия разреза пересекает дендрограмму в 4 точках, так что у нас есть четыре кластера. Если бы мы разрезали дендрограмму в строке № 5 или выше, у нас было бы 2 кластера.
Основное преимущество иерархической кластеризации состоит в том, что нам не нужно изначально определять количество кластеров. Недостаток в том, что это сложно и требует много времени.
Реализация Python кластеризации средств K и иерархической кластеризации.
У нас есть набор данных НПО. НПО собрала средства и хочет передать их странам, которые остро нуждаются в помощи. Нам необходимо классифицировать страны, используя некоторые социально-экономические факторы и факторы здоровья, которые определяют общее развитие страны, и определить 5 стран, которые больше всего нуждаются в помощи. Весь код Python с графиками присутствует в моем профиле GitHub, ссылка приведена в конце статьи.
Наша цель - построить модели кластеризации с использованием алгоритмов K-средних и иерархической кластеризации, чтобы найти список из 5 стран, которые остро нуждаются в помощи.
Начнем с импорта необходимых библиотек.
Мы загружаем данные во фрейм данных pandas и называем его «ngo». Мы используем этот фрейм данных для EDA (исследовательский анализ данных).
Базовый анализ показывает, что фрейм данных состоит из 167 строк и 10 столбцов. Кроме того, данные чистые и отсутствуют пропущенные значения.
Анализ выбросов показывает, что столбцы child_mort, gdpp и доход имеют выбросы. Убираем выбросы.
Мы выполняем одномерный, двумерный и многомерный анализ, как показано.
Построение модели кластеризации
Нам необходимо сформировать кластеры, сравнив, как переменные - gdpp, child_mort и доход различаются для каждого кластера стран, чтобы распознать и дифференцировать кластеры развитые страны из кластера слаборазвитых стран.
Мы формируем новый фрейм данных new_df, отфильтровывая вышеупомянутые столбцы. Далее этот фрейм данных масштабируется с помощью пакета sklearn формы StandardScaler.
Для построения любой модели кластеризации в первую очередь важно проверить, можно ли сформировать эффективные кластеры с имеющимися данными. Это определяется с помощью оценки Хопкина. Чем больше балл, тем лучше тенденция к формированию кластеров в данных. По нашим данным, оценка Хопкина составляет 91% или 0,91. Таким образом, эти данные можно использовать для формирования хороших кластеров.
- Кластеризация средств
Нам нужно решить, сколько кластеров нужно сформировать в самом начале. Мы используем метод локтя и метод оценки по силуэту, чтобы определить то же самое.
Из обоих методов мы решили выбрать 3 в качестве оптимального номера кластера.
Из алгоритма K средних мы получаем следующие 3 кластера:
Образованные таким образом кластеры выглядят следующим образом:
- кластер нет. 0: умеренная детская смертность, средний доход, средний ВВП.
- кластер нет. 1: низкая детская смертность, высокий доход, высокий ВВП.
- кластер нет. 2: высокая детская смертность, низкий доход, низкий ВВП.
Кластер нет. 2 даст нам желаемый результат.
Итак, страны, которые остро нуждаются в помощи:
- Бурунди
- Либерия
- Конго, Дем. Представитель
- Нигер
- Мадагаскар
Теперь посмотрим, какой результат мы получим при использовании иерархической кластеризации.
2. Иерархическая кластеризация
У нас уже есть масштабированные данные в new_df_scaled. Используя Complete Linkage, мы генерируем дендрограмму.
Мы вырезаем дендрограмму в строке № 4 и выберите 4 как оптимальное значение кластера. Получаем следующие кластеры:
Таким образом сформированы четыре кластера:
- кластер нет. 0: высокая детская смертность, самый низкий диапазон доходов, самый низкий диапазон ВВП.
- кластер нет. 1: средняя детская смертность, диапазон доходов от низкого до среднего, диапазон ВВП от низкого до среднего.
- кластер нет. 2: низкая детская смертность, умеренный диапазон доходов, умеренный ВВП
- кластер нет. 3: самый низкий диапазон детской смертности, очень высокий диапазон доходов, очень высокий ВВП
Кластер нет. 0 даст нам желаемый результат.
Итак, пять стран, которые остро нуждаются в помощи, это:
- Бурунди
- Либерия
- Конго, Дем. Представитель
- Нигер
- Мадагаскар
Заключение. Мы видим, что, хотя количество кластеров, сформированных с помощью кластеризации с использованием метода K-средних и иерархической кластеризации, различается, оба алгоритма дали одинаковый результат.
Надеюсь, статья была информативной и легкой для понимания. Также я надеюсь, что вам понравились красочные графики, включенные в анализ.
Не стесняйтесь комментировать и оставлять отзывы.
Вы можете связаться со мной в LinkedIn: https://www.linkedin.com/in/pathakpuja/
Посетите мой профиль GitHub, чтобы найти коды Python: https://github.com/pujappathak