Давайте сначала разберемся с некоторыми важными концепциями.

Евклидово расстояние

Сходство между наблюдениями измеряется с помощью показателя, называемого Евклидово расстояние.

Евклидово расстояние между двумя точками (x1, y1) и (x2, y2) рассчитывается следующим образом:

Итак, на приведенном выше рисунке евклидово расстояние между двумя точками (1, 4) и (4, 1) равно:

Центроид

Центр кластера называется центроидом. Он рассчитывается как среднее значение координат всех точек данных в кластере. Например, предположим, что у нас есть 3 точки данных в кластере, (x1, y1), (x2, y2), (x3, y3). Координаты центроида (X, Y) рассчитываются как:

Теперь предположим, что у вас есть набор точек данных, которые нужно сгруппировать в 2 кластера. Алгоритм кластеризации K-средних работает следующим образом:

  1. Произвольно выберите два центроида для данного набора точек, так как мы хотим иметь два кластера.
  2. Назначьте каждую точку данных каждому центроиду, что означает вычисление евклидова расстояния каждой точки данных от каждого центроида. Этот шаг называется Назначение.
  3. Теперь каждая точка принадлежит кластеру 1 или 2 в зависимости от евклидовых расстояний. Основываясь на этой группировке, вычислите новые центроиды по указанной выше формуле для центроидов. Этот шаг называется Оптимизация.
  4. Повторно сформируйте кластеры на основе вышеуказанных координат центроида.

Шаги присвоения и оптимизации повторяются (называемые итерациями) до тех пор, пока координаты центроида не останутся неизменными или алгоритм не сойдется.

Алгоритм K Means ++

В алгоритме K-средних мы произвольно выбираем начальные центроиды в зависимости от количества кластеров, которые мы хотим сформировать. Алгоритм K-Means ++ - более разумный способ определения этих начальных центроидов. Это следующие шаги:

  1. Определите желаемое количество кластеров, которые нужно сформировать (скажем, 3), и выберите любую точку в наборе точек данных в качестве первого центроида.
  2. Вычислите евклидовы расстояния до каждой точки данных от этого первого центроида и возведите их в квадрат.
  3. В зависимости от полученных значений выберите самую дальнюю точку данных в качестве второго центроида.
  4. Повторите процесс на шаге 2, на этот раз для обоих центроидов и выберите самую дальнюю точку в качестве третьего центроида.

Алгоритм K Means ++ помогает алгоритму K Means сходиться быстрее, то есть количество итераций, необходимых для получения окончательных центроидов, меньше по сравнению со случайным выбором начальных центроидов.

Некоторые недостатки, которые следует учитывать при использовании алгоритма K-средних:

  1. Количество формируемых кластеров должно быть определено изначально.
  2. Выбранные начальные центроиды определяют, как кластеры будут формироваться в конце.
  3. Кроме того, поскольку алгоритм K-средних интуитивно чувствителен к выбросам, выбросы будут препятствовать формированию оптимальных кластеров.

Метод локтя и метод оценки по силуэту

Иногда бывает сложно определить количество кластеров, просто взглянув на данные. Чтобы найти оптимальное количество кластеров для кластеризации K-средних, пригодятся два метода: метод локтя и метод оценки по силуэту. Оба метода дают нам количество кластеров, которые могут быть сформированы, в зависимости от наших данных.

График изгиба - это график между SSD (суммой квадратов расстояний) от каждой точки до назначенного ей центра и количеством кластеров. Это похожий на руку график, который изгибается при определенном значении числа кластеров. Предполагается, что это значение будет наилучшей оценкой для начального количества кластеров, которые будут учитываться при кластеризации K-средних.

Оценка силуэта отображает степень близости каждой точки в одном кластере к точкам в соседних кластерах. В основном он измеряет качество сформированных кластеров. Если имеется 2 кластера, в идеале межкластерное расстояние между точками данных двух кластеров должно быть большим, а внутрикластерное расстояние между точками данных в кластере должно быть ниже. Оценка силуэта рассчитывается по следующей формуле:

Где:

a - это среднее расстояние от точки данных до точек в ближайшем кластере, частью которого эта точка данных не является.

b - это среднее расстояние внутри кластера до всех точек в собственном кластере.

Поэтому в идеале a должно быть максимальным, а b - минимальным.

Значение диапазона оценки силуэта находится в диапазоне от -1 до 1. Оценка, близкая к 1, указывает на то, что точка данных очень похожа на другие точки данных в кластере. Оценка, близкая к -1, указывает на то, что точка данных не похожа на точки данных в своем кластере.

Иерархическая кластеризация

Мы видели, что в алгоритме кластеризации K-средних количество кластеров, которые необходимо сформировать, должно было определяться в самом начале. В иерархической кластеризации дело обстоит иначе. Здесь происходит серия слияний или разделений точек данных, в зависимости от того, какой тип иерархической кластеризации мы используем. Существует два типа иерархической кластеризации: Агломеративная и Разделительная.

Результат иерархической кластеризации называется дендрограммой. Агломеративный подход - это подход снизу вверх, в то время как разделительный подход - это подход сверху вниз.

Давайте подробно обсудим агломерационный подход. Разделительный подход прямо противоположен агломеративному подходу.

Предположим, у нас есть N точек данных. Шаги в агломеративной иерархической кластеризации следующие:

  1. Первоначально каждая точка рассматривается как отдельный кластер. Итак, у нас есть N кластеров.
  2. Рассчитываются расстояния каждой точки от каждой другой точки и формируется матрица NxN.
  3. Две точки, между которыми находится наименьшее расстояние, группируются вместе.
  4. Затем два кластера с наименьшим расстоянием между ними объединяются.
  5. Шаг 4 повторяется до тех пор, пока не будет сформирован один большой кластер, содержащий все точки данных.

Это слияние кластеров зависит от того, какой тип связи выполняется. Есть 3 типа связей:

  1. Одинарная связь: два кластера объединяются в зависимости от кратчайшего расстояния между точками в двух кластерах.
  2. Полная связь: два кластера объединяются в зависимости от наибольшего расстояния между точками в двух кластерах.
  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. Таким образом, эти данные можно использовать для формирования хороших кластеров.

  1. Кластеризация средств

Нам нужно решить, сколько кластеров нужно сформировать в самом начале. Мы используем метод локтя и метод оценки по силуэту, чтобы определить то же самое.

Из обоих методов мы решили выбрать 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