Иерархическая кластеризация с помощью Python и Scikit-Learn

Автор оригинала: Usman Malik.

Иерархическая кластеризация-это тип неконтролируемого алгоритма машинного обучения, используемого для кластеризации немаркированных точек данных. Подобно K-means clustering , иерархическая кластеризация также группирует вместе точки данных с аналогичными характеристиками. В некоторых случаях результат иерархической кластеризации и кластеризации K-средних может быть сходным. Прежде чем реализовать иерархическую кластеризацию с помощью Scikit-Learn , давайте сначала разберемся в теории иерархической кластеризации.

Теория иерархической кластеризации

Существует два типа иерархической кластеризации: Агломеративная и Делительная. В первом случае точки данных группируются с использованием восходящего подхода, начиная с отдельных точек данных, в то время как во втором используется нисходящий подход, при котором все точки данных рассматриваются как один большой кластер, а процесс кластеризации включает в себя разделение одного большого кластера на несколько небольших кластеров.

В этой статье мы сосредоточимся на агломеративной кластеризации, которая включает в себя подход “снизу вверх”.

Шаги для выполнения иерархической кластеризации

Ниже приведены шаги, связанные с агломеративной кластеризацией:

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

Существуют различные способы определения расстояния между кластерами. Само расстояние может быть евклидовым или манхэттенским. Ниже приведены некоторые из вариантов измерения расстояния между двумя кластерами:

1. Измерьте расстояние между точками закрытия двух кластеров.
2. Измерьте расстояние между самыми дальними точками двух кластеров.
3. Измерьте расстояние между центроидами двух кластеров.
4. Измерьте расстояние между всеми возможными комбинациями точек между двумя кластерами и возьмите среднее.

Роль дендрограмм в иерархической кластеризации

В последнем разделе мы говорили, что как только один большой кластер образуется комбинацией небольших кластеров, дендрограммы кластера используются для фактического разделения кластера на несколько кластеров связанных точек данных. Давайте посмотрим, как это делается на самом деле.

Предположим, что у нас есть набор точек данных, представленных массивом numpy следующим образом:

import numpy as np

X = np.array([[5,3],
    [10,15],
    [15,12],
    [24,10],
    [30,30],
    [85,70],
    [71,80],
    [60,78],
    [70,55],
    [80,91],])

Давайте построим график приведенных выше точек данных. Для этого выполните следующий код:

import matplotlib.pyplot as plt

labels = range(1, 11)
plt.figure(figsize=(10, 7))
plt.subplots_adjust(bottom=0.1)
plt.scatter(X[:,0],X[:,1], label='True Position')

for label, x, y in zip(labels, X[:, 0], X[:, 1]):
    plt.annotate(
        label,
        xy=(x, y), xytext=(-3, 3),
        textcoords='offset points', ha='right', va='bottom')
plt.show()

Приведенный выше скрипт рисует точки данных в массиве X | numpy и помечает точки данных от 1 до 10. На рисунке ниже вы увидите, что график, который генерируется из этого кода:

Давайте назовем вышеприведенный график графиком 1. Невооруженным глазом видно, что точки данных образуют два кластера: первый в левом нижнем углу, состоящий из точек 1-5, а второй в правом верхнем углу, состоящий из точек 6-10.

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

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

from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt

linked = linkage(X, 'single')

labelList = range(1, 11)

plt.figure(figsize=(10, 7))
dendrogram(linked,
            orientation='top',
            labels=labelList,
            distance_sort='descending',
            show_leaf_counts=True)
plt.show()

Выходной график выглядит так, как показано ниже. Давайте назовем этот график Graph2.

Алгоритм начинается с нахождения двух ближайших друг к другу точек на основе евклидова расстояния. Если мы оглянемся на график 1, то увидим, что точки 2 и 3 находятся ближе всего друг к другу, а точки 7 и 8-ближе друг к другу. Поэтому сначала между этими двумя точками образуется кластер. На графике 2 вы можете видеть, что дендрограммы были созданы, соединяя точки 2 с 3 и 8 с 7. Вертикальная высота дендограммы показывает евклидовы расстояния между точками. Из графика 2 видно, что евклидово расстояние между точками 8 и 7 больше, чем расстояние между точками 2 и 3.

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

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

