DBSCAN с помощью Scikit-Learn на Python

Введение

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

Изучая данные из разных групп учащихся, вы столкнулись с тремя вариантами распределения баллов, как в пунктах 1, 2 и 3 ниже:

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

На участке 2 есть круглая масса фиолетовых точек, еще одна из оранжевых точек, а также четыре серые точки, которые находятся далеко от всех остальных.

А на графике 3 мы видим четыре скопления точек: фиолетовые, синие, оранжевые, розовые и еще три отдаленные серые точки.

Теперь, если бы вы выбрали модель, которая могла бы понимать новые данные об учащихся и определять похожие группы, существует ли алгоритм кластеризации, который мог бы дать интересные результаты для такого рода данных?

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

Алгоритм на основе плотности, который может отфильтровывать шум, например ДБСКАН (Dчувство-BAsed Sвнутренний Cсияние Aприложения с Noise) — отличный выбор для ситуаций с более плотными участками, округлыми формами и шумом.

О DBSCAN

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

Основная идея DBSCAN заключается в том, что существует минимальное количество точек, которые будут находиться в пределах определенного расстояния или radius от самой «центральной» точки кластера, называемой основная точка. Точки в пределах этого радиуса являются точками соседства, а точки на краю этого соседства являются пограничные пункты or граничные точки. Радиус или соседнее расстояние называется район Эпсилон, ε-окрестность или просто ε (символ греческой буквы эпсилон).

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

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

Чтобы найти основную точку, DBSCAN сначала выберет точку случайным образом, сопоставит все точки в пределах ее ε-окрестности и сравнит количество соседей выбранной точки с минимальным количеством точек. Если выбранная точка имеет количество соседей, равное или большее, чем минимальное количество точек, она будет помечена как основная точка. Эта центральная точка и ее соседние точки составят первый кластер.

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

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

Интересно узнать, как работает алгоритм DBSCAN, хотя, к счастью, нет необходимости кодировать алгоритм, поскольку в библиотеке Python Scikit-Learn уже есть реализация.

Посмотрим, как это работает на практике!

Импорт данных для кластеризации

Чтобы увидеть, как DBSCAN работает на практике, мы немного изменим проекты и воспользуемся небольшим набором данных о клиентах с жанром, возрастом, годовым доходом и оценкой расходов 200 клиентов.

Оценка расходов варьируется от 0 до 100 и показывает, как часто человек тратит деньги в торговом центре по шкале от 1 до 100. Другими словами, если у клиента оценка 0, он никогда не тратит деньги, а если оценка 100, они самые высокие транжиры.

После загрузки набора данных вы увидите, что это файл CSV (значения, разделенные запятыми), который называется шопинг-data.csv, мы загрузим его в DataFrame с помощью Pandas и сохраним в customer_data переменная:

import pandas as pd path_to_file = '../../datasets/dbscan/dbscan-with-python-and-scikit-learn-shopping-data.csv'
customer_data = pd.read_csv(path_to_file)

Чтобы взглянуть на первые пять строк наших данных, вы можете выполнить customer_data.head():

Это приводит к:

 CustomerID Genre Age Annual Income (k$) Spending Score (1-100)
0 1 Male 19 15 39
1 2 Male 21 15 81
2 3 Female 20 16 6
3 4 Female 23 16 77
4 5 Female 31 17 40

Изучив данные, мы можем увидеть идентификационные номера клиентов, жанр, возраст, доходы в тысячах долларов и оценки расходов. Имейте в виду, что некоторые или все эти переменные будут использоваться в модели. Например, если бы мы использовали Age и Spending Score (1-100) в качестве переменных для DBSCAN, который использует метрику расстояния, важно привести их к общему масштабу, чтобы избежать внесения искажений, поскольку Age измеряется годами и Spending Score (1-100) имеет ограниченный диапазон от 0 до 100. Это означает, что мы будем выполнять какое-то масштабирование данных.

Мы также можем проверить, нуждаются ли данные в какой-либо дополнительной предварительной обработке, помимо масштабирования, проверив, согласован ли тип данных, и проверив, есть ли какие-либо пропущенные значения, которые необходимо обработать, выполнив Panda. info() Метод:

customer_data.info()

Это отображает:

