Кластеризация данных в группы, часть 3

СТАТЬЯ

Кластеризация данных в группы, часть 3

Из Data Science Bookcamp Леонарда Апельцина

Эта серия статей из трех частей охватывает:

Кластеризация данных по централизации
Кластеризация данных по плотности
Компромиссы между алгоритмами кластеризации
Выполнение кластеризации с помощью библиотеки scikit-learn
Перебор кластеров с помощью Pandas

Получите скидку 35% на Data Science Bookcamp, введя fccapeltsin в поле кода скидки при оформлении заказа на manning.com.

Если вы пропустили их, посмотрите часть 1 и часть 2.

DBSCAN: алгоритм кластеризации для группировки данных на основе пространственной плотности

DBSCAN – это аббревиатура, обозначающая пространственную кластеризацию приложений с шумом на основе плотности. Это смехотворно длинное название для очень простой техники:

Выберите случайную point координату из data списка.
Получить всех соседей на расстоянии epsilon от этого point.
Если обнаружено менее min_points соседей, повторите шаг 1, используя другую случайную точку. В противном случае сгруппируйте point и его соседей в один кластер.
Итеративно повторите шаги 2 и 3 для всех вновь обнаруженных соседей. Все соседние плотные точки объединяются в кластер. Итерации завершаются после того, как кластер перестает расширяться.
После извлечения всего кластера повторите шаги 1–4 для всех точек данных, плотность которых еще не была проанализирована.

Процедура DBSCAN может быть запрограммирована менее чем в 20 строках кода. Однако любая базовая реализация будет работать очень медленно в нашем списке rocks. Программирование быстрой реализации требует некоторых очень тонких оптимизаций, которые улучшают скорость обхода соседей и выходят за рамки этой книги. К счастью, нам не нужно перестраивать алгоритм с нуля: scikit-learn предоставляет быстрый класс DBSCAN, который мы можем импортировать из sklearn.cluster. Давайте импортируем и инициализируем класс, назначив epsilon и min_points с помощью параметров eps и min_samples. Затем мы используем DBSCAN для кластеризации наших трех колец (рис. 13).

Листинг 21. Использование DBSCAN для объединения колец

from sklearn.cluster import DBSCAN
 cluster_model = DBSCAN(eps=epsilon, min_samples=min_points) (1)
 rock_clusters = cluster_model.fit_predict(rocks) (2)
 colors = [['g', 'y', 'k'][cluster] for cluster in rock_clusters]
 plt.scatter(x_coordinates, y_coordinates, color=colors)
 plt.show()

❶ Создает объект cluster_model для выполнения кластеризации по плотности. Значение эпсилон 0,1 передается с использованием параметра eps. Значение min_points, равное 10, передается с использованием параметра min_samples.

❷ Группирует кольца камней по плотности и возвращает назначенный кластер для каждого камня.

DBSCAN успешно идентифицировал три каменных кольца. Алгоритм преуспел там, где K-средних не удалось.

Сравнение DBSCAN и K-средних

DBSCAN — это выгодный алгоритм для кластеризации данных, состоящих из изогнутых и плотных форм. Кроме того, в отличие от K-средних, алгоритм не требует аппроксимации количества кластеров перед выполнением. Кроме того, DBSCAN может фильтровать случайные выбросы, расположенные в разреженных областях пространства. Например, если мы добавим выброс, расположенный за границей колец, DBSCAN присвоит ему идентификатор кластера -1. Отрицательное значение указывает на то, что выброс не может быть сгруппирован с остальной частью набора данных.

В отличие от K-средних, подогнанную модель DBSCAN нельзя повторно применить к совершенно новым данным. Вместо этого нам нужно объединить новые и старые данные и выполнить кластеризацию с нуля. Это связано с тем, что вычисленные центры K-средних можно легко сравнить с дополнительными точками данных. Однако дополнительные точки данных могут повлиять на распределение плотности ранее просмотренных данных, что вынуждает DBSCAN пересчитывать все кластеры.

Листинг 22. Поиск выбросов с помощью DBSCAN

