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

Что такое ДБСКАН?

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

  1. R (Радиус соседства):R, также называемый эпсилон, определяет указанный радиус, который, если он включает в себя минимальное количество экземпляров/точек внутри, называется плотной областью. эм>
  2. M (минимальное количество соседей):M определяет минимальное количество точек данных, находящихся в соседстве, для определения кластера.

Как это работает?

Давайте определим радиус (который также называется эпсилон) как две единицы. Ради простоты предположим, что радиус вокруг точки интереса составляет два сантиметра. Кроме того, давайте установим минимальные выборки или M равными шести точкам, включая точку интереса.

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

Выберем точку случайным образом. Во-первых, мы проверяем, является ли это основной точкой данных. Итак, что такое ключевой момент? Точка данных является базовой точкой, если в нашей окрестности точки есть не менее M точек. Например, поскольку в радиусе красной точки на картинке выше шесть точек, это центральная точка.

Что произойдет, если это не основная точка? Давайте еще раз посмотрим на картинку.

Теперь обратите внимание на желтую точку. В его радиусе всего пять точек, что меньше M(M=6) . Таким образом, точка, в окрестности которой содержится менее M точек данных, и которая достижима из некоторой базовой точки, называется пограничной точкой. Здесь достижимость означает, что он находится в пределах нашего расстояния от центральной точки. Это означает, что даже если желтая точка находится в пределах двух сантиметров от красной точки, сама по себе она не является центральной точкой, поскольку не имеет по крайней мере шести точек в своей окрестности. Точка, которая не является центральной или пограничной точкой, а также недостаточно близка к основной точке, называется выбросом.

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

Почему DBSCAN?

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

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

Переходим к практической реализации

Класс DBSCAN в Scikit-Learn прост в использовании. Давайте проверим это на наборе данных moons, который доступен в sklearn.datasets.

Сначала импортируйте необходимые библиотеки.

Создайте модель.

Метки всех точек теперь доступны в переменной labels_instances. Его вывод представляет собой массив, который содержит некоторый индекс кластера как -1: это означает, что алгоритм рассматривает их как аномалии/выбросы.

Индексы основных точек:

Сами основные точки:

Вывод с использованием eps=0,05:

Когда мы увеличим число eps до 0,5, мы получим:

Источники информации:

  1. Книга «Практическое машинное обучение с помощью Scikit-Learn, Keras и TensorFlow», автор Орельен Жерон.
  2. IBM.