Понимание DBSCAN и реализация с помощью Python

ОБУЧЕНИЕ БЕЗ КОНТРОЛЯ

Понимание DBSCAN и реализация с помощью Python

В этом посте я кратко расскажу об идеях DBSCAN и его реализации в Python.

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

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

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

В этом посте я расскажу о том, как понять этот алгоритм и как реализовать его на Python. Надеюсь статья будет полезной.

Понимание DBSCAN

Из названия DBSCAN очевидно, что наиболее важной частью является слово «на основе плотности». Итак, что такое плотность? Проще говоря, мы можем понимать плотность как меру количества точек данных в указанной области. Тогда как описать «указанный район»? Мы можем использовать центральную точку с определенным значением расстояния от нее для описания заданной области. Таким образом, кластеры в DBSCAN — это «определенные области» большого количества точек данных (плотная область).

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

На самом деле, все параметры DBSCAN были упомянуты в вопросах выше.

Во-первых, eps, максимальное расстояние между двумя образцами, при котором одно считается соединенным с другим. Расстояние может быть определено любым типом функции расстояния, например, «евклидово расстояние».

Во-вторых, образцы керна, образцы, которые находятся в областях с высокой плотностью.

В-третьих, minPts — минимальное количество выборок в окрестности, при котором точка считается базовой. .

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

На приведенном выше графике мы установили minPts равным 4, что означает, что точка называется основной точкой, если минимум 4 точки (включая себя) находятся на расстоянии eps от него. Таким образом, A — это основная точка, и все остальные коричневые точки также являются основными точками, потому что все они имеют по крайней мере 4 точки в пределах eps, окружающих их.

Несмотря на то, что синие точки, такие как B, не являются основными точками из-за менее чем 4 соседних точек в eps, до них все же можно напрямую добраться из определенных основных точек. Таким образом, они принадлежат к одному и тому же кластеру этих основных точек.

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

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

Алгоритм DBSCAN

Хорошо, после понимания идеи DBSCAN, давайте обобщим алгоритм DBSCAN в следующих шагах:

1. Для каждой точки данных найдите точки в окрестности на расстоянии eps и определите основные точки как те, у которых есть как минимум minPts соседи. .

2. Определите группы связанных основных точек как кластеры.

3. Назначьте каждую неосновную точку соседнему кластеру, если она напрямую достижима из соседней базовой точки, в противном случае определите ее как выброс.

Большой eps, как правило, включает в себя больше точек в кластере, поэтому слишком большой eps будет включать все в один кластер, а слишком маленький eps вообще не приведет к кластеризации.

Слишком маленькое значение minPts не имеет смысла, поскольку оно будет рассматривать каждую точку как основную. Относительно большие minPts лучше подходят для обработки данных с большим количеством помех.

Преимущества DBSCAN

После знакомства с идеей и алгоритмом DBSCAN его преимущества очевидны.

Во-первых, DBSCAN не требует от пользователей указания количества кластеров.

Во-вторых, DBSCAN НЕ чувствителен к выбросам.

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

Но ни один неконтролируемый алгоритм не идеален. DBSCAN имеет свои ограничения. Например, было бы большой проблемой использовать DBSCAN, если плотность данных сильно различается по кластерам, потому что вы можете использовать только одну пару параметров, eps и MinPts, на одном наборе данных. Кроме того, может быть очень сложно определить eps без знания предметной области данных.

from sklearn.cluster import DBSCAN
import numpy as np
DBSCAN_cluster = DBSCAN(eps=10, min_samples=5).fit(X) 

DBSCAN_cluster.labels_