noisy_data = rocks + [[1000, -1000]]
 clusters = DBSCAN(eps=epsilon,
                   min_samples=min_points).fit_predict(noisy_data)
 assert clusters[-1] == -1

Другое преимущество метода DBSCAN заключается в том, что он не зависит от среднего значения. Между тем, алгоритм K-средних требует, чтобы мы вычисляли средние координаты сгруппированных точек. Как мы обсуждали в разделе 5, эти средние координаты минимизируют сумму квадратов расстояний до центра. Свойство минимизации выполняется, только если квадраты расстояний евклидовы. Таким образом, если наши координаты не евклидовы, среднее значение не очень полезно, и алгоритм K-средних не следует применять. Однако евклидово расстояние — не единственная метрика для измерения расстояния между точками — для определения расстояния существует бесконечное количество метрик. Мы рассмотрим некоторые из них в следующем подразделе. В процессе мы узнаем, как интегрировать эти показатели в наши выходные данные кластеризации DBSCAN.

Кластеризация на основе неевклидова расстояния

Предположим, что мы находимся на Манхэттене и хотим узнать расстояние пешком от Эмпайр Стейт Билдинг до Коламбус Серкл. Эмпайр Стейт Билдинг расположен на пересечении 34-й улицы и Пятой авеню. Между тем, Columbus Circle находится на пересечении 57-й улицы и Восьмой авеню. Улицы и проспекты на Манхэттене всегда перпендикулярны друг другу. Это позволяет нам представить Манхэттен в виде двумерной системы координат, в которой улицы расположены по оси x, а проспекты — по оси y. В этом представлении Эмпайр-Стейт-Билдинг расположен в координатах (34, 5), а Колумбус-Серкл — в координатах (57, 8). Мы можем легко вычислить прямолинейное евклидово расстояние между двумя координатными точками. Однако эта окончательная длина будет непроходимой, потому что высокие стальные здания занимают территорию, очерченную каждым городским кварталом. Более правильное решение — ограничиться траекторией по перпендикулярным тротуарам, образующим сетку города. Такой маршрут требует, чтобы мы прошли три квартала между Пятой авеню и Третьей авеню, а затем 23 квартала между 34-й и 57-й улицами, всего 26 кварталов. Средняя длина квартала Манхэттена составляет 0,17 мили, поэтому мы можем оценить пройденное расстояние как 4,42 мили. Давайте вычислим это пешеходное расстояние напрямую, используя обобщенную функцию manhattan_distance.

Листинг 23. Вычисление манхэттенского расстояния

def manhattan_distance(point_a, point_b):
     num_blocks = np.sum(np.absolute(point_a - point_b))
     return 0.17 * num_blocks
  
 x = np.array([34, 5])
 y = np.array([57, 8])
 distance = manhattan_distance(x, y) (1)
  
 print(f"Manhattan distance is {distance} miles")

❶ Мы также можем получить эти выходные данные, импортировав cityblock из scipy.spatial.distance, а затем запустив .17 * cityblock(x, y).

Manhattan distance is 4.42 miles

Теперь предположим, что мы хотим сгруппировать более двух местоположений на Манхэттене. Предположим, что каждый кластер содержит точку, находящуюся в пределах одной мили от трех других сгруппированных точек. Это предположение позволяет нам применять кластеризацию DBSCAN с использованием класса DBSCAN scikit-learn. Мы устанавливаем eps в 1 и min_samples в 3 во время инициализации DBSCAN. Кроме того, мы передаем metric= manhattan_distance в метод инициализации. Параметр metric заменяет евклидово расстояние на нашу пользовательскую метрику расстояния, поэтому расстояние кластеризации правильно отражает ограничения на основе сетки в пределах города. Следующий код группирует координаты Манхэттена и наносит их на сетку вместе с их обозначениями кластеров (рис. 14).

Листинг 24. Кластеризация с использованием манхэттенского расстояния