<class 'pandas.core.frame.DataFrame'>
RangeIndex: 200 entries, 0 to 199
Data columns (total 5 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 CustomerID 200 non-null int64 1 Genre 200 non-null object 2 Age 200 non-null int64 3 Annual Income (k$) 200 non-null int64 4 Spending Score (1-100) 200 non-null int64 dtypes: int64(4), object(1)
memory usage: 7.9+ KB

Мы можем заметить, что пропущенных значений нет, потому что для каждой функции клиента есть 200 ненулевых записей. Мы также можем видеть, что только столбец жанра имеет текстовое содержимое, так как это категориальная переменная, которая отображается как object, а все остальные функции являются числовыми типа int64. Таким образом, с точки зрения согласованности типов данных и отсутствия нулевых значений наши данные готовы к дальнейшему анализу.

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

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

Визуализация данных

С помощью Seaborn pairplot(), мы можем построить график разброса для каждой комбинации признаков. С CustomerID это просто идентификация, а не функция, мы удалим ее с помощью drop() перед нанесением:

import seaborn as sns customer_data = customer_data.drop('CustomerID', axis=1) sns.pairplot(customer_data);

Это выводит:

Глядя на комбинацию функций, созданных pairplot, график Annual Income (k$) Spending Score (1-100) кажется, отображает около 5 групп точек. Это кажется наиболее многообещающей комбинацией функций. Мы можем создать список с их именами, выбрать их из customer_data DataFrame и сохраните выбор в customer_data переменная снова для использования в нашей будущей модели.

selected_cols = ['Annual Income (k$)', 'Spending Score (1-100)']
customer_data = customer_data[selected_cols]

После выбора столбцов мы можем выполнить масштабирование, описанное в предыдущем разделе. Чтобы привести объекты к одному масштабу или стандартизировать их, мы можем импортировать Scikit-Learn's StandardScaler, создайте его, подгоните наши данные, чтобы вычислить его среднее значение и стандартное отклонение, и преобразуйте данные, вычитая его среднее значение и разделив его на стандартное отклонение. Это можно сделать за один шаг с помощью fit_transform() Метод:

from sklearn.preprocessing import StandardScaler ss = StandardScaler() scaled_data = ss.fit_transform(customer_data)

Переменные теперь масштабированы, и мы можем изучить их, просто распечатав содержимое файла scaled_data переменная. Кроме того, мы также можем добавить их в новый scaled_customer_data DataFrame вместе с именами столбцов и использовать head() снова метод:

scaled_customer_data = pd.DataFrame(columns=selected_cols, data=scaled_data)
scaled_customer_data.head()

Это выводит:

 Annual Income (k$) Spending Score (1-100)
0 -1.738999 -0.434801
1 -1.738999 1.195704
2 -1.700830 -1.715913
3 -1.700830 1.040418
4 -1.662660 -0.395980 

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

Выбор Мин. Образцы и Эпсилон

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

$$
текст {мин. точки} >= текст{размеры данных} + 1
$$

Размеры — это количество столбцов в кадре данных, мы используем 2 столбца, поэтому мин. баллы должны быть либо 2+1, то есть 3, либо выше. Для этого примера воспользуемся 5 мин. точки.

$$
text{5 (мин. точек)} >= text{2 (размеры данных)} + 1
$$

Теперь для выбора значения ε существует метод, в котором Ближайшие соседи Алгоритм используется для нахождения расстояний заранее определенного числа ближайших точек для каждой точки. Это предопределенное количество соседей является мин. точек, которые мы только что выбрали, минус 1. Итак, в нашем случае алгоритм найдет 5-1 или 4 ближайшие точки для каждой точки наших данных. это k-соседи и наш k равно 4

$$
текст{k-соседей} = текст{мин. баллы} – 1
$$

Найдя соседей, мы упорядочим их расстояния от наибольшего к наименьшему и нанесем расстояния по оси y и точкам по оси x. Глядя на график, мы обнаружим, где он напоминает изгиб локтя, а точка оси Y, которая описывает этот изгиб локтя, является предполагаемым значением ε.

Чтобы выполнить эти шаги, мы можем импортировать алгоритм, подогнать его к данным, а затем мы можем извлечь расстояния и индексы каждой точки с помощью kneighbors() Метод:

from sklearn.neighbors import NearestNeighbors
import numpy as np nn = NearestNeighbors(n_neighbors=4) nbrs = nn.fit(scaled_customer_data)
distances, indices = nbrs.kneighbors(scaled_customer_data)

Найдя расстояния, мы можем отсортировать их от большего к меньшему. Поскольку первый столбец массива расстояний имеет точку саму на себя (это означает, что все они равны 0), а второй столбец содержит наименьшие расстояния, за которым следует третий столбец с большими расстояниями, чем второй, и так далее, мы можем выбрать только значения второго столбца и сохранить их в distances переменная:

distances = np.sort(distances, axis=0)
distances = distances[:,1] 

Теперь, когда у нас есть отсортированные наименьшие расстояния, мы можем импортировать matplotlib, начертите расстояния и нарисуйте красной линией место «изгиба локтя»:

import matplotlib.pyplot as plt plt.figure(figsize=(6,3))
plt.plot(distances)
plt.axhline(y=0.24, color='r', linestyle='--', alpha=0.4) plt.title('Kneighbors distance graph')
plt.xlabel('Data points')
plt.ylabel('Epsilon value')
plt.show();

Вот результат:

Обратите внимание, что при проведении линии мы узнаем значение ε, в данном случае это 0.24.

Наконец, у нас есть точки минимума и ε. С обеими переменными мы можем создать и запустить модель DBSCAN.

Создание модели DBSCAN

Чтобы создать модель, мы можем импортировать ее из Scikit-Learn, создать ее с ε, который совпадает с eps аргумент, а минимум точек, к которому относится mean_samples аргумент. Затем мы можем сохранить его в переменной, назовем ее dbs и подогнать его к масштабированным данным:

from sklearn.cluster import DBSCAN dbs = DBSCAN(eps=0.24, min_samples=5)
dbs.fit(scaled_customer_data)

Точно так же наша модель DBSCAN была создана и обучена на данных! Для извлечения результатов мы обращаемся к labels_ свойство. Мы также можем создать новый labels столбца в scaled_customer_data dataframe и заполните его предсказанными метками:

labels = dbs.labels_ scaled_customer_data['labels'] = labels
scaled_customer_data.head()

Это конечный результат:

 Annual Income (k$) Spending Score (1-100) labels
0 -1.738999 -0.434801 -1
1 -1.738999 1.195704 0
2 -1.700830 -1.715913 -1
3 -1.700830 1.040418 0
4 -1.662660 -0.395980 -1

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

labels_list = list(scaled_customer_data['labels'])
n_noise = labels_list.count(-1)
print("Number of noise points:", n_noise)

Это выводит:

Number of noise points: 62

Мы уже знаем, что 62 точки наших исходных данных из 200 точек считались шумом. Это много шума, что указывает на то, что, возможно, кластеризация DBSCAN не рассматривала многие точки как часть кластера. Что произошло, мы поймем вскоре, когда нанесем данные на график.

Первоначально, когда мы наблюдали за данными, казалось, что они состоят из 5 кластеров точек. Чтобы узнать, сколько кластеров сформировал DBSCAN, мы можем подсчитать количество меток, которые не равны -1. Есть много способов написать этот код; здесь мы написали цикл for, который также будет работать для данных, в которых DBSCAN обнаружил много кластеров:

total_labels = np.unique(labels) n_labels = 0
for n in total_labels: if n != -1: n_labels += 1
print("Number of clusters:", n_labels)

Это выводит:

Number of clusters: 6

Мы видим, что алгоритм предсказал, что данные будут иметь 6 кластеров со многими точками шума. Давайте визуализируем это, построив его с помощью Seaborn scatterplot:

sns.scatterplot(data=scaled_customer_data, x='Annual Income (k$)', y='Spending Score (1-100)', hue='labels', palette='muted').set_title('DBSCAN found clusters');

Это приводит к:

Глядя на график, мы видим, что DBSCAN захватил точки, которые были более плотно связаны, а точки, которые можно было считать частью одного и того же кластера, были либо шумом, либо считались формирующими другой меньший кластер.

Если мы выделим кластеры, обратите внимание, как DBSCAN полностью получает кластер 1, то есть кластер с меньшим расстоянием между точками. Затем он получает части кластеров 0 и 3, где точки расположены близко друг к другу, рассматривая более разнесенные точки как шум. Он также рассматривает точки в нижней левой половине как шум и разбивает точки в нижней правой части на 3 кластера, снова захватывая кластеры 4, 2 и 5, где точки расположены ближе друг к другу.

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

Оценка алгоритма

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

Во-первых, мы можем импортировать silhouette_score из Scikit-Learn, затем передайте ему наши столбцы и метки:

from sklearn.metrics import silhouette_score s_score = silhouette_score(scaled_customer_data, labels)
print(f"Silhouette coefficient: {s_score:.3f}")

Это выводит:

Silhouette coefficient: 0.506

Судя по этому показателю, кажется, что DBSCAN может захватить примерно 50% данных.

Заключение

Преимущества и недостатки DBSCAN

DBSCAN — это уникальный алгоритм или модель кластеризации.

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

Это требует от нас указать минимальные точки и ε, но нет необходимости заранее указывать количество кластеров, как, например, в K-Means. Его также можно использовать с очень большими базами данных, поскольку он был разработан для многомерных данных.

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

Расширения DBSCAN

Есть и другие алгоритмы, например Иерархический DBSCAN (HDBSCAN) и Пункты заказа для определения структуры кластеризации (OPTICS), которые считаются расширениями DBSCAN.

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

• SEO-контент и PR-распределение. Получите усиление сегодня.
• Платоблокчейн. Интеллект метавселенной Web3. Расширение знаний. Доступ здесь.
• Источник: https://stackabuse.com/dbscan-with-scikit-learn-in-python/