Мы видим, что наибольшее вертикальное расстояние без какой-либо горизонтальной линии, проходящей через него, представлено синей линией. Таким образом, мы рисуем новую горизонтальную красную линию, которая проходит через синюю линию. Поскольку он пересекает синюю линию в двух точках, следовательно, число кластеров будет равно 2.

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

На приведенном выше графике горизонтальная линия проходит через четыре вертикальные линии, в результате чего образуются четыре кластера: кластер точек 6,7,8 и 10, кластер точек 3,2,4 и точки 9 и 5 будут рассматриваться как одноточечные кластеры.

Иерархическая кластеризация с помощью Scikit-Learn

Достаточно теории, теперь давайте реализуем иерархическую кластеризацию с помощью библиотеки Scikit-Learn Python.

Пример 1

В нашем первом примере мы будем кластер X | numpy массив точек данных, которые мы создали в предыдущем разделе.

Процесс кластеризации аналогичен любому другому неконтролируемому алгоритму машинного обучения. Начнем с импорта необходимых библиотек:

import matplotlib.pyplot as plt
import pandas as pd
%matplotlib inline
import numpy as np

Следующим шагом является импорт или создание набора данных. В этом примере мы будем использовать следующие данные:

X = np.array([[5,3],
    [10,15],
    [15,12],
    [24,10],
    [30,30],
    [85,70],
    [71,80],
    [60,78],
    [70,55],
    [80,91],])

Следующим шагом является импорт класса для кластеризации и вызов его метода fit_predict для прогнозирования кластеров, к которым принадлежит каждая точка данных.

Взгляните на следующий сценарий:

from sklearn.cluster import AgglomerativeClustering

cluster = AgglomerativeClustering(n_clusters=2, affinity='euclidean', linkage='ward')
cluster.fit_predict(X)

В приведенном выше коде мы импортируем класс Agglomerative Clustering из библиотеки “sklearn.cluster”. Число параметров устанавливается равным 2 с помощью параметра n_clusters , а affinity – “евклидово” (расстояние между точками данных). Наконец, параметр linkage имеет значение “ward”, что минимизирует вариант между кластерами.

Далее мы вызываем метод fit_predict из Агломеративной кластеризации переменной класса cluster . Этот метод возвращает имена кластеров, к которым принадлежит каждая точка данных. Выполните следующий сценарий, чтобы увидеть, как были кластеризованы точки данных.

print(cluster.labels_)

Выход представляет собой одномерный массив из 10 элементов, соответствующих кластерам, назначенным нашим 10 точкам данных.

[1 1 1 1 1 0 0 0 0]

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

Наконец, давайте построим наши кластеры. Для этого выполните следующий код:

plt.scatter(X[:,0],X[:,1], c=cluster.labels_, cmap='rainbow')

Вы можете видеть точки в двух кластерах, где первые пять точек сгруппированы вместе, а последние пять точек сгруппированы вместе.

Пример 2

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

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

Набор данных для этой задачи можно загрузить по следующей ссылке:

Набор данных для этой задачи можно загрузить по следующей ссылке:

Поместите загруженный файл “shopping-data.csv” в папку “Datasets” каталога “D”. Чтобы сгруппировать эти данные в группы, мы выполним те же действия, что и в предыдущем разделе.

Выполните следующий сценарий для импорта нужных библиотек:

import matplotlib.pyplot as plt
import pandas as pd
%matplotlib inline
import numpy as np

Затем, чтобы импортировать набор данных для этого примера, выполните следующий код:

customer_data = pd.read_csv('D:\Datasets\shopping-data.csv')

Давайте немного изучим наш набор данных. Чтобы проверить количество записей и атрибутов, выполните следующий сценарий:

customer_data.shape

Приведенный выше скрипт вернет (200, 5) , что означает, что набор данных содержит 200 записей и 5 атрибутов.

Чтобы просмотреть набор данных, выполните функцию head() фрейма данных. Взгляните на следующий сценарий:

customer_data.head()

Результат будет выглядеть следующим образом:

Наш набор данных состоит из пяти столбцов: CustomerID, Жанр, Возраст, Годовой доход и Оценка расходов. Для просмотра результатов в двумерном пространстве признаков мы сохраним только два из этих пяти столбцов. Мы можем удалить столбец CustomerID, Жанр и Возраст. Мы сохраним столбцы Годовой доход (в тысячах долларов) и Оценка расходов (1-100). Столбец “Оценка расходов” показывает, как часто человек тратит деньги в торговом центре по шкале от 1 до 100, причем 100-это самый высокий показатель траты. Выполните следующий сценарий, чтобы отфильтровать первые три столбца из нашего набора данных:

data = customer_data.iloc[:, 3:5].values

Далее, нам нужно знать кластеры, на которые мы хотим разделить наши данные. Мы снова будем использовать библиотеку scipy для создания дендрограмм для нашего набора данных. Для этого выполните следующий сценарий:

import scipy.cluster.hierarchy as shc

plt.figure(figsize=(10, 7))
plt.title("Customer Dendograms")
dend = shc.dendrogram(shc.linkage(data, method='ward'))

В приведенном выше скрипте мы импортируем класс иерархии библиотеки scipy.cluster как shc . Класс иерархии имеет метод dendrogram , который принимает значение, возвращаемое методом linkage того же класса. Метод linkage принимает набор данных и метод минимизации расстояний в качестве параметров. Мы используем “ward” в качестве метода , поскольку он минимизирует варианты расстояний между кластерами.

Вывод приведенного выше скрипта выглядит следующим образом:

Если мы нарисуем горизонтальную линию, которая проходит через самое длинное расстояние без горизонтальной линии, мы получим 5 кластеров, как показано на следующем рисунке:

Теперь, когда мы знаем количество кластеров для нашего набора данных, следующий шаг-сгруппировать точки данных в эти пять кластеров. Для этого мы снова будем использовать класс Agglomerative Clustering библиотеки sklearn.cluster . Взгляните на следующий сценарий:

from sklearn.cluster import AgglomerativeClustering

cluster = AgglomerativeClustering(n_clusters=5, affinity='euclidean', linkage='ward')
cluster.fit_predict(data)

Вывод приведенного выше скрипта выглядит следующим образом:

array([4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4,
       3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 1, 4, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 2, 0, 2, 0, 2,
       0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 0, 2, 0, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1,
       2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2,
       0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2], dtype=int64)

Вы можете видеть метки кластеров из всех ваших точек данных. Поскольку у нас было пять кластеров, у нас есть пять меток на выходе, то есть от 0 до 4.

В качестве заключительного шага давайте построим кластеры, чтобы увидеть, как на самом деле наши данные были кластеризованы:

plt.figure(figsize=(10, 7))
plt.scatter(data[:,0], data[:,1], c=cluster.labels_, cmap='rainbow')

Вывод приведенного выше кода выглядит следующим образом:

Вы можете видеть точки данных в виде пяти кластеров. Точки данных в правом нижнем углу принадлежат клиентам с высокими зарплатами, но низкими расходами. Это те клиенты, которые тщательно тратят свои деньги. Точно так же клиенты в правом верхнем углу (зеленые точки данных) – это клиенты с высокими зарплатами и высокими расходами. Это тип клиентов, на которых ориентируются компании. Клиенты в середине (синие точки данных) – это те, у кого средний доход и средняя зарплата. К этой категории относится наибольшее количество клиентов. Компании также могут ориентироваться на этих клиентов, учитывая тот факт, что их огромное количество и т. Д.

Ресурсы

Между всеми различными пакетами Python ( pandas , matplotlib , numpy и sklearn ) в этой статье есть много информации , которую может быть трудно понять, и по этой причине мы рекомендуем проверить некоторые более подробные ресурсы по выполнению задач data science с помощью Python, такие как онлайн-курс:

Мы обнаружили, что эти ресурсы достаточно хороши, чтобы вы пришли с твердым пониманием того, как использовать их в своей собственной работе.

Вывод

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

В этой статье мы объяснили иерархическую кластеризацию с помощью двух примеров. Для получения дополнительной информации о машинном обучении и науке о данных продолжайте посещать этот сайт. Счастливого кодирования!