points = [[35, 5], [33, 6], [37, 4], [40, 7], [45, 5]]
 clusters = DBSCAN(eps=1, min_samples=3,
                   metric=manhattan_distance).fit_predict(points) ❶
  
 for i, cluster in enumerate(clusters):
     point = points[i]
     if cluster == -1:
         print(f"Point at index {i} is an outlier")
         plt.scatter(point[0], point[1], marker='x', color='k') ❷
     else:
         print(f"Point at index {i} is in cluster {cluster}")
         plt.scatter(point[0], point[1], color='g')
  
 plt.grid(True, which='both', alpha=0.5) ❸
 plt.minorticks_on()
  
  
 plt.show()

❶ Функция manhattan_distance передается в DBSCAN через параметр metric.

❷ Выбросы наносятся на график с помощью крестообразных маркеров.

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

Point at index 0 is in cluster 0
 Point at index 1 is in cluster 0
 Point at index 2 is in cluster 0
 Point at index 3 is an outlier
 Point at index 4 is an outlier

Первые три местоположения попадают в один кластер, а остальные точки являются выбросами. Могли бы мы обнаружить этот кластер с помощью алгоритма К-средних? Возможно. В конце концов, координаты нашего блока Манхэттена можно усреднить, что делает их совместимыми с реализацией K-средних. Что, если мы заменим Манхэттенское расстояние на другую метрику, где средние координаты получить не так просто? Давайте определим нелинейную метрику расстояния со следующими свойствами: две точки разделены на 0 единиц, если все их элементы отрицательны, на 2 единицы, если все их элементы неотрицательны, и на 10 единиц в противном случае. Учитывая эту нелепую меру расстояния, можем ли мы вычислить среднее значение любых двух произвольных точек? Мы не можем, и К-средства не могут быть применены. Слабость алгоритма в том, что он зависит от существования среднего расстояния. В отличие от K-средних, алгоритм DBSCAN не требует, чтобы наша функция расстояния была линейно делимой. Таким образом, мы можем легко запустить кластеризацию DBSCAN, используя нашу смехотворную метрику расстояния.

Листинг 25. Кластеризация с использованием смехотворной меры расстояния

def ridiculous_measure(point_a, point_b):
     is_negative_a = np.array(point_a) < 0 ❶
     is_negative_b = np.array(point_b) < 0
     if is_negative_a.all() and is_negative_b.all(): ❷
         return 0
     elif is_negative_a.any() or is_negative_b.any(): ❸
         return 10
     else: ❹
         return 2
  
 points = [[-1, -1], [-10, -10], [-1000, -13435], [3,5], [5,-7]]
  
 clusters = DBSCAN(eps=.1, min_samples=2,
                   metric=ridiculous_measure).fit_predict(points)
  
 for i, cluster in enumerate(clusters):
     point = points[i]
     if cluster == -1:
         print(f"{point} is an outlier")
     else:
         print(f"{point} falls in cluster {cluster}")

❶ Возвращает логический массив, где is_negative_a[i] имеет значение True, если point_a[i] ‹ 0

❷ Все элементы point_a и point_b отрицательны.

❸ Отрицательный элемент существует, но не все элементы являются отрицательными.

❹ Все элементы неотрицательны.

[-1, -1] falls in cluster 0
 [-10, -10] falls in cluster 0
 [-1000, -13435] falls in cluster 0
 [3, 5] is an outlier
 [5, -7] is an outlier

Запуск DBSCAN с нашей метрикой ridiculous_measure приводит к кластеризации отрицательных координат в одну группу. Все остальные координаты рассматриваются как выбросы. Эти результаты не являются концептуально практичными, но гибкость в отношении выбора показателей заслуживает высокой оценки. Мы не ограничены в выборе метрики! Мы могли бы, например, установить метрику для вычисления расстояния прохождения на основе кривизны Земли. Такой показатель был бы особенно полезен для кластеризации географических местоположений.

Методы кластеризации DBSCAN

dbscan_model = DBSCAN(eps=epsilon, min_samples=min_points) — Создает модель DBSCAN для кластеризации по плотности. Плотная точка определяется как имеющая не менее min_points соседей на расстоянии epsilon. Соседи считаются частью того же кластера, что и точка.
clusters = dbscan_model.fit_predict(data) — выполняет DBSCAN для введенных данных, используя инициализированный объект DBSCAN. Массив clusters содержит идентификаторы кластеров. Идентификатор кластера data[i] равен clusters[i]. Некластеризованным точкам выбросов присваивается идентификатор -1.
clusters = DBSCAN(eps=epsilon, min_samples=min_points).fit_predict(data) — выполняет DBSCAN в одной строке кода и возвращает результирующие кластеры.
dbscan_model = DBSCAN(eps=epsilon, min_samples=min_points, metric=metric_function) — создает модель DBSCAN, в которой метрика расстояния определяется пользовательской функцией метрики. Метрика расстояния metric_function не обязательно должна быть евклидовой.

DBSCAN имеет определенные недостатки. Алгоритм предназначен для обнаружения кластеров с похожим распределением плотности точек. Однако реальные данные различаются по плотности. Например, пиццерии на Манхэттене распределены более плотно, чем пиццерии в округе Ориндж, штат Калифорния. Таким образом, у нас могут возникнуть проблемы с выбором параметров плотности, которые позволят нам сгруппировать магазины в обоих местах. Это подчеркивает еще одно ограничение алгоритма: DBSCAN требует значимых значений для параметров eps и min_samples. В частности, различные входные данные eps сильно повлияют на качество кластеризации. К сожалению, не существует ни одной надежной процедуры оценки соответствующего eps. Хотя некоторые эвристики иногда упоминаются в литературе, их польза минимальна. Большую часть времени мы должны полагаться на наше внутреннее понимание проблемы, чтобы назначить практические входные данные для двух параметров DBSCAN. Например, если бы мы кластеризовали набор географических местоположений, наши значения eps и min_samples зависели бы от того, разбросаны ли местоположения по всему земному шару или они ограничены одним географическим регионом. В каждом случае наше понимание плотности и расстояния будет разным. Вообще говоря, если мы группируем случайные города, разбросанные по Земле, мы можем установить параметры min_samples и eps равными трем городам и 250 милям соответственно. Это предполагает, что каждый кластер содержит город в пределах 250 миль по крайней мере от трех других кластеризованных городов. Для более регионального распределения местоположения требуется меньшее значение eps.

Анализ кластеров с помощью Pandas

До сих пор мы разделяли входные данные и выходные данные кластеризации. Например, в нашем анализе каменных колец входные данные находятся в списке rocks, а выходные данные кластеризации — в массиве rock_clusters. Отслеживание как координат, так и кластеров требует от нас сопоставления индексов между входным списком и выходным массивом. Таким образом, если мы хотим извлечь все породы в кластере 0, мы должны получить все экземпляры rocks[i], где rock_clusters[i] == 0. Этот индексный анализ запутан. Мы можем более интуитивно анализировать сгруппированные породы, объединяя координаты и кластеры вместе в одной таблице Pandas.

Следующий код создает таблицу Pandas с тремя столбцами: X, Y и Cluster. Каждая i-я строка в таблице содержит координату x, координату y и группу камней, расположенную в точке rocks[i].

Листинг 26. Сохранение кластеризованных координат в таблице

import pandas as pd
 x_coordinates, y_coordinates = np.array(rocks).T
 df = pd.DataFrame({'X': x_coordinates, 'Y': y_coordinates,
                    'Cluster': rock_clusters})

Наша таблица Pandas позволяет нам легко получить доступ к камням в любом кластере. Давайте нанесем на график породы, попадающие в кластер 0, используя методы, описанные в разделе 8 (рисунок 15).

Листинг 27. Отображение одного кластера с помощью Pandas

df_cluster = df[df.Cluster == 0] ❶
 plt.scatter(df_cluster.X, df_cluster.Y) ❷
 plt.show()

❶ Выберите только те строки, в которых значение столбца "Кластер" равно 0.

❷ Выводит на график столбцы X и Y выбранных строк. Обратите внимание, что мы также выполняем точечную диаграмму, запустив df_cluster.plot.scatter(x=’X’, y=’Y’).

Pandas позволяет нам получить таблицу, содержащую элементы из любого отдельного кластера. В качестве альтернативы мы можем захотеть получить несколько таблиц, где каждая таблица сопоставляется с идентификатором кластера. В Pandas это делается вызовом df.groupby('Cluster'). Метод groupby создаст три таблицы: по одной для каждого кластера. Он вернет итерацию по сопоставлениям между идентификаторами кластера и таблицами. Давайте воспользуемся методом groupby для перебора наших трех кластеров. Впоследствии мы нанесем породы в кластере 1 и кластере 2, но не в кластере 0 (рис. 16).

Вызов df.groupby('Cluster') возвращает больше, чем просто итерацию: он возвращает объект DataFrameGroupBy, который предоставляет дополнительные методы для фильтрации и анализа кластера.

Листинг 28. Перебор кластеров с помощью Pandas

for cluster_id, df_cluster in df.groupby('Cluster'): ❶
     if cluster_id == 0:
         print(f"Skipping over cluster {cluster_id}")
         continue
  
     print(f"Plotting cluster {cluster_id}")
     plt.scatter(df_cluster.X, df_cluster.Y)
  
  
 plt.show()
 Skipping over cluster 0
 Plotting cluster 1
 Plotting cluster 2

❶ Каждый элемент итерируемого объекта, возвращаемый функцией df.groupby(‘Cluster’), является кортежем. Первый элемент кортежа — это идентификатор кластера, полученный из df.Cluster. Второй элемент — это таблица, состоящая из всех строк, где df.Cluster соответствует идентификатору кластера.

Метод Pandas groupby позволяет нам итеративно исследовать различные кластеры. Это может оказаться полезным в нашем анализе тематического исследования 3.

Сводка

Алгоритм K-средних группирует введенные данные путем поиска K центроидов. Эти центроиды представляют средние координаты обнаруженных групп данных. K-средние инициализируются путем выбора K случайных центроидов. Затем каждая точка данных группируется на основе ее ближайшего центроида, и центроиды итеративно пересчитываются до тех пор, пока они не сойдутся в стабильных местоположениях.
K-средние гарантированно сходятся к решению. Однако такое решение может быть не оптимальным.
K-means требует евклидовых расстояний, чтобы различать точки. Алгоритм не предназначен для кластеризации неевклидовых координат.
После выполнения кластеризации K-средних мы можем вычислить инерцию результата. Инерция равна сумме квадратов расстояний между каждой точкой данных и ее ближайшим центром.
При построении графика инерции в диапазоне значений K создается изогнутая диаграмма. Компонент колена на графике в форме колена должен быть направлен вниз до приемлемого значения K. Используя график локтя, мы можем эвристически выбрать значимые входные данные K для K-средних.
Алгоритм DBSCAN группирует данные по плотности. Плотность определяется параметрами epsilon и min_points. Если точка находится на расстоянии epsilon от min_point соседей, то эта точка находится в плотной области пространства. Каждый сосед точки в плотной области пространства также группируется в этом пространстве. DBSCAN итеративно расширяет границы плотной области пространства до тех пор, пока не будет обнаружен полный кластер.
Алгоритм DBSCAN не группирует точки в неплотных регионах. Они рассматриваются как выбросы.
DBSCAN — это выгодный алгоритм для кластеризации данных, состоящих из изогнутых и плотных форм.
DBSCAN может кластеризоваться с использованием произвольных неевклидовых расстояний.
Не существует надежной эвристики для выбора подходящих параметров epsilon и min_points. Однако, если мы хотим сгруппировать глобальные города, мы можем установить два параметра на 250 миль и три города соответственно.
Хранение кластеризованных данных в таблице Pandas позволяет нам интуитивно перебирать кластеры с помощью метода groupby.

Это все для этой серии. Если вы хотите узнать больше о книге, ознакомьтесь с ней на платформе Мэннинга liveBook здесь.

Кластеризация данных в группы, часть 3

СТАТЬЯ